acceptodds
Under review as a conference paper at ICLR 2027

Exact Finite-Query KV Cache Compilation

Abstract

Query-aware key value (KV) cache compression fits a chosen slot count to reference queries, but a successful fit cannot show that fewer slots would fail. We characterize the number of shared KV slots needed to preserve the normalized attention outputs of a finite protected query set exactly. A ratio identity maps each query to a ray of feasible replacement values. With query-specific positive weights, the minimum count is one plus the smallest dimension of an affine subspace meeting all rays. Two queries can already rule out one slot. For grouped query attention (GQA) with query heads per KV head, protecting positions requires slots for entries under explicit rank and key-realizability conditions. All 431,256 evaluated KV-head configurations satisfy the conditional law. With full query rank and realizable weights, a related construction represents an entire prefix by standard KV slots per head for a known -step trace. Across four models, native 32-bit floating-point (FP32) execution preserves every protected token through eight steps, removing 89.31% to 96.95% of same-dtype KV tensor bytes on 524-slot prefixes. The results separate fitting a cache from certifying its capacity within the shared KV representation.

Primary area:
foundation or frontier models, including LLMs
Keywords:
KV Cache Compression, Grouped Query Attention, Exact Cache Compilation, Memory Optimization

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_i6VXOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2(+1)
Soundness
2
Read review
Paper summary

This paper points out that existing KV cache compression methods cannot tell whether fewer slots would suffice. It addresses this by characterizing the minimum number of shared KV slots needed to exactly preserve the attention outputs of a known finite query set.

Critical strengths

S1. The paper raises a valid point that existing compression methods only show that a given slot count is feasible, but not that fewer slots are impossible. It turns this into a well-defined question and provides a clean answer.

Critical weaknesses

W1. Writing quality: The paper is hard to follow. Many coined terms (score-relaxed, key-realizable, visibility-consistent) appear in quick succession, without enough intuition, and nearly every experimental paragraph adds multiple caveats that bury the main findings. The organization is also unconventional and fragmented, with seven sections before the conclusion.

W2. Limited practical use & theoretical depth: As the authors acknowledge in Section 7, the whole-prefix construction requires the future queries to be known in advance. In the experiments, these queries are collected by first running the model with the full cache. While this does not undermine the theoretical slot analysis, it leaves the practical benefit of the construction undemonstrated. Moreover, when the queries are known, the established attention-state merge discussed in Appendix B.12 is more compact in the paper’s own scalar-count comparison and does not require the rank condition. It is therefore unclear what practical advantage the proposed shared-KV form provides. In addition, The theoretical contribution also seems limited, as the exact slot counts hold in the score-relaxed setting or under rank and realizability conditions. For the whole prefix, Tg is only an upper bound, and the minimum slot count remains open.

I don’t think a paper needs to offer both practical benefits and theoretical depth, but given the practical focus of this field (KV cache compression), I feel the paper does not strike a good balance between the two, and the writing quality also makes its contributions harder to appreciate.

Questions for authors

See weaknesses

3 comments

Thank you for pinpointing what made the paper hard to follow.

The contribution in three sentences. Compression methods fit a cache at a chosen size, but a successful fit cannot show that a smaller cache would fail. We determine how many key-value (KV) slots are necessary and sufficient to reproduce the attention outputs of a known set of queries, the error that any smaller cache must incur, and caches that reach these limits. Because the construction uses the queries, it is an offline reference point, like Belady's optimal policy for cache replacement, rather than a deployable compressor.

One example instead of the jargon. Replacing two cached tokens by one slot requires a single stored value that each protected query, with a weight of its choosing, can use to restore its exact output. For each query the usable values form a ray (Theorem 1). In the paper's one-dimensional example the two rays are (3/2,∞)(3/2,\infty) and (−∞,2/3)(-\infty,2/3); they do not meet, so one slot is impossible, while two slots suffice. Under grouped-query attention (GQA) every decode step brings gg such queries to each KV head, which is why, under a rank condition, the exact count is min⁡(k,tg)\min(k,tg) for a group of kk tokens and tt steps.

The coined terms (W1). The revision retires three of them. A protected query is one whose attention output must stay unchanged. Score-relaxed becomes the free-weight count: the minimum when each protected query may weight the new slots independently, which isolates what the values allow (Theorem 4). Key-realizable becomes realizable: shared keys produce the weights, as in an actual cache (Theorem 5). Visibility-consistent becomes one stated assumption: every protected query sees all replaced tokens and new slots, as under causal masking.

Organization (W1). The revised PDF has five sections before the conclusion instead of seven: an introduction built on this example (Figure 1), related work, one theory section (exact count, GQA law with its budget rule, smaller budgets, entire prefixes), experiments, and discussion. Table 1 collects the notation, Table 2 summarizes every study, each experimental paragraph opens with its finding, and numerical qualifications sit in one scope paragraph and the appendix.

Theoretical depth (W2). We agree the original version stressed construction details over what the capacity results mean. Three new results also address the limits you note.

  1. Whole prefixes now have a matching lower bound. The original certificate fails there for a structural reason: the few appended values are shared by all gg heads (Proposition 13). Let UU hold the augmented targets (Or,1)(O_r,1) and WW the unchanged complement values (vs,1)(v_s,1). Every exact replacement needs m≥b:=rank⁡[U;W]−rank⁡Wm\ge b:=\operatorname{rank}[U;W]-\operatorname{rank}W; when b=n=Tgb=n=Tg, keeping nn independent original keys and solving their values attains nn. Interval arithmetic on captured operands certifies b=n=28b=n=28 in all 192 layer-head problems we tested, so TgTg is the exact minimum there (real-arithmetic attention).
  2. Fewer assumptions. The GQA law min⁡(k,tg)\min(k,tg) now holds without the full query-rank condition, by the same retained-key argument; its remaining rank condition held in all 431,256 configurations we tested.
  3. Approximation. Every mm-slot cache obeys ∥Onew−O∥F≥(∑j>mσj(B)2)1/2\lVert O_{\rm new}-O\rVert_F\ge(\sum_{j>m}\sigma_j(B)^2)^{1/2}, where BB is the target output matrix with the unchanged values projected out, and an explicit construction nearly attains this bound.

Practical use (W2). We agree that the attention-state merge of Appendix B.12 stores less; our object is the KV format that every eviction, merging and compaction method uses. Under GQA and the rank condition, merging two tokens into one slot cannot be exact even for one decode step, while groups larger than tgtg compress exactly; Reviewer xu7u highlights this consequence for CaM, KeepKV, AsymKV and KVSlimmer. A new experiment shows what the limits reveal (Qwen2.5-0.5B, 64 ARC-Challenge/OpenBookQA prompts, all 24 layers and both KV heads, 511-token prefix, next 4 decode steps). With 14 slots per KV head, no cache can go below 1.3% median attention error, our construction attains 1.4%, and SnapKV, H2O and StreamingLLM have 61 to 62%; at 224 slots SnapKV and H2O still have 3.9% and 5.2%. So these methods' loss is not a capacity limit of 14 slots, which no fitting experiment could establish. The picture is the same at 8 decode steps and across layer depths. A 128-question check shows exactness carrying through all 24 layers to the answer: the compiled cache keeps all 128 full-cache answers, while same-size heuristics change 33 to 119. Full-cache accuracy (48/128) is preserved by design, not exceeded.

