Structured Reasoning as Search

Once a model is allowed to write intermediate work, the next question is how to move through that work. A chain commits to one path. A tree keeps its alternatives alive, and a graph goes further still, letting partial results be combined, revised, and reused. Search is the family of methods that turns reasoning from "produce the next token" into "choose which partial state deserves the next unit of compute." It is still inference-time work on a frozen model, as in Chapter 24, but the control problem is now explicit.

The State Space Under a Thought

Treat a reasoning trace as a path through partial states. The prompt is $x$. After $t$ reasoning steps, the state is $s_t = (x, z_1, \ldots, z_t)$, where each $z_t$ is a short thought, subgoal, program fragment, proof step, or tool result. The model proposes the next step with a policy $\pi_\theta(z_{t+1} \mid s_t)$, the model itself viewed as a rule for choosing the next step. Some scorer $v(s_t)$ estimates whether the partial state is promising, and a terminal verifier $V(s_T)$ says whether a finished state is correct. The search problem is:

$$\hat{s} = \arg\max_{s_T \in \mathcal{S}_B(x)} V(s_T),$$

where $\mathcal{S}_B(x)$ is the set of terminal states reachable under budget $B$. This notation is deliberately broad. In self-consistency, $\mathcal{S}_B(x)$ is a bag of independent chains and $V$ is often a vote. Tree of Thoughts builds the set by expanding and pruning nodes (Yao et al. 2023). Under AlphaZero-like decoding, the next rollout goes where $v$ or a learned value model points (Feng et al. 2023).

The budget accounting is simple enough to matter:

$$C \approx N_{\text{gen}} C_{\text{decode}} + N_{\text{score}} C_{\text{score}} + N_{\text{verify}} C_{\text{verify}}.$$

Here $N_{\text{gen}}$ counts generated states, $N_{\text{score}}$ counts partial state evaluations, and $N_{\text{verify}}$ counts terminal checks. The constants are not interchangeable. A Python unit test may be cheap, a model-written score may be another full decode, and a formal checker may be cheap to run but costly to author. This is why the verifier ladder in Chapter 27 is not a detail of training alone. It sets the economics of search.

Chains, Beams, Trees, and Graphs

A chain is the degenerate case. It has branching factor one and no memory of alternatives. Its cost is linear in the number of thoughts, and its failure mode is early commitment. Beam search keeps $w$ states after each step, the $w$ best partial solutions found so far. It is useful when a local score is meaningful, but brittle when the score cannot see a delayed payoff. Tree search opens the design further: expand $b$ children, score them, keep a frontier, and allow backtracking. Tree of Thoughts made this pattern concrete by letting the model propose and self-evaluate intermediate thoughts, then running breadth-first or depth-first search over them (Yao et al. 2023).

Graph search removes a hidden assumption of trees. A tree says every partial state has exactly one parent. Many reasoning tasks do not behave that way. A proof can reuse a lemma. Two equivalent states in a planning problem can be merged into one. A data-analysis question can compute two statistics and then combine them. Graph of Thoughts models these intermediate units as vertices and lets edges represent dependency, aggregation, refinement, or feedback, so a later step can consume several earlier thoughts rather than only one parent (Besta et al. 2023). The gain is reuse and composition. The cost is bookkeeping: the system must decide when two thoughts are compatible, redundant, or contradictory.

# A minimal verifier-guided tree search. The details vary, but the control
# problem is stable: generate candidates, score partial states, keep a frontier,
# and spend verification only on finished states.
def search(prompt, budget, width, expand, score, verify):
    frontier = [State(prompt)]
    finished = []
    while budget.remaining() and frontier:
        candidates = []
        for state in frontier:
            for child in expand(state):
                budget.charge_decode(child)
                if child.is_terminal():
                    budget.charge_verify(child)
                    if verify(child):
                        finished.append(child)
                else:
                    budget.charge_score(child)
                    child.value = score(child)
                    candidates.append(child)
        frontier = sorted(candidates, key=lambda s: s.value, reverse=True)[:width]
    return select_best(finished, frontier)

This sketch also shows why search is not a free layer above prompting. If score is noisy, the frontier fills with states that look good rather than states that are good. Near-duplicate proposals from expand spend width on repetition. And when verify is unavailable, the search falls back to a learned reward model and inherits the over-optimization problem of Chapter 19.

Value Guidance and the Board-Game Temptation

The analogy to board-game search is productive but easy to over-read. AlphaZero works because a game state is compact, legal moves are enumerable, the simulator is exact, and win or loss is eventually known. Language reasoning lacks all four properties in their clean form. The state is a text prefix, the action space is a vocabulary or a free-form thought, the transition is another model decode, and terminal correctness may be unavailable. This is why many LLM search systems use the AlphaZero shape without importing the full AlphaZero setting.

The useful import is the separation between proposal and value. The proposal policy says "what could come next." The value model, a learned scorer of how promising a partial state is, says "which partial state is worth another rollout." Self-evaluation guided beam search asks the model to score its own intermediate steps (Xie et al. 2023). AlphaZero-like tree search learns a value function and uses it to guide decoding and later training (Feng et al. 2023). Both methods spend compute on a bet: scoring a partial state is cheaper than fully expanding it, and accurate enough to avoid wasting most of the tree.

That bet fails in predictable regimes. When the value model cannot see the hidden mistake, search amplifies it. A verifier that scores only final answers leaves partial pruning to guesswork. Where the problem has no useful branching structure, a tree only repackages self-consistency with more overhead. Search pays when partial states differ in value before the final answer, and when the system can measure that difference well enough.

What the Search Layer Belongs To

Search can be read three ways in the rest of the book.

• As elicitation. The fixed model already contains useful solution paths, and search is a way to find and select them. This is the view of Chapter 24 and the amplification side of the RLVR debate in Chapter 28.
• As verification infrastructure. Search is only as strong as the scorer or checker in its loop. This connects directly to Chapter 27 and to the model-judge cautions in Chapter 50.
• As agent control. Once a state includes tool results, memory, and actions, this same loop becomes an agent harness. ReAct interleaves reasoning traces and environment actions (Yao et al. 2022); Chapter 41 later treats that loop as production software rather than a prompting pattern.

Search makes the middle layer visible. Below it are model proposals and serving costs. Above it are verifiers, agents, and product latency budgets. The next chapter changes the state itself: instead of making every reasoning step a natural-language thought, it asks the model to hand part of the work to a program, a solver, or a proof checker.

Further reading