Tree-of-Thought: Search Over Reasoning Paths

When One Line of Reasoning Is Not Enough

Chain-of-thought gives the model room to work, but it still commits to one path. If the second step is a bad choice, every step after it is spent defending that choice. You see this on planning tasks: ask a model to order eleven database migrations so that no foreign key breaks, and it picks an order early, notices the conflict at migration seven, and then talks itself into a workaround instead of going back.

Tree-of-Thought (ToT) is the fix for that specific failure. Instead of one chain, you generate several candidate next steps, score each one, keep the promising ones, and expand them further. It is ordinary search, the same breadth-first or depth-first search you wrote in a data structures course, with the model doing two jobs: proposing moves and judging positions.

Where the Idea Comes From

The technique was described by Yao and colleagues in 2023 in Tree of Thoughts: Deliberate Problem Solving with Large Language Models. Their headline result was the Game of 24 (combine four numbers with arithmetic to make 24): GPT-4 with chain-of-thought solved 4% of the puzzles, while the tree search version solved 74%. The gap is so large because the puzzle punishes early commitment. Pick the wrong first operation and no amount of careful arithmetic afterwards saves you.

The paper breaks ToT into four decisions, and they are still the right way to design one:

1. What is a thought? The unit of progress. One equation, one line of a plan, one function in a patch. Too small and the tree explodes; too large and you are back to a single chain.
2. How do you generate candidates? Either sample several independent continuations, or ask for a numbered list of distinct options in one call. The list version gives you more variety per token.
3. How do you evaluate a state?Ask the model to rate it (the paper used “sure”, “likely” and “impossible”), have it vote between candidates, or run a deterministic check.
4. How do you search? Breadth-first with a beam (keep the best b states per level) or depth-first with backtracking when a branch is judged dead.

flowchart TD
    root["Problem"] --> a1["Thought A"]
    root --> a2["Thought B"]
    root --> a3["Thought C"]
    a1 --> e1{"Evaluate"}
    a2 --> e2{"Evaluate"}
    a3 --> e3{"Evaluate"}
    e1 -->|likely| b1["A then A1"]
    e1 -->|likely| b2["A then A2"]
    e2 -->|impossible| x2["Pruned"]
    e3 -->|likely| b3["C then C1"]
    b1 --> done["Best complete solution"]
    b3 --> done

    style x2 fill:#7f1d1d,color:#fff,stroke:#991b1b
    style done fill:#166534,color:#fff,stroke:#15803d

A Breadth-First ToT in About Eighty Lines

The code below is deliberately plain: no framework, one helper that calls whatever model you use. The task is the migration-ordering problem from the introduction. A state is a partial order, a thought is “the next migration to run”, the generator proposes a few candidates, and the evaluator rates whether the partial order can still be completed.

from dataclasses import dataclass, field

BEAM_WIDTH = 3        # states kept per level
CANDIDATES = 4        # next steps proposed per state
MAX_DEPTH = 12

@dataclass
class State:
    steps: list[str] = field(default_factory=list)
    score: float = 0.0

def propose(task: str, state: State) -> list[str]:
    """Ask for several distinct next steps in one call."""
    prompt = (
        f"Task:\n{task}\n\nSteps so far:\n" + "\n".join(state.steps or ["(none)"]) +
        f"\n\nList {CANDIDATES} different options for the NEXT step only, one per line. "
        "Each option must be a migration name from the task. No explanations."
    )
    lines = complete(prompt).splitlines()
    return [l.strip("-. 0123456789").strip() for l in lines if l.strip()][:CANDIDATES]

VALUE = {"sure": 1.0, "likely": 0.5, "impossible": 0.0}

def evaluate(task: str, state: State) -> float:
    """Rate a partial state. Swap this for real code whenever you can."""
    prompt = (
        f"Task:\n{task}\n\nPartial order:\n" + "\n".join(state.steps) +
        "\n\nCan this partial order still be completed without breaking a foreign key? "
        "Answer with one word: sure, likely or impossible."
    )
    word = complete(prompt).strip().lower().split()[0]
    return VALUE.get(word, 0.0)

