Risk-Controlled KV Eviction: The Reliability Contract — And the Full-KV Fallback Nobody Ships

A September 2026 paper from Korea University attacks a habit so entrenched in KV-cache eviction that most serving teams no longer notice they have it: picking a memory budget first and checking average quality later¹. Risk-Controlled KV-Cache Eviction: From Memory Budgets to Risk Targets (Kang, Yun, Kim and Seo, arXiv:2609.27981, 14 pages, cs.CL and cs.LG, submitted September 23, 2026) inverts the order of operations. You state a reliability contract first — a tolerated utility loss and how often that loss may be exceeded — and a statistical certification procedure on calibration data then tells you how aggressive your eviction is allowed to be, with a fallback to full KV when the answer is "not at all"¹.

The uncomfortable part is what the procedure actually returns at its edges. On Llama-3.1-8B it certifies SnapKV at 75% retention on LongBench, but on RULER-32K it certifies no tested compressed SnapKV policy at all and returns full KV — the memory configuration eviction exists to eliminate¹. And on the very benchmark where certification succeeds, it selects retention ratios 5 to 10 percentage points higher than the naive "accept anything under the target" rule would have picked, because finite-sample statistics refuse to certify policies whose observed degradation merely looks fine¹. Both facts are the point, not a defect: the paper is selling a contract whose honest outputs include "spend more memory" and "I cannot prove this is safe."

