Randomized KV-Cache Eviction Enables Verifiable Error Certificates

Deterministic top-k KV-cache eviction — standard practice for efficient LLM serving — has a fundamental blind spot: evicted values can be adversarially chosen so that everything the system retains looks unchanged while true attention-output error grows without bound. This paper proves that no serving-time error estimator can be consistent under deterministic eviction, closing off a whole class of post-hoc accuracy checks.

The fix is randomized eviction via Poisson sampling with known inclusion probabilities. A single logit offset applies a Hájek correction inside the softmax, and a survey-sampling variance estimator over the retained tokens yields a per-step error certificate achieving 0.97 empirical coverage with no accuracy penalty.

On real workloads, the authors pre-registered seven claims and three failed: question-aware eviction at 25-50% budgets is nearly free, output log-probability outpredicts the certificate for failure detection, and certificate-gated budget escalation adds no benefit. What holds up is attribution — the certificate reliably separates cache-induced errors from inherent model errors (AUC 0.73-0.75 versus 0.47-0.54 for output confidence alone) and improves recomputation scheduling over random or confidence-based triggers. The core takeaway for engineers: randomization in KV-cache management buys you diagnostic attribution, not general failure prediction.