PaperlayerView exact revision on arXiv

Source-linked AI summary

Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning

Heng Wang, Jielin Qiu, Wenting Zhao, Cheng Qian, Liangwei Yang, Jiawei Han, Heng Ji, Silvio Savarese, Shelby Heinecke, Huan Wang

arXiv:2609.03430v1cs.CL

TL;DR

Long reasoning traces make KV-cache eviction a memory bottleneck, yet prior methods rely on scores to rank tokens for retention. Random Attention protects the prompt and samples the remaining trace uniformly per attention head, matching strong evictors across models and tasks while delivering 32–43% higher vLLM throughput. The results indicate that prompt protection and redundancy, rather than fine-grained ranking, explain most performance under compression.

  • Problem

    Long chains of thought make KV-cache memory a severe bottleneck, while existing eviction methods assume token-importance scores determine accuracy under compression.

  • Method

    Random Attention permanently keeps the prompt and evicts remaining cached positions uniformly at random and independently within each attention head.

  • Results

    Across four models and six reasoning tasks, Random Attention matches the strongest prior evictor while serving 32–43% higher throughput in vLLM deployment.

  • Takeaways & Limitations

    Eviction accuracy is largely determined by protecting the prompt because reasoning traces provide redundancy in text and across attention heads.

  • Takeaways & Limitations

    Random Attention cannot reliably preserve a fact stated once, never restated, and needed much later; R-KV retrieves such passcodes 84% of the time.

Abstract

from arXiv · show

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.

1 Introduction

Long reasoning chains make KV caches a severe memory bottleneck, while existing eviction methods assume token-ranking scores determine accuracy under compression. The paper finds that Random Attention matches strong evictors and improves serving throughput by avoiding scoring.

  • Long chains of thought make KV-cache memory grow linearly with generation length, creating a severe bottleneck.
  • Existing eviction methods score cached tokens by estimated future importance and retain the highest-scoring positions.
  • Random Attention keeps the prompt and evicts uniformly at random within each attention head, computing no selection score.
  • Across four models and six reasoning tasks, Random Attention is comparable to the strongest baseline and is significantly ahead in 31 of 60 baseline comparisons.
  • 32–43% more tokens per second at 32k-token generations are delivered through vLLM because Random Attention never runs a scoring pass.
  • The prompt is fragile, whereas reasoning traces protect themselves through textual and cross-head redundancy, leaving little for selection signals to improve.
  • The findings suggest using Random Attention as a serving default and focusing future eviction work on long prompts and rare once-stated facts.

2 Preliminaries

The paper frames eviction as periodic, monotonic removal of cached key-value pairs under a fixed per-head budget. Prior methods differ primarily in how they score candidate positions for retention.

  • During decoding, reasoning models may generate more than 10,000 tokens, making eviction necessary once the KV cache reaches a memory budget.
  • Each attention head stores cached key-value pairs for token positions, including the prompt positions, and forms its output from the current query.
  • Eviction decisions are made independently in every layer and KV head, and discarded pairs cannot be recovered.
  • Periodic eviction retains a persistent budget of K pairs plus an unscored buffer of r recent pairs, then scores candidates outside the buffer.
  • The highest-scoring candidates are kept, returning each head to K+r entries; methods differ mainly in their scoring function.
  • StreamingLLM keeps initial attention-sink positions and recent tokens, while H2O and SnapKV use accumulated or recent-query attention scores.
  • R-KV adds a redundancy term, VaSE scores value ranges with sampled completion slots, and TriAttention scores positions by distance from the current query.

3 Random Attention

Random Attention separates prompt protection from trace eviction: it never evicts the prefill and randomly distributes the remaining retention budget independently across KV heads. Its implementation requires only random scores and top-k selection.

  • Random Attention protects the entire prefill because the question is stated once and cannot be recovered after eviction.
  • Every non-prompt cached position receives an independent uniform random score, and each KV head retains its own top-K positions.
  • Independent per-head sampling spreads retained positions across the reasoning trace and creates different retained copies in different heads.
  • The method applies its random scoring independently per KV head at every eviction event.
  • Algorithm 1 generates uniform scores, forces prompt scores to positive infinity, selects the top K positions per KV head, and returns them.
  • Each eviction costs one random-number generation and one top-k operation, making Random Attention a signal-free deployable baseline.

