# Tree of Thoughts

Tree of Thoughts (ToT) is a prompting framework for large language models that performs deliberate search over a tree of intermediate reasoning states, called "thoughts", letting a model explore multiple reasoning paths, evaluate its own progress, and backtrack, instead of committing to a single left-to-right chain of thought. It was introduced in May 2023 (arXiv:2305.10601) by Yao and colleagues at Princeton University and [Google DeepMind](https://www.edgepedia.org/google-deepmind) (authors Yao, Yu, Zhao, Shafran, Griffiths, Cao, and Narasimhan) and published at NeurIPS 2023.<sup>[1](https://proceedings.neurips.cc/paper%5Ffiles/paper/2023/file/271db9922b8d1f4dd7aaef84ed5ac703-Paper-Conference.pdf)</sup><sup> • </sup><sup>[2](https://par.nsf.gov/biblio/10542045)</sup><sup> • </sup><sup>[3](https://klu.ai/glossary/tree-of-thoughts-prompting)</sup> The framework requires no additional training; a pre-trained language model is sufficient, with the model itself serving as both thought generator and state evaluator.<sup>[1](https://proceedings.neurips.cc/paper%5Ffiles/paper/2023/file/271db9922b8d1f4dd7aaef84ed5ac703-Paper-Conference.pdf)</sup>

| Fact | Value |
|---|---|
| Introduced | May 2023 (arXiv:2305.10601), Princeton / Google DeepMind; NeurIPS 2023<sup>[1](https://proceedings.neurips.cc/paper%5Ffiles/paper/2023/file/271db9922b8d1f4dd7aaef84ed5ac703-Paper-Conference.pdf)</sup><sup> • </sup><sup>[3](https://klu.ai/glossary/tree-of-thoughts-prompting)</sup> |
| Game of 24 (GPT-4) | 74% with ToT vs 4% with chain-of-thought (paper-reported)<sup>[1](https://proceedings.neurips.cc/paper%5Ffiles/paper/2023/file/271db9922b8d1f4dd7aaef84ed5ac703-Paper-Conference.pdf)</sup> |
| Mini Crosswords (GPT-4) | 78% letter-level, 60% word-level, and 20% game-level vs 5.0% game-level, 15.6% word-level, and 40.6% letter-level for CoT<sup>[1](https://proceedings.neurips.cc/paper%5Ffiles/paper/2023/file/271db9922b8d1f4dd7aaef84ed5ac703-Paper-Conference.pdf)</sup><sup> • </sup><sup>[9](https://arxiv.org/html/2305.10601)</sup><sup> • </sup><sup>[10](https://aclanthology.org/2025.findings-naacl.428.pdf)</sup> |
| Compute cost | 5.5k completion tokens and $0.74 per Game of 24 case; 5–100x more generated tokens than CoT<sup>[1](https://proceedings.neurips.cc/paper%5Ffiles/paper/2023/file/271db9922b8d1f4dd7aaef84ed5ac703-Paper-Conference.pdf)</sup> |
| Where it helps least | GSM8K 90 vs 86 and StrategyQA 83 vs 82 over CoT, marginal gains<sup>[1](https://proceedings.neurips.cc/paper%5Ffiles/paper/2023/file/271db9922b8d1f4dd7aaef84ed5ac703-Paper-Conference.pdf)</sup> |
| Independent check | A reproduced trajectory in the official repository scored 69% on Game of 24, attributed to stochastic decoding<sup>[4](https://awesome.papernotes.org/en/era5_genai_explosion/2023_tot/)</sup> |
| Guarantees | None: no surveyed implementation uses an explicit domain model, so no admissibility or optimality guarantees<sup>[5](https://arxiv.org/html/2605.28566)</sup> |

## What Tree of Thoughts is

[Chain-of-thought prompting](https://www.edgepedia.org/chain-of-thought-prompting) asks a model to write out intermediate reasoning steps before an answer, but the result is a single linear trace that is never reconsidered.<sup>[6](https://www.agentpatternscatalog.org/patterns/tree-of-thoughts/)</sup> ToT generalizes this: the model decomposes the problem into coherent units of text ("thoughts"), generates several candidate thoughts at each step, scores the resulting states, and searches the tree with lookahead and backtracking.<sup>[1](https://proceedings.neurips.cc/paper%5Ffiles/paper/2023/file/271db9922b8d1f4dd7aaef84ed5ac703-Paper-Conference.pdf)</sup> The original paper shows that plain input–output prompting, chain-of-thought, self-consistency (CoT-SC), and self-refinement are all special cases of this framework.<sup>[1](https://proceedings.neurips.cc/paper%5Ffiles/paper/2023/file/271db9922b8d1f4dd7aaef84ed5ac703-Paper-Conference.pdf)</sup>

The motivation came from an error analysis: on Game of 24, around 60% of chain-of-thought samples had already failed after generating the first step, equivalently the first three words, a direct consequence of left-to-right decoding with no ability to undo an early mistake.<sup>[1](https://proceedings.neurips.cc/paper%5Ffiles/paper/2023/file/271db9922b8d1f4dd7aaef84ed5ac703-Paper-Conference.pdf)</sup>

## How it works

ToT has four components.<sup>[1](https://proceedings.neurips.cc/paper%5Ffiles/paper/2023/file/271db9922b8d1f4dd7aaef84ed5ac703-Paper-Conference.pdf)</sup>

- **Thought decomposition.** The problem is broken into intermediate steps sized appropriately for the task.
- **Thought generator.** At each state the model proposes candidate next thoughts.
- **State evaluator.** Each state is scored either by value scoring, a scalar rating (for example 1–10), or a classification such as sure / likely / impossible, or by vote scoring, where states are compared against each other and the most promising is voted for.<sup>[7](https://www.ibm.com/think/topics/tree-of-thoughts)</sup>
- **Search algorithm.** [Breadth-first search](https://www.edgepedia.org/breadth-first-search) keeps the b most promising states per step, with b ≤ 5 in the paper's experiments, and suits shallow trees (Game of 24 and creative writing, depth ≤ 3); depth-first search with backtracking and pruning suits deeper problems such as Mini Crosswords.<sup>[1](https://proceedings.neurips.cc/paper%5Ffiles/paper/2023/file/271db9922b8d1f4dd7aaef84ed5ac703-Paper-Conference.pdf)</sup>

A 2026 formalization that maps ToT implementations onto classical heuristic search finds that surveyed implementations converge on a small set of patterns: systematic best-first search (BFS) for shallow deterministic tasks and lookahead-heavy DFS or MCTS-style search for deep multi-step reasoning.<sup>[5](https://arxiv.org/html/2605.28566)</sup>

## Measured effects

All benchmark numbers below are reported by the original paper unless noted.

- **Game of 24** (arithmetic to reach 24 from four numbers): GPT-4 with chain-of-thought solved 4% of tasks; ToT solved 74%.<sup>[1](https://proceedings.neurips.cc/paper%5Ffiles/paper/2023/file/271db9922b8d1f4dd7aaef84ed5ac703-Paper-Conference.pdf)</sup> A reproduced trajectory released in the official repository achieved 69%, which the retrospective attributes to stochastic GPT decoding.<sup>[4](https://awesome.papernotes.org/en/era5_genai_explosion/2023_tot/)</sup>
- **Mini Crosswords** (GPT-4): ToT achieved 78% letter-level, 60% word-level, and 20% game-level success; CoT achieved 40.6% letter-level and 15.6% word-level success, and input–output prompting achieved 38.7% letter-level and 14% word-level success.<sup>[9](https://arxiv.org/html/2305.10601)</sup> Ablations show the search machinery matters: removing backtracking dropped word-level success to 20% and removing pruning to 41.5%.<sup>[1](https://proceedings.neurips.cc/paper%5Ffiles/paper/2023/file/271db9922b8d1f4dd7aaef84ed5ac703-Paper-Conference.pdf)</sup>
- **Creative Writing** (GPT-4): ToT scored 7.56 versus 6.93 for CoT and 6.19 for input–output prompting, at roughly 5x the completion tokens.<sup>[1](https://proceedings.neurips.cc/paper%5Ffiles/paper/2023/file/271db9922b8d1f4dd7aaef84ed5ac703-Paper-Conference.pdf)</sup>
- **GSM8K and StrategyQA** (GPT-4): gains were marginal, 90 vs 86 on GSM8K and 83 vs 82 on StrategyQA, because chain-of-thought was already strong on GSM8K and StrategyQA's bottleneck is external knowledge rather than deliberate search.<sup>[1](https://proceedings.neurips.cc/paper%5Ffiles/paper/2023/file/271db9922b8d1f4dd7aaef84ed5ac703-Paper-Conference.pdf)</sup>
- **Model quality matters for generation, not just evaluation.** With GPT-3.5-turbo, ToT solved 19% of Game of 24 versus 3% for CoT. Mixing GPT-4 generation with GPT-3.5 evaluation reached 64%, while the reverse split reached 31%, suggesting thought generation is the bottleneck.<sup>[1](https://proceedings.neurips.cc/paper%5Ffiles/paper/2023/file/271db9922b8d1f4dd7aaef84ed5ac703-Paper-Conference.pdf)</sup>

## Cost and the accuracy-per-compute tradeoff

ToT buys accuracy with substantially more inference computation. Solving one Game of 24 problem with ToT required 5.5k completion tokens and 1.4k prompt tokens at $0.74 per case. For comparison, taking the best of 100 chain-of-thought trials cost $0.47 and reached 49% success, and best-of-100 input–output prompting cost $0.13 at 33% success. The paper notes ToT can require 5–100 times more generated tokens than CoT depending on prompts and search settings.<sup>[1](https://proceedings.neurips.cc/paper%5Ffiles/paper/2023/file/271db9922b8d1f4dd7aaef84ed5ac703-Paper-Conference.pdf)</sup> The main Game of 24 and creative-writing experiments together cost about $106 in API calls, with creative-writing ToT at about $0.32 per problem versus $0.07 for the baselines.<sup>[4](https://awesome.papernotes.org/en/era5_genai_explosion/2023_tot/)</sup>

A practitioner pattern catalog summarizes the tradeoff as 5–100x cost over CoT depending on branching factor and depth, with value-function quality bounding search benefit: a weak evaluator caps what any amount of search can recover.<sup>[6](https://www.agentpatternscatalog.org/patterns/tree-of-thoughts/)</sup>

## Comparison with other reasoning methods

- **Versus chain-of-thought.** CoT produces one linear trace that is never reconsidered; ToT maintains a tree of partial states with explicit lookahead, evaluation, and backtracking.<sup>[6](https://www.agentpatternscatalog.org/patterns/tree-of-thoughts/)</sup>
- **Versus self-consistency.** CoT-SC samples many independent chains and votes on answers. On Game of 24, CoT-SC with k=100 reached 9.0%, and even an oracle selecting the best of 100 CoT samples reached 49%, both below ToT(b=5)'s 74%.<sup>[4](https://awesome.papernotes.org/en/era5_genai_explosion/2023_tot/)</sup>
- **Versus graph-structured methods.** [Graph of Thoughts](https://www.edgepedia.org/graph-of-thoughts) and related schemes generalize the tree to arbitrary thought graphs. A 2026 workshop paper argues that schemes including ToT and Graph of Thoughts require users to define static, problem-specific reasoning structures and are often under-optimized in hyperparameters, prompts, runtime, and cost; its Framework of Thoughts, applying tuning, prompt optimization, parallel execution, and caching, reportedly made ToT-style schemes significantly faster, cheaper, and higher-scoring.<sup>[8](https://aclanthology.org/2026.surgellm-1.8/)</sup>
- **Versus reasoning models.** A 2026 retrospective argues ToT's durable claim is that reasoning ability lives in the inference-time process as well as in the parameters, and that 2024–2025 techniques such as o1, [DeepSeek-R1](https://www.edgepedia.org/deepseek-r1), verifier-guided decoding, and best-of-N with reward models extend the same test-time-compute idea, even when the intermediate thoughts are no longer visible to users.<sup>[4](https://awesome.papernotes.org/en/era5_genai_explosion/2023_tot/)</sup>

## Adoption and practice

Framework support exists: LangChain's `langchain_experimental` ships a `ToTChain` in which a generation strategy proposes child thoughts and a `ToTChecker` classifies each intermediate thought as valid or invalid.<sup>[6](https://www.agentpatternscatalog.org/patterns/tree-of-thoughts/)</sup> IBM's overview describes the method as computationally intensive in processing power and memory, limiting scalability in resource-constrained or real-time settings.<sup>[7](https://www.ibm.com/think/topics/tree-of-thoughts)</sup>

## Recent developments

Test-time compute became a central engineering dimension after 2023. [Reasoning models](https://www.edgepedia.org/reasoning-models) such as o1 and DeepSeek-R1 internalize search: they spend inference computation on longer, self-corrected reasoning traces, often guided by external verifiers, unit tests, symbolic checkers, retrieval evidence, or reward models rather than the model's own prompted self-evaluation.<sup>[4](https://awesome.papernotes.org/en/era5_genai_explosion/2023_tot/)</sup> In this view ToT is less a deployed product technique than a demonstration that shaped the field's direction: the retrospective characterizes it as showing that the same model, with the same weights, performs much better when inference spends structured computation.<sup>[4](https://awesome.papernotes.org/en/era5_genai_explosion/2023_tot/)</sup>

## References

1. Yao, S.; Yu, D.; Zhao, J.; Shafran, I.; Griffiths, T.; Cao, Y.; Narasimhan, K. "Tree of Thoughts: Deliberate Problem Solving with Large Language Models." NeurIPS 2023. https://proceedings.neurips.cc/paper%5Ffiles/paper/2023/file/271db9922b8d1f4dd7aaef84ed5ac703-Paper-Conference.pdf
2. NSF Public Access Repository record for the ToT paper. https://par.nsf.gov/biblio/10542045
3. "Tree-of-Thoughts (ToT) Prompting." Klu glossary. https://klu.ai/glossary/tree-of-thoughts-prompting
4. "Tree of Thoughts — 2026 retrospective." Awesome AI Papers. https://awesome.papernotes.org/en/era5_genai_explosion/2023_tot/
5. "Tree of Thoughts as a Classical Heuristic Search Problem: Formal Foundations and Design Patterns." arXiv, 2026. https://arxiv.org/html/2605.28566
6. "Tree of Thoughts." Agent Patterns Catalog. https://www.agentpatternscatalog.org/patterns/tree-of-thoughts/
7. "What is Tree Of Thoughts Prompting?" IBM. https://www.ibm.com/think/topics/tree-of-thoughts
8. "Framework of Thoughts: A Foundation Framework for Dynamic and Optimized Reasoning based on Chains, Trees, and Graphs." ACL SURGeLLM workshop, 2026. https://aclanthology.org/2026.surgellm-1.8/
9. Tree of Thoughts: Deliberate Problem Solving with Large Language Models, https://arxiv.org/html/2305.10601
10. aclanthology.org, https://aclanthology.org/2025.findings-naacl.428.pdf

---
*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Modern AI: foundation models, generative AI, and the AI industry › Foundation-model methods and training › Prompting, reasoning, and agents*

*Initially written Sep 17, 2026 · Edited: Oct 11, 2026; Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license