Search over Reasoning Steps

The trap of the nearest step

Start at 1. The moves are +2, ×2 and −3. Reach 19.

Always taking the move that lands closest to 19 gives 1 → 3 → 6 → 12 → 14 → 16 → 18. From 6 onward every number is even, and only −3 can make an even number odd, but −3 always looks like a step backwards. The route that works, 1 → 3 → 5 → 10 → 20 → 17 → 19, passes through 5, which looked worse than 6 at the second move.

This is the problem Chapter 1's search addressed for planning. Language models face it every time a reasoning step closes off options.

Search families

All of them repeat one cycle: propose continuations of current states, evaluate them, select which to keep, and expand again.

• Greedy keeps the single best state. Cheap, and trapped by any misleading early score.
• Beam search keeps the best $k$ distinct states each round. The lab implements exactly this over integers, ranking by distance to the target.
• Best-first / A* keeps a priority queue across depths and can return to an old state.
• Monte Carlo Tree Search repeatedly selects a path using visit counts and value estimates, expands a state, evaluates it (often with a rollout or a value network) and backs the value up through its ancestors. AlphaGo combined MCTS with policy and value networks. Established

A tiny count

In the lab, each kept state proposes three moves. With width $k$, a round makes up to $3k$ proposals, each costing one check.

Width 3 spends more than width 2 for the same answer here; on target 29, only width 3 succeeds within six moves. There is no universally right width, only a budget and a task.

Over text instead of integers

Tree of Thoughts ran breadth- and depth-first search over “thoughts”, coherent chunks of text, using the language model both to propose next thoughts and to evaluate states; on the Game of 24 puzzle, GPT-4's success rate rose from 4% with chain-of-thought prompting to 74%. Established

The integer lab hides the hard parts of doing this with text:

• What is a state? A line of a proof, a paragraph, a partial program? The granularity decides how many choices exist.
• Who scores it? A heuristic, the model judging itself, a trained verifier or an executable check. A model's opinion of its own partial work can be confidently wrong.
• When to stop? A known goal (19) is easy. Open-ended questions have no goal test, so search needs a separate verifier.

Reasoning models trained with RL may learn to explore and backtrack within a single long chain of thought, without an external search procedure. Interpretation Whether that internal behaviour amounts to search in the algorithmic sense is a research question; do not assume a product runs an explicit tree unless its documentation says so.

Mini experiment

In the lab, set target 29 and six moves. Try widths 1, 2 and 3 and note which succeed and the checks each uses. Then reduce the moves to 5 with width 3. Write one sentence on what width bought and one on what it could not buy.