Search papers, labs, and topics across Lattice.
The authors challenge the prevailing paradigm of score-based KV cache compression by evaluating Random Attention, a strategy that preserves prompt tokens and evicts remaining reasoning tokens uniformly at random within each head without calculating importance scores. Across four LLMs and six reasoning benchmarks, this zero-overhead random eviction matches the task accuracy of state-of-the-art eviction heuristics while increasing vLLM serving throughput by 32–43%. Mechanistic analyses reveal that preserving the prompt accounts for nearly all performance retention, while dual redundancy—semantic repetition in chain-of-thought text and duplicate representations across attention heads—renders explicit token-selection signals superfluous.
Complex scoring algorithms for KV cache compression are largely unnecessary: protecting the initial prompt and dropping reasoning tokens completely at random matches state-of-the-art accuracy with up to 43% higher serving throughput.
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 https://github.com/SalesforceAIResearch/Random-Attention.
