acceptodds
Under review as a conference paper at ICLR 2027

Count Competitors, Not Context: When KV-Cache Budgets Transfer

Abstract

Every KV-cache eviction method must decide how many tokens to keep, and practice sets that budget as a fraction of the prompt. We show that the fraction is the wrong unit. The budget is set by competition: evidence survives eviction exactly when the budget covers the evidence plus the tokens the scorer ranks above it, and prompt length matters only through those competitors. Prior work misses this for two reasons. It evaluates budgets on prompts where length and competing content grow together, so their effects cannot be separated, and it treats keeping the evidence as enough to answer. Separating length from competition exposes costly errors in both directions: on long prompts with little competing content, a fixed fraction keeps about 100 times more cache than needed, while at a fixed length, added distractors raise the required budget more than 200-fold. Counts frozen before verification forecast budgets within a factor of two at up to 512K tokens, where a constant fraction fails. Keeping the evidence is also not enough: answers depend on keeping the rows that bind the evidence to the question. Compacting the cache to these budgets cuts KV memory by up to two orders of magnitude with no loss of accuracy on the tested requests. The rule for sizing a cache is simple: count competitors, not context.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
KV cache compression, KV cache eviction, long-context inference, efficient LLM inference, memory budget, token retention, evaluation methodology

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_S9ihOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies when a KV-cache retention budget set for a short context can be reused for longer contexts. With a fixed ranking, the minimum budget for retaining an entire evidence set equals the number of evidence positions plus the number of competitors. Competitors are non-evidence positions ranked ahead of the lowest-ranked evidence position. In controlled retrieval experiments, adding filler text had little effect on the budget. Adding distractors at a fixed context length substantially increased the required budget. The authors used short-context experiments to predict budgets for longer contexts. In 22 of 25 testable settings, the predictions were within a factor of two of the measured budgets.

In the eight-value retrieval experiment, the model retained all annotated values but answered only 9 of 20 prompts correctly. At the same budget, retaining the full key–value records and the question raised the number of correct answers to 20 out of 20. This result suggests that correct answers also depend on linking the values to their keys and the question.

Critical strengths
  1. The controlled experiments separate the effects of distractor count and context length. At 32K length, distractors raise Qwen3.5-9B’s retention budget from about 24 to 5,277 positions, while added filler has little effect.

  2. The evaluation links evidence retention, answer accuracy, and physical cache savings. Even with all annotated values retained, only 9/20 ordered answers are correct (Section 5.4). Dense and hybrid models achieve approximately 97–102× and 11× storage reductions while matching full-cache answer accuracy on tested prompts.

Critical weaknesses
  1. The budgeting guidance has limited validation beyond controlled retrieval with 15–20 paired prompts per condition. Rank audits require a specified evidence proxy, leaving unclear how budget reuse can be assessed in natural tasks where evidence is difficult to annotate.

  2. The LongBench analysis applies the same 0.8 validity threshold to retrieval accuracy and token F1 without sufficient justification. All three cohorts fall below this threshold, with full-cache F1 scores of 0.298–0.335, so no budget-crossing estimates are reported. This limits the evidence about budget requirements for natural QA.

Questions for authors
  1. For natural tasks without directly annotatable evidence, which of the described calibration or audit steps remain applicable, and what conditions for budget reuse can they test?

  2. Can the authors justify applying the 0.8 threshold to both retrieval accuracy and LongBench token F1, and use the existing curves to assess how the threshold affects budget estimation?

3 comments

Thank you for the detailed response. E1 provides useful initial evidence. However, it covers only two datasets, with 34 and 23 context-dependent examples for Qwen and Llama, respectively. The post-hoc filtering also makes the results less conclusive. I therefore consider my first concern only partially addressed.

The additional analyses at 50%, 80%, and 90% of full-cache F1 adequately address my second concern. However, the limited natural-task validation remains a concern, so I will maintain my original rating.

AuthorsOpenReview ↗

Response to your last concern

Thank you for engaging with the response, and for confirming that the 50/80/90% analyses address the threshold question. You raise three remaining points about E1: the post-hoc filter, the sample sizes, and the two datasets. We take them in turn. The first answer also corrects an imprecise statement in our earlier post.