The revised PDF is uploaded; OpenReview's comparison view shows every change. We hope the clearer presentation and stronger results make the contribution easier to assess, and would be grateful if you would reconsider your rating.

Dear Reviewer i6VX,

We uploaded a revised PDF, last updated on November 13, and would like to ask you directly about the point you rated lowest.

You found the paper difficult to follow, with coined terms in quick succession, caveats in nearly every experimental paragraph, and seven sections before the conclusion. We rewrote the paper for this. It now has five sections before the conclusion. Figure 1 on the first page shows the setting, the geometric argument and the main count. Three of the coined terms are gone, and the ones that remain are defined where they first appear. Table 1 lists the notation and Table 2 lists every experiment with its outcome. Each experimental paragraph opens with its finding, and the scope is stated once, in Section 5. In the PDF, new content is colored and reorganized text is left black.

Two limits you noted under theoretical depth are also resolved. You wrote that for the whole prefix TgTg is only an upper bound and the minimum remains open. Theorem 8 now gives a lower bound, and on all 192 tested problems the certified minimum is Tg=28Tg=28. You wrote that the exact counts hold under rank and realizability conditions. The GQA law in Theorem 5 now needs only its ray-rank condition, which held in all 431,256 tested configurations.

Is the revised paper readable for you now? If a section is still hard to follow, please name it and we will address it before the discussion closes on November 18.

Thanks for the detailed response and the revision, and sorry for getting back so late. The revised version is easier to read, so I’m raising presentation to 2. Theorems 5 and 8 address part of what I raised on the theory side. But I still don’t see much practical value, because building the cache needs the future queries from a full-cache run. Considering this and the concerns raised by the other reviewers, I’m keeping my rating.

Reviewer_xu7uOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the minimum number of shared synthetic KV slots mm required to preserve the normalized attention outputs O(qr;M)O(q_r; \mathcal{M}) of a declared finite set of "protected queries" R\mathcal{R} (n=∣R∣n = |\mathcal{R}|) exactly within a single attention head. Using a cross-multiplied exact ratio identity (Theorem 1), the authors map each query constraint r∈Rr \in \mathcal{R} to a positive ray Lr+(S)={Or+τD~r:τ>0}\mathcal{L}_r^+(S) = \lbrace O_r + \tau \widetilde{D}_r : \tau > 0\rbrace in value space, where D~r=∑i∈Spri(vi−Or)\widetilde{D}_r = \sum_{i \in S} p_{ri}(v_i - O_r) is the candidate group's signed output contribution relative to the full normalized output OrO_r.

By separating value geometry ("score-relaxed" positive weights yrj>0y_{rj} > 0 chosen independently per query) from key construction ("physical key realizability" via a shared synthetic key kjk_j), the paper establishes three main theoretical results:

  1. Score-Relaxed Slot Count (Corollaries 2–3, Theorem 4): One protected query always admits a 1-slot replacement, whereas two queries with disjoint positive rays (La+(S)∩Lb+(S)=∅\mathcal{L}_a^+(S) \cap \mathcal{L}_b^+(S) = \varnothing) form the minimal witness ruling out any 1-slot replacement regardless of key parameterization. For m≥1m \ge 1 slots, every ray must intersect the relative interior of the convex hull conv{c1,…,cm}\mathrm{conv}\lbrace c_1, \dots, c_m\rbrace, yielding an exact score-relaxed minimum of m+⋆=1+min⁡τ1,…,τn>0affdim{Or+τrD~r:r=1,…,n}≤dv+1m_+^\star = 1 + \min_{\tau_1, \dots, \tau_n > 0} \mathrm{affdim}\lbrace O_r + \tau_r \widetilde{D}_r : r = 1, \dots, n\rbrace \le d_v + 1.
  2. Conditional Physical GQA Law (Theorem 5): Under Grouped Query Attention (GQA) with g=Hq/Hkvg = H_q / H_{kv} query heads sharing each KV head, protecting tt decode positions imposes n=tgn = tg joint constraints per physical KV head. When the augmented ray matrix Rray=[Oˉ1,…,Oˉb,Dˉ1,…,Dˉb]R_{\mathrm{ray}} = [\bar{O}_1, \dots, \bar{O}_b, \bar{D}_1, \dots, \bar{D}_b] (b=min⁡(k,n)b = \min(k, n)) has full column rank 2b2b and (for n<kn < k) the joint query matrix Q∈Rn×dkQ \in \mathbb{R}^{n \times d_k} has full row rank (n≤dkn \le d_k) with key-realizable positive weights, the score-relaxed and physical minima coincide at m+⋆=min⁡(k,tg)m_+^\star = \min(k, tg).
  3. Whole-Prefix Compilation (Theorem 6): For a known TT-step reference trace after an LL-token prefix (L>TgL > Tg, Tg≤dkTg \le d_k), applying homothetic simplex expansion around the centroid of the prefix-only outputs xr=urx_r = u_r and solving the linear system QK∗⊤=GQ K^{\ast\top} = G (after inverting RoPE at assigned logical positions) constructs a dense synthetic KV cache of M=Tg=THq/HkvM = Tg = T H_q / H_{kv} slots per KV head.

Empirically, the authors test 928,695 candidate groups (2,786,085 layer-group evaluations) across 6 checkpoints and 4 datasets, finding that a single scheduled query pair certifies 1-slot infeasibility in 100% of cases. Across 431,256 KV-head configurations, all satisfy the rank conditions and match m+⋆=min⁡(k,tg)m_+^\star = \min(k, tg). Finally, across 8 model-prompt cases and nested horizons T∈{1,2,4,8}T \in \lbrace 1, 2, 4, 8\rbrace, whole-prefix compilation preserves all protected greedy/teacher-forced tokens in native FP32 execution.

Critical strengths
  1. Exact Decoupling of Value-Space Convex Geometry from Key Realizability (Theorems 1, 4, and 5): The cross-multiplied ratio identity ∑j=1myrjZr(cj−Or)=D~r\sum_{j=1}^m \frac{y_{rj}}{Z_r}(c_j - O_r) = \widetilde{D}_r (Theorem 1) provides a clean mathematical separation between value-space feasibility (whether mm shared value vectors can positively span the required output displacements) and key-space realizability (whether mm shared key vectors can induce those positive unnormalized weights under dot-product or soft-capped attention). This yields two consequential insights for the KV-cache merging literature (e.g., CaM, KeepKV, AsymKV, KVSlimmer):

    • First, the two-query disjoint-ray test (Corollary 3) certifies when exact 1-slot merging is impossible before choosing any key parameterization or running any optimization algorithm.
    • Second, Theorem 5 explains why GQA (g=Hq/Hkvg = H_q / H_{kv}) is a major structural barrier to exact local token merging: even for a single decode step (t=1t = 1), any pair of tokens (k=2k = 2) cannot be merged into 1 slot whenever g≥2g \ge 2 and RrayR_{\mathrm{ray}} has full column rank, because min⁡(2,g)=2\min(2, g) = 2.
  2. Exemplary Numerical Honesty and Explicit Scope Delimitation: The manuscript is unusually rigorous and transparent about the boundaries of its theoretical and empirical claims. The authors explicitly separate mathematical float64/extended-precision replay from native FP32 and BF16 execution (Tables 18–19), prove why the whole-prefix lower bound cannot be certified by Theorem 5 when g>1g > 1 (Proposition 10, Appendix E.5), compare their storage footprint directly against query-indexed attention-state merging (Appendix B.12), and report negative generalization results on held-out queries and post-horizon continuation (Sections D.4, E.4, and F.4).

