Tree of Thoughts

Full title: Tree of Thoughts: Deliberate Problem Solving with Large Language Models Authors: Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, Karthik Narasimhan (Princeton University; Google DeepMind) Venue/year: NeurIPS 2023 (arXiv v2, Dec 2023) arXiv: https://arxiv.org/abs/2305.10601 Local PDF: /Users/moscalej/Documents/Onep/research-papers/2305.10601-tree-of-thoughts.pdf

Why this paper matters

Tree of Thoughts (ToT) is the paper that turned "prompting" into "search." Chain-of-thought commits to a single left-to-right token stream; ToT reframes problem solving as classical tree search over thoughts — coherent text units that are partial solutions — where the LM plays both roles of a search algorithm: it generates candidate next states and it evaluates them as a heuristic, while an outer loop (BFS or DFS) supplies lookahead and backtracking (§1, §3). The paper explicitly grounds this in Newell & Simon's view of problem solving as "search through a combinatorial problem-space" (§1, §3). It is the canonical demonstration that test-time compute structured as search can unlock abilities sampling cannot: on Game of 24, GPT-4 with CoT solves 4% of tasks; ToT solves 74% (abstract, Table 2).

The problem

Autoregressive decoding makes "token-level, left-to-right decision-making" the only inference mechanism (abstract). §3 names the two resulting shortcomings of IO/CoT/CoT-SC prompting:

1. Locally, they never explore different continuations of a thought step — no branching.
2. Globally, they have no planning, lookahead, or backtracking — no way to evaluate a partial path and abandon it.

The error analysis makes this concrete: on Game of 24, about 60% of CoT samples have already failed after generating the first step — the first three words commit the whole chain (§4.1 Error analysis, Figure 3b). CoT-SC helps only when answers repeat — "there is no local exploration of different thought steps, and the 'most frequent' heuristic only applies when the output space is limited" (§2). The cognitive framing: LMs are System 1; deliberate planning needs a System 2 wrapped around it (§1).

The mechanism

Formal setup (§2)

p_theta is the pretrained LM; lowercase x, y, z are language sequences. The baselines are written as distributions to be generalized:

• IO: y ~ p_theta^IO(y | x) — direct answer.
• CoT: chain z_1..n bridges x to y, each z_i ~ p_theta^CoT(z_i | x, z_1..i-1).
• CoT-SC: k i.i.d. chains, return argmax_y #{i | y_i = y} — majority vote.

The four design questions (§3)

ToT frames any problem as search over a tree where each node is a state s = [x, z_1..i] — the input plus the thought sequence so far. An instantiation answers four questions:

1. Thought decomposition. What is one "thought"? A unit "small enough so that LMs can generate promising and diverse samples," yet "big enough so that LMs can evaluate its prospect toward problem solving" (§3.1). In the paper: an intermediate equation (Game of 24), a paragraph plan (Creative Writing), a word placed in a grid (Crosswords) — Table 1.

2. Thought generator G(p_theta, s, k). Two strategies to get k candidate next thoughts:

• Sample k i.i.d. thoughts from a CoT prompt: z^(j) ~ p_theta^CoT(z_{i+1} | s), j = 1..k. Better when the thought space is rich (paragraphs) — i.i.d. draws are naturally diverse.
• Propose k thoughts sequentially in one decode via a "propose prompt": [z^(1)..z^(k)] ~ p_theta^propose(z_{i+1}^(1..k) | s). Better when the space is constrained (a word, a line) — proposing in the same context avoids duplicates (§3.2).

3. State evaluator V(p_theta, S). The LM itself is the search heuristic — the paper's claimed novelty over programmed (DeepBlue) or learned (AlphaGo) heuristics (§3.3). Two modes:

• Value each state independently: V(p_theta, S)(s) ~ p_theta^value(v | s) — a reasoning prompt emits a scalar (1–10) or a classification (sure / likely / impossible) that is heuristically mapped to a value. The value prompt may use lookahead simulations ("5, 5, 14 can reach 24 via 5 + 5 + 14") and commonsense to promote good states or kill bad ones ("too big/small to reach 24"). Values "do not need to be perfect, only approximately helpful."
• Vote across states: V(p_theta, S)(s) = 1[s = s*] where the winner s* ~ p_theta^vote(s* | S) is chosen by deliberately comparing the frontier in one prompt — used when direct scoring is hard (passage coherency); "similar in spirit to a 'step-wise' self-consistency strategy," i.e. cast "which state to explore" as multi-choice QA.

