Tree of Thought (ToT)

Multi-path reasoning that branches out like a tree

Concept

Unlike Chain of Thought, which follows a single path, Tree of Thought (ToT) explores several possible paths at once and selects the most promising one.

Structure

The diagram below shows the flow: the problem branches into several approaches, failed branches are discarded, and only the promising branch is explored more deeply.

CoT vs ToT

CoT	ToT
Single path	Multiple paths
Stops on failure	Backtracks on failure
Fast	Slow (search cost)

How it works

Generate several possible next steps
Evaluate how promising each step is
Keep exploring the promising paths
Discard dead ends
Repeat until success

Example: the Game of 24

Given the numbers 3, 3, 8, 8, make 24.

Method 1: $3+3+8+8 = 22$ -- failure
Method 2: $3 \times 8 = 24$ -- the remaining 3 and 8 cannot be handled -- failure
Method 3: $8/(3-8/3) = 24$ -- success

The search

The diagram below expands the three methods into a tree, showing two paths hitting dead ends and being discarded while one reaches 24.

Performance gain

The original ToT paper (Yao et al. 2023, arXiv:2305.10601) measured the following success rates on the Game of 24 with GPT-4.

CoT: 4%
ToT: 74% (roughly an 18x improvement)

Search strategies

ToT can use several search strategies.

BFS (breadth-first search)

Expands every candidate equally, level by level.
Example: Level 1 = A, B, C -> Level 2 = A1, A2, B1, B2, C1, C2
Advantage: hard to miss a solution, and short paths are easy to find.

DFS (depth-first search)

Digs one path to the end, then backtracks on failure.
Example: A -> A1 -> A1-1 (failure) then A -> A2 -> A2-1 (success)
Advantage: uses less memory and validates a promising path quickly.

Best-first search

Prioritizes candidates by their promise score.

Candidate	Score	Search order
A	0.9	1
B	0.7	2
C	0.3	3

Evaluating promise

Ways to evaluate how promising a node is:

Value prompting

Example question: "What is the probability of solving the problem from this state?"
Output format: score each candidate state on a 1-10 scale

Vote prompting

Example question: "Which of the following states is the most promising?"
Candidates: A: state 1, B: state 2, C: state 3
Decide the next path by majority or weighted vote

When to use ToT

Situation	Recommended technique
Simple reasoning	CoT
Problems with clear steps	CoT
Problems with several viable approaches	ToT
Problems that require search	ToT
Problems where another approach must be tried on failure	ToT

Cost-performance trade-off

Technique	API call cost	Problem-solving performance
CoT	Low	Moderate
ToT	High	High (strong on complex problems)

ToT requires more API calls, but on complex problems that cost is worth paying.

Limitations

Compute cost: exploring several paths raises cost
Evaluation accuracy: the promise estimate can be wrong
Search space: a search space that is too large becomes inefficient

An extension: LATS

LATS (Language Agent Tree Search), an extension of ToT, adds the following:

ReAct (external tool use)
Reflexion (learning from failure)
Monte Carlo Tree Search (more efficient search)

Chain of Thought (CoT): single-path reasoning
LATS: ToT + ReAct + Reflexion combined
Monte Carlo Tree Search: a search algorithm used in game AI

Summary

Instead of following one path, ToT generates several candidate paths, evaluates how promising each node is, and backtracks away from hopeless branches. On problems that require search, such as the Game of 24, the success rate rises sharply over CoT, but candidate generation and evaluation add API calls and therefore cost. So simple reasoning with clear steps belongs to CoT, and problems where several approaches must be tried and another route found on failure belong to ToT. When the search space is too large or the promise estimate is inaccurate, efficiency drops. The strategy (BFS/DFS/best-first) and the evaluation method therefore have to be matched to the problem.