Critical weaknesses
  1. Oracle Circularity, Inferiority to Attention-State Composition on Known Traces, and Catastrophic Generalization Failure on Unseen Queries:

    • Oracle circularity in whole-prefix compilation: Constructing the M=TgM = Tg whole-prefix cache (Theorem 6, Section 4) requires already knowing the exact TT-step future query matrices Q∈RTg×dkQ \in \mathbb{R}^{Tg \times d_k}, exact outputs OrO_r, and prefix masses zrz_r at every layer and physical head (Appendix B.11). In autoregressive decoding, obtaining these multi-layer query trajectories for TT steps requires running a full-cache forward pass over those TT steps first (lines 466–469, 925–927). Thus, the method is an offline post-hoc trace interpolator rather than a predictive or online KV-cache compressor.
    • Strictly dominated by attention-state composition when queries are known: As the authors acknowledge in Section 7 (lines 457–462) and Appendix B.12 (lines 962–971), if the finite set of TT queries is known in advance, standard blockwise attention-state composition (e.g., Hydragen / FlashInfer's logaddexp merge of prefix-only output ur∈Rdvu_r \in \mathbb{R}^{d_v} and log-mass ℓr=log⁡zr∈R\ell_r = \log z_r \in \mathbb{R}, Eq. 17) achieves exact preservation using only Tg(dv+1)Tg(d_v + 1) scalars per KV head, requires no query-rank condition, requires no Tg≤dkTg \le d_k horizon bound, and requires no O(NℓHkv[n2(dk+dv)+n3])O(N_\ell H_{kv}[n^2(d_k+d_v)+n^3]) linear solve. Re-encoding those exact same TgTg states (ur,ℓr)(u_r, \ell_r) into synthetic KV slots via Theorem 6 increases storage by nearly 2×2\times to Tg(dk+dv)Tg(d_k + d_v) scalars just to stay in standard KV format.
    • Worse than simple mean pooling on held-out queries: Because the key solve Qkj=log⁡y⋅jQ k_j = \log y_{\cdot j} only constrains kjk_j on the nn-dimensional subspace row(Q)⊂Rdk\mathrm{row}(Q) \subset \mathbb{R}^{d_k} and uses an arbitrary homothetic simplex expansion factor λ>1\lambda > 1 (Eq. 15) without regularizing out-of-subspace key norms, any query outside the declared set suffers severe exponential score distortion. Consequently, on held-out queries (Appendix D.4, lines 1352–1356; Appendix E.4, lines 1435–1438), the compiled cache achieves a median relative error of 0.210 compared to 0.091 for simple uniform mean pooling (losing to mean pooling on >51% of comparisons), and in 31 of 32 whole-prefix windows greedy generation diverges immediately after the TT-step protection horizon ends (Tables 18–19).
  2. Complete Breakdown in Standard Serving Precision (BF16), Constructive Horizon Limit (T≤⌊dk/g⌋T \le \lfloor d_k / g \rfloor), and Unresolved Whole-Prefix Lower Bound:

    • Failure in BF16: Modern LLM inference serves models and KV caches in BF16/FP16 (or lower), never FP32. Because the compiler inverts the correlated query matrix QQ to solve QK∗⊤=log⁡YQ K^{*\top} = \log Y and relies on exact cancellation after exponentiation in the softmax, rounding the compiled cache and execution to BF16 causes the operator relative error εBF16\varepsilon_{\mathrm{BF16}} to explode to 0.585–0.918 (Appendix E.6, line 1494; Tables 18–19, where Qwen2.5-0.5B reaches 0.9182 and Qwen3-4B reaches 0.6890). A KV-cache representation that requires full FP32 model execution to avoid >50%>50\% operator error is not practical for deployment, and the paper's 1.14–4.72s compilation overhead (0.28–1.33s for whole-prefix alone) yields no decode speedup (median speed ratios 0.987–1.003, Appendix E.6).
    • Constructive horizon ceiling Tg≤dkTg \le d_k in Theorem 6: While score-relaxed value feasibility holds in at most dv+1d_v + 1 slots for any number of queries (Theorem 4), the paper's constructive physical key solver (Theorem 6) requires n=Tg≤dkn = Tg \le d_k so that Q∈Rn×dkQ \in \mathbb{R}^{n \times d_k} has full row rank and QK∗⊤=GQ K^{*\top} = G can assign independent scores to M=TgM = Tg slots. For models with large GQA group size gg or smaller head dimension dkd_k—such as Qwen2.5-0.5B (g=7,dk=64g = 7, d_k = 64)—Theorem 6's compilation algorithm is restricted to at most ⌊64/7⌋=9\lfloor 64 / 7 \rfloor = 9 decode steps (and at most T=32T = 32 steps for Qwen3-4B or Llama-3.1-8B where g=4,dk=128g = 4, d_k = 128), regardless of prefix length LL.
    • The lower-bound certificate fails structurally on whole prefixes for all GQA models (g>1g > 1): While the paper frames its contribution around certifying exact minimum slot counts, Proposition 10 (Appendix E.5, lines 1447–1480) proves that when SS is the whole prefix and the visible complement consists of at most TT shared appended values, rank[U,Dˉ]≤min⁡(dv+1,Tg+T)<2Tg\mathrm{rank}[U, \bar{D}] \le \min(d_v + 1, Tg + T) < 2Tg whenever g>1g > 1. Thus, Theorem 5's lower-bound certificate never applies to the whole-prefix setting on any of the evaluated models (g∈{2,4,7}g \in \{2, 4, 7\}), leaving the true minimum slot count of a whole prefix open.
Questions for authors

Clarification Requests

  1. Why Does BF16 Fail So Severely, and Can the Underdetermined Degrees of Freedom Fix It?: When n=Tg<dkn = Tg < d_k, the linear system Qkj=log⁡y⋅jQ k_j = \log y_{\cdot j} is underdetermined with a (dk−n)(d_k - n)-dimensional nullspace, and the simplex expansion parameter λ>1\lambda > 1 in Eq. 15 is also a free hyperparameter. How are λ\lambda and the particular solution kjk_j chosen in your implementation (e.g., minimum ℓ2\ell_2-norm pseudoinverse kj=Q†log⁡y⋅jk_j = Q^\dagger \log y_{\cdot j})? Does the massive BF16 error (εBF16∈[0.35,0.92]\varepsilon_{\mathrm{BF16}} \in [0.35, 0.92] on Qwen2.5/Qwen3 in Tables 18–19) stem from large key norms ∥kj∥2\|k_j\|_2 amplified by small singular values of QQ, and can tuning λ\lambda or regularizing kjk_j stabilize BF16 execution?
  2. Concrete Use Case Relative to Hydragen / FlashInfer State Merging: Given that Theorem 6's constructive solver requires knowing the exact TT-step queries across all layers in advance, fails in BF16, is restricted by its full-row-rank condition to T≤⌊dk/g⌋T \le \lfloor d_k / g \rfloor steps, and stores (dk+dv)/(dv+1)≈2×(d_k + d_v)/(d_v + 1) \approx 2\times more scalars than directly caching the prefix attention states (ur,ℓr)(u_r, \ell_r) via Eq. 17 (Appendix B.12), can you identify a concrete scenario where compiling known queries into shared KV slots via Theorem 6 is advantageous over storing (ur,ℓr)(u_r, \ell_r)?
  3. Whole-Prefix Minimum Slot Count When g>1g > 1: In light of Proposition 10 (rank[U,Dˉ]≤n+T<2n\mathrm{rank}[U, \bar{D}] \le n + T < 2n for g>1g > 1), do you conjecture that the true score-relaxed minimum slot count for a whole prefix is closer to ≈12(Tg+T)\approx \frac{1}{2}(Tg + T) or still TgTg, and can direct nonlinear optimization over τ1,…,τn>0\tau_1, \dots, \tau_n > 0 in Theorem 4 (Eq. 6) find lower-dimensional affine subspaces for small TT?

Suggestions for Future Work

  1. Regularized Subspace Compilation for Unseen Queries and Tg>dkTg > d_k: Replacing the exact interpolation solve QK∗⊤=GQ K^{*\top} = G with a ridge-regularized or distributional least-squares objective over a calibration query distribution (while constraining cjc_j to lie near the empirical value manifold rather than an unregularized homothetic expansion) could prevent held-out query error from degrading below mean pooling and remove the hard Tg≤dkTg \le d_k horizon barrier.
  2. Exploiting ker⁡(WO)\ker(W_O) Across Query Heads (Proposition 8): In GQA or MLA architectures where HqdvH_q d_v exceeds the residual stream dimension or where WOW_O has rapidly decaying singular values, relaxing per-head exactness to block-output exactness (o′−o∈ker⁡(WO)o' - o \in \ker(W_O)) could substantially reduce the effective constraint count below TgTg.
6 comments

Thank you for the detailed and precise analysis.

W1, W2, Q2: oracle queries, state merging, concrete use. We agree that compilation needs the reference queries and that the query-indexed states of Eq. 17 are smaller (n(dv+1)n(d_v+1) versus n(dk+dv)n(d_k+d_v) scalars, n=tgn=tg); we do not claim to beat them. Our object is the shared-KV format in which every eviction, merging and compaction method operates, and the construction is its offline optimum, in the role Belady's MIN plays for cache replacement: it needs the future and measures what any mm-slot cache can achieve. A new experiment shows what this reveals (Qwen2.5-0.5B, 64 ARC-Challenge/OpenBookQA prompts, all layers and KV heads, 511-token prefix, next 4 decode steps, n=28n=28). At 14 slots per KV head, median relative attention error is 1.3% for the bound that every 14-slot cache obeys, 1.4% for our query-informed construction (within 1.5x of the bound in 99.9% of cases), 7.8% for top-attention tokens with values refit on the same queries, and 61 to 62% for SnapKV, H2O and StreamingLLM; Qwen3-4B and Llama-3.2-1B give the same picture (Sec. 4.3). The state table cannot provide this comparison, since it is not a KV cache, and the cited shared-prefix systems pass prefix KV tensors to their kernels.

W3: held-out queries and post-horizon behavior. The held-out result (0.210 versus 0.091 for mean pooling) stands, and we now prove that protected outputs and normalizers alone cannot determine unseen responses: two caches can share all of them yet give opposite outputs at an unseen query. We make no unseen-query claim. Two corrections. Tables 20 and 21 (formerly 18 and 19) show 17/32 immediate divergences, not 31/32 (31/32 diverge within 12 steps). The keys are the minimum-norm solution K0=Q†GK_0=Q^\dagger G, which has no component outside the query row space; for QN=0QN=0, ∥K0+N∥F2=∥K0∥F2+∥N∥F2\|K_0+N\|_F^2=\|K_0\|_F^2+\|N\|_F^2, so nullspace terms cannot shrink keys.

Q1, W4: BF16. Correlated queries create large common score offsets: in one probe an offset near 1439 has BF16 spacing 8, exceeding the intended contrast log⁡29=3.37\log29=3.37. With identical BF16 storage, FP32 QK and scaling lower median error from 0.0087 to 0.0027 (238/240 cases), while dilation changes help 184 and hurt 56, so tuning λ\lambda is no uniform fix. A different construction runs in standard BF16: thin QR gives keys with QK⊤=IQK^\top=I, values are the captured contexts, and one power-of-two scale makes the executed softmax exactly one-hot. On four fixed prompts, full-model BF16 replay keeps all 16 complete logit vectors bitwise in teacher-forced and free modes across 24 layers, with 94.5% less KV storage; construction for all 24 layers of the four prompts takes 1.8 s without linear programming. It relies on machine underflow, so we report it apart from real-arithmetic exactness.

W5: horizon ceiling. It belongs to the solver, not the problem. For distinct queries, keys kj=αqjk_j=\alpha q_j make Wij=exp⁡(αqi⊤qj)W_{ij}=\exp(\alpha q_i^\top q_j) positive definite, so nn slots interpolate any targets without n≤dkn\le d_k; a direction-based variant bounds the coefficient condition number by 2. Native FP32 replay on four prompts preserves every protected token at 12 and 16 steps (n=84,112>dk=64n=84,112>d_k=64), all before end-of-sequence, with maximum relative logit error 1.1×10−61.1\times10^{-6}.

W6, Q3: whole-prefix minimum. Using the complement directly, with UU the augmented targets and WW the augmented complement values, max⁡(1,b)≤m+⋆≤min⁡(n,b+s)\max(1,b)\le m_+^\star\le\min(n,b+s), where b=rank⁡[U;W]−rank⁡Wb=\operatorname{rank}[U;W]-\operatorname{rank}W and s=rank⁡Ws=\operatorname{rank}W. If b=nb=n, keeping nn independent original keys and solving their values attains nn without full query rank. Interval arithmetic on the captured operands certifies b=n=28b=n=28, hence minimum TgTg, in all 192 layer-head problems tested (real-arithmetic attention). Our answer to Q3: the minimum is TgTg while b=nb=n, which requires n+s≤dv+1n+s\le d_v+1; beyond that, Theorem 4 caps the free-weight minimum at dv+1d_v+1, and the open question is the key-realizable minimum between bb and nn. Nonlinear fits only give upper bounds.

Suggestions. Calibration variants gave no unseen-query advantage, consistent with the proof above: in free generation on 56 held-out questions, prefill-calibrated caches with mass correction or bounded values answered 10 to 17 correctly with 64 slots, versus 19 for the full cache and 18 for uniform retention with 28. In the new experiment, values fitted by least squares to prefill queries cut SnapKV's 14-slot error from 62% to 52%, still over 35x the bound. For ker⁡WO\ker W_O: all 24 output projections of Qwen2.5-0.5B have exact rank 896, so this checkpoint offers no kernel to exploit.

We also thank you for drawing out the consequences for CaM, KeepKV, AsymKV and KVSlimmer; the revised introduction leads with them. The revised PDF places them in Sections 3.3 to 3.5 and 4.3 to 4.4, proofs in Appendix C, and experiments in Appendix H. We would be grateful if they support a higher rating.

Dear Reviewer xu7u,

We revised our reply above and the PDF on November 13. Edits do not trigger a notification, so we summarize what changed for the weaknesses you listed.

Three of them are now settled by results in the paper. On the whole-prefix lower bound (W6), Theorem 8 gives a bound that uses the appended tokens, which is where the original test failed. Interval arithmetic on the captured operands certifies that Tg=28Tg=28 slots is the minimum on all 192 layer-head problems we tested (Appendices C.2 and H.6). On the horizon limit Tg≤dkTg\le d_k (W5), setting each key to a scaled protected query makes the weight matrix positive definite, so the limit belonged to the earlier solver and not to the problem. Native FP32 runs keep every protected token at 12 and 16 decode steps, with 84 and 112 queries per KV head against dk=64d_k=64 (Appendices C.3 and H.5). On BF16 (W4), a QR-based construction reproduces every protected logit vector bitwise in standard BF16 on four prompts (Appendix H.7). It relies on machine underflow, and the paper reports it apart from the real-arithmetic results.

On W1 and W2 we agree with you, and Section 5 says so. The construction needs the reference queries, and the query-indexed state table is smaller. What the KV-format result adds is a certified limit for the methods that work in that format. In three models, SnapKV, H2O and StreamingLLM sit 19 to 40 times above the bound at half the exact count (Figure 2). On 128 questions, five of the seven exact slots keep 124 full-cache answers (Figure 4).

Two further points. Tables 20 and 21 show that 17 of 32 continuations diverge at the first unprotected step and 31 of 32 within 12 steps, while the review gives 31 of 32 for the first step. We also found a negative result and report it in Appendix H.4. Refitting values on the most attended retained keys is exact in real arithmetic but ill-conditioned in FP32, and it keeps only 34 of the 128 answers in native execution.

Do the results on W4, W5 and W6 resolve those points for you, and do they change your assessment? We will answer any remaining question before the discussion closes on November 18.

Thank you for the thorough, constructive engagement during the discussion period, the substantial revision, and the follow-up summary. I also appreciate the two factual clarifications regarding Tables 20–21 (17/32 continuations diverging immediately at the first unprotected step and 31/32 within 12 steps) and the orthogonality of nullspace terms (∥K0+N∥F2=∥K0∥F2+∥N∥F2\|K_0 + N\|_F^2 = \|K_0\|_F^2 + \|N\|_F^2 for QN=0QN = 0), as well as your experiments testing the calibration and ker⁡(WO)\ker(W_O) suggestions.

Points Resolved in the Revision (W5, W6 / Q3)

I agree that two of the technical limitations raised in my initial review are cleanly resolved in real arithmetic:

  1. Whole-prefix lower bound (W6, Q3): Using the augmented unchanged complement W=(vs,1)W = (v_s, 1) directly via b=rank[U;W]−rank Wb = \mathrm{rank}[U; W] - \mathrm{rank}\,W (Theorem 8) resolves the structural rank bottleneck of the earlier [U,Dˉ][U, \bar{D}] test when Tg+T≤dv+1Tg + T \le d_v + 1, and your interval-arithmetic check certifies m+⋆=Tg=28m_+^\star = Tg = 28 across the 192 tested layer-head problems.
  2. Horizon ceiling Tg≤dkTg \le d_k (W5): Setting kj=αqjk_j = \alpha q_j (and its normalized direction variant) so that Wij=exp⁡(qi⊤kj)W_{ij} = \exp(q_i^\top k_j) is positive definite and solving linearly for values shows that Tg≤dkTg \le d_k was a limitation of the previous key-inversion solver rather than of real-arithmetic KV realizability, verified in FP32 at T∈{12,16}T \in \{12, 16\} (n=84,112>dk=64n = 84, 112 > d_k = 64).

Why My Overall Assessment Remains Unchanged

Despite these mathematical improvements and the clearer positioning around an offline capacity benchmark, carefully examining the new theoretical and empirical claims leaves core concerns unresolved—and exposes sharp tensions between the paper's real-arithmetic guarantees and actual floating-point KV caches:

  1. BF16 execution (W4 / Q1) remains unresolved for the main constructions, and the Appendix H.7 workaround is incompatible with W5:

    • Both the core exact compiler and the new approximate budget construction (Proposition 7 / Algorithm 1, Section 4.4) still rely on native FP32 execution rather than standard serving precision (BF16).
    • The new BF16 variant (Appendix H.7) constructs thin-QR keys satisfying QK⊤=IQK^\top = I, sets values to the captured contexts, and applies a large power-of-two scale so that BF16 softmax becomes exact one-hot via machine underflow. First, QK⊤=InQK^\top = I_n algebraically re-imposes the hard rank ceiling n=Tg≤dkn = Tg \le d_k, meaning the BF16 workaround (W4) and the Tg>dkTg > d_k kernel construction (W5, tested only in FP32) cannot hold simultaneously. Second, relying on floating-point underflow to turn attention into a brittle one-hot lookup table of captured contexts (suppressing off-target and live complement contributions via underflow) is an arithmetic edge-case artifact rather than a practical shared-KV representation. Moreover, Q1's request to diagnose σmin⁡(Q)\sigma_{\min}(Q) and ∥kj∥2\|k_j\|_2 on the failing whole-prefix BF16 runs (εBF16∈[0.35,0.92]\varepsilon_{\mathrm{BF16}} \in [0.35, 0.92]) was sidestepped in favor of a separate local probe.
  2. The revised Abstract's retained-key claim breaks down catastrophically in native FP32 (34/128 answers):

    • The revised Abstract and main text highlight removing the query-rank/synthetic-key requirement in Theorem 5 because "a larger group compresses to tgtg slots by keeping tgtg of its own keys [and solving their values]."
    • Yet as noted at the end of your November 15 comment (Appendix H.4), refitting values on the most attended retained keys is so ill-conditioned across correlated queries that in native FP32 execution it preserves only 34 of 128 answers on 4-choice ARC/OpenBookQA (essentially 25% random-guessing level, vs. 128/128). Elevating retained-key exactness to the Abstract when solving values on retained keys fails even in 32-bit floating point overstates a real-arithmetic existence argument as an operational property of KV caches.
  3. Downstream task evaluation (Section 4.4) only tests T=1T = 1 decode step, while multi-step generation hits the TgTg barrier:

    • In Section 4.4 (Qwen2.5-0.5B, g=7g = 7 query heads per KV head, 512-token prefix), the exact budget of 7 slots per KV head corresponds to T=1T = 1 single decode step (reproducing the single multiple-choice answer token immediately after a full 512-token reference pass computed it).
    • Multi-step generative tasks (such as GSM8K, used earlier as a query source) require T∼60–150T \sim 60\text{--}150 decode steps, where m⋆=min⁡(L,Tg)m^\star = \min(L, Tg) already saturates or exceeds a 512-token prefix (Tg≥420–1050Tg \ge 420\text{--}1050), offering little to no exact compression while post-horizon continuations still diverge rapidly (17/32 at step T+1T+1, 31/32 within 12 steps; 0.210 held-out error vs. 0.091 for uniform mean pooling).
Reviewer_s7oBOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how many shared KV slots are needed to exactly preserve the attention outputs of a fixed, finite set of known queries. It derives a ratio identity, characterizes the minimum slot count through the geometry of per-query rays, and, under rank and key-realizability conditions, gives the GQA formula m⋆=min⁡(k,tg)m^\star = \min(k, tg). It also gives a construction that replaces a whole prefix with TgTg synthetic slots per KV head for a known TT-step decoding trace. Experiments on four to six open models check that the rank conditions hold on real activations and that the compiled cache reproduces the protected tokens in FP32 for up to eight decode steps.

Critical strengths

The question of exact capacity for a finite query set is cleanly formulated, and the theoretical results are correct and clearly scoped under their stated assumptions.

Critical weaknesses
  1. Insufficient rationale for the problem. The paper motivates its question by noting that a successful fit at a given budget cannot show that fewer slots would fail. However, it does not explain why knowing the exact minimum slot count for a fixed set of known queries matters in practice, or what one would do differently with this number. Without this, it is hard to see why this problem needs to be solved.

  2. No practical benefit is shown, and the setting makes it hard to show one. A KV cache compression method is meant to improve efficiency, so it should show a concrete gain and practical use. The paper does neither. Most importantly, there is no downstream accuracy evaluation at all, even though output preservation is the paper's central claim. ARC, GSM8K, and OpenBookQA are used only as sources of query vectors; no task accuracy is reported for any of them. The only evidence of preservation is token agreement with the full cache on two prompts per model for at most eight decode steps. The paper also does not show better accuracy than other methods at a fixed compression ratio. The memory savings are computed from tensor shapes rather than measured, and there are no results on serving throughput or batch size. Finally, the method is circular: compiling a cache that preserves a TT-step output requires the queries of those steps, and these are only available after decoding with the full cache. The compiled cache can therefore only reproduce an output that has already been computed. Beyond the protected steps it gives no guarantee, and continuations diverge within a few tokens.

Questions for authors
  1. In what practical scenario are the future decode queries known in advance while the full cache is unavailable or too costly to keep? How would the compiled cache be used in such a scenario?
  2. Beyond a theoretical certificate, how should practitioners use the exact slot count m⋆m^\star, for example when choosing budgets or designing compression methods?
  3. Can you report downstream task accuracy, or measured memory and serving throughput, that show a benefit of the compiled cache over the full cache or existing compression methods?
2 comments

Thank you for the direct questions about practical value.

Q1: a scenario with known future queries. We do not claim a deployment in which future queries are known while the full cache is unavailable, and Section 5 of the revision says so. The compiled cache plays the role of an offline optimum, as Belady's MIN policy does for cache replacement: MIN also needs the future, and it defines what any policy could achieve and how far practical policies are from it (it even serves as a training target for learned online policies). Here the reference pass is part of that measurement, not a deployment step. For shared key-value (KV) caches we give the corresponding limits: the exact minimum slot count, a necessary error at every slot budget, and caches that attain or nearly attain them. The known-query setting is also the one query-aware compaction already uses: Fast KV Compaction fits synthetic keys and values to a set of reference queries. Our bounds state how many slots such a fit needs and what error it must accept on its own reference set, which the fit itself cannot certify. We agree that nothing is guaranteed beyond the protected steps.

Q2: how practitioners use the count. Without it, a fit that fails at mm slots cannot be attributed to the optimizer or to the budget; with it, that attribution is immediate. (a) Merge units. Under grouped-query attention (GQA) with g≥2g\ge2 query heads per KV head, merging two tokens into one slot cannot be exact even for one decode step whenever the rank condition holds (it held in all 431,256 tested configurations), while under Theorem 5's conditions a group of kk entries compresses exactly iff k>tgk>tg. Exact merging must operate on groups larger than tgtg, not on pairs; Reviewer xu7u draws the same lesson for CaM, KeepKV, AsymKV and KVSlimmer. (b) Budgets. Every mm-slot replacement obeys ∥Onew−O∥F≥(∑j>mσj(B)2)1/2\lVert O_{\rm new}-O\rVert_F\ge(\sum_{j>m}\sigma_j(B)^2)^{1/2}, where BB is the target output matrix with the unchanged values projected out, and a closed-form construction nearly attains it. The new Algorithm 1 turns the pair into a budget rule: for a target error it returns the fewest slots any cache could use and a cache that meets the target, at most one slot apart in at least 98% of the cases below, in about 25 ms per prompt. (c) Diagnosis. Compare a method's error with this bound. New experiment in three models, 64 ARC-Challenge/OpenBookQA prompts each, every layer and KV head, 511-token prefix, next 4 decode steps. Slots per KV head for 5% relative attention error (median case; other rules: smallest tested budget):

Qwen2.5-0.5BQwen3-4BLlama-3.2-1B
bound: no cache uses fewer876
our construction (queries known)977
top-attention + refit (queries known)211212
SnapKV / H2O (prefill only)224/448224/448448/448

StreamingLLM misses 5% in 49 to 74% of cases even at 448 of 511 slots. At half the exact count the online rules sit 19 to 40x above the bound in the median, while ours stays within 1.5x in at least 99.9% of cases. For a practitioner this locates the loss: it is not a capacity limit of the slots, but comes from not knowing the queries and from keeping original tokens instead of constructed ones. Accuracy at one compression ratio cannot reveal this.

Q3: accuracy, measured memory, throughput. Task level, 128 questions (64 ARC-Challenge, 64 OpenBookQA; 512-token prompts; all 24 layers; 7 slots per KV head): the compiled cache keeps all 128 full-cache answers and full-vocabulary top-1 tokens, while top-attention retention, mean pooling and uniform retention at the same 7 slots change 33, 109 and 119 answers and score 49, 32 and 34. Exact preservation reproduces full-cache accuracy (48/128) by design; the one extra correct answer of top-attention comes with 33 changed answers. Below the exact count the loss is gradual (new Figure 4, Appendix H.4): our 5-slot caches keep 124 of the 128 answers, top-attention retention needs 112 slots for that, and SnapKV, H2O and StreamingLLM keep 102, 98 and 106 at 112 slots. Measured memory: 12,558,336 versus 172,032 bytes of KV tensors per case. The exact path for all 128 questions took 11.9 s, 7.5 s of it in the reference pass. In the paper's long-prefix runs decode latency stayed within 1.3% of the full cache, and we do not claim throughput or batch-size gains, since building the cache requires that pass.

Protection also holds natively at 12 and 16 decode steps on four prompts, and a QR-based variant reproduces complete logit vectors bitwise in standard BF16 with 94.5% less KV storage.

The revised PDF states this role in Sections 1 and 5, adds the error bounds and Algorithm 1 (Section 3.4) and this comparison (Section 4.3, Table 3) to the main text, and reports measured storage (Section 4.4, Figure 4); the new TL;DR is in our general comment. We would be grateful if this clarification and the new evidence lead you to reconsider your rating.

Dear Reviewer s7oB,

We revised our reply above and the PDF on November 13. Edits do not trigger a notification, so we summarize what changed for the points in your review.

Your review states that the paper has no downstream accuracy evaluation, that its memory savings are computed from tensor shapes and not measured, and that it does not show better accuracy than other methods at a fixed compression ratio. The revised PDF now reports on each.

First, Section 4.4 reports answers on 128 ARC-Challenge and OpenBookQA questions. With seven slots per KV head, the exact count in this setting, the compiled cache gives the same answer as the full cache on all 128 questions. With five slots it keeps 124. Keeping the most attended tokens needs 112 slots to keep 124, and SnapKV, H2O and StreamingLLM keep 102, 98 and 106 answers at 112 slots (Figure 4). Second, storage is now measured from the allocated KV tensors. The full cache takes 12,558,336 bytes per question and the compiled cache 172,032, a factor of 73. Third, Section 4.3 compares SnapKV, H2O and StreamingLLM with the lower bound at equal budgets in three models (Figure 2), and Table 3 gives the number of slots each rule needs for a 5% error.

On the third point we claim fidelity and not higher accuracy. The compiled cache reproduces the full-cache accuracy of 48 of 128 by construction. At seven slots, keeping the most attended tokens scores 49 of 128 but changes 33 answers.

One difference in scope remains, and we state it plainly. The paper does not propose an online compressor and claims no throughput gain, because building the cache needs a reference pass. It gives the limit that compressors in the KV format can be measured against, and Algorithm 1 turns that limit into a slot budget for a target error.

With these results in the paper, which of your concerns remain open? We will answer before the discussion closes on November 18.

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

the paper asks how many shared kvs you need to exactly reproduce the attention outputs for a finite set of queries. Each query maps to a ray of feasible values and so if each query can pick its own weights the minimum count is 1 plus the smallest dimension of an affine subspace that meets all the rays (that's thm 4). With grouped query attention and some ok assumptions, the answer is basically: either keep all k original entries or use one slot per protected query (tg of them, for t positions and g query heads per kv head), whichever is smaller. Applied to a whole input this says: if you already know the queries the model will issue over the next T tokens, you can replace the entire prompt cache with Tg fake slots per head and get the same outputs for those T steps. The experiments check that the rank assumptions hold on real models, and that these compiled caches (in FP32) do regenerate the same tokens for traces that were already known. The main point is that exact KV compression has a hard limit: to reproduce attention exactly, you basically need one slot per query.

Critical strengths

The proofs look correct and the hypotheses are stated explicitly. The paper is also honest about scope in places.

Critical weaknesses

Honesty I’m not sure what this paper is exactly for. The math looks right, and I can see it maybe being a useful theory note but I’m struggling to see how anyone working on KV compression changes their mental model for doing anything after reading it. I’ll defer to other reviewers if someone sees a bigger picture but for me it’s a cute result and I’m not sure we really care that much about it? The applied part I didn’t find very convincing. To build the compressed cache you need the queries from a full-cache run so you’re reproducing tokens you already generated.

So overall this feels more like a nice short note or blog post than a full ICLR paper. I don’t see it as a big update for anyone, and I’m not sure it’s a basis for further useful theory either, but I am also not going to call it and curious to hear the rest of the Revs thoughts.

Honestly the version of such a theory I’d actually find interesting is the approximate one, ie what if I let you have some error? Maybe then you can get away with a lot fewer slots and the theory tells us how many. But also again this is a regime where there are a ton of practical methods for so it’s unclear what the theory would point towards beyond what those methods already show empirically?

Questions for authors

Who is this result for, and what should they do differently after reading it?

If you allow some error what happens? And would it say anything beyond what approximate methods show in practice?

I don't want to be nihilistic about "how does theory matter in practice" but given that with new AI models there's an abundance of theoretical work once can do with little effort (cf. openai's proof dump on problems arguably harder than this), one would ask, if the effort required to get this result is near 0 (math wise) what is the value of the question answered by the existence of it? I personally don't know but would love to hear your thoughts on.

That is to say if the only thing limiting us from asking hard theory questions is our ambition (assuming that proofs are near zero effort, when possible), then if you set ambition = infinity, what are impactful theory questions for KV caching that if we had answers for it would vastly update us?

2 comments

Thank you for the candid review and for asking what the result is for.

Who it is for, and what changes. Two groups. First, designers of merging and compaction methods. Under grouped-query attention (GQA) with g≥2g\ge2 query heads per key-value (KV) head, merging two tokens into one slot cannot be exact even for a single decode step whenever the rank condition holds, and it held in all 431,256 configurations we tested. Yet under Theorem 5's conditions a group of kk entries compresses exactly iff k>tgk>tg, so tokens that resist pairwise merging can still be merged jointly: merge groups larger than tgtg, not pairs. Reviewer xu7u independently identifies this as a structural barrier for CaM, KeepKV, AsymKV and KVSlimmer. Second, anyone evaluating a compressor at a budget. A successful fit shows that mm slots work; it cannot show that fewer fail, or how far a method is from the best possible mm-slot cache. Our bounds give that reference independently of any optimizer, in the role Belady's offline MIN policy plays for cache replacement: it also needs the future, and it is the standard yardstick.

Allowing error. Let OO hold the target outputs, PP project out differences of the unchanged complement values vsv_s, and B=(O−1v1⊤)PB=(O-\mathbf 1v_1^\top)P. Every cache replacing the group by mm slots, with any keys and values, satisfies ∥Onew−O∥F ≥ (∑j>mσj(B)2)1/2.\lVert O_{\rm new}-O\rVert_F\ \ge\ \Big(\sum_{j>m}\sigma_j(B)^2\Big)^{1/2}. Among caches that keep each query's prefix mass, the optimum has a closed form. Positive simplex values with shared keys solved from the queries attain it when the query matrix has full row rank, as in every case below.

What it says beyond practice (new experiment). Three models (Qwen2.5-0.5B, Qwen3-4B, Llama-3.2-1B), 64 ARC-Challenge/OpenBookQA prompts each, every layer and KV head, 511-token prefix, next 4 decode steps. Median relative attention-output error at half the exact slot count:

Qwen2.5-0.5BQwen3-4BLlama-3.2-1B
bound, any cache1.31%2.76%2.47%
our construction (queries known)1.42%2.94%2.64%
top-attention + refit values (queries known)7.8%11%9.5%
SnapKV / H2O / StreamingLLM (prefill only)62/61/62%72/62/68%68/62/66%

Four conclusions follow that no fitting run could establish. The best possible error at this budget is pinned down: our construction is within 1.5x of the bound in at least 99.9% of cases. The online rules sit 19 to 40x above it in the median (37 to 113x with 8 protected steps), so their error is not a capacity limit of the slots. And the bound sets budgets: for 5% error, no cache can use fewer than 8/7/6 slots per KV head in the median case, our construction needs 9/7/7, and the two counts are at most one apart in at least 98% of cases (new Algorithm 1, about 25 ms per prompt), while SnapKV and H2O need over 112. Finally, the gap reaches answers: on 128 questions run natively (exact count 7), our 5-slot caches keep 124 full-cache answers; top-attention retention needs 112 slots, and SnapKV keeps 102 there (Figure 4). One limit we state plainly: the bound vanishes once m≥rank⁡Bm\ge\operatorname{rank}B, which never exceeds dvd_v (point (ii) below).

A basis for further theory. You doubted this; the discussion period produced three extensions. (a) The GQA law no longer needs full query rank: when n<kn<k, full ray rank forces the original weights to have rank nn, so keeping nn original keys and solving their values attains nn slots. The refit rule in Figure 2 becomes exact at m=nm=n, as this construction predicts. (b) A lower bound that uses the unchanged complement applies to whole prefixes, where the original test fails structurally; interval arithmetic certifies the minimum Tg=28Tg=28 (real-arithmetic attention) in all 192 layer-head problems tested. (c) A kernel construction removes the Tg≤dkTg\le d_k horizon ceiling, verified at 16 decode steps (n=112>dk=64n=112>d_k=64) on four prompts.

On the value of the question. We agree that a theory result is worth what it changes, not what its proof costs. With unlimited ambition, we would ask: (i) the online analogue of our bound, the least error of any mm-slot cache built before the queries are seen, which must explain the 19 to 40x gap above; (ii) key-side capacity: with free weights, dv+1d_v+1 values serve any finite query set (Theorem 4), so beyond dvd_v slots all difficulty lies in realizing the weights with shared softmax keys, and how many slots n≫dkn\gg d_k queries need is open; (iii) when a per-layer error ε\varepsilon guarantees the same tokens for TT steps. Our exact and approximate results are the finite-query base case for all three.

The revised PDF states this purpose in the introduction, puts the error bounds and Algorithm 1 in Section 3.4, this comparison in Section 4.3 (Figure 2, Table 3), and the protocols in Appendices H.1, H.2 and H.4. We hope this answers who the result is for, and would be grateful if you would reconsider your rating.

Dear Reviewer pKap,

We revised our reply above and the PDF on November 13. Edits do not trigger a notification, so we summarize the change that concerns your review.

You wrote that the version of this theory you would find interesting is the approximate one, where some error is allowed, and you asked whether it would say anything beyond what approximate methods already show. The revised paper contains that version, and it says something those methods cannot.

First, Theorem 6 in Section 3.4 gives a lower bound on the error of every cache with mm slots, whatever its keys and values. A closed-form construction comes within 8% of that bound in the median case at half the exact count. Second, Figure 2 measures three standard methods against the bound in three models. SnapKV, H2O and StreamingLLM sit 19 to 40 times above it. A fitting experiment cannot produce this number, because a fit that reaches some error says nothing about whether a smaller error is possible. Third, Figure 4 shows that the gap reaches the answers. On 128 multiple-choice questions, where seven slots per KV head are exact, five slots keep 124 of the full-cache answers. Keeping the most attended tokens needs 112 slots to do the same.

You also wrote that you would not make the call alone. We would like to hear from you directly. Does the approximate theory in Sections 3.4 and 4.3 change your assessment? If it does not, please tell us what is still missing, and we will answer before the discussion closes on November 18.

Comments on the paper

1 comment

We thank the reviewers for careful and detailed reviews. All four reviews rate soundness as having only minor or fixable concerns, and they ask three questions: what the slot count is for, what happens when some error is allowed, and how the results hold up in practice. The revised PDF answers them with new results and a restructured presentation. All original results are retained and Theorem 5 is strengthened. In the revised PDF, each change is colored by the review it answers (blue pKap, orange s7oB, purple xu7u, green i6VX; a guide sits under the abstract), and OpenReview's comparison view shows every change.

What the paper establishes. A finite set of protected queries determines how many key-value (KV) slots it needs. Each query confines the value of a replacement slot to a ray, and the minimum slot count is one plus the smallest dimension of an affine subspace that meets every ray (Theorem 4). Under grouped-query attention (GQA), preserving tt positions with gg query heads per KV head takes min⁡(k,tg)\min(k,tg) slots for a group of kk tokens (Theorem 5). No pair of tokens therefore merges exactly, while groups larger than tgtg compress exactly. Reviewer xu7u identifies this as a structural barrier for CaM, KeepKV, AsymKV and KVSlimmer.

New in the revision.

  1. Error bounds and budgets below the exact count (Section 3.4). Every mm-slot cache obeys a spectral lower bound on its output error (Theorem 6), and a construction that keeps each query's attention share attains the optimum of its class (Proposition 7). Algorithm 1 turns the pair into a budget rule: for a target error it returns the fewest slots any cache could use and a cache that meets the target. [pKap, s7oB]
  2. The gap between practice and the limit, in three models (Section 4.3, Figure 2, Table 3). On Qwen2.5-0.5B, Qwen3-4B and Llama-3.2-1B, with 64 prompts each, every layer and KV head, and four protected decode steps, the bound and our construction differ by at most 8% in the median case at half the exact count. On the same queries and budget, SnapKV, H2O and StreamingLLM sit 19 to 40 times above the bound in the median case. In slots, a 5% error needs at least 6 to 8 slots per KV head for any cache in the median case, our construction meets it with 7 to 9, within one slot of the bound in at least 98% of cases, and SnapKV and H2O need more than 112. [pKap, s7oB, xu7u]
  3. Fewer assumptions and a matching lower bound (Theorems 5 and 8). The GQA law now needs only its ray-rank condition: keeping nn original keys and solving their values attains it. For entire prefixes, a lower bound from the appended tokens and interval arithmetic certify that Tg=28Tg=28 slots is the minimum on all 192 tested layer-head problems, and TgTg slots suffice without Tg≤dkTg\le d_k. [xu7u, i6VX]
  4. Task fidelity and measured storage (Section 4.4). On 128 ARC-Challenge and OpenBookQA questions, compiled caches with 7 slots per KV head keep every full-cache answer, with 73 times less measured KV storage, while heuristics at the same budget change 33 to 119 answers. Below the exact count the loss is gradual (Figure 4): 5 slots keep 124 answers in native execution, which top-attention retention reaches with 112 slots, and SnapKV, H2O and StreamingLLM keep 98 to 106 answers at 112 slots. [s7oB, pKap]
  5. Standard BF16 execution (Appendix H.7). A variant construction reproduces every protected logit vector bitwise across all 24 layers on four prompts. [xu7u]
  6. Presentation. There are now five sections before the conclusion, a new Figure 1, a notation table and a study overview table, three fewer coined terms, and one place for the scope (Section 5). [i6VX]

Scope. Protected queries come from a full-cache reference, so compiled caches measure what a KV cache of a given size can achieve; they do not replace an online compressor. Per-query output tables store less but leave the KV format, which is the object of every eviction, merging and compaction method and of our counts (Section 5). Code, inputs and recorded checks for every new result are in the supplementary material.

New TL;DR. OpenReview does not allow the TL;DR field to be edited during the discussion phase, so the submission form still shows the original text. The TL;DR we intend is the following.

"We determine how many KV slots a finite query set needs, prove the GQA law min(k, tg), and bound the error of every smaller cache; in three models, SnapKV, H2O and StreamingLLM sit 19 to 40 times above this limit at half the exact budget."

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.