Source-linked AI summary
Tree of Thoughts: Deliberate Problem Solving with Large Language Models
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, Karthik Narasimhan
TL;DR
Language models’ left-to-right token generation can struggle with problems requiring exploration, planning, or backtracking. Tree of Thoughts enables search over coherent reasoning steps and outperforms existing methods across Game of 24, Creative Writing, and Crosswords.
Problem
Existing language-model approaches do not explore alternative continuations or use planning, lookahead, and backtracking for general problem solving.
Method
Tree of Thoughts maintains a tree of coherent intermediate thoughts, enabling language models to generate, evaluate, and search multiple reasoning paths.
Results
ToT obtains superior results on all three evaluated tasks: Game of 24, Creative Writing, and Mini Crosswords.
Takeaways & Limitations
ToT augments language models’ associative token-level reasoning with deliberate search over possible solution paths, including for problems such as creative writing that are difficult to formalize.
Takeaways & Limitations
The evaluated tasks are limited to reasoning and search problems, while future interaction with external environments or humans could introduce harmful uses.
Abstract
from arXiv · showhide
Language models are increasingly being deployed for general problem solving across a wide range of tasks, but are still confined to token-level, left-to-right decision-making processes during inference. This means they can fall short in tasks that require exploration, strategic lookahead, or where initial decisions play a pivotal role. To surmount these challenges, we introduce a new framework for language model inference, Tree of Thoughts (ToT), which generalizes over the popular Chain of Thought approach to prompting language models, and enables exploration over coherent units of text (thoughts) that serve as intermediate steps toward problem solving. ToT allows LMs to perform deliberate decision making by considering multiple different reasoning paths and self-evaluating choices to decide the next course of action, as well as looking ahead or backtracking when necessary to make global choices. Our experiments show that ToT significantly enhances language models' problem-solving abilities on three novel tasks requiring non-trivial planning or search: Game of 24, Creative Writing, and Mini Crosswords. For instance, in Game of 24, while GPT-4 with chain-of-thought prompting only solved 4% of tasks, our method achieved a success rate of 74%. Code repo with all prompts: https://github.com/princeton-nlp/tree-of-thought-llm.
1 Introduction
The paper introduces Tree of Thoughts (ToT), a language-model inference framework that supports deliberate problem solving through multiple reasoning paths, self-evaluation, lookahead, and backtracking. It evaluates this approach on three challenging tasks requiring reasoning alongside systematic planning or search.
- 1 Introduction: Standard language-model inference still makes token-level decisions one at a time in a left-to-right autoregressive process.
- 1 Introduction: ToT operationalizes deliberate decision making by considering multiple choices, evaluating the current state, and looking ahead or backtracking toward global decisions.
- 1 Introduction: ToT frames language-model problem solving as search through a combinatorial problem space represented as a tree of coherent intermediate thoughts.
- 1 Introduction: The framework is tested on Game of 24, Creative Writing, and Crosswords, tasks requiring deductive, mathematical, commonsense, or lexical reasoning with systematic planning or search.
2 Background
The background formalizes input-output prompting and chain-of-thought reasoning as language-model problem-solving methods. It also describes self-consistency with CoT as sampling multiple chains, while noting its lack of local exploration within each chain.
- Input-output prompting: Input-output prompting maps a problem input to an output using task instructions and/or few-shot input-output examples.The output is sampled from the language model conditioned on the prompted input.
- Chain-of-thought prompting: Chain-of-thought prompting inserts coherent intermediate thoughts between the input and final output for non-trivial problems.Thoughts are sampled sequentially, but their decomposition into phrases, sentences, or paragraphs remains ambiguous.
- Self-consistency with CoT: Self-consistency with CoT samples k independent thought chains and returns the most frequent output.This ensemble approach can explore different thought processes for the same problem, such as alternative theorem proofs.
- Self-consistency with CoT: CoT-SC improves upon CoT but provides no local exploration of alternative thought steps within an individual chain.Its “most frequent” output heuristic applies only when the output decision is available.
3 Tree of Thoughts: Deliberate Problem Solving with LM
Tree of Thoughts (ToT) frames problem solving as search over a tree of partial solutions, enabling language models to explore multiple reasoning paths and deliberately evaluate which states to pursue. Its instantiations decompose thoughts, generate candidate continuations, evaluate states, and apply search algorithms such as breadth-first or depth-first search.
- Framework: ToT represents each state as the input plus a sequence of thoughts forming a partial solution, and explores multiple reasoning paths over this tree.The framework treats problem solving as tree search over coherent intermediate thought units.
- Thought decomposition: Thought decomposition adapts the intermediate unit to the problem, ranging from a few crossword words to an equation line or a paragraph-long writing plan.Thoughts should be small enough to support promising and diverse generation.
- Thought generation: Candidate thoughts can be sampled independently from a CoT prompt or proposed sequentially, with sequential proposals better suited to constrained thought spaces because they avoid duplication.Independent sampling is described as effective for richer spaces such as paragraph-length thoughts.
- State evaluation: The state evaluator acts as a search heuristic by estimating progress, using deliberate LM reasoning that can be more flexible than programmed rules and more sample-efficient than learned models.Evaluation may use scalar values or classifications, with few lookahead simulations and commonsense reasoning as explored bases.
- Search algorithm: BFS keeps the b most promising states per step for shallow trees, whereas DFS follows the most promising state, prunes impossible subtrees, and backtracks to continue exploration.BFS is used for Game of 24 and Creative Writing; DFS terminates at the output or when the evaluator falls below a threshold.
4 Experiments
Experiments evaluate Tree of Thoughts (ToT) against input-output and chain-of-thought prompting on tasks requiring search or planning. ToT improves performance substantially, including Game of 24 success rising to 74% and stronger creative-writing coherence.
- Experimental framework: The experiments compare standard input-output and chain-of-thought prompting with deliberate tree search using Chat Completion GPT-4 at temperature 0.7.The tasks are designed to be difficult even for GPT-4 with standard prompting.
- Game of 24: 74% success with ToT breadth b = 5, versus 7.3% for IO, 4.0% for CoT, and 9.0% for CoT-SC on Game of 24.ToT with b = 1 already reaches 45% success.
- Game of 24: Around 60% of CoT samples fail after the first step, highlighting the limitation of direct left-to-right decoding.The first step is equivalent to generating the first three words, such as “4 + 9”.
- Creative writing: ToT achieves a 7.56 average GPT-4 coherency score, compared with 6.19 for IO and 6.93 for CoT, across 100 creative-writing tasks.Humans prefer ToT over CoT in 41 of 100 pairs and prefer CoT over ToT in 21.
- Creative writing: Iterative refinement raises IO coherency from 6.19 to 7.67 and ToT coherency from 7.56 to 7.91.The authors describe refinement as a possible third thought-generation approach in ToT.
- Mini Crosswords: ToT reaches a 60% word-level success rate and solves 4 out of 20 Mini Crosswords games, while IO and CoT remain below 16%.Using the oracle best DFS state increases performance to 7/20 solved games.
5 Related Work
Tree of Thoughts relates to prior work on planning, self-reflection, program-guided generation, and classical search. It extends these lines through multiple feasible plans, self-assessment, and tree-search procedures while differing from specific prior frameworks in task complexity, modularity, and reliance on external information.
- Planning and decision making: ToT extends planning formulations by considering multiple potentially feasible plans during problem solving.Language models can propose reasonable plans from absorbed commonsense knowledge conditioned on problem settings and environmental states.
- Limitations: External retrieval or web interaction could augment LM problem solving under knowledge uncertainty, as illustrated by GPT-4 misreading “agend” as a typo for “agenda”.“Agend” is described as an obsolete form of “agendum”.
- Planning and decision making: ToT is also related to reasoning-as-planning with an internal world model and an MCTS-based method, but that prior framework addresses simpler tasks and lacks modularity for different tree-search algorithms.The supplied passage identifies these as distinctions between the approaches.
- Self-reflection: Prior self-reflection work has LMs evaluate prediction candidates and provide feedback, including feedback based on code execution results.Related approaches also add critic or review steps over actions and states.
- Program-guided LLM generation: Program-guided approaches organize LM behavior with systematic procedures or symbolic guidance, including search trees expanded by relevant external paragraphs.This differs from ToT because those trees are expanded by sampling external information.
- Classical search methods: ToT can be viewed as a heuristic search method like A*, with the LM’s self-assessment providing the heuristic at each search node.It is also related to NeuroLogic A*esque decoding, which uses efficient look-ahead heuristics for language models.
6 Discussion
Tree of Thoughts augments language models’ associative reasoning with tree-based search, translating classical problem-solving insights into actionable methods while supporting complex, less formalizable tasks. Its current evaluation is limited, and future deployment raises both safety risks and opportunities for interpretability and human alignment.
- Limitations and future directions: The initial study explores only three relatively simple tasks challenging GPT-4, and deliberate search may be unnecessary for tasks GPT-4 already handles well.The authors identify better search and planning abilities as a direction for future work.
- Conclusion: Tree of Thoughts augments LMs’ associative “System 1” with “System 2” search over possible solution paths.The framework translates classical problem-solving insights into actionable methods for contemporary LMs.
- Conclusion: ToT addresses complex problems that are not easily formalized, including creative writing.This extends classical problem-solving methods to tasks that are difficult to formalize.
- Limitations and future directions: Future interaction with external environments or humans could create dangers, including facilitating harmful uses of LMs.These applications are described as potential future directions rather than current evaluations.
- Limitations and future directions: ToT may improve interpretability of model decisions and opportunities for human alignment through readable, high-level representations.These benefits are presented alongside the risks of broader deployment.
B Additional Experiment Results
This section reports additional experiments using weaker language models or easier tasks, extending the evaluation beyond GPT-4 on three challenging tasks while discussing cost and efficiency.
- Additional experiments: Additional experiments evaluate weaker LLMs and easier tasks alongside the main GPT-4 experiments.The main experiments focused on GPT-4 and three hard tasks designed to challenge it.
- Additional experiments: Table 5 compares GPT-4 and GPT-3.5 on Game of 24.
- Additional experiments: Table 4 presents new tasks evaluated with zero-shot ToT and GPT-4.
- Additional experiments: Table 6 compares GPT-4 and GPT-3.5 on Creative Writing.
B.1 Extension to new tasks (GSM8k, StrategyQA) with zero-shot ToT
The authors applied a simple, generic zero-shot ToT-BFS to GSM8K and StrategyQA by generating and voting over strategies and then solutions. On 100-question subsets, ToT improved over CoT on both tasks, though only slightly because GPT-4 with CoT was already strong and StrategyQA is limited by external knowledge.
- Method: Zero-shot ToT-BFS samples five problem-solving strategies, votes for the best, then samples five solutions from that strategy and votes again.The implementation was adapted to GSM8K and StrategyQA with few extra lines of code.
- Evaluation: The evaluation used 100 randomly selected GSM8K test questions and 100 randomly selected StrategyQA development questions.Results were reported in Table 4.
- Results: ToT improved over CoT on both GSM8K and StrategyQA, but the gains were only slight.The passage attributes the limited improvement to GPT-4 with CoT already performing very well on these tasks.
- Implications: For traditional NLP tasks, smaller language models combined with ToT may be more suitable, whereas hard tasks may warrant GPT-4 combined with ToT.This recommendation is based on computational costs and the relative reasoning difficulty of the tasks.
B.2 Extension to new LMs (GPT-3.5)
Tests with GPT-3.5 show that ToT retains its advantage over CoT and IO, but Game of 24 performance depends strongly on thought-generation quality.
- Cross-model results: On both Creative Writing and Game of 24, GPT-3.5 preserves the ordering ToT > CoT > IO.The ordering remains true across both evaluated tasks.
- Cross-model results: On Creative Writing, GPT-3.5+ToT outperforms GPT-4+IO and performs similarly to GPT-4+CoT.This result suggests ToT can work well with weaker language models.
- Game of 24: 19%: GPT-3.5+ToT’s Game of 24 success rate, versus 74% for GPT-4+ToT.The 1-shot proposal prompt was changed to 3-shot for GPT-3.5 to make it work.
- Game of 24: 64%: GPT-4 generation + GPT-3.5 evaluation, compared with 31% for GPT-3.5 generation + GPT-4 evaluation.The comparison suggests thought generation is the bottleneck and that mixed models could reduce costs while retaining decent results.
B.3 Cost and efficiency
ToT improves deliberate problem solving but requires substantially more computation than IO or CoT, with costs depending strongly on prompts and search algorithms. Its flexible configuration enables performance–cost tradeoffs and offers opportunities for efficiency improvements.
- Game of 24: 5.5k completion tokens solve a Game of 24 problem with ToT, versus 6.7k tokens for close to 100 CoT trials, while ToT performs better than the best trial.The comparison concerns completion-token usage and performance on Game of 24.
- Creative Writing: Around 5x completion tokens and money cost are required for ToT on Creative Writing, consistent with a beam size of b = 5.Most generated tokens are passages.
- Overall cost: $106 covers the main ToT experiments on Game of 24 and Creative Writing, while Crosswords’ DFS experiments should also remain within $100.The reported total is calculated as 0.74 × 100 + 0.32 × 100 dollars.
- Overall cost: ToT may require 5-100 times more generated tokens than CoT, and its cost and efficiency depend strongly on the prompts and search algorithms used.The passage frames these values as general cost and efficiency behavior.
- Configuration and efficiency: Users can tune beam size, vote number, prompting style, or model choice to trade performance against cost under resource constraints or performance goals.Suggested choices include BFS settings, few-shot versus zero-shot prompting, and GPT-3.5 versus GPT-4.
- Configuration and efficiency: Efficiency could improve by early-stopping BFS after finding a solution or reducing beam size when thoughts become impossible.These are proposed improvements rather than evaluated results.