Scoring-Free Eviction for Prompt-Protected KV Caches: Random Attention Matches Selective Eviction

Random Attention claims that, for long-reasoning LLM workloads, KV-cache eviction does not need token-importance scoring. It protects the prompt and then evicts uniformly at random per attention head. In reported experiments it matches the strongest prior evictor on four models and six reasoning tasks, while achieving 32-43% higher throughput in vLLM. The authors attribute this to prompt fragility and the self-redundancy of reasoning traces.

September 5, 20261 source70% confidence

71Strategic

Strategic score

Evidence strength58

Technical novelty74

Commercial potential68

Random Attention reports that KV-cache eviction can dispense with token scoring: it preserves the prompt and evicts remaining positions uniformly at random within each head, computing no importance scores. On four models and six reasoning tasks this policy matches the strongest prior evictor, while a vLLM deployment runs 32-43% faster because the scoring pass is removed. The main constraint moved is not the size of the cache, but the need to decide which tokens will be needed later.¹

Context

Existing KV-cache compression methods score each cached token and keep the top-scoring ones. Random Attention instead protects the prompt and samples the remaining tokens uniformly in every attention head. The authors argue that this works because the prompt is the fragile part of the cache, while reasoning traces contain two layers of redundancy: textual restatement and per-head duplication.¹

Assessment

The genuinely new claim is that the selection signal contributes almost nothing once prompt safety is separated from token choice. This reframes earlier evictor comparisons: differences between selectors may be driven mostly by whether they happened to keep the prompt, not by how accurately they graded the rest of the cache. The reported breadth is moderate, but the abstract does not reveal the size of any accuracy gap, so the equivalence claim cannot be quantified from this source.¹

Caveats

AI hypothesisThe result would lose force if a workload produced a reasoning trace with weak redundancy, such as one where a single earlier derivation must be retrieved after a long intervening text. If such cases show a clear quality gap under random eviction, the self-protection explanation is falsified and token scoring regains importance. The throughput advantage would also shrink if scoring became nearly free or if cache heads were shared rather than duplicated.¹

Source text

Hugging Face Daily Papers — Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning · September 3, 2026

Computer Science > Computation and Language

Title:Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning

Abstract:Large language models achieve superior performance on tasks that require extended reasoning, but long chains of thought make the KV cache a severe memory bottleneck. Existing KV cache compression methods share one paradigm: score each cached token by some estimate of how much it will matter later, and keep the top-scoring ones. We show that the selection signal contributes almost nothing. Random Attention keeps the prompt and evicts uniformly at random within each attention head, computing no score at all; across four models and six reasoning tasks it matches the strongest prior evictor while serving 32-43% higher throughput than it in vLLM deployment. Controlled experiments explain this by showing that 1) the prompt is the fragile part of the cache, and most of the gap between selectors is just whether their selection signal happened to keep it; 2) the reasoning trace protects itself against eviction with redundancy at two levels, in the text (the model restates what it still needs as it works) and across attention heads (each keeps its own copy of the trace), so once the prompt is safe, a random draw retains enough copies of what the model still needs, and no score is required to pick them. Our code is publicly available at this https URL.

Access Paper:

Bookmark

Bibliographic and Citation Tools

Code, Data and Media Associated with this Article

Demos

Recommenders and Search Tools

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

The source text above remains the property of its publisher and is reproduced for commentary.

↑ Back to top