Explicit versus learned search

Updated 23 Oct 2026

Neural-guided tree search and search-trace learning.

Giving a language model more computation does not specify how it should use it. An external controller can maintain a tree, revisit alternatives and ask learned models where to search next. Alternatively, the model can learn to perform the search in its own generated sequence: proposing branches, evaluating their consequences and returning to earlier decisions.

In 2025, I built research systems for both approaches. The work began as a joint Stanford CS224N project with Yalcin Tur and Mihajlo Stojkovic and developed into my CS224R implementation of batched neural-guided Monte Carlo Tree Search, iterative policy/value training, and Stream-of-Search learning. I was the lead developer of the later system and conducted its experiments.

The central connection was not just a comparison between two inference algorithms. The external search system also became a teacher. A single tree supplied successful paths for the policy, intermediate return targets for the value model, and whole traversals for a model learning to search in language.

The experiments studied two connected questions: how learning changes the performance of an external search system, and what happens when the search procedure itself becomes the training target. Training and search proved complementary, policy and value capacity interacted, and the comparison with internalized search depended on the budget and training configuration. This article and the consolidated report bring the methods and results into one account.

Explore: search architecture · batched execution · learning signals · experiments and results · artifacts.

Where the search lives

“Explicit versus learned” is useful shorthand, but both systems contain learned components. The external controller uses a neural policy and a separately trained value model. The internalized version learns a distribution over textual search procedures.

The operational distinction is who manages the branches and where the state is stored.

The external controller can return to a stored node without regenerating the entire route to it. A search-in-language model can condition its next decision on the preceding traversal, including alternatives that did not become the final answer. These are different computational interfaces, not a division between brute force and intelligence.

The work follows two complementary lines: TS-LLM, which couples learned policies and values to tree search, and Stream of Search, which represents exploration as a sequence that a language model can learn.

A task with an inspectable search structure

The later system used a generalized arithmetic game. Given input integers and a target, construct an expression using every input occurrence exactly once, the four basic arithmetic operations and parentheses. A repeated number is a repeated resource: two threes may be used twice, but one three may not.

The task gives the system three useful objects: a language representation of a partial state, multiple alternative next steps, and an independently checkable final expression. The policy emits arithmetic steps and the remaining numbers. These intermediate descriptions are model-generated text; the final-expression checker, rather than a symbolic transition engine validating every intermediate sentence, supplies the terminal training labels.

One question in the original report asks the model to use $3,3,5,12$ to make $51$. There are distinct routes:

Final-answer-only supervision does not explicitly show the explored alternatives or how the search returned to earlier states. That distinction motivated exporting more than accepted solutions.

A custom neural-guided search engine

For each question, the implementation builds a tree of partial textual trajectories. A node stores its parent and children, visit count $N$, running backed-up value $Q$, an initial learned value estimate and observed terminal labels.

Selection trades off the current value estimate against exploration. The implemented score for a child $u$ of node $s$ is

At a leaf, the policy samples candidate next steps. Duplicate candidates are removed, and the value model scores the resulting partial trajectories. Their estimates initialize the new nodes. Later visits back up values through the ancestors, updating running means and visit counts.

The training and evaluation paths share this search machinery but use different terminal feedback. During data generation, the expression checker provides a terminal success label. During evaluation, learned values guide search and final selection; the checker scores the selected final expression afterward. Finding a correct expression somewhere in a tree and successfully selecting it are different outcomes.

The repository’s final-path selection follows the child with greatest backed-up $Q$ at each step. That is separate from the exploration score above. Keeping the exploration rule, the final-selection rule and the training labels explicit is essential to understanding what the system does.

Making search a batched workload

A single search tree alternates between dependent decisions. Serving one request at a time would turn that dependence into GPU idle time. I reworked the engine around a forest of independently advancing trees.

Each tree submits a request containing its question and partial trajectory, then awaits a future. A shared queue collects requests across trees. The serving layer batches policy generation, gathers the resulting child states, batches their value evaluations and resolves the waiting trees’ requests. A tree can continue as soon as its own expansion returns.

This separates three concerns: the search controller manages state, the serving layer performs neural inference, and the generator or evaluator decides how to consume the completed tree. It also makes policy and value models independently configurable rather than treating them as one inseparable model.

One tree, three learning products

The tree is useful beyond the answer it returns. The generator extracts three distinct forms of supervision, each with a different purpose.

Policy improvement

