Tree of Thoughts Pattern

Overview

Tree of Thoughts (ToT) extends Chain of Thought by allowing agents to explore multiple reasoning branches, evaluate partial solutions, and backtrack when needed—more closely mimicking human problem-solving on complex tasks.

Architecture

                    [Problem]
                        │
            ┌───────────┼───────────┐
            ▼           ▼           ▼
        [Path A]    [Path B]    [Path C]
            │           │           │
        [Eval: 0.3] [Eval: 0.8] [Eval: 0.2]
                        │
                    [Continue B]
                        │
                ┌───────┼───────┐
                ▼       ▼       ▼
            [B1]    [B2]    [B3]

Core Components

Thought Decomposition

Break problem into evaluable intermediate states:

Problem: Write a 4-line poem
Thoughts: Line 1 → Line 2 → Line 3 → Line 4

Thought Generator

Propose multiple candidates at each step:

• Sample independently
• Generate sequentially with diversity
• Use specialized proposers

State Evaluator

Score partial solutions to guide search:

def evaluate_thought(state, thought):
    # Could use LLM or heuristic
    return confidence_score  # 0.0 to 1.0

Search Algorithm

Navigate the tree:

• BFS: Explore breadth-first for thorough coverage
• DFS: Go deep quickly, backtrack on failure
• Best-First: Always expand most promising node

Implementation

def tree_of_thoughts(problem, max_depth=5, branching=3):
    root = Node(state=problem)
    frontier = [root]

    while frontier:
        node = select_best(frontier)

        if is_solution(node.state):
            return node.path()

        if node.depth < max_depth:
            thoughts = generate_thoughts(node.state, n=branching)
            for thought in thoughts:
                child = Node(
                    state=apply_thought(node.state, thought),
                    parent=node,
                    score=evaluate(thought)
                )
                frontier.append(child)

    return best_partial_solution(frontier)

When to Use

Good fit:

• Creative tasks (writing, brainstorming)
• Planning problems with dead ends
• Puzzles and games
• Tasks where exploration beats commitment

Caution:

• Can lead to redundant exploration of low-value paths
• Significantly higher compute cost than linear CoT
• May be overkill for straightforward problems

Graph of Thoughts Extension

Graph of Thoughts (GoT) generalizes ToT:

• Allows merging of thoughts from different branches
• Supports cycles and thought refinement
• Enables reuse of intermediate computations