The memory bill for long-reasoning models ultimately lands on the KV cache. Every generated token forces the attention mechanism to cache its key-value states; run a tens-of-thousands-token chain of thought, and the KV cache becomes a severe memory bottleneck — that is the opening framing of a new paper (arXiv:2609.03430, submitted September 3) from Salesforce AI Research. The field already has a whole family of methods that share one paradigm: score each cached token by some estimate of how much it will matter later, keep the top-scoring ones, evict the rest. The paper's core finding: the selection signal itself contributes almost nothing.
Random eviction matches the strongest scorer
The proposed method, Random Attention, is almost embarrassingly simple: keep the prompt intact, then evict generated reasoning tokens uniformly at random within each attention head up to the budget, plus a short recency window — reading no attention scores, no value statistics, and no calibration data. Across four models (Qwen3-4B/14B/32B and Phi-4-reasoning) and six reasoning tasks (MATH-500, GPQA-Diamond, AIME, HMMT, LiveCodeBench), at matched budgets, random eviction matches carefully designed selective methods like SnapKV, R-KV, VaSE, and TriAttention. The deployment-side number matters more: in a vLLM serving stack, it delivers 32-43% higher throughput than the strongest prior evictor. Skipping the scoring compute converts directly into throughput.
Why randomness suffices: reasoning traces carry two layers of redundancy
The most valuable part of the paper is not the "random works too" headline but the mechanism behind it. Controlled experiments isolate two causes. First, the fragile part of the cache is the prompt: most of the performance gap between selectors comes down to whether their selection signal happened to keep the prompt — once the prompt is safe, how you pick among reasoning tokens matters little. Second, the reasoning trace protects itself with double insurance: at the text level, the model restates what it still needs as it works; at the attention-head level, each head keeps its own copy of the trace. With both layers stacked, a random draw reliably retains enough copies of whatever the model still needs.
Put differently: it is not that randomness is clever — it is that previous scorers have been taking credit for two things that never needed scoring, namely "happening to keep the prompt" and "redundancy doing the backup." A near-zero contribution from the selection signal is the hidden premise this whole family of methods shares.
The engineering angle: the selling point is the cost structure
For inference-serving engineers, the value here is not accuracy but cost. The project README states it plainly: an eviction round costs only the compaction itself, whereas TriAttention requires per-model calibration statistics — a deployment burden beyond the model. The code is open-sourced under Apache 2.0, shipping the eviction engine, evaluation harness, significance tests, the vLLM port, and the mechanism-study tooling; the paper's experiments ran on 8x H200 (141GB). On the Hugging Face papers page it has drawn over a hundred upvotes within two days.
The usual cold water: this is a single-team result, out for less than two days, and awaits independent replication; the study targets long-chain-of-thought reasoning scenarios, so the conclusion should not be blindly extrapolated to every KV cache compression setting; and the 32-43% throughput gain is measured against the strongest selective evictor — versus a fully uncompressed cache it is a different accounting.
Still, the wake-up call for the field is real: the next time a paper claims its new KV cache scoring algorithm gains a few points, the first question to ask is — did you run the random baseline?
Reference: arXiv:2609.03430 (https://arxiv.org/abs/2609.03430); code: github.com/SalesforceAIResearch/Random-Attention