acceptodds
Under review as a conference paper at ICLR 2027

Whether a KV Cache Can Be Evicted Blind Is a Property of Its Queries

Abstract

Two summary statistics of an attention head's queries, their average direction and how tightly they cluster around it, predict whether the head's KV cache can be evicted blind, that is, cut to one set of kept tokens chosen before any query arrives, for queries that continue the document. For questions appended after the document, the model family decides: under a decision rule recorded before the analysis, the prediction holds on Olmo-3 and fails on Llama, Qwen2.5 and Qwen3.5. Blind eviction works on a head only when its queries agree on which cached tokens matter, and the two statistics rank heads by that agreement, with nothing fitted, at a Spearman correlation of at least +0.89 on held-out queries in open-weight models from three families. A serving system can therefore tell before decoding which heads it can evict blind on continuation-style workloads. Measured exactly, this agreement is low and varies widely between heads of one model. A scoring rule built from the average direction adds less output error, over the best set each query could have kept, than every recent method we compare, as released, on held-out continuation queries, and on the LongBench benchmark, whose questions are appended, it is level with Expected Attention within its interval. The measurements also explain why RoCo's division of accumulated attention by the number of positions that could see each token, which kvpress already applies, cuts that excess error for H2O by 45%. They show that a guarantee met on the queries that chose the kept set breaks on many unseen ones, and they yield five practical implications for eviction. Code: https://anonymous.4open.science/r/kv-incompressibility-A706/

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
KV cache, cache eviction, attention heads, long context, inference efficiency, query distribution, transformers

Reviews

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

This paper investigates the problem of KV-cache eviction that blind KV eviction picks which tokens to keep before the questions arrive. The paper measures and try to understand when this can work well. The paper find out that the answer depends on how much a head’s future queries agree on which tokens matter, and it is possible to estimate this agreement per head from two simple statistics of its queries. Based on this finding, the paper proposes a simple scoring rule that does well on queries from inside the document.

Critical strengths

1, The main result in Table 1 shows that the prediction on which heads agree works well with nothing fitted. It suggests these numbers really capture what drives agreement.

  1. This paper defines a clear quantity that measures the agreement between a head’s queries and proves that it limits how well any blind eviction method can do on that head.
Critical weaknesses

1, The evidence that supports the method proposed this method is not strong enough. The method was only tested on the Llama models and the error comparison uses one small model and one document. That raises concerns about the generalizability of the method. In addition, it looks like this method only work for queries inside the document, and it does not work well for queries after the document.

2, Unclear about the contribution of this paper. The proposed method seems to be a combination of Roco, Expected Attention, and CAOTE as mentioned in the paper. And judging from Table 12 this proposed method does not work so well on practical tasks in longbench. Then the main contribution of this paper might be only the measurement and analysis of the KV eviction and predictions.

Questions for authors

1, What is the performance of the proposed method on Qwen models?

2, What is the key novelty of the proposed method? And what is its main advantages over the existing baselines if the performances does not differ too much?

4 comments
AuthorsOpenReview ↗

Response to Reviewer VrnX

Thank you for the review. The two strengths you list, a prediction with nothing fitted and a bound on every blind method, are the paper's core. The revision calls the proposed method MQE (Mean-Query Eviction). In the tables, EA is Expected Attention and QF is Q-Filters.

W1.

1, The evidence that supports the method proposed this method is not strong enough. The method was only tested on the Llama models and the error comparison uses one small model and one document. That raises concerns about the generalizability of the method. In addition, it looks like this method only work for queries inside the document, and it does not work well for queries after the document.

MQE now runs on Qwen models, in the error comparison and on RULER.

Error comparison: median regret, share kept0.10.250.5
Qwen2.5-1.5B, MQE0.00790.00510.0019
Qwen2.5-1.5B, EA0.00820.00560.0021
Qwen3.5-9B-Base, MQE0.01650.00900.0028
Qwen3.5-9B-Base, EA0.01480.00770.0025

MQE is lower by a paired interval at all three budgets on Qwen2.5-1.5B, and Expected Attention at all three on Qwen3.5-9B-Base. On both, MQE's regret is 22 to 53% below that of H2O as released (Table 16).

RULER, Qwen2.5-7B-Instruct, a quarter kept4k8k
MQE minus EA (points)+0.4 [-2.1, +2.9], level+2.2 [-0.1, +4.5], level
MQE minus QF+4.1 [+1.6, +6.7], ahead+3.0 [+0.8, +5.2], ahead
KeyDiff and KVzipahead of all threeahead of all three

They lead in every RULER setting (Table 14).

Prefill statistics do not carry over to queries appended after the document. This is one of the paper's findings, and Section 5.1 now leads with it.

W2.

2, Unclear about the contribution of this paper. The proposed method seems to be a combination of Roco, Expected Attention, and CAOTE as mentioned in the paper. And judging from Table 12 this proposed method does not work so well on practical tasks in longbench. Then the main contribution of this paper might be only the measurement and analysis of the KV eviction and predictions.

