PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2608.15797v1cs.AIcs.CL

TL;DR

KV eviction saves memory but loses context needed for long reasoning, and test-time sampling alone cannot recover it. KV-Rescue interleaves steps from an evicted base model and full-context helper, recovering 87% of eviction-lost accuracy across five math benchmarks at B=64 while reducing base-model token generation by 43%.

  • Problem

    KV eviction can remove context needed by later reasoning steps, while additional sampling from the same partial cache does not restore the missing information.

  • Method

    KV-Rescue is a training-free framework that interleaves reasoning steps from an evicted base model and lightweight full-context helper, selecting candidates with a process reward model.

  • Results

    87% of eviction-lost accuracy is recovered across five math benchmarks with Qwen2.5-Math 7B and 72B at eviction budget B=64.

  • Takeaways & Limitations

    KV-Rescue recovers eviction-lost accuracy while suppressing runaway degeneration and reducing base-model token generation by 43% on average.

  • Takeaways & Limitations

    The work targets incoherent and repetitive degeneration, leaving gradual failures such as unnecessarily prolonged but coherent reasoning outside its scope.

Abstract

from arXiv · show

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.

Introduction · Preliminaries

KV eviction creates an information gap by removing historical context, causing accuracy loss and degeneration that test-time sampling alone cannot fully recover. KV-Rescue addresses this gap by interleaving an evicted large model with a lightweight full-context helper, recovering most eviction loss while reducing wasted decoding.

  • Introduction: 79% of the accuracy gap to the full-KV 7B model is recovered by an oracle choosing between an evicted 7B and a full-context 1.5B.Their complementary errors support interpreting eviction loss as an information gap distinct from a capability gap.
  • Introduction: Stepwise best-of-N improves evicted-model accuracy but eventually plateaus below full-KV because all candidates share the same missing context.Stepwise selection scores candidates at each reasoning step as generation unfolds.
  • Introduction: KV-Rescue is a training-free framework that interleaves reasoning steps from an evicted base model and a lightweight full-context helper.Both models generate candidates from their respective cache states, and a process reward model selects the step to commit.
  • Introduction: 87% of accuracy lost to eviction is recovered on average across five math benchmarks at eviction budget B = 64.The evaluation uses Qwen2.5-Math 7B and 72B models.
  • Introduction: 43% fewer base-model tokens are generated on average when KV-Rescue suppresses runaway degeneration.An online detector terminates degenerate base candidates during generation.
  • KV Eviction: KV eviction limits future predictions to the highest-scoring B retained cache entries, so reducing B restricts accessible historical information.The cache otherwise grows linearly with sequence length and becomes a major memory cost for long reasoning traces.
  • PRM-Guided Stepwise Best-of-N: Stepwise best-of-N updates a committed reasoning context after selecting among N candidate steps, with shared prefixes enabling one batched scoring pass.A process reward model assigns each candidate step a score conditioned on the question and committed prefix.
  • Reasoning Model Degeneration: Aggressive KV eviction produces incoherent generation and repetition loops that continue to the length limit without producing an answer.Incoherent sequences contain unrelated punctuation, symbols, and mixed-script tokens, while repetition loops repeat a token or phrase.

Method

KV-Rescue interleaves candidates from an evicted base model and a full-context helper along a shared reasoning trajectory, selecting steps with a process reward model. An online detector removes incoherent or repetitive base candidates before scoring while preserving helper candidates as alternatives.

  • Setup: The base model conditions on an evicted cache with budget B, while the helper conditions on the full committed context; both follow the same trajectory.The committed context is c_t = (q, s_<t), and the models retain distinct history views.
  • Stepwise interleaving: At each step, KV-Rescue samples N_b base and N_h helper candidates, then commits the candidate with the highest process reward score.The selected step extends the committed context for the next iteration.
  • Stepwise interleaving: If a base step is selected, its fork persists as the next base state; if a helper step is selected, the base processes it before eviction.The helper continues receiving the full committed context at every subsequent step.
  • Online degeneration detection: The detector terminates base candidates with sustained high entropy or low-entropy, highly compressible repetition loops before PRM scoring.It uses entropy and compressibility signals available during decoding, without an additional model forward pass.
  • Online degeneration detection: Helper candidates keep the candidate pool nonempty when all base candidates are aborted, allowing selection to continue.The overall procedure commits the highest-scoring surviving base or helper candidate.

