4. Tree-of-Thought: Exploring Solutions

Overview

Tree-of-Thought (ToT) is a technique proposed by Yao et al. in 2023 that takes LLM reasoning to a new level of complexity. Where CoT generates a single linear chain of thoughts, ToT organizes the reasoning as a tree: each node is a "thought" or partial state of the solution, and the tree is explored systematically to find the best path to the answer.

The analogy is how a chess player thinks: they don't just play the first move that comes to mind, they consider several options, evaluate the consequences of each one a few moves ahead, and pick the most promising line.

Limitations ToT Solves

CoT fails on problems that require exploration

Consider the "Game of 24" problem (use exactly the operations +, -, ×, ÷ with 4 numbers to get 24):

Input: [4, 9, 10, 13]

Pure CoT:
Thought: I'll try 4 + 9 = 13, then 13 + 13 = 26... doesn't work.
Answer: I can't find the solution.  ← FAILS

ToT:
Branch A: 4 + 9 = 13 → (13 × 13 = 169... no) → PRUNE
Branch B: 10 - 9 = 1 → (1 × 4 = 4 → 4 × ... no) → PRUNE
Branch C: 13 - 9 = 4 → (4 × 4 = 16... 10 + 16 = 26... no) → PRUNE
Branch D: 10 + 4 = 14 → (14 - 9 = 5... 5 × 13 = 65... no) → PRUNE
Branch E: 9 - 4 = 5 → (5 × 13 = 65... no) → PRUNE
Branch F: 13 × 4 = 52 → (52 - 9 = 43... no) → PRUNE
Branch G: (10 - 4) × (13 - 9) = 6 × 4 = 24 ✓ → SOLUTION FOUND

ToT Architecture

                    [PROBLEM]
                   /     |     \
         [Branch A]  [Branch B]  [Branch C]
            (0.3)    (0.8✓)    (0.5)
                      |  \
             [Branch B1]  [Branch B2]
                (0.9✓)     (0.4)
                   |
             [FINAL SOLUTION]

Key components

1. Thought generator: Generates K candidate thoughts from a state
2. State evaluator: Scores how promising each state is (0-1 or "sure/likely/impossible")
3. Search algorithm: BFS, DFS, or Beam Search to explore the tree
4. Terminal check: Detects when a complete solution has been reached

Base Implementation

from openai import OpenAI
from dataclasses import dataclass, field
from typing import Optional
import json

client = OpenAI()

@dataclass
class Node:
    """Represents a node in the tree of thoughts."""
    content: str                      # The thought at this node
    parent: Optional['Node'] = None   # Parent node
    children: list['Node'] = field(default_factory=list)
    score: float = 0.0                # Node evaluation (0-1)
    is_solution: bool = False
    
    def full_path(self) -> list[str]:
        """Gets the path from the root down to this node."""
        if self.parent is None:
            return [self.content]
        return self.parent.full_path() + [self.content]
    
    def __repr__(self):
        return f"Node('{self.content[:40]}...', score={self.score:.2f})"


def generate_thoughts(
    problem: str,
    current_context: str,
    k: int = 3,
    temperature: float = 0.8
) -> list[str]:
    """
    Generates K candidate thoughts for the next step.
    
    Args:
        problem: The original problem
        current_context: The steps taken so far
        k: Number of thoughts to generate
        temperature: Higher temperature = more diversity
    """
    prompt = f"""Problem: {problem}

Previous steps taken:
{current_context if current_context else "None (first step)"}

Generate EXACTLY {k} different ideas or steps to move toward the solution.
Each idea has to be different from the others.
Format: one idea per line, starting with a number: "1.", "2.", "3."
Only the steps, no extra explanations."""
    
    response = client.chat.completions.create(
        model="gpt-4o-mini",
        messages=[{"role": "user", "content": prompt}],
        temperature=temperature,
        max_tokens=400
    )
    
    text = response.choices[0].message.content
    lines = [l.strip() for l in text.split('\n') if l.strip()]
    
    # Extract only the numbered lines
    thoughts = []
    for line in lines:
        if line and (line[0].isdigit() or line.startswith('-')):
            # Strip the numbering
            thought = line.lstrip('0123456789.-) ').strip()
            if thought:
                thoughts.append(thought)
    
    return thoughts[:k]


