Tree of Thoughts: Search, Evaluation, and Backtracking
Building on the Basics Lesson 47 introduced the four components of Tree of Thoughts (ToT): thought decomposition, thought generation, state evaluation, and a search algorithm. It implemented one level of the tree: proposing first steps and evaluating them. Lesson 48 applied the idea to open-ended decisions.
This lesson completes the picture with the parts that turn individual steps into a full search:
How breadth-first search (BFS) keeps the best few states at each level. How depth-first search (DFS) follows promising branches and backtracks when they fail. How state evaluation controls pruning, and what happens when it is weak. How to keep searches within a budget of model calls. All search code in this lesson runs without an API, using a code-based proposer and evaluator for the Game of 24. Model-based components are shown afterward and plug into the same functions.
Key Terms Term Meaning State The current situation in the problem, such as the numbers still available in the Game of 24 Thought / step An action that moves from one state to another, such as 10 − 4 = 6 Proposer Generates candidate next steps from a state Evaluator Scores how promising a state is Frontier The set of states waiting to be explored Pruning Discarding states that are unlikely to lead to a solution Backtracking Returning to an earlier state after a branch fails, and trying a different step Beam width In BFS, the number of best states kept at each level Shared Components The State Evaluator The exact evaluator from Lesson 47 decides whether a set of numbers can still reach 24. Here it is wrapped as a value function that returns a score:
from fractions import Fraction from itertools import combinations
def can_reach_24(numbers: list[Fraction]) -> bool: 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
def exact_value(state: list[Fraction]) -> float: """1.0 if the state can still reach 24, otherwise 0.0.""" return 1.0 if can_reach_24(state) else 0.0 The Proposer For testing the search logic, a code-based proposer lists every possible next step. Later, a model-based proposer replaces it.
def fmt(x: Fraction) -> str: """Show whole numbers plainly and fractions in parentheses.""" return str(x) if x.denominator == 1 else f"({x})"
def all_steps(state: list[Fraction]) -> list[tuple[str, list[Fraction]]]: """Return every (step description, new state) reachable in one operation.""" steps = [] for i, j in combinations(range(len(state)), 2): a, b = state[i], state[j] rest = [state[k] for k in range(len(state)) if k not in (i, j)] options = [(a, "+", b, a + b), (a, "", b, a b), (a, "-", b, a - b), (b, "-", a, b - a)] if b != 0: options.append((a, "/", b, a / b)) if a != 0: options.append((b, "/", a, b / a)) for x, op, y, result in options: steps.append((f"{fmt(x)} {op} {fmt(y)} = {fmt(result)}", rest + [result])) return steps Code Explanation all_steps() combines every pair of numbers with every operation, including both orders for subtraction and division, and skips division by zero. Each step returns a readable description and the new state: the unused numbers plus the result. fmt() writes fractions such as 8/3 as (8/3), so expressions like 8 / (1/3) remain readable. Breadth-First Search With a Beam How It Works BFS explores the tree level by level:
Start with the initial state as the frontier. Expand every state in the frontier with the proposer. Evaluate all resulting states. Keep only the best beam_width states (and discard states with a score of 0). Repeat until a solution is found or the frontier is empty. Level 0: [4, 9, 10, 13] / | \ Level 1: (many candidates, evaluated) → keep best 3 / | \ Level 2: (expand each kept state, evaluate) → keep best 3 ... Implementation def bfs(numbers, propose, evaluate, beam_width=3): frontier = [([Fraction(n) for n in numbers], [])] evaluations = 0 while frontier: candidates = [] for state, path in frontier: if len(state) == 1: if state[0] == 24: return path, evaluations continue for step_text, new_state in propose(state): evaluations += 1 candidates.append((evaluate(new_state), new_state, path + [step_text])) candidates.sort(key=lambda c: c[0], reverse=True) frontier = [(s, p) for score, s, p in candidates[:beam_width] if score > 0] return None, evaluations
print(bfs([4, 9, 10, 13], all_steps, exact_value)) print(bfs([1, 1, 1, 1], all_steps, exact_value)) Output:
(['4 - 10 = -6', '9 - 13 = -4', '-6 * -4 = 24'], 108) (None, 36) Code Explanation frontier A list of (state, path) pairs. The path records the steps taken so far, so the solution can be reported.
Expansion and evaluation Every state in the frontier is expanded, and every new state is evaluated. evaluations counts how many evaluations were performed, which corresponds to model calls when a model is the evaluator.
Beam selection Candidates are sorted by score, and only the top beam_width with a positive score are kept. This is pruning: everything else is discarded.
Results
For 4, 9, 10, 13, BFS finds a solution: (4 − 10) × (9 − 13) = (−6) × (−4) = 24. It is a different solution from the one in Lesson 47, because the search simply returns the first solution it reaches. For 1, 1, 1, 1, no solution exists. The evaluator scores every first step as 0, so the frontier becomes empty and the search stops after 36 evaluations, without exploring deeper. Beam Width Trade-Off Beam Width Effect Small (1) Cheap, but if the evaluator makes a mistake, the correct branch may be discarded with no alternative Medium (3–5) A common balance between cost and robustness Large More robust to evaluation errors, but cost grows quickly The original ToT paper used a breadth-first search with a beam of 5 for the Game of 24.
Depth-First Search With Backtracking How It Works DFS follows one branch as deep as possible:
Take the first promising next step. Continue from the new state. If a branch reaches a dead end, backtrack: return to the previous state and try its next step. Stop when a solution is found or all promising branches are exhausted. [3, 3, 8, 8] └─ step A → state → step → dead end ✗ ← backtrack └─ step → state → ... ✓ solution Implementation def dfs(state, path, propose, evaluate, threshold=0.5, stats=None): stats = stats if stats is not None else {"visited": 0, "backtracks": 0} if len(state) == 1: return (path if state[0] == 24 else None), stats for step_text, new_state in propose(state): stats["visited"] += 1 if evaluate(new_state) < threshold: continue # prune this branch result, _ = dfs(new_state, path + [step_text], propose, evaluate, threshold, stats) if result: return result, stats stats["backtracks"] += 1 # branch failed: try the next step return None, stats
start = [Fraction(n) for n in [3, 3, 8, 8]] print(dfs(start, [], all_steps, exact_value)) Output:
(['8 / 3 = (8/3)', '3 - (8/3) = (1/3)', '8 / (1/3) = 24'], {'visited': 26, 'backtracks': 0}) Code Explanation Recursion Each call explores one state. For each proposed step, it evaluates the new state, skips it if the score is below threshold, and otherwise calls itself on the new state.
Backtracking If the recursive call returns None, the branch failed. The loop continues with the next step from the same state. This "return and try the next option" behavior is backtracking. The backtracks counter records how often it happened.
stats A shared dictionary that counts visited states and backtracks across all recursive calls.
The result The puzzle 3, 3, 8, 8 requires fractions: 8 ÷ (3 − 8 ÷ 3) = 8 ÷ (1/3) = 24. Using exact Fraction values makes this solution possible.
Why the Evaluator Matters So Much The evaluator decides which branches are explored. Compare the same DFS with the exact evaluator and with no evaluation at all:
def no_evaluation(state: list[Fraction]) -> float: return 1.0 # every state looks promising
print(dfs(start, [], all_steps, exact_value)[1]) print(dfs(start, [], all_steps, no_evaluation)[1]) Output:
{'visited': 26, 'backtracks': 0} {'visited': 1400, 'backtracks': 1397} Interpretation With the exact evaluator, the search visits 26 states and never backtracks, because every dead branch is pruned immediately. With no evaluation, it visits 1,400 states and backtracks 1,397 times before finding the same solution. If each visited state required a model call, the difference would be 26 calls versus 1,400. The quality of the evaluator determines the cost of the search. A weak evaluator either keeps too many branches (high cost) or prunes correct ones (missed solutions).
Model-Based Components In most real problems, no exact evaluator exists, and the model must propose and evaluate. The search functions above work unchanged, as long as the replacements have the same signatures.
Model-Based Evaluator The original ToT paper asked the model to classify states as sure, likely, or impossible to reach the goal, and converted these labels into values.
from openai import OpenAI
client = OpenAI() MODEL = "gpt-5.4" # Replace with a model available in your account
VALUE_INSTRUCTIONS = """Game of 24: decide whether the remaining numbers can be combined with + - * / (each number used exactly once) to make exactly 24. Reply with exactly one word: sure, likely, or impossible."""
LABEL_VALUES = {"sure": 1.0, "likely": 0.5, "impossible": 0.0}
def model_value(state: list[Fraction]) -> float: numbers = ", ".join(fmt(n) for n in state) response = client.responses.create( model=MODEL, instructions=VALUE_INSTRUCTIONS, input=f"Numbers: {numbers}" ) label = response.output_text.strip().lower() return LABEL_VALUES.get(label, 0.5) # unclear replies are treated as "likely" Code Explanation The model sees only the remaining numbers and returns one of three labels. LABEL_VALUES converts labels to scores that the search can sort and compare with threshold. Unclear replies are treated as 0.5, so a confusing answer neither prunes a branch nor marks it as certain. Using It solution, stats = dfs(start, [], all_steps, model_value) Here, code proposes steps and the model evaluates them. You can also use a model-based proposer, such as the one from Lesson 47, combined with code-based validation of each proposed step.
What Changes With a Model Evaluator Aspect Exact Evaluator Model Evaluator Cost per evaluation Microseconds One API call Accuracy Perfect Imperfect: may mark solvable states "impossible" Effect of an error None A wrong "impossible" prunes a correct branch; a wrong "sure" wastes calls Mitigations Not needed Wider beams, a "likely" category, multiple evaluation votes, code checks where possible The original paper also sampled the value judgment several times and combined the results, which reduces the impact of a single wrong judgment, in the same way self-consistency reduces random reasoning errors (Lesson 45).
Keeping the Search Within Budget With model-based components, every expansion and evaluation costs money and time. Always set limits:
Limit Purpose Maximum depth Prevents endless exploration; often defined by the problem (three operations in the Game of 24) Beam width / branching limit Limits how many states are expanded per level Maximum number of evaluations A hard budget: stop and report failure when reached Pruning threshold Discards states below a minimum score Caching Stores evaluations of states already seen, so identical states are not evaluated twice Caching Example In the Game of 24, [4, 6, 13] can be reached through different paths. Caching avoids paying for the same evaluation twice:
from functools import lru_cache
@lru_cache(maxsize=None) def cached_value(state_key: tuple[Fraction, ...]) -> float: return model_value(list(state_key))
def value_with_cache(state: list[Fraction]) -> float: return cached_value(tuple(sorted(state))) Sorting the state before caching means [4, 6, 13] and [13, 4, 6] share one cache entry, because the order of the numbers does not matter.
BFS or DFS? Aspect BFS (Beam) DFS (Backtracking) Exploration style Wide: several branches in parallel Deep: one branch at a time Cost control Predictable: beam width × depth Varies: depends on how often it backtracks Good when Depth is fixed and short; evaluations are fairly reliable Problems are deep; good solutions can be recognized early Risk Correct branch may fall outside the beam Can waste many calls in a large wrong subtree Parallelism Evaluations at each level can run in parallel Mostly sequential The original paper used BFS for the Game of 24 and creative writing, and DFS for crossword puzzles, where long sequences of decisions must be tried and undone.
Common Mistakes Mistake 1: No Budget Limits What it is: Running a model-based search without limits on depth, branching, or calls.
Why it happens: The search code works in tests with a code evaluator.
What it causes: Unexpectedly large numbers of API calls and costs.
How to fix it: Set depth, beam width, and a maximum number of evaluations.
Mistake 2: Trusting a Weak Evaluator With a Narrow Beam What it is: Beam width 1 with a model evaluator.
Why it happens: It is the cheapest configuration.
What it causes: A single wrong evaluation discards the only path to the solution.
How to fix it: Use a wider beam, a "likely" category, or multiple evaluation votes.
Mistake 3: Not Validating Proposed Steps What it is: Accepting model-proposed steps without checking them.
Why it happens: Validation is skipped to keep code simple.
What it causes: States containing numbers that were never available, or wrong arithmetic results.
How to fix it: Validate and apply steps in code (Lesson 47, apply_step()).
Mistake 4: Evaluating the Same State Repeatedly What it is: Different paths reach identical states, and each is evaluated separately.
Why it happens: No cache is used.
What it causes: Wasted calls.
How to fix it: Cache evaluations using a normalized state key.
Best Practices Test the search logic with code-based components first. It is fast, free, and reveals bugs before you spend on API calls.
Invest in the evaluator. Its quality determines both the cost and the success of the search.
Use code wherever rules are exact. Code for validation and evaluation; the model for proposals and fuzzy judgments.
Choose BFS or DFS by problem shape. Short, fixed depth suits BFS; deep problems with early recognition of failure suit DFS.
Set strict budgets and cache evaluations. Make cost predictable.
Record visited states and backtracks. These statistics show whether the evaluator is doing its job.
Try It Yourself Exercise 1: Compare Search Strategies Run bfs() and dfs() with exact_value on five puzzles, such as [1, 2, 3, 4], [5, 5, 5, 1], [2, 3, 5, 12], [6, 6, 6, 6], and [1, 1, 1, 1]. Record evaluations, visited states, and whether a solution was found.
Exercise 2: Simulate a Weak Evaluator Write an evaluator that returns the exact value but is wrong 20% of the time (use random.random()). Run BFS with beam widths 1, 3, and 5 on ten solvable puzzles and record how often the solution is found. Explain the result.
Exercise 3: Add a Hard Budget Add a max_visits parameter to dfs() that stops the search and returns None once stats["visited"] reaches the limit. Run it with no_evaluation and a limit of 200 on [3, 3, 8, 8], and compare with exact_value under the same limit.