acceptodds
Under review as a conference paper at ICLR 2027

Error Certificates for KV-Cache Eviction via Randomized Design

Abstract

Deterministic KV-cache eviction keeps the top- tokens under an importance score and deletes the rest, and after the deletion the serving system cannot know what the eviction cost it on the current query. We replace the deterministic tail with Poisson sampling at known inclusion probabilities, which makes the eviction error identifiable and turns a survey-sampling variance estimator over the retained set into a per-step error certificate at one extra scalar per retained token. We prove that no estimator computable from the information a deterministic, value-blind scheme retains can bound its own eviction error: evicted values can be altered so that everything retained is unchanged while the true attention-output error grows without bound. The certificate covers the realized attention error in 96.9-97.7% of 12,096 replay cells, in 98.1-99.7% on twelve further architectures, and in every answer of a deployed streaming assistant. A pre-registered study on LongBench at 6k and 16k tokens (about 74,000 generations) finds that the certificate does not predict task failure, output log-probability does, and the certificate separates eviction-induced from inherent failures better than confidence under either sign (AUC 0.70-0.76 against 0.54-0.57); a cheap summary of the evicted set gives a deterministic evictor most of that separation (within 3 points on SnapKV) but no calibrated scale. Gating recomputation on the certificate matches random gating at the same retrieval rate on real conversations and beats it on synthetic ones, and its variance decomposition localizes the lost block far better than raw attention (fact block in the top three in 79-93% against 13-59% of cases). Randomization buys a calibrated, evictor-independent error estimate and a localizer, not prediction.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
KV cache eviction, long-context inference, error certificate, survey sampling, uncertainty quantification, LLM serving

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 2 reviews, above 27% of the others.
Reviewer_L2iqOpenReview ↗
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
AuthorsOpenReview ↗

(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.

  • Theorem 1: under deterministic value-blind eviction, the error is not identifiable from the retained state.
  • Theorem 2: under the Poisson design, the retained-set estimator V̂_t is first-order unbiased for the design variance V_t of the linearized attention-output error, with an O((B/m)^2) remainder. The conditioning on the query is exact when the query does not depend on the draw, as in the replays. In deployment with one draw shared by all layers, the queries of higher layers depend on it (case (d) below).
  • Appendix A.4: with the design variance, Chebyshev's inequality gives a radius sqrt(V_t / δ) that covers the linearized error with probability 1 − δ over the design, finite-sample and distribution-free.

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:

  • 96.9–97.7% of 12,096 replay cells;
  • 98.1–99.7% on twelve further models at the 25% budget;
  • 97–99% per unit and 100% for the deployed statistic in the streaming assistant (Table 14).

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.

  • (a) Per realization: a draw that misses the token the current query needs, the 1–3% of uncovered units. Retrieval-type amnesia (Section 7) is a different failure: it occurs while the radius covers the attention error (Table 14).
  • (b) Misalignment of the decode query with the prefill scores, which inflates B in Assumption 2. The range term guards against a few heavily weighted tail tokens, but it is a sample maximum.
  • (c) An empty retained tail gives V̂_t = 0, and a negligibly weighted one a V̂_t at or numerically near zero; a deployment should read either as a red flag. No certificate logged in the submitted runs is exactly zero (the submitted replays logged summaries only), though near-zero per-unit radii occur in the Table 6 traces; the discussion-period replays of Tables 28–29 log 13 zero radii, all in layer 0 of Qwen2.5-1.5B-Instruct.
  • (d) Queries that depend on the draw. With one draw shared by all layers, this covers every layer above the first from the first decode step on, and all queries at later steps.
  • (e) The deployed aggregate, a mean over probed units and a maximum over steps, which Theorem 2 does not cover.

New (A-2): profile of the deployed coverage run. The lowest-coverage decile of answers has:

  • a higher realized error (for instance 0.55 against 0.43 on Llama at 15%, ten turns);
  • a slightly larger range-term share (equal in one cell); the Spearman correlation between the uncovered fraction and the range-term share is +0.13 to +0.59 across cells;
  • a radius-to-error ratio of 2.4–2.8, against 2.6–3.1 for the other answers.

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).

AuthorsOpenReview ↗

(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:

  1. 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.
  2. 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).
  3. 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.

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

