DropKV is a KV-cache eviction method. It scores each cached token by how much removing it would change the attention output, then drops the `k` lowest-scoring tokens to fit a memory budget.

How does DropKV differ from H2O or SnapKV?

H2O and SnapKV rank tokens by accumulated attention weight. DropKV multiplies the weight by the distance between the token's value vector and the attention output, so a heavy token that only repeats the average can be dropped.

Does the constant-factor guarantee mean DropKV loses almost no accuracy?

No. The bound limits the output shift relative to the best possible eviction set, and only when two conditions hold. The paper measures a median realized factor of about 10 to 12, and accuracy is reported separately on RULER and LongBench.

Why does the Triton kernel matter?

A direct implementation builds dense window-by-context-by-dimension tensors. The fused kernel streams tiles and keeps scratch memory near 17 MB at 128K tokens, instead of about 9 GB, which removes a prefill memory bottleneck.

LLM· 2026-10-18

DropKV paper — Residual-output perturbation scoring for KV-cache eviction — What does it mean?

Jargon

KV cache: The stored key and value vectors of every earlier token, so decoding does not recompute them. Its size grows with context length. How it works
Attention weight: The softmax score p that says how much one cached token contributes to the current output. All weights for one query add up to 1.
Value residual: The difference a - v between the attention output a and one token's value vector v: how far that token sits from the blend.
Prefill: The first pass that reads the whole prompt and builds the KV cache, before any new token is generated. Prefill vs decode
NP-hard: A problem for which no known method avoids trying a number of combinations that explodes as the input grows. Picking the best k tokens to drop together is one.
Cone condition: The assumption that the residuals of the tokens up for eviction all point within a limited angle of one direction, so removing several of them cannot cancel out.
Log-sum-exp (LSE): The log of the softmax denominator. A FlashAttention-style forward pass already produces it, which lets a kernel recompute any attention weight tile by tile. FlashAttention

The news. In October 2026, the paper DropKV: Decoupling Residual-Output Perturbation for Near-Optimal KV-Cache Eviction proposed ranking cached tokens by the exact amount that removing each one changes the attention output. The authors report the highest average RULER accuracy of the methods they compare at a 5% cache budget, a scoring kernel up to 19.8× faster than a PyTorch reference, and a proof that their shortcut stays within a constant factor of the best possible choice under two conditions. Read the paper →

Picture the attention output as one smoothie blended from every cached token. Each token is a cup, and its attention weight p is the share of the pitcher that came from that cup. When GPU memory runs out, you must pour some cups away and re-blend the rest. Methods such as H2O and SnapKV rank cups by share. But taste matters as much as share: a cup that makes up half the blend yet tastes exactly like the blend can leave without changing anything, while a thin cup of a very different flavor can swing the whole pitcher.

The math says the same thing exactly. If token j is removed and the remaining weights are renormalized, the output moves by p_j / (1 − p_j) × (a − v_j) (Lemma 1 in the paper), where a is the original output and v_j is the token's value vector. The cost of evicting a token is its share times its distance from the blend, not its share alone. DropKV uses the length of that shift as the token's score. Every ingredient comes from the same softmax that the attention scores step already computes, so the score can be known before any eviction decision is made.

Choosing the best set of k cups to remove together is hard: the paper shows it is NP-hard, because removing several cups re-scales all the remaining shares at once. DropKV takes a shortcut. It scores each cup alone and removes the k with the smallest scores, ignoring how removals interact. That sounds crude, but the paper proves a bound. If the evictable tokens have small weights and their residuals a − v_j all lie in one cone, the shortcut's output shift is at most 1 / (c (1 − ε)(1 − kε)) times the shift of the best possible set.

The authors checked the cone condition on real 128K-token prefills. The cone condition held on 91.2%, 91.1% and 76.5% of (layer, head, query) cases for Llama-3.1-8B-Instruct, Mistral-7B-512K and Qwen2.5-7B-1M, and both preconditions of the theorem held on 89.1%, 87.5% and 73.4%. Read the guarantee as a worst-case ceiling: among cases where both preconditions held, the realized factor had a median of about 10 to 12, so the bound is loose, and it limits output shift, not answer accuracy. In practice the score is summed over a window of the last w queries, as SnapKV does, so a token that matters to any recent query stays.

Eviction family	Ranks tokens by	Uses the value vector?
Sliding window, StreamingLLM	Position (recent tokens plus initial attention sinks)	No
KNorm	Key norm	No
H2O, SnapKV	Accumulated attention weight	No
CriticalKV	A loose upper bound on the output shift	Yes, through the bound
DropKV	The exact single-token output shift, summed over a query window	Yes, directly

Worked example (illustrative numbers, one-dimensional values so the arithmetic is visible). A head caches four tokens with attention weights 0.50, 0.30, 0.15 and 0.05 and values 5, 5, 15 and 5. The output is a = 0.5×5 + 0.3×5 + 0.15×15 + 0.05×5 = 6.5, so the residuals |a − v| are 1.5, 1.5, 8.5 and 1.5. The scores p/(1−p) × |a − v| are 1.50, 0.64, 1.50 and 0.08. You must evict two tokens. Ranking by attention weight removes tokens 4 and 3; tokens 1 and 2 are left, they re-blend to 5.0, and the output shifts by 1.5. Scoring with DropKV removes tokens 4 and 2; tokens 1 and 3 are left and the output becomes (0.5×5 + 0.15×15) / 0.65 ≈ 7.31, a shift of about 0.81. Token 3 is the thin cup of a very different flavor: its weight is low, yet removing it hurts. In this toy case DropKV's pair is also the best of all six possible pairs.

Scoring is only worth it if it is cheap, and the naive version is not. Computing p_j and a − v_j for every token and every window query builds dense tensors of size window × context × head dimension. DropKV replaces them with fused Triton kernels in the style of FlashAttention. The kernels stream through key and value tiles, recompute each attention weight from the log-sum-exp the forward pass already produced, and add to each token's score on the fly. Expanding ‖a − v‖² into ‖a‖² + ‖v‖² − 2⟨a, v⟩ lets each value tile be read once.

The paper reports, at 128K tokens, window 8 and a 5% budget on an A100-80GB, scoring scratch memory of about 17 MB instead of about 9 GB, and a scoring step 19.8× faster than the PyTorch reference (1.8× at 4K tokens). End-to-end prefill at matched batch size is up to 9.9% faster. The gain sits in prefill: decode time is set by the size of the cache after eviction, which is similar across eviction methods. On RULER at a 5% budget the paper reports the highest average accuracy on all three models it tests: 82.00 (Llama-3.1-8B-Instruct), 83.77 (Qwen2.5-7B-1M) and 85.40 (Mistral-7B-512K), 2.35 to 4.03 points above the best competing baseline. These are the authors' own measurements and have not been independently reproduced.

Goes deeper in: LLM Internals → KV Cache → Memory Cost

Related explainers

From Memory Budgets to Risk Targets: decides how much to evict; DropKV decides which tokens go.
iS-KV: keeps old KV states as low-rank coefficients instead of deleting them.

Frequently Asked Questions

Check what you knowMap your AI & GPU knowledge across every track — free, role-based