Tree of thoughts

Tree of thoughts (Yao et al., 2023) has the LLM propose intermediate steps, score each partial state, and search the tree with BFS or DFS; on Game of 24 GPT-4 went from 4% with chain-of-thought to 74% with beam width 5.

8 min read860 wordsadvanced0 viewsupdated 2026-10-21

Definition

Tree of thoughts (ToT) is a prompting framework in which a language model solves a problem by searching over a tree of partial solutions. Each node is a state (the problem plus the steps so far); the model itself proposes the next steps ("thoughts") and evaluates how promising each state is; a classical search algorithm (breadth-first or depth-first) decides which states to expand. It was introduced by Yao, Yu, Zhao, Shafran, Griffiths, Cao and Narasimhan in "Tree of Thoughts: Deliberate Problem Solving with Large Language Models" (NeurIPS 2023).

Chain-of-thought prompting generates one reasoning path left to right. Self-consistency samples many complete paths and votes on the answers. Neither can look ahead, compare two partial solutions, or back up after a bad step: once a path is written, it is final.

Some problems need exactly that. In Game of 24 you combine four numbers with +,−,×,÷+,-,\times,\div to make 24. Most first moves lead nowhere, and you only find out a few steps later. In the paper's error analysis, about 60% of chain-of-thought samples had already failed after the first step.

ToT wraps the model in a search loop. The program, not the model, holds the tree, picks which nodes to expand and stops the search. The LLM is called many times, each time with a short, focused prompt: "propose next steps from here" or "can this state still reach 24?".

Four design choices

Instantiating ToT for a task

  1. 1Thought decomposition. Choose the size of one step: small enough that the model can propose good candidates, big enough to evaluate. Game of 24: one equation (3 steps per game). Crosswords: one word. Creative writing: one plan.
  2. 2Thought generator G(pθ,s,k)G(p_\theta,s,k). Either sample kk thoughts i.i.d. from a chain-of-thought prompt (good when the space is rich, such as paragraphs), or use one propose prompt that lists several distinct next steps (better when steps are short and samples would repeat).
  3. 3State evaluator V(pθ,S)V(p_\theta,S). Either value each state independently (the model labels it, e.g. sure / likely / impossible, often sampled a few times), or vote across states (the model picks the most promising one from a list).
  4. 4Search algorithm. BFS keeps the bb best states per depth, suited to shallow trees (Game of 24: depth 3, b=5b=5). DFS follows the best state until the evaluator judges it impossible, then backtracks, suited to deep trees (crosswords).
four design choices1 decomposeone thought = one step:two numbers → one2 generatepropose prompt listspossible next steps3 evaluatevalue prompt: sure /likely / impossible4 searchBFS: keep the b bestper depth (b = 5)BFS over thoughts (2 kept per depth for clarity)4 9 10 1310−4=66 9 13sure13−9=44 4 10sure13−10=33 4 9likely4+9=1310 13 13impossible9×10=904 13 90impossible13−9=44 6sure6+9=1513 15impossible10−4=64 6sure4×4=1610 16impossibledashed =pruned4×6=24 ✓(13−9)×(10−4) = 243 steps, 2 surviving routesYao et al. (2023), GPT-4, 100 hard Game-of-24 puzzles, success rate:IO prompt7.3%CoT4.0%CoT-SC k=1009.0%ToT b=145%ToT b=574%CoT fails mostly at step 1: a bad first equation cannot be taken back
fig.Game of 24 with input 4 9 10 13. The propose prompt suggests next steps; the value prompt labels the remaining numbers sure, likely or impossible; BFS keeps the best (2 per depth here; the paper uses b = 5). Two kept routes, 10−4=6 then 13−9=4, and 13−9=4 then 10−4=6, both end in 4×6 = 24. Bottom: the paper's GPT-4 success rates on 100 hard games.

BFS with a learned heuristic

