Random Attention

Every KV-cache compression method scores cached tokens by predicted future importance and keeps the top ones. Salesforce AI Research shows the score contributes almost nothing: Random Attention keeps the prompt and evicts uniformly at random within each head, computing no score, and across four models and six reasoning tasks matches the strongest prior evictor while serving 32 to 43% higher throughput in vLLM. Controlled experiments trace this to the prompt being the fragile part of the cache and the reasoning trace being redundant enough that random retention suffices.