1. The result does not depend on the post-hoc filter. In our earlier post we wrote that the registered analysis set was "censored at the lowest rung." That is accurate only for Qwen on 2WikiMQA, where SnapKV already reaches half of full accuracy at 32 retained positions in every condition. The other three registered sets have well-defined crossings. The registered set is specified in the frozen design: every example the full cache answers correctly at the shortest length, with no closed-book filter, so no selection was made after seeing results.

Registered set, SnapKV-w32nLength changeN50N_{50} (positions)Ratio [95% CI]A fraction predicts
Llama-3.1-8B, 2WikiMQA278K → 32K42 → 421.00 [0.85, 1.18]4.0
Llama-3.1-8B, HotpotQA2816K → 32K44 → 440.99 [0.87, 1.13]2.0
Qwen3.5-9B, HotpotQA3216K → 32K32 → 331.03 [0.99, 1.17]2.0

These are the pre-registered estimates. Each interval sits near 1 and far from the fraction prediction, including a 4× length change on 2WikiMQA. The same sets also answer the competitor question: adding 48 Wikipedia passages gives 0.96 [0.77, 1.17], 1.00 [0.91, 1.12], and 0.97 [0.90, 1.06]. The post-hoc filter was never needed to obtain the result. It only made the Qwen 2WikiMQA cell measurable, and it gives the same answer there.

The same pattern holds with no selection of any kind: all 108 candidate examples per model, scored by token F1. On Llama, the SnapKV half-F1 budget is 46, 47, and 47 positions at 8K, 16K, and 32K on 2WikiMQA, and 45 → 48 on HotpotQA (16K → 32K). This secondary analysis has no bootstrap intervals, so we report it only as a consistency check.

2. The sample sizes are sufficient for the question being tested. The test is whether the budget scales with length, as a fraction does, or stays flat, as a count does. That is a contrast between a ratio of 1 and a ratio of 2–4, and the contrast is far larger than the uncertainty at these sample sizes. Every interval above excludes the fraction prediction. Even the upper bounds (1.13–1.18) are at least 1.7× below what a fraction predicts. The examples are also paired: each prompt is measured at every length, so prompt difficulty cancels out of the ratio. A larger n would narrow the intervals but could not move them from about 1 to 2–4. Across both models and both tasks, the registered sets contain 122 examples.

3. On the number of natural datasets. We agree that two LongBench tasks are a starting point, not the full range of natural workloads. Three other natural-format results bear on the same question:

  • InfiniteBench passkey and 10-digit retrieval show count transfer, with NLL crossings of 23–104 positions on four models: Qwen3.5-9B, Qwen3.5-4B, Qwen2.5-7B-1M, and Phi-4.
  • Single-span audits, frozen before the runs on five unseen InfiniteBench cells, never under-provisioned in 20 of 20 scorer–cell pairs (App. G).
  • RULER, BABILong, and LongBench (Sec. 5.5) are where the paper predicts that a literal-retrieval count should not transfer, and it does not. That is the boundary the protocol is meant to detect.

For the revision, we will extend E1 to MuSiQue, the third LongBench multi-hop task, under the same frozen protocol. We will also state in the abstract that the natural-task validation covers multi-document QA on two model families.

Summary. Your remaining concern was that the natural-task evidence rests on a post-hoc filter and small samples. The pre-registered sets, with no filter, give the same conclusion, with tighter intervals than the filtered analysis in all three cells that are not censored. They exclude the fraction prediction in every case and cover 122 paired examples. We hope this resolves the first concern as well. If it does, we would be grateful if you would consider updating your rating.

AuthorsOpenReview ↗

MuSiQue result, and a test with no example selection

In our previous reply we committed to extending the natural-task test to MuSiQue, the third LongBench multi-hop task. That run is complete, and we report it here together with a second test that answers your sample-size point directly. Both designs, their predictions, and their inputs were hashed before the first eviction run (frozen 2026-11-17 19:28 UTC). The revised PDF now includes both.

1. MuSiQue under the same protocol (all three registered predictions held). We used all 100 LongBench MuSiQue examples on Qwen3.5-9B and Llama-3.1-8B. Only 11 originals fit in 16K, so the filler test runs from 32K to 64K, and 48 Wikipedia competitor passages are inserted at 64K. The analysis set is the registered one, with no post-hoc filter: every example the full cache answers at 32K.

