Tree of Thoughts
Tree of Thoughts (ToT) is a prompting and inference framework that generalizes chain-of-thought reasoning by having a language model explore multiple alternative reasoning paths as branches of a search tree, evaluate the promise of each…
Definition
Tree of Thoughts (ToT) is a prompting and inference framework that generalizes chain-of-thought reasoning by having a language model explore multiple alternative reasoning paths as branches of a search tree, evaluate the promise of each branch, and backtrack from unpromising ones, rather than committing to a single linear chain of reasoning.
Overview
Standard chain-of-thought prompting has the model generate one linear sequence of reasoning steps toward a final answer, with no mechanism to reconsider or explore alternatives if an early step turns out to be a mistake — once the model commits to a reasoning direction, it typically follows it to completion even if it leads to a dead end. Tree of Thoughts, introduced in a 2023 paper by Shunyu Yao and colleagues (with a closely related independent formulation proposed around the same time), addresses this by structuring the reasoning process explicitly as a tree: at each step, the model generates multiple candidate next 'thoughts' (intermediate reasoning steps) rather than just one, a separate evaluation step (often the same model, prompted to self-assess) scores or compares these candidates for how promising they seem toward solving the problem, and a search algorithm — commonly breadth-first search or depth-first search — decides which branches to expand further and which to prune or backtrack from. This turns the reasoning process from a single forward pass of generation into a deliberate search procedure, letting the model effectively explore, compare, and abandon unpromising paths, much like how a person solving a puzzle might consider a few different approaches, evaluate which seems most promising, and backtrack if one leads nowhere. The original paper demonstrated substantial gains on tasks that are difficult for standard chain-of-thought precisely because they require exploration and lookahead, such as the 'Game of 24' arithmetic puzzle, creative writing planning, and mini crossword puzzles. The trade-off for this improved reasoning is significant added inference cost: because the model must generate and evaluate many candidate thoughts across a branching tree rather than a single sequential chain, Tree of Thoughts consumes substantially more tokens and inference compute than plain chain-of-thought prompting for the same problem. As such, it is most useful for tasks with well-defined problem structure and enough value in getting the answer right to justify the extra compute, and it foreshadowed later developments in test-time compute scaling — some modern reasoning-focused models and agent frameworks incorporate tree- or graph-search-like reasoning natively rather than requiring it to be manually engineered via prompting.
Key Concepts
- Generalizes chain-of-thought by exploring multiple reasoning branches rather than one linear path
- Generates multiple candidate 'thoughts' at each reasoning step
- Uses a self-evaluation step to score or compare the promise of each candidate branch
- Applies search algorithms (breadth-first or depth-first search) to expand or prune branches
- Introduced in a 2023 paper by Shunyu Yao and colleagues
- Demonstrated strong gains on tasks requiring exploration and lookahead (e.g., Game of 24)
- Substantially higher inference cost than standard chain-of-thought prompting
- A precursor concept to search-based test-time compute scaling in later reasoning models