St′={[s,z]:s∈St−1,  z∈G(pθ,s,k)},St=arg⁡max⁡S⊆St′,  ∣S∣=b  ∑s∈SV(pθ,St′)(s)S'_t=\{[s,z]: s\in S_{t-1},\; z\in G(p_\theta,s,k)\},\qquad S_t=\arg\max_{S\subseteq S'_t,\;|S|=b}\;\sum_{s\in S}V(p_\theta,S'_t)(s)
StS_{t}
the frontier: the bb states kept at depth tt; S0={x}S_0=\{x\}, the input
[s,z][s,z]
state ss extended by thought zz
GG
the thought generator (a propose or sample prompt to the LLM)
VV
the state evaluator (a value or vote prompt to the LLM)
bb
beam width; b=1b=1 is greedy search in thought space

For Game of 24 the evaluator's labels become numbers and are summed over the samples. In the authors' released code a state's value is the sum, over 3 samples, of 20 for "sure", 1 for "likely" and 0.001 for "impossible":

V(s)=∑j=13w(ℓj),w(sure)=20,  w(likely)=1,  w(impossible)=0.001,ℓj∼pθ(⋅∣value prompt,s)V(s)=\sum_{j=1}^{3} w(\ell_j),\qquad w(\text{sure})=20,\;w(\text{likely})=1,\;w(\text{impossible})=0.001,\quad \ell_j\sim p_\theta(\cdot\mid \text{value prompt},s)
ℓj\ell_j
the label from the jj-th sampled value prompt
ww
a hand-set weighting; one "sure" outweighs many "likely" verdicts

This is heuristic search where the heuristic is the model's own judgement, as in A* or beam search with an LLM in place of a hand-coded scoring function. The evaluator does not need to be exact, only good enough to keep at least one viable state in the frontier.

Paper setup and results (GPT-4)

Game of 24 data
1,362 games from 4nums.com sorted by human solve time; tested on the 100 hard games ranked 901–1,000
Game of 24, success
IO prompt 7.3%, chain-of-thought 4.0%, CoT with self-consistency (k = 100) 9.0%, ToT b = 1 45%, ToT b = 5 74%; even the best of 100 CoT samples reached only 49%
Game of 24, ToT config
3 thought steps, a propose prompt for generation, a value prompt sampled 3 times per state, BFS with b = 5
Mini crosswords
5 × 5 grids, DFS with pruning; word-level success about 60% versus under 16% for chain-of-thought
Creative writing
BFS of depth 2: sample 5 plans, vote for the best, then 5 passages, vote again
Game of 24, input 4 9 10 13 · BFS keeps the b best-scored thoughts per depthscore = Σ of 1 noisy verdict (1 = can still reach 24, flipped w.p. 0.10) + tie-breakdepth 1: kept 5 of 30 proposed states10−4=6left: 6 9 13viable · 1.4413−9=4left: 4 4 10viable · 1.4213−10=3left: 3 4 9viable · 1.3510−9=1left: 1 4 13dead end · 1.249×13=117left: 4 10 117dead end · 1.19depth 2: kept 5 of 57 proposed states4−3=1left: 1 9dead end · 1.3413−9=4left: 4 6viable · 1.314/117=0.03left: 0.03 10dead end · 1.279−6=3left: 3 13dead end · 1.274×13=52left: 1 52dead end · 1.23depth 3: check every last step of the kept states exactlysolved: 10−4=6 → 13−9=4 → 4×6=24this run: 87 value prompts · puzzle 1/10, run 3/20success over 10 puzzles × 20 runs, by b00.5121%b=139%b=252%b=366%b=472%b=5at b = 5, e = 0.10, k = 1success rate72.0%value prompts / puzzle77.0b = 1 (greedy in thought space)20.5%e = 0.5: the evaluator is a coin flip
value samples k
fig.Real BFS over Game-of-24 states with a simulated evaluator that knows if a state can still reach 24 but flips each verdict with probability e. Success is averaged over 10 hard puzzles × 20 seeded runs. At the defaults (b = 5, e = 0.10, k = 1) the shown run keeps 5 of 30 depth-1 states and solves 4 9 10 13 as 10−4=6 → 13−9=4 → 4×6=24 using 87 value prompts. Over all runs: 72.0% at 77.0 value prompts per puzzle; b = 1 gives 20.5%. Switch to k = 3 value samples: 97.5% (b = 5) and 87.0% (b = 1), at 230.3 prompts. At e = 0.5 the evaluator is a coin flip and b = 5 solves 2.5%; at e = 0 every b solves 100%.

Worked example: why beam width matters

At depth 1 of 4 9 10 13 there are 30 distinct next states and 4 of them can still reach 24. Let the evaluator flip each verdict with probability e=0.1e=0.1, keep the states it calls viable first (in random order), then the rest. On average it calls 3.6 of the 4 good states viable and also 2.6 of the 26 dead ends. The chance that the kept set holds at least one good state:

Beam be = 0 (perfect)e = 0.1e = 0.5 (random)
11.0000.6130.133
21.0000.8660.253
31.0000.9580.360
51.0000.9970.538
P(at least one viable state survives depth 1), exact, 30 candidates with 4 viable

With b=1b=1 the top-ranked state is a false positive 39% of the time. With b=5b=5 the frontier almost always holds a good state. The random column is plain combinatorics: 4/30=0.1334/30=0.133 for b=1b=1 and 1−(265)/(305)=1−65,780/142,506=0.5381-\binom{26}{5}/\binom{30}{5}=1-65{,}780/142{,}506=0.538 for b=5b=5. Errors compound over depths, which is why the full-run success in the viz (72.0%) is lower than this single-depth 99.7%.

python
1import re
2
3PROPOSE = "Input: {left}\nPossible next steps (one per line, e.g. '4 + 9 = 13 (left: 10 13 13)'):"
4VALUE = ("Evaluate if the numbers {left} can reach 24 using + - * /. "
5 "Answer with one word: sure, likely or impossible.")
6W = {"sure": 20.0, "likely": 1.0, "impossible": 0.001}
7
8def value(llm, left: str, k: int = 3) -> float:
9 votes = llm(VALUE.format(left=left), n=k) # k sampled verdicts
10 return sum(W.get(v.strip().lower().split()[-1], 0.0) for v in votes if v.strip())
11
12def tot_bfs(llm, numbers: str, depth: int = 3, b: int = 5):
13 frontier = [(numbers, [])] # (numbers left, steps so far)
14 for _ in range(depth):
15 cands = []
16 for left, steps in frontier:
17 for line in llm(PROPOSE.format(left=left), n=1)[0].splitlines():
18 m = re.search(r"\(left: ([\d. ]+)\)", line)
19 if m:
20 cands.append((m.group(1).strip(), steps + [line.split("(")[0].strip()]))
21 scored = sorted(cands, key=lambda c: value(llm, c[0]), reverse=True)
22 frontier = scored[:b] # keep the b most promising states
23 return [steps for left, steps in frontier if left == "24"]
ToT-style BFS for Game of 24. `llm(prompt, n)` stands for any chat-completion call returning n strings; prompts are abbreviated. Not run against a model here.

Use when

  • +Lookahead and backtracking: a bad early step is pruned instead of carried to the end.
  • +Modular: generator, evaluator and search algorithm can be changed independently.
  • +No training; works with any model that can follow propose and value prompts.

Avoid when

  • −Tens to hundreds of LLM calls per problem; latency grows with depth.
  • −Needs a task-specific decomposition and prompts, unlike a one-line chain-of-thought prompt.
  • −Only as good as the evaluator: a confident wrong verdict prunes the right branch.

Follow-ups vary the search: Monte Carlo tree search with the LLM as world model (RAP; Hao et al., 2023) and arbitrary graphs that merge and refine thoughts (Graph of Thoughts; Besta et al., 2023). When the steps are tool calls rather than private thoughts, the same idea becomes planning in an agent; see ReAct prompting.

Check yourself

A ToT system on Game of 24 has a weak evaluator. Which change most directly protects against pruning the only good branch?

Check yourself

What is the main difference between self-consistency and tree of thoughts?

Remember

  • ✓ToT = LLM as thought generator and state evaluator + a classical search algorithm (BFS or DFS) run by your code.
  • ✓BFS keeps the bb highest-valued states per depth: St=arg⁡max⁡∣S∣=b∑s∈SV(s)S_t=\arg\max_{|S|=b}\sum_{s\in S}V(s).
  • ✓Game of 24, GPT-4: chain-of-thought 4.0%, CoT-SC (k = 100) 9.0%, ToT b = 1 45%, b = 5 74%.
  • ✓A wider beam and repeated value samples protect against evaluator errors, at linear extra cost.
  • ✓Worth it when steps are easy to judge but hard to choose; otherwise a single chain-of-thought is cheaper.
← back to Generative AI roadmap