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 <a href=\"https://github.com/SalesforceAIResearch/Random-Attention\" rel=\"nofollow\">https://github.com/SalesforceAIResearch/Random-Attention</a>.</p>\n","updatedAt":"2026-09-04T03:03:10.704Z","author":{"_id":"62ea79dd01ed9b0e8f61ccd3","avatarUrl":"/avatars/70af83e0e267be39fcd5f23b85e2dafa.svg","fullname":"Chengsong Huang","name":"ChengsongHuang","type":"user","isPro":false,"isHf":false,"isHfAdmin":false,"isMod":false,"followerCount":16,"isUserFollowing":false}},"numEdits":0,"identifiedLanguage":{"language":"en","probability":0.9382008910179138},"editors":["ChengsongHuang"],"editorAvatarUrls":["/avatars/70af83e0e267be39fcd5f23b85e2dafa.svg"],"reactions":[],"isReport":false}}],"primaryEmailConfirmed":false,"paper":{"id":"2609.03430","authors":[{"_id":"6a9a13288f7c3b75572393a1","user":{"_id":"64a5583f1e1d475f6da4928c","avatarUrl":"/avatars/a46ddc1479ab6e1d14568822b7546a69.svg","isPro":false,"fullname":"Heng Wang","user":"Heng-Wang","type":"user","name":"Heng-Wang"},"name":"Heng Wang","status":"claimed_verified","statusLastChangedAt":"2026-09-04T08:45:04.204Z","hidden":false},{"_id":"6a9a13288f7c3b75572393a2","name":"Jielin Qiu","hidden":false},{"_id":"6a9a13288f7c3b75572393a3","name":"Wenting Zhao","hidden":false},{"_id":"6a9a13288f7c3b75572393a4","name":"Cheng Qian","hidden":false},{"_id":"6a9a13288f7c3b75572393a5","name":"Liangwei Yang","hidden":false},{"_id":"6a9a13288f7c3b75572393a6","name":"Jiawei Han","hidden":false},{"_id":"6a9a13288f7c3b75572393a7","name":"Heng Ji","hidden":false},{"_id":"6a9a13288f7c3b75572393a8","name":"Silvio Savarese","hidden":false},{"_id":"6a9a13288f7c3b75572393a9","name":"Shelby Heinecke","hidden":false},{"_id":"6a9a13288f7c3b75572393aa","name":"Huan Wang","hidden":false}],"publishedAt":"2026-09-03T00:00:00.000Z","submittedOnDailyAt":"2026-09-04T00:00:00.000Z","title":"Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning","submittedOnDailyBy":{"_id":"62ea79dd01ed9b0e8f61ccd3","avatarUrl":"/avatars/70af83e0e267be39fcd5f23b85e2dafa.svg","isPro":false,"fullname":"Chengsong Huang","user":"ChengsongHuang","type":"user","name":"ChengsongHuang"},"summary":"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.","upvotes":53,"discussionId":"6a9a13298f7c3b75572393ab","ai_summary":"Random eviction of reasoning tokens matches selective KV cache compression because reasoning traces are self-protecting through redundancy, making scoring unnecessary once prompts are preserved.","ai_keywords":["KV cache compression","attention heads","reasoning trace","redundancy","prompt preservation","vLLM throughput"],"ai_summary_model":"thinkingmachines/Inkling-Small","organization":{"_id":"5f6d64475e78cc6b0ed31e4c","name":"Salesforce","fullname":"Salesforce AI Research","avatar":"https://cdn-avatars.huggingface.co/v1/production/uploads/1602756670970-noauth.jpeg"}},"canReadDatabase":false,"canManagePapers":false,"canSubmit":false,"hasHfLevelAccess":false,"upvoted":false,"upvoters":[{"_id":"64a5583f1e1d475f6da4928c","avatarUrl":"/avatars/a46ddc1479ab6e1d14568822b7546a69.svg","isPro":false,"fullname":"Heng Wang","user":"Heng-Wang","type":"user"},{"_id":"66783baec3f824dde8f783ac","avatarUrl":"https://cdn-avatars.huggingface.co/v1/production/uploads/66783baec3f824dde8f783ac/oqFYUrgs2vnGRhAMSrQpC.jpeg","isPro":false,"fullname":"Jeff","user":"JiayuJeff","type":"user"},{"_id":"6449dbd8df4e6cb7eaef943e","avatarUrl":"/avatars/41a549a7b1cfe1d59ea16b3cbd2168cc.svg","isPro":false,"fullname":"ChengQ","user":"0Cheng0","type":"user"},{"_id":"6a7c156d71fa900c3431026a","avatarUrl":"/avatars/0763cf27f0b3c7963e2c1c36c72f4b10.svg","isPro":false,"fullname":"ChengQ-Apodex","user":"ChengQ-Apodex","type":"user"},{"_id":"684f8512aeaf14df648ce3f9","avatarUrl":"https://cdn-avatars.huggingface.co/v1/production/uploads/no-auth/IF3Tf9_TNua0yJF7TPsm-.png","isPro":false,"fullname":"Cheng Qian","user":"chengq-sfr","type":"user"},{"_id":"6a7c16613d34d342bb461539","avatarUrl":"/avatars/5f74ed01471362a0c07defeacd10c5d1.svg","isPro":false,"fullname":"0Cheng1","user":"0Cheng1","type":"user"},{"_id":"6a7c12f88a355e774c4cbb27","avatarUrl":"/avatars/f513aeed3b38d2b32154038b7a0418bb.svg","isPro":false,"fullname":"happysnake","user":"happysnake","type":"user"},{"_id":"6a7c1502c9548a38dc9e3f3d","avatarUrl":"/avatars/7311ce04297c4d5ab112d568c81b91d9.svg","isPro":false,"fullname":"passionfire","user":"passionfire","type":"user"},{"_id":"6a7e3f017ef3700ed7083e55","avatarUrl":"/avatars/5af5abd0a0bd211568a8dfe376f3b994.svg","isPro":false,"fullname":"Heng Wang","user":"wenniebear2","type":"user"},{"_id":"6a7e3e5effe2488635fc6a3e","avatarUrl":"/avatars/9a6f12702965ada3f72d3db2fd0b19b4.svg","isPro":false,"fullname":"Heng Wang","user":"wenniebear1","type":"user"},{"_id":"6a6915711275153b6eb73307","avatarUrl":"/avatars/f5d392b584f63da62b46b8dc7abf584c.svg","isPro":false,"fullname":"qcg3","user":"qcg3","type":"user"},{"_id":"6a6915aa84ce755c44816e72","avatarUrl":"/avatars/794ec0d17425a3492da6d42617ac0e28.svg","isPro":false,"fullname":"qcg4","user":"qcg4","type":"user"}],"acceptLanguages":["en"],"dailyPaperRank":0,"organization":{"_id":"5f6d64475e78cc6b0ed31e4c","name":"Salesforce","fullname":"Salesforce AI Research","avatar":"https://cdn-avatars.huggingface.co/v1/production/uploads/1602756670970-noauth.jpeg"},"markdownContentUrl":"https://huggingface.co/buckets/huggingchat/papers-content/resolve/2609/2609.03430.md","query":{}}">
Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning
Abstract
Random eviction of reasoning tokens matches selective KV cache compression because reasoning traces are self-protecting through redundancy, making scoring unnecessary once prompts are preserved.
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.
Community
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.
Upload images, audio, and videos by dragging in the text input, pasting, or clicking here.
Tap or paste here to upload images
Cite arxiv.org/abs/2609.03430 in a model README.md to link it from this page.
Cite arxiv.org/abs/2609.03430 in a dataset README.md to link it from this page.
Cite arxiv.org/abs/2609.03430 in a Space README.md to link it from this page.
Discussion (0)
Sign in to join the discussion. Free account, 30 seconds — email code or GitHub.
Sign in →No comments yet. Sign in and be the first to say something.