Tree of Thoughts: Deliberate Problem Solving with Large Language Models (2023)

Tree of Thoughts (ToT) extends chain-of-thought prompting by having the model explore multiple reasoning paths, evaluate them, and backtrack when needed. It enables language models to solve problems that require planning and search.

Standard prompting generates a single chain of reasoning. Chain of thought generates a single step-by-step path. Tree of Thoughts generates multiple possible next steps at each point, evaluates which paths are most promising, and can abandon unpromising branches and explore alternatives.

The approach uses the language model itself as both the generator (proposing next steps) and the evaluator (judging whether a partial solution is promising). This creates a search tree over reasoning paths.

Many problems require exploring multiple approaches: solving puzzles, planning, creative writing, mathematical proofs, and complex debugging. Standard prompting commits to a single path and cannot recover from wrong turns. ToT adds the ability to consider alternatives and backtrack.

On tasks like the Game of 24, creative writing, and crossword puzzles, ToT dramatically outperforms chain-of-thought prompting. It shows that combining language models with classical search algorithms produces capabilities that neither has alone.

This work has influenced how modern AI systems handle complex tasks. The explore-evaluate-backtrack pattern appears in various forms in production AI agents.

Authors: Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas Griffiths, Yuan Cao, Karthik Narasimhan (Princeton, Google DeepMind).

Key benchmark: Solved 74% of Game of 24 problems vs. 4% with chain-of-thought prompting.

Link to paper: https://arxiv.org/abs/2305.10601

Full paper: https://arxiv.org/abs/2305.10601

Project GitHub repo - https://github.com/princeton-nlp/tree-of-thought-llm

Dave Hulbert: "Tree of Thoughts prompting" - https://github.com/dave1010/tree-of-thought-prompting