- Rating
- 2
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies whether a language model can estimate the error introduced by KV-cache eviction using only the information retained after compression. The authors first prove that, under deterministic value blind eviction, the attention output error is not identifiable from the retained cache alone.
To address this limitation, they propose a randomized eviction scheme combining deterministic retention of important tokens with Poisson sampling of the remaining tokens. By tracking inclusion probabilities and applying a correction to the attention logits, the method enables estimation of the variance of the attention output error from retained tokens. An empirical Bernstein-style radius is then used as an online error certificate.
The paper evaluates this approach across multiple model architectures, synthetic retrieval tasks, LongBench, and conversational memory benchmarks. The results demonstrate strong empirical coverage and correlation with attention output error. However, the certificate is much less effective at predicting answer correctness. Its more promising applications are identifying eviction induced failures and guiding retrieval of discarded context, although the gains from selective recomputation are limited on real conversational workloads.
Critical strengths
1. Interesting and well motivated idea. The paper addresses an important problem: how to know whether removing tokens from the KV cache has negatively affected the model's output. I find the idea of using randomization to estimate this error interesting, especially since most existing methods focus on deciding which tokens to keep rather than evaluating the impact of removing them.
2. Extensive experiments and honest discussion of limitations. The paper includes experiments across different models, tasks, and context lengths, which helps support its findings. I also appreciate that the authors clearly report cases where their method does not perform well, particularly when predicting whether the model's final answer is correct.
Critical weaknesses
1. The theoretical guarantees seem limited. While the paper provides theoretical results supporting the proposed approach, the actual error certificate does not appear to have a complete theoretical guarantee. Its reliability is mainly demonstrated through experiments. I think this distinction should be clearer, especially since the term "certificate" suggests a stronger guarantee.
2. The practical improvement is not always clear. Although the method estimates attention error well, it is less clear how much it improves the final system. In particular, on real conversational tasks, certificate based retrieval performs similarly to simpler approaches such as random or confidence based retrieval, as far as I understand. Additionally, a relatively simple deterministic method achieves results close to the certificate in some experiments. Given the additional complexity of the proposed approach, I would like to see stronger evidence of its practical benefits.
Questions for authors
1. Theoretical guarantees: The paper reports strong empirical coverage of the proposed error certificate, but its theoretical guarantees appear more limited. Could the authors clarify under what conditions the certificate can be considered reliable, and whether there are situations where it might underestimate the actual error?
2. Comparison with simpler methods: Table 10 shows that a relatively simple deterministic method achieves results close to the proposed certificate in some settings. Could the authors explain what the main advantage of introducing randomization is in these cases, especially considering the additional complexity?
3. Sensitivity to parameter choices: Table 6 shows that the fraction of queries flagged by the certificate changes substantially depending on parameters such as the confidence level. How should these parameters be selected in practice, especially when labeled data is not available?
5 comments
(2/2): W2/Q2 the simpler method and what randomization buys; Q3 parameters without labels
W2 / Q2. The simpler deterministic method, and what randomization buys. The Table 10 summary comes within 3 points of the certificate per cell on the SnapKV-style arm (9 points pooled), and we report that as its strength. Three things separate the two:
- Evictor independence. The summary needs one mean key to represent the evicted set. That works on the SnapKV-style arm (per-cell means 0.645 against 0.674) and fails on the H2O-style arm (0.554 against 0.671, +11.7 points [+8.7, +14.7]). The certificate reads the retained sample, whatever the evictor's score.
- A scale. The certificate is a relative radius with one fixed rule, cert >= 1. On the ten-turn vignette its median crosses 1 where 225–308 tokens remain resident, on five models (Table 5), and one global threshold schedules re-runs on four tasks at once (Table 7). The summary was scored by its ranking only (Table 10); we tested no fixed threshold on it. Pooling the cells (models, tasks, budgets) lowers its AUC on the SnapKV-style arm (0.645 per cell, 0.614 pooled) and raises the certificate's (0.674, 0.705); on the H2O-style arm pooling does not lower it (0.554, 0.575).
- Localization and validity. The certificate ranks evicted blocks: the fact block is
in the top three in 79–93% of red flags against 13–59% for attention mass (Table 13).
It also comes with a coverage statement; the summary ranks queries only. We tested the
summary's block form during the discussion (E-A, Tables 26–27):
- on red flags, the fact block is in its top three in 18–61% of cases, against 50–98% for the certificate (Table 27);
- on all questions, at the same volume, its retrieval accuracy is 0.26–0.53 against 0.50–0.79 (Table 26);
- a Quest-style per-dimension bound does better in three of four cells and still trails by 9–30 points.
On complexity: one logit offset and one stored scalar per retained token, and an estimator that is one sum over the retained tail per head and step. On practical benefit on real conversations we claim no more than the paper shows. On LoCoMo, gating is within 2.4 points of random gating at the same rate (Table 12). The new split finds +0.6 to +2.5 points on questions whose evidence spans several turns, with intervals above zero in seven of nine cells, and one cell above zero and one below on single-evidence ones (Table 24). The benefit claimed is the label-free rate and the block, not the query.
Q3. Choosing δ, the probed steps and τ without labels. δ = 0.1, six probed steps and four heads per layer were first used together in the base-model synthetic suite (17 July), before the registration, and kept for the pre-registered LongBench suites and every later task-level run. τ = 1 is the unit of a relative radius (the certified error exceeds the output's own norm). It is not part of the registration: it was adopted after the first ten-turn run (24 July) and held fixed for everything after (Appendix B).
Table 6 shows what these constants do: they scale the radius, so they move the rate at which cert >= 1 fires and change the ranking little. Across the settings shown, except the maximum over units, the AUC is 0.77–0.82 at 25% and 0.86–0.91 at 15%. With the variants computed but not shown it is 0.85–0.94 at 15%.
Two label-free procedures follow (the paper states the first):
- Keep the nominal constants and the rule cert >= 1, whose red-flag rate reads the damage: 0.98–1.00 at the 10% budget on the four models run there on the ten-turn vignette (Table 5), and 0.00 at 25% on LoCoMo (Table 4).
- Given a retrieval budget r, threshold the certificate at its (1 − r) quantile on unlabeled traffic, which needs no labels. Table 7 evaluates this procedure at re-run rates of 5–50%. Under the same single threshold a confidence score does worse than random gating, and it catches up with a threshold per model and task.
We hope this states the guarantee at the precision the review asks for and separates what the certificate does from what the simpler summary does. If you prefer "error radius" in the body we will make that change, and we would be grateful if you would reconsider the assessment in light of the revision.
Dear Reviewer L2iq,
Thank you again for your review. We have updated our two responses to you and the general response in place, and uploaded a revised PDF (added and changed text in blue). Section 3.4 now states what is proved and what is measured, and Appendix A.4 and Table 25 when the radius underestimates. The simpler summary is compared in Table 10 (prediction) and Tables 26–27 (localization); how the constants were set is in Section 3.4 and Appendix B, and their effect in Table 6. The discussion closes on November 18 (AoE); if any point remains open, we would be glad to answer it before then.
(1/2): W1/Q1, what is proved, what is measured, and when the radius underestimates
Thank you for the review. The two weaknesses concern the two things we most want to state precisely: the guarantee (part 1) and the practical use (part 2).
W1 / Q1. What is proved, what is measured, and when the radius underestimates.
Proved.
Measured. The deployed radius has the empirical-Bernstein shape of eq. (4): a variance term sqrt(2 V̂_t log(1/δ)) plus a range term, with the estimate plugged in. Its coverage is measured, not proved:
The median radius is about three times the realized error. We agree this belongs in Section 3.4 rather than Appendix A. The revision says it there, and Section 3.4 defines "certificate" (the word is used earlier) as a design-based error radius with measured coverage, the sense of the survey-sampling literature. If you prefer "error radius" in the body, we will use it throughout; the title is fixed by the conference rules.
When it underestimates.
New (A-2): profile of the deployed coverage run. The lowest-coverage decile of answers has:
Per-unit coverage also drifts down from the first to the sixth probed step, by about one point on Qwen and 0.1–0.4 on Llama (Table 25). Together these point to mechanisms (b) and (d).
The Chebyshev plug-in without the range term, the shape that is provable with the true variance, is 0.86–0.94 of the deployed radius (per-cell medians of the coverage records). It still covers the deployed error of every answer in that run, and 0.935–0.994 of the units across the 96 configurations of the new sensitivity replay (Appendix A.4, Tables 25 and 28).