This guide decomposes the machinery that produces those outputs, reproduces the certification cutoffs and their conservatism in Python (illustrative implementation — we rebuild the paper's exact bound, stated as such below), and marks where the guarantee's honest scope ends: it is a statement about a calibration population, and distribution drift voids it. The capacity and cost context lives in our KV cache glossary, the eviction-policy zoo in random attention vs. SnapKV, the working-set side of the memory question in KVSET prefix-cache sizing, and the memory price that makes the fallback expensive in HBM4 shortage economics.

1. The problem: means hide tail failures

Eviction research overwhelmingly reports average quality-memory trade-offs: a curve of mean benchmark score against retained fraction, and an operating point somewhere on it. The paper's central observation is that this is the wrong functional of the data for a deployment decision. A small mean degradation says nothing about how often eviction badly damages an individual request. Formally, a small expected degradation does not imply a small probability of a large degradation — the mean is an aggregate, the exceedance probability is a tail statement¹.

The paper's reframing is a two-parameter contract on the tail:

• Material degradation: for a single request, eviction lowers task utility by more than a tolerance τ relative to full-KV inference on the same request, under the same model, prompt, generation settings and evaluator. Utilities are normalized to the 0-1 range, so τ is a fraction of total utility. The paper's main setting is τ = 0.10 — a ten-point drop on a 0-100 scale¹.
• Deployment risk: the population frequency of such events, and the contract bounds it at ϵ = 0.05 — at most 5% of requests may materially degrade¹.
• Confidence: the certification procedure is allowed to fail to control that bound with probability at most δ = 0.05 over the randomness of calibration sampling¹.

Two details earn emphasis because a summary will drop them. First, the risk is defined relative to full KV, not relative to task correctness: a request whose full-KV utility is already zero cannot degrade, so low certified risk does not mean high absolute quality — the paper says exactly this¹. Second, utility improvements on some requests do not offset material degradations on others; there is no netting, only counting¹. The tail is the product.

Why the tail is invisible in current practice: a production eviction policy is tuned against average benchmark scores or eyeballed output samples, and real aggregate risk concentrates in specific tasks. The paper's own Table 4 is the demonstration — Llama with Layer-DefensiveKV at 35% retention averages 53.5 across LongBench, essentially tied with full KV's 53.6, mean-neutral. Yet 4% of requests still drop more than ten points, and the per-task spread runs from 0% (PassageRetrieval-en) to 10% (SAMSum)¹. Mean-neutral, tail-heavy: exactly the profile an average-based signoff waves through, and exactly the profile a 95th-percentile-failure event used to be in every cache-sizing decision this site's fleet-cost guide warns about.

2. The machine: Learn-then-Test on calibration data

The certification is a wrapper, not a new compressor. It does not modify the eviction algorithm; it selects among a pre-specified sequence of candidate policies — SnapKV at a grid of retention ratios, AdaKV at the same grid, even the request-adaptive ReFreeKV at a grid of thresholds¹. For fixed-budget methods the grid is shared: retention 0.80, 0.75, 0.70, down to 0.20, ordered conservative to aggressive, fixed before any calibration outcome is inspected¹. That pre-specification is not a formality; it is a load-bearing assumption of the guarantee (Section 4).

The procedure, end to end:

1. Calibration. On LongBench, 100 calibration requests per task across 12 tasks — 1,200 paired (full-KV, compressed) evaluations per candidate policy. On RULER-32K, 100 per task across 13 tasks — 1,300 pairs¹.
2. Violation counting. For each candidate, count calibration requests whose paired degradation exceeds τ. Call the count K; the empirical risk is K/n¹.
3. Hypothesis test. Each candidate is tested as H: "population risk ≥ 5%" against "strictly below 5%," using the exact binomial lower tail as a valid p-value: under the null, the probability of observing at most K violations is compared against δ = 0.05. This is the paper's actual machinery — not Hoeffding's inequality (the Chernoff-style bound), but the exact binomial tail, made valid for task-stratified calibration by Hoeffding's 1956 comparison theorem, which lets heterogeneous per-task Bernoulli probabilities be dominated by a single binomial at the mixture rate¹².
4. Fixed-sequence selection. Candidates are tested in the pre-specified conservative-to-aggressive order and the procedure stops at the first non-rejection, returning the last certified candidate — or full KV if the very first candidate fails. Fixed-sequence testing needs no monotonicity assumption and no correction across candidates: the probability of any false certification is bounded by δ because any false certification requires falsely rejecting the first true null in the sequence¹³.

The full-KV fallback is not a special case bolted on; it is a policy in the sequence with degradation 0 and risk 0 by definition¹. When no compressed candidate passes, the contract quietly returns the memory budget you were trying to shrink — which is why Section 3 matters commercially, not just academically.

The guarantee, stated in full and conditional form: with probability at least 1 − δ = 95% over calibration sampling, the selected policy's population material-degradation risk is at most 5% on the declared task-balanced population — provided the contract, candidate grids and their order were fixed before calibration inspection, and calibration requests are independent draws from the task distributions¹. Every qualifier in that sentence is doing real work, and Section 4 prices each one.

3. The results, including the fallback

Evaluated were two open-weight models — Llama-3.1-8B-Instruct and Mistral-7B-Instruct-v0.3 — four fixed-budget evictors (SnapKV, AdaKV, DefensiveKV, Layer-DefensiveKV) plus the request-adaptive ReFreeKV (Llama only, LongBench only), on LongBench (Llama and Mistral) and RULER-32K (Llama)¹. Hardware note for reproducibility: RTX A6000 48 GB GPUs, FlashAttention-2 for fixed-budget runs, eager attention for ReFreeKV¹.

The headline decomposition — the same contract, wildly different operating points:

LongBench, Llama-3.1-8B. Certified retention at (τ, ϵ, δ) = (0.10, 0.05, 0.05): SnapKV 0.75, AdaKV 0.65, DefensiveKV 0.40, Layer-DefensiveKV 0.35. Held-out test risks for all four sit at 2.5%-4.1%, under the 5% target¹.

LongBench, Mistral-7B. Same contract, different answers: SnapKV 0.70, AdaKV 0.70, DefensiveKV 0.40, Layer-DefensiveKV 0.45 — and note DefensiveKV and Layer-DefensiveKV swap ranks between the models (0.40/0.35 on Llama, 0.40/0.45 on Mistral), which is the non-monotone, model-specific behavior the compressor-agnostic design is built to tolerate¹.

RULER-32K, Llama. Layer-DefensiveKV certifies at 0.35, DefensiveKV at 0.45, AdaKV at 0.70. SnapKV's first, most conservative candidate — 80% retention — racks up 135 of 1,300 calibration violations (10.38%), fails certification outright, and fixed-sequence testing never tests anything more aggressive: the procedure returns full KV¹. The paper is careful to scope this: retention fractions between the grid points were not evaluated, so the claim is not "every compressed SnapKV policy on RULER is uncertifiable," only "no tested one"¹. Precision matters here — this is exactly the sentence a vendor's slide would truncate.

ReFreeKV (request-adaptive, Llama LongBench). A threshold grid certifies the first threshold (3.25% calibration risk), rejecting the next at 4.42% empirical — the same conservative behavior, applied to a compressor with no fixed retention ratio. Average retained fraction: 87.5%¹.

Two honesty checkpoints the paper itself performs and publishes, both worth quoting as method:

• On held-out test data, seven of the eight LongBench model-compressor pairs land under 5% empirical risk. The eighth — Mistral DefensiveKV — shows 61/1,200 = 5.08%, one event over the proportion. The paper states plainly that this neither invalidates the calibration certificate nor establishes that population risk exceeds 5%: the guarantee was a 95%-probability statement about the procedure, not an assertion that the test rate always lands under the line¹. A mean-based method would have no way to say anything at all here.
• On RULER-32K, all three certified compressed policies land under the nominal target on test — but test risk concentrates badly in one task: common-word extraction hits 9% (AdaKV), 15% (DefensiveKV) and 29% (Layer-DefensiveKV)¹. A post-hoc Clopper-Pearson analysis with Bonferroni correction across 147 policy-task combinations finds lower confidence bounds above 5% for RULER CWE under both DefensiveKV variants and for LongBench TriviaQA under ReFreeKV¹. The certificate covers a task-balanced mixture; it promises nothing per task, and the paper shows you the per-task damage rather than hiding it.

The ß sensitivity table (Section 6 of the paper) proves the dial actually dials: tightening τ from 0.10 to 0.05 raises Layer-DefensiveKV retention from 0.35 to 0.65 and pushes SnapKV from 0.75 to full KV; loosening ϵ to 0.20 lets six of eight model-compressor rows fall to the 0.20 grid floor¹. The contract, not the memory budget, is the control knob.

4. The conservatism, priced

Here is the part that will annoy every efficiency engineer and should be understood anyway. Empirical thresholding — the naive rule "accept any candidate whose observed calibration risk is under 5%" — would have accepted at most 60 violations in a 1,200-request calibration, and on Llama LongBench it would have accepted the next candidate for every single compressor¹:

• SnapKV at 70% retention: 50 violations, 4.17% empirical.
• AdaKV at 60%: 49 violations, 4.08%.
• DefensiveKV at 35%: 58 violations, 4.83%.
• Layer-DefensiveKV at 30%: 48 violations, 4.00%.

All four sit under the nominal 5% target. All four fail the finite-sample test, because the test is asking a harder question: not "was the observed rate under 5%" but "is there statistical evidence the population rate is strictly below 5%, at confidence 95%." With n = 1,200 that requires the observed count to come in at or under 47 — an effective screened threshold of 3.92%, not 5%¹. Across the four Llama compressors, certification consequently selects retention 0.05 to 0.10 higher than empirical selection would¹. On the concrete Layer-DefensiveKV comparison: the plug-in rule picks 0.30 retention, certification picks 0.35, and on held-out data the 0.30 policy shows 5.33% test risk versus 4.00% for the certified one — the naive rule was selecting a genuinely riskier policy, and this once, the caution earned its cost¹.

That gap is the price of the guarantee, and it is perpetual, not a startup cost: it persists as long as calibration sets are finite. The next section makes the mechanism tangible by running it.

5. The certification core, run

Everything below is our illustration — it implements the paper's exact machinery (the exact binomial lower-tail p-value at the paper's parameters, not a Chernoff/Hoeffding-style inequality), so the cutoffs reproduce the paper's own numbers, but the certification-probability and sample-size sweeps are our illustrations of the same bound, not figures from the paper.