Either way, prompt multiple times and aggregate (e.g. sample values 3 times per state) to trade compute for a more faithful heuristic (§3.3).

4. Search algorithm. Plug and play (§3.4): ToT-BFS (Algorithm 1) keeps the b most promising states per depth (used with T ≤ 3, small b ≤ 5); ToT-DFS (Algorithm 2) dives into the most promising child, prunes a subtree when its value drops to/below a threshold v_th (the evaluator deems it "impossible"), and backtracks to the parent to try the next candidate. A*/MCTS are left to future work.

The paper claims four conceptual wins (§3 end): generality (IO/CoT/CoT-SC/self-refinement are special cases — trees of limited depth/breadth), modularity, adaptability, convenience (no training; a frozen LM suffices).

The algorithm

Faithful reconstruction of Algorithm 1 (ToT-BFS) with Algorithm 2 (DFS) as the variant:

# ToT-BFS(x, p_theta, G, k, V, T, b)
#   x: input   G: thought generator, k candidates per state
#   V: state evaluator   T: step (depth) limit   b: breadth limit
S_0 ← {x}                                     # root state = bare input
for t = 1 .. T:
    S'_t ← { [s, z] : s ∈ S_{t-1}, z ∈ G(p_theta, s, k) }   # expand every kept state
    V_t  ← V(p_theta, S'_t)                   # value or vote over the frontier
    S_t  ← argmax_{S ⊆ S'_t, |S|=b} Σ_{s∈S} V_t(s)          # keep top-b states
return G(p_theta, argmax_{s∈S_T} V_T(s), 1)   # decode final answer from best leaf

# ToT-DFS(s, t, ...): if t > T record output; else for each child s' of
# G(p_theta, s, k) in sorted value order: recurse only if V(s') > v_th
# (otherwise prune the subtree); exhausting children = backtrack to parent.

Walkthrough:

1. S_0 ← {x} — the tree's root is the raw problem; every state is always the input plus a prefix of thoughts, so any state can be re-prompted from scratch (the method is stateless between LM calls).
2. Expansion — for each of the b surviving states, the generator produces k candidate next thoughts (sample or propose), giving up to b·k frontier states. In Game of 24: k proposed "next equations" per node, b = 5, T = 3 steps (§4.1 ToT setup).
3. Evaluation — one LM call (or several, aggregated — values sampled 3 times per thought in Game of 24) scores each frontier state. sure/maybe/impossible labels become the heuristic values; "impossible" is the pruning signal.
4. Selection — keep the b best-scoring states. With b = 1 this collapses to greedy step-by-step decoding with candidate generation and evaluation — which alone already lifts Game of 24 from 4% to 45% (Table 2).
5. Output — decode the final answer from the best depth-T state.
6. DFS variant — for deep, variable-length problems (Crosswords: 5–10 steps): explore the best child first, prune any state where some remaining clue is judged impossible to fill, backtrack on dead ends; step budget 100 (§4.3).

Symbols: p_theta frozen LM; s = [x, z_1..i] state; G generator; k candidates per expansion; V evaluator; v scalar value; v_th DFS pruning threshold; T depth limit; b BFS breadth; S_t kept states at depth t.

Results that matter

All experiments: GPT-4 chat completions, sampling temperature 0.7 (§4); run May 5–16, 2023 (footnote 1).

Ablations (Table 3, §4.3, Crosswords): oracle "+best state" output 67.5% word-level (7/20 games) — the output heuristic, not the search, is a bottleneck; -prune 41.5% and -backtrack 20% word-level — both search ingredients are load-bearing. Error analysis (Figure 3b): ~60% of CoT samples fail at step 1; ToT failures concentrate at the final step instead.

Limitations & how to defend the findings

• "It's just spending more compute." Partly, and the paper measures it: Figure 3a compares ToT against IO/CoT best-of-k with nodes visited on the x-axis — CoT best-of-100 reaches 49% while ToT (b>1) is far above it at comparable node counts. The gain is from where compute goes (explore + evaluate + prune), not the amount alone. Cost is still real: "ToT requires more resources (e.g. GPT-4 API cost) than sampling methods" (§6; details Appendix B.3).
• "The tasks are toys." Conceded up front: "this work only explores three relatively simple tasks that challenge GPT-4" (§6); the counterpoint is that they were chosen because IO/CoT score near zero, isolating search ability; harder deployments (coding, data analysis) are named as future opportunities.
• "Deliberate search may be unnecessary for most tasks." The authors agree — ToT is not for "many existing tasks that GPT-4 already excels at" (§6, Appendix B.1). It is a tool for the planning/search regime, not a universal replacement for CoT.
• "The LM heuristic can be wrong." Documented: in Crosswords the evaluator wrongly labels some rare/obsolete words "impossible" and prunes solvable subtrees (footnote 2, §4.3) — the no-prune ablation internally finds correct solutions for 4/20 games, 3 of which ToT-with- pruning cannot solve within 100 steps, so "better heuristics for DFS pruning are critical" (§4.3). Defense: even this imperfect heuristic beats no pruning on aggregate (60 vs 41.5 word-level), and the evaluator only needs to be "approximately helpful" (§3.3).
• "Is it robust to the base model?" Appendix B.2 has GPT-3.5 results (noted in §6 — associated with "better search and planning abilities incorporated with LMs"); the main claims are GPT-4-only, a fair reproducibility caveat.
• "Fine-tuning could subsume this." The discussion itself proposes ToT-style high-level counterfactual decision making as a training objective (§6) — the paper reads today as an early argument for what became test-time-compute/RL-on-reasoning training.

Connections

• Chain-of-thought & self-consistency — both are formal special cases (§2, §3): CoT is a tree with b = 1 and no evaluation; CoT-SC is k root-to-leaf chains with a vote only at the end. ToT's vote evaluator is explicitly "step-wise self-consistency" (§3.3) — see self-consistency.md for the voting math.
• ReAct / agent loops — ReAct follows one greedy trajectory through an environment; ToT shows what the "thought" half gains from branching. LATS and later agent-search systems merge the two: tree search over ReAct-style tool trajectories (see react.md).
• Reflexion / self-evaluation — ToT's state evaluator and Reflexion's evaluator are the same emerging primitive: the LM judging its own partial work (§5 Self-reflection discusses this lineage, incl. self-eval guided decoding) — see reflexion.md.
• Classical AI search — explicit rendition of Newell–Simon problem-space search; the paper positions itself as A*-like with an LM self-assessment heuristic (§5 Classical search methods), and leaves MCTS/A* instantiations to future work (§3.4).
• Test-time compute scaling — Figure 3a is an early "accuracy vs inference compute" curve; the modern reasoning-model literature (deliberation internalized by RL) is the §6 speculation made real.

Reading guide

• Read first: §1 (System 1/System 2 framing) and Figure 1 — the IO/CoT/CoT-SC/ToT schematic is the paper's thesis in one picture; then §3 in full: the four design questions are the reusable engineering checklist.
• Then: §4.1 (Game of 24) with Figure 2 and Table 2 — the cleanest instantiation (propose-prompt + value-prompt + BFS) and the headline 4% → 74%.
• Then: Table 3's ablation row block (+best state / -prune / -backtrack) — the evidence that search mechanics, not just sampling, drive the gains.
• Skim: §4.2 (vote evaluator in the wild), §4.3 + Figure 6 (DFS with pruning/backtracking), §5 Related Work, §6 (read the Limitations paragraph carefully — best source of caveats).
• Appendices as needed: B.1 (where ToT is unnecessary), B.2 (GPT-3.5), B.3 (cost/efficiency).
• The one figure to study: Figure 2 — propose prompt and value prompt on a real Game-of-24 node; once it clicks, Algorithms 1–2 are obvious.