Error Certificates for KV-Cache Eviction via Randomized Design

• URL: http://arxiv.org/abs/2607.21475v2
• Date: Sat, 25 Jul 2026 14:37:35 GMT
• Title: Error Certificates for KV-Cache Eviction via Randomized Design
• Abstract summary: KV-cache eviction keeps the top-$k$ tokens under an importance score and deletes the rest.<n>We prove that this design cannot know what it destroyed.<n>We show that Randomized eviction restores identifiability.
• Score: 3.860898721527665
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Deterministic KV-cache eviction keeps the top-$k$ tokens under an importance score and deletes the rest. We prove that this design cannot know what it destroyed: evicted values can be altered so that everything the serving system retains is unchanged while the true attention-output error grows arbitrarily, so no serving-time estimator of that error is consistent. Randomized eviction restores identifiability. With a Poisson-sampled tail at known inclusion probabilities, one logit offset performs the Hájek correction inside the softmax, and a survey-sampling variance estimator over the retained set becomes a per-step error certificate with 0.97 empirical coverage at no accuracy cost. On real workloads, seven pre-registered claims locate the certificate's value precisely. Prediction goes to output confidence: question-aware eviction at 25--50\% budgets is nearly free, output log-probability predicts failure better than any cache-side signal, and certificate-gated budget escalation adds nothing. Attribution stays with the certificate: it separates cache-induced from inherent failures (AUC 0.65--0.75, against 0.47--0.54 for output confidence) and schedules recomputation better than random or confidence gating. Randomization buys attribution, not prediction.

Related papers

• What Eviction Destroys: A Restore-Counterfactual Audit of Forgetting in Agent Memory [1.6558929815405155]
  We introduce the restore counterfactual, a per-question paired intervention that reinstates the question's gold evidence in the read-time context.<n>We evaluate FIFO, random, redundancy-aware, and LLM-importance eviction on LongMemEval-S at three budgets and under two retrieval regimes.
  arXiv  Detail & Related papers  (2026-09-08T05:48:10Z)
• A Probabilistic Interpretation of KV Cache Eviction [52.196873305708955]
  Cache eviction can achieve higher throughput by evicting some entries from the KV cache.<n>This paper formalizes the problem of KV eviction through the lens of probabilistic reasoning.<n>We show that this probabilistic version of KV eviction coupled with decode time correction is more robust to different tasks.
  arXiv  Detail & Related papers  (2026-08-28T12:57:07Z)
• EDGE: a closed-form directed test for the calibration of probabilistic binary classifiers [0.0]
  We propose EDGE, a calibration test for the canonical probabilistic classifier, logistic regression.<n> EDGE reads the same binned predicted-observed table a reliability diagram plots, and projects its standardized bin residuals onto a small pre-specified basis of smooth calibration-distortion.<n>Across link and feature misspecification the pre-specified default led or tied every rival binned test on the fitted index in 19 of 22 detectable scenarios, and stayed computable where the refit-based Stukel score test separates in 20% to 28% of samples.
  arXiv  Detail & Related papers  (2026-08-20T19:06:05Z)
• $TCP_α$: Margin-Controlled Confidence estimation for reliable Music Information Retrieval [7.679660052685777]
  Deep neural networks are often overconfident, assigning high confidence even to incorrect predictions.<n>Existing targets suffer from inherent ambiguity: they assign overlapping confidence values to correct and incorrect predictions, while errors near the decision boundary receive confidence scores indistinguishable from correct predictions.<n>We propose $ TCP_$, a novel confidence target that resolves these limitations by introducing a margin-controlled penalty for misclassified samples.
  arXiv  Detail & Related papers  (2026-08-20T17:58:50Z)
• SVR: Self-Verifying Refinement via Joint Verdict-Confidence Reinforcement Learning for Adaptive Test-Time Compute [62.3458279176813]
  Self-Verifying Refinement is an oracle-free multi-turn reinforcement learning framework.<n>It learns to use self-verification as a compute-control policy.<n>It achieves a macro-average accuracy of 0.563 with only 2.99 inference turns on average.
  arXiv  Detail & Related papers  (2026-07-30T16:20:58Z)
• CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees [1.7545090618311434]
  Machine-learned predictions can speed up offline NP-hard optimization, but asking a predictor what to do amounts to asking it to solve the problem.<n> CASP (Certificate-Augmented Solution Pruning) instead asks which parts of the search space may be ignored, and accepts each answer only after a sound-time verifier has checked it.<n>With trained predictors, unverified pruning loses up to $26%$ of the optimum under distribution shift, while the verified deployment of the same predictions loses nothing.
  arXiv  Detail & Related papers  (2026-07-16T04:02:15Z)
