acceptodds
Desk rejected at ICLR 2027

The KV Cache as a Rotary Associative Memory

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

KV cache compression is standard practice in long-context inference. Existing compression methods are validated by benchmarking after the fact, providing no a-priori guarantee on retrieval performance. Across ten models and four compression methods, retrieval accuracy falls by 41% on average, while zero-shot accuracy falls by 2% and perplexity rises by 19%. To understand the structure responsible, we formulate every attention read from the KV cache under rotary position embeddings (RoPE) as an exact retrieval from an associative memory, whose stored addresses are related across read times by a unitary representation of time translation at a fixed spectrum of frequencies. We term this view a rotary associative memory (RoAM). The representation decomposes the cache into frequency bands and gives closed forms for how far a head can retrieve (retrieval range), how many entries it separates at that distance (capacity at distance), and where distinct positions become indistinguishable (positional aliasing). Using band-targeted perturbation, we show that retrieval at distance is carried by the slow bands. Removing an eighth of the slow bands raises perplexity to between and and drives retrieval to zero across RoPE bases from to , whereas removing an eighth of the fast bands leaves retrieval within of baseline. At matched perturbation norm, slow-band damage costs more retrieval accuracy on every model, while zero-shot accuracy moves by at most . Position-uniformity of the readout bounds the worst-case effect of any key edit at every future read position, with the edit-side factor computable at compression time and the query-side factor bounded from the model's weights. The bound is audited on 115 million measured perturbations from deployed reconstruction methods. Predicted attention-logit curves match measured ones head by head across the ten evaluated models, with coefficients estimated from activations and no parameters fitted to the curves (median detrended ), and aliasing distances predicted in advance from each configuration alone are reproduced to the integer.

Primary area:
foundation or frontier models, including LLMs
Keywords:
rotary position embeddings, KV cache, language models, associative memory, attention analysis

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_EcCeOpenReview ↗
Rating
3(+1)
Confidence
3(+1)
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes the view of Rotary associative memory for exploring and analyzing KV cache compression. The cache is decomposed into frequency bands (inspired by the motivation of RoPE), and discussions on the retrieval range, capacity at distance, and positional aliasing have been conducted. A perturbation certificate is also proposed.

Critical strengths
  1. This work proposes an analytical framework (RoAM) for KV cache compression and a corresponding set of certificates.
Critical weaknesses
  1. This paper analyzes only RoPE. I suggest considering the extrapolation schemes commonly used in real-world systems, such as YaRN, and conducting a more in-depth analysis of them. In addition, during mid-training in some industrial LLMs, there is often a long-context stage in which the RoPE base is progressively increased to accommodate longer sequences (e.g., RoPE base from 10k to 500k). Does the analytical framework still hold in such cases?
  2. Retrieval is mainly evaluated at 8192 tokens, which is shorter than practical settings (at least 128k or even up to 1M for recent LLMs). More discussions and experiments are required.
Questions for authors
  1. Plain retrieval alone may not be sufficient to fully reflect an LLM’s long-context capability. I suggest evaluating on more realistic long-context tasks besides retrieval.
  2. It is interesting to provide an additional analysis of partial RoPE and NoPE, as well as of this situation under hybrid models, since the current trend implies that RoPE may not be the only effective mechanism for long-context capability (e.g., NoPE and linear attention may work).
3 comments

Executive Summary

Thank you for the careful review. The revised PDF (changes in blue; pointers use its numbering) answers each point:

  1. Rescaled spectra (W1): a new corollary (Corollary 4) predicts coverage and alias integers under YaRN and position interpolation; predictions registered before the runs held on all 17 captured buffers (new Table 5, F.13). A base increase is the same per-band rescaling; the fleet spans bases 10410^4 to 10710^7.
  2. Length (W2): measurements at 32,768 (two models), 65,536 (band ablation, Table 30) and 131,072 (Table 31); the certified range L∗L^{\ast} of each spectrum is closed-form up to 10710^7 (Table 3).
  3. Realistic tasks (Q1): the retrieval macro includes HotpotQA and passage retrieval; new Table 36 adds five LongBench QA subtasks generated through the compressed cache.
  4. Partial RoPE, NoPE, hybrids (Q2): a new scope paragraph in Section 2.

