KV-Rescue: Recovering Reasoning Language Model KV Eviction Loss via Stepwise Interleaving

Minsoo Cheong; Woosang Lim; Vincent-Daniel Yun; Sungjoo Yoo

cs.AIAug 16, 2026

KV-Rescue: Recovering Reasoning Language Model KV Eviction Loss via Stepwise Interleaving

Authors: Minsoo Cheong, Woosang Lim, Vincent-Daniel Yun, Sungjoo Yoo

Organizations: Seoul National University · University of Southern California

Abstract

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

\tau_{\mathrm{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

\tau_{\mathrm{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

\pi_{b}

and a full-context helper

\pi_{h}

; an online degeneration detector prunes degenerate base steps, the PRM commits the best step

s_{t}

, and base and helper steps interleave. The best-of-

N

baseline for comparison is in the Appendix

Dataset	Bud.	BoN	KVR	BoN	KVR	BoN	KVR	KVR
		Steps		Out. len		Base 7B tok		1.5B tok
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\times 5

grid (Qwen2.5-Math 7B/72B

\times

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^{\prime}{=}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	$t_{\text{gen}}$ (s)	$t_{\text{score}}$ (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);

t_{\text{gen}}

: per-problem generation time (base

\pi_{b}

and full-context helper

\pi_{h}

run concurrently);

t_{\text{score}}

: 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

\pi_{b}

and a full-context helper

\pi_{h}

; an online degeneration detector prunes degenerate base steps, the PRM commits the best step

s_{t}

, and base and helper steps interleave.

model	$L$	$d$	$h_{\mathrm{kv}}$	$d_{h}$	$d_{\mathrm{ffn}}$	$P$
base 7B	28	3584	4	128	18944	$7.62\times 10^{9}$
base 72B	80	8192	8	128	29568	$72.7\times 10^{9}$
helper 1.5B	28	1536	2	128	8960	$1.54\times 10^{9}$

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 $\pm$ 1.3	16.5 $\pm$ 3.7	54.4	13.8
		bon 128	64.4	1.3 $\pm$ 1.6	28.0 $\pm$ 2.9	81.0	25.8
		bon 256	73.6	4.7 $\pm$ 1.6	46.0 $\pm$ 9.7	92.0	32.9
		bon 512	77.0	4.7 $\pm$ 2.7	50.0 $\pm$ 6.5	95.3	36.1
		b2n 64	77.8	12.7 $\pm$ 3.9	58.0 $\pm$ 5.6	91.8	38.4
		b2n 128	78.6	12.7 $\pm$ 1.3	60.0 $\pm$ 3.5	94.2	39.4

Appendix

Table 5: Accuracy (%, boxed+correct; mean

\pm

std over seeds) vs. base KV budget, for the

4\times 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

\wedge

\boxed ; PRM/small-degraded rows excluded). std shown only where

>

1 seed (AIME, AMC23).

KV-Cache Eviction

Key-value (KV) cache eviction reduces language-model memory use by removing or compressing cached tokens while preserving useful context.

See all 99 papers

Value-Aware Stochastic KV Cache Eviction for Reasoning Models
Jun 2, 2026Ting-Yun Chang, Harvey Yiyun Fu, Deqing Fu +3LLM Inference Efficiency KV Caching
University of Southern California · University of Chicago
Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning
Sep 3, 2026Heng Wang, Jielin Qiu, Wenting Zhao +8KV Caching Memory-Efficient Optimization
Salesforce AI Research · University of Illinois Urbana-Champaign
Spend Bytes on Breadth: Precision-Count Trade-offs for Decode-Time KV Compression in Long Chain-of-Thought Reasoning
Oct 5, 2026Runguo LiCoT Reasoning KV-Cache Eviction
University of Illinois Urbana-Champaign

Jun 2, 2026J/K move · Enter open · S save

Value-Aware Stochastic KV Cache Eviction for Reasoning Models

Ting-Yun Chang, Harvey Yiyun Fu, Deqing Fu, Chenghao Yang+2

University of Southern California · University of Chicago

LLM Inference Efficiency KV Caching Memory-Efficient Optimization KV-Cache Eviction KV-Cache Compression Large Reasoning Models

Open paper AskPDF arXiv

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.

Abstract

KV-Cache Eviction

Explore similar work

Value-Aware Stochastic KV Cache Eviction for Reasoning Models

Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning

Spend Bytes on Breadth: Precision-Count Trade-offs for Decode-Time KV Compression in Long Chain-of-Thought Reasoning