Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Reasoning Strategies › Tree of Thought

Michael BrenndoerferMarch 3, 202612 min read

Language AI HandbookAll chapters

Part 39 of 67Reasoning

Chapter 295Reasoning Strategies › Tree of Thought

Reading section 3 of 10 · Tree of Thought · 12 minSection 3 of 10 · 12 min

Section 3 of 10 · 12 min read

Reasoning Strategies › Tree of ThoughtOne section · Sections in this chapter3 / 10 ↓

Sections in this chapter10

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

Self-consistency improves accuracy by aggregating multiple complete reasoning paths. But it does not change how each path is generated: the model still reasons linearly, one token at a time, without backtracking. Tree of Thought (ToT), introduced by Yao et al. (2023), goes further by enabling explicit exploration of the search space.

The key insight is that expert human problem-solving is rarely linear. A chess player considers candidate moves, evaluates them, abandons bad ones, and backtracks. A mathematician tries a proof approach, gets stuck, and switches strategies. A programmer writes code, runs it, sees it fail, and revises the approach. All of these involve generating options, evaluating their promise, and pruning unpromising directions before committing to them. Standard chain of thought gives language models none of this infrastructure. Tree of Thought gives them an analogous ability to explore, evaluate, and backtrack.

The analogy to tree search from classical AI is intentional and deliberate. In game-playing AI like AlphaGo, a tree search algorithm evaluates candidate moves many steps ahead, prunes branches that look unpromising, and commits to the best-looking sequence. Tree of Thought applies the same architecture to open-ended language reasoning, but with the language model serving dual roles: as the generator that proposes candidate thoughts, and as the evaluator that scores their promise.

Thought DecompositionLink Copied

Tree of Thought treats the reasoning process as a tree search where each node is a "thought": a coherent unit of reasoning that represents an intermediate step toward a solution.

The first design decision is what counts as a thought. This depends on the problem:

For mathematical word problems, a thought might be one equation or one inference step
For writing tasks, a thought might be an outline point or a paragraph plan
For puzzle solving, a thought might be the state after applying one rule

The key property is that a thought should be small enough to generate many candidates, but large enough to represent meaningful progress. Sentence-level thoughts work well for most language reasoning tasks. If thoughts are too fine-grained (single words), the branching factor becomes astronomically large and the search collapses under its own cost. If thoughts are too coarse (entire solution attempts), there is no room for the search to discover that a partial solution looks promising and deserves further exploration.

The granularity of thoughts defines the shape of the search space. Choosing well requires understanding the problem structure. For a math puzzle like Game of 24, where you combine four numbers using arithmetic operations, a thought might be one operation: "I'll multiply 3 and 4 to get 12." For a creative writing task, a thought might be one structural decision: "The story will open with the protagonist discovering the key." In both cases, the thought is specific enough to evaluate, general enough to leave multiple continuations open, and small enough to generate quickly.

The Search TreeLink Copied

Given a problem and a sequence of thoughts $t_1, t_2, \ldots, t_k$ , the model can:

Generate: Produce $b$ candidate next thoughts from the current state
Evaluate: Score each candidate thought for how promising it looks
Search: Apply a search algorithm (breadth-first or depth-first) to navigate the tree

The evaluation step is what separates Tree of Thought from simple beam search. Rather than using the model's probability as the score, ToT uses the language model itself as a deliberate evaluator. The evaluator is prompted to assess whether a partial solution looks promising, typically producing a rating like "sure", "maybe", or "impossible". This prompting approach lets the evaluator reason about promise in a task-specific way, rather than just computing token probabilities.

Formally, let $s = (x, t_1, \ldots, t_k)$ be the current state: the original input $x$ plus $k$ thoughts taken so far. The tree is explored according to:

\text{score}(s) = V(p_\theta, s)

\text{next}(s) = G(p_\theta, s, b)

where:

$V(p_\theta, s)$ : the value function, which prompts the language model $p_\theta$ to evaluate state $s$
$G(p_\theta, s, b)$ : the generation function, which samples $b$ candidate thoughts from $p_\theta$ at state $s$
$b$ : the branching factor (number of candidates to generate at each node)

