🤖 machine learning

Statistical Inference and Quality Measures of KV Cache Quantisations Inspired by TurboQuant

This paper analyzes three KV cache quantization schemes under a fair bit budget, demonstrating through statistical inference and empirical metrics that the asymmetric KQV method outperforms the symmetric QKQV approach at the practically dominant 4-bit budget by mitigating variance inflation and softmax-induced errors, while revealing a budget-dependent crossover in geometric reconstruction performance.

Original authors: Paolo D'Alberto

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Paolo D'Alberto

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a massive library of information (a Large Language Model). To answer a question, the library needs to remember the context of the conversation. This memory is called the KV Cache. As conversations get longer, this memory takes up so much space that it becomes the main bottleneck, slowing everything down.

To fix this, engineers try to "compress" this memory, like zipping a file. The paper you provided analyzes three different ways to zip this memory without losing the ability to find the right answers. The authors use a mix of math, geometry, and statistics to figure out which method is best.

Here is the story of their findings, explained simply.

The Three Competitors

The paper compares three strategies for compressing the "Key" (K) and "Value" (V) parts of the memory. Think of K as the "address" (where to look) and V as the "content" (what you find there).

KV (The Baseline): The old-fashioned way. It just shrinks the numbers slightly. It's simple but often inaccurate.
KQV (The Winner): A smart hybrid. It uses a special rotation trick on the "address" (K) to make it easier to compress, and a different trick on the "content" (V) to fix small errors.
QKQV (The Over-Engineer): This tries to use the error-fixing trick on both the address and the content, hoping for the best of both worlds.

The Big Discovery: Don't Fix the Address

The most surprising finding is that KQV is the clear winner, especially at the most common compression level (4 bits).

Why did QKQV fail? The authors discovered a fundamental difference between the "address" (K) and the "content" (V).

The "Address" (K) is like a Compass: The model uses the address to decide which piece of information to pay attention to. This decision is made by a mathematical process called Softmax, which acts like a spotlight. If the compass is even slightly off, the spotlight might shine on the wrong building entirely.
- The paper found that the "error-fixing trick" (QJL) used in QKQV actually makes the compass wobblier. It introduces a tiny bit of random shaking.
- Because the spotlight (Softmax) is so sensitive, this tiny shaking gets amplified massively. It's like trying to balance a pencil on its tip; a tiny wobble makes it fall over.
- Result: Fixing the address with this trick actually makes the model more likely to look at the wrong thing.
The "Content" (V) is like a Bucket: Once the spotlight picks a building, the model gathers the information (the bucket).
- Here, the "error-fixing trick" works perfectly. If you spill a little water, the trick helps you get it back. Since the model just adds up all the buckets, small errors cancel each other out over time.
- Result: Fixing the content with this trick is very helpful.

The Analogy: Imagine you are a chef (the model).

K (Address) is deciding which ingredient to grab. If you grab the wrong one because your hand shook, the whole dish is ruined. You need a steady hand (scalar quantization), not a shaky one.
V (Content) is the amount of salt you add. If you add a little too much or too little, it's fine; the other ingredients will balance it out. You can use a shaky hand here if it helps you measure faster.

The "Low-Rank" Trap

The paper also found a hidden danger. Imagine the library isn't random; it's organized in a very specific, narrow pattern (Low-Rank).

When the data is random, the compression tricks work fine.
But when the data is highly organized (like real-world AI models often are), the "address" becomes extremely sensitive. The model focuses intensely on just one or two pieces of information.
In this scenario, even a tiny error in the "address" causes the model to completely ignore the correct information and focus on the wrong one. The paper found that this "organized" data causes much more damage than "messy" (heavy-tail) data.

The "6D" Scorecard

Instead of just measuring "how wrong" the numbers are (a single score), the authors created a 6D Error Framework.

Think of it like a car crash test. You don't just measure "how much the car crumpled." You measure:
1. Did the engine break? (K Scale)
2. Did the steering wheel turn? (K Direction)
3. Did the seats rip? (V Scale)
4. Did the passengers get hurt? (V Direction)
5. Did the car stop? (Output Scale)
6. Did the car go off the road? (Output Direction)
This detailed view showed that while some methods looked good on paper (low average error), they were actually terrible at keeping the car on the road (routing errors).