• Think Again or Think Longer? Selective Verification for Budget-Aware Reasoning [15.231928045776293]
  sevra is a serving-layer controller that decides whether to preserve a frozen solver's initial answer or invoke active verification.<n>On mathfive, selective verification reaches 76.3% accuracy, compared with 75.5% for always verifying.<n>On CommonsenseQA, always-on verification hurts, while Self-Consistency@5 improves accuracy about five times the realized token cost.
  arXiv  Detail & Related papers  (2026-06-18T05:25:43Z)
• Re-feeding Is Not Replaying: Measuring Replay Noise in Counterfactual Token-Credit Estimation [0.0]
  Per-token counterfactual credit estimation asks which token in a language-model rollout caused the final answer to be right or wrong.<n>We measure what that assumption costs on a stock inference engine, with a three-pass design.<n>Across six configurations and three models, re-feeding changes the credit estimate at rates 14-28 percentage points above the replica floor.
  arXiv  Detail & Related papers  (2026-06-14T06:09:16Z)
• Causal Label Recovery in Payment Networks [0.0]
  Fraud detection models in payment networks train on chargeback labels that are systematically biased.<n>A companion paper [arXiv05:26.27557] proved that these four impairments impose a minimax lower bound on detection performance.<n>We formalize the observation pipeline as a sequential missing-data problem with three stages and a corruption layer, and construct the Sequential Triply Robust estimator.
  arXiv  Detail & Related papers  (2026-05-28T02:43:34Z)
• COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees [51.5976496056012]
  COIN is an uncertainty-guarding selection framework that calibrates statistically valid thresholds to filter a single generated answer per question.<n>COIN estimates the empirical error rate on a calibration set and applies confidence interval methods to establish a high-probability upper bound on the true error rate.<n>We demonstrate COIN's robustness in risk control, strong test-time power in retaining admissible answers, and predictive efficiency under limited calibration data.
  arXiv  Detail & Related papers  (2025-06-25T07:04:49Z)
• Robust Conformal Prediction with a Single Binary Certificate [58.450154976190795]
  Conformal prediction (CP) converts any model's output to prediction sets with a guarantee to cover the true label with (adjustable) high probability.<n>We propose a robust conformal prediction that produces smaller sets even with significantly lower MC samples.
  arXiv  Detail & Related papers  (2025-03-07T08:41:53Z)
• Robust Yet Efficient Conformal Prediction Sets [53.78604391939934]
  Conformal prediction (CP) can convert any model's output into prediction sets guaranteed to include the true label. We derive provably robust sets by bounding the worst-case change in conformity scores.
  arXiv  Detail & Related papers  (2024-07-12T10:59:44Z)
• Beyond calibration: estimating the grouping loss of modern neural networks [68.8204255655161]
  Proper scoring rule theory shows that given the calibration loss, the missing piece to characterize individual errors is the grouping loss. We show that modern neural network architectures in vision and NLP exhibit grouping loss, notably in distribution shifts settings.
  arXiv  Detail & Related papers  (2022-10-28T07:04:20Z)
• Getting a-Round Guarantees: Floating-Point Attacks on Certified Robustness [19.380453459873298]
  Adversarial examples pose a security risk as they can alter decisions of a machine learning classifier through slight input perturbations. We show that these guarantees can be invalidated due to limitations of floating-point representation that cause rounding errors. We show that the attack can be carried out against linear classifiers that have exact certifiable guarantees and against neural networks that have conservative certifications.
  arXiv  Detail & Related papers  (2022-05-20T13:07:36Z)
• Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations [78.23408201652984]
  Top-k predictions are used in many real-world applications such as machine learning as a service, recommender systems, and web searches. Our work is based on randomized smoothing, which builds a provably robust classifier via randomizing an input. For instance, our method can build a classifier that achieves a certified top-3 accuracy of 69.2% on ImageNet when an attacker can arbitrarily perturb 5 pixels of a testing image.
  arXiv  Detail & Related papers  (2020-11-15T21:34:44Z)
• Certifying Confidence via Randomized Smoothing [151.67113334248464]
  Randomized smoothing has been shown to provide good certified-robustness guarantees for high-dimensional classification problems. Most smoothing methods do not give us any information about the confidence with which the underlying classifier makes a prediction. We propose a method to generate certified radii for the prediction confidence of the smoothed classifier.
  arXiv  Detail & Related papers  (2020-09-17T04:37:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.