An initial synthetic successful-solution dataset first taught the policy the arithmetic response format. Subsequent iterations used newly generated search trajectories: accepted terminal paths become prompt/completion examples for supervised fine-tuning. In conceptual form, the policy objective is

After training, the updated policy generates the next round of search data. The loop is search → extract successful trajectories → train → search again. The dataset therefore evolves with the policy rather than remaining a fixed set of demonstrations.

A learned value at intermediate steps

The value model is trained from both successful and unsuccessful terminal trajectories. Its targets include the intermediate states along those trajectories. Where terminal outcomes have been backed up through a state, their mean supplies a soft target; the generator has a terminal-label fallback where such observations are absent. These are empirical targets under the sampled search, not exact optimal values of the arithmetic state.

In the later implementation, a causal language model supplies the value through one designated vocabulary logit. Its sigmoid is the scalar estimate. Training aligns value labels to newline-token positions marking the question and successive steps, masks every other position and padding, and applies binary cross-entropy at the labelled positions:

Here $J$ denotes the labelled step positions. The custom trainer checks the alignment between newline positions and supplied labels before computing the loss. This gives the controller a trainable evaluator for partial progress, not just a reward attached to the final answer.

Teaching the traversal, not only the winning path

For search-in-language training, the generator records nodes in first-visit order and serializes their relationships. A nonterminal entry names its node and parent. A terminal entry can include its ancestor chain. The sequence is wrapped in thought markers and followed by a separately marked selected accepted expression.

The representation makes a crucial distinction: two consecutive lines in the stream need not be consecutive steps on one solution path. Parent references tell the model where each explored state belongs.

An abbreviated illustration of the format is:

Q | Use 3, 3, 5, 12 to make 51.
<START_THOUGHT>
N1->Q | 3*12=36 Left: 3, 5, 36
N2->Q | 12*5=60 Left: 3, 3, 60
N3->N1 | 3*5=15 Left: 15, 36
N4->N2 | 3*3=9 Left: 9, 60
N5->N2 | 60-3=57 Left: 3, 57
N6->N5 | 57-3=54 Left: 54
N7->N6->N5->N2->Q | 12*5-3-3=54
...
<END_THOUGHT>
<START_ANSWER>
3*12+3*5=51
<END_ANSWER>

This is an explanatory excerpt, not a complete training record. The route ending at $54$ is unsuccessful, yet belongs in the traversal that teaches the search process. The full records include the remaining visited states and terminal references.

The model is initialized from a pretrained checkpoint and fine-tuned on these traversals. “Learning search” here does not mean pretraining a new foundation model from nothing. It means teaching a model to reproduce a search process and emit a final answer within one generated sequence.

The project also implements a STaR-style rejection/self-training path: generate attempts, keep successful completions and use them for further fine-tuning. The later study compared one attempt per new question with up to ten attempts, retaining the first successful completion in the latter variant. This follows the broader STaR idea of learning from successful reasoning; the implemented refinement is rejection-based supervised self-training.

Historical experiments and results

The investigation progressed through two related settings. The first varied learned proposal and evaluation capacity on Game of 24. The second generalized the arithmetic target and used the external system to teach search in language.

Policy and value capacity interact

The CS224N study used SmolLM2 models and independently varied the policy and value model across 135M, 360M and 1.7B parameters. At a common search configuration, the following matrix records accuracy in percent. Rows vary the value model; columns vary the policy. The entries retain the original report’s mean and standard deviation.

For a fixed 135M policy, changing the value model from 135M to 360M raised reported accuracy from 12.29% to 15.95%. Moving instead to a 1.7B value model produced 10.53%. With the 1.7B policy, the largest value model achieved the highest entry in its column, 26.87%. A larger evaluator was therefore not uniformly the better partner: the useful allocation depended on both sides of the proposal–evaluation interface.

Learning shifts the search curve

Increasing inference-time search was one lever; improving the models guiding that search was another. In the 135M/135M experiment, the later training iteration shifted the search-accuracy curve upward across the displayed range. Search-generated supervision improved what a subsequent search could achieve, rather than merely increasing the size of a fixed model’s tree.

The size sweeps revealed a further interaction. The smallest system’s plotted curve flattened earlier, while the 360M/360M and 1.7B/1.7B systems continued improving across their larger explored budgets. The table below gives the highest accuracy and corresponding search settings reported for each same-size policy/value pair. The 135M peak includes a later training round than the 135M curve in the size-sweep figure.

