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-cache eviction removes parts of the history needed for later reasoning, and it remains unclear whether test-time scaling alone can recover the loss. KV-Rescue interleaves reasoning steps from an evicted model and a full-context helper; across five math benchmarks, it recovers an average of 87% of accuracy lost at B=64.

  • Problem

    KV eviction removes past context needed for later steps, and it remains unclear whether test-time scaling alone can recover the resulting accuracy loss.

    Source: Introduction · p. 1

  • Method

    KV-Rescue interleaves reasoning candidates from an evicted base model and a full-context helper, selecting each committed step with a process reward model.

    Source: Introduction · p. 1

  • Results

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

    Source: Introduction · p. 2

  • Takeaways & Limitations

    The observed complementary errors support treating eviction loss as an information gap distinct from model-capacity limits.

    Source: Introduction · p. 1

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

    Source: Reasoning Model Degeneration · p. 2

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

KV-Rescue addresses the information lost when KV eviction restricts a reasoning model’s access to its history by interleaving its steps with those of a lightweight full-context helper. Across five math benchmarks, it recovers much of the accuracy lost to eviction while curbing runaway degeneration.

Introduction

  • An evicted 7B and full-context 1.5B model make complementary errors, and an oracle choice recovers 79% of the accuracy gap to full-KV 7B.Source: Figure 1 · p. 1, Introduction · p. 1
  • Increasing stepwise best-of-N improves evicted-model accuracy but plateaus below full-KV because candidates share the same partial cache and cannot restore missing context.Source: Introduction · p. 1, Figure 1 · p. 1
  • KV-Rescue is a training-free framework that interleaves reasoning steps from an evicted base model and full-context helper, with a process reward model selecting shared-trajectory steps and a detector stopping degenerate candidates.The procedure also extends to best-of-N candidates from each model.Source: Introduction · pp. 1–2
  • At B=64, KV-Rescue recovers an average 87% of eviction-lost accuracy across five math benchmarks with 7B and 72B models, while reducing base-model token generation 43% on average.The reported recovery persists across two eviction methods and model scales.Source: Introduction · p. 2

Preliminaries KV Eviction

Reasoning Model Degeneration

Method

KV-Rescue interleaves candidates from an evicted base model and a full-context helper on one committed reasoning trajectory, using a process reward model to select steps and online signals to stop degenerate base candidates.

Stepwise Interleaved Reasoning

  • At each step, KV-Rescue samples from the evicted base and full-context helper, then commits the candidate with the highest process-reward score.Both models continue from the same trajectory but retain distinct context views: the base processes helper-selected tokens and applies eviction, while the helper receives the full committed context.Source: Stepwise Interleaved Reasoning · pp. 2–3

Online Degeneration Detection

  • High moving-average entropy flags incoherent candidates, while a low gzip ratio flags repetitive loops; either signal terminates a base candidate before scoring.Both signals use quantities already available during decoding and require no additional model forward pass; helper candidates keep the pool nonempty if all base candidates are aborted.Source: Online Degeneration Detection · pp. 3–4

KV-Rescue

Experiments

Across the tested budgets and model settings, KV-Rescue stays closer to the full-KV reference than eviction-only best-of-N; at B = 64 it recovers an average of 87% of the full-KV accuracy loss. It also prevents length-cap runaways, reducing base-model token generation by 43% in the reported 7B, N = 8 analysis.

Experiment Setup

  • Experiments use Qwen2.5-Math 7B/72B bases, a full-context 1.5B helper, and a 7B PRM; pass@1 is reported on five math benchmarks.AIME and AMC are averaged over five seeds; other benchmarks use one run, with the official grader and temperature 0.8, top-p 0.95, and top-k 20.Source: Experiment Setup · p. 4
  • Main comparisons use N = 1 or 8 base candidates per method, with KV-Rescue also drawing N helper candidates; helper decode compute is 24% of 7B and 2.5% of 72B.Comparisons match base-model candidate and eviction budgets rather than total policy candidates.Source: Experiment Setup · p. 4
  • R-KV uses λ = 0.1, a 128-token protected recent window, and B ∈ {64, 128, 256, 512}, with a full-KV reference also evaluated.The physical cache bound is B′ = B + 128.Source: Experiment Setup · p. 4

Experiment Results

  • At B = 64, KV-Rescue recovers an average of 87% of full-KV accuracy loss across the 4 × 5 grid, remaining closer to full-KV than eviction-only best-of-N.The grid spans Qwen2.5-Math 7B/72B, N = 1/8, and five math benchmarks; increasing N generally improves both methods but does not eliminate the gap under aggressive eviction.Source: Experiment Results · p. 4, Figure 5 · p. 5
  • At B = 64 with the 7B base and N = 8, KV-Rescue reduces base-model token generation by 43% on average across benchmarks and prevents length-cap runaways.As B decreases, eviction-only generations inflate in length as degeneration approaches the output cap.Source: Experiment Results · pp. 4–5

Discussion

The discussion attributes recovery to combining complementary base and helper steps, limiting runaway degeneration, and reducing the decode cost of aggressive KV eviction.