This paper studies error diagnosis following KV-cache eviction. The authors first argue that deterministic, value-blind eviction methods cannot identify their attention-output error from the retained state alone. To address this, the paper combines deterministic retention with Poisson sampling, records token inclusion probabilities, and constructs an online error indicator using Hájek correction and design-based variance estimation. Experiments show that this indicator tracks local attention error well, but is less effective than output confidence at predicting answer failures on real-world tasks.

Critical strengths
  1. The paper offers a perspective on KV compression beyond optimizing retention policies. It focuses on whether a system can assess the error introduced by compression, rather than further refining token importance scores, providing a useful conceptual framework for understanding KV eviction.

  2. The experimental scope is reasonably broad. The authors distinguish local error estimation, answer-failure prediction, failure attribution, and fallback decisions, with evaluations across multiple models, tasks, and context lengths.

  3. The error indicator shows promise for compression diagnosis and selective information recovery. It achieves high empirical coverage and strong correlation with actual error in replay experiments. Its variance contributions also help identify historical blocks to recover, suggesting a direction worth further investigation.

Critical weaknesses
  1. Comparisons with relevant alternatives are incomplete. The experiments primarily evaluate H2O, SnapKV, StreamingLLM, and their variants, without directly benchmarking MagicPIG or vAttention, both discussed in the paper. In particular, the fallback setting allows historical information to be retrieved from host memory, yet no comparisons are provided against on-demand retrieval or offloading methods.

  2. End-to-end efficiency is not evaluated, leaving diagnostic and fallback costs insufficiently accounted for. The paper reports overhead from probing and the unfused logit offset, but does not comprehensively measure end-to-end latency and throughput. Even if reliability is the primary focus, the proposed trade-off should be shown to outperform simple baselines under matched quality or latency constraints.

  3. Compatibility with mainstream inference systems remains unverified. The experiments run on a single GPU and do not explain integration with attention-head TP or vLLM PagedAttention. Under TP, diagnostic aggregation across heads and layers may require additional reductions or synchronization, whose costs should be measured. With paged KV caches, token-level random retention may not directly translate into physical GPU memory savings and could require page reorganization, compaction, or finer-grained indexing. Implementation and performance evidence is also lacking on whether per-token probability biases and variance computation can be efficiently integrated into existing fused attention kernels.

Questions for authors

Please see the weakness part.

4 comments
AuthorsOpenReview ↗

(1/3): W1, MagicPIG/vAttention and on-demand retrieval, with new experiments E-D and E-A

Thank you for reading the paper from the serving side. W1 and W2 asked for measurements and we ran them (parts 1 and 2); W3 is mostly design, with one measurement (part 3).

W1. Baselines: MagicPIG, vAttention, on-demand retrieval.

MagicPIG and vAttention. Both keep the full cache and sample it at every step; neither evicts, so neither meets the paper's question, what the system can know after tokens have left the device. MagicPIG's sampling is a design the certificate can sit on (Remark 3), and we now show it (E-D): in the replay protocol of Section 4 (instruct checkpoints, bf16), the Poisson tail is replaced by MagicPIG's design (centered SimHash, K = 8 hyperplanes per table, tables added until the expected retained size meets the budget, keys weighted by the inverse of their collision probability), with independent draws at those probabilities and with actual shared tables, whose dependence the single-sum estimator ignores.

