Keep What You Prune: Archive-Backed Search Below the Reasoning Threshold

Small language models fail at multi-step reasoning in an abrupt, threshold-like way. Below a few billion parameters they cannot simulate a simple rule-following machine for more than a handful of steps. The prompting and search tricks that help large models, such as step-by-step rationales, self-checking, and pruning bad reasoning branches, often make them worse. Evolutionary optimization faced a structurally similar problem and solved it. A population of candidate solutions that must both explore new regions and keep the best solutions found so far does both jobs badly. Handing the "keep" job to a separate, unbounded archive lets the population explore freely, and in some settings this provably speeds up search. This note proposes carrying that separation of search from storage into inference-time reasoning for small models. The model and its active set of reasoning traces do the searching. A separate ledger outside the model's context stores every distinct intermediate state it has found, and nothing is ever lost when the active set prunes a branch.

In two sentences: current thought-level search methods permanently discard branches that a scorer ranks poorly, and for small models the scorer is unreliable, so correct branches get discarded. If discarded branches go into an external archive that search can draw from again, then the population no longer needs to be elitist, and the gain from doing so should be largest exactly where the scorer is worst, below the reasoning threshold.

Core Claim

The claim is an interaction effect, not a general "search helps" statement. Take thought-level search, where a "thought" is one paragraph-sized reasoning step. Consider two ways to run it. In archive-backed, non-elitist search, the active population is fully replaced each round under weak selection, while an unbounded archive keeps every distinct intermediate state. In elitist pruning, the lowest-scoring traces are deleted and the highest-scoring ones duplicated. We predict that the accuracy advantage of the first over the second grows as the per-step scorer becomes less accurate. Because scorer accuracy tracks model scale, the advantage should be concentrated below the emergent threshold. It should move the scale at which accuracy "turns on" downward, rather than adding a constant offset at all scales. If the advantage is flat across scorer quality, or if a well-tuned softer version of elitist selection matches it, the claim fails.

Why the Two Literatures Meet Here

The storage side supplies the mechanism. Non-elitist Evolutionary Multi-objective Optimizers Revisited shows that once an unbounded external archive exists, forcing the population to also be elitist is redundant. Non-Elitist Evolutionary Multi-Objective Optimisation: Proof-of-Principle Results shows a fully generational, archive-backed optimizer drifting across fitness valleys that trap NSGA-II, SMS-EMOA and NSGA-III on NK-landscapes and large knapsack instances. An Archive Can Bring Provable Speed-ups in Multi-Objective Evolutionary Algorithms proves a $\Theta(n)$ speed-up on OneMinMax and LOTZ because the archive stops the population from discarding and then rediscovering the same solutions. A Theoretical Perspective on Why Stochastic Population Update Needs an Archive in Evolutionary Multi-objective Optimization shows the population can then shrink to a small constant. We reuse these ideas directly: an archive, weak selection, a small active population, and rediscovery as a diagnostic.

Two results from this literature also constrain the design. Liang et al. report extreme sensitivity to mutation rate and very large populations. Tanabe and Ishibuchi (Algorithm Configurations of MOEA/D with an Unbounded External Archive) show that control parameters must be re-tuned once an archive is added. For us this means sampling temperature and population size have to be tuned per method, and the fairness of the comparison depends on it.

The threshold side supplies the regime and the motivation. Computational Reasoning of Large Language Models introduces TMBench, a benchmark in which a model simulates a simple rule-rewriting machine step by step. Models under about 4B parameters fail even at the first steps of that simulation, and accuracy decays over 30 steps even for strong models. Other papers identify what small models cannot do: Large Language Models are Better Reasoners with Self-Verification finds that 0.4B and 1.3B models get worse when asked to verify their own answers. Constraint-First Reasoning finds that 1.5B models hallucinate false constraints that derail solving. ModeLing and Measuring Taiwanese Mandarin Language Understanding find that step-by-step rationales hurt small models. Taken together, these negative results rule out any design that asks the small model to judge or store its own state inside its context. Archive admission and scoring must therefore sit outside the generating model.