SnapKV-w32, registered setnFiller 32K → 64K, N50N_{50} ratio [95% CI]+48 passages at 64K, ratio [95% CI]90% count fixed at 32K: share of full at 64K
Qwen3.5-9B361.09 [0.93, 1.23] (32 → 35)0.92 [0.81, 1.11]1.00
Llama-3.1-8B270.98 [0.74, 1.45] (57 → 56)1.03 [0.73, 1.41]0.94
  • The count transfers on a third dataset. Doubling the length leaves the budget flat in both models, and both intervals exclude the 2.0 a fraction predicts. MuSiQue therefore behaves like 2WikiMQA and HotpotQA.
  • The direct reuse test passes. The count chosen at 32K, applied unchanged at 64K, kept at least its target minus 0.10 in all 12 registered cells (two scorers, two models, targets of 50%, 80%, and 90%).
  • Same-topic competitors again do not raise the budget, which replicates the E1 finding on new data.
  • Two caveats, stated plainly. TOVA reaches half accuracy at the lowest tested budget in every condition, so its ratio carries no information. Llama's own full-cache accuracy also drops at 64K (from 1.00 to 0.67 on this set), so every share is relative to the full cache at the same length.

2. A test with no example selection at all (your sample-size point). We ran all 100 2WikiMQA and all 100 HotpotQA examples at their natural length, with nothing inserted and nothing filtered. For each model and task, we calibrated the count on the shortest third of examples (median 4.3K–10.0K tokens) and applied it unchanged to the longest third (median 10.6K–17.0K). This tests the claim on different, naturally longer examples, not on padded copies of the same ones.

  • Registered prediction 1 held in 16 of 16 cells. At the 90% target, the count kept 0.93–1.00 of full-cache accuracy for SnapKV and 0.80–1.00 for TOVA. SnapKV's 90% budget did not grow with length: 169 → 91, 111 → 51, 676 → 104, and 62 → 62 positions.
  • Registered prediction 2 failed in 9 of 16 cells, and we report it. A fraction calibrated the same way used 1.3–13.7× more positions. In 9 of 16 cells, that extra memory raised accuracy by more than 0.05 above a target the count already met.

What this means for your three points.

  • Post-hoc filter: every number above uses registered sets, or no selection at all.
  • Sample size: the natural-text evidence now covers 3 tasks, 2 model families, and 63 more registered MuSiQue examples, plus 400 unselected natural-length examples (100 per model and task).
  • Two datasets: there are now three, and the result holds on all three.

The abstract now states this scope: count transfer on natural multi-hop QA, measured on three LongBench tasks and two model families.

We hope this closes the remaining questions. If it does, we would be grateful if you would reconsider your rating.

Reviewer_2XSPOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

This paper argues that KV-cache budgets should be determined by the number of tokens competing with task-relevant evidence, rather than by a fixed fraction of context length. For a fixed ranking-based selector, the required budget is characterized as the evidence size plus the number of non-evidence tokens ranked ahead of the weakest evidence token. Controlled experiments show that adding filler leaves the required budget nearly unchanged, while adding distractors at fixed length can increase it by over 200×. The paper also shows that retaining answer tokens is not sufficient for correct generation because key–value and query relationships may be lost. Physical cache compaction reduces measured KV storage by 11–102× on two models.

Critical strengths
  1. The paper addresses how to choose the total KV-cache budget, a question often overlooked by methods focusing only on token selection.
  2. Separating filler from distractors provides convincing evidence that competition, rather than length alone, determines the required budget.
  3. The paper clearly demonstrates that preserving answer tokens does not guarantee that the model can use them correctly.
  4. The authors report invalid cells, failed forecasts, non-monotone curves, and actual physical cache bytes rather than only logical compression ratios.
Critical weaknesses
  1. Computing (C) requires knowing the true evidence set, which is usually unavailable in natural QA or reasoning. Evaluating observable competitor proxies using evidence-annotated or realistic long-context datasets will enhance this paper.
  2. Many key results use only 15–20 artificial retrieval examples. Adding larger experiments on realistic QA, code, multi-document, and multi-hop workloads will be better.
  3. The reported memory reductions occur after full prefill and do not reduce peak prefill memory or demonstrate meaningful latency gains.
  4. Reaching 50% of full-cache accuracy does not demonstrate quality preservation, especially when curves are non-monotone.
