Random Attention Questions the Need for Smart KV Cache Eviction

Long reasoning chains help large language models solve difficult problems, but they also make the KV cache a major memory bottleneck. Most existing compression methods follow the same recipe: estimate how useful each cached token will be later, rank the tokens, and keep the highest-scoring entries. Random Attention asks whether that ranking signal is doing meaningful work at all.

Its policy is deliberately simple. The prompt is always retained, while other cached tokens are evicted uniformly at random within each attention head. No token-level importance score or ranking step is required. In experiments covering four models and six reasoning tasks, the method matched the strongest prior evictor. In a vLLM deployment, it also achieved 32% to 43% higher throughput than that baseline.

Key points

• The prompt is the fragile region. Controlled experiments indicate that much of the performance gap between selectors comes from whether their signal happens to preserve prompt information. Protecting the prompt therefore matters more than finely ranking every reasoning token.
• Reasoning text carries redundancy. As generation proceeds, the model often restates information it still needs. Later parts of the trace can therefore provide usable alternatives when earlier entries are removed.
• Attention heads provide another form of redundancy. Each head maintains its own representation of the trace. Random eviction does not need to identify the single most valuable token if enough copies of relevant information survive across heads.
• Removing scoring reduces serving overhead. A policy without importance estimation and sorting is easier to implement and avoids computation that may contribute little to final quality.

The result should not be read as proof that every token is interchangeable, or that random eviction is universally safe. Rather, it highlights a special property of long reasoning workloads: the generated trace may already contain enough redundancy to tolerate substantial randomness. Under those conditions, sophisticated selectors can cost more than the quality they recover.

For inference infrastructure, the paper suggests a different design priority. Instead of spending resources ranking an entire reasoning trace, a system could first protect the context most vulnerable to loss, then rely on repetition and multi-head redundancy to absorb the remaining eviction. Whether this principle holds for broader long-context tasks, tighter memory budgets, and stricter quality targets remains an open question. Even so, the work offers a useful baseline: before adding a more complex cache policy, measure how much value a simple random rule already provides.

Source: Hugging Face Daily Papers