TL;DR
Standard KV-cache eviction methods optimize for average performance, which can mask catastrophic quality drops on individual requests. This paper introduces a compressor-agnostic framework that applies statistical risk control (Learn-then-Test) to guarantee that request-level degradation stays below a user-defined threshold. By shifting from fixed memory budgets to explicit reliability contracts, the system automatically determines the safest maximum compression ratio or safely falls back to full-KV inference if the risk is too high.
What Problem Does This Paper Address?
Serving long-context Large Language Models (LLMs) is incredibly memory-intensive due to the Key-Value (KV) cache, which stores past token states during generation. To save memory, practitioners use eviction policies to discard less important tokens from the cache.
Typically, these eviction methods are evaluated based on their average performance across a benchmark suite. However, the authors point out a dangerous flaw in this approach: a stellar average score can easily hide a long tail of individual requests where the model's utility completely tanks—an effect they call material degradation. For production systems where consistency matters, hiding user-facing failures behind a nice aggregate average isn't acceptable. Engineers need a way to bound the risk of these individual failures before deploying compressed models.
Methods
The authors reframe KV-cache eviction as a deployment risk-control problem. Instead of picking an arbitrary memory budget, a system operator defines a reliability contract using two main parameters:
- Tolerance ($\tau$): The maximum acceptable drop in utility for a single request compared to uncompressed (full-KV) inference.
- Risk Target ($\epsilon$): The maximum allowed fraction of requests in the population that can violate this tolerance threshold.
To enforce this contract with rigorous statistical guarantees, the paper adapts the Learn-then-Test (LTT) framework. The procedure operates as a post-hoc calibration wrapper:
It takes a pre-specified sequence of eviction policies ordered from conservative to aggressive (e.g., retaining 80% down to 20% of the cache) and evaluates them on a small calibration dataset. Using a task-stratified binomial lower-tail inversion test, it calculates valid p-values for each policy's risk. The framework steps through the sequence and certifies the most aggressive policy that statistically guarantees the risk target is met with high confidence ($1-\delta$). If even the most conservative policy fails to meet the bar, the system triggers a full-KV fallback, ensuring deployment safety.
Datasets
The framework was validated using two prominent long-context benchmarks:
- LongBench: A heterogeneous suite of long-context tasks spanning multi-document QA, summarization, and code completion. The authors used 12 tasks that contained at least 200 distinct contexts.
- RULER-32K: A rigorous stress-test benchmark evaluated at a 32K context length, covering needle-in-a-haystack retrieval, variable tracking, and word extraction.
To prevent tasks with abundant data from skewing the results, the calibration and testing sets were curated as a task-uniform mixture (100 requests per task split equally into calibration and testing).
Key Insights and Ideas
- Averages Lie: Policies with nearly identical mean degradation can exhibit vastly different tail risks. Controlling the exceedance probability directly is essential for reliable deployment.
- The Cost of Uncertainty: Naive empirical thresholding (i.e., picking a policy simply because its error rate on the calibration set is under 5%) ignores finite-sample variance. Statistical certification requires a stricter bound. For a sample size of $n=1200$ and a 5% risk target, the framework only certifies a policy if it sees fewer than 47 failures (an empirical rate of ~3.92%).
- Workloads Dictate Compression Limits: The exact same reliability contract yields completely different memory operating points depending on the workload complexity. Harder benchmarks drastically restrict how aggressively you can evict tokens.
Key Results
The authors evaluated four fixed-budget eviction methods (SnapKV, AdaKV, DefensiveKV, Layer-DefensiveKV) and one request-adaptive method (ReFreeKV) using Llama-3.1-8B and Mistral-7B models.
- LongBench Savings: Under a contract allowing at most a 10-point utility drop on at most 5% of requests ($\tau=0.10, \epsilon=0.05$), the framework successfully certified significant memory savings. For Llama-3.1-8B, Layer-DefensiveKV was certified at a highly aggressive 35% retention ratio (65% reduction), while SnapKV required a more conservative 75% retention ratio.
- The Safety Net in Action: On the more punishing RULER-32K benchmark, SnapKV's first candidate (80% retention) suffered a 10.38% failure rate on calibration data. The framework successfully flagged this violation and triggered the full-KV fallback, demonstrating its ability to avert deployment failures automatically.
- Adaptive Calibration: The framework also successfully calibrated a global threshold for the request-adaptive method (ReFreeKV), proving it can handle dynamic compression techniques where retention varies per request.
Limitations and Future Work
- Aggregate vs. Per-Task Risk: The statistical guarantee applies to the overall task-balanced mixture, not to individual tasks. The authors noted that even when a policy is certified globally, specific difficult tasks (like common-word extraction in RULER or TriviaQA in LongBench) can still experience high localized risk.
- Discrete Grids: The policy selection relies on a pre-defined, discrete grid of retention ratios. Finer grids could optimize memory savings further but would increase offline calibration costs.
- Hardware Metrics: The paper focuses entirely on utility risk and retention ratios rather than direct system-level metrics like latency, throughput, or actual GPU memory savings.
Summary updated