Preprint · 2026

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

Samuel Fernández-Menduiña* ·  Amir Ziashahabi* ·  Eduardo Pavez ·  Antonio Ortega ·  Salman Avestimehr

University of Southern California

NOVA-KV uses attention-aware non-orthogonal transforms and vector quantization to preserve accuracy at approximately two bits per KV element.

*Equal contribution

Paper Code BibTeX
Abstract

Long-context LLM decoding reads the key–value (KV) cache at every step. Loading it takes longer than computing attention over it, so throughput is bandwidth-bound. Hence, reducing the cache size can raise both decoding speed and serving capacity. The challenge is to reduce cache size while preserving the attention products, keeping reconstruction cheap, and using a fixed per-token bit count. At two bits per element, the most competitive methods rely on orthogonal transforms. However, existing techniques are either data-oblivious or use the query statistics without deriving the transform from a distortion criterion. Moreover, they rely on transforms built on top of random or Hadamard rotations, which equalize variances across entries rather than compacting energy, and fixed-width scalar quantizers, which are suboptimal at low rates. In this paper, we formulate KV cache quantization as a transform coding problem in which distortion is the error in the attention products. We derive closed-form optimal transforms for keys and values from calibration statistics, under a high-resolution model. We show that the optimal key transform is not orthogonal and satisfies a generalized Parseval relation: the attention-aware distortion becomes mean-squared error (MSE) in the transform domain. Thus, we can use MSE-optimal vector quantizers applied directly to the transformed key coefficients. To meet the fixed-width layout requirement, we show that grouping coefficients into equal-volume partitions makes equal-size codebooks attain the variable-rate optimum under the same high-resolution model. At two bits per element, our method, termed NOVA-KV, recovers most of the long-context retrieval accuracy lost by scalar quantization methods at comparable throughput. The margin is widest on hybrid-attention mixture-of-experts models: on GPT-OSS-20B, prior two-bit transforms collapse at every context length, while NOVA-KV remains effective.

KV cache quantization

A transformer caches one key and one value vector per token, per layer, per head. This cache grows with context length and with batch size, and every decoding step must read all of it from memory. Modern kernels compute attention faster than the cache can be loaded, so once the context is long, the cache becomes the bottleneck.

Measured per-step decode time by phase for Qwen3-8B at batch sizes 1, 4, 16 and 64, showing KV cache loading growing to dominate the step.
Measured per-step decode time, Qwen3-8B, 8×H100, 16K context. Parameter loading is flat in batch size. At batch 64, reading the cache is 76% of the step, more than six times the cost of loading the model weights. Compressing the cache buys decoding speed and serving capacity.

Three requirements

Three requirements constrain the design of KV cache compressors.

  1. Accuracy. What has to be preserved is downstream task performance. A quantizer cannot optimize that directly, so it needs a proxy. Since the cache is only ever read through the attention computation, we use the error in the attention products as the proxy.
  2. Read cost. The cache is read at every decoding step, so any per-element work at read time is paid over the whole cache, every step.
  3. Fixed-width layout. Serving engines page the cache, so every token must occupy the same number of bits.

We pose the problem as transform coding with the attention-product error as the distortion. This gives an optimal transform, and that transform is not a rotation.

What's wrong with MSE?

Standard quantizers minimize the error in the stored keys and values. Keys are read through the key–query inner product. Two reconstructions with identical MSE can distort the attention logits by very different amounts, depending on whether their error lands in directions the queries look along.

Scatterplot of keys and queries in two dimensions, with the query covariance drawn as a dashed ellipse.
Distribution of keys and queries, together with query covariance (dashed).
Scatterplot of quantization error under the KLT versus under our transform, against the same query covariance ellipse.
Quantization error. The KLT spreads error isotropically. Ours steers the error away from the high-energy query directions.

Transform coding and VQ for the attention products

  1. Distortion is defined on the attention products rather than on the stored vectors.
  2. The optimal key transform is therefore not orthogonal: it whitens by the query second moment, then decorrelates.
  3. That transform satisfies a generalized Parseval relation, so ordinary MSE-optimal vector quantizers apply directly in the transform domain.
  4. Equal-volume grouping makes fixed-width codebooks attain the variable-rate optimum, so VQ survives the paged layout.
NOVA-KV online inference. Keys and values are transformed and encoded once on the write path into a fixed-width paged cache; on the read path, each is a codebook lookup followed by an inverse transform, then attention.
Each key and value is transformed and encoded once, on the write path. The read path, paid at every decoding step, is a codebook lookup plus one multiply.  ·  click to enlarge

Results

2.22
bits per KV element
75.4
NIAH @128K
(OSCAR: 25.3)
−1.8
points vs BF16
reasoning & code

Long-context retrieval

On Qwen3-8B the scalar baselines collapse as context grows, while NOVA-KV tracks the uncompressed reference:

MethodBPE8K32K64K128K
BF16 (uncompressed)1699.998.584.383.4
QuaRot2.2554.823.50.00.0
OSCAR2.2896.786.960.625.3
NOVA-KV (ours)2.2299.496.076.475.4

RULER NIAH mean accuracy (%), Qwen3-8B.

Throughput

A smaller cache leads to faster decoding. We measure decode throughput in SGLang, excluding time to first token.

Decode throughput bar charts. Top row: throughput against input length at 30K, 60K and 90K for GPT-OSS-20B, Qwen3-8B and Qwen3-4B-Thinking. Bottom row: throughput against batch size.
Decode throughput, prefill excluded. Top: against input length at batch 1. Bottom: against batch size. NOVA-KV reaches 1.6–3.1× BF16 on Qwen3-8B and 1.7–3.4× on Qwen3-4B, with the larger factors at the longer inputs. The factor is smaller on GPT-OSS-20B (1.1–1.5×), whose sliding-window layers leave less cache to compress. Against OSCAR at the same rate the two arms are within a few percent. At 90K the BF16 cache admits at most batch 4 on either Qwen model, while both 2-bit arms serve batch 16.

Robustness across architectures

The gap widens on models where orthogonal transforms struggle. On GPT-OSS-20B, NOVA-KV preserves most of the BF16 accuracy on every generation benchmark (mean 72.4 against 76.5). Across all four models tested, NOVA-KV stays close to BF16 while the robustness of the orthogonal-transform baselines varies considerably.

Citation

@article{fernandezmenduina2026novakv, title = {Spend Bits Where Queries Look: KV Cache Vector Quantization with Attention-Preserving Transforms}, author = {Fern\'andez-Mendui\~na, Samuel and Ziashahabi, Amir and Pavez, Eduardo and Ortega, Antonio and Avestimehr, Salman}, journal = {arXiv preprint arXiv:ARXIV_ID}, year = {2026} }