PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Beomgu Kang, SoJin Yun, Hojoon Kim, Hyunseok Seo

arXiv:2609.27981v1cs.CLcs.LG

TL;DR

Average quality-memory trade-offs can hide requests with material utility losses, motivating request-level risk control for KV-cache eviction. The paper uses compressor-agnostic calibration to select a retention policy with a finite-sample guarantee. Across models, compressors, and benchmarks, the same reliability contract yields substantially different retention choices, and empirical thresholding can select uncertified policies.

  • Problem

    Average degradation does not establish how often individual requests incur losses beyond a deployment tolerance, leaving a request-level reliability question for KV-cache eviction.

    Source: §1 · p. 1

  • Method

    A compressor-agnostic calibration wrapper applies fixed-sequence testing to pre-specified policies and returns the most aggressive certified policy, with full-KV fallback if none passes.

    Source: §1 · p. 2

  • Results

    Certified operating points vary across models, compressors, and benchmarks; on Llama LongBench, certification selects policies retaining 5–10 percentage points more cache than empirical thresholding, even when empirical calibration risk is at most 5%.

    Source: §1 · p. 2, §8 · p. 10

  • Takeaways & Limitations

    The framework converts a declared request-level reliability requirement into a retention choice for the stated benchmark population and utility metric.

    Source: §8 · p. 10

    The certificate applies to the declared benchmark population and assumes independent calibration requests from each task; it does not establish task-specific guarantees or robustness under distribution shift.

    Source: §7 · p. 10

Abstract

from arXiv · show

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.

1 Introduction

The paper reframes KV-cache eviction as request-level risk control because average degradation can conceal material losses on individual requests. It uses compressor-agnostic calibration to select retention policies under a reliability requirement, with full-KV fallback when no compressed policy is certified.

1 Introduction

  • Growing KV-cache memory costs motivate eviction methods that retain selected cached states while preserving model quality.The introduction evaluates fixed-budget methods with Llama and Mistral on LongBench and Llama on RULER-32K, plus request-adaptive ReFreeKV with Llama on LongBench.Source: §1 · pp. 1–2
  • Similar mean degradation can correspond to different material-degradation risks, so average quality alone does not determine how often requests exceed the deployment tolerance.The figure illustrates this distinction for Llama-3.1-8B on LongBench at τ = .10, with target ϵ = .05.Source: §1 · p. 1, Figure 1 · p. 2
  • Calibration applies finite-sample risk control to pre-specified eviction policies without modifying the compressor, selecting the most aggressive certified policy or falling back to full KV.The procedure uses an independent calibration set and controls request-level utility degradations exceeding a deployment-specified tolerance.Source: §1 · p. 2
  • The reliability contract specifies tolerated utility loss and its allowed population frequency relative to paired full-KV inference.The deployment question is how aggressive eviction can be while remaining reliable at the request level.Source: §1 · pp. 1–2
  • Across models, compressors, and benchmarks, certified operating points vary; on Llama LongBench, certification retains 5–10 percentage points more cache than empirical thresholding, even when empirical calibration risk is at most 5%.Empirical thresholding can select policies that fail finite-sample certification.Source: §1 · p. 2

2 Related Work

Prior KV-cache work adapts which states or how much cache to retain, while risk-control work calibrates resource-saving inference decisions. This paper applies finite-sample certification to request-level task degradation from eviction.

2.1 KV-cache eviction

  • KV-cache methods vary which states they retain, how fixed budgets are allocated across heads or layers, or how total retention adapts across requests; these approaches do not report finite-sample control of population material-degradation risk.Related methods include H2O, SnapKV, AdaKV, PyramidKV, DynamicKV, DefensiveKV, Layer-DefensiveKV, ReFreeKV, and CompilerKV.Source: §2.1 · pp. 2–3

2.2 Distribution-free and quantile risk control for inference

  • Prior risk-control methods calibrate resource-saving choices such as decoder depth or reasoning length, whereas this work certifies the population frequency of request-level task degradation from eviction relative to paired full-KV inference.Earlier KV-compression certificates focus on attention fidelity, while this approach uses task-stratified finite-sample certification over pre-specified policy families without modifying the compressor.Source: §2.2 · p. 3, §2.1 · p. 3

3 Risk-Controlled KV Deployment

The paper formulates KV eviction as controlling the population frequency of request-level utility losses beyond a tolerance relative to full-KV inference. It uses calibration data to certify a retention policy from a pre-specified sequence, with full KV as fallback.