4 Experiments

Experiments compare eviction methods across four models and six reasoning tasks using accuracy under compression, with statistical tests for claimed margins. Random Attention generally matches or exceeds selectors, while longer code prompts expose the importance of prompt protection.

  • Main results: 31 of 60 baseline cells significantly favor Random Attention, while only one significantly favors a baseline.Paired, problem-clustered bootstrap tests and exact sign tests determine significance.
  • Math and science: On MATH500 and GPQA-D, Random Attention significantly beats VaSE and SnapKV on every model, with no selector significantly ahead.TriAttention’s nominal 0.3–0.6-point leads on two GPQA-D cells remain within noise.
  • Competition math: On AIME and HMMT, no selector significantly exceeds Random Attention, while SnapKV trails it significantly on every model.VaSE’s nominal Qwen3-32B leads of 1.7 and 1.5 points are smaller than the ±5-point run-to-run standard deviation.
  • Code reasoning: 20–35 points separate SnapKV from Random Attention on LiveCodeBench across every model, where prompts average 557 tokens and can consume half the K=3072 budget.TriAttention ties on Qwen3-4B and Phi-4-reasoning but leads Qwen3-32B by about three points, the sole significant baseline win.
  • Compression pressure: From 2× to 16× compression, Random Attention stays tied with TriAttention while VaSE’s gap opens as budgets tighten.The sweep covers Qwen3-4B and Phi-4-reasoning on four math and science tasks; dashed lines indicate full attention.
  • Prompt protection: Protecting the prompt improves SnapKV everywhere, whereas R-KV gains at most 1.9 points and VaSE gains materially only on Phi-4-reasoning.Table 2 isolates prompt protection from the selector’s scoring behavior.

5 Why the Selection Signal Buys So Little

The prompt is the fragile component of the KV cache, while the reasoning trace remains usable because its information is redundantly represented in text and across attention heads. Consequently, once prompt protection is standardized, ranking the remaining cached tokens contributes little.

  • 5.2 The Working State Protects Itself: The reasoning trace is redundant in text because models restate intermediate information they continue using.Thus, important values rarely occupy only one token position.
  • 5.1 The Prompt Is the Fragile Part: Prompt protection explains most selector differences: after every method keeps the prompt, baseline gaps largely disappear.The three baselines remain within 2.2 points of one another in every tested setting.
  • 5.1 The Prompt Is the Fragile Part: Random Attention can lose accuracy when the prompt is not protected, while adding the protection rule removes the important loss.Without the rule, Random Attention scores 0.23–0.76; with it, it is best in every setting.
  • 5.2 The Working State Protects Itself: Cross-head copies pool effectively: in Qwen3-4B, retrieval rises from 3% for the best single head to 99% across all eight heads.A value remains usable when some heads retain copies, which independent per-head random draws preserve.
  • 5.2 The Working State Protects Itself: The arrangement of retained trace tokens matters little until blocks become large: contiguous blocks cost nothing through size 64, with accuracy dropping at size 256.At that point, the budget leaves each head with only four or two blocks for K=1024 or K=512.
  • 5.3 What Is Left for a Selection Signal: Signal-free eviction cannot reliably recover a unique, distant fact that is stated once and never restated.In the passcode probe, Random Attention never reproduces the passcode, whereas R-KV retrieves it in 84% of traces.

6 Efficiency Evaluation

Random Attention improves serving efficiency by eliminating token-scoring overhead while preserving comparable accuracy. Its throughput advantage persists across serving conditions and arises from both cache capacity and avoiding an expensive scoring pass.

  • 32–43% faster than TriAttention under paged serving at 32k-token generations.Both methods use one H200, K=2048, 1k-token prompts, 32k-token generations, and 128 requests.
  • 1.6–2.7× full-attention throughput across four models, while exceeding TriAttention by 32–43% on the same kernels.The advantage also holds at short generations and lighter loads.
  • At capacity plateau, adding 512 requests raises throughput by only 7% on Qwen3-4B and under 1% on Qwen3-14B, while Random Attention’s margin remains +41% and +42%.
  • At capacity, compressed caches fit 109–200 concurrent sequences versus 20–28 for full attention, producing 3–10× speedups from shared cache capacity.The residual ordering comes from the scoring pass: Random Attention fits the largest batch at the smallest peak footprint and reaches 10.0× and 8.8× full-attention throughput on Qwen3-4B and Qwen3-14B.
  • At matched capacity, Random Attention reaches 10.0× and 8.8× full-attention throughput on Qwen3-4B and Qwen3-14B.At K=1024 on MATH500, the same protocol reaches 28.8×.
  • Random Attention’s eviction round costs 0.30 ms, compared with 1.47–1.64 ms for TriAttention’s scoring-and-compaction pass.Concurrent serving multiplies this per-eviction difference across requests.

