KV-cache eviction caps the memory cost of long reasoning traces but is inherently lossy because the model decodes from a partial view of its history. Under aggressive budgets, this not only lowers accuracy but can also cause runaway degeneration, where the model produces incoherent or repetitive tokens until reaching the length limit. We characterize much of this loss as an information gapf caused by missing context, rather than a capability gap caused by limited model capacity. An evicted 7B model and a full-context 1.5B model make complementary errors, and an oracle choice between their answers recovers 79% of the accuracy gap to the full-KV 7B model. Based on this observation, we propose KV-Rescue, a training-free inference framework that bridges the information gap introduced by KV eviction using a lightweight full-context helper. KV-Rescue interleaves reasoning steps from the two models into a shared trajectory. An online detector uses entropy and compressibility to terminate the generation of incoherent or repetitive base-model candidates early. Across five math benchmarks with Qwen2.5-Math 7B and 72B, KV-Rescue recovers an average of 87% of the accuracy lost to eviction at eviction budget B=64. A decode-cost analysis further shows that preventing runaway degeneration cuts base-model token generation by 43% on average.
Figures & tables
Figure 1: (a) An evicted 7B and a full-KV 1.5B make complementary errors; an oracle pick between them recovers 79% of the eviction loss. (b) Best-of- N plateaus below full-KV, while KV-Rescue (ours) recovers most of the gap and wins at every N . (MATH500, Qwen2.5-Math-7B, budget 128.)
Figure 2: Two degeneration modes observed under aggressive KV eviction in Qwen2.5-Math-7B stepwise best-of- N decoding traces. Coherent reasoning (gray) transitions into (a) incoherent generation or (b) a repetition loop, and continues to the length limit without producing an answer.
Figure 3: Online degeneration detection (Qwen2.5-Math-7B, R-KV eviction). Both signals are computed from statistics already available during decoding. (a,b) Incoherent generation has high token-level entropy, so coherent and incoherent candidates split into two modes that a flat τent separates without labels. (c,d) Repetition loops are confident (low entropy) but highly redundant: the gzip ratio (compressed size of a sliding text window over its raw size; lower means more repetitive) collapses below τcmp , leaving a small loop population cleanly below the coherent bulk.
Figure 4: KV-Rescue. At each step, candidates are sampled from an evicted base πb and a full-context helper πh ; an online degeneration detector prunes degenerate base steps, the PRM commits the best step st , and base and helper steps interleave. The best-of- N baseline for comparison is in the Appendix
Steps
Out. len
Base 7B tok
1.5B tok
Dataset
Bud.
BoN
KVR
BoN
KVR
BoN
KVR
KVR
MATH500
full
27.0
–
673
–
6,106
–
–
512
31.8
15.4
670
687
6,189
5,841
6,102
256
46.7
14.8
701
653
6,704
5,855
5,931
128
63.8
15.6
754
666
7,607
6,068
6,142
64
114
21.1
960
671
10,587
6,327
6,560
Table 1: Decode cost of best-of- N (BoN) vs. KV-Rescue (KVR) on Qwen2.5-Math-7B ( N=8 ): per-problem mean steps, output length, and generated 7B-base / 1.5B-small tokens. Cells are heat-shaded per dataset and metric (green = low, red = high); as the KV budget shrinks the evicted-only BoN runs away (red) while KVR stays controlled (green). full = full-KV;
Figure 5: Main results. pass@1 vs. base KV budget across the 4×5 grid (Qwen2.5-Math 7B/72B ×N=1,8 ; MATH500, AIME24, AMC23, GSM8K, OlympiadBench). Blue is KV-Rescue (ours), red is eviction-only best-of- N ; dashed and dotted lines mark the base full-KV and helper full-KV references. Best-of- N falls off sharply as the budget shrinks, while KV-Rescue stays close to base full-KV across budgets.
Figure 6: Share of committed steps selected from the evicted 7B base and the full-context 1.5B helper on MATH500 with best-of- N+N decoding: (a) as N varies at budget 128 and (b) as the KV budget varies at N=8 .
Figure 7: A representative problem solved by KV-Rescue but not by either model’s independent trajectory: (a) the evicted base, (b) KV-Rescue, and (c) the full-context helper. Blue and orange mark committed base and helper steps, respectively.
Budget
Method
Acc.
Degen.
Base tok.
Steps
EE
(%)
(%)
(%)
full
full-KV
84.0
2.4
6,106
27
–
64
best-of- N
52.8
13.4
10,587
114
–
+ interleaving
81.8
2.8
7,898
36
–
+ early exit
82.2
0.2
6,327
21
8.0
128
best-of- N
69.2
6.0
7,607
64
–
Table 2: Ablation of interleaving and early exit on MATH500 ( N=8 , Qwen2.5-Math-7B). Rows are cumulative. Degen. is the fraction of incorrect trajectories with at least 256 committed steps, used to identify context-length runaways. Base tok. is the mean number of tokens generated by base-model candidates per problem; Steps is the mean number of committed steps; and EE is the fraction of base candidates terminated by early exit.
Figure 8: Per-sequence KV memory (a) and per-token decode compute (b) of KV-Rescue vs. context length , for a 7B and a 72B base (bf16, R-KV budget 512 , B′=640 ). Bars are KV-Rescue: the evicted base (blue, bounded by the budget) plus the full-KV helper 1.5B (orange). Lines are the full-KV base baseline.
Method
Batch
prob/min
tgen (s)
tscore (s)
72B tok
full-KV
8
6.7
8.41
0.375
5,392
64
OOM
BoN
8
1.2
44.45
1.619
18,144
64
3.2
12.84
0.193
18,371
KV-Rescue
8
4.2
12.67
0.410
5,951
64
10.6
4.58
0.034
5,460
Table 3: MATH500 wall-clock efficiency (Qwen2.5-Math-72B, N=8 , KV budget 64; optimized engine with batched eviction and dynamic KV reserve). prob/min : steady-state throughput (excludes one-time load); tgen : per-problem generation time (base πb and full-context helper πh run concurrently); tscore : PRM time; all amortized over batch concurrency. Max length 4096; full-KV OOMs at batch 64.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 9: KV-Rescue. (a) Best-of- N under KV eviction draws every candidate from the same lossy cache, so the information lost to eviction leads the base to produce wrong or degenerate steps. (b) KV-Rescue samples steps from an evicted base πb and a full-context helper πh ; an online degeneration detector prunes degenerate base steps, the PRM commits the best step st , and base and helper steps interleave.
model
L
d
hkv
dh
dffn
P
base 7B
28
3584
4
128
18944
7.62×109
base 72B
80
8192
8
128
29568
72.7×109
helper 1.5B
28
1536
2
128
8960
1.54×109
Appendix
Table 4: Model constants used in the derivation (from each model’s config.json ).
Figure 10: KV-Rescue with SnapKV eviction (Qwen2.5-Math-7B). pass@1 vs. base KV budget over the five benchmarks (MATH500, AIME24, AMC23, GSM8K, OlympiadBench), for N=1 (top) and N=8 (bottom). Blue is KV-Rescue (ours), red is eviction-only best-of- N ; dashed and dotted lines mark the base full-KV and helper (small) full-KV references. Same setup as main results with R-KV replaced by SnapKV.
model
N
budget
MATH500
AIME24
AMC23
GSM8K
Olympiad
7B
1
bon 64
46.8
0.7 ± 1.3
16.5 ± 3.7
54.4
13.8
bon 128
64.4
1.3 ± 1.6
28.0 ± 2.9
81.0
25.8
bon 256
73.6
4.7 ± 1.6
46.0 ± 9.7
92.0
32.9
bon 512
77.0
4.7 ± 2.7
50.0 ± 6.5
95.3
36.1
b2n 64
77.8
12.7 ± 3.9
58.0 ± 5.6
91.8
38.4
b2n 128
78.6
12.7 ± 1.3
60.0 ± 3.5
94.2
39.4
Appendix
Table 5: Accuracy (%, boxed+correct; mean ± std over seeds) vs. base KV budget, for the 4×5 Pareto grid (Qwen2.5-Math 7B/72B, N=1,8 ). bon = evicted-main best-of- N ; b2n = ours (+full-KV 1.5B safety net); full-KV / small full-KV are no-eviction references. Metric identical to the Pareto figure (is_correct ∧ \boxed ; PRM/small-degraded rows excluded). std shown only where > 1 seed (AIME, AMC23).
Reasoning models improve accuracy through extended chains of thought, but their long outputs create a memory and compute bottleneck. 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, which keep the full KV cache. We identify key factors crucial to KV cache eviction accuracy. First, a small fraction of value states have abnormally large magnitudes, and evicting them causes catastrophic failure where models enter repetitive reasoning loops. Second, introducing stochasticity during eviction improves accuracy by increasing cache diversity. Based on these findings, we propose Value-aware Stochastic KV Cache Eviction (VaSE), a training-free recipe that protects large-magnitude value states and promotes diverse eviction decisions. Across six reasoning tasks, Qwen3 models using VaSE with 4x KV cache compression yield higher average accuracies than SOTA selection method at the same sparsity, while outperforming the strongest eviction method by more than 4%. Overall, VaSE bridges the gap between efficiency and accuracy, supporting FlashAttention2 and enabling a static memory footprint for reasoning models.
Ting-Yun Chang, Harvey Yiyun Fu, Deqing Fu +3
University of Southern California · University of Chicago
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 baseline in task performance while delivering 32-43% higher throughput than that method when deployed with vLLM. 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.
Heng Wang, Jielin Qiu, Wenting Zhao +8
Salesforce AI Research · University of Illinois Urbana-Champaign
Reasoning models write most of their KV cache while decoding long chains of thought (CoT), so the cache has to be compressed online under a fixed memory budget. Decode-time methods mostly decide which tokens to evict. We ask how a fixed byte budget should be split between the number of cached tokens and their precision. BreadthKV spends the bytes on more tokens at low precision, combining quantization with eviction, and picks the bit-width for each model and budget with a 60-problem end-to-end calibration, since offline attention error does not predict it reliably. On three reasoning models and four math and science benchmarks, it scores above eviction alone in 17 of 18 settings and produces shorter outputs. Much of what eviction loses comes from derailed runs, which keep reasoning until the length cap without reaching an answer. On Qwen3-8B at our tightest budget, eviction sends 91% of AIME samples to the cap and BreadthKV 40%. Under the same protocol, BreadthKV is statistically indistinguishable from a joint rate-distortion allocator (RDKV) that uses 27% more KV memory-time, and it outperforms our re-implementation of ThinKV.