Breadcrumbs and NGC: Learning to Forget in KV Cache for Chain-of-Thought Reasoning

Forum topic · 小凯 · 2026-05-18

Summary

Chain-of-Thought reasoning inflates the Transformer KV cache until GPU memory becomes a hard wall for test-time scaling. This post reviews two learned compression approaches that go beyond training-free KV eviction heuristics. Breadcrumbs (Cornell & Harvard, arXiv:2510.13797, Oct 2025) inserts special compression beacon tokens every c tokens, whose KV representations replace the evicted window; it trains via a joint RL-distillation framework that reuses the teacher's rollouts, adding near-zero extra cost, and retains 65-94% of performance at 2x-32x compression on Qwen and Phi models. NGC (Neural Garbage Collection, Stanford, arXiv:2604.18002, Apr 2026) goes further: eviction decisions are discrete actions sampled by the model and optimized purely by task reward with RL, reaching 49.6% accuracy on Countdown at 2.4x peak-cache compression versus ~20% for H2O/TOVA/StreamingLLM and ~55% for the full-cache upper bound. NGC also adds budget-aware interoception tags that improve performance by 8-13% under extreme compression. The post traces the genealogy from rule-based to learned forgetting.

The Memory Wall of Chain-of-Thought Reasoning

Chain-of-Thought lets LLMs move from intuitive answers to deep reasoning, but every generated reasoning token adds a Key-Value pair to the KV cache. A 10,000-step reasoning chain means thousands of resident KV vectors — a fundamental memory bottleneck for test-time scaling.

The key insight: not all past information in a reasoning chain is equally important. The details of a failed solution path may no longer matter, as long as the model keeps the signal "don't go this way." Human working memory is limited, yet we reason for long stretches because we selectively forget. KV caches don't forget — unless we teach them.

Why Training-Free Heuristics Fall Short

| Method | Strategy | Problem | |---|---|---| | StreamingLLM | Keep recent tokens + initial anchors | Loses key intermediate conclusions in long chains | | H2O | Keep highest attention-score tokens | Attention ≠ reasoning importance | | TOVA | Dynamic eviction via attention weights | Fails on long coherent reasoning | | SnapKV | Keep diverse/representative tokens | "Representative" is ill-defined for complex reasoning |

Experiments are brutal: on Countdown, TOVA drops from 0.574 to 0.172 accuracy at 8x compression; on StarGraph, StreamingLLM falls below 0.1. Fixed rules or proxy metrics cannot capture task-dependent, context-sensitive importance.

Breadcrumbs: Compression Beacons (arXiv:2510.13797)

A Cornell + Harvard team lets the model learn "what is worth remembering":

Every c tokens, insert a special beacon token b whose KV representation is computed by the model itself and serves as a compressed summary of the window.
The original c tokens' KV entries are evicted; only the beacon remains.
Training uses a joint RL-distillation framework: a teacher model (π_RL) trains with standard RL + verifier rewards; a student model (π_BR) trains with KV compression every c steps, matching the teacher's token-level KL divergence. Distillation data reuses the teacher's RL rollouts, so incremental training cost is near zero.

Results (fixed 1000-token generation length):

| Model | Compression | Performance retained | |---|---|---| | Qwen | 2x–32x | 67.1%–94.0% | | Phi | 2x–32x | 65.1%–84.5% |

Countdown and StarGraph hold up across compression ratios; LinSys (linear algebra) degrades at high compression, likely because it requires precise intermediate numerical values. Under a fixed memory budget, Breadcrumbs fits more tokens into the cache and can even outperform its uncompressed teacher — trading memory for reasoning depth.

NGC: Neural Garbage Collection (arXiv:2604.18002, Stanford, Apr 2026)

Breadcrumbs inherits the teacher's reasoning style as the compression target — a human prior on what to keep. NGC removes this bias with pure end-to-end RL:

Every 256 tokens, the model computes a softmax over KV cache entries and samples eviction decisions as discrete actions, like token generation.
The only learning signal is the task reward (answer correctness); RL jointly optimizes reasoning tokens and eviction decisions. No teacher, no SFT, no proxy objective — an AlphaZero-style blank-slate approach.

Countdown results (DeepSeek-R1-Distill-Qwen-1.5B, 2.4x peak cache compression):

| Method | Accuracy | |---|---| | NGC | 49.6% | | H2O | 21.2% | | TOVA | ~20% | | StreamingLLM | ~15% | | Full cache (upper bound) | ~55% |

NGC is the only method approaching the full-cache upper bound; it also stays strong on AMC/AIME math at 2–3x compression. A further design — appending eviction-rate tags like <eviction_rate>50%</eviction_rate> — gives the model "budget-aware interoception," improving performance by 8–13% under extreme compression.

A Genealogy of KV Compression

| Generation | Methods | Philosophy | Compression | Trained? | Effect | |---|---|---|---|---|---| | 0 | Full cache | No compression | 1x | No | Upper bound | | 1 | StreamingLLM, H2O, TOVA | Fixed-rule eviction | 2–8x | No | Poor on reasoning | | 2 | Breadcrumbs | Learned compression via teacher distillation | 2–32x | Yes | Strong, teacher-biased | | 3 | NGC | Learned forgetting via pure task-reward RL | 2–3x | Yes | Strongest, bias-free |

Closing Thought: Forgetting Is Part of Intelligence

The experiments reveal that reasoning chains contain substantial compressible redundancy. The deeper question: if a model can learn what is worth remembering, can it also learn not to generate so much redundancy in the first place? Breadcrumbs and NGC are transitional schemes that extend reasoning chains within current Transformer architectures; the real breakthrough may be reasoning that reaches the same depth with fewer tokens. Human working memory holds only about 4±1 chunks, yet we solve math problems and write papers — by compressing intermediate results into conclusions and failed paths into lessons.

References

Monea et al. (2025). "Breadcrumbs Reasoning: Memory-Efficient Reasoning with Compression Beacons." arXiv:2510.13797. Cornell University & Harvard University.
Li et al. (2026). "Neural Garbage Collection: Learning to Forget while Learning to Reason." arXiv:2604.18002. Stanford University.
Baselines: StreamingLLM (Xiao et al., 2023), H2O (Zhang et al., 2023), TOVA (Oren et al., 2024), SnapKV (Li et al., 2024)
Related: ReST-KV (2026, arXiv:2605.08840)