This formulation separates deliberate thinking (the evaluator) from creative generation (the generator), and both are implemented by the same underlying language model through different prompts. The generator is prompted to be creative and diverse. The evaluator is prompted to be analytical and critical. This dual-role architecture mirrors how expert problem-solvers think: generating ideas freely, then subjecting them to critical scrutiny.

BFS vs DFSLink Copied

Two search strategies apply naturally to the ToT framework:

Breadth-first search (BFS) maintains a frontier of $k$ most promising states at each tree depth. At each step, it generates $b$ children from each frontier state, evaluates all of them, and prunes to keep only the best $k$ . BFS is appropriate when the search space is wide and you want to explore many partial solutions before committing. It guarantees that the retained frontier always contains the most promising options seen so far at each depth level.

Depth-first search (DFS) explores one path as deep as possible, then backtracks when the evaluator judges a state as "impossible". DFS uses less memory and finds solutions faster when solutions exist at deeper levels, but can get stuck exploring unproductive branches if the evaluator is imperfect. With a good evaluator, DFS terminates quickly on hard problems. With a poor evaluator, it can explore an entire subtree of wrong paths before backtracking.

For puzzles like Game of 24, where a complete solution requires exactly 4 steps, BFS with a small frontier ( $k = 5$ ) works well. The problem has a fixed depth and you want to find the best path to that depth. For creative writing with many valid paths, DFS with backtracking is more efficient because you want to find one good solution, not the best among all solutions.

The choice between BFS and DFS interacts with the quality of the evaluation function. BFS is more forgiving of evaluator noise because it keeps multiple candidates at each level; even if the evaluator mis-scores one promising state, it is unlikely to mis-score all $b \times k$ candidates at that level. DFS is more sensitive to evaluator quality because it goes all-in on the highest-scored path at each step.

A Concrete Example: Game of 24Link Copied

The Game of 24 is a classic test of ToT. Given four numbers, combine them using addition, subtraction, multiplication, and division to reach 24. Standard chain of thought achieves only 4% on this task because a single wrong step early in the reasoning often propagates forward. If you combine the wrong pair of numbers in your first operation, the remaining numbers make 24 nearly impossible to reach, and standard prompting cannot detect this dead end or backtrack.

ToT with BFS achieves 74% accuracy by:

Generating 3 candidate equations at each step ("5 + 5 = 10", "5 * 5 = 25", "5 - 5 = 0")
Evaluating each candidate: is it possible to reach 24 from the remaining numbers?
Keeping the top 5 candidates at each depth
Backtracking from "impossible" states

The evaluator is prompted with examples like: "Given remaining numbers [10, 3, 7], is it possible to reach 24?" The model learns to recognize promising vs. dead-end states from few-shot examples. For instance, [10, 3, 7] is promising because 10 + 7 = 17 and 17 + 3 = 20, or more directly 3 * 7 = 21 and 21 + 3 = 24. The evaluator catches cases where no combination of the remaining numbers can possibly reach 24.

This concrete 18-fold improvement (4% to 74%) from chain of thought to ToT demonstrates that the failure mode is not the model's arithmetic ability or language understanding. The model knows how to do arithmetic. What standard prompting lacks is the ability to abandon a partially constructed solution that has gone wrong and try a different approach.

In[7]:

Code

# Demonstrate tree of thought search structure
# We'll simulate a simplified ToT BFS on a toy decision problem


class ThoughtNode:
    def __init__(self, state, thoughts, score):
        self.state = state  # Current problem state
        self.thoughts = thoughts  # Sequence of thoughts taken
        self.score = score  # Evaluation score


