# Error Certificates for KV-Cache Eviction via Randomized Design

arXiv: https://arxiv.org/abs/2607.21475 · HTML: https://mlsanity.com/paper/2607.21475/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 39 references that are in the map.
- First posted on arXiv 23 Jul 2026.

## Builds on (most cited first, 25 of 25)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [A Baseline for Detecting Misclassified and Out-of-Distribution Examples in Neural Networks](https://mlsanity.com/paper/1610.02136/) (2016)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [SnapKV: LLM Knows What You are Looking for Before Generation](https://mlsanity.com/paper/2404.14469/) (2024)
- [Selective Classification for Deep Neural Networks](https://mlsanity.com/paper/1705.08500/) (2017)
- [Evaluating Very Long-Term Conversational Memory of LLM Agents](https://mlsanity.com/paper/2402.17753/) (2024)
- [Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference](https://mlsanity.com/paper/2406.10774/) (2024)
- [PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funneling](https://mlsanity.com/paper/2406.02069/) (2024)
- [Ada-KV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference](https://mlsanity.com/paper/2407.11550/) (2024)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Estimating means of bounded random variables by betting](https://mlsanity.com/paper/2010.09686/) (2020)
- [Game-theoretic statistics and safe anytime-valid inference](https://mlsanity.com/paper/2210.01948/) (2022)
- [Transformers are Multi-State RNNs](https://mlsanity.com/paper/2401.06104/) (2024)
- [MagicPIG: LSH Sampling for Efficient LLM Generation](https://mlsanity.com/paper/2410.16179/) (2024)
- [CAOTE: KV Cache Selection for LLMs via Attention Output Error-Based Token Eviction](https://mlsanity.com/paper/2504.14051/) (2025)
- [Value-Aware Stochastic KV Cache Eviction for Reasoning Models](https://mlsanity.com/paper/2606.03928/) (2026)
- [vAttention: Verified Sparse Attention](https://mlsanity.com/paper/2510.05688/) (2025)
- [MomentKV: Closing the Directional Gap in KV Cache Eviction for Long-Context Inference](https://mlsanity.com/paper/2606.01563/) (2026)
- [When Does Value-Aware KV Eviction Help? A Fixed-Contract Diagnostic for Non-Monotone Cache Compression](https://mlsanity.com/paper/2605.08234/) (2026)
- [Generalized friendship paradox in complex networks: The case of scientific collaboration](https://mlsanity.com/paper/1401.1458/) (2014)
- [Forget Without Compromise: Nexus Sampling for Streaming KV-Cache Eviction Under Fixed Budgets](https://mlsanity.com/paper/2606.23961/) (2026)

## Built on by (most cited first, 2 of 2)

- [Risk-Controlled KV-Cache Eviction: From Memory Budgets to Risk Targets](https://mlsanity.com/paper/2609.27981/) (2026)
- [CORE: COverage CAlibration and Evicted-Mass REdistribution for KV Cache](https://mlsanity.com/paper/2610.02235/) (2026)

## Abstract (arXiv)

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. On a thirty-turn assistant compressed to a 10% cache budget, the certificate-gated system answers 0.97 of recall questions against 0.09 for top-k, and for facts stated 26 to 30 turns earlier it recalls 97% against 2%. We prove that no estimator computable from the information a deterministic scheme retains is consistent for its own eviction error: evicted values can be altered so that everything retained is unchanged while the true attention-output error grows without bound. Under the Poisson design the certificate covers the realized attention error in 96.9--97.7% of 12,096 replay cells and in 98.1--99.7% on twelve further architectures. Randomization buys attribution, not prediction: a pre-registered study on LongBench at 6k and 16k tokens (about 74,000 generations) finds question-aware eviction at 25--50% budgets nearly free and output log-probability the better failure predictor, while the certificate answers the question confidence cannot, separating eviction-induced from inherent failures at AUC 0.65--0.75 against 0.47--0.54, and schedules recomputation at 1.7--1.8 times the gain of random gating. On real long-term conversations the gated system returns the full-cache score inside the heavy-damage regime, and the rule that triggers it is the same across five model families.