TurboQuant From Scratch on Real KV Tensors — What 3 Bits Actually Cost, and Why the Forks Beat the Paper's Layout

TurboQuant From Scratch on Real KV Tensors — What 3 Bits Actually Cost, and Why the Forks Beat the Paper's Layout

Every TurboQuant number you have read so far — ours included — came from someone else's kernel. This post removes that layer. We implement PolarQuant (TurboQuant's Algorithm 1) in ~60 lines of PyTorch, plug it into a HuggingFace cache so the model attends over *exactly* what a compressed cache would hold, and measure on real KV tensors from Llama-3.2-1B and Qwen3-8B: reconstruction error, attention-distribution distortion, and end-to-end perplexity — across bits, norm correction, the QJL residual, K/V asymmetry, and the block-32 layout the llama.cpp forks quietly adopted.

Three findings that do not match the folklore:

1. 3-bit keys and values are not free. +10% perplexity on Qwen3-8B, +34% on Llama-3.2-1B with one norm per head vector.
2. The QJL residual stage is not useless — it's just not worth it *at 4 bits*. At 2–3 bits it buys 1–17 points of perplexity back.
3. Block-32 is not a parallelism trick. Giving each 32-value block its own norm cuts the 3-bit penalty from +10.3% to +6.3% on Qwen3-8B. That, not the rotation, is most of the gap between the paper's layout and the forks' numbers.

This is Part 6 of our TurboQuant series. Part 3 covers what shipped where; Part 5 benchmarks the CUDA fork on the same model.

1. Why Measure This Way

There are two ways to evaluate a KV-cache quantizer. The paper's way is vector-level: draw vectors, quantize, report distortion. The serving-engine way is end-to-end: run a benchmark through a kernel. Both hide something. Vector distortion doesn't tell you what the *model* does with distorted keys; a kernel benchmark bundles the algorithm with layout decisions, outlier handling, and implementation shortcuts that nobody documents.

Our setup sits in between. We write the algorithm ourselves, then fake-quantize — quantize and immediately dequantize — every key and value as it enters the cache during a forward pass. The tensors are not smaller, but they are numerically identical to what a real compressed cache would return, so the perplexity we measure is the perplexity a real implementation of the same math would get. Layout choices become explicit knobs instead of hidden defaults.

class PolarQuantCache(DynamicCache):
    def update(self, key_states, value_states, layer_idx, cache_kwargs=None):
        key_states   = self.qk.fake_quant(key_states)
        value_states = self.qv.fake_quant(value_states)
        return super().update(key_states, value_states, layer_idx, cache_kwargs)

Everything below runs on one A100. Perplexity is teacher-forced over 16,384 tokens of wikitext-2 in 2,048-token chunks; every token in a chunk attends over quantized keys and values.

2. The Algorithm in 60 Lines

PolarQuant-MSE does four things per vector:

1. Split direction from magnitude. Store ‖x‖ as one fp16 scalar; quantize the unit vector u = x / ‖x‖.
2. Rotate with a randomized Walsh–Hadamard transform, y = H·D·u (D = random signs). After rotation every coordinate of a unit vector in R^d is approximately N(0, 1/d), regardless of the model.
3. Scalar-quantize each coordinate with a Lloyd–Max codebook computed *once* for N(0, 1/d) at the chosen bit width. No calibration data — the codebook depends only on d.
4. Un-rotate on the way out.

Two optional stages sit on top:

• Norm correction: after dequantization, rescale so the reconstructed direction has unit length again. Free; one division.
• QJL residual: take the residual r = u − Q(u), project through a random Gaussian matrix, keep only the sign bits (1 bit per coordinate), and use the standard QJL inner-product estimator to add a correction on the way out.

