Research map / Architectures and efficiency / Attention and transformers

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

NeurIPS 2026 · Architectures and efficiency › Attention and transformers · approach: KV cache eviction and compression

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes DropKV, a KV-cache eviction method that decouples the NP-hard joint perturbation minimization into per-token scoring with a constant-factor guarantee under a cone condition, implemented with fused Triton kernels.

Problem

KV-cache eviction for long-context LLMs requires minimizing attention-output perturbation from evicting tokens, which is an NP-hard combinatorial problem, so existing methods use suboptimal heuristics or are hard to kernelize.

Approach

Score each token independently by its exact single-token attention-output perturbation (p_j/(1-p_j))·||a - v_j||, aggregated over an observation window, and evict the lowest-scoring tokens; prove a constant-factor approximation to the joint objective under an empirically verified cone condition, and compute scores with fused Triton kernels that avoid materializing the attention matrix.

Key results

• On RULER at 128K and 5% budget, DropKV reaches average 82.00 on Llama-3.1-8B-Instruct, 83.77 on Qwen2.5-7B-1M, and 85.40 on Mistral-7B-512K, 2.35-4.03 points above the best baseline.
• On LongBench at 5% budget, DropKV averages 45.51 (Llama-3.1-8B), 42.66 (Qwen2.5-7B-1M), and 36.22 (Mistral-7B-512K), gaining 0.68-0.94 over the strongest baseline.
• The fused Triton scoring kernel is 19.8x faster than the PyTorch reference at n=128K, reducing scoring scratch memory from about 9 GB to about 17 MB.

Surprising findings

• The empirical approximation ratio on small brute-force subsets (median 1.16) is far smaller than the worst-case theoretical bound (median factor about 10-12).
• Cone condition holds only on 76.5% of triples for Qwen2.5 versus about 91% for Llama and Mistral.

Limitations

• Current Triton implementation accelerates only prefill scoring; decode-time kernel is future work.
• Theoretical guarantee relies on small attention weights and a cone condition that holds only on a majority of (layer, head, query) triples.
• Per-step decode latency is bandwidth-bound and comparable across eviction methods, so serving gains are mainly from prefill.

Experimental setup

Datasets: RULER LongBench

Benchmarks: RULER LongBench

Metrics: accuracy average score scoring latency prefill speedup end-to-end latency time to first token

Baselines: SnapKV PyramidKV StreamingLLM KeyDiff CAKE CriticalKV AnDPro AdaKV

Builds on: SnapKV CriticalKV AnDPro FlashAttention-2

Closest papers by meaning

• Taming the Fragility of KV Cache Eviction in LLM Inference (ICLR 2026 · similarity 0.91)
• CAKE: Cascading and Adaptive KV Cache Eviction with Layer Preferences (ICLR 2025 · similarity 0.91)
• Ada-KV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference (NeurIPS 2025 · similarity 0.90)
• Get More with LESS: Synthesizing Recurrence with KV Cache Compression for Efficient LLM Inference (ICML 2024 · similarity 0.90)
• ForesightKV: Optimizing KV Cache Eviction for Reasoning Models by Learning Long-Term Contribution (ICML 2026 · similarity 0.90)
• Value-Aware Stochastic KV Cache Eviction for Reasoning Models (NeurIPS 2026 · similarity 0.90)