Random Attention: When KV-Cache Eviction Science Meets a Coin Flip and Loses

A paper from Salesforce AI Research landed in September 2026 with a claim of the best kind — a negative result with receipts: across four reasoning models and six reasoning tasks, a KV-cache eviction policy that literally walks the trace flipping a coin matches the strongest learned evictor in the literature, while serving 32–43% higher throughput in vLLM because it never computes a score at all¹². If you build serving infrastructure, this is not a curiosity. It is a direct audit of what the last three years of "which cached token will matter later" research actually purchased — and the answer is: almost nothing, on reasoning-trace workloads — the long self-generated traces agents spend most of their tokens on, though the paper never tests agentic traces themselves.

This guide takes the claim apart at the level we care about: what the outlier-centric eviction literature says it is optimizing, what the paper actually measured, why a random policy can tie a learned one (and the settings where it provably cannot), what would falsify the whole reading, and when you should still pay for a learned evictor. Provenance first, as always: this is Salesforce AI Research plus UIUC, with authors including Heng Wang and colleagues¹. A vendor research lab publishing "your sophisticated scoring pass is worthless" about a component it does not sell has a decent incentive profile — but note the paper's own efficiency claims depend on its vLLM integration being the fair baseline, and Salesforce ships serving stacks, so read the throughput section with the usual one-vendor caveat.

1. What outlier-centric KV eviction claims to solve

Every method in the eviction family shares one premise: a cached token's future importance is estimable from statistics of the cache itself, and keeping the top-scoring tokens under a hard budget recovers most of full attention's accuracy. The scoring signal is where the literature diverges, and each generation of papers is a strictly better score — with the mechanism stated precisely because the whole article turns on what each signal actually measures:

In prose:

• H2O (2023) — accumulated attention: keep the tokens that have received the most attention mass since they entered the cache; the "heavy hitters" are assumed to be the load-bearing ones³.
• StreamingLLM (2023) — no score at all, but the structural prior everyone copied: keep the first few attention sink positions plus a contiguous recency window⁴.
• SnapKV (2024) — attention from a recent window of queries, max-pooled over neighboring positions: the idea being that what recent queries looked at predicts what future ones will⁵.
• R-KV (2025) — SnapKV-style attention mixed with a redundancy penalty (mean cosine similarity of a key to all other cached keys), so a restated thought is not kept twice⁶.
• VaSE (2026) — scores values rather than keys: a small fraction of value states has abnormally large magnitude, and VaSE's own ablation shows evicting the largest-magnitude values collapses GSM8K to 14.3% — 38.9 points below random eviction — because the model enters repetitive reasoning loops⁷. This is the purest outlier-protection argument in the family: the distribution has heavy tails, and the tails are load-bearing.
• TriAttention (2026) — position-dependent key statistics: pre-RoPE query/key vectors concentrate around fixed non-zero centers, so key importance is a calibrated trigonometric function of Q/K distance, plus Q/K norms⁸.

Note what this progression looks like from the outside: quantile logic ("keep the attention/heavy-hitter tail"), spectral arguments (cosine-similarity redundancy as subspace coverage, and the CurDKV line that VaSE builds on literally uses random-projection leverage scores — an SVD-flavored statistic), and outlier-magnitude arguments ("the skewed tail of value norms must be preserved"). The framing is distributional: the cache contains a few high-information outliers in a sea of noise, and eviction is a feature-selection problem — rank tokens by importance, keep the tail.

Three years of incremental benchmarks were built on that framing. The Salesforce result is the cleanest yet to hold everything else fixed and ask: how much does the ranking itself — the actual output of all this machinery — contribute?

2. The counter-evidence: on reasoning traces, the ranking buys nothing

The method under test is almost insultingly simple. Random Attention does exactly two things:

1. Protect the question. Every prefill position — system prompt, chat template, the question itself — is never evicted.
2. Scatter the rest, per head. Every remaining position gets an i.i.d. uniform random score; each KV head independently keeps its top-K. No statistics, no calibration, no scoring pass — one RNG draw and one top-K per eviction round².

The evaluation grid: Qwen3-4B/14B/32B and Phi-4-reasoning across MATH500, GPQA-Diamond, AIME 2025/2026, HMMT, and LiveCodeBench-v6, at a fixed cache budget typical of 4× compression (~3× for LiveCodeBench), every cell gated with paired, problem-clustered bootstrap CIs and sign tests². The headline results, recomputed here from the paper's Table 1:

• Random Attention beats SnapKV by 4.3–35.3 points depending on model and task (e.g. Phi-4-reasoning LiveCodeBench: 0.667 vs 0.314 — a 35.3-point gap).
• It statistically ties or beats VaSE and R-KV on math and science tasks across the main grid's three models — the Qwen3-14B appendix grid is the exception, with VaSE significantly ahead on AIME — and is "significantly ahead in 31 of the 60 baseline comparisons" in the main grid¹.
• Against TriAttention — the strongest baseline — it ties on most cells; TriAttention's single significant win in the whole main grid is code reasoning on Qwen3-32B, by about three points, which the paper traces to prompt length, not selection quality².
• Full attention is still the ceiling (e.g. Qwen3-4B MATH500: 0.939 full vs 0.874 random-at-4×) — so eviction still costs accuracy; the paper's claim is that no selector recovers more of it than a coin flip does, once the prompt is protected.

Then the controlled experiments, which is where the paper earns its keep:

The prompt is the fragile part. Prior methods disagree about whether the prompt survives: TriAttention pins it by rule; SnapKV, R-KV and VaSE leave it to the score, keeping only attention sinks. Give every method the same keep-the-prompt rule, and most of the inter-method gap vanishes. The payoff of the rule is ordered exactly by how much prompt each score had been silently losing: SnapKV, which retains the least of the question, gains up to +22.5 points (Phi-4 GPQA-D); R-KV, which already kept most of it, moves by at most ~2 points. And the signal-free rows make the point brutally: a recency window without prompt protection scores 0.246 on Qwen3-4B MATH500; with the rule, 0.843 — a +59.7-point swing that dwarfs every inter-selector difference in the table². The same confound, the paper argues, explains why earlier papers reported random baselines falling far behind scored selection: their random baselines were losing the prompt².

The trace protects itself. Reasoning traces are redundant at two levels. In the text, the model restates what it is still using. And across heads: every KV head holds its own copy of every token, and eviction decides per head which copies die. A planted-fact probe quantifies the cross-head pooling: the best single retrieval head of Qwen3-4B yields a planted value in only a small fraction of trials on its own; several heads together retrieve almost always; the pooling is superadditive — the shape and location of surviving copies does not matter, only whether some usable copy survives somewhere². Two further probe details deserve the mechanism-level read: dealing the fact's tokens out one per head, so that no two consecutive tokens share a head and no head holds a readable span, barely moves retrieval — contiguous blocks only start to hurt when the budget leaves a head fewer than ~4 blocks, i.e. what matters is blocks per head, not block length. And a shared random draw (the same positions in every head — the opposite of independent) scores within 0.3 points of Random Attention at 4× and 8× on real traces, because text-level restatement already carries most of the load; the cross-head level only carries what the text does not restate².

Needle-finding is the one real skill — and it does not transfer. A passcode-stated-once-never-restated probe: Random Attention never reproduces the passcode; R-KV, the best needle-finder, finds it most of the time. But R-KV leads only one column of the main grid, while TriAttention, the strongest overall baseline, recovers almost nothing on the needle probe. Aggregate strength and needle-finding are dissociated — and reasoning traces rarely state a load-bearing fact exactly once².