Experiments

Experiments evaluate KV-Rescue across Qwen2.5-Math 7B and 72B models, five math benchmarks, multiple candidate counts, and KV budgets. KV-Rescue remains closer to full-KV accuracy while mitigating degenerate long generations and reducing base-model decoding cost.

  • Experimental setup: Experiments use Qwen2.5-Math 7B or 72B bases, a 1.5B full-context helper, and a Qwen2.5-Math-PRM-7B verifier.The 7B PRM also guides the 72B base, testing whether a smaller verifier can guide the larger model.
  • Experimental setup: Pass@1 is reported on MATH500, AIME 2024, AMC 2023, GSM8K, and OlympiadBench using the official Qwen2.5-Math grader.AIME and AMC use five seeds; the remaining benchmarks use one run.
  • Experimental setup: 24% and 2.5% are the helper’s approximate per-token decode compute shares relative to the 7B and 72B bases, respectively.Main results use N ∈{1, 8}, with matching base-model candidate and eviction budgets rather than total policy candidates.
  • Accuracy versus KV Budget: 87% of full-KV accuracy loss is recovered at B = 64 across the 4 × 5 grid.The recovery uses (AKVR−Aevict)/(Afull−Aevict) for each setting, while eviction-only best-of-N degrades sharply as B decreases.
  • Generation Length: 43% less base-model token generation is achieved at B = 64 in the 7B, N = 8 analysis across benchmarks.Eviction-only best-of-N shows severe length inflation as degenerate generations approach the length cap, whereas KV-Rescue prevents these runaways.

Discussion

KV-Rescue’s gains arise from complementary, selectively interleaved trajectories: the helper contributes more as eviction worsens, while early exit suppresses degeneration and token waste. The helper adds modest per-token compute, and shared-resource measurements show substantial throughput gains over eviction-only decoding.

  • Complementarity: The full-context helper supplies 17–34% of committed steps, rising from 17% at budget 512 to 33% at budget 64 as eviction becomes more severe.The base still contributes most steps, while the source ratio changes little as N grows.
  • Complementarity: Interleaving combines complementary errors: the base loses the requested quantity, while the helper retains the target but errs in derivation.Interleaving steps from both models avoids both failures and reaches the correct answer.
  • Interleaving and early exit: 13.4% degeneration under eviction-only best-of-N at budget 64 falls to 2.8% with interleaving, while accuracy rises from 52.8% to 81.8%.Sampling alone does not prevent runaways because candidates share the same evicted cache.
  • Interleaving and early exit: At budget 64, early exit fires on 8.0% of base candidates, reduces base-model generation by 20% (7.9k→6.3k), and lowers degeneration from 2.8% to 0.2%.It terminates degenerate branches during generation without reducing accuracy and eliminates degeneration under the table’s criterion at budget 128.
  • Efficiency: The helper adds only ∼2.5% of the 72B base’s per-token compute, compared with ∼24% for the 7B base.Eviction caps the base model’s KV, while the helper’s KV remains small as context grows.
  • Efficiency: At batch 64, KV-Rescue delivers 3.3× eviction-only throughput and cuts base-model generation by 70% (18.4k→5.5k tokens per problem).KV-Rescue serves batch 64 under the capped base KV cache, whereas full-KV cannot fit.

Related Work