7 Related Work

Prior KV-cache work addresses long-context understanding through quantization, eviction, and query-aware selection, while reasoning introduces a distinct long-output regime. Random Attention evaluates eviction under matched budgets and prompt protection, finding random retention comparable to stronger selectors with greater efficiency.

  • Long-context methods reduce memory through quantization, eviction, or query-aware selection, which saves compute but not memory.
  • Reasoning reverses the usual cache ratio: short prompts produce very long traces, making eviction necessary to bound peak GPU memory.Sparse attention attends to part of the cache but retains every pair, so memory still grows with trace length.
  • Matched-budget experiments show that keeping the prompt lets random eviction remain comparable to the strongest baseline while being much more efficient.

8 Conclusion

The paper concludes that KV-cache eviction accuracy depends mainly on protecting the prompt, not ranking the remaining trace. Random Attention therefore serves as an efficient default and shifts research toward matched prompt protection and budget comparisons.

  • Random Attention matches strongest baselines across four models and six tasks while delivering 32–43% higher vLLM throughput.
  • Controlled evidence attributes selector differences mainly to prompt survival, while textual and cross-head redundancy protects the reasoning trace.
  • The remaining role for selection signals is the rare fact stated once and never restated, which reasoning seldom produces.
  • The manuscript reports generative-AI assistance for drafting, coding, plotting, and typesetting, with authors reviewing outputs and recomputing statistics from released logs.

A Generality: additional models

Additional Qwen3-14B results replicate the headline pattern: Random Attention beats VaSE and SnapKV on MATH500 and GPQA-D, while selected baseline wins remain task-specific.

  • On Qwen3-14B, Random Attention significantly beats VaSE and SnapKV on MATH500 and GPQA-D.
  • TriAttention leads LiveCodeBench by +2.6 points and MATH500 by +2.1 points, while VaSE leads AIME by +2.6 points.These are the three significantly ahead baseline cells at this scale.

B The planted-fact probe: instrument and metric

The planted-fact instrument feeds scripted reasoning through the true decode path while controlling which heads retain the fact. Recall measures each condition’s average log-probability gain relative to the average available gain, with paired bootstrap uncertainty estimates.

  • Instrument: The instrument inserts a 16-token synthetic fact into screened MATH500 reasoning traces, followed 256 tokens later by a terminal query.Token-by-token forcing makes eviction treat scripted tokens exactly like generated reasoning, while preventing the model from restating the fact.
  • Instrument: Fact distances are controlled by eviction-event counts E∈{3, 15, 39, 57}, with per-copy survival modeled as (1024/1088)^E.
  • Instrument: Pinning retains the fact only in designated layer-head sites, whereas background eviction uses standard per-head uniform draws without protection.
  • Metric: Recall R is the average log-probability gain of a condition over the average available gain, with both endpoints measured per needle.Retrieval leads when conditions separate; recall carries comparisons when retrieval floors.
  • Statistics: Confidence intervals use 4,000-replicate instance-clustered bootstrap percentiles, with paired contrasts on identical instances.Fresh eviction randomness shifts reported values by one to two points.

C Matched protection in the remaining settings