Independent convergence: VestigeKV. A different group, publishing within the same week (arXiv:2609.03949, Sept 3, 2026), reached a complementary negative from the other direction: on a NoPE-MLA model, selection by observed attention — the H2O/SnapKV mechanism in its purest form — collapses to 0.00–0.33 needle retrieval on long-held caches, because a token's importance has not yet been observed at eviction time⁹. Their fix is not a better score but a different topology: the top-m rows stay in an attended tier, everything else moves — exactly, never deleted — to a GPU-resident archive. The convergent lesson across both papers: the interesting design space is not "better importance estimates" but what you structurally never lose (Random Attention: the prompt; VestigeKV: everything, just possibly off-tier) plus what actually determines recoverability (coverage and redundancy, not rank).

The capacity arithmetic behind the throughput deltas. Why does any of this show up as 30–40% throughput in a serving engine? Because at long generations the KV cache — bytes on HBM, not FLOPs — is the requests-in-flight limiter, and eviction shrinks the bytes. Per-token KV cost in fp16 is 2 × (K+V) × 2 bytes × KV heads × head dim × layers:

On a 141-GB H200 minus weights and activations, the compressed per-request footprint is what lets the request pool hold many more sequences than full attention could. That capacity gain is identical for every evictor — the bytes saved depend on the budget, not on the policy. So where does Random Attention's residual edge come from? Entirely from deleting the scoring pass.

Stall arithmetic, derived from the paper's Table 4. Served in vLLM on one H200 (1k-token prompts, 32k-token generations, 128 requests — capped at 96 on Qwen3-32B), Random Attention's throughput is 2,046 vs 1,494 tok/s (Qwen3-4B), 1,737 vs 1,212 (Phi-4-reasoning), 1,819 vs 1,303 (Qwen3-14B), 923 vs 700 (Qwen3-32B) against TriAttention — recomputed: +37/+43/+40/+32%, matching the abstract's 32–43%, and 1.6–2.7× full-attention throughput². Where does the margin physically come from? Take Qwen3-14B: 128 requests × 32,768 tokens at 1,819 vs 1,303 tok/s implies wall-clock times of roughly 2,306 s vs 3,219 s — a 913-second delta over a workload containing 128 × 32768/64 = 65,536 compression events. That is ~14 ms of whole-batch penalty per compression event attributable to the scorer (913 s across 65,536 events) — compare the paper's own accounting (910 s of extra wall-clock over about 62k compressions — about 15 ms of whole-batch waiting per compression event, on this model, against well under a millisecond for Random Attention; treat our derived per-event figure as an order-of-magnitude sanity check, since the delta also folds in second-order batch-composition effects)². The structural reason: each eviction round costs the paper's measured 0.30 ms under Random Attention, which only compacts, versus 1.47–1.64 ms under TriAttention, which scores first — walking vLLM's block tables layer by layer over candidate keys, because fused attention kernels do not materialize the attention statistics a scorer needs. And vLLM compresses at a synchronization point between batched decode steps: with 128 concurrent requests each compressed roughly every 64 of its own tokens, some request gets compressed at nearly every step, and all requests wait while one of them scores. A few milliseconds times tens of thousands of events eats a third of your throughput².

3. The math: why can a random policy tie a learned one?

A random policy tying a learned one should feel wrong. Write out when it cannot, and the agent setting starts making sense.

The setting where random loses badly: low-rank / strong-outlier distributions. Suppose the cache's utility mass is concentrated: a fraction of positions carries almost all future-attention mass (needles, planted facts, rare key statistics in the VaSE sense), and the rest is exchangeable noise. A learned selector that can rank importance captures mass ≈ its true top-K; a random K-subset captures the base rate. On needle probes this is exactly what happens — Random Attention's passcode retrieval is zero, because a value stated once has survival probability K/T per head (budget K over T candidates), and with per-head retention p the probability that all H KV heads drop it is (1−p)^H. Formally, the paper cites a companion result (Wang, 2026) proving random caches must lose at pointer-chasing when nothing is redundant². If load-bearing content is stated once in a long context, a learned signal has real headroom. Needle-in-haystack RAG lives exactly here — and this is the regime the outlier-centric literature believes it is in.