New Results

New Table 5 (seed 42; complete in new Table 31): PG-19 perplexity and mean RULER accuracy, full cache and with the slowest or fastest half of the bands zeroed.

Model (trained)ScheduleLengthPPLRULERslow halffast half
Llama-3-8B (8192)unscaled327685535530.000.000.000.000.000.00
interpolation ×4\times 4327681381380.000.000.000.000.000.00
YaRN ×4\times 4327688.728.720.460.460.000.000.560.56
Qwen2.5-7B-Instruct (32768)vendor YaRN ×4\times 46553610.1210.120.740.740.000.000.720.72
Mistral-7B v0.1, stockYaRN ×16\times 163276811.7311.730.100.100.000.000.340.34
Yarn-Mistral-7b-128kYaRN ×16\times 16327689.919.910.230.230.000.000.510.51

W1: YaRN, Interpolation and Base Changes

New Corollary 4 (proof in Appendix D): interpolation divides every frequency by ss, YaRN only the slow bands. (i) Both satisfy cov(Θ′;sL0)=cov(Θ;L0)\mathrm{cov}(\Theta'; sL_0) = \mathrm{cov}(\Theta; L_0), the extended context inherits the coherent bands of the original, no others; (ii) YaRN leaves the fast bands, hence resolution and aliasing, unchanged, while interpolation moves the top-band onset off Δ=1\Delta = 1; (iii) YaRN's attention factor is a change of β\beta, not of the spectrum. Predictions were registered before any run: all 17 buffers match to 3×10−73 \times 10^{-7}, all 272 onset and alias integers reproduce, the coverage identity holds on all 11 variants, and the per-head fit holds (median rr 0.82 to 0.94). Stock models that fail past their trained length recover under YaRN with no fine-tuning; interpolation restores coverage but spends resolution (Llama-3-8B in range: perplexity 8.0 to 118, retrieval 0.84 to 0.00); in every row the slow half carries retrieval. Weights trained under a schedule retrieve better than stock weights (0.23 against 0.10).

A base change from θ\theta to θ′\theta' multiplies band mm by (θ′/θ)−2m/d(\theta'/\theta)^{-2m/d}: a per-band rescaling of the same form, so Theorem 5 gives the new certified range L∗L^{\ast} in closed form and Theorem 4 the alias integers. The fleet spans bases 10410^4 (Mistral v0.1, Gemma) to 10710^7 (Granite), Llama-3.1-8B carries its long-context schedule, and every spectrum prediction holds on each (Table 3). What a progressive schedule transfers across stages is a property of the weights, not the spectrum; the Mistral pair is that measurement.

W2: Length

F.12 repeats the capture-side measurements at 32,768 on two models (detrended rr 0.924 and 0.888 against 0.895 and 0.885; Table 29), retrieval at 32,768 (macro 0.853 against 0.882, three seeds), and band ablation at 65,536 on Llama-3.1-8B (Table 30): macro 0.820, the slow-half arm 0.000 in all fifteen (subtask, seed) cells with perplexity multiplied by 161, the fast-half arm −0.008±0.012-0.008 \pm 0.012. F.13 runs to 131,072. The compression audit stays at 8,192, where ten models, four methods and three seeds fit; 131,072-token cells with a compressor in the loop exceed 48 GB (Section 9).

Q1: Beyond Plain Retrieval

The seven-task retrieval macro of Table 4 contains HotpotQA (multi-hop F1) and LongBench passage retrieval. New Table 36 (F.15) generates five LongBench subtasks (NarrativeQA, Qasper, MultiFieldQA, HotpotQA, passage retrieval) on Llama-3.1-8B-Instruct after a compressed 8,192-token prompt: zeroing the slow half takes all five to zero; KIVI-2 moves the four QA subtasks by at most 0.04 and passage retrieval by 0.42; H2O costs the QA subtasks 0.08 to 0.19.