modelbudgetcoverage: Poisson by score (paper's design) / LSH, independent / LSH, shared tablesSpearmanmedian error (top-k)
Qwen2.5-1.5B25%0.971 / 0.977 / 0.9640.97 / 0.91 / 0.890.029 / 0.136 / 0.148 (0.043)
Qwen2.5-1.5B12.5%0.965 / 0.967 / 0.9490.94 / 0.90 / 0.880.080 / 0.235 / 0.256 (0.096)
Qwen2.5-7B25%0.986 / 0.985 / 0.9800.97 / 0.91 / 0.890.035 / 0.147 / 0.153 (0.050)
Qwen2.5-7B12.5%0.980 / 0.975 / 0.9650.97 / 0.91 / 0.890.089 / 0.260 / 0.287 (0.113)
Llama-3.1-8B25%0.994 / 0.986 / 0.9760.98 / 0.91 / 0.890.038 / 0.139 / 0.155 (0.065)
Llama-3.1-8B12.5%0.993 / 0.984 / 0.9680.97 / 0.91 / 0.880.091 / 0.245 / 0.276 (0.126)

The certificate transfers to MagicPIG's design with the shape it has on ours: coverage above the nominal 0.9 in every cell, a median radius-to-error ratio of 3.0–3.5, Spearman 0.88–0.91 against 0.94–0.98 on the Poisson tail; shared tables cost 0.5–1.8 points of coverage. The LSH design's own error is 2.7–4.6 times the score-proportional tail's at the same retained size with independent draws and 3.0–5.0 times with shared tables, the price of collision probabilities that track the angle and not the score, which the certificate reports as a wider radius (Table 29). We did not re-implement either serving system: an accuracy-at-budget comparison would measure the sampling scheme, which the paper does not claim.

On-demand retrieval at matched volume (E-A). For every question of the ten-turn vignette (two models, 25% and 15% budgets, 200 questions per cell) we fetch 10% of the context from the archive (a GPU-resident copy in this probe; Appendix C) on every question, ranked by (i) the certificate's variance contributions, (ii) an eviction-time mean-key summary per block (the block form of Table 10), (iii) a Quest-style page bound (per-dimension min/max of each block's evicted keys), (iv) attention mass on the retained neighbours, (v) random; the gated policy fetches only on red flags. Cell: accuracy (average volume; 0.10 for every always-retrieve arm).

modelbudgetred-flag rategated, full archivealways: certificatemean keyQuest boundattention massrandomoracle
Qwen2.5-7B25%0.510.61 (0.51)0.740.260.440.580.260.94
Llama-3.1-8B25%0.280.42 (0.28)0.790.530.530.690.310.95
Qwen2.5-7B15%0.940.98 (0.94)0.500.280.410.340.230.90
Llama-3.1-8B15%0.930.98 (0.93)0.560.340.440.460.280.94

At the same volume the certificate's ranking is 21–48 points more accurate than the mean key, 9–30 more than the Quest bound (which closes part of the gap only at 15%, where most of each block is evicted and the box is informative) and 10–16 more than attention mass; both summaries need per-block storage at eviction time, the certificate's ranking comes from the retained sample it already has. At the 25% budget the gate fires on 28–51% of questions and misses failures it does not see (retrieval-type amnesia, Section 7), so always fetching the certificate's block at 10% volume (0.74–0.79) beats the gated full re-run at 28–51% volume (0.42–0.61); at 15% the flag fires on 93–94% and the full re-run (0.98) is the right policy. The certificate supplies the rate and the ranking (Tables 26–27).

AuthorsOpenReview ↗

(2/3): W2, end-to-end cost with a batched probe, and matched quality

W2. End-to-end cost and matched quality.

The submitted paper gave 0.2–0.3 s per answer for the probe and 12% per token for the offset. The measurement behind those figures, now in Appendix B and Table 30, gave per-answer latency on an H100: full cache / top-k / Poisson / Poisson + probe of 157 / 227 / 202 / 398 ms for short Qwen answers and 1,276 / 1,326 / 1,504 / 1,736 ms for answers capped at 128 tokens; Llama 84 / 72 / 102 / 294 and 1,443 / 1,440 / 1,624 / 1,891 ms. In that measurement the probe took a fixed 0.19–0.27 s per answer, and the unfused offset added about 13% per token over top-k on the answers capped at 128 tokens (12% and 4% on the short Qwen and Llama answers). We did not measure batched throughput and do not claim a serving implementation. Two additions.

E-C, batched probe. All probed heads of a layer in one call (same arithmetic, checked against the loop at run time to within 1e-6), same protocol and H100:

model, answersPoisson (paper run / new run)+ probe, loop (paper)+ probe, batchedprobe cost, loop / batched
Qwen2.5-7B, short (full-cache median 12 tokens)202 / 227 ms398 ms303 ms196 / 76 ms
Qwen2.5-7B, up to 128 tokens1,504 / 1,546 ms1,736 ms1,682 ms232 / 136 ms
Llama-3.1-8B, short (full-cache median 5 tokens)102 / 105 ms294 ms184 ms192 / 79 ms
Llama-3.1-8B, up to 128 tokens1,624 / 1,642 ms1,891 ms1,780 ms268 / 138 ms

The two Poisson values show the run-to-run spread of a shared node. The probe cost is the within-run difference, 76–138 ms per answer: a third of a short Qwen answer and 8–9% of an answer of up to 128 tokens (Table 30).