The novelty is a bound that every blind eviction policy obeys, measured exactly for every head of six models.

The agreement that sets it varies more than tenfold between heads. RoCo, Expected Attention and CAOTE are eviction scores, and none asks on which heads a score fixed before the queries can work at all. Lemma 1 and the per-head measurement answer that, and your review lists both as strengths.

MQE uses the first moment of the query model alone. It places one query along the head's mean direction, at its median norm, and ranks tokens by the exact cost of evicting each. Each piece has a precedent, and we credit it:

  • the visibility division is RoCo's
  • the exact cost coincides with CAOTE's for one token
  • scoring with a model of future queries is Expected Attention's idea.

Combined, they match or beat their sources as released where we can measure them, with every baseline from released code (Section 6.1):

ResultValue
Regret below H2O with RoCo's division, Llama-3.2-1B, three budgets25 to 39%
Against EA as released, Llama-3.2-1Bahead at a quarter and half, level at a tenth
Random direction instead of the mean, same norm, Llama-3.2-1Bregret ×\times 2.2 to 5.3
Same control, six models, three segments, three budgetsregret ×\times 2.4 to 26.2
Median regret below H2O as released, all 18 cells22 to 85%

On LongBench (your Table 12, now Table 15), the submitted run was level with Expected Attention at a quarter of the cache and behind it at half. It applied the chat template to every subset. We reran it with the official prompts and metrics and three times the samples, and added RULER from NVIDIA's code. On LongBench MQE is ahead of Q-Filters by +5.9 points [+4.1, +7.8] and behind Expected Attention by -2.9 [-4.4, -1.3]. On RULER it is ahead of Q-Filters in 7 of 10 settings. KeyDiff and KVzip, which do not model the queries, lead in all ten, the boundary the paper measures on appended questions (Section 6.2).

Q1.

1, What is the performance of the proposed method on Qwen models?

Answered with W1 above.

Q2.

2, What is the key novelty of the proposed method? And what is its main advantages over the existing baselines if the performances does not differ too much?

Answered with W2 above.

We hope the revision resolves your concerns, and we would appreciate it if you took it into account in your final score. We are happy to discuss any point further.

AuthorsOpenReview ↗

Follow-up for Reviewer VrnX

We extended the experiments to the Qwen family, in both the error comparison and RULER. On both Qwen models, our method's regret is 2222 to 53%53\%% below H2O as released (Table 16). The method is now tested beyond Llama, on several models and documents. We would be glad to hear whether this resolves your concern, and if so, we would be grateful if you would consider revising your rating.

Thank you for the detailed response and the additional experiments, which address my concern about evaluation across model families. However, several concerns remain unaddressed.

  1. Novelty of MQE: The rebuttal confirms that each component of MQE has a precedent (RoCo, CAOTE, and Expected Attention) and places the novelty in Lemma 1 and the per-head measurement instead. So it looks like it confirms my previous analysis in W2 that the main contribution of the paper lies within the analysis of KV eviction and predictions.

The authors argue that “The novelty is a bound every blind method obeys.” It is a true statement and the math is correct, but it follows in a few lines from a known fact (Jaccard distance obeys the triangle inequality). The paper itself also calls this a “loose boundary". It also limits how much a kept set overlaps each query’s ideal set, not how much quality is lost.

  1. Advantage over existing methods: My question about MQE’s main advantage was not answered. The rebuttal states that MQE matches or beats its sources but does not identify a practical advantage, such as lower cost or memory. The improvement over H2O does not distinguish MQE, since existing methods show similar or larger gains over H2O

Overall, I appreciate the analysis, but the contribution and advantage of MQE as a method remains unclear. The technical contribution of this work is a bit too limited for me to consider improving the score. I am more inclined to maintain the current evaluation score for the reasons above.

AuthorsOpenReview ↗

Response to Reviewer VrnX

Thank you for the follow-up. On MQE's practical advantage: it needs one direction per head, the same information as Q-Filters. With it, MQE is ahead of Q-Filters on LongBench and in most RULER settings, and lower or level with Expected Attention as released in most continuation cells. We agree with your reading that the paper's main contribution is the analysis, and the revision is framed that way. MQE's role is to show that the query geometry the analysis identifies yields a competitive policy.

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

