DropKV: Decoupling Residual-Output Perturbation for Near-Optimal KV-Cache Eviction

Aozhong Zhang, Selcuk Gurses, Yanxia Deng, Naigang Wang, Chi-Chun Liu, Davis Wertheimer, Derrick Liu, Xin Li

Oct 15, 2026arXiv:2610.22130v1

cs.AI

Scorecard· 16/16

6.0/10 impact

Solid, practical, well-validated incremental advance in KV eviction with a theory-plus-kernel package and library integration, but gains on LongBench are small and the subfield is crowded.

Abstract

Key-value (KV) cache management has become a critical bottleneck for scaling Large Language Models (LLMs) to long-context scenarios due to linear memory growth. While recent eviction methods have moved beyond simple attention-score heuristics to incorporate value representations, they typically face a fundamental trade-off: the underlying optimization for minimizing output perturbation is an NP-hard combinatorial problem, leading to mathematically suboptimal heuristics or implementations that are difficult to kernelize. In this work, we propose DropKV, a simple principled eviction framework based on Decoupled Residual-Output Perturbation. By decoupling the joint eviction decision into independent per-token scoring, DropKV circumvents combinatorial intractability and admits a provable constant-factor approximation guarantee under a cone condition that we empirically verify on three long-context LLMs. To ensure practical viability, we provide a high-performance implementation using fused Triton kernels that avoid materializing the full attention matrix, delivering a 19.8x scoring-kernel speedup that translates to up to a 9.9% matched-batch end-to-end prefill speedup. Extensive evaluations on the RULER and LongBench benchmarks demonstrate that DropKV consistently outperforms state-of-the-art baselines at equivalent cache budgets, achieving the lowest inference latency among eviction methods while also remaining faster than the dynamic cache baseline.

AI Impact Assessments

(1 model)

Core Contribution

DropKV is a KV-cache eviction method that scores each token by its exact single-token output perturbation, ‖Δ({j})‖ = p_j/(1−p_j)·‖a−v_j‖. Scores are summed in squared form over an observation window, as in SnapKV. The method drops the interaction terms of the NP-hard joint perturbation objective. The paper offers three things:

A constant-factor approximation guarantee (Theorem 1) for the decoupled top-k proxy, under a "cone condition" (residuals a−v_i lie in a cone) and small attention weights.

A multi-query extension (Proposition 1) and a robust additive-error version (Theorem 2).

Fused Triton kernels that avoid materializing the w×n attention and w×n×d residual tensors, via the identity ‖a−v‖² = ‖a‖² + ‖v‖² − 2⟨a,v⟩.

The paper also includes an NP-hardness reduction from Balanced Partition and an AdaKV-style variant, AdaDropKV.

The idea is simple and well motivated. Prior value-aware methods (CriticalKV, AnDPro) use bounds or convex relaxations. DropKV claims the exact singleton perturbation is better and also kernelizable. The novelty is moderate: the perturbation formula already appears in prior work, and the new elements are the decoupled proxy, the cone-condition analysis, and the systems implementation.

Methodological Rigor

*Theory.* The proofs are short and correct as written. The main bound follows from the triangle inequality plus the cone alignment. The weak points are:

The guarantee is loose. The measured worst-case factor is about 10–12 at the median, with a heavy tail, and the factor is infinite on 9–27% of triples where the cone condition fails.

The cone condition is trivially satisfiable when the candidate pool is small or the residuals are diffuse, so it says little about why the method works.

The bound is on the single-layer, single-query output perturbation, not on downstream task accuracy, so it does not explain the empirical gains. In practice, the gain over SnapKV likely comes from the value-residual factor and the squared weighting.

The theory's pool-restricted setting differs from the deployed algorithm (max-pooling, window summation, GQA).

*Empirical validation of the theory.* This is a real strength. The authors check the assumptions on 128K prefills across three models. They also run brute-force enumeration (n=20, k=10/18) and report a realized approximation ratio with median ≤1.16, with stratified adversarial sampling. That analysis is more honest than most theory-flavored efficiency papers. It is small-scale (n=20), though.

*Experiments.* Three 7–8B long-context models are evaluated on RULER (16K–128K) and LongBench at 5/10/30% budgets, against eight baselines under matched budgets. Gains are large on RULER at 5% budget (+2.4 to +4.0 over the best baseline; much larger on specific tasks such as N-S3 and N-MK2). On LongBench the gains are small (+0.7–0.9) and mixed per task. Weaknesses:

There are no error bars or seeds, although the checklist claims otherwise.

Only 7–8B models are tested, with no larger scale and no reasoning or decoding-time eviction.

Baselines are run via kvpress defaults, with no tuning of window or pooling.

Gains concentrate on a few RULER subtasks (N-S3, N-MK2) and FWE is sometimes worse, so the average gain is partly driven by a small number of tasks.

Several ablations are missing: squared versus unsquared weighting, with versus without the (1−p) term, and the effect of pooling.

*Systems.* The kernel speedups are measured against a naive PyTorch reference (19.8× at 128K), which is a weak baseline. The end-to-end prefill gain is only about 2–10% over the same method in PyTorch. The "faster than dynamic cache" claim mainly reflects eviction in general, not DropKV in particular. The full-generation comparison against SnapKV shows near-identical latency (16.21 vs 16.44 s). The Nsight profiling is a nice detail.

Potential Impact

KV-cache eviction is a crowded area with many incremental methods. DropKV is likely to be cited as a strong baseline and as a principled framing of output-perturbation scoring. It is also integrated into NVIDIA/kvpress, which raises its practical adoption potential. The approximation theory is mostly a justification device and unlikely to be built on heavily. Prefill-only scoring limits the use cases. The method is orthogonal to quantization and to head budget allocation (AdaDropKV shows it composes with AdaKV). The impact is moderate and incremental: it strengthens the case for value-aware scoring but does not change the paradigm.

Timeliness

Long-context memory cost is a pressing bottleneck, and the work is relevant. However, the subfield is saturated and moving toward query-agnostic compression, sparse attention, and learned approaches, with eviction at extreme budgets (5%) of debated practical value because eviction can fail on multi-query tasks.

Strengths

Clean, simple method.

Theory that is checked empirically, including brute-force ratios.

Broad evaluation across models, lengths, and budgets.

Kernel implementation and an upstreamed library integration.

A careful appendix comparing the scoring functions of prior methods.

Limitations

The theory is loose and distant from end-task accuracy.

Modest LongBench gains.

No variance estimates.

Weak kernel baseline.

Prefill-only.

No larger models.

The incremental over-SnapKV gain is not fully isolated by ablation.

The paper's own caveat applies: the 1/(1−p) correction is negligible at deployment-scale weights, so the substantive change is the value residual and the quadratic weighting.

Rating:6/ 10

Significance 5.5Rigor 6Novelty 5Clarity 7

Generated Oct 16, 2026

Comparison History (0)

No comparisons yet.

Scorecard· 16/16

6.0/10 impact

Solid, practical, well-validated incremental advance in KV eviction with a theory-plus-kernel package and library integration, but gains on LongBench are small and the subfield is crowded.