Matched quality. Table 7 is the comparison at equal accuracy. Under one global threshold, certificate gating re-runs 11.0% / 15.7% of the queries (25% / 12.5% budget) to reach the accuracy of random gating at a 25% re-run rate, and log-probability gating 27.5% / 30.4%. With a threshold per model and task log-probability needs 13.0% / 17.9% against the certificate's 12.8% / 19.5%: level at the 25% budget and fewer than the certificate at 12.5% (two seeds; about one point fewer at both budgets with four seeds, caption of Table 7). A re-run is a 16k prefill, 0.65 s (Qwen2.5-7B) / 0.75 s (Llama-3.1-8B) in the paper's harness (H200, Table 32), so the 9–14 points saved against random gating under one global threshold are 0.06–0.11 s per query. Against that, the probe costs 0.08–0.14 s per answer, timed on 1k-token dialogues on an H100. We did not time the probe at 16k, where its six steps run over a larger retained set, so we claim no wall-time saving: at 16k the gain is the lower re-run rate at equal accuracy. On real conversations gating is within 2.4 points of random at the same rate (Table 12), so the saving there is small. What remains there is the label-free rate. The accounting is in Appendix B.

AuthorsOpenReview ↗

(3/3): W3, tensor parallelism, paged caches, and the offset inside a fused kernel (E-E)

W3. Tensor parallelism, paged caches, fused kernels.

These are implementation questions. The revision answers one with a measurement and the rest with design arguments (Appendix B), summarized here. We have not built them into vLLM or SGLang and do not present them as results.

  • Storage. One fp16 scalar per retained token, against 57 KB (Qwen2.5-7B) or 131 KB (Llama-3.1-8B) of KV per token.
  • Paged caches. The retained set is a set of token positions, as for H2O or SnapKV. Any token-level eviction needs the same gather or compaction into pages, and randomization adds nothing new.

The offset in a fused kernel (E-E). The table gives microseconds per decode-step call (H100, bf16, batch 1, one query; backends forced and recorded). Flash takes no mask, so the mask path runs on the memory-efficient kernel:

layoutkeysflash+ maskFlexFlex + biasFlex, GQAFlex, GQA + biasbias in one extra head dim, flash
Qwen2.5-7B1k18.446.272.8103––18.7
16k85.3763113190––132
64k3613,020395685––544
Llama-3.1-8B1k18.751.273.074.166.467.719.2
16k97.976411419594.295.6151
64k4103,011395702114187619
  • The additive mask, the paper's harness path, costs 2.5–8.9 times the flash kernel. This plausibly accounts for the offset's cost of about 13% per token on the answers capped at 128 tokens, though we have not broken that cost down.

  • Folding the same bias into one extra head dimension keeps the flash kernel at 1.0–1.5 times.

  • Inside FlexAttention's fused kernel, on the GQA-native kernel, the bias costs at most 2% up to 16k keys and 1.6 times at 64k. At 64k that kernel is 3.6 times faster than the expanded flash call.

  • With K/V expanded to the query heads it costs 1.0–1.8 times (1.4–1.7 on the Qwen layout).

  • Output differences from an fp32 reference are 5e-4 to 1e-2 for all three paths, the bf16 level (Table 31, all four cache sizes).

  • The variance estimator in the same pass. sum_i w_i ||v_i - y_hat||^2 = sum_i w_i ||v_i||^2 - 2 y_hat . sum_i w_i v_i + ||y_hat||^2 sum_i w_i. These are three accumulators next to the softmax sums, with ||v_i||^2 computed from v_i in the same pass. The range term has a one-pass bound through ||v_i - y_hat|| <= ||v_i|| + ||y_hat||.

  • Tensor parallelism. Radii are per head, so each rank computes its own. The deployed statistic needs one scalar all-reduce per probed step, six per answer.

We hope the measurements answer W1 and W2 as posed, and W3 to the extent a paper without a serving implementation can. We will answer any point that remains open within the discussion period, and would be grateful if you would reconsider the assessment in their light.

Dear Reviewer TThZ,

Thank you again for your review. We have updated our three responses to you and the general response in place, and uploaded a revised PDF (added and changed text in blue). The measurements added for W1 and W2 are in Tables 26–27, 29, 30 and 32, and W3 is answered by design arguments and one kernel measurement (Table 31). The discussion closes on November 18 (AoE); if any point remains open, we would be glad to answer it before then.

Comments on the paper