def simulate_tot_bfs(
    problem_depth=3,
    branching_factor=3,
    frontier_size=3,
    p_good_step=0.4,
    seed=42,
):
    """
    Simulate ToT BFS.
    - At each depth, generate branching_factor children from each frontier node
    - Score each child (1.0 = correct path step, 0.0 = wrong)
    - Keep top frontier_size nodes for next level
    - Returns success (True/False) and total nodes explored
    """
    rng = np.random.default_rng(seed)

    # Initial frontier
    frontier = [ThoughtNode(state="start", thoughts=[], score=1.0)]
    nodes_explored = 0

    for depth in range(problem_depth):
        candidates = []
        for node in frontier:
            for b in range(branching_factor):
                # Simulate thought generation and evaluation
                is_good = rng.random() < p_good_step
                thought = f"step{depth + 1}_option{b + 1}"
                score = float(is_good) * rng.uniform(0.7, 1.0) + (
                    1 - float(is_good)
                ) * rng.uniform(0.0, 0.3)
                candidates.append(
                    ThoughtNode(
                        state=f"depth{depth + 1}",
                        thoughts=node.thoughts + [thought],
                        score=score,
                    )
                )
                nodes_explored += 1

        # Keep top frontier_size nodes
        candidates.sort(key=lambda n: n.score, reverse=True)
        frontier = candidates[:frontier_size]

    # Check if any top node reached a good final state
    return any(n.score > 0.5 for n in frontier), nodes_explored


# Compare standard CoT vs ToT across many trials
n_trials = 2000
p_good = 0.4  # probability each single step is correct
depth = 3
branching = 3
frontier = 3

cot_successes = sum(
    all(np.random.random() < p_good for _ in range(depth))
    for _ in range(n_trials)
)
tot_successes = sum(
    simulate_tot_bfs(depth, branching, frontier, p_good)[0]
    for _ in range(n_trials)
)

cot_accuracy = cot_successes / n_trials
tot_accuracy = tot_successes / n_trials

Out[8]:

Console

CoT accuracy (single path, 3 steps): 6.8%
ToT BFS accuracy (B=3, K=3): 100.0%
Improvement: +93.2%

Out[9]:

Visualization

Bar chart comparing CoT vs ToT BFS accuracy on a simulated reasoning task. — Comparison of standard chain of thought (single path) versus Tree of Thought BFS with branching factor 3 and frontier size 3, simulated across a 3-step reasoning problem where each step is correct 40% of the time. ToT substantially improves accuracy by exploring and pruning multiple candidate paths, showing the value of systematic search over linear generation.

The simulation confirms the structural advantage of ToT. By generating and evaluating multiple candidate steps, the search tree is far more likely to find a path through all three correct steps than a single linear chain. With 40% per-step accuracy, a linear chain of 3 steps succeeds only $0.4^3 = 6.4\%$ of the time. With branching factor 3, there are 9 candidates at depth 1, and at least one of them is likely to be a good step. The pruning step concentrates the frontier on good paths, compounding the advantage at each depth.

Evaluation Quality and Its ConsequencesLink Copied

The value function determines whether Tree of Thought succeeds. Everything else: the generation, the search, the branching factor is secondary. If the evaluator cannot reliably distinguish promising states from dead ends, the entire search degrades into an expensive version of random search.

In the original ToT paper, the evaluation prompt was carefully designed for each task with few-shot examples of states labeled as "sure", "likely", or "impossible". This task-specific design effort is the price of the method's effectiveness. A generic evaluation prompt that works across all tasks is considerably harder to write, and the Yao et al. experiments did not demonstrate such a prompt.

This reveals a tension in ToT's design. The method achieves impressive results on the specific tasks it was designed and evaluated for. But applying it to a new task requires writing new decomposition prompts, new generation prompts, and new evaluation prompts, and verifying that they collectively produce a working search. This effort barrier means ToT is better suited to high-value problem types where engineering time is justified than to one-off problems where quick prompting suffices.

Limitations of Tree of ThoughtLink Copied

Tree of Thought is powerful but expensive. Generating and evaluating $b \times k$ candidate thoughts at each depth, across $d$ depths, costs $O(b \times k \times d)$ language model calls, compared to $O(1)$ for a single chain of thought pass. For a 3-depth problem with $b = 3$ and $k = 5$ , this is roughly 45 model calls versus 1. The financial and latency costs scale accordingly.

A subtler limitation is that ToT assumes the search tree is well-defined: that thoughts are discrete units, that the problem has a clear depth, and that partial solutions can be evaluated reliably. Many real-world reasoning tasks have continuous or ill-defined structure. Open-ended conversation, creative writing, and abstract reasoning do not naturally decompose into discrete thought steps with evaluable partial states. For these tasks, the ToT framework requires significant adaptation or may not apply at all.