Restarts for Compressed Reasoning: Detecting and Repairing Cache-Induced Runaway Generation

Reasoning models write long chains of thought, and the memory that stores their past context (the KV cache, a per-token record of attention keys and values) grows with every token. Compressing that cache, by evicting or low-bit quantizing old entries, saves memory. It also has a failure mode that makes the savings illusory. When the budget is too tight, the model loses track of what it has already established and starts to babble in circles. It then writes far longer traces, which wipes out the latency and memory gains. Hold Onto That Thought calls this the "talkative tradeoff," and ThinKV reports the same stuttering under uniform low-bit quantization. Today the only remedy is to pick a safer, larger budget for every problem in advance.

Combinatorial search hit the same pathology decades ago. A SAT or planning solver can wander into an unproductive region of the search tree and stall. Solvers watch cheap progress signals during search and intervene when a run looks doomed: Horvitz et al. used Bayesian predictors over backtracking depth and assignment rates to trigger restarts, Huang tuned restart frequency from conflict rates, and Bjørner et al. switched strategies when progress thresholds stalled. We propose to carry this idea into compressed decoding. Run each problem at an aggressive cache budget. Keep evicted entries recoverable in a cheap host-memory tier. Monitor the generation for early signs of runaway, and only then either restore the lost context or rewind a short stretch and re-decode with it restored. The bet is that runaway is concentrated in a minority of problems, so paying for a large cache only when it is needed should beat any single static budget on cost per correct answer.

Core Claim

For reasoning models, accuracy and cost are not monotone in the cache budget, because the budget also changes how many tokens get generated. The quantity worth optimizing is the cost of producing a correct answer. Define the total resident-cache cost of one problem as

$$C = \sum_{t=1}^{T} b_t,$$

where $T$ is the number of generated tokens and $b_t$ is the number of cache entries held in GPU memory at decoding step $t$. A static method fixes $b_t$ at a budget $B$, so it pays $B \cdot T(B)$, and $T(B)$ explodes on runaway problems. Our claim is that a stall-triggered controller reaches a lower point on the accuracy-versus-$C$ curve than every static budget. It keeps $b_t$ small by default and raises it, possibly retroactively, only on trajectories predicted to run away.

Three things are new relative to the closest work:

  • The signal is generation progress. ThinKV classifies tokens into reasoning, execution, and transition types using offline-calibrated attention-sparsity thresholds, then applies fixed precision and eviction rules per type. EntroKV sets per-head budgets from real-time attention entropy. Both decide how much to compress from the shape of attention. We decide from whether the generation itself is still making progress.
  • The intervention can be undone. Neither ThinKV nor EntroKV can bring evicted information back once it is gone.
  • There is a rewind action. It is the direct analogue of a solver restart, and no compression method in the file has one.

The search literature plays two roles here. It motivates the design, and it supplies the method: progress-feature predictors and interval-sampled features, the latter echoing how DASH computes features only every few nodes to control overhead. It also supplies the evaluation logic of comparing against a per-instance oracle.

Research Program

The system has three parts.

A recoverable eviction tier. The base eviction scorer is SnapKV-D or H2O, the heavy-hitter methods that Hold Onto That Thought found necessary for reasoning models. Instead of discarding evicted entries, we copy them to host memory in 2-bit form, using a paged layout in the spirit of ThinKV's slot-reuse kernel. GPU-resident memory stays bounded by the budget. Re-promotion is a batched host-to-device transfer of the entries the scorer ranks highest.

A runaway predictor. Every $k$ tokens it reads cheap features:

  • the repetition rate of $n$-grams in a recent window;
  • the token-level predictive entropy and its trend;
  • the current length relative to a length estimate from the prompt;
  • the attention mass the current queries would place on cold-tier keys, sampled sparsely because it requires reading the host tier.

The predictor is a small logistic or gradient-boosted model, in keeping with the Naive Bayes classifier Domshlak et al. used for per-state heuristic choice. It is trained on traces from a held-out set of problems decoded both with and without compression. A trace is labeled runaway if the compressed run fails or exceeds 1.5 times the full-cache length.

An arbitration policy. It has three actions:

  • continue at the current budget;
  • escalate, which raises $b_t$ and re-promotes top cold entries for future steps;
  • rewind, which discards the last $m$ tokens (back to the predicted onset), re-promotes, and re-decodes.

We first use thresholds on the predictor's output. A learned policy in the style of Learning Heuristic Selection with Dynamic Algorithm Configuration is a later extension, attempted only if thresholds leave a measurable gap to the oracle.

The analysis question running through the project is whether runaway is a property of problems, which suits adaptive escalation, or of budgets, which suits a better static choice.

Baselines