def evaluate_state(
    problem: str,
    path: list[str],
    check_solution: bool = True
) -> dict:
    """
    Evaluates how promising a path of thoughts is.
    
    Returns:
        dict with 'score' (0-1), 'is_solution' (bool), 'reason'
    """
    path_str = "\n".join([f"Step {i+1}: {step}" for i, step in enumerate(path)])
    
    prompt = f"""Problem: {problem}

Reasoning path:
{path_str}

Evaluate this path:
1. Is this solution/answer correct? (only if it looks complete)
2. If it isn't complete, how promising is it for reaching the solution?

Reply in JSON:
{{
    "is_solution": true/false,
    "score": 0.0-1.0,
    "reason": "short explanation (max 20 words)"
}}
If it is a solution, score must be 1.0."""
    
    response = client.chat.completions.create(
        model="gpt-4o-mini",
        messages=[{"role": "user", "content": prompt}],
        temperature=0,
        max_tokens=150,
        response_format={"type": "json_object"}
    )
    
    try:
        evaluation = json.loads(response.choices[0].message.content)
        return {
            "score": float(evaluation.get("score", 0.5)),
            "is_solution": bool(evaluation.get("is_solution", False)),
            "reason": evaluation.get("reason", "")
        }
    except (json.JSONDecodeError, KeyError):
        return {"score": 0.5, "is_solution": False, "reason": "Evaluation error"}

BFS Strategy (Breadth-First Search)

def tot_bfs(
    problem: str,
    max_depth: int = 3,
    breadth: int = 3,
    beam_size: int = 2
) -> dict:
    """
    Tree-of-Thought with Breadth-First Search + Beam Search.
    
    Keeps the beam_size best nodes at each level.
    This caps the combinatorial explosion.
    
    Args:
        problem: The problem to solve
        max_depth: Maximum depth of the tree
        breadth: Thoughts generated per node
        beam_size: Best nodes to keep per level
    
    Returns:
        dict with 'solution', 'path', 'nodes_explored'
    """
    # Initial level: explore straight from the problem
    current_level = [Node(content="Start")]
    nodes_explored = 0
    best_solution = None
    
    for depth in range(max_depth):
        next_level = []
        
        for parent_node in current_level:
            # Generate thoughts from this node
            context = "\n".join(parent_node.full_path()[1:])  # Exclude "Start"
            new_thoughts = generate_thoughts(
                problem=problem,
                current_context=context,
                k=breadth
            )
            
            # Evaluate each thought
            for thought in new_thoughts:
                nodes_explored += 1
                new_node = Node(
                    content=thought,
                    parent=parent_node
                )
                parent_node.children.append(new_node)
                
                # Evaluate the state
                path = new_node.full_path()[1:]  # Without "Start"
                evaluation = evaluate_state(problem, path)
                new_node.score = evaluation["score"]
                new_node.is_solution = evaluation["is_solution"]
                
                if new_node.is_solution:
                    best_solution = new_node
                    # Keep searching to find the BEST solution
                
                next_level.append(new_node)
        
        if best_solution:
            # We found a solution, we can stop
            break
        
        # Beam Search: keep only the beam_size best
        next_level.sort(key=lambda n: n.score, reverse=True)
        current_level = next_level[:beam_size]
        
        if not current_level:
            break
    
    # If we found no explicit solution, use the best node
    if best_solution is None:
        all_nodes = []
        def collect_nodes(node):
            all_nodes.append(node)
            for child in node.children:
                collect_nodes(child)
        for node in current_level:
            collect_nodes(node)
        
        if all_nodes:
            best_solution = max(all_nodes, key=lambda n: n.score)
    
    if best_solution:
        final_path = best_solution.full_path()[1:]  # Without "Start"
        return {
            "solution_found": best_solution.is_solution,
            "path": final_path,
            "score": best_solution.score,
            "nodes_explored": nodes_explored,
            "depth": len(final_path)
        }
    
    return {
        "solution_found": False,
        "path": [],
        "score": 0.0,
        "nodes_explored": nodes_explored
    }

DFS Strategy (Depth-First Search)

