Tree of Thoughts: Deliberate Problem Solving with Large Language Models

In plain words

A language model normally writes an answer in one go, left to right, and never looks back. That works for many questions. It fails on puzzles where an early choice decides everything: if the first step is wrong, everything after it is wasted, and the model has no way to notice and try something else.

Tree of Thoughts makes the model work more like a person solving a puzzle on scratch paper. The answer is cut into a few meaningful steps, such as one equation, one writing plan or one crossword word. At each step the model suggests several possible next moves. The same model then judges which partial solutions look promising ("sure", "maybe", "impossible", or a vote for the best one). A classic search procedure, breadth-first or depth-first, keeps the good branches, drops the hopeless ones and backs up when it hits a dead end.

Nothing is trained: it is a program wrapped around ordinary prompts to an existing model. In the paper, GPT-4 solved 4% of hard "Game of 24" arithmetic puzzles with step-by-step prompting and 74% with Tree of Thoughts. The price is many more model calls per problem, so it pays off on tasks that need search or planning, not on questions the model already answers well.

TL;DR

ToT wraps a frozen LM in a tree search whose nodes are partial solutions s=[x, z_{1\cdots i}] made of task-specific "thoughts" (an equation line, a paragraph plan, a crossword word). A thought generator (i.i.d. sampling or a single "propose" prompt) expands nodes, and a state evaluator (the LM valuing each state, or voting across states) acts as the search heuristic for BFS (keep top b) or DFS (prune below a threshold, backtrack). Author-reported with GPT-4: Game of 24 74% vs 4.0% CoT and 9.0% CoT-SC (k=100); Mini Crosswords word-level success 60% vs 15.6% CoT; Creative Writing coherency 7.56 vs 6.93 CoT. Cost is several times CoT (Game of 24: $0.74 vs $0.47 per problem for best-of-100 CoT). Relevant if you build LM agents or solvers for problems with a natural step structure and a cheap way to judge partial progress.

Problem

Autoregressive decoding commits to token-level choices left to right, so it cannot explore alternative continuations or look ahead and backtrack §1. Prior prompting schemes inherit this: CoT samples one chain, and CoT-SC samples k independent chains and takes a majority vote, which explores nothing within a chain and only works when the output space is small enough for voting (e.g. multiple choice) §2. On tasks where early steps are decisive this fails badly: about 60% of GPT-4 CoT samples on Game of 24 are already dead after the first step, i.e. the first three words §4.1 fig. 3. ToT assumes access to a capable pretrained LM and a task whose solution can be decomposed into steps the LM can both generate and judge §3.

Method

ToT frames a problem as search over a tree whose nodes are states s=[x, z_{1\cdots i}]: the input plus the thoughts so far §3. An instantiation answers four questions §3:

1. Thought decomposition. Choose a thought size small enough that the LM produces diverse, promising samples and large enough that the LM can judge its prospects (one token is too small, a whole book too big) §3. Per task: one equation line (Game of 24, 3 steps), one paragraph-level writing plan (Creative Writing, 1 intermediate step), one word for one clue (Crosswords, 5-10 steps) tab. 1.
2. Thought generator G(p_\theta, s, k) produces k candidates §3:
   • Sample: k i.i.d. draws z^{(j)} \sim p_\theta^{CoT}(z_{i+1} \mid x, z_{1\cdots i}). Suited to rich thought spaces (paragraphs), where independent samples are diverse.
   • Propose: one "propose prompt" emits several candidates in one context, [z^{(1)},\dots,z^{(k)}] \sim p_\theta^{propose}(z_{i+1}^{(1\cdots k)} \mid s). Suited to constrained spaces (a word or a line), where independent samples would duplicate.
3. State evaluator V(p_\theta, S), the search heuristic, computed by the LM itself §3:
   • Value: each state on its own, V(p_\theta,S)(s) \sim p_\theta^{value}(v \mid s), where the prompt reasons and outputs a scalar (e.g. 1-10) or a class (e.g. sure/likely/impossible) mapped to a number. Reasoning combines short lookahead ("5 5 14 reaches 24 via 5+5+14") with commonsense ("1 2 3 are too small").
   • Vote: across states, V(p_\theta,S)(s) = \mathbb{1}[s=s^*] with s^* \sim p_\theta^{vote}(s^* \mid S), a multiple-choice comparison; useful when success is hard to score directly (e.g. coherence).
   • Either can be sampled several times and aggregated to trade cost for robustness.