def tree_of_thought(task: str, all_steps: set[str]) -> State | None:
    frontier = [State()]
    for _ in range(MAX_DEPTH):
        children = []
        for state in frontier:
            for step in propose(task, state):
                if step in state.steps or step not in all_steps:
                    continue                      # reject repeats and invented names
                child = State(steps=state.steps + [step])
                child.score = evaluate(task, child)
                if child.score > 0:
                    children.append(child)        # prune "impossible"
        if not children:
            return None                           # every branch died
        children.sort(key=lambda s: s.score, reverse=True)
        frontier = children[:BEAM_WIDTH]
        done = [s for s in frontier if set(s.steps) == all_steps]
        if done:
            return done[0]
    return None

Two lines in there do more work than they look. The membership check throws away candidates the model invented, which happens more than you would like when the list of valid moves is long. And the beam cut keeps the cost bounded: with a beam of 3 and 4 candidates, each level costs at most 3 proposal calls (one per kept state, each returning four options) and 12 evaluation calls, so a twelve-step problem tops out around 180 calls. Write that number down before you ship anything, because it is the number your finance team will eventually ask about.

The Evaluator Is the Whole Game

Most ToT setups that disappoint have a weak evaluator. If the model that proposed a step also grades it, it tends to grade its own ideas kindly, and the search turns into an expensive way to follow the first chain. Three ways to make evaluation honest, in the order I would try them:

1. Use real code. For the migration example, you can parse the foreign keys and check the partial order directly. For a code fix, run the failing test. A deterministic check is cheaper than a model call and it cannot be talked round. When a real check exists, ToT stops being a prompting trick and becomes a normal search with a model as the move generator.
2. Separate the judge from the proposer.A different prompt at minimum, ideally a different model. A cheaper model is often fine as a judge when the question is narrow (“can this still be completed?”) rather than open-ended.
3. Vote instead of score. Show the judge all the candidates at one level and ask which is most promising. Comparisons are more stable than absolute scores, which drift with phrasing.

def evaluate_with_code(task_fks: dict[str, set[str]], state: State) -> float:
    """Deterministic evaluator: a migration may only run after
    every table it references has been created."""
    created = set()
    for step in state.steps:
        if not task_fks.get(step, set()) <= created:
            return 0.0            # references a table that does not exist yet
        created.add(step)
    return 1.0                    # still valid; depth decides the rest

Once the evaluator is real code, you will notice something uncomfortable: for this particular problem you no longer need the model at all, because a topological sort solves it. That is a useful test for any ToT design. If you can write the evaluator as code and the move set is small and known, write the solver as code too. ToT earns its place when the moves are open-ended (wording, design options, patch contents) but the judgement can still be checked.

Breadth-First or Depth-First

Tree-of-Thought When Models Already Reason

The current frontier models (GPT-6 tiers with reasoning on, the Claude 5.5 models with adaptive thinking, current Gemini models with a thinking level) already explore and backtrack inside one call. For a lot of the puzzles that made ToT famous, raising the reasoning effort now gets you most of the way for a fraction of the engineering. So it is fair to ask whether the technique still matters.

It does, in three situations:

• You need the intermediate states. Internal reasoning is not returned in full, so you cannot audit which options were considered and why one was dropped. An explicit tree gives you that record, which matters for anything a reviewer has to sign off.
• You have an external checker. A model reasoning internally cannot run your test suite between thoughts. An orchestrated tree can, and a test result is worth more than any amount of self-assessment.
• You are on a small or self-hosted model. Without built-in reasoning, explicit search is one of the few ways to buy quality with compute, and those calls are cheap.

Outside those three, my default is a reasoning model with higher effort and a good prompt. Measure it on your own examples first; only build the tree if the simpler setup misses in ways the tree would catch.

Pitfalls

Branches that are the same idea reworded

Ask for four options and you often get one option phrased four ways. The tree looks wide but explores nothing. Ask for options that differ in a named dimension (“each option must change a different table first”), or deduplicate candidates before you evaluate them.

Scores that drift with wording

A numeric 1 to 10 score is unstable: the same state can get a 6 or an 8 depending on how the prompt is worded. Coarse labels such as “sure, likely, impossible” or a pairwise vote are steadier. If you must use numbers, use them only to rank within one level, never to compare across runs.

No stopping rule

Without a depth limit and a budget, a tree on an unsolvable input keeps going until something times out. Set a maximum depth, a maximum number of model calls, and a clear “no solution found” result your caller can handle.

Treating the final answer as verified

A tree that ends in a high-scoring leaf has found an answer the evaluator liked. If the evaluator was the model, that is not verification. Run the same final checks you would run on any other model output before anything downstream relies on it.