Prior KV-cache compression reduces memory through quantization, merging, or eviction, including methods adapted to reasoning models. KV-Rescue differs from closest approaches by treating a full-context small model as an independent policy whose steps interleave with those of an evicted base, rather than merely guiding eviction or drafting tokens.

  • KV cache compression: KV-cache compression reduces memory through quantization, merging, and eviction, with recent methods adapting eviction to reasoning models.
  • KV cache compression: SmallKV uses a full-cache small model to guide large-model eviction, whereas KV-Rescue interleaves independent reasoning steps from the small model and evicted base.The large model remains the sole generator in SmallKV; KV-Rescue operates above the eviction mechanism by using the small model as an independent reasoning policy.
  • Test-time and multi-model inference: Test-time scaling methods use best-of-N or PRM-guided search to select candidates typically sampled from a single policy under the same context state.
  • Test-time and multi-model inference: KV-Rescue draws step candidates from two policies with asymmetric context access, using selection to recover information unavailable to the evicted base.Unlike speculative decoding, which uses the small model to draft tokens while preserving the large model, KV-Rescue interleaves reasoning steps from both policies.

Conclusion

KV-Rescue addresses information loss from KV eviction by interleaving reasoning between an evicted large model and a lightweight full-context model. Its training-free framework also terminates degenerate base-model candidates online.

  • KV eviction reduces memory costs for long reasoning but can remove information needed by later steps.
  • The observed loss is characterized primarily as an information gap, with evicted large and lightweight full-context models making complementary errors.
  • KV-Rescue is a training-free inference framework that interleaves reasoning steps from the two models and terminates degenerate base candidates online.

KV-Rescue vs KV Evicted Best-of-N

KV-evicted best-of-N cannot recover information missing from its shared lossy cache, so candidates may remain incorrect or degenerate. KV-Rescue samples from an evicted base and full-context helper, prunes degenerate base steps, and interleaves surviving steps to recover the correct trajectory.

  • KV-Rescue vs KV Evicted Best-of-N: Under KV eviction, best-of-N samples every candidate from the same lossy cache, leaving the PRM unable to recover evicted information.Candidates therefore share the base model’s missing context.
  • KV-Rescue vs KV Evicted Best-of-N: KV-evicted best-of-N can produce incorrect answers or incoherent and repetitive steps until reaching the length cap.The PRM can only select among candidates that share the base model’s missing context.
  • KV-Rescue vs KV Evicted Best-of-N: KV-Rescue samples candidate steps from the evicted base πb and full-context helper πh at each step.Both caches re-base onto c_t+1 after the PRM commits the best surviving step s_t.
  • KV-Rescue vs KV Evicted Best-of-N: An online degeneration detector prunes degenerate base candidates before selection, allowing committed base and helper steps to interleave over the solution.Each policy’s steps cover the other’s failure and recover the correct trajectory.

KV-Rescue Pseudocode

KV-Rescue decodes by interleaving candidate reasoning steps from an evicted base model and a full-context helper. An online detector removes degenerate candidates, while the PRM selects the best surviving step and both caches re-base on the shared prefix.

  • Decoding pass: Each decoding step samples N_b candidates from the evicted base and N_h from the full-context helper, aborting candidates that trigger deg(·) midgeneration.The base operates on compressed cache E_B(c).
  • Decoding pass: The PRM commits the best non-degenerate step s_t, extending the shared context c.After commitment, both model caches re-base onto the shared prefix.
  • Decoding pass: The loop repeats until an <eos> step or the length cap L is reached.

Implementation Details