Q2: Partial RoPE, NoPE, Hybrids

Section 2 now states the scope. Un-rotated dimensions are bands at θ=0\theta = 0: coherent at every distance, a floor to the kernel, no resolution, no aliasing; Theorem 2 permits any linear map on them. Under NoPE the band statements do not apply; Proposition 3 holds. In hybrids, RoPE layers are covered layer by layer; state-space and linear-attention layers keep a fixed-size state, not an addressed store, and lie outside the frame.

We thank the reviewer for the thorough reading and gladly discuss further.

Thank you for the timely response. It mostly addresses my concerns about the extrapolation schemes and the experiments with longer context lengths. Since my main concerns have been largely resolved, I am inclined to raise my score to 3.

Thank you for reading the response and the revision, and for the updated assessment.

Reviewer_jtQuOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
2(+1)
Soundness
2
Read review
Paper summary

The paper provides a mathematical framework for analyzing what a KV cache remembers and how retrieval changes with distance. The authors reframe the rotation applied to KVs from RoPE as a Hopfield-style associative memory and call this view rotary associative memory (RoAM). The main intuition is that the fast bands will oscillate frequently over long distances, so slow bands are especially important for long-range retrieval. Results show that the predicted attention vs distance curves match measured ones with correlation of 0.894.

Critical strengths

The main strength is the evidence that long-range retrieval is dependent on the slow RoPE bands. The band ablation show how removing slowest 1/8 of bands causes retrieval to drop to zero, while removing fast 1/8 costs little. The matched norm perturbation also show the equal edits hurts more on slow bands, which further support the finding.

Critical weaknesses

The main weakness is that the compression guarantees have limited practical impact. The paper pitches the idea of making KV cache certifiable, but the certificate results directly from the Cauchy-Schwarz bound which is generally loose (6-25x) and only certifies in only a small fraction of the reported cases. As a result, this is uninformative for eviction, and no compression policy method is proposed based on the theory.

Questions for authors
  1. In the experiments, the certificate guarantees preservation in only a small fraction of cases despite much higher observed preservation rates. Is there an evaluated operating regime where it supports a useful compression decision?

  2. To what extent is the asymmetry (ΔRetr - ΔZS) explained by unequal compression between retrieval tasks and zero-shot prompt tasks which are likely shorter? For each method, what fraction of the cached tokens is actually quantized, reconstructed, or evicted during the evaluations? In particular, do typical prompts fit within H2O’s or KIVI's budget?

3 comments

Executive Summary

Thank you for the careful review. The revised PDF (changes in blue; pointers use its numbering) answers each point:

  1. Practical impact (W1, Q1): the bound now yields a compression policy, new Corollary 8, which beats uniform precision on perplexity in 30 of 30 cells and on retrieval at matched bits (new Tables 25, 26); a new precision sweep (Table 24) states where the certificate decides.
  2. Unequal compression (Q2): yes for two of the four methods under the bare prompt. A new length-matched protocol (new Table 27) compresses 97 to 99% of the cache every item reads; the asymmetry holds in all twelve cells.
  3. Presentation: a new results map (Table 10) states what each result assumes and where it is tested; a scope paragraph in Section 2; Sections 7 and 9 shortened.

New Results

New Table 27: zero-shot change from the identity cache, five-task mean, bare prompt (Table 21, three seeds) against a 76807680-token compressed prefix (seed 42), with the retrieval change of the same cells.

