{"id":"e12e2a27-f00d-4907-b5ac-d70552af01a4","arxiv_id":"2607.21475","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Deterministic KV-cache eviction provably cannot self-diagnose its own error; Poisson-sampled eviction with a Hajek logit offset yields an empirically valid error certificate (0.97 coverage) that attributes, but does not predict, failures.","lead":"A new proof shows deterministic KV-cache eviction can never estimate the error it causes, because the evicted values can be changed without altering anything the system still sees. Randomized eviction with known sampling probabilities restores a usable error certificate, which separates cache-caused from model-inherent failures—though it does not predict failure better than output confidence.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Assumption 2's uniform weight bound is not guaranteed by the floor/certainty layer as claimed; since Eq (2)'s pi_i is based on an arbitrary importance score rather than the softmax weight a_i, the bound B/m is unproven and Theorem 2's O(B^2/m^2) remainder is vacuous.","rationale":"The reader's weakest assumption matches my independent reading. The paper's central positive contribution is the design-based variance estimator (Theorem 2) and the certificate built on it. Both rely on Assumption 2 to control the remainder in the Hajek expansion and the range term in the empirical-Bernstein radius. The authors claim the bound is constructive, but the construction (floor epsilon + certainty layer) does not obviously force the normalized ratio a_i/(pi_i sum a_j) to be O(1/m) with an absolute constant. Because pi_i in Eq (2) is a clipped function of an arbitrary importance score while a_i is the softmax weight, the two can be exponentially far apart; the floor gives only a 1/epsilon bound, which is numerically vacuous at epsilon=1e-6. This is not an external disagreement with consensus; it is an internal gap between the theorem's hypothesis and the design's stated guarantee. Theorem 1 appears correct and is independently supported by the permutation experiment. The empirical coverage and pre-registered outcomes are strong evidence for practical value, but they do not substitute for the missing proof of Assumption 2. A simple data audit on released logs can settle whether the bound holds in the deployed system; if it fails, the theorem's statement requires qualification (e.g., B as a data-dependent constant, or a different design where pi is proportional to a_i). Thus the conditional verdict is appropriate: the paper should supply this verification or revise the theorem.","tokens_in":20393,"tokens_out":6372,"duration_ms":58805,"concrete_test":"Take a random sample of 2,000 decode steps from the released logs of the 16k LongBench Poisson runs. For each step, compute the actual tail softmax weights a_i, the pi_i from Eq (2) with epsilon=1e-6, and the ratio R = max_i a_i/(pi_i sum_j a_j). Regress log(R) on log(m) and n_tail. If R*m is not bounded by a constant (e.g., exceeds 1000 or grows with n_tail), Assumption 2 fails for the deployed configuration, and the O(B^2/m^2) remainder is not small. Additionally, recompute bV_t and the certificate coverage after replacing pi_i with pi_i proportional to a_i on the tail (the case where Assumption 2 is plausible); if coverage remains near 0.97, the practical result is robust, but if it changes materially, the design's validity is sensitive to the score-weight mismatch.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 2 and the deployed certificate's variance/range terms rest on Assumption 2: a_i/(pi_i sum_j a_j) <= B/m for all tail tokens. The text asserts this is 'guaranteed constructively by the floor epsilon and the certainty layer.' This does not follow. The floor epsilon only gives pi_i >= epsilon, so the trivial bound is <= a_i/(epsilon sum a_j) <= 1/epsilon; with epsilon=1e-6 this is B/m <= 1e6 (B <= 1e6*m), making the remainder O(B^2/m^2) enormous. The certainty layer removes high-score tokens from the tail, but the softmax weights a_i = exp(s_i) are exponentially sensitive to the logits s_i, while pi_i is clipped proportional to an arbitrary score_i (Eq 2). For a tail token with a large softmax weight but a small score_i (or vice versa), the ratio is not controlled by any construction. The proof in Appendix A.1 explicitly requires a uniform bound to claim bN/N = 1+O(B/m) and the O(B^2/m^2) remainder. Without an independent argument that B is an absolute constant (e.g., that the certainty layer truncates the tail so that max a_i/sum a_j <= c/m for a known c), the unbiasedness statement is incomplete. This is load-bearing because the paper's central positive result — that a randomized design yields an unbiased variance estimator and hence a certificate — depends on it. The empirical coverage may still hold, but the theoretical claim as stated is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies whether KV-cache eviction can estimate its own induced attention-output error at serving time. It proves a negative result for deterministic top-k eviction: no estimator measurable from the retained information can be uniformly consistent. It then proposes a randomized Poisson-tail design with known inclusion probabilities and a single logit offset implementing a Hajek correction, and derives a Sen-Yates-Grundy-style variance estimator over the retained set (Theorem 2), which is used to build an empirical-Bernstein certificate. Extensive pre-registered experiments on LongBench and synthetic tasks evaluate the certificate as a failure predictor and as an attribution/scheduling signal, with several claims deliberately killed. The paper honestly distinguishes theoretical guarantees from empirically validated behavior.","tokens_in":20797,"tokens_out":8880,"duration_ms":85106,"significance":"The negative result (Theorem 1) is clean and conceptually important: deterministic evictors cannot self-diagnose their induced error. The proposed randomized design is elegant, cheap, and supported by an unusually credible empirical study: pre-registered claims with kill conditions, per-run logs, released scripts, and explicit reporting of what failed. If Assumption 2 can be properly justified, or the design adjusted so that it holds, the certificate would be a valuable new capability for streaming compression. As it stands, the theoretical guarantee behind the positive result is incomplete, but the gap is local and fixable.","major_comments":[{"comment":"The assertion that a_i/(pi_i * sum_j a_j) <= B/m is 'guaranteed constructively by the floor epsilon and the certainty layer' is not established. From Eq (2), pi_i is a clipped version of m * score_i / sum_j score_j, whereas a_i = exp(s_i). The floor only gives pi_i >= epsilon, so the stated bound would require B >= m/epsilon (with epsilon = 1e-6, B >= 1e6 * m); such a B is not the constant implied by the O(B^2/m^2) remainder. The certainty layer removes high-softmax-weight tokens from the tail, but the ratio a_i/score_i for a tail token with small score, or with a_i large relative to score_i, is unconstrained. This is load-bearing: Theorem 2 and the range term in Eq (4) both depend on the uniform bound. Please either prove Assumption 2 from the design (e.g., choose pi_i proportional to a_i on the tail) or replace it with an explicit, verifiable condition.","section":"Section 3.3, Assumption 2"},{"comment":"The proof asserts that 'each summand contributes at most B/m after normalization' and uses this to conclude bN/N = 1 + O_p(B/m) and a final O(B^2/m^2) remainder. If B is as large as m/epsilon, the first-order term is O(1/epsilon) and the remainder is O(1/epsilon^2), so the asymptotic statement is vacuous; if B is meant to be an absolute constant independent of m, that needs to be stated and proved. The unbiasedness claim E[bV_t] = Var(e_lin^t) + O(B^2/m^2) is therefore not established as written. This directly affects the certificate radius (4), whose variance term is bV_t and whose range term has the same B-dependence.","section":"Appendix A.1, proof of Theorem 2"}],"minor_comments":[{"comment":"Equation (2) uses 'score_i' while Eq. (1) defines s_i and a_i = exp(s_i). Clarify whether score_i is the same as s_i or an arbitrary importance score; this matters for interpreting Assumption 2 and for replicating the experiments.","section":"Eqs. (1)-(2)"},{"comment":"The proof assumes S != C ('whenever eviction occurs'). Add this condition explicitly to the theorem statement, or state that the result is vacuous when the full cache is retained.","section":"Theorem 1"},{"comment":"The reproducibility section says logs and scripts are 'packaged for release'; for a claims-based paper, a repository URL or supplement link would strengthen verifiability.","section":"Reproducibility"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this paper is worth reading and worth refereeing, but the main theoretical certificate is not fully established as written.\n\nThe genuinely new piece is Theorem 1: deterministic, value-blind eviction cannot consistently estimate its own induced error, because the evicted values are unconstrained given the retained set. The proof is two lines and it is correct; extending it to value-aware scores via rotations is a nice touch. That alone is a contribution.\n\nThe positive construction is also interesting. Poisson-sampled tail with known inclusion probabilities, a one-logit Hajek correction, and a Sen-Yates-Grundy variance estimator computed from the retained set is a clean idea. The empirical coverage numbers (96.9-97.7%) and the correlation with true error are strong, and the pre-registered study is unusually honest: three of seven claims die, and the paper concedes that output log-probability beats the certificate at predicting failure. The attribution result, separating eviction-induced from inherent failures, is the real practical payoff and it is well supported. The paper also reports its measured 2x overhead rather than the asymptotic promise.\n\nThe soft spot is Assumption 2. The text says the bound a_i/(pi_i sum a_j) <= B/m is 'guaranteed constructively' by the floor epsilon and the certainty layer. That does not follow. The floor only gives pi_i >= epsilon, which yields a bound on the order of 1/epsilon, not a constant B independent of m. The certainty layer absorbs the head of the importance-score distribution, but pi_i in Eq (2) is proportional to that importance score, while a_i is the softmax weight from the current query-key logits. Nothing in the construction controls the ratio between the two. So the O(B^2/m^2) remainder in Theorem 2 is vacuous as stated, and the proof in Appendix A.1 explicitly depends on that bound. This is fixable: either prove the bound under an explicit condition (e.g., pi_i proportional to a_i, or a tail truncation that controls max a_i / sum a_j), or downgrade Theorem 2 to a conditional statement supported by the empirical coverage. As it stands, the unbiasedness claim is not established.\n\nEverything else is in proportion. The anytime extension is honestly labeled a sketch, the limitations section is substantive, and the reproducibility package is promised. This deserves a serious referee; the right outcome is conditional acceptance after the authors tighten Assumption 2 or the theorem statement. I'd bring it to a reading group.","headline":"Novel impossibility theorem and an honest, well-executed empirical study; but Theorem 2 rests on an unproven uniform weight bound that needs fixing.","tokens_in":21295,"tokens_out":2735,"would_cite":true,"duration_ms":27468,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Deterministic top-k KV-cache eviction is provably unable to diagnose the error it causes; randomized eviction restores a per-step error certificate.","keywords":["KV-cache eviction","error certificate","randomized design","Poisson sampling","Hajek correction","Sen-Yates-Grundy","silent failure","attribution"],"falsifier":"Compute the ratio a_i/(pi_i * sum_j a_j) for tail tokens in a real model using the paper's probability formula. If the ratio is not uniformly bounded in practice, run the replay cells where an unbounded token is retained and check whether the certificate covers the realized error at near-nominal rates; a persistent deficit would falsify the design-based guarantee. Separately, a powered study finding a deterministic self-signal that predicts its own eviction-induced failures substantially above chance on natural data would weaken the practical significance of the impossibility theorem.","tokens_in":20255,"feed_emoji":"🎲","tokens_out":4627,"duration_ms":47432,"temperature":0.7,"pith_summary":"Keeping only the top-k KV tokens makes the retained state independent of every evicted value, so a serving system that looks only at what it kept cannot tell how much the deletion changed the answer—even in principle. The paper proves this impossibility for any deterministic value-blind evictor and then shows that randomizing the tail restores the information: if eviction is a Poisson sample with known inclusion probabilities and one logit offset performs the Hajek correction inside the softmax, a survey-sampling variance estimator computed from the retained set alone becomes a per-step error certificate, measured to cover the true attention error about 97% of the time. On real long-context workloads the certificate is not a failure predictor—output confidence beats it at that—but it is the only online signal that separates cache-induced failures from inherently difficult ones, and scheduling recomputation on it beats random or confidence gating. The upshot the paper presses: deterministic eviction is structurally blind to its own damage, and randomization buys attribution, not prediction.","feed_headline":"Randomized KV eviction certifies its own error at 97%","feed_subtitle":"A Poisson-tail cache design yields a per-step error bound that separates cache-induced failures from hard questions.","key_machinery":"The core mechanism is a randomized eviction design: a certainty set with inclusion probability 1, a Poisson-sampled tail with known inclusion probabilities, and a single logit offset per retained tail token that turns the softmax denominator into a Hajek estimator. The variance estimate is the Sen-Yates-Grundy single-sum form, which reduces to a Horvitz-Thompson-style sum over retained tail tokens, and an empirical-Bernstein radius (variance term plus range term) turns it into a per-step certificate. The proof machinery is classical design-based inference: unbiased variance estimation from the retained set without any assumptions on score quality, grounded in a uniform bounded-weight assumpt","core_discovery":"Theorem 1 states that for any deterministic, value-blind eviction mechanism, no estimator measurable with respect to the online information can be consistent for the induced attention-output error: one can perturb all evicted values so that the retained keys, scores, and query history are bit-identical while the true output error grows arbitrarily. The paper then gives the design that restores identifiability: keep a certainty set, evict the tail by independent Bernoulli sampling with algorithm-chosen inclusion probabilities, and add log(1/pi) to the retained logit so the softmax denominator performs a Hajek correction. Theorem 2 shows that the resulting single-sum Sen-Yates-Grundy statistic","pith_inferences":["The same unidentifiability argument likely transfers to other deterministic deletion or selection channels in inference—token pruning, early-exit dropping, context distillation—where the selection decision is independent of the deleted content; a known-randomness design could provide similar certificates there.","A cheaper two-run baseline of independent Poisson draws reaches only 0.62-0.69 attribution AUC against the certificate's 0.73-0.75 from a single draw, suggesting that the certificate's advantage comes from design-based validity rather than extra compute; this predicts that an optimized single threshold on a learned model would not close the gap.","The unablated implementation choices—head and layer subsampling, six-step window, normalizer floor—are natural places to test whether a cheaper certificate retains ranking quality; a single-layer, single-step version is a plausible deployment-ready extension.","The paper's stated but untested prediction that merging-based eviction error scales with within-stratum dispersion of evicted values rather than evicted attention mass is a direct testable extension of its stratified-ratio view, and would bound the certificate's relevance to merging-style methods."],"forward_implications":["Any deterministic top-k serving system that claims a self-diagnostic of eviction damage is making an unsupportable promise: the failure is structural, not a matter of finding a better monitor.","The randomized design costs one scalar logit offset per retained tail token plus O(|tail|) work per head per step, with no retraining, and yields a per-step certificate with measured coverage of 96.9-97.7% at 12.5-50% budgets.","At question-aware budgets of 25-50%, eviction is nearly free, so the damage regime is streaming and agent memory, where history is compressed before future queries arrive.","Mean output log-probability is a stronger predictor of overall failure than any cache-side signal; the certificate's value is attribution, such as deciding whether a failure was caused by the cache or by the model itself.","Certificate-gated recomputation captures about 36% of the oracle's recoverable gain in streaming settings, beating random gating by roughly a factor of 1.7-1.8 and confidence gating, which can fall below random."],"fun_headline_variants":["Randomized eviction gives KV-cache error a 97% certificate","KV-cache error certificate from Poisson-sampled eviction","Randomized KV eviction certifies its own error at 97%","Error certificates for KV-cache eviction via randomization","Randomness in KV eviction yields per-step error bounds"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The per-step certificate's validity rests on the uniform bounded-weight assumption: normalized softmax weights on the tail are bounded by B/m, which the paper says the probability floor and certainty layer guarantee; if the inclusion probabilities are computed from a different importance score than the softmax weight, no such bound follows, and the certificate's remainder and range term may understate the true error.","fun_headline_variants_meta":{"raw":{"variants":["Randomized eviction gives KV-cache error a 97% certificate","KV-cache error certificate from Poisson-sampled eviction","Randomized KV eviction certifies its own error at 97%","Error certificates for KV-cache eviction via randomization","Randomness in KV eviction yields per-step error bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00016,"raw_usage":{"total_tokens":1071,"prompt_tokens":748,"completion_tokens":323,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":492,"completion_tokens_details":{"reasoning_tokens":236}},"tokens_in":492,"tokens_out":323,"duration_ms":4271,"temperature":1.0,"reasoning_tokens":236,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T07:19:18.139810+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the ratio a_i/(pi_i * sum_j a_j) for tail tokens in a real model using the paper's probability formula. If the ratio is not uniformly bounded in practice, run the replay cells where an unbounded token is retained and check whether the certificate covers the realized error at near-nominal rates; a persistent deficit would falsify the design-based guarantee. Separately, a powered study finding a deterministic self-signal that predicts its own eviction-induced failures substantially above chance on natural data would weaken the practical significance of the impossibility theorem.","supporting_citations":[],"review_version":1}