# Spend Bits Where Queries Look: KV Cache Vector Quantization with Attention-Preserving Transforms

> NOVA-KV derives non-orthogonal optimal transforms for KV cache quantization, enabling fixed-width vector quantization that preserves attention accuracy at 2 bits, outperforming prior methods on long-context retrieval.

- **Source:** [arXiv](https://arxiv.org/abs/2608.04074)
- **Published:** 2026-08-18
- **Permalink:** https://picx.dev/p/S0E5DV
- **Whiteboard:** https://picx.dev/p/S0E5DV/image

## Summary

## Summary (Overview)

- **Core contribution**: NOVA-KV formulates KV cache quantization as a transform coding problem where distortion is measured by attention product error, deriving closed-form optimal transforms for keys and values from calibration statistics.
- **Key theoretical finding**: The optimal key transform is **non-orthogonal** and satisfies a generalized Parseval relation, converting the attention-aware distortion into MSE in the transform domain—enabling the use of standard MSE-optimal quantizers.
- **Fixed-width VQ design**: Under an independent-Gaussian high-resolution model, equal-volume grouping of transform coefficients allows fixed-rate vector quantization to attain the variable-rate optimum, satisfying serving engines' fixed-width layout requirements.
- **Empirical results**: At 2 bits per element, NOVA-KV recovers most of the long-context retrieval accuracy lost by scalar quantization methods, with the largest margin on hybrid-attention mixture-of-experts models (GPT-OSS-20B), where prior 2-bit transforms collapse entirely.
- **Practical impact**: Decoding throughput is on par with scalar baselines while maintaining significantly better accuracy, with 1.6–3.4× speedup over BF16 at long contexts.

## Introduction and Theoretical Foundation

### Background and Motivation

The KV cache stores key and value vectors for each past token and attention head to avoid recomputation during decoding. Its size is a central inference bottleneck: it grows with context length and batch size, yet every decoding step reads it fully from memory. Since attention kernels compute products faster than the cache can be loaded, **decoding throughput is memory-bandwidth-bound** rather than compute-bound.

Three requirements constrain KV cache compressor design:
1. **Accuracy preservation**: Minimize errors in attention products rather than MSE in the factors
2. **Low read-path complexity**: The cache is read at every decoding step, so per-element costs compound
3. **Fixed-width layout**: Tokens must occupy a fixed number of bits for efficient retrieval by serving engines

### Theoretical Foundation

The paper builds on classical rate-distortion (RD) theory and transform coding (Goyal, 2001). In classical transform coding, a data-dependent linear operator decorrelates inputs; scalar quantization is applied to outputs, followed by entropy coding. However, entropy coding requires sequential decoding, breaking the fixed-width layout requirement.

The attention output error can be bounded as:

$$\|\mathbf{S}\mathbf{V} - \widehat{\mathbf{S}}\widehat{\mathbf{V}}\|_F \lesssim \|\mathbf{S} - \widehat{\mathbf{S}}\|_F \|\mathbf{V}\|_2 + \|\mathbf{S}(\mathbf{V} - \widehat{\mathbf{V}})\|_F \tag{4}$$

This separates into two terms: a key-dependent term (score error) and a value-dependent term (value error weighted by scores).

## Methodology

### Key Transform Derivation

The key-dependent term is bounded via the logit error. Since row-wise softmax is 1/2-Lipschitz:

$$\|\mathbf{S} - \widehat{\mathbf{S}}\|_F \leq \frac{1}{2\sqrt{d}}\|\mathbf{Q}\mathbf{K}^\top - \mathbf{Q}\widehat{\mathbf{K}}^\top\|_F$$

Defining $\mathbf{M}_q = \mathbf{Q}^\top\mathbf{Q}$, the goal is to minimize:

$$\|\mathbf{Q}\mathbf{K}^\top - \mathbf{Q}\widehat{\mathbf{K}}^\top\|_F^2 = \sum_{j=1}^{M}(\mathbf{k}_j - \widehat{\mathbf{k}}_j)\mathbf{M}_q(\mathbf{k}_j - \widehat{\mathbf{k}}_j)^\top \tag{5}$$

**Theorem 1**: The optimal key transform is:

$$\mathbf{R}_{K,p}^{\star} = \mathbf{M}_q^{1/2}\mathbf{E}_{1:p}$$

where $\mathbf{E}\mathbf{\Lambda}\mathbf{E}^\top$ is the eigendecomposition of $\mathbf{M}_q^{1/2}\widetilde{\mathbf{S}}_k\mathbf{M}_q^{1/2}$, with $\widetilde{\mathbf{S}}_k = \sum_j \widetilde{\mathbf{k}}_j^\top\widetilde{\mathbf{k}}_j$ being the centered key scatter matrix.

**Proposition 1 (Generalized Parseval relation)**: For any vectors $\mathbf{r}, \hat{\mathbf{r}}$ with $\mathbf{k} = \mathbf{r}\mathbf{R}_K^{-1}$ and $\hat{\mathbf{k}} = \hat{\mathbf{r}}\mathbf{R}_K^{-1}$:

$$\|\mathbf{r} - \hat{\mathbf{r}}\|_2^2 = \|\mathbf{k} - \hat{\mathbf{k}}\|_{\mathbf{M}_q}^2$$

This converts the weighted attention-aware objective into ordinary MSE, allowing any MSE-optimal quantizer to operate on transform coefficients.

### Value Transform

**Corollary 1**: The optimal value transform is orthogonal, given by the eigendecomposition of $\mathbf{M}_o = \mathbf{V}^\top\mathbf{M}_s\mathbf{V}$ where $\mathbf{M}_s = \mathbf{S}^\top\mathbf{S}$ is the second moment of attention scores.

### Vector Quantization with Volume-Equalized Grouping

Under the high-resolution regime, the distortion-rate function for group $G_\ell$ is:

$$D_\ell(b_\ell) = C_g 2^{-2b_\ell}\left(\prod_{i \in G_\ell}\sigma_i^2\right)^{1/g}(1 + o(1)) \tag{7}$$

**Theorem 2**: The optimal bit allocation is:

$$b_\ell^*(\pi) = b + \frac{1}{2g}\log_2\left(v_\ell(\pi)/\prod_m v_m(\pi)^{1/L}\right) \tag{8}$$

where $v_\ell(\pi) = \prod_{i \in G_\ell}\sigma_i^2$ is the group volume. The allocation is uniform (fixed-width) **only when volumes are equalized**. The paper uses a heuristic: sort entries by decreasing log-variance and group entries with indices $i \equiv \ell - 1 \mod L$.

## Empirical Validation / Results

### Long-Context Retrieval (RULER NIAH)

**Table 2** shows mean accuracy across context lengths (8K–128K):

| Model | Method | BPE | 8K | 16K | 32K | 64K | 128K |
|-------|--------|-----|-----|------|------|------|------|
| Qwen3-8B | BF16 | 16 | 99.9 | 99.4 | 98.5 | 84.3 | 83.4 |
| | QuaRot | 2.25 | 54.8 | 31.3 | 23.5 | 0.0 | 0.0 |
| | OSCAR | 2.28 | 96.7 | 94.6 | 86.9 | 60.6 | 25.3 |
| | **NOVA-KV** | **2.22** | **99.4** | **98.7** | **96.0** | **76.4** | **75.4** |
| GPT-OSS-20B | BF16 | 16 | 95.8 | 95.7 | 94.6 | 92.2 | 80.4 |
| | QuaRot | 2.50 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 |
| | OSCAR | 2.53 | 0.5 | 0.0 | 0.0 | 0.0 | 0.0 |
| | **NOVA-KV** | **2.41** | **89.6** | **81.0** | **79.2** | **70.6** | **54.0** |

On GPT-OSS-20B, both baselines **collapse entirely** (0.0 accuracy at all contexts), while NOVA-KV retains 54.0 at 128K against 80.4 for BF16.

### Reasoning and Coding Benchmarks

**Table 3** shows NOVA-KV maintains near-BF16 performance across GPQA, HumanEval, LiveCodeBench, AIME25, and MATH500:

- **Qwen3-4B**: Mean 73.7 vs 75.3 BF16 (drop: -1.6), vs OSCAR's -2.6
- **Qwen3-8B**: Mean 72.9 vs 74.7 BF16 (drop: -1.8), vs OSCAR's -2.5
- **GPT-OSS-20B**: Mean 72.4 vs 76.5 BF16 (drop: -4.1), vs OSCAR's collapse to 13.9

### Ablation Studies

**Table 4** (Transform-quantizer ablation on Qwen3-8B):

| Transform | Quantizer | BPE | 64K | 128K |
|-----------|-----------|-----|------|------|
| OSCAR | SQ | 2.28 | 60.6 | 25.3 |
| OSCAR | VQ | 2.22 | 68.1 | 62.7 |
| NOVA-KV | SQ | 2.28 | 0.0 | 0.0 |
| **NOVA-KV** | **VQ** | **2.22** | **76.4** | **75.4** |

Both the transform and the quantizer are necessary: neither substitution alone achieves the full result.

### Throughput

NOVA-KV achieves 1.6–3.1× BF16 speedup on Qwen3-8B and 1.7–3.4× on Qwen3-4B at long inputs, with performance within a few percent of OSCAR at the same rate.

## Theoretical and Practical Implications

### Theoretical Contributions

1. **Non-orthogonal optimal transforms**: The paper proves that orthogonal transforms (used by all prior work) are suboptimal for minimizing key-query inner product distortion unless $\mathbf{M}_q \propto \mathbf{I}$. The optimal transform satisfies $\mathbf{R}_K\mathbf{R}_K^\top = \mathbf{M}_q$, a linear compander condition from high-resolution quantization theory.

2. **Generalized Parseval relation**: The transform converts the attention-weighted objective into ordinary MSE, bridging the gap between attention-aware distortion and standard quantization theory.

3. **Fixed-width optimality**: Equal-volume grouping makes fixed-rate VQ attain the variable-rate optimum, resolving the tension between energy compaction (which creates variance spread) and fixed-width layout requirements.

### Practical Implications

- **Serving-compatible design**: The read path is a simple codebook lookup (no matrix multiplication), enabling fusion into attention kernels
- **Architecture robustness**: NOVA-KV works across diverse architectures, including hybrid-attention MoE models where orthogonal-transform baselines fail completely
- **Calibration efficiency**: Fitting on a disjoint domain (MMLU instead of GPQA) leaves RULER NIAH within 2.0 points, showing no evaluation-domain advantage

## Conclusion

NOVA-KV formulates KV cache quantization as a transform coding problem with attention-product distortion. The key theoretical contributions are: (1) the optimal key transform is non-orthogonal and satisfies a generalized Parseval relation, and (2) equal-volume grouping makes fixed-rate VQ attain the variable-rate optimum. At 2 bits per element, NOVA-KV reduces the gap to BF16 relative to the 2-bit state-of-the-art at comparable decoding speed, with the largest gains on hybrid-attention MoE models.

**Future directions**: Joint quantization of keys and values is left for future work, as is extending the framework to even lower bit rates or alternative distortion criteria.

---

_Markdown view of https://picx.dev/p/S0E5DV, served by PicX — AI-generated visual whiteboard summaries of research papers._