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

What it claims

DropKV evicts KV-cache entries by scoring each token with the exact attention-output shift its removal would cause, rather than its attention weight alone. The page's practical claims go beyond the summary in three ways:

• Memory: the fused scoring kernel cuts scratch memory at n=128K from about 9 GB to about 17 MB. The authors present this as removing the prefill memory bottleneck.
• Scaling of the speedup: the 19.8× scoring speedup is the 128K figure. It is only 1.8× at 4K, measured against a naïve PyTorch implementation with an observation window of 8 on an A100-80GB.
• Approximation in practice: the worst-case bound is loose, but the observed approximation ratio is close to 1.

The reported settings are 5% and 10% cache budgets on RULER and LongBench. The comparison covers query-aware baselines (e.g., SnapKV) and output-aware baselines (CriticalKV, AnDPro).

How it works

Evicting set J shifts the attention output by Σ_{i∈J} p_i(a − v_i) / (1 − P_J), where p_i is the attention weight, a the full output and v_i the value. Choosing the k tokens that minimise this is NP-hard. DropKV ignores interactions between evicted tokens and scores each token on its own:

1. For each query in an observation window of the last w prompt tokens (SnapKV-style), compute the attention weights and the output a.
2. Compute score_j = Σ_t (p_j/(1−p_j))² · ‖a − v_j‖². The squared form is chosen for the kernel and gives the same ranking as the unsquared proxy at w=1.
3. Apply MaxPool1D over the scores, and never evict the window tokens.
4. Evict the k lowest-scoring tokens. Scoring costs O(nd).

The kernel has three fused Triton passes:

• a FlashAttention-2-style forward pass that produces the log-sum-exp of the logits;
• a scoring kernel that recomputes logits per key tile and expands ‖a−v‖² = ‖a‖² + ‖v‖² − 2⟨a,v⟩, so each V tile is read once;
• a split-K merge.

The output matches the PyTorch reference within BF16 round-off.

Evidence

The guarantee is F(Ĵ) ≤ F(J*) / [c(1−ε)(1−kε)]. It requires small attention weights in the candidate pool and the "cone condition", meaning the residuals a − v_i point in roughly the same direction. The authors checked the cone condition at 128K on Llama-3.1-8B-Instruct, MegaBeam-Mistral-7B-512K and Qwen2.5-7B-Instruct-1M:

A brute-force check on small subsets puts the real ratio much lower: median ≤ 1.16 and 95th percentile ≤ 1.43 across all three models.

The fetched text does not include the RULER or LongBench accuracy numbers. It states only that DropKV has the highest accuracy and the lowest latency among the eviction baselines, and is faster than the dynamic (uncompressed) cache baseline.

How to use it

• Code is at https://github.com/AozhongZhang/DropKV.
• The authors say it is also available in NVIDIA/kvpress, which is the likely route if you already use that library.
• No install commands, licence or API details appear in the fetched text.

Limits

• Early layers: the guarantee is weakest here. The cone condition holds on about 16% of Llama layer 0 and below 10% of Qwen2.5 layers 0–3. Qwen2.5 is the weakest model overall.
• Scope of the theorem: it covers only a single query over a restricted candidate pool (e.g., the lowest-attention tokens). The multi-query version relies on a proposition in the appendix.
• Prefill only: the 9.9% end-to-end gain is a matched-batch prefill measurement. Decode-time gains are not quantified in the fetched text.
• Short contexts: the speedup is small (1.8× at 4K).
• Permanent eviction: evicted tokens are gone. Dynamic sparse attention (Quest, SparQ) and compression/offload methods (ShadowKV) keep the full cache, and the authors treat them as orthogonal rather than comparing against them.
• Truncated text: the fetched page ends partway through Section 4, so the benchmark tables and ablations were not available for this analysis.