The premise is query-free ("blind") KV-cache eviction: where one kept set must be fixed before the queries it serves arrive.

  • Measurement. For each unit, the authors compute the exact leave-one-out change in the head's output from evicting each token (Eq. 1, p.3). Each query's top-B tokens form its retention set. Cross-query agreement is the median pairwise Jaccard overlap of these sets, averaged over B ∈ {32, 64, 128}.
  • Bound. Lemma 1, an elementary triangle-inequality argument, bounds the mean overlap of any fixed set with the queries' retention sets by (1+J̄)/2.
  • Query model. Unit query directions are drawn as √c̄·µ + √(1−c̄)·e, with e isotropic in µ⊥. The model simulates 330 query events against the head's own keys and values and correlates simulated with measured agreement across units.
  • Setup. Experiments use post-RoPE captures of one 8192-token document on six models: Llama-3.2-1B and 3B, Qwen2.5-1.5B, Olmo-3-7B and 32B, and Qwen3.5-9B-Base. A 64-token sink and a 256-token recency band are always kept. The queries that estimate the moments are content-separated from those that measure agreement.
  • Statistics. Intervals are cluster bootstraps by layer, and correlations are read against measured reliability ceilings. Nearly every analysis is pre-registered in the repository, with amendments recorded.

Section 4 reports the headline correlations, which reach 0.91–0.97 of the ceiling, plus controls (Table 8, p.19):

  • random µ: +0.58 / +0.46;
  • dispersion-matched µ: +0.82 / +0.78;
  • isotropic query: +0.11 / +0.37;
  • gradient boosting on head-level scalars: +0.74 / +0.58.

The moments also transfer across documents on Llama-3.2-1B (median +0.932). The model overpredicts the level of agreement by 1.6–2.3×, which App. J traces to anisotropy in the residual directions.

Section 4.1 appends 48 template questions to the same document. Moments measured on the questions predict agreement among questions (+0.940 to +0.979), but prefill moments do not, except on Olmo-3. On Llama-3.2-1B, median c̄ moves from 0.720 to 0.955 between the two regimes.

Section 5 covers four things:

  • held-out violation of droppability guarantees, repaired by a uniform 1.25–4× budget inflation;
  • per-head regret on Llama-3.2-1B against four ported 2023–24 policies and five kvpress 2025–26 policies;
  • an account of why RoCo's division by visibility count helps;
  • a pre-registered LongBench check (7 English subsets × 50 samples).

Section 6 lists five practical implications. Two more registered negatives appear only in the appendices:

  • Allocating budget by predicted, or even measured, agreement does not beat uniform allocation (App. K).
  • Per-head inflation factors from predicted agreement free no more cache than a uniform factor (App. Q).
Critical strengths

The empirical practice is well above the norm in this area:

  • Exact measures and real controls. Agreement uses exact leave-one-out costs, not attention proxies. Correlations are read against measured reliability ceilings and information-free controls (Table 8, App. I).
  • Correct inference. Heads within a layer are treated as dependent, and intervals are bootstrapped by layer.
  • Traceable and anonymous release. The repository is cleanly anonymised. A spot check of 34 numbers across Tables 1, 2, 4–6, 10 and 12 traced each one through generated macros to a result file, with no mismatch.

The findings that survive are strong:

  • Agreement varies widely by head. Within one model it differs more than tenfold between heads (Fig. 2, p.6).
  • On continuation queries the ranking is predictable. It follows from query geometry plus the head's own keys, with no fitted parameters and across documents (+0.932, p.5).
  • The regime split is a real caution. Prefill-derived query statistics don't describe appended questions on most families tested. On Llama-3.2-1B, c̄ is 0.720 vs 0.955, and its cross-regime rank correlation is +0.178 (pp.6–7). This bears on any method that estimates future queries from prefill.
  • Guarantees need held-out checking. In-sample droppability guarantees break on 8.9–26.1% of unseen queries (Table 1; Tables 5–6). This is a lesson other evaluations can adopt.
Critical weaknesses

The predictor has no demonstrated operational value, and it fails precisely where it is needed. The abstract claims that “a serving system can therefore tell before decoding which heads it can evict blind.” The authors’ own results show that a system does better without the model.