Recovering KV-Eviction-Induced Information Loss

  • The helper supplies 17–34% of committed steps, with its share rising from 17% at budget 512 to 33% at budget 64, while the base contributes most steps.In the example, the base loses track of the requested quantity while the helper retains the target but errs in derivation; interleaving avoids both failures.Source: Recovering KV-Eviction-Induced… · p. 5

Degeneration Analysis

  • At budget 64, interleaving lowers degeneration from 13.4% to 2.8%, mean trajectory from 114 to 36 steps, and raises accuracy from 52.8% to 81.8%.Eviction-only best-of-N raises degeneration from 2.4% under full-KV to 13.4%; sampling alone does not prevent runaways from the shared evicted cache.Source: Degeneration Analysis · pp. 5–6, Table 2 · p. 6
  • At budget 64, early exit fires on 8.0% of base candidates, cuts base-model tokens 20% (7.9k→6.3k) without reducing accuracy, and lowers degeneration to 0.2%.It terminates runaway branches during generation; degeneration is eliminated under the table’s criterion at budget 128.Source: Degeneration Analysis · p. 6, Table 2 · p. 6

Efficiency Analysis

  • At 4k context, 72B KV memory is 0.31 vs. 1.25 GiB for eviction and full-KV, while the helper adds ∼2.5% of 72B per-token compute (∼24% for 7B).The comparison holds generation length fixed; the helper’s KV grows with context but remains small.Source: Efficiency Analysis · p. 6
  • At batch 64, KV-Rescue achieves 3.3× throughput over eviction-only best-of-N and reduces base-model generation by 70% (18.4k→5.5k tokens per problem).The shared-resource setup also allows batch 64, which full-KV cannot fit.Source: Table 3 · p. 6, Efficiency Analysis · p. 6

Related Work

Related work reduces KV-cache memory within a single model or improves test-time inference by selecting candidates, whereas KV-Rescue interleaves reasoning steps from policies with asymmetric context access. It operates above eviction mechanisms and can be combined with different eviction policies.

KV cache compression

  • KV-cache compression uses quantization, merging, or eviction, while SmallKV guides large-model eviction with a full-cache small model but leaves generation to the large model.KV-Rescue instead treats the small model as an independent reasoning policy and interleaves its steps with the evicted base’s; it is orthogonal to eviction policies.Source: Related Work · pp. 6–7

Test-time and multi-model inference

  • Best-of-N and PRM-guided search select candidates from a single policy conditioned on the same context, unlike KV-Rescue’s selection across policies with asymmetric context access.KV-Rescue uses the full-context policy to recover information unavailable to the evicted base.Source: Related Work · p. 7
  • Speculative decoding uses a small model to draft tokens while preserving the large model’s output distribution, whereas KV-Rescue lets either model contribute a committed reasoning step.KV-Rescue targets reasoning quality under KV eviction rather than accelerating an unchanged target policy.Source: Related Work · p. 7

Conclusion

KV-Rescue bridges information loss from KV eviction by interleaving reasoning from an evicted large model and a lightweight full-context model. It recovers accuracy and reduces generation and throughput costs under severe KV memory constraints.

Conclusion

  • 87% of accuracy lost at eviction budget 64 was recovered on average across five math benchmarks, while base-model token generation fell by 43%.The evaluation used Qwen2.5-Math 7B and 72B.Source: Conclusion · p. 7
  • At batch 64, KV-Rescue achieved 3.3× the throughput of eviction-only best-of-N, while full-KV runs ran out of memory.Source: Conclusion · p. 7
  • KV-Rescue is a training-free framework that interleaves reasoning steps from an evicted large model and a lightweight full-context model, terminating degenerate base candidates online.The models make complementary errors, and much of the loss from eviction is attributed to missing information rather than limited model capability.Source: Conclusion · p. 7

KV-Rescue vs KV Evicted Best-of-N

KV-Rescue addresses KV-evicted best-of-N’s shared-context limitation by interleaving steps from an evicted base model and a full-context helper, pruning degenerate base candidates before selection.

KV-Rescue vs KV Evicted Best-of-N

  • Under KV eviction, best-of-N candidates share the base model’s missing context, so PRM selection and sampling cannot recover evicted information.The base may answer incorrectly or degenerate into incoherent or repetitive steps until the length cap (Fig. 9a).Source: KV-Rescue vs KV Evicted Best-of-N · p. 9
  • KV-Rescue samples steps from the evicted base and full-context helper, prunes degenerate base candidates, selects the best surviving step, and re-bases both caches.Committed steps from the two models interleave, with each covering the other’s failure and helping recover the correct trajectory (Fig. 9b).Source: KV-Rescue vs KV Evicted Best-of-N · p. 9

KV-Rescue Pseudocode

KV-Rescue decodes by sampling candidate reasoning steps from an evicted base model and a full-context helper, then committing a selected step to their shared trajectory.