Why the reasoning/agent setting is not that regime. The objective term outlier methods optimize (hit-rate on the high-information tail) is orthogonal to what actually predicts end-task accuracy on reasoning traces: retainment of (i) the prompt, and (ii) at least one restated copy of every working value. Consider cross-head redundancy arithmetic for a GQA model with H KV heads (Qwen3-4B: H = 8) and per-head retention p over the trace:

(Computed: 0.75^8 = 0.100, 0.5^8 = 0.0039.) At 4× compression, before text-level restatement even enters, each trace token survives in at least one head with probability 1 − 0.75^8 ≈ 0.900 — and reasoning traces additionally restate working values in text, which is exactly the redundancy R-KV's cos-similarity penalty was designed around⁶. So the effective retention of anything the model currently uses is near 1, no matter how the retained sets are chosen — as long as the draws are independent across heads, which random selection guarantees and a shared deterministic score does not. That is the sharpest mechanistic point in the paper's analysis: a deterministic top-K score applied identically across heads produces correlated survivors — if the score is wrong about a token, it is wrong everywhere simultaneously. Independent per-head random draws de-correlate the failure. The learned signal has to be right about rank; the random signal only has to be right about coverage.

A worked example makes the correlation failure concrete. Take VaSE's stochastic fill (sampling positions with probability proportional to their SnapKV score, independently per slot) versus a deterministic top-K. For a token the score underestimates — a working value the recent-window attention has not yet visited — the deterministic policy assigns it rank below cutoff in all 8 heads at that eviction round: death probability 1. Under independent draws, survival per head is p ≥ (1 − (1 − ᾱ/Z))^K, strictly positive — every token keeps a nonzero chance across every round. The VaSE authors themselves proved this property in their own paper⁷, which is quietly funny: the stochastic half of VaSE is more similar to Random Attention than to its deterministic scoring half. Conversely the failure case for random: a needle stated once and never restated needs concentrated retention (one head keeping the whole span beats every head keeping scattered fragments — except the probe showed even that is wrong: scattered copies pool fine across heads). What random cannot do is guarantee retention of a specific span with probability above the base rate; what deterministic scoring cannot do is spread its errors. Reasoning traces are built so the first failure mode does not occur (restatement) and the second is fatal when it does (a dropped prompt). That asymmetry, not scoring quality, is the paper's result.

And in bytes, eviction is not optional on these workloads — a 32,768-token trace at Qwen3-4B costs 4.5 GiB of KV (32B: 8.0 GiB) per sequence, which on a 141-GB H200 is the requests-in-flight constraint. The bytes math is what makes the scoring-pass overhead the only differentiator between evictors — and the scoring pass is the only component random deletes.

Now the argument, stated as an argument and not a fact: the outlier-centric line (H2O-heavy-hitters, VaSE-value-tails, CurDKV leverage scores, TriAttention positional statistics) inherited its evaluation methodology from long-context benchmarks (perplexity-style and long-input QA) where the "needle" framing is literal — one fact, stated once, inside a long haystack. Reasoning and agentic traces invert the data: short prompt, long self-generated output, where the cache fills with the model's own restated, head-duplicated working state. It is a reasonable hypothesis — supported by this paper's Tables 1 and 2, by the planted-fact probe, and convergently by VestigeKV's independent finding that selection by observed attention (H2O, SnapKV) collapses to 0.00–0.33 needle retrieval on a NoPE-MLA model where importance has not yet been observed⁹ — that a large share of the eviction literature is over-indexed on a trace distribution its scoring signals were never designed for, and that benchmark selection, not signal quality, drove the reported gaps. That last sentence is our inference, not the paper's claim; the paper only proves it for its grid.

4. What would falsify "random is enough"

The honest failure modes, in decreasing order of our worry:

1. Workload scope. Everything above is reasoning traces: short prompt, long self-generated output, budget at 2–4× compression. A needle-in-haystack RAG workload — long input, many documents, facts stated once — is exactly the low-rank regime where §3 says random must lose; the paper's own passcode probe is a miniature of this and random scores zero there. Anyone reading "random eviction is enough" as a universal claim is over-reading the paper.
2. The prompt-pinning confound could be most of the paper. If the finding reduces to "the prompt matters and prior baselines dropped it," much of the delta is a benchmark-construction artifact, and a learned scorer with prompt protection might beat random on workloads with long, partially-useful prompts. The paper anticipates this: under matched protection, protected baselines still trail random by 1–3 points on several cells — a small but real residual in random's favor. But TriAttention's code win on Qwen3-32B shows learned signals are not literally worthless.
3. Single-framework deployment. The 32–43% throughput margin is measured in one vLLM integration, and the paper concedes TriAttention's in-framework scorer was not fused ("the threefold gap to TriAttention here reflects an unfused re-implementation of its scorer"). A fused scorer kernel could reclaim much of the efficiency margin; the accuracy parity, though, is kernel-independent.
4. Trace bias. The six tasks are math, science, code — domains where models restate heavily. Agentic traces with tool-call outputs (JSON payloads, stack traces, stale retrieved documents) contain far more once-stated, never-restated content than math does; the passcode probe suggests random will drop it. Tool-call gaps are also temporally structured in ways (interaction boundaries) that a learned signal could exploit at near-zero cost.
5. Replication generally. One paper, one lab, v1 at submission, four Qwen-family models plus Phi-4 — the model diversity is thinner than the task diversity. SGLang replication, non-Qwen families, and 2027's agent-trace benchmarks are all still open.

5. Practical guidance: when to pay for learned eviction

When hit-rate-per-byte stops mattering, stop paying for it. The decision, as a matrix over the two workload axes that §3 showed actually matter:

In prose:

• Reasoning-model serving under a memory budget, heavy trace redundancy, short prompts: pin the prompt (and sinks), evict the trace uniformly at random per head. It needs no calibration, no tuning, no scoring pass, and it is the floor any new selection signal must beat at matched budget and matched prompt protection². The 32–43% throughput margin is real in vLLM today.
• Long-context retrieval workloads (long input, short output): the needle regime is real, learned signals earn their score there, and VestigeKV-style query-independent archive-tiering shows a third path — move to a tier instead of deleting — which beats both random and scored eviction on needle tasks⁹. Note the paper's own scoping sentence: its setting differs because "a short prompt is followed by a long generation, so what fills the cache is the model's own trace"².
• Memory-bandwidth-bound decode with low prefix sharing: per-sequence eviction quality still bounds accuracy per byte; if your traffic does not share prefixes and your sequences are short, eviction buys little and mostly adds risk — but if you do compress, the scoring-pass overhead the paper quantifies (a few ms per eviction round × a compression every few decode steps × whole-batch synchronization stalls) is a serving-throughput line item, so budget it.
• Agent traces in production: heavy prompt/system-prefix reuse, tool-call boundaries, restated plans — mostly the random-friendly regime, but the tool-result payloads are your needle risk. If your agent reads a number out of a tool response fifteen turns later, that value is stated once; a content-dependent signal (R-KV-style accumulated attention) is the known way to keep it. Characterize your traces before choosing.

The transferable lesson is not "random wins." It is that the paper reframes the problem: eviction accuracy is decided by what you protect, not by how you rank the rest. The open questions it leaves — budgeting long partially-scaffolded prompts (code prompts alone ran 6× the tokens of MATH500 under the same tokenizer, up to half the budget²) and recovering rare once-stated facts — are precisely where the next round of real selection work should go. And if your eviction pipeline currently has no random-with-prompt baseline, you do not know how much of your accuracy your scorer is actually buying. Probably almost nothing. Measure.

Sources