\hline \text{Model} & \text{Direct measurement} & \text{Two-moment model} \\\\ \hline \text{Llama-3.2-1B} & 0.965 & 0.942 \\\\ \text{Llama-3.2-3B} & 0.970 & 0.938 \\\\ \text{Qwen2.5-1.5B} & 0.954 & 0.900 \\\\ \text{Olmo-3-32B} & 0.987 & 0.960 \\\\ \text{Olmo-3-7B} & 0.972 & 0.895 \\\\ \text{Qwen3.5-9B-Base} & 0.946 & 0.898 \\\\ \hline \end{array}$$ These numbers are taken directly from the authors’ supplementary repository (rel_meas_query_half in results/r22_ceiling.json and results_r33/r22_ceiling.json). They report the unadjusted Spearman correlation of agreement measured on 16 real prefill queries against 17 disjoint ones. Direct measurement also requires fewer exact cost evaluations than the model’s 330 simulated events. Registered downstream uses likewise fail. Budget allocation by predicted (or even measured) agreement does not beat uniform allocation (App. K, Table 9). Per-head safety factors free essentially no more cache than a uniform factor: 0.264 vs 0.261 dropped, with paired per-unit median +0.0000; the registered primary endpoint is not met (App. Q). The main text never summarizes the allocation result, even though App. K, App. Q and Table 3 all point to Section 5 for it. Appended questions break transfer: for RAG, QA and LongBench, prefill moments fail on 5 of 7 configurations. The claim that “the model family decides” rests on two Olmo-3 checkpoints against five others, a single document, and 48 questions in one template. Agreement among those questions also lies close to its marginals-preserving null (0.497 vs 0.437; App. L, p. 20). This is far too thin to separate “family” from a specific architectural or training property. Evaluation scope, proxy validity and positioningThe protocol is narrow and partly misdescribed. - Apart from LongBench, every result rests on one 8192-token document per model. - The code scores eviction only on one fixed early span, tokens [64, 2944) (mid = arange(NSINK, min_qpos − NREC)). This span is shared by all queries at positions ≥ 3200; it is not each query’s visible cache, contrary to the reading of Section 3 (p. 4). - The headline split uses a dense 72-position grid, not the 33-query rule of Section 3. - Table 2’s “1040 of 2880 mid-cache tokens” is in fact 720 selected mid-cache tokens plus the 320 sink and recency tokens. - The simulation runs on the evaluation half’s own positions, keys and values, so the claim that the two halves “share nothing” (Fig. 1 caption) holds only for the query vectors. The policy comparison is correspondingly thin: one model, one document, one budget. Outputs are per-head on frozen captures with no propagation across layers. The margin over Expected Attention is only 0.00035 in absolute regret. The proxy itself is not supported by the task results. At a quarter of the cache, KVzip and KeyDiff incur 2–3× the score’s Table 2 regret, yet they are the strongest compressed arms on LongBench. The score sits below the released H2O and above only SnapKV; the claimed 45 % normalization gain disappears. The LongBench run is underpowered and noisy (50 samples per subset, ±3-point intervals) and yields full-cache scores of only 16.0 on TREC and 24.5 on LCC. Those low scores coincide with the disclosed chat-templating of every subset and a brittle classification metric; KeyDiff even exceeds the full-cache baseline. Under the paper’s post-prefill protocol the “ceiling” is a usable baseline: exact ordering from held-out real queries averages exact costs over 33 interior prefill positions of the same document (App. O, p. 23). A method that runs at prefill time can use those positions. It beats the score (0.0061 vs 0.0066), so the claim that the score “closes 95 % of the distance” to the ceiling is generous. Novelty and positioningThe score is close to Q-Filters (Godey et al., 2025): a per-head principal query direction, calibrated offline and shipped in kvpress. The paper does not cite it. The score adds CAOTE’s leave-one-out cost (which is cited). Expected Attention is described as first-moment only (p. 3, Table 3), yet its released form (ported by the authors with use_covariance=True) includes a $k^\top\Sigma k$ second-moment term. The claim that $\sigma_t$ is what “no first-moment score observes” therefore needs to be stated more precisely. The visibility division is RoCo’s and is already present in kvpress; Lemma 1 is elementary.
Questions for authors
  1. Is there any downstream setting (perplexity, task accuracy, or memory at a fixed guarantee) where predicted per-head agreement beats a uniform policy?
  2. What distinguishes Olmo-3 from the other families: query/key normalization, the hybrid layer layout, or the training recipe?
6 comments
AuthorsOpenReview ↗

Response to Reviewer 52bM (1/4)

Thank you for tracing 34 numbers through the repository. You wrote that the findings that survive "are strong", and your list of them is now the paper's contribution paragraph (Section 1). MQE (Mean-Query Eviction) is the revision's name for the score. Below, EA is Expected Attention and QF is Q-Filters.

W1.

The predictor has no demonstrated operational value, and it fails precisely where it is needed. The abstract claims that “a serving system can therefore tell before decoding which heads it can evict blind.” The authors’ own results show that a system does better without the model.

ModelDirect measurementTwo-moment model
Llama-3.2-1B0.9650.942
Llama-3.2-3B0.9700.938
Qwen2.5-1.5B0.9540.900
Olmo-3-32B0.9870.960
Olmo-3-7B0.9720.895
Qwen3.5-9B-Base0.9460.898

These numbers are taken directly from the authors’ supplementary repository (rel_meas_query_half in results/r22_ceiling.json and results_r33/r22_ceiling.json). They report the unadjusted Spearman correlation of agreement measured on 16 real prefill queries against 17 disjoint ones. Direct measurement also requires fewer exact cost evaluations than the model’s 330 simulated events.

We agree for the predictor, and drop "a serving system can therefore tell before decoding which heads it can evict blind" from the abstract.

Measured on 16 real queries, agreement ranks heads better than the two moments on all six models. The moments still explain why agreement varies. Queries that concentrate around their mean direction agree, and spread ones do not.

W2.

Registered downstream uses likewise fail. Budget allocation by predicted (or even measured) agreement does not beat uniform allocation (App. K, Table 9). Per-head safety factors free essentially no more cache than a uniform factor: 0.264 vs 0.261 dropped, with paired per-unit median +0.0000; the registered primary endpoint is not met (App. Q). The main text never summarizes the allocation result, even though App. K, App. Q and Table 3 all point to Section 5 for it.

