Error Certificates for KV-Cache Eviction via Randomized Design

Deterministic KV-cache eviction keeps the top-$k$ 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.