import math
 
def binom_cdf(k, n, p):
    """P[Bin(n,p) <= k], stable for large n: accumulate in log space.
    Case k < mode: sum the lower tail directly. Case k >= mode:
    compute 1 - P(X >= k+1). No factorials, no overflow."""
    if k < 0: return 0.0
    if k >= n: return 1.0
    def pmf_log(i):
        return (math.lgamma(n+1) - math.lgamma(i+1) - math.lgamma(n-i+1)
                + i*math.log(p) + (n-i)*math.log1p(-p))
    def logaddexp(a, b):
        if abs(a-b) >= 700: return max(a, b)
        m = max(a, b); return m + math.log1p(math.exp(-abs(a-b)))
    mode = math.floor((n+1)*p)
    if k < mode:
        total = term = pmf_log(k)
        for i in range(k, 0, -1):
            term += math.log(i/(n-i+1)) + math.log((1-p)/p)
            total = logaddexp(total, term)
        return min(math.exp(total), 1.0)
    total = term = pmf_log(k+1)
    for i in range(k+1, n):
        term += math.log((n-i)/(i+1)) + math.log(p/(1-p))
        total = logaddexp(total, term)
    return max(1.0 - math.exp(total), 0.0)
 
def k_max(n, eps=0.05, delta=0.05):
    """Largest CAL violation count the paper's fixed-sequence test certifies:
    the exact binomial lower tail at the target risk must stay <= delta."""
    for k in range(0, n+1):
        if binom_cdf(k, n, eps) > delta:
            return k - 1
    return n
 
