Random Attention Randomly Evicts KV Cache Entries After Preserving the Prompt, Outperforming Scoring-Based Methods on Long-Reasoning Throughput

Long-chain reasoning causes the attention KV cache at every layer to grow continuously as output is generated. Existing eviction methods typically compute attention weights, key statistics, or redundancy scores, then retain the highest-ranked tokens. [Random Attention](https://arxiv.org/abs/2609.03430), proposed by Salesforce AI Research and collaborators, takes the opposite approach: it permanently protects the full prompt and a short recent window, while uniformly sampling the remaining generated tokens within each KV head. It does not inspect attention scores or value statistics and requires no model calibration, leaving physical cache compaction as the only work performed in each round.

The study covers Qwen3-4B, 14B, and 32B, as well as Phi-4-reasoning, across six reasoning benchmarks, including MATH-500, GPQA-Diamond, AIME, HMMT, and LiveCodeBench. Under the same cache budget, the random strategy matched or outperformed SnapKV, R-KV, VaSE, and TriAttention overall. The authors attribute this to two forms of redundancy: reasoning text often restates information that remains relevant, while the same token is also distributed across multiple KV heads. As long as the problem itself is not evicted, random sampling usually preserves enough copies. Synthetic experiments further show that a one-time fact retained in only a single head is almost impossible to retrieve reliably; the success rate rises rapidly only after it is retained across multiple heads.

The serving tests used a single H200, vLLM 0.19, a 1K-token prompt, a 32K-token output, K=2048, and 128 concurrent requests. Across four models, Random Attention achieved 1.58× to 2.67× the throughput of full attention and delivered 32% to 43% higher throughput than TriAttention using the same paging, scheduling, and compaction kernels. The main reason was not that sampling itself was dramatically faster, but that scoring repeatedly reads data across block tables in a paged cache. Tens of thousands of synchronous compaction operations can therefore force the entire batch to wait.

This does not mean that randomness always beats content-based selection. When outputs are only 8K tokens and computation rather than memory becomes the bottleneck, the compression strategies deliver just 0.52× to 0.96× the throughput of full attention. Long code prompts may also consume most of the cache budget, while one-time facts that are never restated still require content-aware protection. The public [Apache-2.0-licensed repository](https://github.com/SalesforceAIResearch/Random-Attention) includes evaluation code, statistical significance tests, and a vLLM port, but the performance results remain concentrated on the H200, specific models, and configurations with prefix caching disabled. Deployers should rerun benchmarks using their own prompt lengths, generation lengths, concurrency levels, and hardware.