4 comments
AuthorsOpenReview ↗

Authors' general response: what the certificate changes, and what was added during the discussion

We thank the reviewers. All three reviews describe the impossibility result, the identifiable variance estimator, and a certificate that tracks the attention error. All three also note what it does not do: the certificate predicts task failure only weakly. Two add that on real conversations its gating gains little over random gating. The first is the outcome of pre-registered tests (R1, S2); the second is a post hoc result (Section 7); the paper reports both as results. The question common to the reviews is what decision the certificate changes. Four, all in the submitted paper and all post hoc (Appendix D):

  1. The retrieval rate, without labels. One rule, cert >= 1, on five models from three families: on the ten-turn vignette the median certificate crosses 1 where 225–308 tokens remain resident (Table 5). The Table 10 summary was scored by its ranking only, with no fixed threshold; our reply to L2iq (part 2) gives that comparison.
  2. Fewer re-runs at equal accuracy. On 16k LongBench, under one global threshold the certificate re-runs 11.0% / 15.7% of the queries (25% / 12.5% budget) to reach the accuracy of random gating at a 25% re-run rate; log-probability needs 27.5% / 30.4%. With a threshold per model and task log-probability needs 13.0% / 17.9% against the certificate's 12.8% / 19.5%: level at the 25% budget and fewer than the certificate at 12.5% (Table 7, two seeds; about one point fewer at both budgets with four seeds).
  3. The block to fetch. The fact block is in the top three in 79–93% of red flags against 13–59% for attention mass. On those red-flagged questions, retrieving 10% of the context gives accuracy 0.70–0.87, against 0.66–0.74 for attention mass and 0.18–0.28 for random blocks (Table 13).
  4. Offline attribution. AUC 0.70–0.76 against 0.53–0.57 for confidence on LongBench, conditions pooled (Table 11); on LoCoMo the edge is 0–11 points with overlapping intervals.

What it does not do: predict task failure usefully (AUC 0.56–0.57 against the registered 0.6; log-probability does better), or pick individual queries on real conversations much better than random at the same rate (within 2.4 points, Table 12).

Added during the discussion. The revised PDF is uploaded. Added and changed text is in blue; deletions and the changes to Figures 1 and 4 are not marked. The main text stays within ten pages, Tables 1–23 keep their numbering and the new material is Tables 24–32.

  • E-A: two eviction-time page summaries (mean key; Quest-style per-dimension bound) as localizers and as always-retrieve baselines at matched volume: fact block in the top three in 18–61% and 42–55% of red flags against 50–98% for the certificate; at 10% of the context per question the certificate's ranking is 21–48 and 9–30 points more accurate (Tables 26–27; TThZ W1, aDBj Q3, L2iq W2).
  • E-B: certainty-layer share x floor replay on three models, 96 configurations: coverage 0.945–0.995, Spearman 0.93–0.98, only the width moves (Table 28; aDBj Q2).
  • E-C: the probe batched over heads, 76–138 ms per answer instead of 192–268 (Table 30), and prefill timing for the re-runs it saves (Table 32; TThZ W2).
  • E-D: the certificate on MagicPIG's LSH design: coverage 0.949–0.986, Spearman 0.88–0.91 (Table 29; TThZ W1).
  • E-E: the per-key offset inside attention: the paper's mask path costs 2.5–8.9 times the flash kernel, the same bias in one extra head dimension 1.0–1.5 times, inside a fused GQA kernel at most 2% up to 16k keys (Table 31; TThZ W3).
  • A-1: LoCoMo selectivity by evidence span: on multi-evidence questions +0.6 to +2.5 points over random, intervals above zero in seven of nine cells; on single-evidence questions above zero in one of nine and below zero in one (Table 24; aDBj Q1).
  • A-2: where the radius underestimates, profiled (Appendix A.4, Table 25; L2iq W1).
  • Text: Section 3.4 states what is proved and what is measured and defines "certificate"; Appendix B adds implementation notes and the cost accounting; Appendix C the protocols of the new replays and re-runs (Tables 24, 25 and 30–32 describe theirs in the captions).

Each reviewer's points are answered under their review.

AuthorsOpenReview ↗

(1/2): the payoff, and Q1 on where per-query selectivity appears (new analysis)

Thank you for the precise reading. Each of the three questions received an experiment or an analysis: Q1 and the payoff are in part 1, Q2 and Q3 in part 2.

