# Risk-Controlled KV-Cache Eviction: From Memory Budgets to Risk Targets

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving.
- Builds on 18 of its 26 references that are in the map.
- First posted on arXiv 23 Sep 2026.

## Placed in

- Efficient LLM inference and serving / [KV cache optimization](https://mlsanity.com/inference/kv-cache-optimization/)

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

- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (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)
- [PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funneling](https://mlsanity.com/paper/2406.02069/) (2024)
- [Distribution-Free, Risk-Controlling Prediction Sets](https://mlsanity.com/paper/2101.02703/) (2021)
- [Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control](https://mlsanity.com/paper/2110.01052/) (2021)
- [Ada-KV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference](https://mlsanity.com/paper/2407.11550/) (2024)
- [DynamicKV: Task-Aware Adaptive KV Cache Compression for Long Context LLMs](https://mlsanity.com/paper/2412.14838/) (2024)
- [Fast yet Safe: Early-Exiting with Risk Control](https://mlsanity.com/paper/2405.20915/) (2024)
- [The Pitfalls of KV Cache Compression](https://mlsanity.com/paper/2510.00231/) (2025)
- [Quantile Risk Control: A Flexible Framework for Bounding the Probability of High-Loss Predictions](https://mlsanity.com/paper/2212.13629/) (2022)
- [Taming the Fragility of KV Cache Eviction in LLM Inference](https://mlsanity.com/paper/2510.13334/) (2025)
- [Controlling the Risk of Corrupted Contexts for Language Models via Early-Exiting](https://mlsanity.com/paper/2510.02480/) (2025)
- [WitCert: Sound Runtime Risk Observability and Gating for KV-Cache Quantization](https://mlsanity.com/paper/2607.28699/) (2026)
- [CompilerKV: Risk-Adaptive KV Compression via Offline Experience Compilation](https://mlsanity.com/paper/2602.08686/) (2026)
- [Error Certificates for KV-Cache Eviction via Randomized Design](https://mlsanity.com/paper/2607.21475/) (2026)
- [ReFreeKV: Towards Threshold-Free KV Cache Compression](https://mlsanity.com/paper/2502.16886/) (2025)

## Abstract (arXiv)

KV-cache eviction is typically evaluated through average quality-memory trade-offs, yet a small average loss can hide requests whose utility degrades materially. We reformulate eviction as a deployment risk-control problem: a material degradation occurs when eviction lowers task utility by more than a deployment-specified tolerance relative to full-KV inference on the same request, and deployment risk is the population frequency of such events. Given a reliability contract specifying a target risk level and confidence requirement, we use a compressor-agnostic post-hoc certification procedure to select a retention policy from calibration data with a finite-sample guarantee, falling back to full KV when no compressed policy is certified. Across multiple eviction methods, Llama and Mistral models, and LongBench and RULER-32K, the same contract supports substantially different levels of eviction: on Llama, it certifies SnapKV at 75% retention on LongBench but no tested compressed policy on RULER-32K, triggering full-KV fallback. Policies with empirical degradation rates below the 5% target can still fail finite-sample certification; on Llama LongBench, empirical thresholding selects uncertified policies that retain 5-10 percentage points less cache across fixed-budget methods. The proposed framework converts a deployment-level reliability requirement into a KV-memory operating point.