We agree, and Section 6 now states the allocation result in two sentences.

  • Allocating budget by predicted or even measured agreement is level with uniform allocation at a tenth of the cache, and below it at a quarter and a half (Appendix K).
  • Per-head inflation factors free no more cache than a uniform factor (Appendix Q).

So our answer to your Q1 is no.

AuthorsOpenReview ↗

Response to Reviewer 52bM (2/4)

W3.

Appended questions break transfer: for RAG, QA and LongBench, prefill moments fail on 5 of 7 configurations. The claim that “the model family decides” rests on two Olmo-3 checkpoints against five others, a single document, and 48 questions in one template. Agreement among those questions also lies close to its marginals-preserving null (0.497 vs 0.437; App. L, p. 20). This is far too thin to separate “family” from a specific architectural or training property.

We agree, and Section 5.1 drops the family claim.

It now says that prefill moments fail on most configurations tested, and that both passing configurations are Olmo-3, on one document and one 48-question template.

On your Q2, three readable fields of the six configurations are unique to Olmo-3:

  • query and key normalisation over the whole projection, before the head split
  • sliding-window layers that keep a KV cache
  • YaRN RoPE scaling.

The paper calls them candidates, with no demonstrated cause.

On the null, question agreement is 0.497 against 0.437 for the marginals-preserving null (Appendix L). Most of the overlap is the same tokens dominating every question. Appendix L reports this as the near-duplicate regime of Section 5, reached through homogeneous content.

W4.

Evaluation scope, proxy validity and positioningThe protocol is narrow and partly misdescribed.

  • Apart from LongBench, every result rests on one 8192-token document per model.
  • The code scores eviction only on one fixed early span, tokens [64, 2944) (mid = arange(NSINK, min_qpos − NREC)). This span is shared by all queries at positions ≥ 3200; it is not each query’s visible cache, contrary to the reading of Section 3 (p. 4).
  • The headline split uses a dense 72-position grid, not the 33-query rule of Section 3.
  • Table 2’s “1040 of 2880 mid-cache tokens” is in fact 720 selected mid-cache tokens plus the 320 sink and recency tokens.
  • The simulation runs on the evaluation half’s own positions, keys and values, so the claim that the two halves “share nothing” (Fig. 1 caption) holds only for the query vectors.

You were right on each point. Section 4 and the caption of Figure 2 now say what the code does.

Your pointWhat the code does
Evicted spanOne fixed range, positions 64 to 2,943, shared by every query
Visible cache64 sink tokens, the span's retained tokens and the query's own last 256 positions. Positions in between are dropped for every arm
Headline splitA 72-position grid (the submission named the 33-query rule)
"1040 of 2880"720 selected mid-cache tokens plus 320 sink and recency tokens
SimulationUses the evaluation half's own keys and values, so the halves share only their queries

We add one caveat. PyramidKV matches the 720-slot count only on average over layers.

AuthorsOpenReview ↗

Response to Reviewer 52bM (3/4)

W5.

The policy comparison is correspondingly thin: one model, one document, one budget. Outputs are per-head on frozen captures with no propagation across layers. The margin over Expected Attention is only 0.00035 in absolute regret.

Done: three budgets on the corrected capture, then six models.

On Llama-3.2-1B, every baseline runs from released code at matched slots and granularity.

Llama-3.2-1B, MQE vsTenthQuarterHalf
EA as released, per query headlevelahead, -0.00013 [-0.00025, -0.00001]ahead, -0.00006 [-0.00015, -0.00001]
QF, per query headlevellevelahead
EA, per KV head (saves memory)levelaheadahead
QF released, per KV headlevellevellevel

MQE closes 91 to 93% of the distance from H2O to an ordering that reads the held-out queries (Section 6.1, Table 2).

We extended this to six models and three disjoint 8,192-token segments of two genres. Brackets give paired median differences.

18 cells, MQE vsMQE lowerLevelOther lower
EA as released, per query head8 (-0.00004 to -0.00393)73, all Qwen3.5-9B-Base (+0.00040 to +0.00149)
QF, per query head5112, at half the cache
EA, per KV head5103
QF, per KV head6111

With its rotation matched to the evaluation positions, EA is lower in 15 of the 18 cells. The submission's sensitivity row showed this on the capture of record (Figure 6, Table 17).

Regret on frozen captures does isolate each head. The rerun LongBench and new RULER runs measure the effect end to end, with every layer compressed at once (W6 below).

W6.

The proxy itself is not supported by the task results. At a quarter of the cache, KVzip and KeyDiff incur 2–3× the score’s Table 2 regret, yet they are the strongest compressed arms on LongBench. The score sits below the released H2O and above only SnapKV; the claimed 45 % normalization gain disappears. The LongBench run is underpowered and noisy (50 samples per subset, ±3-point intervals) and yields full-cache scores of only 16.0 on TREC and 24.5 on LCC. Those low scores coincide with the disclosed chat-templating of every subset and a brittle classification metric; KeyDiff even exceeds the full-cache baseline.