def fwht(x):                                  # orthonormal Walsh-Hadamard, last dim
    d = x.shape[-1]; h = 1; y = x.clone()
    while h < d:
        y = y.view(*y.shape[:-1], d // (2*h), 2, h)
        a, b = y[..., 0, :], y[..., 1, :]
        y = torch.stack((a + b, a - b), dim=-2).reshape(*x.shape[:-1], d); h *= 2
    return y / math.sqrt(d)

def fake_quant(self, x):
    norm = x.norm(dim=-1, keepdim=True)
    y    = fwht((x / norm) * self.sign)      # rotate the unit vector
    yq   = self.code[torch.bucketize(y, self.bounds)]   # Lloyd-Max lookup
    uq   = fwht(yq) * self.sign               # un-rotate
    if self.qjl:                              # optional 1-bit residual
        r = x / norm - uq
        uq = uq + math.sqrt(math.pi/2) * r.norm(dim=-1, keepdim=True) * (torch.sign(r @ self.S.T) @ self.S) / self.dim
    if self.nc:                               # optional norm correction
        uq = uq / uq.norm(dim=-1, keepdim=True)
    return uq * norm

That is the whole method. The full script, with the cache wrapper and the measurement harness, is linked at the end.

3. Sanity Check: The Quantizer Hits the Theoretical Bound

Before touching a model, we check the quantizer against theory. For a Gaussian coordinate, the optimal (Lloyd–Max) scalar quantizer has relative distortion of about 0.118 at 2 bits, 0.0345 at 3 bits, and 0.0095 at 4 bits.

Measured on real Qwen3-8B keys (head dim 128, eight layers sampled):

Real KV vectors quantize *at* the Gaussian bound. The rotation is doing what the paper says it does: it makes model-specific key distributions look like the distribution the codebook was built for. Nothing to tune.

4. Finding 1: What 3 Bits Cost End-to-End

!Perplexity change vs bits — Qwen3-8B

Perplexity relative to bf16 KV, one norm per 128-dim head vector, norm correction on:

Three things stand out.

Vector distortion hides the damage. A 3.2% relative MSE on keys becomes a 10% perplexity hit on an 8B model and a 34% hit on a 1B one. The reason is visible in the attention distributions: KL(attention ‖ quantized attention) at 3 bits is 0.18 nats per query on Qwen3-8B — small errors on keys become large errors in *which* tokens get attended.

Keys matter far more than values. k4v3 costs +4.4%; k3v4 costs +9.4%. Same total bits, more than double the damage when the missing bit comes off the key. The reason is in the norms: on Qwen3-8B the mean K-vector norm is 21.8x the mean V norm, and the worst layer is 490x. Key errors are scaled up by the softmax; value errors are averaged away. (The community's "up to 182x" figure came from the same phenomenon on other models; Llama-3.2-1B shows 9.8x mean, 24x max.)

k8v4 is the honest sweet spot. Keeping keys at 8 bits and values at 4 costs 0.2–0.3% on both models — indistinguishable from noise — for 2.6x compression. This is exactly vLLM's turboquant_k8v4 preset, and exactly what vLLM's own study found.

Smaller models are more fragile. Every configuration hurts Llama-3.2-1B two to three times as much as Qwen3-8B. Reports of "+1% perplexity at 3 bits" measured on 30B-class models do not transfer down.

5. Finding 2: QJL Is Not Useless — It's Just a Low-Bit Tool

The community consensus that "Algorithm 1 alone is enough" is true at 4 bits and false below it.

At 4 bits QJL recovers under a point — not worth a 1-bit-per-coordinate residual plus a random projection. At 3 bits on the small model it recovers 11 points. At 2 bits it is the difference between broken and merely bad. The forks dropped QJL because they target 3–4 bits on large models, where it genuinely doesn't pay. It is not that the paper's second stage doesn't work.

6. Finding 3: Norm Correction Fixes Attention, Not Perplexity — Except at 2 Bits

!Attention KL with and without norm correction — Qwen3-8B

Norm correction is a one-line rescale, and it has a strange profile. On attention distributions it is enormous: at 3 bits, KL drops from 2.16 to 0.18 nats on Qwen3-8B (12x). Without it, the reconstructed direction is systematically shorter than unit length (scalar quantization shrinks toward the centroids), every dot product is biased low, and the softmax flattens.

On perplexity, the same fix barely registers at 3–4 bits (+10.3% vs +13.1%; +3.8% vs +4.4%) — the model is more robust to a uniformly flattened attention than the KL suggests. At 2 bits it becomes decisive: +55% with, +98% without.

So: always turn it on (it is free), but don't expect it to rescue 3-bit quality. That's what the forks' _nc suffix buys you.

7. Finding 4: Block-32 Is Where the Forks' Numbers Come From

Every llama.cpp fork quantizes in blocks of 32 values, each with its own fp16 scale, and the community explained this as a flash-attention parallelism choice. On the same Qwen3-8B, the CUDA fork's turbo3 measures +5.5% perplexity (Part 5) — roughly half our +10.3%. We added a block=32 option: rotate and quantize each 32-dim sub-vector separately, with its own norm.

Block-32 closes most of the gap at 3 bits. It costs 0.5 extra bits per value (a 16-bit norm per 32 values) — which is exactly why the forks report turbo3 as 3.25–3.5 bpv rather than 3. In other words, the layout that the community adopted "for parallelism" is a genuine algorithmic improvement: it is polar quantization at a finer granularity, and it is where a meaningful share of the "near-lossless" reputation comes from.

Two caveats. At 2 bits block-32 is *worse* (+69% vs +55%): with only four codebook levels, splitting into 32-dim blocks makes the per-coordinate distribution deviate more from Gaussian. And turbo4 at +0.65% is still clearly better than our +2.6% — the fork additionally handles outliers and uses an asymmetric mean-centring we did not replicate. The remaining gap is a to-do, not a mystery.

Also note k4v3_blk32 = k4v4_blk32 to two decimals. With block-32, dropping values to 3 bits is free. That is the strongest argument yet for the asymmetric K/V allocation the forks and vLLM both settled on.

8. Finding 5: The Residual Window Doesn't Help Perplexity

Keeping the last 128 tokens in full precision (a common recommendation) changed Qwen3-8B 3-bit from +10.3% to +12.5% and Llama-1B from +33.8% to +32.1% — noise. In teacher-forced evaluation almost all attention mass is on the long quantized prefix, so exempting 128 tokens does little. It may matter more for generation quality on short prompts; it does not matter for long-context perplexity.

9. What This Does and Doesn't Show

Shows: on real KV tensors, PolarQuant hits the theoretical scalar-quantization bound with zero calibration; keys are 5–20x more sensitive than values because their norms are 10–500x larger; QJL helps at ≤3 bits; norm correction is free and mostly fixes attention distributions; block-32 explains about half the forks' advantage at 3 bits.

Doesn't show: downstream task accuracy (perplexity is a proxy — vLLM's study found reasoning benchmarks punish 3-bit harder than perplexity does); speed (fake quantization is free; real kernels are not — see Part 5); behavior above 16K tokens; the fork's outlier handling and mean-centring, which we did not implement.

10. Takeaways

• If you want lossless: 8-bit keys, 4-bit values. +0.2%. Done.
• If you want 3-bit: use a block layout, give keys at least one more bit than values, and keep norm correction on. Expect +5–6% perplexity on an 8B model, more on smaller ones.
• Don't dismiss QJL if you're going below 3 bits; do dismiss it at 4.
• Don't trust a vector-distortion number. 3% MSE was 10% perplexity.

The full script (polarquant_kv.py, ~200 lines including the harness) and both JSON result files are attached to this post.

References

• Zandieh et al., TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate, ICLR 2026
• Zandieh et al., QJL: 1-Bit Quantized JL Transform for KV Cache Quantization
• Part 3: TurboQuant Status Check · Part 5: llama.cpp CUDA fork benchmarked
• llama.cpp Discussion #20969 — block-32, K/V asymmetry, norm correction consensus