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 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
- 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.
- 2Thought generator . Either sample 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).
- 3State evaluator . 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).
- 4Search algorithm. BFS keeps the best states per depth, suited to shallow trees (Game of 24: depth 3, ). DFS follows the best state until the evaluator judges it impossible, then backtracks, suited to deep trees (crosswords).
BFS with a learned heuristic
- the frontier: the states kept at depth ; , the input
- state extended by thought
- the thought generator (a propose or sample prompt to the LLM)
- the state evaluator (a value or vote prompt to the LLM)
- beam width; 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":
- the label from the -th sampled value prompt
- 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
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 , 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 b | e = 0 (perfect) | e = 0.1 | e = 0.5 (random) |
|---|---|---|---|
| 1 | 1.000 | 0.613 | 0.133 |
| 2 | 1.000 | 0.866 | 0.253 |
| 3 | 1.000 | 0.958 | 0.360 |
| 5 | 1.000 | 0.997 | 0.538 |
With the top-ranked state is a false positive 39% of the time. With the frontier almost always holds a good state. The random column is plain combinatorics: for and for . Errors compound over depths, which is why the full-run success in the viz (72.0%) is lower than this single-depth 99.7%.
1import re23PROPOSE = "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}78def value(llm, left: str, k: int = 3) -> float:9 votes = llm(VALUE.format(left=left), n=k) # k sampled verdicts10 return sum(W.get(v.strip().lower().split()[-1], 0.0) for v in votes if v.strip())1112def 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 states23 return [steps for left, steps in frontier if left == "24"]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 highest-valued states per depth: .
- ✓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.