ModelMethodΔ\DeltaZS bareΔ\DeltaZS prefixΔ\DeltaRetr
Llama-3.1-8BKIVI-2+0.00+0.00−0.034-0.034−0.08-0.08
KVQuant-3−0.00-0.00−0.004-0.004−0.01-0.01
PALU−0.03-0.03+0.026+0.026−0.19-0.19
H2O+0.00+0.00+0.014+0.014−0.65-0.65
Mistral-7B v0.3KIVI-2+0.00+0.00−0.013-0.013−0.11-0.11
KVQuant-3+0.00+0.00−0.004-0.004−0.02-0.02
PALU−0.02-0.02+0.018+0.018−0.08-0.08
H2O+0.00+0.00+0.011+0.011−0.61-0.61
Qwen2.5-7BKIVI-2−0.00-0.00−0.020-0.020−0.08-0.08
KVQuant-3−0.00-0.00−0.004-0.004−0.02-0.02
PALU−0.08-0.08−0.214-0.214−0.61-0.61
H2O−0.00-0.00+0.003+0.003−0.62-0.62

W1 and Q1: What the Certificate Decides

A policy. Minimizing the edit-side factor of Proposition 3 under a bit budget gives bm=B+log⁡2rm−2d∑jlog⁡2rjb_m = B + \log_2 r_m - \tfrac{2}{d}\sum_j \log_2 r_j (new Corollary 8, proof in Appendix E): no frequency enters, yet the slowest eighth of bands gets 0.8 to 2.0 more bits than the fastest. Over ten models and three seeds, 4-bit keys cost a median 2.2% perplexity against 10.9% uniform, 3-bit keys 17% against 213%, 30 of 30 cells (new Table 25). At matched bits (new Table 26), RULER on Llama-3.1-8B at 3 bits is 0.698 against 0.463 uniform, on Qwen2.5-7B at 4 bits 0.805 against 0.653, within 0.01 of uncompressed.

Operating regime. At 2 and 3 bits the margin condition certifies at most 13% of long-range reads (Table 23); new Table 24 follows it to 8 bits: 0, 1, 3, 13, 17% certified at 2, 3, 4, 6, 8 bits, against 98 to 100% empirical survival at 8 bits. The uncertified reads are near-ties, margins below the key error of even 8-bit storage. The 6 to 25 factor is the median read; the largest measured shift reaches 0.72 to 0.93 of the bound (Table 4), which is the read a guarantee must cover. What the bound decides at every precision is the allocation: the allocated arm keeps more top entries than uniform at every width up to 4 bits (0.89 against 0.80 at 2 bits on Llama-3.1-8B, 0.78 against 0.59 on Qwen2.5-7B).

Eviction. Section 7 states that H2O is classified, not certified: an evicted key has δ=−k\delta = -k, where the bound is valid but uninformative. The deciding statistic is attention mass on evicted slots, median 0.41 and 90th percentile 0.89 at 94% eviction (Table 23); H2O takes retrieval from 0.592 to 0.078 while perplexity moves 10%, the failure the certificate predicts and perplexity misses.

Q2: Unequal Compression

Yes, for two methods. Retrieval prompts are 8,192 tokens: KIVI-2 quantizes all but its last 128 tokens (98%), KVQuant-3 and PALU every token, H2O evicts 94% of slots (Table 4). The zero-shot prompts are shorter than KIVI-2's residual window and H2O's 512 retained slots, so those two methods compressed little or nothing of what those items read, and every method scored the first answer token before compressing. Section 7 now says so, and the zero-shot figure is removed from the abstract and Section 1.

New Table 27 removes both differences: a 7,680-token prefix is prefilled through each compressor in 128-token chunks and every answer token of 500 items per task is scored through the compressed cache; the prefix is 97 to 99% of what an item reads (H2O keeps 512 slots). The five-task mean moves by at most 0.034 (KIVI-2), 0.004 (KVQuant-3) and 0.014 (H2O) while retrieval falls by up to 0.65 on the same cells; PALU on Qwen2.5-7B, the one cell where zero-shot falls (0.21), is the cell whose perplexity rises 656% (Table 21). Retrieval degrades more than zero-shot in all twelve cells.

Presentation