The closest bridging work motivates the gap without filling it. Thought-Level Beam Search for Reasoning, called Gambit, manages traces as a population at the thought level with prefix reuse. It separates the hardware memory state from the logical tree, but its selection is strictly elitist: pruned thoughts are gone. It was evaluated only on large reasoning models. Amortized Reasoning Tree Search, called ARTS, freezes the proposer and moves decisions to a separately trained 1.5B verifier. It keeps no archive across steps or queries and still ranks by a single score. A Strategic Coordination Framework of Small LMs Matches Large LMs in Data Synthesis shows committees of 7B–8B models matching a 72B model, but as a fixed pipeline with no search state. Our proposal differs from all three in the same place. None of them lets the active search set forget what storage remembers, and none tests whether that matters more as the scorer gets weaker.

We deliberately set aside the tempting claim that an external archive "breaks" the 124-parameters-per-bit law of Finding the Minimal Parameter Budget for Implicit Reasoning. That law concerns reasoning performed inside the weights with no intermediate tokens. Our intervention works at inference time, so it cannot contradict the law. We use that paper's synthetic knowledge graphs, where the number of plausible next hops at each step can be controlled, only as a way to dial search difficulty.

Research Program

The system has three parts, all built around an unchanged small model that proposes thoughts.

The first part is the active population. It holds $\mu$ partial traces. Each round, every trace is replaced by one child. A child's parent is chosen by a $k$-tournament on the scorer, which is weak selection pressure, rather than by keeping the top-$K$ and discarding the rest. With probability $\rho$ the parent is drawn from the archive instead of the population. This re-injection rule addresses an open problem the evolutionary literature flags: those archives are mostly passive and do not feed solutions back into search.

The second part is the archive. Each generated thought is reduced to a canonical intermediate state, such as the current machine state in TMBench, the set of entities reached in a graph hop, or a normalized derived equation or value in mathematics. The state is inserted if it is new. The archive keeps states that are non-dominated on three criteria: scorer value, progress depth, and novelty relative to other archived states. Dominated states are logged but not used for re-injection.

The third part is the external scorer. It is a separate process-level scorer of fixed size, or the frozen ARTS-style verifier where one is available. It is never the generating model judging itself in context.

Final answers are chosen by score-weighted voting over completed traces in the archive. The instrumentation also records the rediscovery rate, meaning the fraction of generated thoughts whose canonical state already exists in the archive or was pruned earlier. This is the language-model analogue of the cyclic rediscovery that Bian et al. identify as the source of wasted evaluations.

The key manipulated variable is scorer quality. We vary it two ways. The natural way is to use scorers of different sizes. The controlled way is to add calibrated label noise to an oracle step-correctness signal. The oracle signal exists on TMBench and the synthetic graphs, where intermediate states can be checked exactly. The controlled version lets us draw the predicted curve directly: archive advantage as a function of scorer error, holding the generating model fixed.

Baselines

The naive reference point is a single greedy pass with a minimal direct prompt. It is compared against the same model with a step-by-step prompt, since prior work suggests the minimal prompt may be the stronger of the two for small models. Both are run at every model scale. They define where the threshold sits without any search.

The budget-matched sampling baseline is Best-of-$N$ with self-consistency voting and with scorer reranking. $N$ is chosen so that the total generated tokens equal those used by our method. It answers whether structured search adds anything beyond spending more tokens.

The strongest existing search method is Gambit-style elitist thought-level beam search. It is reimplemented with prefix reuse, the same thought delimiter, and the same scorer we use. Its prune-and-branch interval and $K$ are tuned on a development split with the same number of configurations we give our own method. Gambit reports absolute gains of +6.7% on HMMT-24 and +3.3% on AIME-25 over the strongest pruning baselines, on large reasoning models only. The file does not give absolute accuracies, and no reported result on Lacuna exists for Gambit on sub-4B models.

On MATH-500, ARTS is the reference: 74.6% at Best-of-16 with a 1.5B flow-matching verifier and a frozen base model, versus 74.7% for a fully fine-tuned 7B GRPO policy (Amortized Reasoning Tree Search). For TMBench there is no reported result on Lacuna for any search method on small models. The paper reports only that sub-4B models collapse and that Gemini-2.5-Pro stays above 90% at step 30. For the synthetic knowledge graphs, no reported search-based result was found on Lacuna.

