Randomized KV-Cache Eviction Guarantees Error Bounds, Deterministic Fails
Deterministic KV‑cache eviction, which simply keeps the top‑k tokens, can hide arbitrarily large attention errors. The authors introduce a Poisson‑sampled randomized eviction that yields per‑step error certificates with 97 % empirical coverage and no loss in output quality. This makes inference caching safer for production LLM services.