KV-Rescue uses a 7B or 72B Qwen2.5-Math base with a full-context 1.5B helper and PRM-guided step interleaving. Base-only KV eviction uses fixed budgets, while candidate degeneration is screened online before selection.

  • Models: The base reasoner is Qwen2.5-Math-7B-Instruct, with Qwen2.5-Math-72B-Instruct used for scaling; the helper is Qwen2.5-Math-1.5B-Instruct.Step selection uses the token-classification Qwen2.5-Math-PRM-7B, scoring the positive-label probability at the final token.
  • KV eviction: Eviction applies only to the base through R-KV, retaining the top-B tokens plus a recent window under budgets B ∈{64, 128, 256, 512}.The headroom buffer is w=128, giving physical KV bound B′=B+w, and the query-attention/key-redundancy mix weight is λ=0.1; helper and PRM caches remain full.
  • Best-of-(N+N) trajectory: KV-Rescue forks base and helper candidates, scores all candidates with the PRM, and appends the selected step while preserving the corresponding model cache.The implementation uses a persistent accepted trajectory and physically copies the evicted base KV slots into fresh blocks, avoiding history re-prefilling.
  • Online degeneration detection: Base candidates are dropped when mean predictive entropy exceeds τent=7.0 or minimum gzip ratio falls below τcmp=0.18.The detector uses a 24-token entropy guard, a 12-token window, and a compression window of width wcmp=800, adding negligible cost.
  • Decoding and evaluation: Evaluation samples at temperature 0.8, top-p 0.95, and top-k 20, using pass@1 on MATH500, AIME24, AMC23, GSM8K, and OlympiadBench.Decoding allows maximum context 4096, up to 1024 reasoning steps, and at most 512 tokens per step; final answers use the official Qwen2.5-Math grader.

Overhead Derivation

The derivation shows that eviction makes KV memory and attention cost bounded in context length, but its scoring overhead is repaid only beyond a crossover near 2,500 tokens. The helper adds modest per-token compute, especially for the larger base model.

  • KV memory: 28 KiB per token is the 7B model’s KV footprint, with full-KV memory growing as Mfull(ℓ)=mkvℓ while eviction fixes Mevict=mkvB′.At ℓ=8k and B=512, ℓ/B′=8192/640 ≈12.8×.
  • KV memory: 1.75/1.15 ≈1.5× versus 10.0/2.44 ≈4.1× is the full-method memory ratio for 7B versus 72B bases at ℓ=4k, B=512, N=8.The helper keeps full KV while the base is evicted, so helper memory becomes more dominant as the base grows.
  • Decode compute: 11% (7B) / 7% (72B) is attention’s share of the forward at ℓ=4k, so bounded-KV attention saves little compute at short context.Dense costs are 15.2 and 145.4 GFLOP/token, while attention costs are 0.401M · ℓ and 2.62M · ℓ FLOP.
  • Decode compute: ℓ⋆≈2500 is the measured crossover: eviction is slightly slower below it, then faster above it, reaching about 2% savings at 4k and 6% at 12k.For B′=640, the crossover corresponds to α ≈2.9, within the estimated [1.5, 3] range for R-KV overhead.
  • Helper overhead: 24% for the 7B base and 2.5% for the 72B base are the helper’s per-token overhead fractions at ℓ=4k.The fixed 1.5B helper cost falls as the base model grows.

Experiment Results

Experiments show that KV-Rescue’s recovery pattern persists when the base model uses SnapKV instead of R-KV. The evaluation spans five math benchmarks, two candidate counts, and a 4 × 5 Pareto grid across Qwen2.5-Math 7B and 72B.

  • Evictor Robustness: KV-Rescue remains effective with SnapKV, indicating recovery does not depend on the specific eviction method.Figure 10 repeats the 7B study with SnapKV replacing R-KV and reports the same pattern.
  • Benchmark Evaluation: The SnapKV evaluation compares pass@1 against base KV budget across MATH500, AIME24, AMC23, GSM8K, and OlympiadBench for N=1 and N=8.KV-Rescue is compared with eviction-only best-of-N, alongside base full-KV and helper full-KV references.
  • Benchmark Evaluation: Table 5 reports accuracy as boxed-and-correct percentages over a 4 × 5 Pareto grid covering Qwen2.5-Math 7B and 72B with N=1 and N=8.The grid compares eviction-only best-of-N, KV-Rescue with a full-KV 1.5B safety net, and no-eviction references.
Loading 2608.15797v1…