Structured Reasoning as Search

A language model still generates one token after another. Search adds an outer controller that decides which model call to make next, which partial result to retain, and when to stop. A chain retains one continuation. A beam retains several at the same depth. A tree can revisit alternatives, while a graph can also reuse or combine earlier work. The model still generates tokens in every case; the search procedure allocates model calls around those generations.

This chapter isolates inference-time control. The proposal model's weights need not change during a request, but that does not mean the whole system was obtained without training. A partial-state scorer, value model, or outcome model may have been trained separately. Keeping that boundary explicit prevents a prompted tree and a trained AlphaZero-like system from being treated as the same method.

A search problem needs an interface

Calling intermediate text a “thought” does not yet define a search problem. The controller needs a task-specific interface:

A state is the task information used to predict valid continuations and outcomes. A search node is bookkeeping: it can also hold a parent pointer, incoming action, depth, path cost, score, and visit count. Different nodes may represent the same state. That distinction matters once the controller tries to merge duplicate work.

Let $x$ be the request, $s_0$ its initial state, $a$ a thought-sized action, and $T(s,a)$ the successor state. The proposal distribution $\pi_\theta(a\mid s)$ supplies possible actions from model parameters $\theta$; it does not choose which search node to expand. The frontier policy makes that choice.

Suppose $\mathcal{T}_B(x)$ is the collection of terminal states actually evaluated before budget $B$ is exhausted. An oracle objective would be

$$s^\star \in \arg\max_{s\in\mathcal{T}_B(x)} q(s),$$

where $q(s)$ is the unknown task quality of terminal state $s$, and $s^\star$ is a best evaluated state under that quality. Writing the objective does not make the oracle objective executable. A deployed controller instead has whatever evidence the task exposes. With an observable terminal checker $G(s)\in\{0,1\}$ and an optional utility $U(s)$, it can select

$$\widehat s \in \arg\max_{s\in\mathcal{T}_B(x):G(s)=1} U(s).$$

Here $G(s)=1$ means that $s$ satisfies the checker's encoded acceptance condition, $U(s)$ ranks accepted states, and $\widehat s$ is the returned state. If no exact checker exists, the final selector may use a learned or prompted estimate, a vote, or human review. Those are weaker observations of quality, not replacements for $q$. Answer voting is also a property of the candidate collection, not a verifier applied to one terminal state.

Branching consumes the budget quickly

If every nonterminal state produces $b$ children and search reaches maximum depth $D$, a full tree contains

$$N_{\text{full}} = \sum_{d=0}^{D} b^d = \begin{cases} D+1, & b=1,\\ \dfrac{b^{D+1}-1}{b-1}, & b\ne 1. \end{cases}$$

Here $b$ is the effective branching factor after proposal filtering, $D$ is the maximum depth, $d$ indexes a depth, and $N_{\text{full}}$ counts the root and every generated node. At $b=4$ and $D=8$, the total is 87,381 nodes. The relevant $b$ is not the model's vocabulary size. It is the number of thought units or actions the expansion function actually admits at each node, and the total above counts all generated nodes.

A beam of width $w$ limits retained states, not necessarily proposals. Under the simplifying assumptions that every retained state produces exactly $b$ distinct children and no state terminates early, the generated-node count for $D\ge 1$ is at most

$$N_{\text{beam}} \le 1+b+(D-1)wb.$$

The first expansion produces $b$ nodes; each later layer expands at most the beam width $w$. This linear bound is the reason beam search is practical. It does not guarantee that a valid path remains in the beam. A small $w$ controls work by making pruning irreversible.

Token counts alone also miss part of the bill. A more honest total-work account is

$$W_B = \sum_{(s,a)\in E_B} c_{\text{gen}}(s,a) + \sum_{s\in Q_B} c_{\text{score}}(s) + \sum_{s\in C_B} c_{\text{check}}(s).$$

In this expression, $E_B$ is the set of generated state-action expansions, $Q_B$ is the set of scored states, and $C_B$ is the set of checked terminal states within budget $B$. The three $c$ terms are their measured costs. Generation cost depends on prefix length, output length, cache reuse, and batching. A prompted evaluator can cost another decode, while an executable check may be cheap per call but expensive to engineer. Parallel calls can reduce wall time when capacity exists; they do not reduce $W_B$.