We agree on all three, and the numbers are corrected.

Visibility division's cut in H2O regretSubmittedCorrected
Llama-3.2-1B45%7.1% (budgets matched)
Three 2024 models, pooled over three segments–2 to 17%
Three 2025 to 2026 models, pooled–21 to 66%

Appendix S gives the per-model values. The low full-cache scores came from the chat template, which the official convention skips on few-shot tasks. The rerun on Llama-3.1-8B-Instruct gates compressed arms on sane full-cache scores.

LongBenchSubmitted runRerun
Prompts and metricschat template on every subsetofficial
Samples per subset (first n, seven subsets)50150
Full cache, TREC / LCC16.0 / 24.568.7 / 61.2 (gate passed)
Rerun, a quarter keptMacroMQE minus arm
Full cache46.9
KVzip46.8
EA41.4-2.9 [-4.4, -1.3]
MQE38.6
KeyDiff35.8
QF32.6+5.9 [+4.1, +7.8]

On RULER, from NVIDIA's code, MQE is ahead of QF in 7 of 10 settings (details in our reply to r5UT). The 50-sample run stays in Appendix P, with its deficit to EA at half the cache.

On the proxy, regret uses continuation queries, while LongBench asks its questions after the context. In that regime KeyDiff and KVzip, which do not model the queries, also lead on RULER in all ten settings. Section 8 scopes regret and MQE's gains to continuation queries.

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

The paper investigates how cross-query agreement affects query-free KV-cache eviction. The authors propose a method that uses two statistics of query vectors to predict cross-query agreement and derive an eviction score based on the mean query direction. Experiments across six language models show strong correlations between predicted and measured agreement on held-out continuation queries. The proposed eviction score achieves lower regret than several existing methods on held-out continuation queries, but shows limited improvements over Expected Attention on LongBench.

Critical strengths

S1: Evaluation across multiple models. The paper evaluates cross-query agreement across six language models from three different families, providing evidence that the observed correlations hold across different models and scales.

S2: Interesting insights. The paper provides interesting insights into how cross-query agreement limits the effectiveness of query-free KV-cache eviction and how query geometry can help predict which attention heads are more suitable for query-free eviction.

Critical weaknesses

W1: Limited downstream benchmarks. The downstream evaluation is limited to LongBench. Additional benchmarks, such as RULER and InfiniteBench, would help validate the proposed method across different long-context tasks.

W2: Limited downstream gains. Despite achieving lower regret on held-out continuation queries, the proposed method shows limited improvements on LongBench, performing comparably to or worse than Expected Attention.

W3: Limited evaluation of eviction scoring. The regret comparison in Table 2 is limited to one model (Llama-3.2-1B), one document, and one cache budget. Additional experiments across models, documents, and retention ratios would help establish the robustness of the proposed eviction score.

Questions for authors

Q1: Downstream evaluation. Could the authors evaluate the proposed method on additional long-context benchmarks, such as RULER or InfiniteBench?

Q2: Downstream evaluation on Olmo-3. Could the authors evaluate the proposed eviction score on downstream tasks using Olmo-3, where prefill query statistics reliably predict agreement on appended questions?

Q3: Robustness of eviction scoring. Could the authors extend the regret comparison in Table 2 to more models, documents, and cache budgets?

3 comments
AuthorsOpenReview ↗

Response to Reviewer r5UT (1/2)

Thank you for a clear review. The revision centres on the insight you note, that query geometry predicts which heads suit blind eviction. It calls the proposed method MQE (Mean-Query Eviction). In the tables, EA is Expected Attention and QF is Q-Filters.

W1.

W1: Limited downstream benchmarks. The downstream evaluation is limited to LongBench. Additional benchmarks, such as RULER and InfiniteBench, would help validate the proposed method across different long-context tasks.

Done: RULER from NVIDIA's official code.

We chose it over InfiniteBench because its 13 tasks at two context lengths gave item-paired comparisons on three models within the discussion period. Both place the question after the context. Each of the 13 standard tasks has 27 items, at 4k and 8k, on Llama-3.1-8B-Instruct, Qwen2.5-7B-Instruct and Llama-3.2-3B-Instruct. Llama-3.2-3B-Instruct is the instruct sibling of a model we measure, and Llama-3.1-8B-Instruct also runs at half and a tenth of the cache.

Macro, a quarter kept, 4k / 8kLlama-3.1-8BQwen2.5-7BLlama-3.2-3B
Full cache94.7 / 93.992.5 / 90.791.8 / 83.4
KVzip95.0 / 93.292.1 / 90.486.3 / 80.2
KeyDiff70.9 / 72.069.4 / 70.268.5 / 67.8
EA54.2 / 48.131.8 / 29.241.0 / 42.0
MQE46.0 / 44.032.2 / 31.436.6 / 37.2
QF38.1 / 38.328.1 / 28.451.3 / 48.1