def tot_dfs(
    problem: str,
    max_depth: int = 4,
    breadth: int = 2,
    prune_threshold: float = 0.3
) -> dict:
    """
    Tree-of-Thought with DFS and pruning on low scores.
    
    More memory-efficient than BFS but it can get lost
    down long unpromising branches.
    """
    best_path = {"path": [], "score": 0.0, "is_solution": False}
    nodes_explored = [0]  # List to stay mutable inside the closure
    
    def dfs_recursive(current_node: Node, depth: int):
        if depth >= max_depth:
            return
        
        context = "\n".join(current_node.full_path()[1:])
        thoughts = generate_thoughts(
            problem=problem,
            current_context=context,
            k=breadth
        )
        
        for thought in thoughts:
            nodes_explored[0] += 1
            new_node = Node(content=thought, parent=current_node)
            
            path = new_node.full_path()[1:]
            evaluation = evaluate_state(problem, path)
            new_node.score = evaluation["score"]
            new_node.is_solution = evaluation["is_solution"]
            
            # Pruning: don't explore unpromising branches
            if new_node.score < prune_threshold:
                continue
            
            if new_node.is_solution:
                if new_node.score > best_path["score"]:
                    best_path.update({
                        "path": path,
                        "score": new_node.score,
                        "is_solution": True
                    })
                return  # Stop at the first solution found
            
            # Keep exploring if it looks promising
            if new_node.score > best_path["score"] - 0.1:
                best_path.update({"path": path, "score": new_node.score})
            
            dfs_recursive(new_node, depth + 1)
    
    root = Node(content="Start")
    dfs_recursive(root, 0)
    
    return {
        **best_path,
        "nodes_explored": nodes_explored[0]
    }

Simplified Implementation (Practical)

For most use cases, a simplified version is enough — and far more token-efficient:

def tot_simplified(
    problem: str,
    breadth: int = 3,
    depth: int = 2,
    verbose: bool = True
) -> str:
    """
    Simplified ToT for practical use.
    
    1. Generate breadth initial approaches
    2. Evaluate which one is most promising
    3. Continue with CoT from the best approach
    """
    # Step 1: Generate initial approaches
    approaches_prompt = f"""Problem: {problem}

Generate {breadth} DIFFERENT approaches to solve this problem.
Each approach has to be the key FIRST STEP of a distinct strategy.
Format: one line per approach, starting with a number."""
    
    response = client.chat.completions.create(
        model="gpt-4o-mini",
        messages=[{"role": "user", "content": approaches_prompt}],
        temperature=0.8,
        max_tokens=300
    )
    
    lines = [l.strip() for l in response.choices[0].message.content.split('\n') if l.strip()]
    approaches = [l.lstrip('0123456789.-) ').strip() for l in lines if l[:1].isdigit() or l[:1] == '-'][:breadth]
    
    if not approaches:
        approaches = lines[:breadth]  # Fallback
    
    if verbose:
        print(f"Approaches generated:")
        for i, a in enumerate(approaches, 1):
            print(f"  {i}. {a}")
    
    # Step 2: Evaluate each approach
    scores = []
    for approach in approaches:
        eval_prompt = f"""Problem: {problem}
Proposed first step: {approach}

How promising is this approach for reaching the correct solution?
Reply ONLY with a number between 0.0 and 1.0 (e.g. 0.8)"""
        
        eval_resp = client.chat.completions.create(
            model="gpt-4o-mini",
            messages=[{"role": "user", "content": eval_prompt}],
            temperature=0,
            max_tokens=10
        )
        
        try:
            score = float(eval_resp.choices[0].message.content.strip()[:5])
            score = max(0.0, min(1.0, score))
        except ValueError:
            score = 0.5
        
        scores.append(score)
        if verbose:
            print(f"  Score for '{approach[:40]}...': {score:.2f}")
    
    # Step 3: Continue with the best approach
    if not scores:
        best_approach = approaches[0] if approaches else "direct reasoning"
    else:
        best_idx = scores.index(max(scores))
        best_approach = approaches[best_idx]
    
    if verbose:
        print(f"\nBest approach selected: {best_approach}")
    
    # Step 4: Solve using CoT from the best approach
    final_prompt = f"""Problem: {problem}

Starting from this approach: {best_approach}

Keep reasoning step by step until you reach the final solution.
Show all your reasoning and close with "Final answer: [answer]"."""
    
    final = client.chat.completions.create(
        model="gpt-4o-mini",
        messages=[{"role": "user", "content": final_prompt}],
        temperature=0,
        max_tokens=500
    )
    
    return final.choices[0].message.content


