- 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
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 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 . 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.
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,∞) and (−∞,2/3); they do not meet, so one slot is impossible, while two slots suffice. Under grouped-query attention (GQA) every decode step brings g such queries to each KV head, which is why, under a rank condition, the exact count is min(k,tg) for a group of k tokens and t 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.
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 tg 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.