# --- Reproduce the paper's certification cutoffs -------------------------
for n, note in ((1200, 'LongBench: 12 tasks x 100 CAL requests'),
                (1300, 'RULER-32K: 13 tasks x 100 CAL requests')):
    k = k_max(n)
    print(f'n={n} ({note}): K_max={k}, certifiable empirical risk {k/n:.2%}')
# n=1200: K_max=47 -> certifiable empirical risk 3.92%  (paper: 47, 3.92%)
# n=1300: K_max=51 -> certifiable empirical risk 3.92%  (paper: 51, 3.92%)
# The naive plug-in rule would have accepted up to 60 events at n=1200
# (60/1200 = 5.00%); the test accepts 47. That 13-event gap IS the price
# of the guarantee, and it is why SnapKV@70% (50 events) fails despite
# 4.17% < 5%.
 
# --- The screened threshold tightens only with data -----------------------
print()
for n in (1200, 2600, 5200, 10400, 26000, 104000):
    k = k_max(n)
    print(f'n={n:>6}: K_max={k:>5} -> screened threshold {k/n:.3%} vs 5.000% nominal')
# n=  1200: K_max=   47 -> screened threshold 3.917% vs 5.000% nominal
# n=  2600: K_max=  111 -> screened threshold 4.269% vs 5.000% nominal
# n=  5200: K_max=  233 -> screened threshold 4.481% vs 5.000% nominal
# n= 10400: K_max=  483 -> screened threshold 4.644% vs 5.000% nominal
# n= 26000: K_max= 1241 -> screened threshold 4.773% vs 5.000% nominal
# n=104000: K_max= 5084 -> screened threshold 4.888% vs 5.000% nominal
# The screened rate converges to the nominal target only as O(1/sqrt(n)):
# quadrupling n roughly halves the safety margin. Conservatism is not a
# constant tax - it is a function of how much paired calibration data you
# are willing to pay for (each CAL request = one full-KV + one compressed
# generation, greedily evaluated twice per candidate on the same grid).
 
# --- Why borderline policies fail: P(certify) vs the TRUE rate ------------
print()
for p in (0.030, 0.035, 0.040, 0.045, 0.050):
    print(f'true degradation rate p={p:.1%}: expected CAL events {p*1200:.0f}, '
          f'P(certify at n=1200) = {binom_cdf(47, 1200, p):.2f}')
# true degradation rate p=3.0%: expected CAL events 36, P(certify) = 0.97
# true degradation rate p=3.5%: expected CAL events 42, P(certify) = 0.81
# true degradation rate p=4.0%: expected CAL events 48, P(certify) = 0.48
# true degradation rate p=4.5%: expected CAL events 54, P(certify) = 0.18
# true degradation rate p=5.0%: expected CAL events 60, P(certify) = 0.05
# This is the RULER story in one curve. A policy that truly satisfies the
# contract with 10% headroom (4% vs 5% target) certifies only ~half the time
# at n=1200 - a genuinely SAFE policy stalls in the certification queue.
# And P(certify) at p=5% is 0.05, not 0: the test's own delta leakage, the
# 5% of calibration draws where a violating policy slips through.
 
# --- Buying back the conservatism with calibration data -------------------
lo, hi = 1200, 400000
while lo < hi:                       # smallest n where a true-4% policy
    mid = (lo + hi) // 2             # certifies with probability >= 0.90
    if binom_cdf(k_max(mid), mid, 0.04) >= 0.90: hi = mid
    else: lo = mid + 1
n4, k4 = lo, k_max(lo)
print(f'\ntrue-4% policy, P(certify) >= 0.90 needs n ~ {n4} '
      f'({n4/1200:.0f}x the calibration set used in the paper); '
      f'screened threshold there: {k4/n4:.3%}')
# true-4% policy, P(certify) >= 0.90 needs n ~ 3808 (3x the paper's
# calibration set); screened threshold there: 4.412%

Four things to read off the output, because they are the paper's whole argument in executable form:

• The cutoffs match the paper exactly. K_max = 47 at n = 1,200 and 51 at n = 1,300 — the same numbers printed in the paper's Section 3.2 and 4.2, derived here independently from the binomial tail. Reproduced, not transcribed.
• Conservatism is a data-purchase decision. The screened threshold is 3.92% on the paper's calibration sizes, and creeps to only 4.89% even at 100,000 paired samples. Every notch toward 5% costs paired full-KV-plus-compressed generations across the whole candidate grid — the convergence is O(1/√n), so the last mill of conservatism is always the most expensive.
• The moderate-rate trap is real. A policy with true 4% risk — inside the contract with headroom — certifies with probability 0.48 on the paper's calibration size. Flip a coin on your memory operating point. The mechanism, made tangible: at n = 1,200 the test demands near-perfection from a merely-good policy, and no reasonable calibration budget fixes this cheaply (0.90 certification probability for a true-4% policy needs roughly 3x the paper's calibration set).
• The delta is priced, not hidden. P(certify) at true 5% is 0.05 — precisely the δ the contract spent. The guarantee says the procedure fails at most 5% of the time over calibration draws, and the simulation shows exactly that residual leakage. Nothing about the certificate is absolute; it is a 95% statement about a procedure, and the code displays the 5%.

One caveat on the illustration's edge: certification probability is computed for a single candidate. Fixed-sequence testing over a grid shifts the picture only slightly there — the first tested (most conservative) candidate faces essentially the single-candidate test, and later candidates only get tested if the earlier ones passed.

6. Honest scope: what the guarantee does not say

The paper's limitations section is unusually complete, and every clause in it is a deployment boundary worth restating as an operating assumption:

The guarantee is anchored to the calibration population. The contract covers the task-balanced mixture: 12 LongBench tasks (or 13 RULER tasks) mixed uniformly, with calibration requests drawn independently per task. It is not a per-task guarantee — the RULER common-word-extraction rates (up to 29%) live inside a certified 3.5% mixture — and it is not a guarantee under distribution shift. Serve a traffic mix unlike the calibration mix, or let the mix drift, and the certificate stops describing your deployment. Recalibration after drift is not an optional hardening step; it is the only thing that keeps the guarantee true¹.

The fallback is full KV, and full KV is the cost you came to avoid. When nothing certifies — as with SnapKV on RULER-32K — the procedure does not return "the best available compressor"; it returns the paired full-KV reference, at 100% of the memory the project was launched to save. The contract trades memory for certainty, and in the worst case it trades all of it.

Post-hoc choices void the certificate. The guarantee requires the tolerance, target, confidence, candidate grids and their order to be fixed before calibration outcomes are inspected. Changing τ or ϵ after seeing results — or selecting among multiple sequence outputs on their calibration outcomes — requires multiplicity control or fresh calibration data. The paper applies this rule to itself: its Section 6 sensitivity table over (τ, ϵ) pairs is explicitly labeled exploratory, off-the-frozen-path¹.

Relative ≠ absolute. Risk is measured against paired full-KV inference. A model whose full-KV utility is low certifies just as easily as a good one; low certified risk says nothing about serving quality, only about not making it materially worse than full KV would have. Similarly, the guarantee does not extend to end-to-end serving metrics — no latency or throughput claims are made; the object is retained-KV fraction and utility risk¹.

Scope of evidence. Two 7-8B models, five eviction methods, two benchmarks, discrete grids. Whether the same contract certifies the same operating points on frontier-scale models, on other serving stacks, or under production traffic distributions is simply not tested¹.

7. Verdict

The paper's contribution is not a compressor — it deliberately builds none — but a decision procedure that converts a reliability requirement into a memory operating point, with falsifiable outputs at every step. That is the correct primitive: eviction aggressiveness is a bet about the tail behavior of a population, and the population, not the mean, is what a deployment actually serves. The two honest outputs — a full-KV fallback that costs the entire savings, and a conservatism surcharge of 5-10 retention points that persists as long as calibration sets are finite — are not weaknesses of the framework; they are the first numbers anyone has actually printed for what a reliability contract on KV eviction costs.

The failure mode to watch for is recognition, not implementation: a vendor quoting "risk-controlled compression" without stating the contract's (τ, ϵ, δ), the calibration population, and the fallback behavior on their own production mix is selling the average, again, with a new label. The certificate is only as good as the population it was calibrated on — and the fallback is only cheap if you never hit it. Ask those two questions and the honest articles separate quickly from the rest.

Footnotes