Paired by item over these six settings and the four at half and a tenth on Llama-3.1-8B:

MQE vsAheadLevelBehind
QF, also built on a query direction712, on Llama-3.2-3B
EAnone46
KeyDiff and KVzip (secondary)nonenoneall 10

This matches the boundary the paper measured. In most configurations tested, prefill query statistics do not predict what an appended question will need, and KeyDiff and KVzip do not rely on them. LongBench is in W2 below. Section 6.2, Figure 7, Table 14 and Appendix P give the details.

AuthorsOpenReview ↗

Response to Reviewer r5UT (2/2)

W2.

W2: Limited downstream gains. Despite achieving lower regret on held-out continuation queries, the proposed method shows limited improvements on LongBench, performing comparably to or worse than Expected Attention.

On the rerun LongBench, MQE is ahead of Q-Filters and behind Expected Attention.

The submitted run applied the chat template to every subset. There MQE was level with Expected Attention at a quarter of the cache and behind it at half (-2.9 [-5.1, -0.9] points). The rerun uses the official prompts and metrics and three times the samples, the first 150 of each of the seven subsets. Its gate on full-cache scores passed (Table 12).

Rerun, a quarter keptMacroMQE minus arm
Full cache46.9
KVzip46.8
EA41.4-2.9 [-4.4, -1.3]
MQE38.6
KeyDiff35.8
QF32.6+5.9 [+4.1, +7.8]

Measured directly on the corrected Llama-3.2-1B capture, MQE is ahead of Expected Attention as released at a quarter and half of the cache. This holds per query head and per KV head, with paired intervals that exclude zero. It is level at a tenth, and closes 91 to 93% of the distance from H2O to an ordering that reads the held-out queries (Table 2).

Over six models, three segments and three budgets, MQE has lower regret than Expected Attention as released in 8 of 18 cells, and higher in 3, all on Qwen3.5-9B-Base. Against Q-Filters it is lower in 5 and higher in 2 (Figure 6, Table 17).

W3.

W3: Limited evaluation of eviction scoring. The regret comparison in Table 2 is limited to one model (Llama-3.2-1B), one document, and one cache budget. Additional experiments across models, documents, and retention ratios would help establish the robustness of the proposed eviction score.

Done: six models, three segments and three budgets, with every baseline from released code.

18 (model, budget) cellsMQE's regret
Against EA as releasedlower or level in 15
Against QFlower or level in 16
Against H2O as releasedmedian 22 to 85% lower, in all 18

Figure 6 and Appendix S give the per-model values.

Q1.

Q1: Downstream evaluation. Could the authors evaluate the proposed method on additional long-context benchmarks, such as RULER or InfiniteBench?

Answered with W1 above.

Q2.

Q2: Downstream evaluation on Olmo-3. Could the authors evaluate the proposed eviction score on downstream tasks using Olmo-3, where prefill query statistics reliably predict agreement on appended questions?

We ran it. On this checkpoint the full cache itself gives degenerate answers, so the run tests no policy.

We ran LongBench on Olmo-3-7B-Instruct as registered: 100 samples of each of the seven subsets, then the registered restoration to 150. In our pipeline the full cache answers with a lone quotation mark or "he" on NarrativeQA, and repeats question stems on TREC (macro 10.7, TREC 3.0). Appendix P records the run outside the evidence and draws no comparison from it (Table 13). It is also the instruct checkpoint, while the paper measures base checkpoints. The kvpress library needed three declared adaptations to run Olmo-3, applied to the full-cache arm as well.

Q3.

Q3: Robustness of eviction scoring. Could the authors extend the regret comparison in Table 2 to more models, documents, and cache budgets?

Answered with W3 above.

We hope the revision resolves your concerns, and we would appreciate it if you took it into account in your final score. We are happy to discuss any point further.

AuthorsOpenReview ↗

Follow-up for Reviewer r5UT

We ran the RULER evaluation you suggested, from NVIDIA's official code: 13 tasks at 4k and 8k on three instruct models, with item-paired comparisons against Expected Attention, Q-Filters, KeyDiff and KVzip. Against Q-Filters, the closest method using a query direction, our method is ahead in 7 of 10 settings. The paper now has a second downstream benchmark beyond LongBench. We would be glad to hear whether this resolves your concern, and if so, we would be grateful if you would consider revising your rating.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Response to all reviewers (1/2): main results

