ptrnsai

Tree of Thoughts

Advanced🧠 Reasoning PatternsPrinceton (Yao et al., 2023)

Intent

Explore multiple reasoning paths in a tree structure, evaluate them, and backtrack to find the best solution.

Problem

Chain-of-thought reasoning follows a single path — if it goes wrong early, the entire chain produces a bad answer. For problems with many possible approaches, you need the ability to explore alternatives and backtrack when a path looks unpromising. Standard prompting has no mechanism for this.

Solution

Treat problem-solving as a search over a tree of reasoning states. Each node represents a partial solution. From each node, generate multiple possible next steps (branches). Evaluate each branch using a heuristic or LLM-based evaluation. Expand the most promising branches and prune poor ones. This can use breadth-first search (explore all options at each level), depth-first search (go deep, backtrack on failure), or best-first search (always expand the most promising node).

Diagram

                    [Root Problem]
                   /       |       \
             [Path A]   [Path B]   [Path C]
              / \          |         / \
          [A1] [A2]      [B1]    [C1] [C2]
           ✗    ↓         ✗        ↓    ✗
               [A2.1]            [C1.1] ← Best solution
                 ↓
              [Dead end]

When to Use

  • Complex problems with multiple valid approaches
  • Strategic planning and game-playing scenarios
  • Creative writing where you want to explore narrative branches
  • Mathematical proofs and puzzles requiring exploration

When NOT to Use

  • Simple tasks where one reasoning path suffices
  • Latency-sensitive applications — tree search is expensive
  • When the problem has an obvious single approach

Pros & Cons

Pros

  • Explores multiple solution paths, finding better answers
  • Can backtrack from dead ends — no single-path commitment
  • Systematic exploration of the solution space
  • Evaluation of partial solutions enables early pruning

Cons

  • Significantly higher cost — many LLM calls per problem
  • Complex to implement compared to linear CoT
  • Evaluation of partial solutions is itself unreliable
  • Overkill for most practical applications

Implementation Steps

  1. 1Define how to decompose problems into 'thought steps' (nodes)
  2. 2Implement a generator that produces N candidate next-steps from any node
  3. 3Build an evaluator that scores partial solutions
  4. 4Choose a search strategy (BFS, DFS, or best-first)
  5. 5Implement backtracking and pruning logic
  6. 6Set resource limits (max depth, max total nodes, timeout)

Real-World Example

Game of 24

Given numbers [4, 9, 10, 13], make 24 using arithmetic. The tree explores: Path A: 13 - 9 = 4 → 4 × 4 = 16 (dead end). Path B: 10 - 4 = 6 → 13 - 9 = 4 → 6 × 4 = 24 ✓. Tree search systematically finds the solution that linear reasoning might miss.

PromptTree of Thoughts for Puzzle Solving
Solve the Game of 24: use the numbers [3, 8, 7, 1] with basic
arithmetic (+, -, *, /) to make exactly 24. Each number must be
used exactly once.

Explore 3 different approaches. For each:
1. Propose a first operation (combine two numbers)
2. Evaluate: does this path look promising? (score 1-10)
3. If promising (7+), continue expanding
4. If stuck, backtrack and try a different combination

Branch A: [first operation]
  Evaluation: [score]/10 — [reasoning]
  Continue → [next step] → ...

Branch B: [first operation]
  Evaluation: [score]/10 — [reasoning]
  Continue → [next step] → ...

Branch C: [first operation]
  Evaluation: [score]/10 — [reasoning]
  Continue → [next step] → ...

Expand the highest-scoring branch until you find a solution.

References