agent-readings

Reasoning, Acting, and Reflection

Tree of Thoughts

Tree of Thoughts generalizes chain-of-thought prompting into explicit search over intermediate language states, letting an LLM generate, evaluate, and backtrack among multiple reasoning paths.

6Claims
6Evidence

Why It Matters

ToT makes the reasoning loop look like a planner: the runtime must manage state frontiers, candidate generation, heuristic evaluation, pruning, and search budget.

Problem

  • Input-output prompting makes one left-to-right completion.
  • Chain-of-thought prompting gives a single sequential reasoning trace without local exploration or backtracking.
  • Self-consistency samples multiple full traces, but does not explore alternatives within each intermediate step and works best when answers can be voted over.

Key gap: The paper targets tasks where early decisions matter and problem solving requires exploration, lookahead, or backtracking over intermediate states.

Method

Represent problem solving as search over a tree of language thoughts. For each task, choose the thought granularity, generate candidate thoughts, evaluate partial states with the LLM, and apply a search algorithm such as breadth-first or depth-first search to explore, prune, and backtrack.

  • Decompose the task into thought units such as equations, writing plans, or crossword words.
  • Generate candidate next thoughts from each frontier state.
  • Evaluate candidate states with value prompts or vote prompts.
  • Use BFS for shallow fixed-depth problems or DFS for deeper variable-depth problems.
  • Return a final solution once a complete state satisfies the task.

Claims

C1 · paper-supported

ToT defines LLM problem solving as search over a tree whose nodes are partial solutions expressed as language thoughts.

Scope: Framework definition in Sections 1-3.

  • E-framework: The paper defines each thought as a coherent language sequence and frames a state as a partial solution containing the input and thoughts so far, enabling exploration over a tree of thoughts.

C2 · paper-supported

A ToT implementation must answer four design questions: thought decomposition, thought generation, state evaluation, and search algorithm.

Scope: Section 3 method definition.

  • E-four-questions: A ToT instantiation chooses how to decompose thoughts, how to generate candidate thoughts, how to evaluate states, and what search algorithm to use; the paper explores BFS and DFS.

C3 · paper-supported

On Game of 24, ToT strongly outperforms IO, CoT, and CoT self-consistency baselines.

Scope: 100 relatively hard Game of 24 instances indexed 901-1000 from 4nums.com.

  • E-game24: On Game of 24, IO prompting solves 7.3%, CoT 4.0%, CoT-SC with k=100 solves 9.0%, ToT with breadth 1 solves 45%, and ToT with breadth 5 solves 74%. Best-of-100 CoT reaches 49%.

C4 · paper-supported

On the Creative Writing task, ToT uses planning plus voting to improve passage coherence relative to IO and CoT baselines.

Scope: Four-sentence constrained creative writing task evaluated by GPT-4 preference scoring.

  • E-creative-writing: The Creative Writing setup asks for a coherent four-paragraph passage ending in four provided sentences; ToT generates writing plans and uses voting to choose plans before final writing, improving coherence scores relative to IO and CoT in the paper's evaluation.

C5 · paper-supported

On Mini Crosswords, ToT with DFS and state pruning improves over IO and CoT but still solves only a minority of full puzzles.

Scope: 5x5 crossword task with 10 clues and exact-letter constraints.

  • E-crosswords: The Mini Crosswords task uses 5x5 puzzles with horizontal and vertical clues. ToT applies DFS with pruning by state value and improves over IO/CoT baselines while still solving only a limited share of complete puzzles.

C6 · paper-supported

ToT trades accuracy for inference cost and task engineering: it requires multiple LLM calls for generation/evaluation and task-specific search design.

Scope: Method setup, experiments, and discussion.

  • E-search-cost: ToT repeatedly calls the LLM for thought generation and state evaluation, uses breadth limits, value samples, and thresholds, and adapts decomposition/search choices separately for Game of 24, Creative Writing, and Crosswords.

Agent Infrastructure Takeaways

  • ToT turns reasoning into an explicit search workload: the runtime owns frontier state, branch expansion, scoring, pruning, and backtracking.
  • Thought granularity is an interface decision. A good runtime needs task-specific state representations that are neither token-level nor whole-solution level.
  • LLM-as-heuristic is useful but not authoritative; value prompts should be logged and paired with verifiers when available.
  • Search raises serving costs sharply because every branch can trigger generation and evaluation calls; batching and budget controls become part of the agent design.
  • ToT is the bridge from prompt engineering to planning: later agent systems can reuse the same generate/evaluate/search pattern around tool actions, code edits, or environment states.

Caveats

  • The paper evaluates three custom tasks, not broad production-agent workloads.
  • The strongest Game of 24 result benefits from an exact success verifier and task-specific decomposition.
  • Creative Writing evaluation uses GPT-4 judgments, which are weaker evidence than executable checks or human studies.
  • The framework increases latency and model-call cost compared with a single CoT trace.
  • The implementation requires task-specific prompts and search parameters, so adding a new task is not just turning on a generic algorithm.