Risk-Controlled KV-Cache Eviction: From Memory Budgets to Risk Targets
Beomgu Kang, SoJin Yun, Hojoon Kim, Hyunseok Seo
cs.CL · cs.LG
Quick verdict
Careful LTT-based risk control for KV eviction; statistically sound, but the guarantee rests on a chosen task-mix population and a relative utility metric.
Summary
The paper reformulates KV-cache eviction as a deployment risk-control problem. Rather than fixing a memory budget and reporting average quality loss, it defines material degradation as a request-level utility drop exceeding a tolerance τ (default 0.10) relative to full-KV inference on the same request, and controls the population frequency ε (default 5%) of such events. Building on Learn-then-Test with fixed-sequence testing over a pre-specified conservative-to-aggressive retention grid, a task-stratified calibration set (n=1200 LongBench; n=1300 RULER-32K) certifies the most aggressive policy with a finite-sample guarantee (δ=0.05), falling back to full KV when nothing certifies. Across SnapKV, AdaKV, DefensiveKV, and Layer-DefensiveKV on Llama-3.1-8B and Mistral-7B, certified retention varies widely under the identical contract (Llama LongBench: SnapKV 0.75 versus Layer-DefensiveKV 0.35); on Llama RULER-32K, SnapKV fails already at retention 0.80, triggering full-KV fallback. Empirical thresholding would select 5–10 percentage points less retention while failing certification. The request-adaptive ReFreeKV calibrates to a threshold retaining 87.4% on average. Held-out rates mostly stay below 5%, but per-task risks reach 29% on RULER common-word extraction. Limitations: the guarantee covers only a declared task-uniform mixture, degradation is relative to full-KV (253/1200 test requests have zero full-KV utility), grids are coarse, only two 7–8B models are tested, and no code or latency measurements are reported.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Mean eviction-induced degradation does not bound the frequency of large per-request losses: configurations with similar average loss differ materially in P[Δπ(X) > 0.10] (Fig. 1).
- Fixed-sequence Learn-then-Test over a pre-specified retention grid provides a compressor-agnostic finite-sample certificate Pr{Rτ(π̂) > ε} ≤ δ with full-KV fallback, without modifying the compressor or assuming monotone risk.
- Under the same contract (τ,ε,δ)=(.10,.05,.05), certified retention varies substantially across methods and benchmarks: on Llama, SnapKV is certified at 0.75 on LongBench but no compressed policy certifies on RULER-32K.
- Policies whose empirical calibration risk is below the 5% target can fail finite-sample certification; empirical thresholding selects policies retaining 5–10 percentage points less cache on Llama LongBench.
- Mixture-level certification can conceal task-specific population risks exceeding ε, e.g., 29% on RULER common-word extraction for Layer-DefensiveKV.
Strengths
Well-posed reformulation with a deployment-relevant target
The mean-vs-exceedance distinction (Eq. 1–2, Fig. 1) is the right framing: risk is defined against paired full-KV inference on the same request (Eq. 3–5), removing budget/sampling confounds, and the contract (τ, ε, δ) is made explicit as a deployment knob.
Statistically rigorous certification machinery
Conservative null including equality, valid p-values via Hoeffding's comparison theorem under unequal per-task violation probabilities (Eq. 13–14), fixed-sequence testing controlling FWER at δ=0.05 with arbitrary p-value dependence, and explicit certifiable cutoffs (Kmax=47/1200 = 3.92%; Kmax=51/1300).
Unusual transparency about scope of guarantees
Actionable quantification of finite-sample honesty cost
Heterogeneity analysis that goes beyond the mixture certificate
Weaknesses
Certificate applies only to a declared task-uniform mixture
Relative-to-full-KV metric has floor effects and mixed semantics
Coarse grids plus stop-at-first-failure rule
Fragmented protocols weaken adaptive-vs-fixed comparison
No code release and narrow model scope
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper converts a deployment reliability requirement into a KV-memory operating point. Instead of fixing a memory budget and reporting average quality–memory trade-offs, it asks: given a tolerance τ on per-request utility loss relative to paired full-KV inference and an allowed exceedance frequency ε, which pre-specified eviction policy can be certified (confidence 1−δ) to satisfy Rτ(π) ≤ ε on a declared population — and if none can, when should the system fall back to full KV? Central claims: (1) mean degradation does not bound tail risk — configurations with similar E[Δ] differ in P[Δ>0.10] (Fig. 1); (2) fixed-sequence Learn-then-Test yields compressor-agnostic finite-sample certification with full-KV fallback, without modifying the compressor or assuming monotone risk; (3) under one contract (τ,ε,δ)=(.10,.05,.05), certified retention varies widely across compressors and benchmarks (Tables 1–2); (4) empirical thresholding is optimistic by 5–10 retention points on Llama LongBench; (5) mixture-level certificates hide per-task failures. All five claims are supported within their declared scope.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What does risk-controlled KV-cache eviction mean?
Instead of choosing a fixed memory budget and checking average accuracy afterwards, the paper certifies with a finite-sample statistical guarantee that the fraction of requests whose task utility drops by more than a tolerance (default 0.10) relative to full-KV inference stays below a target frequency (default 5%). If no compressed eviction policy can be certified on calibration data, the system falls back to running with the full KV cache.
How much KV cache can be compressed while staying reliable?
It depends strongly on the eviction method and benchmark. Under the paper's default contract on Llama-3.1-8B with LongBench, certified retention ranges from 75% (SnapKV) down to 35% (Layer-DefensiveKV). On the harder RULER-32K benchmark, SnapKV could not be certified even at 80% retention, so the framework prescribes full-KV fallback, while Layer-DefensiveKV certifies at 35%.
Why does the certified setting keep 5–10 percentage points more cache than just picking the policy with observed error under 5%?
With 1200 calibration requests and a 5% risk target at 95% confidence, the statistical test only accepts up to 47 violation events, i.e., a 3.92% observed rate — stricter than the nominal 5%. A policy showing 4.0–4.8% observed degradation lacks sufficient evidence that its true population risk is below 5%, so certification forces a more conservative retention choice.
Does the 5% guarantee hold for every individual task?
No. The guarantee applies to a declared task-balanced mixture population, not to each task separately. On held-out data, some tasks show much higher risk — for example, 29% of RULER common-word-extraction requests degraded materially under Layer-DefensiveKV at its certified setting, even though the aggregate mixture risk was 3.54%.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figures 1–2 are present only as extracted axis/tick labels and marker legends; curve shapes and exact marker positions could not be verified visually.
- The extracted text is arXiv v1 (23 Sep 2026); no supplementary appendix, code link, or per-request data availability statement appears in the text.
- Several cited works are 2026 preprints or very recent conference papers whose contents could not be checked.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.