From Memory Budgets to Risk Targets — Risk-controlled KV cache eviction — What does it mean?
The news. On September 23, 2026, researchers at Korea University posted Risk-Controlled KV-Cache Eviction: From Memory Budgets to Risk Targets on arXiv. They wrap existing eviction methods (SnapKV, AdaKV, DefensiveKV, Layer-DefensiveKV and the request-adaptive ReFreeKV) in a statistical test. They evaluate Llama-3.1-8B and Mistral-7B on the LongBench long-context benchmark, and Llama-3.1-8B on the RULER-32K stress test. The same reliability target allowed very different eviction levels depending on the method, the model and the workload. Read the paper →
Picture a bottle factory that wants to save plastic. Thinner walls are cheaper, but the factory does not ask how strong the average bottle is; it asks how many bottles crack when a customer drops one. Risk-controlled eviction asks the same question of the KV cache: not "how good is the average answer?" but "how often does dropping cache entries break an answer?" The KV cache holds a key and a value vector for every processed token, so on long contexts it fills GPU memory quickly. Eviction methods keep only a chosen share of those entries, the retention ratio, and discard the rest — the same trade-off a server faces when it evicts cached prefixes to make room.
The paper defines one bad event precisely. Each calibration request is run twice with the same model and greedy decoding (no random sampling, so any score change comes from the eviction): once with the full cache and once with the compressed cache. If the normalized task score drops by more than τ = 0.10, that request is a material degradation — one cracked bottle. A policy can have a small average score drop and still crack too many bottles, because a few large drops are averaged away by many requests that barely change. It is the same lesson as tail latency: the mean hides the users with the worst experience. The contract is written like an SLO: at most ε = 5% of requests may degrade materially, and the check may be wrong at most δ = 5% of the time.
Remove earliest tokens first
Now the factory's test procedure. It cannot drop every bottle it will ever make, so it drop-tests one batch and leaves a margin for bad luck in that batch. With 1,200 calibration requests, a 5% target would naively allow 60 failures, but the binomial test certifies a policy only with 47 or fewer (3.92%) — the gap of 13 is the price of judging from a finite sample. The candidate policies are fixed in advance and tested in order from thick to thin: 80% retention, then 75%, then 70%, down to 20%. Testing stops at the first policy that fails, the last passing policy is used, and if even the first candidate fails, the system keeps the full cache. Within one pre-specified sequence (one model, one eviction method, one benchmark), this fixed-sequence testing keeps the chance of any false certification at δ without a separate correction for every candidate, and it does not assume that thinner is always worse. The guarantee holds for each sequence separately, not for all of them at once. The wrapper never changes the eviction method itself: SnapKV still decides which tokens to drop, and the wrapper only decides how many.
A worked example from the paper, holding three things fixed: Llama-3.1-8B, the LongBench tasks, and the contract (τ = 0.10, ε = 5%, δ = 5%, 1,200 calibration requests). SnapKV at 75% retention has 3.50% material degradations — 42 of 1,200, under the cap of 47 — so it passes. At 70% retention it has 50 of 1,200 (4.17%). That is below the nominal 5%, so a plain "is the observed rate under 5%?" rule would accept it, but 50 is above 47, so certification stops. The certified choice is 75% retention; across the four Llama compressors, certification kept 5 to 10 percentage points more cache than the plain rule. The paper's held-out check shows what the margin buys. For Layer-DefensiveKV on the same model, the plain rule picks 30% retention, which then produced 64 of 1,200 (5.33%) material degradations on fresh test requests; the certified 35% produced 48 of 1,200 (4.00%). The authors note that this single comparison is not by itself a statistically significant difference.
| Method (Llama-3.1-8B, LongBench) | Certified retention | Calibration risk | Held-out test risk | Source |
|---|---|---|---|---|
| SnapKV | 75% | 3.50% | 2.50% | Table 1 |
| AdaKV | 65% | 3.33% | 3.08% | Table 1 |
| DefensiveKV | 40% | 3.67% | 4.08% | Table 1 |
| Layer-DefensiveKV | 35% | 3.58% | 4.00% | Table 1 |
The same contract gives different answers on a different workload, and that is the point of stating the contract instead of a fixed budget. On the RULER-32K stress test with Llama, SnapKV's first candidate (80% retention) had 135 of 1,300 (10.38%) material degradations, so the procedure fell back to the full cache, while Layer-DefensiveKV still passed at 35% retention. The guarantee also has clear limits. It covers the declared mix of tasks, not each task: on RULER-32K the held-out risk for Layer-DefensiveKV was concentrated in one task, common-word extraction, at 29%. It assumes calibration requests look like production traffic, it measures quality relative to the full cache rather than absolute quality, and the paper does not measure latency or throughput. In factory terms, a certificate for today's bottle shape says nothing about a new shape — when the traffic mix changes, the calibration has to be run again, much like an eval-driven rollout re-checks a model before it takes more traffic.
Goes deeper in: LLM Internals → KV Cache → Memory Cost
Related explainers
- InfoKV: entropy-aware KV-cache compression — a scoring policy that decides which entries to keep; this wrapper could certify how many.
- AnchorKV: safety-aware KV compression — another case where average quality misses a specific failure class.
- Quantized retrieval: a per-query score-gap certificate — the same "aggregate accuracy hides per-item damage" problem, solved for retrieval.