On the payoff being narrower than the abstract suggests. We agree with the description. The abstract of the submitted PDF states both limits: the certificate "does not predict task failure", and gating on it "gains little over random gating at the same retrieval rate on real conversations". The revision corrects the first to "predicts task failure only weakly" (AUC 0.56–0.57, below the registered 0.6). We read "what you can certify doesn't matter that much" differently in one respect. What the certificate changes is mainly how many queries are re-run and from where, and on real conversations only slightly which query:

  • (i) One rule, cert >= 1, with no labels: on five models the median certificate crosses 1 where 225–308 tokens remain resident on the ten-turn vignette (Table 5).
  • (ii) At equal accuracy on 16k LongBench, it re-runs 11–16% of queries under one global threshold, against 25% for random gating. Under that threshold confidence gating does worse than random gating. With a threshold per model and task it needs 13.0% / 17.9% (25% / 12.5% budget), against the certificate's 12.8% / 19.5% under the same thresholds (Table 7, two seeds; with four seeds log-probability needs about one point fewer than the certificate at both budgets).
  • (iii) It places the fact block in the top three in 79–93% of red flags, against 13–59% for attention mass (Table 13).

Per-query selectivity on real conversations is where it adds little; Q1 asks where it appears at all.

Q1. Where per-query selectivity becomes clearer on real conversations. We split the LoCoMo cells at the 10–25% budgets by the number of evidence turns. We then recomputed certificate gating against random and log-probability gating at a matched 50% rate, with cluster-bootstrap intervals over conversations (Table 24). At the 2–5% budgets, which are not in the table, no multi-evidence interval is above zero.

modelbudgetseveral evidence turns: cert − random [95% CI]single evidence turn: cert − random [95% CI]
Qwen2.5-7B10% / 15% / 25%+0.6 [−0.1, +1.7] / +0.9 [−0.3, +2.2] / +1.7 [+0.6, +3.3]−0.3 [−1.7, +0.9] / −0.4 [−2.6, +0.7] / −0.4 [−1.9, +0.9]
Llama-3.1-8B10% / 15% / 25%+1.7 [+0.4, +2.9] / +2.5 [+1.1, +3.8] / +1.9 [+0.9, +3.3]+0.2 [−1.7, +1.7] / −0.0 [−2.0, +1.6] / +1.3 [+0.4, +2.5]
Qwen2.5-32B10% / 15% / 25%+2.0 [+0.5, +3.1] / +1.7 [+0.6, +2.9] / +2.0 [+0.8, +3.3]−1.5 [−3.0, +0.5] / −1.7 [−3.1, −0.4] / −0.0 [−2.5, +1.2]

On multi-evidence questions the intervals are above zero in seven of nine cells, the exceptions being Qwen2.5-7B at 10% and 15%. On single-evidence questions only one cell is above zero. Against log-probability gating, the multi-evidence cells range from −0.7 to +1.4 points, except +2.5 [+0.9, +3.6] on Llama at 15% (Table 24).

By release category (not in the paper), the 25% edge is on multi-hop questions: +1.5 to +2.7, with intervals above zero on all three models. On Llama it also appears on temporal questions (+1.4 [+0.3, +2.7]); no open-domain interval is above zero.

Our reading of the mechanism is the paper's. A single-evidence question mostly fails by retrieval-type amnesia: the one fact is resident or not, which a per-step certificate does not see. A multi-evidence answer is reconstructed from several partly evicted blocks, and that distortion is what the certificate measures. The effect is real and small (up to 2.5 points), and we report it as such.

AuthorsOpenReview ↗

(2/2): Q2 sensitivity to the certainty layer and floor (E-B); Q3 does the summary localize (E-A)

Q2. Sensitivity of coverage and ranking to the certainty layer and the floor. In the paper, Table 15 forced the certainty layer to 25 / 50 / 75% (Poisson and gated accuracy), and Table 6 varied δ, the probed steps and the head count; Table 6 shows the operating point moving while the ranking changes little. Theorem 2 does not involve the score, so the layer and the floor change the width (and B of Assumption 2), not the validity.

E-B tests this on three models (instruct checkpoints), coupled draws, 4,032–4,608 units per configuration (Table 28). The grid crosses:

  • certainty shares {adaptive, >=25, >=50, >=75% of the free budget};
  • floors {1e-6, 1e-3, 1e-2, 5e-2};
  • budgets {25%, 12.5%}.
