Random Attention evicts KV cache entries uniformly at random per attention head (while pinning the prompt), matching the strongest learned eviction scores on reasoning tasks and serving 32–43% more tokens/second on vLLM because there is no scoring pass.
You’re serving a reasoning model that thinks for 20k+ tokens before answering. The KV cache grows linearly with every generated token, and at some point one GPU can’t hold enough concurrent requests to keep throughput up. The standard fix is eviction: cap the cache at K entries per head, and when it overflows, score each cached token by “how important will this be later?” and drop the low scorers. A whole line of work (H2O (Heavy-Hitter Oracle), SnapKV, R-KV, VaSE, TriAttention) proposes better and better scores. This paper asks whether the score matters at all, and finds it mostly doesn’t, as long as you don’t throw away the user’s question.
The method has exactly two rules. First, never evict any token from the original prompt (system message, chat template, user question). Second, for every other cached token, assign a uniform random number as its “score,” and independently in each key-value head keep the top-K. That’s it. No attention statistics, no value magnitudes, no calibration.
Because each head draws its own random keep-set, a token that gets dropped by one head usually survives in some other head. The paper argues this cross-head redundancy is what makes random selection work: the model reads a value from whichever heads still hold a copy, and independent random draws maximize the chance that at least some head still has it.
Here is the entire per-eviction procedure:
def random_attention_evict(cache, prompt_len, K):
# cache shape: (batch, kv_heads, seq_len, dim)
S = cache.seq_len
scores = uniform_random(batch, kv_heads, S)
scores[:, :, :prompt_len] = +inf # pin the prompt
keep_idx = topk(scores, K, dim=-1) # per-head, independent
return gather(cache, keep_idx)
The per-round cost is one random draw plus one top-K, versus the extra pass over cached keys or attention weights that every learned scorer needs.
The prevailing view is that eviction is a ranking problem: better scores mean better accuracy under compression. This paper shows the opposite. The score barely matters; what matters is whether the prompt survives and whether enough redundant copies of the working state remain across heads. A uniform random draw satisfies both. The load-bearing evidence is the matched-protection experiment: once every baseline is forced to keep the prompt, most of the gap between methods collapses, and the residual runs in random’s favor.
The key diagnostic is Table 2. When each learned scorer is given the same prompt-protection rule as Random Attention, SnapKV jumps by +12 to +22 points, VaSE gains +4 to +10 where its retention was weak, and R-KV (which was already keeping the prompt implicitly) moves by under 2 points. Each method gains exactly as much as its score had been losing on the question. After the fix, the three baselines land within 2.2 points of each other, and often still trail Random Attention.
Secondary results support this. On four models (Qwen3-4B/14B/32B and Phi-4-reasoning) across six reasoning tasks, Random Attention is significantly ahead in 31 of 60 baseline comparisons and significantly behind in only 1 (code reasoning on Qwen3-32B, where long prompts eat the budget). A planted-fact probe explains the cross-head half of the story: a synthetic value pinned in only one head is retrieved 3% of the time, but pinned in two heads it jumps to 60%, three heads 83%, all eight 99%. The shape of the surviving copies (contiguous block vs. scattered tokens) essentially doesn’t matter. The one case a random policy loses badly is a fact stated once, never restated, and needed 57 eviction rounds later: Random Attention retrieves it 0% of the time while R-KV gets 84%. Reasoning traces rarely produce this pattern because the model keeps restating what it’s using.
On serving throughput in vLLM with 32k-token generations, Random Attention runs at 1.6–2.7× full-attention throughput, which is 32–43% more than TriAttention on the same kernels, entirely because it skips the scoring pass that gets multiplied across ~62k compression events per workload.
Reach for this when you’re serving a reasoning model under a memory budget and were about to reach for SnapKV, R-KV, or a similar scored evictor. Replace the scorer with “pin prompt + uniform random per head.” You get the same accuracy on math and science reasoning, higher serving throughput because there is no scoring kernel to run at each synchronization barrier, and no hyperparameters to tune. It also becomes the new null baseline: any future selection signal has to beat random-with-prompt-protection at matched budget, not random-without-prompt-protection, which is what earlier papers were quietly comparing against.
The paper doesn’t announce a released repo in the text provided; if you want to try it, the description is short enough to reimplement in a few dozen lines against a runtime that already supports per-head physical eviction. The authors themselves added it to TriAttention’s existing vLLM plugin as a single function.
Protect the prompt, then stop scoring. Reasoning traces restate themselves in the text and mirror themselves across heads, so a random draw keeps enough copies of what the model still needs.
•
Code reasoning breaks the story when prompts are long. On LiveCodeBench, prompts average 557 tokens and can consume half the cache budget before random selection even begins, and TriAttention beats Random Attention significantly on Qwen3-32B code. If your prompts are long relative to K, pinning them whole is wasteful and a smarter rule may still help.
•
The self-redundancy argument depends on the trace restating what it’s using. For workloads with rare, once-mentioned facts needed much later (passcode lookup, pointer chasing, agent memory over long horizons), random loses catastrophically. R-KV’s accumulated-attention score exists for a reason there.
•
All results are on a narrow slice of open reasoning models (Qwen3 family plus Phi-4-reasoning) at one context length (32k). Whether the two-level redundancy story holds at 128k+ generations, on non-reasoning workloads, or on models with very different head counts is not tested.