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 shows several approaches to the problem. Failed paths are discarded, and promising paths are explored further.

flowchart TD
    problem[Problem]
    problem --> method1[Method 1]
    problem --> method2[Method 2]
    problem --> method3[Method 3]

    method1 --> success1((Success))
    method2 --> fail2((Failure))

    method3 --> method31[3-1]
    method3 --> method32[3-2]
    method3 --> method33[3-3]
    method31 --> success3((Success))

CoT vs ToT

How it works

1. Generate several possible next steps
2. Evaluate how promising each step is
3. Keep exploring the promising paths
4. Discard dead ends
5. Repeat until success or the search budget is exhausted

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.

flowchart TD
    start[Make 24 from 3, 3, 8, 8]
    start --> path1[3+3=6 -> state: 6,8,8]
    start --> path2[3x8=24 -> state: 3,8]
    start --> path3[8 divided by 3 minus 8 over 3]

    path1 --> path1b[6+8=14 -> state: 14,8]
    path1b --> fail1((Failure))
    path2 --> fail2((Cannot proceed))
    path3 --> success((Success))

Performance gain

The NeurIPS 2023 ToT paper (arXiv:2305.10601) measured the following success rates on the Game of 24 with GPT-4.

• CoT: 4%
• ToT: 74% (under the paper's GPT-4 and Game of 24 conditions)

Search strategies

The original paper uses BFS and DFS. The best-first and score examples below explain general search concepts, not additional experimental results from the paper.

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.

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

Cost-performance trade-off

Compare on the same problem set including candidate-generation and evaluation costs. Complexity alone does not justify the additional cost.

Limitations

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

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)

Related concepts

• 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 search problems such as the Game of 24, success rates rise sharply over CoT. Candidate generation and evaluation add API calls and cost.

CoT suits simple reasoning with clear steps. ToT suits problems requiring several approaches and alternative paths after failure. 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.