Error Certificates for KV-Cache Eviction via Randomized Design

Randomized KV-cache eviction enables error certificates with provable coverage

A new arXiv paper proves that deterministic KV-cache eviction is fundamentally unidentifiable: evicted values can be manipulated so that retained state is unchanged while true attention-output error grows arbitrarily, making any serving-time error estimator inconsistent. The authors show that Poisson-sampled randomized eviction restores identifiability, enabling a Hájek-corrected survey-sampling variance estimator that serves as a per-step error certificate with 0.97 empirical coverage. Pre-registered experiments on real workloads show the certificate is most useful for attribution—separating cache-induced from inherent failures (AUC 0.73–0.75 vs. 0.47–0.54 for output confidence)—and for scheduling recomputation, though it does not improve predictive gating.