Chain-of-Thought › Tree-of-Thought Prompting

Both CoT and least-to-most prompting generate linear sequences of reasoning steps. Tree-of-thought (ToT) prompting (Yao et al., 2023) generalizes this to a tree structure, where the model explicitly explores multiple reasoning paths, evaluates partial solutions, and prunes unpromising branches before committing to a final answer.

In ToT, the reasoning process involves three components. First, a thought generator proposes multiple candidate next steps (thoughts) from the current state. These might be different problem decompositions, alternative arithmetic approaches, or distinct subproblem orderings. Second, a state evaluator assesses the quality or promise of each candidate thought, either by asking the model to score it directly ("Is this a good direction? Yes/No/Maybe") or by running a separate value estimation. Third, a search algorithm (breadth-first, depth-first, or beam search) navigates the tree by following promising branches and backtracking from dead ends.

The power of ToT is most evident on tasks that require non-obvious exploration. The Game of 24, where you must find arithmetic operations combining four numbers to reach 24, is a canonical example. Single-chain CoT rarely finds solutions because the task requires exploring many combinations before finding one that works. ToT succeeds by explicitly generating candidate combinations, evaluating whether each brings the calculation closer to 24, and backtracking when a branch reaches a dead end.

ToT comes at significant computational cost. Exploring a tree with branching factor three and depth four requires up to 81 model calls, compared to one for standard CoT. For most applications, this is prohibitive. But for high-stakes problems where accuracy matters more than cost, and for research into model reasoning capabilities, ToT provides a principled framework for extending CoT to problems requiring explicit search.