← All papers

Tree of Thoughts: Deliberate Problem Solving with Large Language Models

Yao, Yu, Zhao et al. · 2023 · NeurIPS 2023

ReasoningRead on arXiv

Generalizes chain-of-thought prompting by letting the model explore a tree of intermediate "thoughts," self-evaluate partial solutions, and search over reasoning paths. ToT is a foundational precursor to o1/o3-style test-time compute scaling.

Key Idea

Tree of Thoughts (ToT) reframes LLM reasoning as search over a tree instead of a single linear chain. Each node is a coherent "thought" (an intermediate step or partial solution), and the model both generates child thoughts and evaluates them as it goes. Classical search algorithms (BFS or DFS) then explore the tree, pruning bad branches and backtracking when needed.

How It Works

A ToT system is defined by four choices:

  1. Thought decomposition: what counts as one "thought" for the task (a single equation, a paragraph plan, a candidate word for a crossword cell)
  2. Thought generator: the LLM proposes k next thoughts given the current path (either by sampling or by an explicit "propose" prompt)
  3. State evaluator: the LLM scores each partial state as sure / maybe / impossible, or assigns a numeric value, used to rank branches
  4. Search algorithm: BFS (expand best-b states per level) or DFS (depth-first with backtracking when the evaluator says "impossible")

This lets the model look ahead, backtrack, and compare alternatives instead of committing to the first chain it samples.

Results

  • Game of 24 (combine 4 numbers with +−×÷ to make 24): GPT-4 with chain-of-thought reaches ~4% success; ToT reaches ~74%
  • Creative Writing (4-paragraph coherent passages with constraints): ToT produces passages humans prefer over CoT in pairwise comparisons
  • Mini Crosswords (5×5): word-level success jumps from ~16% (CoT) to ~60% with ToT-DFS

Why It Matters

  • Establishes that test-time search, not just bigger models, is a lever for harder reasoning
  • Directly inspired the o1 / o3 generation of reasoning models, which internalize search-like behavior
  • Shows that self-evaluation by the same LLM is a usable heuristic for pruning, no separate verifier model required
  • Modular: any of the four components can be swapped (e.g., a learned value function instead of LLM scoring)

Key Takeaways for Interviews

  • CoT = one linear path; ToT = explicit tree with generation + evaluation + search
  • ToT trades more inference compute for higher accuracy on planning/search-heavy tasks, it is dramatically more expensive than CoT
  • Best suited for problems with decomposable steps and a checkable notion of progress (puzzles, planning, constrained generation), less useful for one-shot factual queries
  • Self-evaluation by the LLM is the key trick that makes the tree searchable without an external oracle
  • Conceptual ancestor of test-time-compute scaling laws (o1, o3, DeepSeek-R1), knowing ToT helps explain why "thinking longer" works