- 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.
- 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
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 to % 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.
- 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.
- 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.
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.
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.
MQE now runs on Qwen models, in the error comparison and on RULER.
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).
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.
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:
Combined, they match or beat their sources as released where we can measure them, with every baseline from released code (Section 6.1):
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.
Answered with W1 above.
Q2.
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.