A best-first tree search baseline keeps a full frontier of unexpanded nodes but always expands the highest-scoring one. It is included because a frontier is already a kind of archive, so it isolates whether storage alone or storage plus non-elitist expansion is responsible for any gain.

Two ablations isolate the key ingredients. One keeps the archive but restores elitist top-$K$ replacement in the active population. The other keeps non-elitist replacement but removes the archive, so pruned states are lost. We also run an oracle-admission variant, in which only truly correct states enter the archive. This is an upper bound, not a competitor.

Every method runs on the same model checkpoints, prompts, scorer, token budget per problem, and hyperparameter search budget. Beating the strongest competitor means one of two things, each with non-overlapping bootstrap confidence intervals across problems:

  • a statistically reliable accuracy gain over tuned Gambit-style search at matched tokens on sub-4B models, together with no loss at larger scales; or
  • moving the threshold scale down by at least one model size in the family.

Why not just…?

Why not just soften elitism with a higher selection temperature? This is the real threat. A beam that samples parents proportionally to exponentiated scores rather than truncating might recover most of the benefit with no archive at all. We include exactly this: an elitist beam with tuned softmax selection and no archive. If it matches the full system across the scorer-noise sweep, the contribution reduces to "use weaker selection." We would report that and drop the archive claim. The evolutionary evidence suggests softening alone is not enough, because non-elitist populations without an archive lose good solutions: this is the truncation-and-rediscovery effect in Bian et al. and the motivation in Ren et al. The rediscovery-rate measurement will show whether the same thing happens with language-model traces.

Why not just use best-first search or tree search, which already keeps every node? A frontier stores nodes, but expansion remains greedy on the scorer. When the scorer is wrong, correct low-scored nodes are stored yet never revisited, which in practice is the same as losing them. The best-first baseline and the archive-plus-elitism ablation separate "remembering" from "revisiting." The prediction is that storage without non-elitist expansion captures little of the gain at high scorer noise.

Why not just spend the same compute on a larger model, or fine-tune the small one? For many deployments that is the honest competitor, so every accuracy curve is also plotted against total inference FLOPs, including a single pass of the next larger model at equal FLOPs. Fine-tuning is out of scope as a method, and prior evidence suggests it does not generalize here. ConceptMath shows targeted fine-tuning lifting a 13B model's ten weakest concepts from 15.29% to 53.36% only with per-concept data. NaturalProofs shows fine-tuned retrieval falling below TF-IDF out of distribution: 13.24 versus 15.79 mAP. If a larger model at matched FLOPs wins everywhere, the method's value is limited to settings where larger models are unavailable, and we would say so.

Why not just have the small model verify and repair its own steps? Self-Verification and Constraint-First Reasoning both show this backfires below the threshold. The small model misreads the verification prompt or invents constraints. This is why scoring and archive admission are external by design.

Proposed Experiments

We use one open model family spanning roughly sub-1B to about 14B parameters as generators, with a fixed external scorer. There are three task regimes, chosen to pull storage and search apart.

TMBench is almost pure state tracking with one correct path, so it tests storage. The prediction there is that the archive's value comes mostly from re-injecting verified states after a trace drifts. The measure is how many steps the small model survives before failing, compared against the reported sub-4B collapse.

The synthetic knowledge graphs of Wang et al. let us raise the number of plausible next hops at a fixed reasoning depth, so search difficulty is controlled. The prediction is that the non-elitist advantage grows with branching.

MATH-500, AIME-25 and HMMT-24 are the realistic setting. There we compare against the ARTS and Gambit reference points above, and break results down by MATH-500 subject. ARTS found its largest gains in Counting & Probability, and the archive should help most where many plausible branches exist.

The decisive checks are three. First, the scorer-noise sweep on TMBench and the knowledge graphs must show the archive-minus-elitist accuracy gap increasing with injected scorer error at a fixed generator. A flat or shrinking gap refutes the core claim. Second, across model scales, the scale needed to reach half of the largest model's accuracy must move down under archive-backed search relative to tuned elitist search at matched tokens. A uniform upward shift instead would mean the method is ordinary test-time compute, not a threshold effect. Third, the rediscovery rate must be measurably higher under elitist and archive-free search than under the full system. That links any accuracy gain to the mechanism the evolutionary theory predicts, rather than to extra diversity from some other source.