3.1 Risk-Controlled KV Eviction Formulation

  • Material-degradation risk is the population frequency of paired utility drops beyond tolerance τ relative to full-KV inference, bounded by a reliability contract.The main setting allows utility drops greater than 0.10 on at most 5% of requests, with a finite-sample confidence requirement.Source: §3.1 · pp. 3–4

3.2 Finite-Sample Certification with Fixed-Sequence Testing

  • Fixed-sequence Learn-then-Test evaluates pre-specified policies using calibration p-values, returning the last certified policy before the first failure or full KV if none passes.The sequence controls false certification at level δ without requiring risk to be monotone in retention.Source: §3.2 · pp. 4–5
  • Equal task allocation makes the certificate apply to the task-uniform mixture, not to each task individually or differently weighted deployment populations.Candidate policies and their order are fixed before calibration outcomes are inspected.Source: §3.2 · p. 4

3.3 Request-Adaptive Policies

  • For request-adaptive compressors, each pre-specified threshold defines a policy that uses the same degradation test and fixed-sequence selection rule.The selected policy’s mean retained fraction is estimated overall and within each task on held-out data using equal task weights.Source: §3.3 · p. 5

4 Experimental Setup

The experiments compare two open-weight models and several fixed-budget and request-adaptive eviction methods across LongBench and RULER. They use task-balanced evaluation populations, a fixed reliability contract, and separate calibration and held-out evaluation.

4.1 Models and eviction methods

  • The primary LongBench evaluation considers 8B-Instruct (Grattafiori et al., 2024) and Mistral-7B-Instruct-v0.3 (Jiang et al., 2023), using four fixed-budget KV-cache eviction methods and additionally evaluating request-adaptive ReFreeKV.Layer-DefensiveKV extends DefensiveKV with layer-wise budget allocation. Fixed-budget runs use FlashAttention-2, while ReFreeKV uses eager attention.Source: §4.1 · p. 5

4.2 Benchmarks and evaluation populations

  • LongBench uses 12 eligible tasks (n = 1,200 per split), while 32K RULER uses 13 tasks (n = 1,300); certificates cover task-balanced aggregates.Per-task TEST risks are descriptive diagnostics, not individual task guarantees.Source: §4.2 · p. 6
  • ReFreeKV’s certificate covers adaptive-policy calibration within its matched 8K protocol, not preprocessing-induced degradation or cross-protocol efficiency comparisons.Its input budget and some prompt formatting differ from the fixed-budget protocol.Source: §4.2 · p. 6

4.3 Reliability Contract and Experimental Details

  • Confirmatory sequences use τ = 0.10, ϵ = 0.05, and δ = 0.05, targeting population risk at most 0.05 with at least 0.95 calibration confidence.Utilities are normalized to [0, 1] before paired degradation is computed against full KV; fixed-budget experiments vary retained fraction and use deterministic greedy decoding.Source: §4.3 · p. 6

4.4 Calibration and Held-out Evaluation Protocol

  • Candidates are tested on CAL in a pre-specified conservative-to-aggressive order; the frozen selection is evaluated descriptively on TEST, and benchmarks are calibrated independently.TEST outcomes do not modify the candidate sequence, certification decision, or selected operating point.Source: §4.4 · pp. 6–7

5 Results

Across LongBench and RULER-32K, certification selects different retention levels across methods and can reject candidates whose empirical risk is below the nominal target. The framework also certifies a request-adaptive ReFreeKV threshold without requiring a fixed retention ratio for every request.

5.1.1 Selected Operating Points and Held-out Evaluation

  • On LongBench, certified retention varies by model and compressor; Layer-DefensiveKV retains 0.35 on Llama versus 0.45 on Mistral, while DefensiveKV retains 0.40 versus 0.40.Seven of eight selected model–compressor pairs have TEST risk below 5%; Mistral DefensiveKV has 61/1200 events (5.08%). More aggressive candidates can fail certification despite empirical risk below 5%.Source: §5.1.1 · p. 7

5.1.2 Certified versus Empirical-Risk Selection

  • On Llama LongBench, first non-certified candidates for all four fixed-budget methods have empirical risks below 5%, yet certification selects retention ratios 0.05–0.10 higher than empirical thresholding.Under (ϵ, δ) = (.05, .05), the finite-sample test certifies at most 47 events.Source: §5.1.2 · p. 7