The naive reference points. These are the full KV cache, which sets the accuracy ceiling and the cost ceiling, and SnapKV-D at a sweep of fixed budgets. The sweep traces the static Pareto curve. It is the most important comparison, because our claim is specifically that we lie below this curve. All methods use the same models (DeepSeek-R1-Distill-Llama-8B and Nemotron-Nano, both used by Hold Onto That Thought), the same sampling settings, the same maximum generation length, and the same GPU.

The strongest existing method. This is ThinKV. It reports near-lossless accuracy on AIME and LiveCodeBench with 1.3% to 3.7% of the full cache, and less than a 4% accuracy drop at 75× less memory on R1-Llama-8B. It is the strongest competitor because it already adapts compression to the reasoning phase and was designed with the stuttering failure in mind.

We also run EntroKV with SnapKV-D as its underlying operator. EntroKV reports about 98% of full-cache performance at a 30% budget on long-context benchmarks. No reported result was found on Lacuna for EntroKV, H2O, or SnapKV-D accuracy on MATH-500 specifically, so we measure all of them ourselves under identical conditions. Each baseline gets the same hyperparameter tuning budget on the same held-out tuning split that trains our predictor.

What counts as beating them. We beat a baseline if we match its accuracy within one point at lower mean $C$ and lower wall-clock time per solved problem. Equivalently, we beat it if we reach higher accuracy at equal $C$.

The oracle. This is the per-problem best static budget, chosen in hindsight. It is the analogue of the Virtual Best Solver that DASH measured itself against; there, dynamic switching cut mean solve time from 289 s for the static ISAC selector to 241 s for DASH+filt, but still fell short of the oracle.

Ablations. These isolate the key ingredient:

  • escalation without restoration, where the budget grows but evicted entries are not brought back;
  • restoration without rewind;
  • a random-trigger controller matched to our escalation rate;
  • the predictor with the cold-tier attention feature removed, to see whether a cheap text-only stall detector suffices.

Why not just…?

Why not just pick one larger static budget? If runaway hits most problems once the budget drops below some level, a slightly higher static budget will match us at lower complexity. That would kill the idea. The first experiment therefore measures, per problem, how length and correctness change with budget. Adaptive escalation helps only if runaway concentrates in a minority of problems, as stalls do in search. If it does not concentrate, we report that and stop.

Why not just select a budget or heuristic per prompt before decoding? This is the instance-level selection that ISAC performs in search, and DASH beat it because structure shifts mid-search. AgentKV's finding that queries move between distinct subspaces across phases suggests a similar shift during generation (AgentKV). It is still plausible that prompt difficulty predicts runaway well. We test this with a prompt-only predictor that chooses a static budget, using the same training data as our controller.

Why not just add a repetition penalty or n-gram blocking? This is the most serious threat, because it attacks the symptom at near-zero cost. Our hypothesis is that the loops come from lost context. Under that hypothesis, suppressing repetition should turn babble into short wrong answers rather than recovered correct ones. We run repetition penalties at several strengths on top of static SnapKV-D. Their accuracy is compared against the restore-without-rewind ablation at matched $C$. If the penalty matches us, the information-loss hypothesis is wrong.

Why not just train the model to be concise, as BFS-PO does? BFS-PO cuts GSM8K reasoning from 277 to 198 tokens through reinforcement learning with verifiers. But it requires that training and does not limit cache growth at inference. It is complementary rather than competing, and we will apply our controller to a concise model if a checkpoint is available.

Why not just switch between eviction heuristics mid-generation, as the search analogy suggests most directly? Hold Onto That Thought finds that heavy-hitter methods dominate for reasoning models. The per-token scoring overhead saved by switching to KNorm is also small next to the cost of lost context. We therefore expect switching scorers to matter less than controlling how much context is retained. We include a SnapKV-D/KNorm switching variant to check this.

Proposed Experiments

Evaluation uses MATH-500, GSM8K, AIME, and LiveCodeBench. We report accuracy, generated tokens, peak GPU cache memory, $C$, host-to-device transfer volume, and wall-clock time per solved problem. The experiments run in order, and the early ones can end the project.

  1. Runaway census. Across a budget sweep, we plot per-problem length inflation and failure. Our idea needs a heavy tail, with most problems unaffected at tight budgets.
  2. Predictor lead time. We measure the predictor's AUROC for flagging runaway within a fixed number of tokens after onset, and how much the cold-tier feature adds over text-only features. A detector that fires only after hundreds of wasted tokens cannot save cost.
  3. Pareto comparison. We place our controller against the static sweep, ThinKV, EntroKV, repetition penalties, the prompt-only selector, and the oracle, and report the fraction of the static-to-oracle gap we close.
  4. Restore-versus-rewind ablation. This tells us whether stalls can be fixed going forward or require discarding the derailed text, and with it whether the restart analogy actually holds.