Frontier policies make different sacrifices

“Tree search” names a data structure, not one algorithm. The frontier rule determines what gets explored and what can be lost.

Breadth-first and depth-first search do not require a learned value. Beam and best-first search do. Monte Carlo tree search (MCTS) repeats selection, expansion, leaf evaluation or simulation, and backup. A common selection form from UCT is (Kocsis and Szepesvári 2006)

$$a_{\text{UCT}} = \arg\max_{a\in\mathcal{A}(s)} \left[ Q(s,a) + c\sqrt{\frac{\log N(s)}{1+N(s,a)}} \right].$$

Here $\mathcal{A}(s)$ is the set of currently available actions, $Q(s,a)$ is the backed-up mean return for action $a$, $N(s)$ is the visit count of state $s$, $N(s,a)$ is the action visit count, and $c>0$ controls the exploration bonus. An implementation must also force or otherwise handle unvisited actions. AlphaZero-style PUCT adds a proposal-policy prior; it is not merely best-first search under another name.

Classical guarantees depend on assumptions that language-model controllers often break. Breadth-first completeness assumes finite branching and a solution at finite depth. Optimal graph search needs correct transitions, a correct goal test, and appropriate cost or heuristic conditions. Sampled actions, finite budgets, learned scores, and beam pruning remove those guarantees. The algorithmic name alone does not restore them.

A pruned branch cannot recover later

This runnable example uses a deliberately misleading partial-state heuristic. The fast branch looks best at both of its visible states but ends in failure. The patient branch starts with a lower score and reaches the only verified solution.

GRAPH = {
    "start": [("fast", 0.90), ("patient", 0.70)],
    "fast": [("dead_end", 0.95)],
    "patient": [("bridge", 0.60)],
    "bridge": [("solution", 1.00)],
}
VERIFIED = {"dead_end": False, "solution": True}

def beam_search(width):
    frontier = [("start", ["start"], 0.0)]
    while frontier:
        candidates = []
        for state, path, _ in frontier:
            if VERIFIED.get(state, False):
                return path
            for child, heuristic in GRAPH.get(state, []):
                candidates.append((child, path + [child], heuristic))
        frontier = sorted(
            candidates,
            key=lambda item: item[2],
            reverse=True,
        )[:width]
    return None

for width in (1, 2):
    path = beam_search(width)
    result = "no verified solution" if path is None else " -> ".join(path)
    print(f"width={width}: {result}")

The output is width=1: no verified solution and width=2: start -> patient -> bridge -> solution. Width one commits to fast and cannot return to the pruned alternative. Width two retains both branches long enough for the terminal check to distinguish them. A wider beam raises candidate coverage, but it also raises work. It helps only if the expansion function proposes the useful branch and the partial-state evaluator keeps it alive.

Graphs mean two different things here

A state-space graph and a thought workflow solve different problems.

In graph search, a transposition occurs when different paths reach the same task state. A reached table can then avoid expanding that state twice. This requires a canonical state key that preserves everything relevant to future actions and outcomes. The same text can refer to a different hidden state when tool versions, files, database contents, permissions, or prior side effects differ. Conversely, two differently worded traces may encode the same symbolic state. Merging by surface text alone is therefore unsafe. Cyclic state spaces also require cycle detection, a closed set, or explicit reopening rules.

Graph of Thoughts (GoT) uses “graph” in a broader dataflow sense. Its vertices are thought units, while edges can encode generation, aggregation, refinement, or feedback (Besta et al. 2024). A later operation may consume two earlier results without claiming that they are equivalent states. The published system used human-designed operation graphs, task-specific prompts, parsers, and scorers. On four tasks chosen to support these transformations, including a sorting benchmark, set intersection, keyword counting, and document merging, tailored GoT schedules outperformed the adapted baselines reported in the paper. That evidence supports programmable composition on those tasks. It does not demonstrate automatic semantic merging or a general-purpose graph-search algorithm.