New Table 10 (F.1) maps every result to its assumption and test. Only Theorem 3 assumes random keys; Corollary 2 needs per-band second moments (median r=0.894r = 0.894 over 8,992 heads). Section 2 now states the scope (partial RoPE, NoPE, hybrids); Figures 2 to 4 are narrowed and Sections 7 and 9 shortened.

We thank the reviewer for the thorough reading and gladly discuss further.

Thank you for the response. The proposed compression policy and its improvements over uniform precision provide an application of the framework and partially address my concern about practical relevance. However, I remain unconvinced of the policy’s broader practical impact as the policy's evaluation remains limited to 8K tokens, and its benefits relative to stronger compression baselines remain unclear. Nevertheless, some of my concerns are addressed, so I am raising my score to 2.

Thank you for the updated assessment. Both remaining points, a stronger baseline and the policy beyond 8K, are now measured; the results are in the revised PDF uploaded today, as the new Section F.16 (Tables 37 and 38), and Section 7 points to them.

(i) Against a stronger baseline: Corollary 8 inside KIVI-2. KIVI-2's own quantizer, 32-token groups, 128-token residual window, 2-bit values; only the key width varies across bands, at the same 2-bit average per head, so the footprint is identical. Three models, 8,192 tokens; entries are RULER mean over the five subtasks / PG-19 perplexity (new Table 37).

ModeluncompressedKIVI-2KIVI-2 + Corollary 8
Llama-3.1-8B0.8880.888 / 7.997.990.8210.821 / 8.478.470.8280.828 / 8.378.37
Mistral-7B v0.30.8150.815 / 6.566.560.6940.694 / 6.766.760.7920.792 / 6.726.72
Qwen2.5-7B0.7960.796 / 8.738.730.6980.698 / 9.019.010.7830.783 / 8.958.95

The allocation improves stock KIVI-2 on all three models, on retrieval and on perplexity, recovering 10%, 81% and 87% of the retrieval KIVI-2 loses; on Llama-3.1-8B, LongBench passage retrieval is 0.40 against 0.34 and HotpotQA 0.25 against 0.22. The uniform arm runs through the same code and is bit-exact with stock KIVI-2.

(ii) The policy at 32,768 tokens. The Table 26 comparison at four times the context: allocated against uniform key precision at 4 and 3 bits, keys only, with the uncompressed cache scored at the same length (new Table 38). Entries are RULER mean / PG-19 perplexity.

Modeluncompresseduniform, 4 bitsallocated, 4 bitsuniform, 3 bitsallocated, 3 bits
Llama-3.1-8B0.8590.859 / 7.827.820.7710.771 / 8.088.080.8370.837 / 7.947.940.2730.273 / 10.2610.260.6220.622 / 9.019.01
Mistral-7B v0.30.6010.601 / 7.057.050.5810.581 / 7.147.140.6120.612 / 7.087.080.4040.404 / 7.577.570.6070.607 / 7.187.18
Qwen2.5-7B0.7680.768 / 8.778.770.5960.596 / 10.1510.150.7500.750 / 8.818.810.3060.306 / 11.8111.810.6470.647 / 9.469.46

The allocation is ahead of uniform precision in all six model-width pairs, on retrieval and on perplexity. At 4 bits it is within 0.02 of the uncompressed RULER mean on every model, where uniform loses 0.09, 0.02 and 0.17; at 3 bits it loses 0.24, 0.00 and 0.12, where uniform loses 0.59, 0.20 and 0.46. The gaps are wider than at 8,192 tokens. On Llama-3.1-8B the LongBench pair at this length is 0.38 / 0.35 under the 4-bit allocation against 0.36 / 0.31 uncompressed.

We thank the reviewer for the two questions; both pointed at measurements the paper needed.

