Tree of Thoughts (ToT) Prompting
What Is Tree of Thoughts? Tree of Thoughts (ToT) is a reasoning approach in which the model explores several possible next steps at each stage of solving a problem, evaluates how promising each one is, and continues only with the most promising ones, abandoning dead ends.
In simple terms: instead of following one line of reasoning to the end, the model behaves like a person solving a puzzle who tries a few options, notices which ones lead nowhere, and goes back to try others.
How It Differs From Earlier Techniques Chain-of-Thought: step → step → step → answer (one path, no going back)
Self-Consistency: path 1: step → step → answer ┐ path 2: step → step → answer ├→ vote path 3: step → step → answer ┘ (several complete paths, compared only at the end)
Tree of Thoughts: ┌→ step ✗ (abandoned) step ────┼→ step → step → answer ✓ └→ step → step ✗ (abandoned) (branches at every stage, evaluated along the way) Technique Explores Alternatives? When Are Paths Compared? Can Abandon a Bad Path Early? Chain-of-Thought No Never No Self-Consistency Yes Only at the final answer No Tree of Thoughts Yes At every step Yes Where It Comes From Tree of Thoughts was introduced in the 2023 paper "Tree of Thoughts: Deliberate Problem Solving with Large Language Models" by Yao et al. The authors tested it on problems that require planning and search, where an early wrong choice makes success impossible.
The best-known result comes from the Game of 24: given four numbers, combine them with +, −, ×, and ÷ to reach exactly 24. In the paper's experiments with GPT-4, standard chain-of-thought prompting solved about 4% of the puzzles, while Tree of Thoughts solved about 74%.
The large gap shows what ToT addresses: problems where choosing well at each step matters more than reasoning fluently.
Why Linear Reasoning Fails on Search Problems The Game of 24 Example Numbers: 4, 9, 10, 13
A chain-of-thought attempt might start:
4 + 9 = 13. Now I have 10, 13, 13. 13 + 13 = 26. Now I have 10, 26. 26 − 10 = 16. That is not 24. The first step, 4 + 9, made the puzzle impossible: there is no way to reach 24 from 10, 13, 13. But chain of thought has no mechanism to recognize this and go back. It continues to the end and fails.
What a Tree Search Does At the first step, ToT considers several options and evaluates each one:
First Step Remaining Numbers Can 24 Still Be Reached? 4 + 9 = 13 10, 13, 13 No 9 × 13 = 117 4, 10, 117 No 13 − 9 = 4 4, 4, 10 Yes: (10 − 4) × 4 = 24 10 − 4 = 6 6, 9, 13 Yes: 6 × (13 − 9) = 24 The dead branches are abandoned immediately, and the search continues from a promising state. Following 10 − 4 = 6, then 13 − 9 = 4, then 6 × 4 = 24 solves the puzzle: (10 − 4) × (13 − 9) = 24.
The Four Components of Tree of Thoughts The ToT framework is built from four design decisions.
- Thought Decomposition What it is: Deciding what one "thought" (one step in the tree) is.
A thought should be big enough to make progress, but small enough that the model can generate several good options and evaluate them.
Problem One Thought Game of 24 One arithmetic operation on two of the remaining numbers Writing a structured article One outline or one section plan Planning a project One phase or one decision Debugging One hypothesis about the cause
- Thought Generation What it is: Producing candidate next steps from the current state.
Two approaches were described in the original paper:
Sample: generate several thoughts independently, which works well when the space of possible thoughts is large, such as different paragraph plans. Propose: ask for several different thoughts in one response, which avoids duplicates when the space is small, such as arithmetic operations.
- State Evaluation What it is: Judging how promising each state is, so the search knows which branches to keep.
Value: evaluate each state independently, for example as "sure", "likely", or "impossible" to reach the goal. Vote: compare several states together and choose the most promising one. The evaluator can be the model itself or, when possible, code that checks the state exactly.
- Search Algorithm What it is: The strategy for exploring the tree.
Breadth-first search (BFS): keep the best few states at each level and expand them all. Depth-first search (DFS): follow the most promising branch deeply, and backtrack when it fails. Search strategies, evaluation methods, and backtracking are covered in depth in Lesson 54.
Code as an Exact State Evaluator For problems with exact rules, code can evaluate states perfectly. The following function decides whether a set of numbers can still reach 24. It is the "evaluator" for the Game of 24.
from fractions import Fraction from itertools import combinations
def can_reach_24(numbers: list[int | Fraction]) -> bool: """Return True if the numbers can be combined with + - * / to make exactly 24.""" nums = [Fraction(n) for n in numbers] if len(nums) == 1: return nums[0] == 24 for i, j in combinations(range(len(nums)), 2): a, b = nums[i], nums[j] rest = [nums[k] for k in range(len(nums)) if k not in (i, j)] results = {a + b, a - b, b - a, a * b} if b != 0: results.add(a / b) if a != 0: results.add(b / a) if any(can_reach_24(rest + [r]) for r in results): return True return False
for state in ([10, 13, 13], [4, 10, 117], [4, 4, 10], [6, 9, 13]): print(state, can_reach_24(state)) Output:
[10, 13, 13] False [4, 10, 117] False [4, 4, 10] True [6, 9, 13] True Code Explanation Fraction Exact rational numbers from Python's standard library. Using fractions instead of floating-point numbers avoids rounding errors, such as 8 / 3 * 3 not being exactly 8.
combinations(range(len(nums)), 2) Generates every pair of positions in the list. Each pair is combined with every operation.
results All possible results of combining the pair: both subtraction orders and both division orders, skipping division by zero. A set removes duplicate results, such as when a + b equals a * b.
Recursion Each combination replaces two numbers with one result. The function calls itself on the shorter list until one number remains, which is checked against 24.
The output matches the table above: the two dead branches are correctly identified as impossible, and the two promising branches as reachable.
Why This Matters for ToT In this puzzle, a code-based evaluator is perfect, so the model only needs to propose steps. In most real problems, no exact evaluator exists, and the model must evaluate states itself, which is less reliable. When a code evaluator is possible, use it.
Combining Model Proposals With Code Evaluation The following example asks the model to propose possible first steps and uses can_reach_24() to evaluate them. This is one level of a Tree of Thoughts. The code continues from the previous block, so Fraction and can_reach_24() are already defined.
Requirements: pip install openai and an OPENAI_API_KEY environment variable.
import json
from openai import OpenAI
client = OpenAI() MODEL = "gpt-5.4" # Replace with a model available in your account
PROPOSE_INSTRUCTIONS = """You are given numbers for the Game of 24. Propose up to 6 different possible first steps. Each step combines exactly two of the numbers with one of + - * /. Return only a JSON array of objects: {"a": number, "op": "+", "b": number}"""
OPS = { "+": lambda a, b: a + b, "-": lambda a, b: a - b, "": lambda a, b: a b, "/": lambda a, b: a / b if b != 0 else None, }
def apply_step(numbers: list[int], step: dict) -> list[Fraction] | None: """Apply a proposed step; return the new list of numbers, or None if invalid.""" remaining = [Fraction(n) for n in numbers] a, b = Fraction(step["a"]), Fraction(step["b"]) if step["op"] not in OPS or a not in remaining: return None remaining.remove(a) if b not in remaining: return None remaining.remove(b) result = OPS[step["op"]](a, b) return None if result is None else remaining + [result]
def evaluate_first_steps(numbers: list[int]) -> None: response = client.responses.create( model=MODEL, instructions=PROPOSE_INSTRUCTIONS, input=f"Numbers: {numbers}", ) for step in json.loads(response.output_text): new_state = apply_step(numbers, step) if new_state is None: print(f"{step}: invalid step") continue status = "promising" if can_reach_24(new_state) else "dead end" print(f"{step['a']} {step['op']} {step['b']} → {[str(n) for n in new_state]}: {status}")
evaluate_first_steps([4, 9, 10, 13]) Possible output:
4 + 9 → ['10', '13', '13']: dead end 13 - 9 → ['4', '10', '4']: promising 10 - 4 → ['9', '13', '6']: promising 9 * 13 → ['4', '10', '117']: dead end 13 - 10 → ['4', '9', '3']: promising 10 + 13 → ['4', '9', '23']: dead end The model's proposals vary between runs, but the evaluation of each proposal is exact. Notice that 13 - 10 is also promising, because (9 − 3) × 4 = 24. The code evaluator finds valid branches that are easy for a person, or a model, to overlook.
Code Explanation PROPOSE_INSTRUCTIONS Implements the propose approach to thought generation: one request returns several distinct candidate steps as JSON.
apply_step() Validates and applies a proposed step in code. It checks that the operation is known and that both numbers are actually available, which catches proposals that use numbers that do not exist. Using remove() one number at a time correctly handles duplicates such as two 4s.
Evaluation Each valid new state is passed to can_reach_24(). Only promising states would be expanded at the next level of the tree.
Why the model does not do the arithmetic here The model proposes; code computes and evaluates. This avoids the arithmetic errors described in Lesson 44 and makes each branch's status certain.
Expanding the promising states level by level until a solution is found is a full breadth-first ToT search, which Lesson 54 implements.
Note: As in earlier lessons, if the model wraps its JSON in a code fence, json.loads will fail; use the extraction helper from Lesson 8 or structured outputs (Lesson 99) for robust parsing.
Single-Prompt Tree of Thoughts Full ToT requires many model calls and orchestration code. A lighter approximation asks the model to simulate branching and evaluation within a single response. A widely shared version of this idea, often attributed to Dave Hulbert (2023), frames the task as several experts reasoning together:
Imagine three different experts are answering this question. Each expert writes down one step of their thinking and shares it with the group. Then all experts move on to the next step. If any expert realizes their reasoning is wrong at any point, they leave.
The question is: [problem] A more direct version:
Solve the problem below.
- Propose three different approaches.
- For each approach, take the first step and evaluate whether it is promising.
- Abandon approaches that cannot work and explain why.
- Continue the most promising approach to the final answer. Strengths and Limitations Strength Limitation One request, simple to use The model evaluates its own branches, without exact checks Encourages considering alternatives Branching is limited to what fits in one response Useful for open-ended problems Not a real search: it cannot reliably backtrack across many levels Single-prompt ToT is a practical way to encourage exploration. For problems that truly require search, the multi-call approach with code-based evaluation is far more reliable.
When to Use Tree of Thoughts Good Fit Problems where early choices can make success impossible: puzzles, scheduling with constraints, planning with dependencies. Problems with a checkable goal: you can tell whether a state can still succeed. Problems with several plausible approaches: design decisions, debugging hypotheses, structuring a complex document. Poor Fit Straightforward multi-step problems where chain of thought already works (Lesson 43). Tasks with a single obvious path, such as translation or extraction. Latency-sensitive features: ToT requires many model calls. Problems where states cannot be evaluated reliably: without a good evaluator, the search has no basis for choosing branches. Cost A full ToT search can require many requests per problem: several proposals at each level, plus evaluations for each candidate. It is best reserved for high-value problems where simpler techniques fail.
Common Mistakes Mistake 1: Using ToT for Simple Problems What it is: Applying tree search to tasks that CoT already solves.
Why it happens: ToT is seen as a more powerful version of CoT.
What it causes: Many times the cost and latency with no benefit.
How to fix it: Use ToT only when early choices matter and linear reasoning fails.
Mistake 2: Letting the Model Do All Evaluation When Code Could What it is: Asking the model to judge whether a state is valid or solvable when code can check it exactly.
Why it happens: Building the whole system in prompts seems simpler.
What it causes: Unreliable pruning: good branches are abandoned and dead ones are kept.
How to fix it: Use code for validation and evaluation wherever the rules are exact.
Mistake 3: Poorly Sized Thoughts What it is: Thoughts that are too small (no progress per step) or too large (impossible to evaluate).
Why it happens: Thought decomposition is not designed deliberately.
What it causes: Huge trees, or evaluations that cannot distinguish good from bad states.
How to fix it: Define a thought as a step that makes clear progress and leaves an evaluable state.
Mistake 4: Trusting Single-Prompt ToT as a Real Search What it is: Assuming the "three experts" prompt explores and verifies alternatives reliably.
Why it happens: The output looks like a structured search.
What it causes: Overconfidence in answers that were not actually checked.
How to fix it: Use single-prompt ToT for exploration and ideas; use multi-call ToT with real evaluation for problems that require correctness.
Best Practices Use ToT for search problems. Where early choices determine success and alternatives must be compared.
Design the four components deliberately. Thought size, generation method, evaluation method, and search strategy.
Use code to validate and evaluate states when possible. Let the model propose; let code check.
Abandon dead branches early. Pruning is what makes the search efficient.
Start with single-prompt ToT for open-ended exploration. Move to multi-call ToT when correctness requires it.
Budget for cost. Limit the number of candidates per step and the depth of the search.
Try It Yourself Exercise 1: Trace the Tree by Hand For the numbers 3, 3, 8, 8, list at least six possible first steps and use can_reach_24() to mark each as promising or a dead end. Then find a full solution. (Hint: this puzzle requires division.)
Exercise 2: Compare CoT and Proposals Ask a model to solve five Game of 24 puzzles with chain-of-thought only. Then run evaluate_first_steps() on the same puzzles. Count how often the CoT attempt chose a dead-end first step, and how many promising steps the proposal approach found.
Exercise 3: Single-Prompt ToT for a Design Decision Use the direct single-prompt ToT template to decide how to store uploaded course videos for a small learning platform (for example, local server storage, cloud object storage, or a video hosting service). Compare the result with a standard chain-of-thought answer. Note whether exploring alternatives revealed trade-offs that the linear answer missed.