The Final Verdict

The paper concludes with a clear rule for the future:

Don't trade bits for tricks on the "Address": If you have 4 bits to compress the "address," use all 4 bits for a steady, direct compression. Do not steal 1 bit to try to "fix" the error later; the fix makes the compass wobbly and causes the model to hallucinate.
Do use tricks on the "Content": It is safe and beneficial to use the error-fixing trick on the "content" part of the memory.
Watch out for "Organized" data: The most dangerous failure happens when the model is highly focused on specific topics. Standard compression methods often fail here, and we need new ways to handle these specific patterns.

In short: Keep the compass steady, and let the buckets be flexible. The "KQV" method does exactly this, making it the superior choice for compressing AI memory.

Technical Summary: Statistical Inference and Quality Measures of KV Cache Quantisations Inspired by TurboQuant

Problem Statement

The KV (Key-Value) cache is the primary memory bottleneck in transformer inference, growing linearly with context length. Compression via quantization is essential, yet standard scalar quantization (MSE) often fails to preserve the geometric properties required for attention mechanisms. While TurboQuant proposes a two-stage pipeline (random rotation + scalar quantization + 1-bit QJL sketch for bias correction), the optimal allocation of bits between Key (K) and Value (V) caches remains unclear. Specifically, it is unknown whether applying the QJL residual correction to Keys (in addition to Values) improves or degrades attention quality, particularly under varying bit budgets and data distributions (e.g., low-rank, heavy-tailed).

Existing evaluation metrics, such as Mean Squared Error (MSE) or even KL divergence, often conflate scale and direction errors or fail to capture catastrophic "argmax-shift" failures where a single mis-quantized dominant key collapses the attention distribution.

Methodology

Theoretical Framework

The authors ground their analysis in the geometry of high-dimensional spheres. They establish that for a vector uniformly distributed on a hypersphere $S^{d-1}$ , the marginal distribution of coordinates follows a Beta distribution $\text{Beta}(\frac{d-1}{2}, \frac{d-1}{2})$ . As dimension $d \to \infty$ , this converges to a Gaussian.

Jensen's Inequality & Softmax: The paper highlights a critical nonlinearity: the softmax function amplifies variance in Key inner products. Even if quantization errors are zero-mean, the convexity of the exponential function ( $e^x$ ) introduces a bias (Jensen bias) that inflates attention weights for keys with high quantization variance.
K-V Asymmetry: The Key tensor enters the attention mechanism via inner products (nonlinear), while the Value tensor enters via a linear weighted sum. Consequently, variance inflation in Keys is catastrophic, whereas unbiased bias correction in Values is beneficial.

Quantization Schemes

Three schemes are compared under a strict, equal bit-budget constraint ( $n$ bits per vector):

KV: Scalar MSE quantization (Lloyd-Max) on both K and V. No rotation, no sketch.
KQV: Applies a Walsh-Hadamard Transform (WHT) to both. K is quantized via scalar MSE ( $n$ bits). V is quantized via scalar MSE ( $n-1$ bits) + 1-bit QJL sketch.
QKQV: Applies WHT to both. Both K and V use ( $n-1$ bits) + 1-bit QJL sketch.

Evaluation Metrics

To move beyond scalar metrics, the paper introduces a 6D Error Framework decomposing error into Scale (SNR) and Direction ( $\phi$ ) for three sites: Key cache, Value cache, and Output ( $T$ ).

Shannon- $\phi$ Plane: Plots scale error vs. direction error.
Statistical Instruments: Mann-Whitney $U$ (rank-biserial correlation), Kolmogorov-Smirnov (CDF separation), and Energy Distance (6D metric).
Mechanistic Proxies: KL divergence between reference and quantized softmax distributions, and top-5 routing recall.

Key Contributions

1. Theoretical Proof of QJL Harm on Keys

The paper proves that replacing scalar quantization on Keys with a 1-bit QJL sketch inflates inner product variance by a factor of at least $\pi/2$ (approx. 1.57) relative to the scalar residual, and by a factor of $2\pi$ when comparing a full $n$ -bit scalar scheme to an $(n-1)$ -bit scalar + 1-bit QJL scheme.