Reviewer_kcLyOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper analyzes attention with rotary positional embeddings (RoPE) from the perspective of associative memory. In particular, it treats the stored keys as memory entries and studies whether a query identical to one of the stored keys can successfully retrieve that entry by assigning it the highest attention score. Using several simplifying assumptions, the authors derive theoretical bounds characterizing retrieval capacity as a function of sequence length, head dimension, and the RoPE frequency spectrum. They also analyze KV-cache compression, deriving bounds on how perturbations to stored keys affect attention logits and providing sufficient conditions for preserving retrieval. The authors validate their theoretical analysis through extensive experiments on 10 pretrained language models, demonstrating that their framework can predict properties such as average attention logits at different distances, retrieval capacity in controlled settings, and the relative importance of different RoPE frequency bands.

Critical strengths
  1. The theoretical analysis is interesting and novel, providing a useful perspective on the relationship between RoPE and associative-memory retrieval. Despite the simplifying assumptions, the experiments suggest that several theoretical predictions remain relevant to pretrained language models.

  2. The experimental evaluation is extensive and thorough, covering ten pretrained models, different RoPE configurations, and several KV-cache compression methods.

Critical weaknesses
  1. Limited practical implications. While predicting average attention logits and other retrieval-related quantities is interesting, there is no immediate practical value of these predictions to my awareness. One potentially useful insight is that compression methods should allocate more resources to preserving low-frequency RoPE bands, which the authors show are particularly important for long-range retrieval. However, the paper does not demonstrate that this insight can improve an existing compression method. Similarly, the proposed compression certificate has limited practical utility: it bounds attention-logit perturbations rather than downstream retrieval accuracy, and its sufficient conditions for preserving the top-scoring entry are too loose to certify most reads under the evaluated compression settings. For example, under KVQuant-3, the certificate verifies preservation for only 2.1% of reads, despite the top-scoring entry actually being preserved in 94.1%.

  2. A substantial gap between the theoretical setting and practical transformer retrieval. As it stands, the paper's main contribution seems to be a better theoretical understanding of how RoPE affects retrieval and how KV-cache compression interferes with it, rather than a direct practical improvement. While this is valuable, much of the theoretical analysis relies on strong simplifying assumptions. In particular, stored keys are modeled as independent random vectors, queries are assumed to be identical to the target keys, and retrieval is largely studied through identifying a single matching entry. In practice, queries and keys are contextualized and correlated, and transformer attention retrieves weighted combinations of multiple values rather than simply identifying one stored key. Although the authors partially address these limitations through more general query–key statistics and experiments on captured activations, the connection to actual end-to-end retrieval remains indirect. Since the primary contribution is explanatory, I would have liked a stronger theoretical setting that models the behavior of real transformers more closely.

  3. Limited architectural scope. The analysis focuses specifically on RoPE-based attention and does not directly extend to other positional encoding mechanisms or efficient sequence architectures. With the increasing adoption of hybrid models combining attention with recurrent or state-space layers, and not using RoPE, it would be interesting to understand whether similar principles apply to these other forms of sequence memory. This limits the generality of the proposed framework.

Questions for authors

The recent NeurIPS 2026 paper Training Transformers for KV Cache Compressibility explores training transformers to produce KV caches that are inherently easier to compress. I would be interested in understanding how your theoretical analysis applies when the model itself is trained to produce more compressible or retrievable keys and values. For example, could such training modify the distribution of query–key statistics in ways that improve retrieval capacity or mitigate the limitations identified by your bounds?

4 comments

Executive Summary

Thank you for the careful review. The revised PDF (changes in blue; pointers use its numbering) answers each point:

  1. Practical use (W1): a compression rule derived from the bound (new Corollary 8) beats uniform precision on perplexity in 30 of 30 cells and on retrieval at matched bits (new Tables 25, 26).
  2. Theory vs. trained models (W2): only Theorem 3 assumes random keys; a new results map (Table 10) states what each result assumes and where it is tested.
  3. Scope (W3): a new scope paragraph (Section 2) and a new YaRN study (Corollary 4, Table 5, F.13).
  4. KV-CAT (Q): RoAM's predictions, new in Section 8.

New Results

New Table 26: band-allocated (Corollary 8) against uniform key precision, same quantizer, ranges and budget, 8,192 tokens; RULER mean, change from uncompressed in parentheses.