Questions for authors

Please refer weaknesses.

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

For KV-cache eviction methods, the paper argues that using a fraction of the prompt or context length as the retention budget, as done in some prior work, is wrong. Instead, it argues that the budget should depend on the number of competitors. The paper defines competitors as non-evidence tokens ranked above the weakest-ranked evidence token by the selector. Its synthetic benchmarks vary context length and distractor counts separately to test how the required retention budget changes. It evaluates an NLL selector, which uses token surprisal, and UnionKV, its proposed allocator combining content and attention selection, among other methods.

The paper defines N50N_{50} as the first budget reaching half the full-cache accuracy, estimated by interpolation. On synthetic literal retrieval with Qwen3.5-9B, it reports that N50N_{50} stays around 24–28 retained positions from 16K to 256K context length. At a fixed 32K length, adding 512 distractor statements raises N50N_{50} approximately 220-fold.

The paper also studies cases where the answer is incorrect despite all answer tokens being retained, and measures physical memory savings after cache compaction.

Critical strengths

The controlled synthetic experiments clearly separate the effects of context length and distractor content, as demonstrated in Section 5.1. They provide evidence that using a fixed fraction of context length as the retention budget may be suboptimal in these controlled settings.

Critical weaknesses
  1. The contribution and practical significance are unclear. The main positive results rely on a simple synthetic task whose repetitive filler and random-digit distractors strongly favor the expected behavior of NLL selection. Meanwhile, NLL and UnionKV-v2 perform substantially worse than attention-based baselines on the structured tasks reported in Section 5.5 and Section 6. Furthermore, the paper does not demonstrate how “count competitors, not context” can predict useful budgets in realistic settings where the required evidence is unknown.

  2. The presentation makes the paper unnecessarily difficult to understand. Essential method details, metric definitions, and supporting tables and figures are heavily deferred to appendices. UnionKV, a method proposed in this paper, is evaluated in Section 5 before its explanation, which is deferred to Section 6 and mainly to Appendix I. Sections 2–3 introduce substantial mathematical notation and several bounds, but they provide little help in the later analysis. I cannot understand the main idea this paper aims to convey without extensively reading the appendices.

Questions for authors

Clarification of contribution. Is the headline “count competitors, not context” intended as a practical budgeting rule for scenarios where the required evidence is unknown, beyond the controlled trivial synthetic setting? Given that the controlled synthetic experiments appear to demonstrate expected behaviour of the methods, what do the authors regard as the main contribution?

Comments on the paper

2 comments
AuthorsOpenReview ↗

Revised submission based on feedback

3. Section 5.5 (contradiction point 1). We agree, and the revised PDF makes this change. The structured-task section (now Sec. 5.6) states that literal-retrieval budgets and scorer rankings do not transfer to these tasks. It also says that we do not measure ∣S∣|S| or CC there, so we do not attribute the change to either term; the proposed retitling is dropped. The paper's claim that the rule tells you when to re-measure rests on the filler and competitor tests, not on that section.

4. High-quality budgets, as counts and fractions (done). N90N_{90} on fresh seeds (n = 60): length 16K→256K, count 32→30 (×0.96), fraction ×0.06; filler 8K→64K, count 494→492 (×1.00), fraction ×0.12. Full-quality budget: 48→32 positions where 1% keeps 164→2,621. On LongBench filler, SnapKV's N90N_{90} count moves ×0.48–1.46 while its fraction falls to ×0.12–0.73. The revision makes N90N_{90} and full-quality budgets primary, for every cell.

5. Naturally shorter → naturally longer examples (new, pre-registered, hashed before any run). All 100 LongBench 2WikiMQA and 100 HotpotQA examples at their natural length, nothing inserted, on Qwen3.5-9B and Llama-3.1-8B. We calibrated on the shortest third (median 4.3K–10.0K tokens) and applied the result unchanged to the longest third (10.6K–17.0K).

  • Registered prediction 1 (held in 16 of 16 cells). The count reaching 80% or 90% of full accuracy on short examples keeps at least that target minus 0.10 on long ones. At the 90% target it kept 0.93–1.00 for SnapKV and 0.80–1.00 for TOVA (0.80 is the only cell exactly at the margin).
  • The count does not grow with natural length. SnapKV's N90N_{90}, short third → long third, is 169→91, 111→51, 676→104 and 62→62.
  • Registered prediction 2 (failed in 9 of 16 cells). We predicted that a fraction calibrated the same way would spend more positions and gain at most 0.05 in share. It did spend 1.3–13.7× more positions on the long third, but in 9 of 16 cells it gained more than 0.05 (up to 0.20). The extra memory buys extra accuracy above the target; the count meets the target with less.