# Usage example:
if __name__ == "__main__":
    print("=== Tree-of-Thought: Complex Problem ===\n")
    
    problem = """A company has three possible projects:
    - Project A: $100K investment, 30% expected return
    - Project B: $150K investment, 25% expected return
    - Project C: $80K investment, 35% expected return
    
    They have a $200K budget. Which combination maximizes the total return?"""
    
    solution = tot_simplified(problem, breadth=3, depth=2, verbose=True)
    print(f"\nSolution:\n{solution}")

Comparison: CoT vs Self-Consistency vs ToT

Ideal Use Cases

Project Planning

planning_problem = """
I need to launch a software product in 3 months with a team of 4 people.
The tasks are: backend development, frontend, testing, deployment, marketing.
What's the best planning strategy?
"""
solution = tot_simplified(planning_problem, breadth=4, verbose=True)

Diagnosing Technical Problems

debug_problem = """
A REST API returns a 200 code but the data is inconsistent.
Sometimes it shows cached data, sometimes fresh data. The problem is intermittent.
How would you diagnose and fix it?
"""
solution = tot_simplified(debug_problem, breadth=3, verbose=True)

Business Strategy

business_problem = """
A fintech startup with $500K in capital wants to grow to 10,000 users 
in 6 months. They currently have 500 users and an 8% monthly churn rate.
What growth strategy should they follow?
"""
solution = tot_simplified(business_problem, breadth=3, verbose=True)

Tree-of-Thought with Anthropic

import anthropic

client_anthropic = anthropic.Anthropic()

def tot_claude(problem: str, breadth: int = 3) -> str:
    """
    Simplified Tree-of-Thought using Claude.
    Claude tends to be more explicit in its reasoning.
    """
    # Generate approaches
    message = client_anthropic.messages.create(
        model="claude-3-5-haiku-20241022",
        max_tokens=400,
        messages=[{
            "role": "user",
            "content": f"Generate {breadth} distinct approaches for: {problem}\nOne approach per line, numbered."
        }]
    )
    raw_approaches = message.content[0].text
    approaches = [l.lstrip('0123456789.-) ').strip() 
                  for l in raw_approaches.split('\n') 
                  if l.strip() and l.strip()[0].isdigit()][:breadth]
    
    # Evaluate and select the best one
    scored_approaches = []
    for approach in approaches:
        eval_msg = client_anthropic.messages.create(
            model="claude-3-5-haiku-20241022",
            max_tokens=20,
            messages=[{
                "role": "user",
                "content": f"Problem: {problem}\nApproach: {approach}\nHow promising is it (0.0 to 1.0)? The number only."
            }]
        )
        try:
            score = float(eval_msg.content[0].text.strip()[:4])
        except ValueError:
            score = 0.5
        scored_approaches.append((score, approach))
    
    best_score, best_approach = max(scored_approaches, key=lambda x: x[0])
    
    # Solve from the best approach
    solution_msg = client_anthropic.messages.create(
        model="claude-3-5-haiku-20241022",
        max_tokens=600,
        messages=[{
            "role": "user",
            "content": f"Problem: {problem}\n\nStarting from: {best_approach}\n\nKeep going step by step until the final solution."
        }]
    )
    
    return solution_msg.content[0].text

Troubleshooting

Problem 1: The evaluator is inconsistent

Symptom: The same thought gets very different scores on each call.

Causes:

• Temperature > 0 in the evaluator
• An ambiguous evaluation prompt

Solution:

def evaluate_with_consistency(problem: str, path: list[str], n_eval: int = 3) -> float:
    """Average several evaluations for more consistency."""
    scores = []
    for _ in range(n_eval):
        evaluation = evaluate_state(problem, path)
        scores.append(evaluation["score"])
    return sum(scores) / len(scores)

# Inside the ToT functions, replace:
# evaluation = evaluate_state(problem, path)  # Single score
# with:
# score = evaluate_with_consistency(problem, path, n_eval=3)  # Average of 3

Problem 2: Too many API calls (combinatorial explosion)