ModelBitsUniformAllocated (Cor. 8)
Llama-3.1-8B40.7990.799 (−0.089-0.089)0.8510.851 (−0.037-0.037)
30.4630.463 (−0.425-0.425)0.6980.698 (−0.190-0.190)
Mistral-7B v0.340.7580.758 (−0.057-0.057)0.8110.811 (−0.004-0.004)
30.5250.525 (−0.290-0.290)0.7710.771 (−0.044-0.044)
Qwen2.5-7B40.6530.653 (−0.143-0.143)0.8050.805 (+0.009+0.009)
30.3410.341 (−0.455-0.455)0.6950.695 (−0.101-0.101)

W1: Practical Implications

The bound yields a compression rule. Minimizing the edit-side factor of Proposition 3 under a bit budget gives bm=B+log⁡2rm−2d∑jlog⁡2rjb_m = B + \log_2 r_m - \tfrac{2}{d}\sum_j \log_2 r_j (new Corollary 8; proof in Appendix E). No frequency enters it, yet the slowest eighth of bands gets 0.8 to 2.0 more bits than the fastest. Over ten models and three seeds, 4-bit keys cost a median 2.2% perplexity against 10.9% uniform; at 3 bits 17% against 213%; it wins all 30 cells (new Table 25).

On the certificate. We agree it is conservative at 2 and 3 bits; Section 7 now states beside the bound that it certifies at most 13% of long-range reads at the audited settings (Table 23) and at most 17% at any precision up to 8 bits (new Table 24: 0, 1, 3, 13, 17% at 2, 3, 4, 6, 8 bits; empirical survival 98 to 100% at 8 bits; the uncertified reads are near-ties). The guarantee covers the worst-aligned future query: the largest measured shift reaches 0.72 to 0.93 of the bound, the median 6 to 25 times lower. What the bound decides at every precision is where the bits go: in the sweep the allocated arm keeps more top entries than uniform at every width up to 4 bits (at 2 bits, 0.89 against 0.80 on Llama-3.1-8B, 0.78 against 0.59 on Qwen2.5-7B).