We thank the three reviewers. The revision puts first the findings that Reviewer 52bM listed as surviving. It corrects every number found wrong by the reviews or our own audit. The main results:

  • How far a head's queries agree bounds every policy that evicts before they arrive (Lemma 1). We measure it exactly for every head. It varies more than tenfold between heads of one model. Some heads can be cut blind at almost no cost. On others, any fixed set overlaps the queries' own retention sets by at most about one half.
  • Two query moments rank heads by agreement at Spearman +0.895 to +0.960 on held-out queries, with nothing fitted.
  • Guarantees met on the queries that chose the kept set break on 8.9 to 26.1% of unseen (head, query) blocks, at a mass budget of 0.01.
  • MQE (Mean-Query Eviction), our query-free policy built on the first query moment, has 22 to 85% lower median regret than H2O as released in all 18 (model, budget) cells. It matches or exceeds Expected Attention as released (Devoto et al., 2025) in 15 cells and Q-Filters (Godey et al., 2025) in 16, by paired 95% intervals.
  • On Llama-3.2-1B, MQE closes 91 to 93% of the distance from H2O to an ordering that reads the held-out queries.

The cells cross six models (1B to 32B, three families, released 2024 to 2026) with three budgets, pooled over three disjoint 8,192-token segments. Regret is on held-out continuation queries.

Query-free eviction cuts the KV cache before the question arrives, so one compressed context can serve many questions (Kim et al., 2025). The paper tells, head by head, whether that can work. Close queries agree about twice as much as distant ones, which tells an evaluation which regime it tests. In most configurations tested, prefill statistics do not carry over to questions appended after the context. RULER (Hsieh et al., 2024) asks such questions. In all ten settings we ran, the three policies that score keys through query statistics stay below KeyDiff (Park et al., 2025) and KVzip (Kim et al., 2025). MQE is one of the three. KeyDiff uses key similarity alone, and KVzip has the model reconstruct the context. Our reply to Reviewer r5UT gives the table.

MQE against the strongest published policies, at matched budgets and granularity:

ComparisonMQE lowerOther lower
Expected Attention and Q-Filters, Llama-3.2-1B capture, 12 paired comparisons5none
Expected Attention as released, 18 cells83, all on Qwen3.5-9B-Base
Q-Filters, 18 cells52, at half the cache

With its rotation matched to the evaluation positions, a sensitivity the submission reported, Expected Attention is lower in 15 of the 18 cells.

AuthorsOpenReview ↗

Response to all reviewers (2/2): corrections and changes to the PDF

Corrections (submitted to corrected, same capture):

Number in the submissionSubmittedCorrectedWhy
Visibility division's cut in H2O regret (abstract)45%7.1%H2O kept a median of 319 of 720 mid-cache slots. Every arm now keeps exactly 720
MQE's regret relative to H2O as released0.42x0.61xsame budget correction
Gap closed to the ordering that reads held-out queries95%93%same
KVzip median regret0.01290.0106KVzip read the prefill through the last evaluation query
Expected Attention per query head, margin to MQE+0.00035+0.00013 [+0.00001, +0.00025]it read the prefill through position 8,192
Expected Attention per KV head, margin to MQE+0.00031+0.00015 [+0.00006, +0.00023]that block read past the first evaluation query

Every arm of the submitted Table 2 read the prefill through position 8,192, MQE included. Appendix N disclosed this only for its third block. Every arm now reads only the context before the first evaluation query, except the reference ordering, labelled as reading held-out queries. Most corrections moved toward the competitors, the largest exception being H2O with the visibility division. On the corrected capture, MQE is ahead or level in every paired comparison with Expected Attention and Q-Filters (Table 2).

We also drop one abstract sentence. Measured directly on a few real queries, agreement ranks heads better than the two-moment model, which explains agreement without replacing its measurement.

Baselines from released code (Appendix N):

  • kvpress presses, where kvpress ships the method
  • Q-Filters with its released filters, or the authors' recipe where none exist
  • the H2O authors' heavy-hitter code
  • THUDM's LongBench prompts and metrics, and NVIDIA's RULER.

PyramidKV is not rerun, since its per-layer budgets cannot keep the matched count. Our earlier ports give the official sets exactly, with three exceptions. SnapKV differs by one token, as the release pads its observation window. The StreamingLLM release keeps the most recent mid tokens, and Table 2's port the oldest. The block-wise KeyDiff release ranks the mid region alone.

Changes to the PDF (Blue marks results and content added in this revision. Changes of wording are not marked.):

  • Abstract and Section 1 lead with the bound and the measurement.
  • Related work is now Section 2, so Sections 2 to 6 of the submission are Sections 3 to 7.
  • Sections 2 and 6.1 cite and compare Q-Filters.
  • Sections 2 and 3 describe Expected Attention with its covariance term.
  • Sections 2, 3 and 6.1 credit RoCo for the visibility division and CAOTE for the exact cost.
  • Section 4 and the Figure 2 caption correct the evicted span, query grid, slot count and simulation.
  • Table 2 (Section 6.1) is corrected and extended. The ordering that reads held-out queries is labelled a reference, since Expected Attention with its rotation over the evaluation positions goes below it.
  • Figure 6 and Appendix S give regret on six models.
  • Section 6.2 and Appendix P add RULER and the rerun LongBench. They keep the Olmo-3 LongBench run as a record outside the evidence, since its full cache gives degenerate answers.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.