6. Main-text evidence (done). Sec. 5.4 of the revised PDF has a single replication table covering fresh seeds (n = 60), LongBench filler and competitors, MuSiQue, and the natural-length test. It reports N90N_{90} as a count and as a fraction for every row, plus the direct-reuse accuracy, so the breadth of the evidence is visible without the appendix.

Summary. Your follow-up asks four things. The first is whether a short-context budget delivers its accuracy at long context; it does, in every case where the protocol says to reuse it. The second is whether the identity explains the measured budget change; under distractors it accounts for it to within 0.05–2.66 positions per statement. On Sec. 5.5 we agree, and the revised PDF makes the change. The high-quality budgets and the natural-length test are now reported above, including the registered prediction that failed. We hope this resolves the remaining soundness and significance questions. If it does, we would be grateful if you would reconsider your overall score.

AuthorsOpenReview ↗

TL;DR: what the discussion established

We thank all three reviewers and the AC. The exchange made the paper's claims sharper and its evidence much broader. Here is the outcome in one place.

The claim. Choose a KV-cache budget as a count of retained positions, calibrated once per scorer and model. Do not choose it as a fraction of the prompt. Reuse the count at a new length if a filler test and a competitor test pass. This works because the budget is set by the tokens that outrank the evidence, not by prompt length.

What the reviewers asked for, and what is now in the revised PDF.

RequestDeliveredResult
Natural text, not only synthetic retrieval (all reviewers)3 LongBench multi-hop tasks (2WikiMQA, HotpotQA, MuSiQue), 2 model familiesAs length grows 2–4×, the registered half-accuracy count changes only 0.98–1.09×; a fraction predicts 2–4×
Does a short-context budget actually work at long context? (boD3)Direct reuse test, no re-tuningA SnapKV count reused at longer length keeps 0.90–1.00 of full-cache accuracy at the 90% target
Naturally longer examples, not padding (boD3)400 unselected natural-length examples (100 per model and task)Count calibrated on the shortest third meets its target on the longest third in 16 of 16 registered cells
High-quality budgets, not N50N_{50} (boD3)N90N_{90} and full-quality budgets, as counts and as fractionsAt 256K the count needs 32 positions for full quality; a 1% budget keeps 2,621
Larger samples (2XSP, S9ih)60 fresh seeds per headline cellAll three effects reproduce; the distractor effect is 223× [192, 265]
Does CC explain anything beyond calibration? (2XSP, boD3)Token-level distractor analysisTokenization predicts 10–18 positions per distractor; measured 10.05–12.66
Structured tasks (boD3)Count-first selector with a ChunkKV fill0.97 on both literal and key–value retrieval, where each earlier selector failed one
Scope and presentation (boD3, 2XSP)Main-text replication table, scoped abstract, Sec. 5.6 attribution removed, boundary cells marked—

How the evidence was produced. Five new experiments, about 58,000 generations with 0 failed rows. Each design and its predictions were hashed before the first eviction run. The first round's numbers were recomputed independently from the raw outputs. Two registered predictions did not hold, and both are reported in the paper:

  • Same-topic Wikipedia passages do not raise the budget, because attention does not rank them above the evidence.
  • A fraction rule buys extra accuracy above the target by spending 1.3–13.7× more memory.

The tests could have failed. Some did, and we report it.

Bottom line. Across 14 models at calibration, length sweeps up to 512K, 3 distractor families, 3 natural multi-hop tasks, and naturally longer inputs, the same rule holds:

Count competitors, not context. Calibrate a count, reuse it where the filler and competitor tests pass, and it meets its accuracy target with up to 80× less cache than a 1% fraction.

We are grateful for the reviewers' engagement and hope the revised paper reflects it.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.