5.2 RULER-32K Results

  • On RULER-32K, Layer-DefensiveKV certifies 0.35 retention, while SnapKV falls back to full KV after its 0.80 candidate fails; retention fractions from 0.80 to 1.00 were untested.The three certified compressed policies have held-out TEST risks below 5%, but common-word extraction risks reach 9%, 15%, and 29% for AdaKV, DefensiveKV, and Layer-DefensiveKV.Source: §5.2 · p. 8, Table 2 · p. 8

5.3 Request-Adaptive Certification with ReFreeKV

  • For ReFreeKV, fixed-sequence LTT certifies threshold T = .0005; the selected policy retains 87.48% on CAL and 87.36% on TEST, with 42/1200 TEST degradation events (3.50%).The next threshold, T = .001, is not certified despite 4.42% empirical CAL risk; this calibrates a global threshold without prescribing fixed retention for each request.Source: §5.3 · p. 8

6 Additional Analyses

Additional analyses show that selected retention depends on the reliability contract, and task-level risks can differ from aggregate results. The certificate applies to the declared task-balanced benchmark population, not to each task or distribution shifts.

Sensitivity to the reliability contract

  • At ϵ = .05, tightening τ from .10 to .05 raises Layer-DefensiveKV retention from .35 to .65 and moves SnapKV from .75 to full KV.These post-hoc sensitivity cells are descriptive; favorable contract selection after inspecting the table requires fresh calibration data or an appropriate multiplicity correction.Source: §6 · p. 9

Task and metric heterogeneity

  • Fixed-budget aggregate risks of 2.50%–4.08% coexist with task risks of 10% for DefensiveKV on 2WikiMQA and Layer-DefensiveKV on SAMSum.ReFreeKV has 3.50% aggregate risk but 20% on TriviaQA; under its separate protocol, mean utility changes from 32.1 under full KV to 32.0.Source: §6 · p. 9
  • The certificate covers the task-balanced mixture, not individual tasks; simultaneous lower confidence bounds exceed 5% for RULER common-word extraction under Layer-DefensiveKV and DefensiveKV.The respective observed rates are 29/100 (95% simultaneous CI: [14.6%, 47.1%]) and 15/100 ([5.1%, 31.1%]).Source: §6 · p. 9
  • On LCC, full-KV utility averages 71.0 points and Layer-DefensiveKV at retention 0.35 averages 75.2 points, yet 3% of requests lose more than ten points.The common τ = .10 threshold is a ten-point loss on the 0–100 scale, but its semantic meaning varies across LongBench task metrics.Source: §6 · pp. 9–10
  • In the fixed-budget protocol, full-KV utility is zero on 253/1200 TEST requests; low relative-degradation risk therefore does not imply high absolute task quality.Requests with Ufull(X) ≤ τ cannot incur degradation strictly greater than τ when compressed utility is nonnegative.Source: §6 · p. 10

7 Limitations

The guarantees and operating points are bounded by the calibration population, evaluation scope, pre-specified selection process, and utility-risk contract.

  • The certificate applies to the declared benchmark population under independent calibration requests; it provides neither task-specific guarantees nor distribution-shift robustness.Source: §7 · p. 10
  • Evaluation covers two 7–8B model families, limited eviction methods, and discrete candidate grids, so operating points may not transfer to larger models, architectures, or serving stacks.Source: §7 · p. 10
  • The contract, candidates, and their order must be fixed before calibration outcomes are inspected; post-hoc selection needs multiplicity control or fresh calibration.Source: §7 · p. 10
  • Tolerance and risk targets are application-dependent, certified low risk does not ensure high absolute utility, and system-level latency or throughput are not evaluated.Source: §7 · p. 10

8 Conclusion

The paper reframes KV-cache eviction as reliability-first retention selection, using calibration to control material request-level degradation and determine an operating point for a declared population.

  • The formulation selects retention from an allowable frequency of material request-level degradation rather than fixing a memory budget and judging average quality afterward.Source: §8 · p. 10
  • Fixed-sequence Learn-then-Test provides finite-sample risk control for the returned policy without modifying the compressor or assuming monotone risk.Source: §8 · p. 10
  • Across multiple eviction methods, models, and long-context benchmarks, one reliability contract yields substantially different retention choices, while average utility can conceal request-level failures.Source: §8 · p. 10

Related papers

Loading 2609.27981v1…