KV-Rescue Pseudocode

  • Each decoding step samples candidates from both models and aborts generation of any candidate that triggers the online degeneration detector.The base samples from its compressed cache, while the helper uses full context.Source: KV-Rescue Pseudocode · p. 9
  • The PRM commits the best non-degenerate step, both caches re-base onto the shared prefix, and decoding continues until an <eos> step or length cap L.Source: KV-Rescue Pseudocode · p. 9

Implementation Details

KV-Rescue interleaves steps from an evicted Qwen2.5-Math base and a full-KV helper, with a process reward model selecting steps and an online detector filtering degenerate base candidates. Its implementation uses fork-based decoding and a fixed-budget base cache.

  • The base is Qwen2.5-Math-7B-Instruct (or 72B for scaling), the full-KV helper is Qwen2.5-Math-1.5B-Instruct, and Qwen2.5-Math-PRM-7B scores each candidate step (Yang et al. 2024; Zhang et al. 2025).The PRM’s step score is the softmax probability of the positive label at the final token, using a double-newline step separator; models run in bfloat16.Source: Implementation Details · p. 9
  • R-KV (Cai et al. 2025) compresses only the base cache to B ∈ {64, 128, 256, 512}, with a 128-token headroom buffer and λ=0.1; the helper and PRM retain full KV.R-KV ranks cached tokens using query-attention importance and key redundancy, retaining the top-B tokens plus a recent window.Source: Implementation Details · p. 9
  • With N=8, a fork-based vLLM v1 engine scores eight candidates from each model per step and accepts the PRM’s best without history re-prefilling or backtracking.Accepted helper steps are encoded into the base cache in one forward pass; continuous batching lets problems score and retire independently. The PRM and helper run asynchronously alongside base decoding; for the 72B base, the base uses TP=8 and the PRM TP=4.Source: Implementation Details · pp. 9–10
  • Base candidates are discarded when mean per-token entropy exceeds 7.0 or the minimum gzip ratio in an 800-token sliding window falls below 0.18.The entropy check uses a 24-token guard and a 12-token window; both signals come from decoding and add negligible cost.Source: Implementation Details · p. 10
  • Evaluation uses pass@1 on MATH500, AIME24, AMC23, GSM8K, and OlympiadBench, with temperature 0.8, top-p 0.95, top-k 20, and a 4096-token maximum context.Generation allows up to 1024 reasoning steps and 512 tokens per step; final boxed answers are scored with the official Qwen2.5-Math grader, and AIME24 and AMC23 are averaged over five seeds.Source: Implementation Details · p. 10

Overhead Derivation

The derivation shows how KV eviction bounds cache memory while adding scoring overhead that is repaid only beyond a decode-length crossover. The lightweight helper adds a smaller per-token cost as the base model grows.

KV memory

  • For the 7B model, each cached token uses 28 KiB; full-KV memory grows as m_kvℓ, while eviction holds it constant at m_kvB′.B′=B+w is the physical KV bound.Source: KV memory · p. 11
  • At ℓ=8k with B=512, eviction yields a model-size-independent ℓ/B′ saving of 8192/640 ≈12.8× on base-model KV memory.The eviction saving follows from the full-context cache growing linearly with ℓ while the evicted cache is bounded by B′.Source: KV memory · p. 11
  • At ℓ=4k, B=512, N=8, full-BoN/MKVR memory is 1.75/1.15 ≈1.5× for a 7B base and 10.0/2.44 ≈4.1× for a 72B base.The helper's full-context KV dominates MKVR when the base is small and is negligible when the base is large.Source: KV memory · p. 11

Decode compute

  • At ℓ=4k, attention is 11% (7B) / 7% (72B) of forward compute, so bounded-KV attention saves little compute at short context.Per-token forward cost combines a context-independent dense component with attention cost linear in the number of cached tokens.Source: Decode compute · p. 11
  • Evicted decoding becomes cheaper beyond ℓ⋆≈2500; its gap reaches about 2% at 4k and 6% at 12k.Below ℓ⋆, R-KV scoring outweighs the attention it saves. At ℓ=4k, the 1.5B helper adds about 24% of base-candidate cost for a 7B base and 2.5% for a 72B base.Source: Decode compute · p. 11

Experiment Results

The experiments report pass@1 across a 4 × 5 grid and show that KV-Rescue’s recovery pattern persists when SnapKV replaces R-KV.

Main Result

  • Table 5 reports exact pass@1 values across the 4 × 5 Pareto grid of model sizes, KV budgets, and N settings.It reports accuracy as boxed-and-correct percentage, with mean±std over seeds; the caption excludes PRM and small-degraded rows.Source: Main Result · p. 11, Table 5 · p. 13

KV-Rescue with SnapKV

  • With SnapKV replacing R-KV, Figure 10 shows the same recovery pattern, supporting KV-Rescue’s agnosticism to the eviction method.KV-Rescue treats the base as a black-box policy conditioned on the cache retained by the evictor; SnapKV is cited as Li et al. 2024.Source: KV-Rescue with SnapKV · p. 11, Figure 10 · p. 12

Related papers

Loading 2608.15797v1…