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):

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):

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.