Tree of Thoughts: Deliberate Problem Solving with Large Language Models

Problem

Framing

LLM inference stayed token-local and greedy at test time, which breaks on tasks that need lookahead, branching, and backtracking. The paper replaces single-chain decoding with search over semantically coherent thoughts plus LM-based self-evaluation. On Game of 24, GPT-4 rises from 4% with CoT to 74% with ToT.

Currently Used Methods

Direct antecedents

• @yaoReAct2022 — interleaves reasoning traces with actions in external environments.
  • Limitation in context: no explicit tree search over alternative thoughts.
• @weiCoT2022 — elicits intermediate reasoning with chain-of-thought prompting.
  • Limitation in context: commits to one left-to-right reasoning path.
• @kojimaZeroShotCoT2022 — triggers reasoning by prompting “let’s think step by step”.
  • Limitation in context: improves decomposition, not exploration or backtracking.
• @schrittwieserMuZero2020 — plans by tree search with learned value and policy models.
  • Limitation in context: needs trained search heuristics, not language-native evaluation.

Proposed Method

Architecture

ToT represents inference as a tree whose nodes are partial thoughts and whose edges are LM-generated continuations. The LM alternates between generating candidate thoughts, scoring states, and applying a search policy such as BFS or DFS. The thought granularity is task-specific: 3 arithmetic steps, a writing plan, or crossword fills.

Loss / Objective

The framework changes inference, not model training.It still queries the base LM autoregressively:

Algorithm

At each step, ToT expands candidate thoughts and keeps or explores states using LM-scored heuristics.

For Game of 24, BFS keeps the best $b=5$ states per depth. For Mini Crosswords, DFS explores one clue fill at a time and backtracks after low-value states.

Training Procedure

• Base model: GPT-4 chat completion.
• Sampling temperature: $0.7$.
• Game of 24: BFS, depth $3$, beam width $b=5$.
• Creative Writing: sample $5$ plans, vote $5$ times.
• Mini Crosswords: DFS with LM state evaluation and pruning.

Evaluation

Datasets

• Game of 24: 100 hard instances from 4nums.com, indexed 901–1000.
• Creative Writing: 100 prompts built from 4 random sentences.
• Mini Crosswords: 5×5 crossword puzzles with 10 clues.

Metrics

• Game of 24: success rate over valid equations.
• Creative Writing: GPT-4 coherency score; human pairwise preference.
• Mini Crosswords: crossword solve quality from exact fills / clue consistency.

Headline results

• Game of 24, GPT-4 CoT: 4.0% success.
• Game of 24, GPT-4 ToT $(b=5)$: 74% success.
• Game of 24, best-of-100 CoT: 49% success.
• Creative Writing, GPT-4 IO: coherency 6.19.
• Creative Writing, GPT-4 ToT: coherency 7.56.

Table 2: Game of 24 Results.

Ablations

• Beam width on Game of 24: $b=5$ far exceeds $b=1$; search breadth matters.
• Best-of-$k$ sampling: independent CoT samples trail deliberate search at similar token budgets.
• Creative Writing voting: plan-level voting raises coherency from 6.19 to 7.67.
• Passage refinement atop ToT raises coherency from 7.56 to 7.91.

Method Strengths and Weaknesses

Strengths

• Large gain on Game of 24: 74% versus 4% for GPT-4 CoT.
• Modular across tasks: same framework supports arithmetic, writing, and crosswords.
• Search is interpretable through explicit thought states and LM valuations.
• Beats best-of-100 CoT on Game of 24 with structured exploration.

Weaknesses

• Adds substantial inference cost; ToT uses far more tokens than IO or CoT.
• Requires task-specific thought granularity and search design.
• Evaluation is narrow: three bespoke tasks, all relatively small.
• Relies on LM self-evaluation, which can be noisy or miscalibrated.

Suggestions from the authors

• Apply ToT to harder tasks with deeper search trees.
• Learn or improve search heuristics beyond prompt-based self-evaluation.
• Study interaction with external environments and humans.
• Reduce token cost with better prompts and search algorithms.

Links

Prior Papers

• @yaoReAct2022 — ReAct is the clearest direct precursor: LM reasoning traces coupled to sequential decisions.
• @weiCoT2022 — ToT generalizes chain-of-thought from one trajectory to a searched set of trajectories.
• @kojimaZeroShotCoT2022 — Zero-shot CoT is a core inference baseline that ToT extends with branching and evaluation.
• @schrittwieserMuZero2020 — MuZero is a planning analogue: tree search with state evaluation, but outside language prompting.

Further Papers

• @kwonvLLM2023 — Extends LLM inference with explicit search or verification, in the same planning-for-reasoning vein.
• @lightmanProcessSupervision2023 — Focuses on supervising intermediate reasoning steps, complementary to ToT’s thought-level search.
• @shaoGRPO2024 — Later reasoning work can use structured rollouts and selection, echoing ToT’s multi-path exploration.