Tree-of-Thought & Search-Based Reasoning

Last lesson, the agent revised one line of thought (L129). This lesson, it explores many. That's the leap from chain-of-thought to tree-of-thought — from a single guess to deliberate search.

Why bother? Because a chain of thought is brittle. It reasons left-to-right in one straight line, with no lookahead and no backtracking — so a single wrong early step dooms the whole chain. Humans don't solve hard problems that way; we branch ("what if I try X… no, dead end… back up, try Y"). Search-based reasoning gives the model that ability, and the payoff can be enormous: on the Game of 24, plain chain-of-thought solves ~4% of puzzles while Tree-of-Thoughts solves ~74%.

Chain-of-thought is a guess down one path. Tree-of-thought is a search over many — propose, evaluate, prune, backtrack.

In this lesson:

• Why a single chain is brittle, and Self-Consistency — the simplest search
• Tree-of-Thoughts — the generator, the evaluator, the search, and backtracking
• Graph-of-Thoughts, MCTS, and LATS — and the real cost (and the evaluator bottleneck)
• The 2026 nuance: reasoning models do this internally — so when does explicit search still pay?

Scope: this is search over reasoning. Re-planning & recovering from failure (fixing a broken plan when reality intervenes) is the section's finale, L131 (Replanning & Recovering From Failure).

Chain-of-Thought (CoT) — "let's think step by step" — was a breakthrough: writing intermediate steps dramatically improves reasoning. But it has a structural weakness that no prompt fixes: it's a single, committed, left-to-right path.

• No lookahead. It picks the next step greedily, without checking whether that step can actually lead to a solution.
• No backtracking. Once it commits to a step, it's stuck with it. If step 2 was a dead end, steps 3–10 are wasted, and it can't go back and try a different step 2.
• One wrong early move dooms everything. The error compounds (L114) down the rest of the chain.

The Game of 24 makes this vivid: reach 24 using 4, 9, 10, 13 (each once). A CoT model commits to a plausible-looking first move — say 4 × 9 = 36 — and rides it to a dead end, with no way to undo and try 13 − 9 = 4 instead. The solution (13 − 9) × (10 − 4) = 24 requires exploring and backing out of bad branches — exactly what a single chain can't do. (Play the widget below to feel it.)

The smallest step beyond a single chain isn't a tree at all — it's an ensemble. Self-Consistency (Wang et al., 2022) samples several independent CoT chains from the same prompt (at non-zero temperature, so they differ) and takes the majority vote of their answers:

The intuition: any single chain might slip on a step, but if you sample many, the correct answer tends to be the one most paths converge on — wrong answers are wrong in scattered, inconsistent ways. It's "search" only in the loosest sense (parallel sampling over paths, no branching mid-reasoning — this is the parallelization idea of L118 — Parallelization applied to reasoning), but it's cheap, trivially parallel, and reliably lifts accuracy on reasoning benchmarks. It's the natural baseline before you reach for a real tree.

Tree-of-Thoughts (Yao et al., 2023) makes the search explicit. Reasoning becomes a tree: each node is a partial "thought" (an intermediate state), and the model branches, scores branches, and backtracks. Three components do the work:

1. Thought generator (proposer) — at each state, propose k candidate next steps (not just one).
2. State evaluator — judge each candidate: how promising is it? ToT uses labels like "sure / likely / impossible" (a self-evaluation — this is the L129 — Self-Reflection & Self-Critique/L120 — Evaluator-Optimizer evaluator, now steering a search).
3. Search algorithm — BFS, DFS, or beam search over the tree, expanding the promising branches, pruning the impossible ones, and backtracking out of dead ends.

That's the whole idea: lookahead (evaluate before committing), pruning (drop dead branches), and backtracking (abandon a path and try another). The Game-of-24 jump from ~4% to ~74% comes entirely from this deliberate exploration — same model, smarter control flow around it. It's the test-time compute idea from L120 (Evaluator-Optimizer) again: spend more inference to search for a better answer.

Watch both strategies attack the same Game-of-24 puzzle. Flip between Chain-of-Thought and Tree-of-Thought:

The contrast is the lesson:

• CoT commits to 4 × 9 = 36 and rides it to a dead end — no branching, no backtrack, stuck.
• ToT proposes several first moves, the evaluator prunes the dead ones (10+13=23, 4×9=36), and the search backtracks to follow 13−9=4 → 10−4=6 → 6×4=24. Solved.
• And the metrics show the price: ToT explored more nodes and spent several times the model calls. Search isn't free.

Once reasoning is a search, you can use richer structures and smarter search algorithms:

• Graph-of-Thoughts (GoT) (Besta et al., 2023) — generalize the tree to a directed graph, so thoughts can be merged, aggregated, and refined, not only branched. Useful when sub-solutions need to be combined (e.g., merge-sort-style: solve parts, then aggregate).
• MCTS-based reasoning — borrow Monte Carlo Tree Search from game-playing (AlphaGo's algorithm): balance exploring new branches against exploiting promising ones, using rollouts to estimate which paths are worth deepening. The basis of several 2024–2025 reasoning systems.
• LATS — Language Agent Tree Search (Zhou et al., 2024) — the synthesis: unify ToT + ReAct + reflection under MCTS, so the search is over actions in an environment (tool calls, L121–L126 — Tools → Hands-On: Web Search + DB + Calculator), not just abstract reasoning. This is where search-based reasoning meets agents — searching over what to do, with real observations as feedback.

The throughline: reasoning as search is a design space (chain → self-consistency → tree → graph → MCTS over actions), and you pick the structure and algorithm to match the problem's shape and your budget.

Search is powerful, and it is expensive — two hard truths keep it from being a default:

1. The cost explodes. A tree with k branches and depth d is k candidates × evaluations × d levels — easily 10–100× the model calls of a single chain. Self-consistency multiplies by N. The accuracy gains are real, but so is the bill and the latency: a budget-aware comparison sometimes shows that, per token spent, a simpler method wins. Always weigh the lift against the compute.

2. The search is only as good as its evaluator. The whole tree is steered by the state evaluator — if it can't tell a promising branch from a doomed one, the search prunes the right branch and chases the wrong one. And here's the uncomfortable finding ("larger models excel in generation, not discrimination," 2024): models are often better at generating candidate thoughts than at judging them. Discrimination — the evaluator's job — is the bottleneck. This is the L129 (Self-Reflection & Self-Critique) lesson again: a self-evaluator is unreliable; ground it (a real verifier, a solver, executed tests) and the search gets dramatically better; leave it to pure introspection and it can mislead the whole search.

Two questions before you build a tree: Can I afford the compute? and Do I have a trustworthy evaluator? If either answer is no, search will disappoint.

Here's the twist that reframes this entire lesson. Tree-of-Thoughts was a 2023 prompting technique — and modern reasoning models have largely absorbed it. Models trained for reasoning (the o-series, Claude with extended thinking, and peers) were optimized to explore alternatives, evaluate them, and backtrack inside their hidden chain of thought. When such a model "thinks," it's already doing a search you used to have to scaffold by hand.

The practical consequence: bolting an explicit external ToT harness onto a strong reasoning model is often a bad trade — you pay 10–100× the calls to orchestrate a search the model already does internally, for diminishing (sometimes negative) returns. Reaching for hand-built ToT on every hard problem is a 2023 reflex worth unlearning.

Explicit search still clearly pays off when:

• You have an external, verifiable evaluator — tests, a solver, a simulator, ground truth. Grounding the search in a real signal beats any internal self-eval (the L129 — Self-Reflection & Self-Critique principle).
• You need the search to be inspectable or controllable — auditing, safety, or steering which branches get explored.
• You're using a weaker / cheaper model that doesn't search well internally — external ToT can lift it toward what a reasoning model does natively.
• The search is over actions, not just reasoning (LATS) — exploring real moves in an environment with real feedback, which no amount of internal thinking can substitute for.

The durable idea isn't the ToT prompt — it's the principle: when one line of reasoning is too brittle, explore many and evaluate them. Whether that happens inside the model or in your harness is an engineering choice driven by cost, control, and whether you have a real evaluator.

Reason through these, then use the widget to confirm:

1. Predict: in the widget, why does Chain-of-Thought get stuck on Game of 24 while Tree-of-Thought solves it? Name the two capabilities CoT lacks.
2. What are the three components of Tree-of-Thoughts, and which one is usually the bottleneck?
3. You have a budget for ~5 model calls on a medium-hard math question. Tree search or self-consistency? Why?
4. A teammate wraps a state-of-the-art reasoning model in a hand-built ToT loop and costs 50× more with no accuracy gain. What happened, and when would explicit search have helped?
5. Your ToT search keeps pruning the correct branch and chasing wrong ones. What's broken, and what's the fix?

→ (1) CoT has no lookahead (it can't check whether a step leads anywhere) and no backtracking (it can't undo a bad early move) — so it commits to 4×9=36 and can't recover. ToT branches, evaluates, prunes, and backtracks. (2) Thought generator (propose k candidates), state evaluator (score them — sure/likely/impossible), search algorithm (BFS/DFS/beam + backtrack). The evaluator is the usual bottleneck (discrimination is harder than generation). (3) Self-consistency — with a tiny budget, sampling ~5 chains and voting is cheap, trivially parallel, and robust; a real tree needs more calls per useful branch. (4) The reasoning model already searches internally during extended thinking, so the external ToT harness duplicated it at huge cost (2026 nuance). Explicit search would help with a verifiable external evaluator, a weaker model, an inspectable requirement, or action search (LATS). (5) The state evaluator is weak/ungrounded — it can't discriminate good branches. Ground it in a real verifier (a solver, executed tests, a checkable heuristic) instead of pure self-evaluation.

• "Chain-of-thought can solve anything if it just thinks longer." A longer single chain still can't backtrack — one wrong early step dooms it. You need branching, not more length.
• "Tree-of-Thoughts is a prompt." It's a search procedure — a generator, an evaluator, and a search algorithm with pruning and backtracking around the model. The prompt is the small part.
• "More branches = better." More branches = more cost (10–100×), and a wider search with a weak evaluator just prunes the right answer faster. Width without a good evaluator is wasted compute.
• "The model can evaluate its own branches fine." Discrimination is harder than generation — a self-evaluator is the bottleneck. Ground it (real verifier) wherever possible (L129).
• "Self-consistency is the same as ToT." Self-consistency is parallel sampling + vote (no branching mid-reasoning); ToT is a structured search with intermediate evaluation and backtracking.
• "Always use ToT for hard problems." In 2026, reasoning models search internally — explicit ToT often duplicates that at huge cost. Reach for it with a verifiable evaluator, a weak model, an inspectable need, or action search.
• "It's free accuracy." It's paid accuracy — in tokens and latency. Always compare per-budget, not just peak score.

• Search beats a single chain on brittle problems. CoT is one linear path with no lookahead or backtracking — one wrong early step dooms it. Search-based reasoning explores many paths.
• Self-Consistency (Wang 2022) is the simplest search: sample N chains, majority-vote — an ensemble over paths; cheap and parallel.
• Tree-of-Thoughts (Yao 2023): generator (propose k thoughts) + state evaluator (sure/likely/impossible) + search (BFS/DFS/beam) with pruning & backtracking. Game of 24: ~4% → ~74%.
• Generalizations: Graph-of-Thoughts (merge/aggregate), MCTS (explore vs exploit), LATS (ToT + ReAct + reflection + MCTS — search over actions).
• The catch: search costs 10–100× the calls, and it's only as good as its evaluator (discrimination > generation is the bottleneck) — ground the evaluator and weigh the compute.
• 2026: reasoning models search internally during extended thinking, so explicit external ToT is largely subsumed — reserve it for a verifiable evaluator, inspectable search, weak models, or agentic action search.
• The durable principle: when one line of reasoning is too brittle, explore many and evaluate them — inside the model or in your harness, your call.
• Next — L131: Replanning & Recovering From Failure — the section finale: what an agent does when reality breaks its plan mid-run.