Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning

• URL: http://arxiv.org/abs/2609.03430v1
• Date: Thu, 03 Sep 2026 06:38:38 GMT
• Title: Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning
• Abstract summary: Large language models achieve superior performance on tasks that require extended reasoning.<n>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.<n>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.
• Score: 78.75986976062454
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Back from the Future: Key-Value Cache Management by Counter-Causal Surprise [67.1056509495879]
  Key-value (KV) cache management through compression and eviction strategies has emerged as an important research direction in recent years.<n>We propose a simple yet effective KV eviction scheme motivated by the insight that past tokens which can be well-predicted from more recent tokens are redundant.<n>We evaluate our strategy on various open-source LLMs and benchmark datasets showing competitive or improved performance over other state-of-the-art methods.
  arXiv  Detail & Related papers  (2026-07-30T02:42:51Z)
• Value-Aware Stochastic KV Cache Eviction for Reasoning Models [34.29227693805387]
  Reasoning models improve accuracy through extended chains of thought, but their long outputs create a memory and compute bottleneck.<n> KV cache eviction methods reduce this cost by evicting unimportant key-value pairs from the cache, yet they often yield worse accuracy than selection-based sparse attention alternatives.<n>We propose Value-aware KV Cache Eviction (VaSE), a training-free recipe that protects large-magnitude value states and promotes diverse eviction decisions.
  arXiv  Detail & Related papers  (2026-06-02T17:16:33Z)
• Make Each Token Count: Towards Improving Long-Context Performance with KV Cache Eviction [65.710271475739]
  We introduce a global retention-based KV eviction method that learns each token's future utility under a unified memory budget.<n>We show that our method substantially reduces KV memory while matching or surpassing full-cache inference.<n>These results suggest that learned, globally calibrated KV eviction is not only a compression technique, but also a mechanism for improving long-context reasoning.
  arXiv  Detail & Related papers  (2026-05-10T16:47:50Z)
• Neural Garbage Collection: Learning to Forget while Learning to Reason [36.674101487378245]
  We introduce Neural Garbage Collection, in which a language model learns to forget while learning to reason.<n>By treating tokens in a chain-of-thought and cache-eviction decisions as discrete actions sampled from the language model, we can use reinforcement learning to jointly optimize how the model reasons.<n>On Countdown, AMC, and AIME tasks, NGC maintains strong accuracy relative to the full-cache upper bound at 2-3x peak KV cache size compression.
  arXiv  Detail & Related papers  (2026-04-20T09:26:28Z)
• G-KV: Decoding-Time KV Cache Eviction with Global Attention [57.47409249054187]
  Large language models (LLMs) excel in complex tasks but encounter significant computational and memory challenges due to long sequence lengths.<n> KV cache compression has emerged as an effective approach to greatly enhance the efficiency of reasoning.<n>We propose G-KV, a KV cache eviction method that employs a global scoring mechanism, combining local and historical attention scores to more accurately assess token importance.
  arXiv  Detail & Related papers  (2025-11-29T14:21:33Z)
• Judge Q: Trainable Queries for Optimized Information Retention in KV Cache Eviction [53.83828564664595]
  Large language models (LLMs) utilize key-value ( KV) cache to store historical information during sequence processing.<n>Current methods for KV cache eviction typically utilize the last window from the pre-filling phase as queries to compute the KV importance scores for eviction.<n>We propose Judge Q, a novel training method which incorporates a soft token list.
  arXiv  Detail & Related papers  (2025-09-13T03:34:12Z)
• LazyEviction: Lagged KV Eviction with Attention Pattern Observation for Efficient Long Reasoning [21.761205124793175]
  extended reasoning sequences introduce significant GPU memory overhead due to increased key-value (KV) cache.<n>Existing KV cache compression methods mitigate memory bottlenecks but struggle in long reasoning tasks.<n>We propose LazyEviction, an observation window-based lagged eviction framework retaining latent recurring tokens by prioritized eviction based on tokens' recurrence patterns.
  arXiv  Detail & Related papers  (2025-06-19T02:25:04Z)
• AttentionPredictor: Temporal Patterns Matter for KV Cache Compression [64.75459635661562]
  We propose AttentionPredictor, which is the first learning-based method to directly predict attention patterns for KV cache compression and critical token identification.<n> AttentionPredictor accurately predicts the attention score and shares the unified prediction model, which consumes negligible memory.<n>By retaining most of the attention information, AttentionPredictor achieves 13$times$ KV cache compression and 5.6$times$ speedup in a cache offloading scenario.
  arXiv  Detail & Related papers  (2025-02-06T13:41:46Z)
• RazorAttention: Efficient KV Cache Compression Through Retrieval Heads [11.708388082001074]
  We propose a novel compression technique for Key-Value cache that preserves all token information. RazorAttention achieves a reduction in KV cache size by over 70% without noticeable impacts on performance.
  arXiv  Detail & Related papers  (2024-07-22T01:12:23Z)
• CORM: Cache Optimization with Recent Message for Large Language Model Inference [57.109354287786154]
  We introduce an innovative method for optimizing the KV cache, which considerably minimizes its memory footprint. CORM, a KV cache eviction policy, dynamically retains essential key-value pairs for inference without the need for model fine-tuning. Our validation shows that CORM reduces the inference memory usage of KV cache by up to 70% with negligible performance degradation across six tasks in LongBench.
  arXiv  Detail & Related papers  (2024-04-24T16:11:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.