Error Certificates for KV-Cache Eviction via Randomized Design

Peng Xie of the Technical University of Munich argues that deterministic KV-cache eviction, including top-k strategies such as H2O and SnapKV, cannot reliably estimate the attention error caused by deleting tokens: unseen evicted values can change arbitrarily while every retained statistic remains identical. The proposed remedy is certainty-plus-Poisson tail sampling with known inclusion probabilities, a Hájek correction implemented as the logit offset log(1/πi), and a retained-set Sen–Yates–Grundy variance estimator converted into an empirical-Bernstein error certificate; it requires no training or new matrices and supports an e-process extension for trajectory-wide monitoring. In offline replays of Qwen2.5-1.5B, certificate coverage reached 96.9% at the 12.5% budget, while certificate-to-attention-error Spearman correlation reached 0.943. Across four models—Qwen2.5-1.5B and 7B, Llama-3.1-8B, and Mistral-7B-v0.3—on four RULER-style tasks, certificate–failure AUC was positive in 16 of 16 cells, with mean 0.836. The real-world LongBench study is more restrained: failure prediction AUC was only 0.555 at 6k contexts and 0.572 at 16k, losing to mean output log-probability. The certificate’s practical advantage is attribution rather than prediction: among failures, it separated cache-induced from inherent errors with AUC 0.749 at 6k and 0.727 at 16k, outperforming confidence signals and improving recomputation scheduling. Randomization therefore makes compression damage identifiable, but it does not reveal whether the model will fail overall.