Mechanism: While QJL provides an unbiased estimator of the residual, it discards magnitude information, replacing it with sign bits. The variance of this estimator is $\frac{\pi}{2} \frac{\|r\|^2}{d}$ .
Consequence: This inflated variance is amplified nonlinearly by the softmax exponential (via Jensen's inequality), leading to systematic distortion of attention weights. Thus, applying QJL to Keys is structurally inferior to scalar quantization under fair budgets.

2. The K-V Asymmetry and Optimal Scheme (KQV)

Empirical results confirm that KQV (QJL on V only) is superior to QKQV (QJL on both) across all tested distributions and budgets.

KL Divergence: At the practically dominant 4-bit budget ( $n=4$ ), KQV achieves a KL divergence 2.25 $\times$ lower than QKQV ( $p < 10^{-23}$ ).
Routing: Lower KL in KQV directly correlates with higher top-5 routing recall and lower output direction error.
Conclusion: The 1-bit QJL sketch should be reserved for the Value cache (where it corrects bias without variance penalty) and never applied to the Key cache (where it introduces fatal variance).

3. The Low-Rank Pathology

The paper identifies a critical failure mode for low-rank Key distributions that scalar metrics miss.

Marginal vs. Joint: While WHT makes marginal coordinates Beta-distributed (matching the codebook), it does not destroy the joint low-rank structure.
Catastrophic KL: At high dimensions ( $d=1024$ ), low-rank keys produce KL divergence orders of magnitude worse than heavy-tailed keys, despite having identical marginal histograms. The softmax amplifies small errors on dominant keys within the subspace, causing "argmax-shift" failures.
Implication: Standard rotation-based quantization is insufficient for low-rank attention matrices; the joint structure must be addressed.

4. Budget-Dependent Crossover

A counter-intuitive finding is a crossover in geometric K reconstruction quality:

At low budgets ( $n \in \{2, 3\}$ ), QKQV (QJL on K) sometimes achieves better geometric K reconstruction (lower direction error) than KQV.
However, this geometric improvement does not translate to better attention quality (KL or routing) because the variance inflation still harms the softmax.
At $n=4$ , KQV wins on all measures. This crossover is invariant to rank and tail weight, suggesting a fundamental rate-distortion trade-off between scalar precision and JL residual correction.

Results

Dominance of KQV: At $n=4$ , KQV outperforms QKQV and KV on KL divergence, geometric K error, and 6D distance across all distributions (Gaussian, heavy-tail, low-rank, focused).
QJL on Keys is Harmful: Replacing scalar bits with QJL on Keys consistently increases KL divergence due to variance inflation, except in specific low-budget geometric reconstruction scenarios that do not benefit the final output.
Fat-Tail Robustness: WHT provides unconditional protection against marginal concentration (heavy tails). KQV maintains stable direction error ( $\epsilon_{dir}^K \approx 0.027$ ) even as tail weight increases ( $\nu \to 1.05$ ), whereas KV fails catastrophically.
Low-Rank Failure: Low-rank distributions cause the most severe degradation in attention quality, far exceeding heavy-tail issues, due to the preservation of joint subspace structure despite marginal normalization.

Significance and Claims

The paper claims to provide a rigorous statistical and geometric explanation for why TurboQuant's original application of QJL to Keys (if extended symmetrically) would be detrimental.

Metric Refinement: It argues that Mean KL is an optimistic metric; worst-case KL and routing recall are the true measures of reliability for KV cache quantization.
Design Principle: It establishes that K and V caches require fundamentally different quantization strategies due to the nonlinearity of softmax. QJL is a bias-correction tool suitable for linear outputs (V) but a variance-injection tool that harms nonlinear outputs (K).
Limitation of Marginal Guarantees: It demonstrates that ensuring marginal distributions match the codebook (via WHT) is necessary but insufficient; the joint structure (specifically low-rank) dictates the ultimate failure mode.
Open Problem: The paper identifies the budget-dependent crossover in geometric reconstruction as an open rate-distortion problem, noting that while QKQV wins geometrically at very low bits ( $n=2,3$ ), it loses functionally due to the Jensen amplification of variance.

The work concludes that robust KV cache quantization requires explicit handling of low-rank structures (e.g., via SVD or subspace-aware codebooks) and that the KQV scheme (WHT + Scalar on K, WHT + Scalar + QJL on V) is the optimal configuration for current bit budgets.