Error Certificates for KV-Cache Eviction via Randomized Design

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.