Symptom: With breadth=4 and depth=3, you need up to 4³ = 64 evaluations + 4² + 4 = 84 generations = 148+ calls.

Solution: Use aggressive pruning and a limited beam search:

def tot_efficient(problem: str, call_budget: int = 20) -> str:
    """ToT with a fixed API call budget."""
    # With a budget of 20 calls:
    # 3 initial approaches = 3 generation calls + 3 evaluations = 6
    # Top 2 → 2 continued approaches = 2 + 2 = 4
    # 1 final solution = 1
    # Total: ~11 calls
    
    breadth = min(3, call_budget // 4)
    return tot_simplified(problem, breadth=breadth, depth=1, verbose=False)

Problem 3: The generated thoughts are too similar to each other

Symptom: The 3 approaches generated are basically the same approach with different words.

Solution:

def generate_diverse_thoughts(problem: str, k: int = 3) -> list[str]:
    """Force diversity by using different roles."""
    roles = [
        "a software engineer who thinks in terms of algorithms and efficiency",
        "a mathematician who looks for patterns and formal proofs",
        "an entrepreneur who looks for the most practical, fastest solution"
    ]
    
    thoughts = []
    for i, role in enumerate(roles[:k]):
        prompt = f"You are {role}. What would YOUR first step be for: {problem}? Only the first step, in one sentence."
        resp = client.chat.completions.create(
            model="gpt-4o-mini",
            messages=[{"role": "user", "content": prompt}],
            temperature=0.7,
            max_tokens=100
        )
        thoughts.append(resp.choices[0].message.content.strip())
    
    return thoughts

Exercises

Exercise 1: ToT for a Sudoku problem

Implement a simplified version of ToT to solve a 4×4 Sudoku. The tree has to:

1. Generate 3 possible values for the most constrained empty cell
2. Evaluate which one breaks the fewest rules
3. Continue from the most promising one

def tot_sudoku_4x4(grid: list[list[int]]) -> list[list[int]]:
    """
    Solves a 4x4 Sudoku using ToT.
    0 represents an empty cell.
    """
    grid_str = "\n".join([" ".join(map(str, row)) for row in grid])
    
    # Find the most constrained cell
    analysis_prompt = f"""4x4 Sudoku (0=empty):
{grid_str}

Identify which empty cell has the fewest valid possible values.
Then suggest 3 possible values for that cell (there may be fewer if it's very constrained).
JSON format: {{"cell": [row, column], "possible_values": [1, 2, 3]}}"""
    
    response = client.chat.completions.create(
        model="gpt-4o-mini",
        messages=[{"role": "user", "content": analysis_prompt}],
        temperature=0,
        response_format={"type": "json_object"}
    )
    
    try:
        analysis = json.loads(response.choices[0].message.content)
        cell = analysis["cell"]
        values = analysis["possible_values"]
    except Exception:
        return grid  # Fallback
    
    # Evaluate each possible value
    best_score = -1
    best_value = values[0] if values else 0
    
    for value in values:
        grid_copy = [row[:] for row in grid]
        grid_copy[cell[0]][cell[1]] = value
        new_grid_str = "\n".join([" ".join(map(str, row)) for row in grid_copy])
        
        eval_prompt = f"""4x4 Sudoku with value {value} at position {cell}:
{new_grid_str}
Is this value valid (doesn't break any rule)? How good is this choice (0.0-1.0)?
Reply with the number only."""
        
        eval_resp = client.chat.completions.create(
            model="gpt-4o-mini",
            messages=[{"role": "user", "content": eval_prompt}],
            temperature=0,
            max_tokens=10
        )
        
        try:
            score = float(eval_resp.choices[0].message.content.strip()[:4])
        except ValueError:
            score = 0.5
        
        if score > best_score:
            best_score = score
            best_value = value
    
    # Apply the best value and continue
    result = [row[:] for row in grid]
    result[cell[0]][cell[1]] = best_value
    
    # Check whether it's complete
    if all(c != 0 for row in result for c in row):
        return result
    
    # If not, continue recursively (simplified: only 1 more level)
    return result

# Test with a simple 4x4 Sudoku:
sudoku = [
    [1, 0, 3, 0],
    [0, 3, 0, 1],
    [3, 0, 1, 0],
    [0, 1, 0, 3]
]
print("Original Sudoku:")
for row in sudoku:
    print(row)
result = tot_sudoku_4x4(sudoku)
print("\nSudoku solved (one step):")
for row in result:
    print(row)

Exercise 2: Compare BFS vs DFS

For the same problem, run tot_bfs and tot_dfs and compare:

• Number of nodes explored
• Execution time
• Quality of the solution

When is BFS better? When is DFS?

import time

problem = "Design a microservices architecture for an e-commerce site with 100K daily users."

print("=== BFS ===")
start = time.time()
bfs_result = tot_bfs(problem, max_depth=2, breadth=3, beam_size=2)
bfs_time = time.time() - start
print(f"Nodes explored: {bfs_result['nodes_explored']}")
print(f"Time: {bfs_time:.2f}s")
print(f"Score: {bfs_result['score']:.2f}")

print("\n=== DFS ===")
start = time.time()
dfs_result = tot_dfs(problem, max_depth=3, breadth=2, prune_threshold=0.4)
dfs_time = time.time() - start
print(f"Nodes explored: {dfs_result['nodes_explored']}")
print(f"Time: {dfs_time:.2f}s")
print(f"Score: {dfs_result['score']:.2f}")

# Expected conclusions:
# BFS with beam: Explores more nodes but finds a better global solution
# DFS with pruning: Faster but can get stuck down long paths
# BFS is better for: problems where the depth is short and the breadth matters
# DFS is better for: deep problems where the first correct branch is usually the good one

Exercise 3: Designing a specialized evaluator

The generic evaluator works for many cases, but a specialized evaluator for your domain is far more accurate. Build an evaluator for "Python code":

• Evaluate whether the code is syntactically correct
• Whether it solves the stated problem
• Whether it's efficient (big O)

def evaluate_python_code(problem: str, code: str) -> dict:
    """Specialized evaluator for Python code in ToT."""
    
    # Syntax test
    try:
        compile(code, "<string>", "exec")
        syntax_ok = True
    except SyntaxError:
        syntax_ok = False
    
    if not syntax_ok:
        return {"score": 0.1, "is_solution": False, "reason": "Syntax error"}
    
    # Semantic evaluation
    prompt = f"""Python code:
```python
{code}

response = client.chat.completions.create(
    model="gpt-4o-mini",
    messages=[{"role": "user", "content": prompt}],
    temperature=0,
    response_format={"type": "json_object"}
)

try:
    metrics = json.loads(response.choices[0].message.content)
    average_score = (
        metrics.get("correct", 0) * 0.5 +
        metrics.get("efficient", 0) * 0.3 +
        metrics.get("robust", 0) * 0.2
    )
    return {
        "score": average_score,
        "is_solution": average_score > 0.7,
        "reason": f"Correct:{metrics.get('correct', 0):.1f} Efficient:{metrics.get('efficient', 0):.1f}"
    }
except Exception:
    return {"score": 0.5, "is_solution": False, "reason": "Evaluation error"}

</details>

---

## Summary

- **Tree-of-Thought:** Organizes the reasoning as a tree where each node is a thought/partial state
- **Components:** Thought generator + Evaluator + Search algorithm (BFS/DFS)
- **When to use it:** Problems with multiple strategies, when CoT fails systematically, when you have budget for many calls
- **BFS:** Better when the solution could be in any branch; guarantees finding the optimal one at the given level
- **DFS with pruning:** More token-efficient; can get stuck down long paths
- **Simplified version:** For 80% of practical cases: generate K approaches → evaluate → continue with the best one

---

## Additional resources

1. [Tree of Thoughts: Deliberate Problem Solving with Large Language Models (Yao et al., 2023)](https://arxiv.org/abs/2305.10601) - Original paper
2. [Large Language Model Guided Tree-of-Thought](https://arxiv.org/abs/2305.08291) - Guided variant
3. [GitHub: princeton-nlp/tree-of-thought-llm](https://github.com/princeton-nlp/tree-of-thought-llm) - Reference implementation
4. [OpenAI response_format JSON mode](https://platform.openai.com/docs/guides/text-generation/json-mode)
5. [Prompt Engineering Guide - Tree of Thoughts](https://www.promptingguide.ai/techniques/tot)
6. [Graph of Thoughts - a ToT extension](https://arxiv.org/abs/2308.09687)