Value guidance is a bet on partial evidence

For a rollout policy $\rho$, the ideal state value is

$$v^\rho(s)=\mathbb{E}[R(s_T)\mid s,\rho],$$

where $s$ is the current state, $s_T$ is the terminal state reached by continuing under $\rho$, $R(s_T)$ is its terminal return, and the expectation averages over stochastic proposals or environment outcomes. A prompted confidence score, a local process score, and an estimate of remaining path cost are not automatically estimates of this same quantity. Their scales can also drift with depth.

Let a controller observe

$$\widehat v(s)=v^*(s)+\varepsilon(s),$$

where $v^*(s)$ is the true continuation value for the controller's objective, $\widehat v(s)$ is its observed score, and $\varepsilon(s)$ is evaluator error. Search selects states with the highest observed score, so it also selects unusually positive errors. This selection bias becomes more important as the controller compares more states or optimizes the same scorer more aggressively (Gao et al. 2023). A score calibrated on ordinary traces may also become out-of-distribution on prefixes created by deeper search. False pruning is the opposite error: one underestimated state is removed before its delayed payoff becomes visible.

Prompted self-evaluation illustrates the dependency. Self-evaluation-guided stochastic beam search used the same language model under different generation and evaluation prompts, combining step confidence with model likelihood (Xie et al. 2023). It improved the reported arithmetic settings, but matched-budget results were not uniformly better on commonsense tasks. The method is useful evidence that partial scoring can guide a beam, not evidence that the model supplies an exact verifier of its own work.

The published systems are not interchangeable

Several influential systems share a generator-evaluator loop, but their controllers and training assumptions differ.

Tree of Thoughts does not establish that trees dominate repeated sampling on arbitrary tasks. Its Game of 24 result is striking, but the task exposes compact intermediate equations that can be judged before completion. GoT likewise selected tasks where aggregation and refinement were meaningful. TS-LLM shows what trained critics can add, but those critics cross the training boundary established at the start of this chapter.

AlphaEvolve offers a related, broader example. It performs evaluator-guided evolutionary search over programs, not beam search or MCTS over natural-language thoughts. Its white paper reports a rank-48 procedure for multiplying $4\times4$ complex matrices and a Borg scheduling heuristic that Google reports recovers an average 0.7 percent of fleet-wide compute (Novikov et al. 2025). Automated evaluation made those searches actionable. The result is not evidence that language tree search is generally superior.

Operating a search controller

A production implementation needs more than an algorithm name.

1. Define the state schema, legal action schema, canonicalization rule, terminal test, and final output contract. Reject unparsable states before they enter the frontier.
2. Calibrate the evaluator on states generated by the controller that will use it. A held-out set of direct answers does not measure behavior on deep, selected prefixes.
3. Compare direct generation, repeated sampling, best-of-$n$, and structured search in a matched-budget evaluation. Match total generated tokens, scorer calls, checker calls, model versions, and wall-clock capacity; report latency separately.
4. Put hard limits on nodes, depth, generated tokens, tool calls, dollars, memory, and the wall-clock deadline. Stop early on verified success only when the task contract permits it.
5. Define a fallback for an empty frontier, parser failure, evaluator timeout, no accepted terminal, and conflicting checkers. A service may return a direct answer, abstain, or escalate, but the choice should not be implicit.

Tool-using search needs one more boundary: speculative branches should not commit irreversible external effects. Run checks in sandboxes or transactions, separate read-only exploration from approved writes, and deduplicate idempotent calls.

Per-request telemetry should record the prompt and model version, controller and evaluator version, expansion count, generated-token count, frontier size by depth, deduplication rate, evaluator scores, checker outcomes, selected path, stopping reason, fallback path, total work, and latency. Offline analysis should separate candidate coverage, selected-answer accuracy, false pruning, selector regret, cost per accepted answer, and tail latency.

Structured reasoning search is an allocation layer. The proposal model supplies possible actions; the controller chooses where to spend work; the evaluator changes which branches survive; and the checker determines what evidence can stop the search. The next chapter changes the state representation itself by moving some work from natural-language traces into programs, solvers, and proof checkers.

Further reading