Tree of Thoughts (ToT) is a search framework that explores and evaluates alternative intermediate reasoning states produced by a language model. A state represents partial progress toward a solution. The system generates candidate continuations, evaluates them and decides which states to expand or abandon.
The original work studied tasks including Game of 24, creative writing and mini crosswords. It showed the value of explicit search on those tasks; it did not establish ToT as the implementation behind every research agent or reasoning model. Yao et al., Tree of Thoughts.
Define the search problem first
For a deployment-plan assistant, an illustrative state could contain the proposed migration order, completed validation checks and unresolved constraints. The application must define:
- Initial state: the known environment and required outcome.
- Expansion: proposed next planning steps.
- Validity: conditions that immediately reject a proposal.
- Evaluation: a score or ranking for promising valid states.
- Termination: a verified solution, exhausted budget or inability to progress.
Keep this as planning unless execution is explicitly authorized. A speculative branch must not perform a production migration just to find out whether its plan was good.
Trace one decision tree
Read diagram source
flowchart TD
S[Need an additive schema migration] --> A[Drop old column first]
S --> B[Add nullable new column first]
S --> C[Require all clients to stop]
A --> X[Reject: active readers need old column]
B --> D[Backfill with checkpoints]
B --> E[Switch reads before backfill]
E --> Y[Reject: incomplete data]
D --> F[Validate then switch readers]
C --> Z[Check against availability requirement]
The diagram is a simplified planning exercise. A production plan also needs compatibility tests, recovery procedures, ownership and rollout measurements. The strongest part of the example is the explicit rejection condition: active readers still depend on the old column. A fluent model-generated score is weaker evidence than an actual compatibility test.
ToT differs from self-consistency: self-consistency commonly samples complete solutions and aggregates answers, while ToT can evaluate partial progress, prune branches and revisit earlier alternatives.
Compare search policies
| Policy | Selection behavior | Tradeoff |
|---|---|---|
| Breadth-first search | Expand all states at the next depth | Broad coverage, rapidly growing frontier |
| Depth-first search | Follow one branch before backtracking | Lower frontier memory, may spend budget on a poor branch |
| Beam search | Retain only the best few states per depth | Bounded work, can permanently discard the solution |
| Monte Carlo tree search | Allocate trials using estimated value and exploration | More bookkeeping; quality depends on rollout/evaluation signals |
ToT can use different search strategies. MCTS is a general search method, not a synonym for ToT. A language-model evaluator does not automatically satisfy the assumptions of a reliable heuristic or give a probability of eventual success.
Calculate the search cost correctly
For branching factor 3 and depth 5, a fully expanded tree contains:
root: 1
depths 1 through 5: 3 + 9 + 27 + 81 + 243 = 363
all states: 364
That is 363 non-root candidate states, not fifteen. API-call count depends on implementation: one call might propose several children; evaluations may be batched; some checks may run without an LLM. State counts, model calls, generated tokens and wall time are different quantities.
For a beam of width 2 with three children per retained state, depth 1 generates 3 candidates, and each of the next four depths generates at most 6: 3 + 4 × 6 = 27 proposals. This assumes no retries, no early stopping, and exactly two retained states whenever available. It saves work by sacrificing coverage.
If each proposal and its evaluation cost an illustrative 500 tokens together, those 27 proposals consume about 13,500 tokens, excluding initial instructions and repeated context. Measure actual serialization and caching before using this estimate for pricing.
Control failures and recovery
| Failure | Repair | Residual cost or risk |
|---|---|---|
| Evaluator prefers persuasive wrong plans | Use constraint checks, tests and calibrated human review | Verifiers have incomplete coverage |
| Early pruning removes the only valid branch | Preserve diversity or allow bounded revisiting | More search cost |
| Duplicate states waste budget | Canonicalize state and track visited alternatives | Equivalence can be difficult to define |
| Search loops without a solution | Cap expansions, tokens and deadline; return unresolved constraints | Some solvable tasks will stop early |
| Branch evaluation performs side effects | Sandbox evaluation and separate authorized execution | Simulation may differ from reality |
| Stale assumptions invalidate the best plan | Revalidate environment before execution | Additional checks and possible replanning |
Backtracking in a search tree means returning to an earlier planning state. It does not undo external actions. A submitted payment, sent message or committed migration needs its own recovery semantics.
Interview practice
Q1: When is ToT worth considering?
When meaningful alternatives exist, partial progress can be evaluated, and a better solution is worth extra computation. It is less attractive for simple extraction or tasks whose intermediate quality cannot be assessed. I would compare a simpler workflow and a strong single-call baseline first.
Q2: What are the most important design choices?
State representation, candidate generation, evaluation, search policy and stopping criteria. A poor state representation loses constraints; a poor evaluator prunes correct branches. Increasing the model budget does not automatically fix either problem.
Q3: Does branching factor three for five steps mean fifteen calls?
Only if a particular bounded procedure defines that call count. A full tree has 363 non-root states. I would calculate the actual policy's expansions and then account for how generation and evaluation are batched into calls.
Q4: How does beam width affect quality?
A wider beam retains more alternatives and usually costs more. It can reduce premature pruning, but an unreliable evaluator may still rank the wrong states highest. Measure the quality/cost curve; width alone is not a correctness guarantee.
Q5: How would you search over code repairs?
Generate candidate patches in isolated workspaces, run relevant tests and retain promising candidates under a budget. Include tests for the reported defect and regressions. A patch passing incomplete tests is a candidate for review, not proof of semantic correctness.
Q6: What should the system return when the budget ends?
The best validated result if it meets the acceptance criteria; otherwise an explicit incomplete outcome with unresolved constraints. Do not label the highest-scoring unverified plan as successful merely because the search has stopped.
Final notes
Recall card: Represent → expand → evaluate → select → stop. Search creates alternatives; verification establishes which properties those alternatives satisfy.
Whiteboard exercise: Draw a width-two search for a schema change. Mark which checks use deterministic code, which require judgment, and the exact boundary where a plan could become an authorized action.