modelbudgetcoverage, min–max over the 16 configurationsSpearmanmedian radius: adaptive / forced 75% layer / floor 0.05
Qwen2.5-1.5B25%0.962–0.9720.95–0.970.093 / 0.100 / 0.101
Qwen2.5-1.5B12.5%0.945–0.9700.93–0.940.248 / 0.287 / 0.310
Qwen2.5-7B25%0.978–0.9900.97–0.980.112 / 0.123 / 0.120
Qwen2.5-7B12.5%0.967–0.9810.96–0.970.282 / 0.337 / 0.358
Llama-3.1-8B25%0.992–0.9950.980.116 / 0.136 / 0.121
Llama-3.1-8B12.5%0.985–0.9930.96–0.970.288 / 0.357 / 0.333

Coverage and ranking hold.

  • Coverage moves by at most 2.5 points within a cell and stays above the nominal 0.9 everywhere.
  • The lowest coverage is 0.945, on Qwen2.5-1.5B at 12.5% with a 75% layer and floor 0.05. That is one of three configurations, one per model, where the floor alone overruns the budget; here it does so by 14%.
  • Spearman moves by at most 0.02.

Only the width moves.

  • From the adaptive layer to a forced 75% layer the width grows by 7–24%, and the realized error moves with it (radius-to-error ratio 3.2–3.5 throughout, from the replay records).
  • The floor matters mainly at 0.05: +4 to +27% with the adaptive layer, up to +39% with a forced 50% layer, and at most 4% at 0.01.
  • Forcing 25% changes almost nothing, because with the 20 protected positions the certainty layer already holds 37–47% of the retained tokens. Forcing 50% widens the median radius by at most 4% at the default floor.

The Chebyshev plug-in radius covers 0.935–0.994 of the units in all 96 configurations. These are width parameters, as Theorem 2 says: coverage and ranking change little with them.

Q3. Does the evicted-set summary also localize? We built two block summaries, both stored at eviction time and scored by the same decode queries as the certificate:

  • the block form of the summary: count and mean key of the evicted tokens of each 64-token block;
  • the page summary a Quest-style system keeps: the per-dimension min/max of the same keys, with each block scored by the upper bound of the query-key logit over that box.

We scored them on the red flags and on every question of the discussion-period re-run of the Table 13 probe, on the vignette's fifty dialogues (Tables 26–27):

modelbudgetred flagsfact block in top 3, red flags: certificate / mean key / Quest bound / attention massaccuracy at 10% fetched, all questions: certificate / mean key / bound / mass / random / oracle
Qwen2.5-7B25%1010.84 / 0.18 / 0.55 / 0.220.74 / 0.26 / 0.44 / 0.58 / 0.26 / 0.94
Llama-3.1-8B25%570.98 / 0.61 / 0.54 / 0.770.79 / 0.53 / 0.53 / 0.69 / 0.31 / 0.95
Qwen2.5-7B15%1880.50 / 0.21 / 0.43 / 0.140.50 / 0.28 / 0.41 / 0.34 / 0.23 / 0.90
Llama-3.1-8B15%1850.56 / 0.39 / 0.42 / 0.310.56 / 0.34 / 0.44 / 0.46 / 0.28 / 0.94

Neither summary localizes as the certificate does:

  • The mean key tracks how much attention mass has left, which is why it predicts induced failures. But the single key a question needs is averaged into its block (exp(q·k_bar) <= mean of exp(q·k)).
  • The bound keeps that key's coordinates, but it is loose over a 64-token box. It stays 9–30 points behind at the same volume and closes part of the gap only at 15%. On Llama at 25% it places the fact block in the top three less often than the mean key (0.54 against 0.61).
  • Both summaries need per-block storage at eviction time; the certificate does not.

Attention mass recovers much of the accuracy on Llama while ranking the fact block less sharply. Contributions 3 and 4 therefore stand as written: the summary predicts, and the variance weighting localizes.

We hope these three answers, and the revision that carries them, address the concern about the payoff. We would be glad to answer anything that remains open, and grateful if you would reconsider the assessment.

Dear Reviewer aDBj,

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). Q1 is answered by Table 24, Q2 by Table 28, and Q3 by Tables 26–27. The discussion closes on November 18 (AoE); if any point remains open, we would be glad to answer it before then.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.