The scoring pass inside your KV cache compressor is not earning its keep. A team from Salesforce AI Research and the University of Illinois Urbana-Champaign replaced it with a coin flip — keep the prompt, evict everything else uniformly at random — and matched the strongest published evictor across four models and six reasoning tasks while serving 32-43% more tokens per second in vLLM, precisely because it computes no score at all.
If you size GPU capacity for reasoning workloads, that is your new baseline. Not the best method. The dumbest one that works. Any vendor selling "intelligent cache compression" as a differentiator now has to beat a random draw, and the paper's own numbers say most of them do not.
What Salesforce Actually Removed
They removed the entire idea that you need to know which cached tokens matter.
KV cache eviction is the practice of throwing away key-value pairs mid-generation so a long chain of thought does not exhaust GPU memory. Every method in the literature works the same way: score each cached token by some estimate of its future importance, keep the top-K, discard the rest. SnapKV watches recent attention. R-KV accumulates attention over the whole history. TriAttention — the current state of the art, from MIT, NVIDIA and Zhejiang University — computes importance in the pre-RoPE space to dodge a rotation artifact that corrupts the ranking.
Random Attention does one thing differently. It pins the prompt — system message, chat template, question — with infinite priority, then assigns every remaining cached position "an i.i.d. uniform random score," and each KV head independently keeps its top-K. There is no attention statistic, no ranking model, no scoring kernel. There is a random number generator.
On Qwen3-4B at a 1,024-token budget on MATH500, that scores 0.874 against TriAttention's 0.864, R-KV's 0.810 and SnapKV's 0.703. On AIME at a 4,096-token budget: 0.610 against TriAttention's 0.592 and R-KV's 0.494. On Phi-4-reasoning it beats TriAttention on three of the five tasks in the main table — 0.910 vs 0.891 on MATH500, 0.662 vs 0.633 on AIME. Across the 60 head-to-head cells in that table, paired tests put the random policy significantly ahead in 31 — and significantly behind in exactly one.
Be clear about what "matched" means here, because the paper is: this whole family still costs you accuracy against full attention. On Qwen3-32B, full attention scores 0.950 on MATH500 and 0.886 on LiveCodeBench. Random Attention scores 0.891 and 0.806. That is a 6-point and an 8-point haircut, and TriAttention's numbers (0.887 and 0.834) sit in the same band. Compression buys memory with correctness. The finding is not that eviction is free. It is that the expensive half of eviction is free to delete.
The Prompt Is the Fragile Part. Everything Else Restates Itself.
The mechanism is the most useful thing in the paper, because it tells you what to protect in any cache policy you already run.
The authors ran the ablation that nobody had bothered to run: same random eviction, prompt protection switched off. On Qwen3-4B, MATH500 collapses from 0.874 to 0.459 and GPQA-Diamond from 0.530 to 0.231. Their summary is blunt — "losing the prompt is catastrophic and cutting the trace at random is not." Once every method is given the same rule, "most of the gap between them disappears." The published leaderboard of KV evictors was, to a first approximation, a leaderboard of which scoring signal happened to protect the question.
That also reconciles this with the prior literature, which said the opposite. Earlier evaluations of KV compression on reasoning reported that "random or recency baselines fall far behind scored selection" — and the paper cites them. They do fall far behind. Without the prompt pinned.
The reasoning trace survives random deletion because it is redundant twice over. In the text, the model restates what it is still using as it works. Across attention heads, each head keeps its own copy. The paper measures the second effect directly: for a planted fact, "the best single head yields the value in 3% of trials, the next in 1%. But ... the same two heads together yield the fact in 60% of trials, three heads in 83%, and all eight in 99%."
That is why a random draw is enough. You are not trying to keep the copy of a fact. You are trying to keep any of eight copies, and uniform sampling across independent heads does that well.
Where the Randomness Breaks: A Fact Stated Once
There is one failure mode, it is sharp, and it is the reason you should not turn this on for a retrieval workload.
The authors planted a passcode in the trace "once, 57 compression rounds before the question" — thousands of tokens back, never restated. Random Attention retrieved it 0.000 of the time. R-KV, whose score accumulates attention over the whole history, found it 0.836 of the time. VaSE managed 0.344. The signal that contributes nothing on math contributes everything here.
Their own framing: "The one case a signal-free policy cannot cover is a fact stated once, never restated, and needed much later." They argue it is rare on real reasoning traces. On a reasoning trace, agreed. On a long RAG context, an agent transcript full of tool outputs, or a document summarisation job, that is not an edge case — it is the entire workload. This paper evaluated math, science and code reasoning. It did not evaluate long-context retrieval, and you should not extrapolate it there.
The second soft spot is code. LiveCodeBench prompts average 557 tokens against roughly 90 for MATH500, so a pinned prompt eats up to half the budget and leaves less room for the trace. That is where TriAttention keeps a real ~3-point edge on Qwen3-32B — and the authors attribute it to prompt length, not to a smarter score. Their own note is that "much of a code prompt is scaffolding (I/O formats, harness instructions) that a smarter rule might compress rather than pin whole."
The Throughput Is Real Because the Scoring Pass Is Gone
The speedup is real, but not for the reason a kernel timing suggests — and the distinction decides whether you should expect it on your own stack.
One eviction round costs 0.30 ms under Random Attention and 1.47-1.64 ms under TriAttention. Multiply that 1.2 ms gap by how often it fires and you get a small fraction of the observed difference, not the whole of it. The served cost is far larger, for two reasons the microbenchmark does not capture. vLLM performs each compression "at a synchronisation point between batched steps, so all 128 requests wait" — the scorer does not amortise across the batch, it stalls it. And TriAttention "makes an additional pass over the candidate cached keys, through vLLM's block tables and layer by layer, to compute its score, whereas Random Attention performs only the shared compaction step." Walking paged KV in order to score it costs more than the scoring arithmetic does. The authors put the real figure at "about 15 ms of whole-batch waiting per compression" — roughly twelve times the isolated kernel gap.
So the expensive thing is scoring under paging, not scoring in the abstract. That is the same constraint the NVIDIA post below describes, and it is the reason to check how your runtime pages before assuming the gain transfers.
Measured on one H200 at a 2,048-token budget with 11k-token prompts, 32k-token generations and 128 concurrent requests:
| Model | Full attention | TriAttention | Random Attention |
|---|---|---|---|
| Qwen3-4B | 1,296 tok/s | 1,494 | 2,046 |
| Phi-4-reasoning | 780 | 1,212 | 1,737 |
| Qwen3-14B | 925 | 1,303 | 1,819 |
| Qwen3-32B | 346 | 700 | 923 |
Put a price on the middle row of that table. Together AI lists on-demand HGX H200 at $5.99 per GPU-hour (H100 at $3.99). One H200 running Qwen3-32B at 923 tok/s produces 3.32M output tokens an hour, or $1.80 per million. The same GPU under TriAttention produces 2.52M, or $2.38 per million. Under full attention, 1.25M — $4.81 per million.
So the compression decision is worth about $3.00 per million output tokens on this workload, and roughly $0.58 of that — a quarter of your remaining bill — is the scoring pass you can now delete. If you are buying reserved capacity against a reasoning roadmap, that is a line item, not a footnote. It is the same arithmetic problem as reading a GPU hourly rate without the utilisation behind it, and the same reason a headline tokens-per-second figure only means something at a stated batch size.
You Cannot Flip This On in Stock vLLM
Nothing in this ships in your serving runtime today, and the gap is the most under-reported part of the story.
Read the repository carefully. The code is Apache 2.0, and the serving benchmark implements "Random Attention as a selector inside TriAttention's vLLM 0.19 runtime (their paged-KV compression machinery, our selection rule)." Read that twice. The result does not say delete your compression stack. It says the cheap half — pinning the prompt and compacting paged KV — earns the gain, and the expensive half — the scorer bolted on top — earns nothing. You still need somebody's paged-KV compression machinery. Salesforce borrowed the incumbent's.
That machinery is hard for a reason NVIDIA's own efficient-AI lab wrote up in June 2026. Production servers use FlashAttention, which "never materializes the N×N score matrix in HBM" — so a method that needs attention scores has to fall back to eager attention and hand back the speed it was chasing. Worse, in paged attention "a block can be freed only when it is completely empty," and eviction scatters what is left — "evicting 14,400 of 16,000 tokens leaves 1,600 survivors spread over the roughly 1,000 blocks originally allocated." The result: "almost every block keeps at least one survivor, so the allocator reclaims almost nothing." That post also notes R-KV's reported "90% memory savings" were measured "with pre-allocated contiguous tensors, not in vLLM." Paper memory savings and served memory savings are different quantities. Ask which one a vendor is quoting.
Upstream, vLLM's Q3 2026 roadmap commits to a "KV Cache Manager redesign," to "prefix cache prefetching, eviction, and selective offloading," and to moving "KV-cache compression for agentic and long-context workloads" from feature availability to production — but that line is about quantization (FP8, NVFP4, INT2/4), not token-level eviction. There is no upstream eviction-policy plug point. Meanwhile the reference implementation sits on vLLM 0.19 while vLLM's release page shows v0.29.0 as current. Ten minor versions of drift is a fork you maintain, not a flag you set. Weigh that against the runtime you already standardised on.
One more distinction worth holding, because vendors blur it: this is not what LMCache and NVIDIA Dynamo do. LMCache reuses "computed key-value pairs across requests, users, and even nodes" to skip prefill. That is cross-request cache reuse and offloading. Eviction is within-request, mid-generation, and orthogonal. Both can be true at once, and neither substitutes for the other — much as transferring a cache between models to skip prefill solves a different problem again.
What to Do About It
This Week:
- Find out whether you evict at all. Most self-hosted vLLM deployments do not — they run full attention and pay for it in KV memory. If your reasoning workload is memory-bound, the table above says the first move (full → any evictor) is worth far more than the second (scorer → random). Do not skip step one to argue about step two.
- Grep your inference config for a pinned prompt. Whatever policy you run, the ablation says prompt protection is the single load-bearing setting. If your evictor does not explicitly reserve the system message, chat template and question, you are running the 0.459 configuration, not the 0.874 one.
- Send the paper to whoever is selling you compression. Ask one question: what does your method score against a random baseline with the prompt pinned? "We didn't test that" is now a meaningful answer.
This Month:
- Reproduce it on your own traffic, not on MATH500. The repo ships
scripts/vllm_rp_bench/with an accuracy-transfer check. Run it against your real prompt distribution — your prompts are almost certainly longer than the 90-token math questions where the method looks best, and closer to the 557-token code prompts where it loses ground. - Classify your workloads by restatement. Reasoning traces restate; retrieval contexts do not. Any workload where a fact appears once and matters much later — RAG, long agent transcripts, summarisation — keeps a scoring evictor or keeps full attention. Write that boundary down before someone applies one policy fleet-wide.
- Re-run your KV budget math. The paper's budgets are roughly 4x compression of typical trace length, 3x for code, on models from Qwen3-4B up to 32B pulled from the Hub. Your model, your trace lengths, your number.
Before Your Next Capacity Commit:
- Re-price the commitment with the compression assumption stated. A reserved-instance plan built on full-attention throughput is buying 1.6-2.7x the GPUs a compressed serving path needs, depending on the model. That is a term-length decision, and it is the kind that outlives the technical choice underneath it — the same trap as committing to a GPU cloud on a headline rate.
- Require the random baseline in every serving benchmark you accept. If a vendor benchmark does not include "prompt pinned, evict at random," it is not measuring the thing it claims to measure — the same discipline that separates a real evaluation result from a favourable round.
The Bottom Line
The authors' own conclusion is the line to take into your next architecture review: "the accuracy of an evictor is decided by what it protects, not by how it ranks the rest."
We have seen this shape before. A field builds increasingly clever machinery on top of a step nobody ever ablated, publishes a leaderboard measuring the machinery, and then somebody runs the null model and discovers the leaderboard was measuring an incidental side effect. It happened to recommender systems. It happened to neural architecture search. It is now happening to KV cache eviction — and Random Attention is not the only shot fired. An independent matched-budget audit published in July ran six published presses against three trivial baselines, including random eviction, and found that SnapKV — the most widely deployed of them — loses to "keep the start and the recent window" when compression happens before the question is visible. Two groups, different benchmarks, same shape of answer: protect the front of the context and the ranking of the rest stops mattering much. TriAttention went up on 6 April 2026, the audit on 11 July, Random Attention on 3 September.
The practical read is smaller and more useful than the headline. You still need paged-KV compression machinery. You still pay several accuracy points for the memory. You still cannot use this on retrieval. What you no longer have to buy, build or benchmark is the scorer — and you should stop paying anyone who charges for one.
The cleverest part of your cache policy was the part doing nothing. Pin the prompt and roll the dice.
Continue Reading
- Tencent Says 49B Active. Your Node Loads All 770B.
- 3,400 Tokens/s Was Batch 1. At 100K Context, It's Batch 12.
- vLLM vs TensorRT-LLM vs SGLang: Default to vLLM
- Nvidia Skipped the Prefill. The Math Went With It.
- GPU Hour Pricing: A $3.44 Rate Cost $68.80 to Use
- GPU Clouds Compared: Nebius on Price, CoreWeave at 3AM
- Claude Matched the Patch. Qwen Overshot. Score the Scope.
- Hugging Face Alternatives: Cache the Hub, Sign at the Door