# 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.

Source: https://www.mlfoundry.in/learn/tree-of-thoughts  
Section: Generative AI › Prompt Engineering  
Level: advanced · 8 min read · updated 2026-10-21

**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. **Thought 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. **Thought generator** $G(p_\theta,s,k)$. Either sample $k$ 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. **State evaluator** $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. **Search algorithm.** BFS keeps the $b$ best states per depth, suited to shallow trees (Game of 24: depth 3, $b=5$). DFS follows the best state until the evaluator judges it impossible, then backtracks, suited to deep trees (crosswords).

> Figure: 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

$$
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)
$$

- $S_{t}$: the frontier: the $b$ states kept at depth $t$; $S_0=\{x\}$, the input
- $[s,z]$: state $s$ extended by thought $z$
- $G$: the thought generator (a propose or sample prompt to the LLM)
- $V$: the state evaluator (a value or vote prompt to the LLM)
- $b$: beam width; $b=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)=\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)
$$

- $\ell_j$: the label from the $j$-th sampled value prompt
- $w$: 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

> Figure: 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.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:

P(at least one viable state survives depth 1), exact, 30 candidates with 4 viable

| 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 $b=1$ the top-ranked state is a false positive 39% of the time. With $b=5$ the frontier almost always holds a good state. The random column is plain combinatorics: $4/30=0.133$ for $b=1$ and $1-\binom{26}{5}/\binom{30}{5}=1-65{,}780/142{,}506=0.538$ for $b=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
import re

PROPOSE = "Input: {left}\nPossible next steps (one per line, e.g. '4 + 9 = 13 (left: 10 13 13)'):"
VALUE = ("Evaluate if the numbers {left} can reach 24 using + - * /. "
         "Answer with one word: sure, likely or impossible.")
W = {"sure": 20.0, "likely": 1.0, "impossible": 0.001}

def value(llm, left: str, k: int = 3) -> float:
    votes = llm(VALUE.format(left=left), n=k)                # k sampled verdicts
    return sum(W.get(v.strip().lower().split()[-1], 0.0) for v in votes if v.strip())

def tot_bfs(llm, numbers: str, depth: int = 3, b: int = 5):
    frontier = [(numbers, [])]                              # (numbers left, steps so far)
    for _ in range(depth):
        cands = []
        for left, steps in frontier:
            for line in llm(PROPOSE.format(left=left), n=1)[0].splitlines():
                m = re.search(r"\(left: ([\d. ]+)\)", line)
                if m:
                    cands.append((m.group(1).strip(), steps + [line.split("(")[0].strip()]))
        scored = sorted(cands, key=lambda c: value(llm, c[0]), reverse=True)
        frontier = scored[:b]                               # keep the b most promising states
    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.

> **The cost is in the evaluator calls:** Every candidate state costs $k$ value prompts and every frontier state a proposal prompt. In the viz, $b=5$ with $k=3$ uses about 230 value prompts per puzzle, against one call for chain-of-thought. ToT pays off on tasks with a large, deceptive search space and a cheap, reliable evaluation; on tasks a model already solves with a single chain-of-thought, it only adds cost and latency.

> **Value with lookahead:** The Game-of-24 value prompt works because judging a state is easier than solving it. With two or three numbers left, the model can try a few combinations ("10 + 14 = 24: sure") or rule a set out by size ("1 2 3: too small: impossible"). Pick the thought size so that this kind of local check is possible.

**Strengths**

- 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.

**Limitations**

- 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**.

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

- A. Lower the sampling temperature of the propose prompt
- B. Increase the beam width b and/or sample the value prompt several times
- C. Use chain-of-thought instead of the propose prompt
- D. Reduce the number of thought steps from 3 to 2

**Answer:** B. Increase the beam width b and/or sample the value prompt several times — A wider beam keeps more candidates, so a good state survives even if a few dead ends outrank it, and averaging $k$ value samples reduces the evaluator's error. In the viz at $e=0.1$, success goes from 20.5% (b = 1, k = 1) to 72.0% (b = 5) and 97.5% (b = 5, k = 3).

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

- A. Self-consistency needs fine-tuning; ToT does not
- B. Self-consistency votes over complete paths at the end; ToT scores partial states and prunes during generation
- C. ToT uses greedy decoding only
- D. Self-consistency uses a separate verifier model

**Answer:** B. Self-consistency votes over complete paths at the end; ToT scores partial states and prunes during generation — Self-consistency samples full paths independently and aggregates only the final answers. ToT evaluates intermediate states, so it can drop or back up from a branch before it is finished. In the paper, self-consistency over 100 chain-of-thought samples reached 9% on Game of 24, against 74% for ToT.

**Key points**

- ToT = LLM as thought generator and state evaluator + a classical search algorithm (BFS or DFS) run by your code.
- BFS keeps the $b$ highest-valued states per depth: $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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
