Research

Tree of Thoughts: Deliberate Problem Solving with Large Language Models

Shunyu Yao12 min readResearch
FOUNDATIONALAI AgentsAdvanced

Key takeaway

Foundational work on search and planning over reasoning paths.

Updated on Oct 3, 2026

01

Abstract

  • Tree of Thoughts (ToT) generalizes Chain-of-Thought by maintaining multiple intermediate reasoning states rather than committing to one linear chain.
  • A “thought” is a coherent language sequence representing an intermediate step toward solving a problem.
  • ToT lets the model generate multiple candidate thoughts, evaluate them, and search over them.
  • The paper evaluates ToT on Game of 24, creative writing, and crosswords.
  • The central result is that deliberate search can solve tasks where standard prompting and linear CoT frequently fail.

02

Introduction

  • Standard autoregressive decoding commits to the next token and therefore naturally produces a single reasoning trajectory.
  • Chain-of-Thought improves reasoning by exposing intermediate steps but still commits to one trajectory and cannot backtrack once a bad branch is taken.
  • ToT treats reasoning as a search problem in a space of partial solutions.
  • The framework borrows ideas from classical planning and search: states, operators, value functions, breadth-first search, and depth-first search.
  • The authors argue that some tasks require deliberate planning, lookahead, and self-evaluation rather than greedy generation.

03

Problem

  • The problem is how to enable an LM to explore alternatives and recover from locally plausible but globally wrong reasoning paths.
  • CoT can fail catastrophically when an early arithmetic or planning choice makes the rest of the trajectory unsalvageable.
  • Self-consistency samples multiple complete CoT solutions but does not explicitly evaluate partial states during reasoning.
  • ToT introduces intermediate-state evaluation so obviously unpromising branches can be pruned before completion.
  • The method must balance breadth, depth, candidate generation, state evaluation, and search cost.

04

Methodology

  • ToT has four explicit components: thought decomposition, thought generation, state evaluation, and search algorithm.
  • Thought decomposition defines the granularity of each reasoning unit instead of forcing one token at a time.
  • Candidate thoughts can be generated independently or sampled sequentially depending on the task.
  • State evaluation can be absolute, where each state receives a value, or relative, where candidates are compared.
  • The search controller uses these evaluations to retain promising states and discard weak ones.
Figure 1

05

Architecture

The system connects an LLM with state, control, tools, memory, environments, interfaces, or other agents.

06

Dataset

  • Game of 24 asks the solver to use four given numbers exactly once with +, −, ×, and ÷ to produce 24.
  • The task has 1,362 test instances and requires exact arithmetic composition.
  • The authors define a thought as an intermediate equation that uses two available numbers and produces a new number.
  • A state is represented by the remaining numbers plus the sequence of operations already performed.
  • The 4×4 crosswords task requires constructing a 4×4 grid where words satisfy crossing constraints.
  • Creative writing asks the model to write a coherent four-paragraph story with specified constraints.

07

Training

  • The main experiments use GPT-4 as the underlying language model.
  • For Game of 24, the authors prompt GPT-4 to generate candidate arithmetic operations and evaluate whether states can still reach 24.
  • For creative writing, the model generates story outlines and receives self-evaluation prompts for coherence and quality.
  • For crosswords, the model proposes candidate words and evaluates partial grids using constraint satisfaction signals.
  • The paper relies primarily on prompting and search rather than gradient-based training of a new model.

08

Experiments

  • The Game of 24 implementation uses breadth-first search with a fixed number of candidate states retained at each level.
  • The model generates multiple candidate thoughts from the same state rather than committing to its first suggestion.
  • State evaluation asks whether a partial arithmetic expression can plausibly reach 24.
  • For crosswords, ToT combines generation with evaluation and backtracking so inconsistent words can be replaced.
  • For creative writing, ToT performs planning over multiple outlines before producing the final story.
  • The experiments compare different thought granularity and search configurations.

09

Baselines

  • Standard CoT generates a single reasoning chain.
  • CoT with self-consistency samples multiple complete chains and selects the majority answer.
  • ToT differs by evaluating and pruning partial reasoning states during generation.
  • The paper also compares against IO prompting, where the model directly produces the final answer without explicit reasoning.
  • Human performance provides an additional reference point for the Game of 24 and crossword tasks.

10

Results

  • On Game of 24, standard GPT-4 prompting solves only 4% of the test set.
  • CoT improves performance to 4% in the reported setup, while self-consistency reaches 9%.
  • ToT solves 74% of the 1,362 Game of 24 instances.
  • Human performance is reported at approximately 60% for the same task, so ToT substantially exceeds the human reference under the paper's evaluation.
  • The result demonstrates that search over intermediate states can be more important than simply sampling more complete answers.

11

Conclusion

  • Tree of Thoughts reframes LLM reasoning from greedy sequence generation into deliberate search over a structured state space.
  • The key benefit is the ability to look ahead, compare alternatives, prune weak branches, and backtrack.
  • The approach is especially useful for tasks with verifiable intermediate states and substantial planning depth.
  • The paper suggests extending the framework with learned value functions, reinforcement learning, and broader search strategies.
  • Its central lesson is that inference-time computation can be spent on search instead of only generating longer linear chains.

12

References

Primary source: Yao, Shunyu; Yu, Dian; Zhao, Jeffrey; Shafran, Izhak; Griffiths, Thomas; Cao, Yuan; Narasimhan, Karthik. “Tree of Thoughts: Deliberate Problem Solving with Large Language Models.” arXiv:2305.10601.

  • The paper was published at NeurIPS 2023.
  • It explicitly positions ToT as a general framework that can incorporate different generation, evaluation, and search procedures.
  • The experiments demonstrate the framework on three qualitatively different tasks: arithmetic search, creative writing, and crossword solving.
  • The paper's limitation is that prompts and search hyperparameters remain task-specific, so the framework is not a fully autonomous universal planner.

Continue reading

Related research

Browse all research