All three listed configurations used temperature 1.0 and exploration constant 0.3. They are separately chosen peak configurations, not equal-cost points. Branching controls how many candidates an expansion proposes; expansion count controls how much additional tree exploration the controller performs. The latter is not the structural depth of the arithmetic problem.

From a search teacher to search in language

The CS224R study moved to generalized arithmetic targets and Qwen2.5 models: a 1.5B policy plus a 1.5B value model for external search, and a 3B model for learning the traversal. Repeated policy/value updates improved the external system’s search curve. The final checkpoint reached 51.13% in the training-checkpoint evaluation reported below.

The trained external system then generated the full traversals used to teach the 3B model. Separate traversal-trained models were constructed for seven tree-branching configurations. The comparison included plain Stream of Search and the two rejection-self-training variants described above.

The comparison shows a budget-dependent crossover. Search-in-language variants, particularly the stronger rejection-self-trained variant, led at several smaller and intermediate plotted budgets. External MCTS continued improving and led at the largest comparison point. The longest-traversal SoS configurations dropped in accuracy; the original report proposed a context-length explanation, which remains a hypothesis rather than an isolated cause.

What the experiments establish

The useful result is a connected design space, not a universal winner. Learning can improve the proposals and values used by external search; the resulting search can in turn supply supervision for internalized exploration. Policy capacity, evaluator capacity, branching, expansion count and traversal training all influence that cycle. A meaningful comparison accounts for both the repeated solve cost and the teacher-search/training investment that can be amortized over later queries. It also separates finding a correct branch from selecting it, and varying one frozen model’s inference budget from training different search models. External and internal planning research provides a broader setting for these questions.

These are historical results from the two 2025 studies, with their settings and original figures kept distinct. The refreshed verifier and maintenance checks do not rerun or retrospectively rescore them. Reported axes are historical budget or proxy measures, not newly measured end-to-end FLOPs; equal total parameter counts do not equalize inference or teacher-search cost. The matrix’s dispersion is preserved as reported standard deviation, not reinterpreted as confidence intervals or independent-seed uncertainty. The evidence supports these observed trade-offs, not a general or asymptotic separation between the architectures.

Contributions and continuity

The early project was a team effort. My contributions included MCTS implementation, evaluation and writing; Yalcin Tur and Mihajlo Stojkovic contributed policy/value training, data generation and infrastructure. I subsequently led the later implementation, repeatedly reworked the search engine, added the search-in-language pipeline and ran its experiments. The original CS224R contribution statement records those roles. This article and the consolidated report are my technical retrospective on that joint work.

Code, report and released models

The companion repository contains the search engine, policy/value serving, generators, trainers and evaluation paths. Its historical evidence archive preserves earlier evaluation summaries, all recovered plotting-array versions and source provenance, with offline inspection and plot-recreation tools. Those developmental records are kept distinct from the final-report figures shown here. CPU regression checks exercise arithmetic verification and evaluation accounting without downloading models or running training. GPU training and generation remain separate workflows with explicit environment, data and model prerequisites.

Selected released artifacts include a policy checkpoint, a step-value checkpoint and a traversal-trained checkpoint. These are examples of the project’s different learning products, not a prescribed matched comparison set.

The consolidated report presents the methods and empirical results in one document. Its typesetting source and version record accompany the PDF. The original Stanford reports remain historical sources for that account, rather than alternative primary versions readers must assemble themselves.

This work connects to the systems I later built for distributed agent training and evaluation and to learning from hindsight. In each case, the question is not just how to obtain a useful outcome once, but how to convert the computation behind it into a reusable improvement process.

References

• Feng et al. AlphaZero-like Tree-Search Can Guide Large Language Model Decoding and Training, 2023/2024.
• Gandhi et al. Stream of Search: Learning to Search in Language, 2024.
• Zelikman et al. STaR: Bootstrapping Reasoning With Reasoning, 2022.
• Schultz et al. Mastering Board Games by External and Internal Planning with Language Models, 2024/2025.
• Tur, Stojkovic and Raychev. Size Doesn’t Matter If You Search Enough, Stanford CS224N, 2025. Historical project report; its tables and original figure assets underpin the earlier study above.
• Raychev, Tur and Stojkovic. In-context Search: Efficiency Boost or Fundamentally New Capability?, Stanford CS224R, 2025. Historical project report.