Tree of thoughts

Also known as: ToT

On this page 7

Tree of thoughts (ToT) is a reasoning technique in prompting in which a language model generates several candidate intermediate steps, called thoughts, evaluates each partial solution and uses a search algorithm to expand promising branches and abandon weak ones. Instead of committing to one linear chain of reasoning, the model explores a tree of possible paths and can backtrack when a branch fails.

The approach was formalized in 2023 as an extension of chain-of-thought prompting for problems that require planning, lookahead or trial and error. It sits at the deliberate end of the prompting spectrum: it usually yields markedly better accuracy on search-heavy tasks but costs many more model calls than a single prompt.

How tree of thoughts searches for a solution

Tree of thoughts treats problem solving as search over a space of partial solutions. Each node in the tree is a state, consisting of the original problem plus the thoughts produced so far. The controller repeatedly asks the model to extend a state, asks the model again to judge the resulting states, and keeps only the best ones for the next round.

A working implementation needs four design decisions, summarized in the table below. Each one is chosen per task, which is why ToT is better described as a framework than as a single fixed prompt.

ComponentQuestion it answersTypical choices
Thought decompositionHow large is one step?One equation, one line of text, one crossword word
Thought generatorHow are candidate steps produced?Independent sampling or a single propose prompt
State evaluatorHow promising is a partial solution?Scalar value per state or a vote across states
Search algorithmWhich branches are expanded next?Breadth-first search or depth-first search
The four components of a tree of thoughts system

The evaluator is the decisive element. The model may label a state as “sure”, “likely” or “impossible” to reach the goal, and those labels are mapped to numeric scores. Because the same model both proposes and judges, the method depends on the model being better at verifying a step than at producing it, a property that holds for many arithmetic and constraint problems.

Search strategies and key parameters

The original experiments used breadth-first search (BFS) with a fixed beam width for shallow problems and depth-first search (DFS) with pruning for deeper ones. BFS keeps the best few states at every level, while DFS follows one branch until the evaluator rejects it and then backtracks to the most recent alternative.

The parameters below determine both quality and cost. Their values interact: the number of model calls grows roughly with branching factor times depth times beam width, plus the evaluation calls.

ParameterTypical rangeEffect of increasing it
Branching factor3 to 8 candidates per stateWider exploration, more generation calls
Beam width1 to 5 kept statesFewer missed solutions, higher cost
Depth3 to 10 stepsHandles longer plans, compounds evaluator error
Evaluation samples1 to 5 per stateMore stable scores, more calls
Pruning thresholdTask-specific score cutoffFaster search, risk of discarding valid paths
Main tree of thoughts parameters

On the Game of 24 benchmark, where four numbers must be combined into 24, the original study reported success rising from about 4 percent with chain-of-thought to about 74 percent with ToT using GPT-4 and a beam width of five. Gains on open-ended writing were smaller and judged more subjectively.

Tree of thoughts belongs to a family of methods that spend extra inference compute on reasoning. The distinctions lie in whether paths are independent, whether they are scored during generation and whether the structure allows merging.

TechniqueReasoning structureIntermediate evaluationRelative cost
Chain-of-thoughtOne linear pathNoneLow
Self-consistencyMany independent pathsMajority vote on final answers onlyMedium
Tree of thoughtsBranching tree with backtrackingScores every partial stateHigh
Graph of thoughtsGraph allowing merges and loopsScores and aggregates statesHigh
Least-to-most promptingOrdered subproblemsImplicit, through sequencingLow to medium
Tree of thoughts and neighboring techniques

Self-consistency differs from ToT in one crucial way: it cannot prune a bad path early, because it judges only completed answers. Graph of thoughts generalizes ToT by letting separate branches be combined into a single thought, which suits tasks such as merging sorted sublists.

When to use tree of thoughts in practice

Tree of thoughts pays off when a task has verifiable intermediate states and when an early wrong step makes the final answer unreachable. Puzzles, constrained planning, code with test cases and multi-step mathematics fit this profile. It is rarely worthwhile for factual lookup, summarization or classification.

The decision table summarizes typical situations.

SituationRecommended choiceReason
Arithmetic puzzle with a clear targetTree of thoughts with BFSPartial states are easy to verify
Long plan with hard constraintsTree of thoughts with DFSBacktracking recovers from dead ends
Question with one short answerSelf-consistencyVoting is cheaper and nearly as effective
Latency-sensitive chat responseSingle chain-of-thought promptToT adds seconds to minutes
Model with built-in extended reasoningTest before adding ToTInternal search may already cover the gain
Deciding whether to apply tree of thoughts

Implementations usually run the controller in ordinary code rather than inside one prompt. A short propose prompt, a short value prompt and a loop that tracks the frontier give far more control than asking the model to simulate the whole tree in a single response.

Limitations and common mistakes

The most serious limitation is cost and latency. A modest search can require dozens to hundreds of calls for one problem, which makes ToT impractical for high-volume traffic. Its benefits also shrink as models gain stronger native reasoning, so measured gains on one model do not transfer automatically to another.

  • Unreliable evaluator: if the model scores states inconsistently, search amplifies noise instead of finding better paths.
  • Thoughts that are too large: steps covering a whole solution leave nothing meaningful to compare or prune.
  • Single-prompt imitation: asking the model to imagine several experts in one reply lacks real backtracking and independent evaluation.
  • No budget limit: without a cap on calls or depth, costs grow quickly on unsolvable inputs.

Explained without jargon

Most AI answers are written in one go, like walking down a single path without looking back. Tree of thoughts asks the model to try several possible next steps, judge which ones look promising and drop the ones that lead nowhere.

It resembles how a person solves a maze on paper. You test a few turns, notice when a corridor is blocked and return to the last fork. This takes more time, but it finds answers that a single attempt would miss.

A typical use case

An operations analyst at a regional logistics firm uses a language model to draft weekly delivery schedules for 14 vans under constraints on driver hours, loading-dock windows and refrigerated cargo. A single prompt frequently produces schedules that violate one constraint late in the plan, forcing manual repair.

The analyst builds a tree of thoughts controller: each thought assigns one van’s route, a validator prompt scores the partial schedule against the constraints, and a depth-first search with a branching factor of four backtracks whenever a conflict appears. Each schedule now costs about 120 model calls and roughly three minutes, but the share of drafts needing manual correction falls from more than half to under one in ten, a trade the team accepts for a weekly task.