Matched prompt protection largely removes selector differences, especially where baseline scores were losing prompt tokens, but residual gaps remain in some settings.

  • Matched protection: Across fifteen protected model–task settings, the matched prompt-protection control tests whether selector differences arise from prompt retention.
  • Prompt retention: SnapKV gains +35.2, +22.1, +16.5, +13.9 and +1.3 points when its prompt retention deficit is repaired, while R-KV moves −1.4 to +0.9 points.VaSE gains +27.3, +3.2 and +2.9 where prompt retention falls short, but moves −2.1 and −1.0 where it does not.
  • Residual differences: Protection closes prompt-driven gaps completely on code for both models and on HMMT, making SnapKV and VaSE statistical ties with Random Attention.
  • Residual differences: Residual deficits persist on GPQA-D at 32B, where protected baselines remain 4–6 points below Random Attention while TriAttention ties it.On AIME, SnapKV, R-KV and VaSE remain 5.4, 11.1 and 3.5 points below Random Attention.

D Keep-log measurements

Keep-log measurements show Random Attention creates a soft recency window while distributing older trace positions differently across heads. On real traces, text-level redundancy can preserve accuracy even without cross-head diversity.

  • Logging: Keep logs record every eviction round across nineteen policy–cell logs, with 16 traces and roughly 10^4–10^5 rounds per log.Each round records the keep-set of every layer–KV-head pair and the age of retained positions.
  • Age profiles: Random Attention’s retention decays geometrically with age, whereas VaSE freezes old favourites and TriAttention spreads retention nearly uniformly across ages.TriAttention retains less of the recent middle than Random Attention but more of the very old tail.
  • Implicit age bias: After n evictions, a surviving position faces a fresh draw, giving approximate survival 0.94^n at K=1024 and r=64.This makes Random Attention a soft recency window with a thin, head-specific old-position tail.
  • Redundancy: Removing cross-head diversity changes Qwen3-4B MATH500 accuracy only from 0.874 to 0.871 at K=1024 and from 0.789 to 0.788 at K=512.The shared-draw control reduces the 1–2k-band cross-head union from 0.776 to 0.161, yet text-level restatement preserves real-trace accuracy.
  • Generation behavior: Random Attention is the shortest-generating evictor on Qwen3-4B and Qwen3-14B when averaged over five tasks.
  • Implementation: The experiments use per-KV-head physical eviction with monotonic compaction, standardized triggers and buffers, and model-specific task budgets.

G Efficiency: protocols and additional measurements

Efficiency measurements compare evictors under shared serving protocols and isolate selector cost where possible. Random Attention benefits most at long generations and tighter memory budgets, but short generations can make compression unhelpful.

  • vLLM integration: The vLLM comparison uses bf16, one H200, vLLM v0.19.0, shared kernels and paging, differing only in retained positions.Random Attention integrates as a random slot-index permutation using the existing compaction path.
  • Short-generation boundary: For 8k outputs, Random Attention reaches 0.52×, 0.70× and 0.96× full-attention throughput on Qwen3-4B, 14B and 32B, respectively.At this operating point arithmetic rather than cache capacity bounds throughput, so compression buys nothing.
  • Comparison caveats: Published TriAttention throughput is not directly comparable when measured at different budgets, decode lengths, GPUs, or with different scorer implementations.The paper therefore relies on matched measurements rather than the published ∼2.5× figure.
  • Long-generation throughput: At 32k generations and K=3072, a rerun preserves Random Attention’s lead: 2011 versus 1437 tok/s on Qwen3-4B and 1696 versus 1223 on Qwen3-14B.The differences are +40% and +39%, respectively, despite the budget difference between serving tables.
  • Eviction cost: Random Attention’s eviction-round time is the compaction floor because it performs no scoring; other methods pay additional selector cost.The ordering and per-call costs remain within 12% across a 3.5× model-size change.
  • Concurrency boundary: The integration caps compressed concurrency because compression state does not survive vLLM preemption, while full attention can recompute preempted requests.Both compressed methods share the same cap, but full attention’s handling affects some capacity comparisons.
  • Protocols: Equal-memory tests run each method on the same engine and code path, bisecting the largest batch that fits a 143 GB H200.This isolates scoring-pass cost among methods, while full attention receives its own feasible-batch search.
  • Tighter budget: At K=1024 on Qwen3-4B, Random Attention reaches 28.8× full-attention throughput, 16% above SnapKV and 20% above VaSE.The tighter budget fits 584 compressed sequences versus 28 for full attention.
Loading 2609.03430v1…