The KV cache does not need a score.

Random Attention is a KV-cache eviction policy for long reasoning runs. The policy pins prompt positions, assigns random scores to the other cached positions independently within each KV head, and keeps a recent buffer with a persistent budget. The paper argues that prompts are fragile, while reasoning traces survive through restatement and copies across attention heads. 12

Why does that matter for a product team? KV caches turn long reasoning into a memory and serving-cost problem. Random Attention removes the token-scoring pass while preserving the prompt. Across four models and six reasoning tasks, the paper reports parity with the strongest prior evictor at about 4× compression and 32–43% higher throughput in vLLM. 2

Start with a shadow evaluator: pin the full prompt, evict outside the recent buffer, and compare answer quality, tokens per second, memory, and p95 latency with the current path. Keep vanilla attention or the current evictor as the live fallback. Stress long code prompts and facts stated only once. The paper reports that LiveCodeBench prompts average 557 tokens, and the longest prompts consume up to half of K=3072. 2