Deployed methods RoAM explains (new in Section 8): KVQuant stores keys before rotation (RoAM's form); CommVQ's codebooks commute with the rotation (Theorem 2); Block-GTQ allocates bits per RoPE block by energy, as Corollary 8 derives; EliteKV and p-RoPE keep un-rotated bands.

W2: Theory vs. Trained Transformers

Only Theorem 3 uses independent keys and a query equal to the target key; new Table 10 states the assumption and test of every result. Corollary 2 needs only per-band second moments and is tested head by head: median r=0.894r = 0.894 over 8,992 heads, 0.875 across corpora. On captured keys (F.11) the predicted margin orders the measured rate within a head at Spearman 0.86 to 0.97 over store sizes and 0.72 to 0.89 over distances; the constants do not transfer. Correlated keys: B.11 replaces log⁡N\log N by an effective count. General queries: the tuning curve of Corollary 2 is the object; the theorem is not extended. Value mixing: Proposition 1(iii) bounds the softmax weights in total variation by βε/2\beta\varepsilon/2, so the output moves by at most (βε/2) diam{vj}(\beta\varepsilon/2)\,\mathrm{diam}\{v_j\}.

W3: Architectural Scope

A new Section 2 paragraph states the scope. Partial RoPE: un-rotated dimensions are bands at θ=0\theta = 0, coherent at every distance, without resolution or aliasing; Theorem 2 permits any linear map on them. NoPE: the band statements do not apply; Proposition 3 holds. Hybrids: RoPE layers are covered layer by layer; state-space layers keep a fixed-size state, not an addressed store, and lie outside. Rescaled spectra: new Corollary 4 predicts coverage and alias integers under YaRN and interpolation; the predictions held on all 17 captured buffers (272 of 272 alias integers); in every row only the slow half of the bands carries retrieval (new Table 5, F.13).

Q: Training for Compressibility

KV-CAT (Gelberg et al., 2026) continues pretraining with masked slots. RoAM predicts: (i) coverage, alias distances and the base bound are fixed by the frequencies, untouched by training; (ii) training changes band energy, margins and live slots, all measurable (Corollary 2, Theorem 3); (iii) slot removal is classified, not certified; the deciding statistic is attention mass on removed slots (median 0.41, 90th percentile 0.89 under H2O; Table 23). Section 8 now cites it; once its checkpoints are released, all three can be measured with our code.

We thank the reviewer for the thorough reading and gladly discuss further.

I thank the authors for their detailed rebuttal and the substantial additional experiments. In particular, the new band-wise precision allocation results (Tables 25–26) are a meaningful response to my concern about limited practical implications, showing considerable improvements over uniform precision. I also appreciate the additional analysis of YaRN and longer contexts, as well as the clarification regarding which theoretical results rely on simplifying assumptions.

That said, some concerns remain. While the new compression results are encouraging, the comparison is primarily against uniform precision rather than existing sophisticated KV-cache compression methods, making the practical contribution somewhat less clear. Furthermore, the compression certificate remains quite conservative, certifying only a small fraction of reads even at higher precision. Finally, while I appreciate the clarification that only Theorem 3 relies on independent keys and queries identical to target keys, these assumptions still underlie the main retrieval-capacity result, leaving a gap between the theoretical analysis and realistic transformer retrieval.

Overall, I think the rebuttal strengthens the paper, particularly its practical contributions. I still find the theoretical perspective interesting and the experimental validation thorough, and therefore maintain my positive score.

Thank you for the follow-up and for maintaining the score.

On the comparison: Corollary 8 fixes how a bit budget is split across bands and is independent of the quantizer, so it can be applied inside an existing method rather than compete with it; the uniform arm of Tables 25 and 26 isolates the allocation, which is the quantity the certificate decides. We have started that experiment: Corollary 8's allocation inside KIVI-2 (same quantizer, groups, residual window and values; only the key widths vary across bands at the same 2-bit average) against stock KIVI-2 on three models at 8,192 tokens, and will post the result before the discussion closes if the runs finish in time. The certificate is a worst-case, distribution-free bound and is reported as such, and the assumptions of the capacity theorem are stated in Table 10 and its ordering tested on captured keys in Section F.11.

Result of the KIVI-2 comparison promised above. Corollary 8 applied inside KIVI-2 (its own quantizer, 32-token groups, 128-token residual window, 2-bit values; only the key width varies across bands at the same 2-bit average per head, so the footprint is identical) against stock KIVI-2, three models, 8,192 tokens, seed 42. Entries are RULER mean over the five subtasks / PG-19 perplexity.

ModeluncompressedKIVI-2KIVI-2 + Corollary 8
Llama-3.1-8B0.8880.888 / 7.997.990.8210.821 / 8.478.470.8280.828 / 8.378.37
Mistral-7B v0.30.8150.815 / 6.566.560.6940.694 / 6.766.760.7920.792 / 6.726.72
Qwen2.5-7B0.7960.796 / 8.738.730.6980.698 / 9.019.010.7830.783 / 8.958.95

The allocation improves stock KIVI-2 on all three models, on retrieval and on perplexity, at the same footprint; it recovers 10%, 81% and 87% of the retrieval KIVI-2 loses. On Llama-3.1-8B, LongBench passage retrieval is 0.40 against 0.34 and HotpotQA 0.25 against 0.22. The uniform arm runs through the same code and is bit-exact with stock KIVI-2 (its perplexity, 8.47, matches the fleet's KIVI-2 cell). The corollary allocates by the range each band presents to the quantizer; KIVI scales per 32-token group, so that range is the within-group spread, and computed from it the rule keeps the fastest and slowest bands at or above 2 bits and takes bits from the middle bands, where the spread is smallest. This comparison is reported in the new Section F.16 (Table 37) of the revised PDF, uploaded today; Section 7 now points to it.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.