4. Search algorithm: BFS or DFS; A* and MCTS are left for future work §3.

Algorithm: ToT-BFS(x, p_θ, G, k, V, T, b)   [alg. 1]
Input: input x, LM p_θ, thought generator G with size limit k,
       state evaluator V, step limit T, breadth limit b
1. S_0 ← {x}
2. for t = 1..T:
     S'_t ← { [s, z] : s ∈ S_{t-1}, z ∈ G(p_θ, s, k) }    # expand every kept state
     V_t  ← V(p_θ, S'_t)                                   # LM evaluates all candidates
     S_t  ← the b states of S'_t with the largest V_t       # prune to breadth b
3. return G(p_θ, argmax_{s ∈ S_T} V_T(s), 1)                # generate final output from best state

Algorithm: ToT-DFS(s, t, p_θ, G, k, V, T, v_th)   [alg. 2]
Input: current state s, step t, LM, generator G with size limit k, evaluator V,
       step limit T, value threshold v_th
1. if t > T: record output G(p_θ, s, 1)
2. for s' in G(p_θ, s, k), in order of decreasing promise:
     if V(p_θ, {s'})(s') > v_th:      # prune hopeless subtrees
         ToT-DFS(s', t + 1)
   # returning from the loop = backtracking to the parent

BFS is used when depth is small (T \le 3) and the frontier can be pruned to a few states (b \le 5) (Game of 24, Creative Writing); DFS when the tree is deeper (Crosswords) §3. IO, CoT, CoT-SC and self-refinement are described as special cases (trees of limited depth and breadth) §3 fig. 1.

Per-task instantiations.

• Game of 24 §4.1 fig. 2: at each node the remaining numbers are extracted and a 1-shot propose prompt (same prompt for all 3 steps, with a 4-number example) lists candidate next equations. BFS keeps b=5. Each candidate is valued as sure/maybe/impossible about reaching 24, sampled 3 times.
• Creative Writing §4.2 fig. 4: depth-2 tree with one intermediate thought (a plan). Sample k=5 plans, vote 5 times with a zero-shot vote prompt, keep the winner (b=1); then sample 5 passages from that plan and vote 5 times again.
• Mini Crosswords §4.3 fig. 6: DFS where a thought fills one clue. Filled words and letters may not be changed, so there are at most 10 steps. Existing thoughts are rendered as letter constraints on remaining clues; a propose prompt is called 5 times and asked for confidence levels, which are aggregated into a sorted candidate list. To evaluate a state, every remaining clue is checked for whether it can still be filled under its constraints; if any is "impossible", the subtree is pruned and DFS backtracks. DFS is capped at 100 steps; the output is the deepest explored state (the first one found if tied).

Baselines §4.1-§4.3: IO (5-shot for Game of 24 and Crosswords, zero-shot for writing); CoT (Game of 24: each example shows 3 intermediate equations; writing: plan then passage; Crosswords: intermediate words in order h1..5 then v1..5); CoT-SC as majority over 100 CoT samples (Game of 24); IO + iterative refine (at most 10 rounds with ground-truth correctness feedback on Game of 24; at most 5 rounds with LM self-judged coherence on writing). Oracle "best of k" for IO/CoT picks the best of k \le 100 samples.

Hyperparameters

Results

Author-reported, GPT-4 unless stated §4.

Game of 24 (100 hard games, success = valid equation equal to 24 using each input number once) tab. 2:

When success is plotted against nodes visited, ToT with b>1 beats best-of-k CoT §4.1 fig. 3a.

Creative Writing (100 inputs of 4 random sentences, coherency) §4.2 fig. 5: average GPT-4 score IO 6.19, CoT 6.93, ToT 7.56. In a blind pairwise comparison by a subset of the authors, ToT was preferred in 41 pairs, CoT in 21, 38 judged similar. Iterative refine improves IO from 6.19 to 7.67 and ToT from 7.56 to 7.91.

Mini Crosswords (20 games) tab. 3:

Without pruning, the correct solution was reached in 4/20 games, but the output heuristic returned only 1 of them; 3 of those 4 were games ToT with pruning did not solve within 100 steps §4.3.

Additional experiments app. B:

GPT-3.5 Game of 24 needed a 3-shot propose prompt instead of 1-shot. Mixing models: GPT-4 generation + GPT-3.5 evaluation 64%, GPT-3.5 generation + GPT-4 evaluation 31%, so generation is the bottleneck app. B.2.

Cost app. B.3:

tab. 7

tab. 8 (captioned "Cost analysis on Game of 24" in the paper, but it reports Creative Writing.) The authors estimate ToT needs 5-100x more generated tokens than CoT depending on prompts and search app. B.3.

Paper vs code

• Game of 24 depth. Paper: 3 thought steps tab. 1. Code: 4 BFS steps; when only "24" remains, the propose step switches to the CoT prompt to write the final "Answer:" expression, and a separate value_last_step_prompt judges that answer game24.py game24.py.
• Value labels and weights. Paper: sure/maybe/impossible §4.1. Code prompt: sure/likely/impossible, with weights 20 / 1 / 0.001 summed over the 3 samples, marked "ad hoc" in a comment; a state with 4 lines and no answer gets value 0 game24.py game24.py.
• Duplicate candidates within one step get value 0, so they are effectively never selected; value prompts are cached across calls bfs.py. Not in the paper.
• Final output. Alg. 1 returns one output generated from the best state alg. 1. Code returns all b selected candidates and logs both the mean and the "any correct" rate over them bfs.py run.py. Which of the two the 74% is, is not stated.
• Creative Writing temperature. Paper: 0.7 throughout §4. Script: 1.0 bfs.sh.
• Vote prompt input. The writing vote prompt lists the choices only; the task input x is not included text.py.
• Crosswords proposals. Paper: propose prompt 5 times §4.3. Notebook: n=8 completions, confidence weights 1/0.5/0.2/0.1, and at most 3 children expanded per state search_crosswords-dfs.ipynb search_crosswords-dfs.ipynb. Clues with 4 or more blanks are skipped by the evaluator crosswords.py. A child is also discarded without an LM call if it conflicts with already filled letters search_crosswords-dfs.ipynb.
• Crosswords DFS lives in a notebook, not in run.py; only BFS is in the package.

Pitfalls

• Alg. 2 as printed has a typo: the pruning test reads V(p_\theta,\{s'\})(s) > v_{thres}; the text and code imply evaluating the child s' against v_{th} alg. 2 §3. Alg. 2 also does not return after recording an output at t>T; implement an explicit stop.
• "k" in propose mode is not controlled. With the propose prompt, the number of children is however many lines the LM writes bfs.py, so BFS frontier size and cost vary per node.
• Heuristic scales are ad hoc. The 20/1/0.001 value mapping and the crossword confidence weights are unexplained code constants; changing them changes the ranking. The paper presents evaluation as qualitative classes only §4.1 §4.3.
• Evaluator errors prune correct answers. On crosswords, GPT-4 sometimes marks valid but rare words as impossible, pruning solved games §4.3. The output heuristic is also weak: oracle best state solves 7/20 games vs 4/20 tab. 3.
• Cost hides in evaluation. Every candidate gets several value calls (3 per thought in Game of 24), and Game of 24 ToT costs more per problem than 100 CoT samples ($0.74 vs $0.47) tab. 7. The appendix suggests early stopping once a solution is found, which the code does not do app. B.3.
• Ground-truth feedback in one baseline. IO + Refine on Game of 24 uses ground-truth correctness feedback §4.1; ToT uses none.
• Small evaluations. 100 games, 100 writing prompts, 20 crosswords; human writing judgments come from a subset of the authors §4.2 §4.3. GPT-4 snapshots from May 2023 are not identified further §4.
• Domain dependence. Prompts, thought format and parsing are hand-written per task (e.g. "left:" parsing in Game of 24 game24.py); gains on GSM8K and StrategyQA are small (86→90, 82→83) tab. 4.
• Vote parsing takes the last digit after "best choice is" via a greedy regex, which breaks with 10 or more choices text.py.

Lineage

• Builds on: chain-of-thought prompting (arXiv:2201.11903) and self-consistency (arXiv:2203.11171); ToT adds per-step branching, LM self-evaluation as a search heuristic, and BFS/DFS with backtracking §2 §3. Inspired by Newell, Shaw and Simon's problem solving as tree search §1.
• Compared against: IO, CoT, CoT-SC, iterative refinement §4.
• Related: RAP (arXiv:2305.14992), a concurrent MCTS-based method; self-evaluation guided decoding (Xie et al., 2023), which uses code-form thoughts with stochastic beam search §5.