Risk-Controlled KV Eviction: The Reliability Contract and Full-KV Fallback

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 often reports average quality-memory trade-offs: a curve of mean benchmark score against retained fraction, and an operating point somewhere on it. The paper argues that an average alone is insufficient for a request-level reliability decision. Good outcomes on some requests can offset bad ones in the mean, while the fraction with large losses remains material. A tail-event count answers a different question from an aggregate score¹.

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 a binomial lower-tail envelope as the p-value when K is below the null mean (and p = 1 otherwise): the probability of observing at most K violations under the boundary risk is compared against δ = 0.05. This is the paper's actual machinery — not Hoeffding's inequality (the Chernoff-style bound), but the paper’s binomial lower-tail envelope, made valid for task-stratified calibration by Hoeffding's 1956 comparison theorem in the lower-tail range below the null mean; it does not assert stochastic dominance at every count¹².
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 has degradation 0 and risk 0 by definition and is returned when the first compressed candidate fails¹. 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 observed price of certification on this finite sample. A finite calibration set generally leaves a nonzero uncertainty margin; the number of extra retention points depends on the candidate grid and its data. 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):
        p_env = binom_cdf(k, n, eps) if k <= math.floor(n*eps)-1 else 1.0
        if p_env > 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 paper’s plug-in rule accepts 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
# A policy with true 4% risk certifies only about half the time at n=1200.
# At the null boundary p=5%, certification rounds to 0.05; the exact
# probability is at most delta because the count cutoff is discrete.
 
# --- A larger illustrative calibration set (not the paper's run) ---------
n4 = 4000
k4 = k_max(n4)
print(f'\nn={n4}: K_max={k4}, P(certify a true-4% policy) = '
      f'{binom_cdf(k4, n4, 0.04):.2f}')
# n=4000: K_max=177, P(certify a true-4% policy) = 0.92

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.
• A policy below the target may still fail certification. At true 4% risk, the single-candidate pass probability is about 0.48 with 1,200 calibration requests. At the illustrative n = 4,000 it rises to about 0.92. These are probabilities under an assumed common true risk, not measurements of the paper’s compressors.
• The delta is bounded, not hidden. At the null boundary of true 5% risk, the single-candidate certification probability rounds to 0.05. The exact probability is at most δ because violation counts are discrete. For a policy whose true risk exceeds 5%, the probability of a false certificate is also bounded by δ under the stated sampling assumptions. 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 can lower a later candidate’s selection probability substantially: the candidate is tested only if every earlier candidate passed. The calculation therefore illustrates a single candidate, not the selection probability of the full procedure.

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 no longer establishes the risk for that deployment. A new representative calibration and certification are needed to make a claim for the changed mix¹. The paper samples finite benchmark corpora without replacement but models requests within each task as independent draws; the formal guarantee relies on that sampling model.

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. Eviction aggressiveness is a bet about the tail behavior of the declared population. The two observed outcomes — a full-KV fallback that removes the memory savings, and 5–10 additional retention points in the studied Llama LongBench comparisons — show the cost of this particular reliability contract and calibration setup.

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