Tree of Thoughts: Deliberate Problem Solving with Large Language Models
Authors: Shunyu Yao
Dian Yu
Jeffrey Zhao
Izhak Shafran
Thomas L. Griffiths
Yuan Cao
Karthik R Narasimhan
Venue: NeurIPS 2023 oral (2023)
Keywords: large language model
general problem solving
heuristic search
reasoning
planning
decision making
TL;DR: We combine LLM's capabilities of generating and evaluating diverse “thoughts” with search algorithms for robust problem solving.

Abstract: 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.

Tree of Thoughts: Deliberate Problem Solving with Large Language Models
Shunyu Yao Princeton University
Dian Yu Google DeepMind
Jeffrey Zhao Google DeepMind
Izhak Shafran Google DeepMind
Thomas L. Griffiths Princeton University
Yuan Can Google DeepMind
Karthik Narasimhan
Princcton University
Abstract
Language models are increasingly being deployed for general problem solving across a wide range tasks, are still confined 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 pivotal role. To surmount these challenges, introduce language model inference, "Tree Thoughts" (ToT), which generalizes over the popular "Chain of Thought" approach to prompting language models, and enables exploration over coherent units 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, well looking ahead backtracking when necessary to make global choices. Our experiments show that ToT significantly enhances language models' problem-solving abilities three novel tasks requiring non-trivial planning or search: Game 24, Creative Writing, and Mini Crosswords. For instance, in Game of 24, while GPT-4 with chain-of- of-thuught prompting only solved 4% of tasks, our method achieved a success rate of 74%. Code repo with all prompts:
framework for
geg.hi/..om/rrinntttoonnneeeeeee thouuhhh
1
Introduction
Originally designed to generate text, scaled-up versions of language models (LMs) such GPT 25
26 23 and PaLM (5] have been shown to be increasingly capable of performing an ever wider range of tasks requiring mathematical, symbolic, commonsense, and knowledge reasoning. It is perhaps surprising that underlying all this progress is still the original autoregressive mechanism for generating text, which makes token-level decisions one by and in left-to-right fashion. such a simple mechanism sufficient for L.M to be built toward general problem solver? If not, what problems would challenge the current paradigm, and what should be alternative mechanisms?
The literature on human cognition provides some clues to answer these questions. Research on "dual process" models suggests that people have two modes in which they engage with decisions fast, automatic, unconscious mode ("System I"") and a slow, deliberate, conscious mode ("System 2")
31 16 [5]. These two modes have previously been connected to variety of mathematical models used in machine learning. For example, research on reinforcement learning in humans and other animals has explored the circumstances under which they engage in associative "model free" learning or more deliberative "model based" planning 7 The simple associative token-level choices of LMS are also reminiscent of "System 1", and thus might benefit from augmentation by more deliberate "System 2" planning process that (1) maintains and explores diverse alternatives for current
30
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Input
Input
Input
Input
thought
Majo
Output
Output
Output
Output
(a]
(c) Chain of Thought Prampting (CaT]
(<) Self Consistency
(d) Tree of Thoughts (ToT)
Prompting (IO)
CoT (CoT-SC)
Figure 1: Schematic illustrating various approaches to problem solving with LLMs. Each rectangle box represents thought, which coherent language sequence that serves as an intermediate step toward problem solving. See concrete examples of how thoughts are generated, evaluated, and searched in Figures 6
choices instead of just picking one, and (2) evaluates its current status and actively looks ahead or backtracks to make more global decisions.
To design such planning process, we return the origins of artificial intelligence (and cognitive science), drawing inspiration from the planning processes explored by Newell, Shaw, and Simon starting in the 1950s [21 22). Newell and colleagues characterized problem solving [2] search through a combinatorial problem space, represented as tree. We thus propose the Tree of Thoughts (ToT) framework for general problem solving with language models. As Figure Iillustrates, while existing methods (detailed below) sample continuous language sequences for problem solving, ToT actively maintains a tree of thoughts, where each thought a coherent language sequence that serves as intermediate step toward problem solving (Table [ Such high-level semantic unit allows the LM self-evaluate the progress different intermediate thoughts make towards solving the problem through deliberate reasoning process that is also instantiated in language (Figures 4 This implementation search heuristics via LM self-evaluation and deliberation novel, as previous search heuristics are either programmed or learned. Finally, we combine this language- capability to generate and evaluate diverse thoughts with search algorithms, such as breadth-first search (BFS) depth-first search (DFS), which allow systematic exploration of the tree of thoughts with lookahead and backtracking.
Empirically, we propose three new problems that challenge existing LM inference methods even with the state-of-the-ard language model, GPT-4 (23]: Game of 24, Creative Writing, and Crosswords (Table []. These tasks require deductive, mathematical, commonsense, lexical reasoning abilities, and way to incorporate systematic planning or search. We show ToT obtains superior results on all three tasks by being general and flexible enough to support different levels of thoughts, different ways to generate and evaluate thoughts, and different search algorithms that adapt to the nature of different problems. We also analyze how such choices affect model performances via systematic ablations and discuss future directions better train and use LMs.
2 Background
We first formalize some existing methods that use large language models for problem-solving. which our approach is inspired by and later compared with. We use pe to denote a pre-trained LM with parameters 0, and lowercase letters y, 2, to denote a language sequence, i.e. (x[[1),-. ".ll),...,,,,1) ,<()) where each xr] is token, so that pe (a) = II_ (1]..)) We use uppercase letters S, to denote collection of language sequences.
Input-output (IO) prompting is the most common way turn a problem input into output with LM: y po(u/promptrr where promptro wraps input x with task instructions and/or few-shot input-output examples. For simplicity, let us denote pprompt(outpan pa( pe(output prompt(input)) so that IO prompting be formulated y pb (ylz).
linput)

---

Chain-of-thoughe (CoT) prompting [38 was proposed to address cases where the mapping of input x to output y is non-trivial (e.g. when æ is math question and y the final numerical answer). The key idea is to introduce chain of thoughts "1,".. 2n, to bridge x and y. where each is coherent language sequence that serves as a meaningful intermediate step toward problem solving (e.g. 2g could be an intermediate equation for math QA). To solve problems with Co'I, each thought 24 ~ Pg CoTl
(Za I. 21...-1) is sampled sequentially, then the output y ~ Pg Poo (ylæ, Z1...). In Coll (21..n: is sampled as a continuous language sequence, and the decomposition of thoughts (e.g. is each zj phrase, a sentence, or a paragraph) is left ambiguous.
practice, [Z y) ~ Pa
Self-consistency with CoT (CoT-SC) 36 is an ensemble approach that samples l: i.i.d. chains of thought: [ef y01 ~ P y/z)
(i = 1 .... k), then returns the most frequent output: arg maxy # {i ( = y)- CoT-SC improves upon CoT, because there are generally different thought processes for the same problem (e.g. different ways to prove the same theorem), and the output decision can be more faithful by exploring a richer set of thoughts. However, within each chain there no local exploration of different thought steps, and the "most frequent" heuristic only applies when the output space is limited (e.g. multi-choice QA).
(21...m.
3 Tree of Thoughts: Deliberate Problem Solving with LM
A genuine problem-solving process involves the repeated use of available informa- tion to initiate exploration, which discloses, in turn, more information until a way to attain the solution is finally discovered.-NNwwe et al. (27
Research on human problem-solving suggests that people search through combinatorial problem- space - a tree where the nodes represent partial solutions, and the branches correspond to operators that modify them 21 Which branch to take is determined by heuristics that help to navigate the problem-space and guide the problem-solver towards a solution. This perspective highlights two key shortcomings of existing approaches that use LMs solve general problems: 1) Locally, they do not explore different continuations within a thought process - the branches of the tree. 2) Globally, they do not incorporate any type of planning, lookahead, or backtracking to help evaluate these different options- the kind of heuristic- prrristic-uuiedd search that seems characteristic of human mooblem-solvigg
To address these shortcomings, we introduce Tree of Thoughts (ToT), a paradigm that allows LMs to explore multiple reasoning paths over thoughts Ffigure[e)) ToT frames any problem as search over tree, where each node is state s = [ar, 21- representing partial solution with the input and the sequence of thoughts so far. A specific instantiation of ToT involves answering four questions: 1. How decompose the intermediate process into thought steps; 2. How to generate potential thoughts from each state; 3. How to heuristically evaluate states; 4. What search algorithm to use.
1. Thought decomposition. While CoT samples thoughts coherently without explicit decomposition. ToT leverages problem properties to design and decompose intermediate thought steps. As Table [ shows, depending different problems, thought could be couple of words (Crosswords), line of equation (Game of 24), or a whole paragraph of writing plan (Creative Writing). In general, a thought should be "small" enough so that LMs can generate promising and diverse samples (c.g. generating a whole book is usually too "big" to be coherent), yet "big" enough so that LMs can evaluate its prospect toward problem solving (e.g. generating one token is usually too "small" evaluate).
2. Thought generator G(pe, s, k). Given a tree state s = [z, 21...). we consider two strategies to generate & candidates for the next thought step:
(a) Sample i.idd. thoughts from a CoT prompt (Creative Writing, Figure 4
2
1...k pCol (Zz41 [s) = py Coo (24+1 12, 21...) (j=1l..kk) k). This works better when the thought space is rich (e.g. each thought is a paragraph), and i.i.d. samples lead to diversity:
(b) Propose thoughts sequentially using a "propose prompt" (Game of 24, Figure Crosswords,
Figure 6): [=(1).... ..., (*)) proppsse [z++]
(l..k) s). This works better when the thought
space is more constrained (e.g. each thought is just a word or a line), so proposing different thoughts in the same context avoids duplication.
3. State evaluator (ppo, S). Given a frontier of different states, the state evaluator evaluates the progress they make towards solving the problem, serving as a hearistic for the search algorithm to determine which states to keep exploring and in which order. While heuristics are standard approach to solving search problems, they are typically either programmed (e.g. DeepBlue (3) or
3

---

learned (e.g. AlphaGo (2)). We propose a third alternative, by using the LM to deliberately reason about states. When applicable, such deliberate heuristic can be more flexible than programmed rules, and more sample-efficiet than learned models. Similar to the thought generator, we consider two strategies to evaluate states either independently or together:
(a) Value each state independently: V (peo (s) pp Vs E S. where a value prompt reasons about the state s to generate scalar value v (e.g. 1-10) or a classifica- tion (e.g. sure/likely/mppssibble that could be heuristically turned into value. The basis of such evaluative reasoning can vary actoss problems and thought steps. In this work, we explore evaluation via few lookahead simulations (e.g. quickly confirm that 5, 5, 14 can reach 24 via 5 + 5 + 14, or "hot_I" can mean "inn" via filling "e" in "-") plus commonsense (e.g. 1 2 are too small to reach 24, or no word can start with "tzxc"). While the former might promote "good" states, the latter could help eliminate "bad" states. Such valuations do not need to be perfect, and only need to be approximately helpful for decision making.
(b) Vote across states: V(po, ()) [[s s*], where a "good" state ~ P/ p (s*(S) is voted out based on deliberately comparing different states in S in vote prompt. When problem success harder to directly value (e-g. passage coherency), it is natural to instead compare different partial solutions and vote for the most promising one. This is similar in spirit to a "step-wise" celf-consistency strategy, i.c. cast "which state to explore" as a multi-choice QA, and use LM samples to vote for it.
For both strategies, we could prompt the LM multiple times to aggregate the value or vote results to trade time/resource/costt for more faithful/robust heuristics.
Algorithm 1 ToT-BBS(r, Po, V,
Algorithm 2 (oT-DESSss,,,p)) G, k. V,T, vi)
Require: Input æ, LM pe. thought generator G()
Require: Current state 8, step I, LM pe. thought generator G() and size limit k, states evaluator VO, step limit T, threshold Eth if > T then record output G(pp, s, 1, end if
& size limit k states evaluator V(), step limit T. breadth limit b.
So f {z}
for t = 1, 1,.... ......Tda T do
Sy + {[s, =| I E St-1, 2t E G(pg, s, k)}
for s' E G(ppo... 8.)) do b sorted candidates if V(o. {s'))(s) > Uthres then & pruning DFS(s',t +t)
V. V(po, St)
S. + ma Eses Vi(s)
end for return G(pg. arg max (s),
end if end for
4. Search algorithm. Finally, within the ToT framework, one can plug and play different search algorithms depending on the tree structure. We explore two relatively simple search algorithms and leave more advanced ones (e.g. A* [T,, MCTS (2)) for future work:
(a) Breadth-first search (BFS) (Algorithm [ maintains set of the most promising states per step. This is used for Game of 24 and Creative Writing where the tree depth is limit (T' < 3), and initial thought steps can be evaluated and pruned to a small set (b S 5).
(b) hepth-first search (DFS) (Algorithm 2 explores the most promising state first, until the final output is reached (t > T), or the state evaluator deems it impossible to solve the problem from the current s (Vo {s)) S Uth for a value threshold Vn)). In the latter case, the subtree from s is prumed to trade exploration for exploitation. In both cases, DFS backtracks to the parent state of to continue exploration.
Conceptually, ToT has several benefits as a method for general problem-solving with LMs: (1) Gener- ality: 10, COT, CoT-SC, and self-refinement can be seen as special cases of ToT (i.e. trees of limited depth and breadth; Figure T). (2) Modularity. The base LM, as well as the thought decomposition, generation, evaluation, and search procedures can all be varied independently.
(3) Adaptability. Different problem properties, LM capabilities, and resource constraints can be accommodated. (4) Convenience. No extra training is needed. just a pre-trained LM is sufficient. The next section will show how these conceptual benefits translate to strong empirical performance in different problems.
4 Experiments
We propose three tasks that are hard even when sampling from the state-of-the-art language model, GPT-4 23), using standard 10 prompting chain-of-thought (CoT) prompting. We show how

---

Game 24
Creative Writing
5x5 Crosswords
Input
numbers (4 9 10 13)
random sentences
10 clues (h1. presented;.)
Output
An equation to reach 24
A passage 4 paragraphs
5x5 letters: SHOWN;
(13-9)(10-4)=24
ending in the 4 sentences
WIRRA; AVAIL; ...
Thoughts
intermediate equations (13-9=4 (left 104, 10- 4-6 (left 4,6); 4*6-24)
A short writing plan
Words to fill in for clues:
(I. Introduee a book that connects..)
(h1. shown; v5, naled; ...)
#ToT steps
5-10 (variable)
Table I: Task overview, Input, output, thought examples are in blue.
deliberate search in trees of thoughts (ToT) produces better results, and more importantly, interesting and promising new ways use language models solve problems requiring search planning. Unless otherwise stated, we perform experiments using a Chat Completion mode GPT-4 with a sampling temperature of 0.7.
4.1 Game of 24
Game of 24 is a mathematical reasoning challenge, where the goal is to use 4 numbers and basic arithmetic operations (+-*/) to obtain 24. For example, given input "4 9 10 13", a solution output could be "(10 4) (13 - 9) = 24"h
Input 9
(a) Propose Prompt
Thought Generation
[ore etampil)
9- Jef: 10 15)) 10-4-6 6left 6
Input:49 10 10
LM
nest steps:
[.more lines.)
13-6-7 1
13-944 Gat-4
Value Prompt
Thought Evaluation
Esalusts if given numbers can reach (sureliceyingossibb 4: 14. sure (more esamples) 10:313
[13 10) - wey to obtain 24 with these big rumbers. impossibie
LM
4+6-10
Figure 2: ToT in game of 24. The LM is prompted for (a) thought generation and (b) valuation.
Task Setup. We scrape data from 4nums.com which has 1,362 games that sorted from easy to hard by human solving time, and use a subset of relatively hard games indexed 901-1,000 for testing. For each task, we consider the output as success if it is a valid equation that equals 24 and uses the input numbers each exactly once. We report the success rate across 100 games as the metric.
Baselines. We use standard input-output (IO) prompt with 5 in-context examples. For chain-of- thought (CoT)) prompting, we augment each input-output pair with 3 intermediate equations, each operating on two remaining numbers. For example, given input "4 9 10 13", the thoughts could be (left: 24)". For each game, we sample IO and CoT prompting for 100 times for average performance. We also consider a CoT self-consistency baseline, which takes the majority output from 100 CoT samples, and an iterative-refine approach on top of an 10 sample for at most 10 iterations. At each iteration, the LM is conditioned on all previous history to "reflect on your mistakes and generate a refined answer" if the output is incorrect. Note that it uses groundtruth feedback signals about equation correctness.
"13 9= 4 (left: 4 10); 10 - 4 6 (left: 4 6); & 6 24
ToT Setup. To frame Game of 24 into ToT, it is natural to decompose the thoughts into steps, each an intermediate equation. As shown in Figure aaa), at each tree node, we exact the remaining numbers and prompt the LM to propose some possible next steps. The same "propose prompt" is used for all 3 thought steps, though it only has one example with 4 input numbers. We perform breadth-fire first search (BFS) in ToT, where at each step we keep the best = 5 candidates. To perform deliberate BFS in ToT, as shown in Figure b)) we prompt LM to evaluate each thought candidate as hanir//iayy/mmoosibllle with regard to reaching 24. The aim is to promote correct partial solutions that can be verdicted within few lookahead trials, and eliminate impossible partial solutions based on "too big/small" commonsense, and keep the rest "maybe". We sample values 3 times for each thought.
a),
"Experiments were done between May 5-16, 2023.
5

---

Method
Success
(a) Success rate with nodes visiled
(b) Samples failed at each step
10 prompt
7.3%
CoT
ToT (b=5)
CoT prompt
4.0%
0.6
0.6
CoT-SC (=100)
9.0%
ToT (ours) (b=1)
45%
0.4
0.4
ToT (ours) (b=5)
74%
10 Refine (k=10)
27%
0.2
1D (best k) COT (best k) (b=1...5)
0.2
10 (best
33%
CoT (best of 100)
49%
0.0
25
Correct
Table 2: Game of 24 Results.
Figure 3: Game of 24 (a) scale analysis (b) error analysis.
Results. As shown in Table 2 I0, CoT, and CoT-SC prompting methods perform badly on the task, achieving only 7.3%, 4.0%, and 9.0% success rates. In contrast, ToT with breadth of b already achieves success rate of 45%, while b = 5 achieves 74%. We also consider an oracle setup for IO/CoT, by calculating the success rate using best of l samples (1 S k S 100). compare 10/CoT (best of k) with ToT, we consider calculating the tree nodes visited per task in ToT across b b= 1 ....5. and map the success rates in Figure Ba). treating IO/CoT (best of kt) as visiting & nodes in a bandit. Not surprisingly. CoT scales better than IO, and best of 100 CoT samples achieve a success rate of 49%, but still much worse than exploring more nodes in ToT (b > 1).
Error analysis. Figure 3 breaks down at which step CoT and ToT samples fail the task, i.e. the thought (in CoT) or all b thoughts (in ToT) are invalid or impossible to reach 24. Notably, around 60% of CoT samples already failed the task after generating the first step, or equivalently, the first three words (e.g. "4 + 9*)) This highlights the issues with direct left-to-right decoding.
4.2 Creative writing
Next, we invent creative writing task where the input is 4 random sentences and the output should be a coherent passage with 4 paragraphs that end in the 4 input sentences respectively. Such a task is open-ended and exploratory, and challenges creative thinking as well as high-level planning.
Task setup. We sample random sentences from randomwordgeneratoo..oom form 100 inputs, and there is no groundtruth passage for each input constraint. As find that GPT-4 can follow the input constraints most of the time, we focus on evaluating passage coherency in two ways: using a GPT-4 zero-shot prompt to provide 1-10 scalar score, using human judgments to compare pairs of outputs from different methods. For the former, we sample scores and average them for each task output, and we find these 5 scores usually consistent, with standard deviation of around 0.56 on average across outputs. For the latter, we employ a subset of the authors in blind study to compare the coherency of CoT ToT generated passage pairs, where the order of passages is random flipped over 100 inputs.
Baselines. Given the creative nature of the task, both 10 and CoT prompts are zero-shot. While the former prompts the LM to directly generate a coherent passage given input constraints, the latter prompts the LM to first make brief plan then write the passage, i.e. the plan serves as the intermediate thought step. We generate 10 I0 and CoT samples per task. We also consider an iterative-refine (k 5) method on top of random I0 sample for each task, where the LM is conditioned on input constraints and the last generated passage to decide if the passage is already "perfectly coherent", and if not generate a refined one.
ToT setup. We build ToT with depth (and only intermediate thought step) - the LM first generates 5 plans and votes for the best one (Figure 4 then similarly generate k passages based on the best plan then vote for the best one. Here the breadth limit = 1, as only one choice is kept per step. A simple zero-shot vote prompt ("analyze choices below, then conclude which is most promising for the instruction") ") is used to sample 5 votes at both steps.
Results. Figure 5[a) shows average GPT4 scores across 100 tasks, where ToT (7.56) is deemed to generate more coherent passages than 10 (6.19) and CoT (6.93) on average. While such an automatic metric might be noisy. Figure 5(b) confirms the finding by showing that humans prefer ToT over CoT in 41 out of 100 passage pairs, while only prefer CoT over ToT 21 (other 38 pairs are found "similarly coherent"). Lastly, iterative-refine is more effective on this natural language task, where

---

Whkee cohwment panouage of short peragraphe The and venterte of penegraph aphh must ine 1. iach difficult to de hanostond you stond your hande It louught quard that space smelled sonred steat When she disntt guy who trying to pick herup she Fach per who known you hwss diffeenn perception who you
(a)
Input
ng language
Input
Plan 3-5
[b]
1, Intoddure end explain the techniique caing a hanchlard 2. Seiich to story about an antronead's uu first tame in
1. Introduurii ahoo to unsuusl self help book, mer dianing handktand as metappor for srrbeacing ci challrages 2, Discusa the unsepecied things learned from astronsudh dudts including the small of space 3. Describe a awamanis clover tactic avokiing unmeatted citendion as bar: Contampiiseo ow difforent per copoio is oncself can shope oness lcentity.
Plans
Plan1
space Describe iluutiin where woman cass sign lansuage to avoid unia rsed utber tion 4, The rinall parograph explains how everyone has diftorent percopcoens of others
Passage
Passage
0/5 wobee
Anceysing
incorponnting requi paregrapt Choice offees parspet boack's
Votes
paregraphs
Figure 4: A step of deliherate search in randomly picked Creative Writing task. Given the input, the LM samples 5 different plans, then votes 5 times to decide which plan is best. The majority choice is used consequently write the output passage with the same sample-vote procedure.
(a) GPT-4 coherency scores
(b) Human coherency comparison
Method
Success Rate (%)
Letter Word Game
I0 CoT
38.7
14
0
40.6
15.6
20
38
41
ToT (ours)
78
60
20
+best state
82.4
67.5
35
10
21
-prune
65.4
41.5
5
backtrack
54.6
20
CoT
erefine treline
CoT ToT Simiar ToT CoT
Table 3: Mini Crosswords results.
Figure 5: Creative Writing results.
it improves 10 coherency score from 6.19 to 7.67, and ToT coherency score from 7.56 to 7.91. We believe it could be thought of as third approach thought generation in the ToT framework, where new thoughts can arise from refining old thoughts instead of i.i.d. or sequentially generated.
4.3 Mini crosswords
In Game of 24 and Creative Writing, ToT is relatively shallow most 3 thought steps needed to reach the final output. Here we explore x mini crosswords as a harder search problem involving natural language. Again, the goal is not just solve the task, more general crosswords can be readily solved with specialized NLP pipelines
(34) that leverages large-scale retrieval instead of LM. Rather, aim explore the limit of LM general problem solver that explores its own thoughts and guides its own exploration with deliberate reasoning as heuristics.
Task setup. We scrape data from GooBix which contains 156 games of 5 5 mini crosswords. As we observe adjacent games contain similar clues, we use 20 games with indices 1, .,, 91, 96 for testing, and games 136, 141, 146, 151, 156 for prompting. For each task, the input describes the horizontal clues and 5 vertical clues, and the output should be a board of 5 x 25 letters to solve the crosswords. For evaluation, consider three levels of success: the portion of correct letters (25 per game), words (10 per game), and games.
Baselines. We provide example input-output pairs in the 10 prompt, and in the CoT prompt additionally include intermediate words in the order hl..5 then vl.55. We run each prompt for 10 samples and average the results.
ToT setup. We leverage depth-first search (Algorithm 2 that keeps exploring the most promising subsequent word clue until the state is no longer promising, then backtrack to the parent state to explore alternative thoughts. To make search tractable, subsequent thoughts are constrained not to change any filled words or letters, so that the ToT has at most 10 intermediate steps. For thought generation, at each state we translate all existing thoughts (e.g. "h2.motor; hl al.tksss" for the state in Figure af)) into letter constraints for remaining clues (e.g. "vl.To heap: tm ....") and prompt a proposal prompt 5 times to come up with candidates for where and what to fill in the next word. Importantly, we also prompt the LM to give confidence level for different thoughts, and aggregate
7

---

tasks motor
Input Clues
(o]
DES
Thought Proposals
Order
salon
h2.motor
h4, salon (sure)
aggregake
h4. salon
srdry (law)
hå. grand
v3 string (high)
v3. string
h1.tasks
(b)
[aactrack
State Evaluator
clue)
v3. Pretentious, Flowery
sure
h3.grand
h4.salon
vi. To heap: tm
impossible
subtree pruned)
v5. Desiccator, more drycsr_n, nr_ (-) maybe
Figure 6: In Mini Crosswords, (a) how thoughts are proposed and aggregated in a priority queue for depth-first search (DFS), and (b) how state is evaluated based the possibility of filling in each remaining word clue, and pruned if any remaining clue is deemed not possible to fill by the LM. Then DFS backtracks the parent state and explore the next promising thought for clue.
these across proposals obtain sorted list of next thoughts explore (Figure ( For state evaluations, we similarly translate each state into letter constraints for remaining clues, then evaluate for each clue if is possible to fill given the constraints. If any remaining clue is deemed "impossible" to fill in (e.g. "vl. To heap: tm_s_"), then the exploration of the state's subtree is pruned and DFS backtracks to its parent explore the next promising thought. We limit DFS search steps 100, and simply render the deepest explored state (the first explored one if multiple) into the final output.
Results. As shown in Table 3 IO and CoT prompting methods perform poorly with word-level success rate less than 16%, while ToT significantly improves all metrics, achieving a word-level success rate of 60% and solving 4 out of 20 games. Such an improvement is not surprising, given IO and CoT lack mechanisms to try different clues, make changes to decisions, or backtrack.
Oracle and ablation studies. When outputting from the oracle best DFS state (instead of the heuristically determined best state) per task, ToT performance is even higher and actually solves 7/20 games (Table 3 "+best state"), indicating our simple output heuristics can be readily improved. Interestingly, sometimes when the crosswords game is actually solved, the state evaluator might still deem some words as "impossible" and prune possibly because 5 5 crosswords by design have some rare or obselete words that GPT-4 cannot recognize] Given the state evaluation as a pruning heuristic is imperfect, (Table 3 "-prune"). However, it could actually find the correct solution for 4/20 games (though only outputting via heuristic), 3 of which are games ToT+puunngg cannot solve within 100 steps. Thus, better heuristics for DFS pruning are critical for problem solving in this case. Lastly, we confirm the importance of backtracking by running ablation that keeps filling the most promising clue for at most 20 steps, allowing overwrites. This is similar to a "greedy" BFS search with breadth limit of b 1, and performs poorly with word level success of only 20% (Table 3 "-backtrack").
also explore ablating the pruning. and find the performance generally worse
5 Related Work
Planning and decision making. Smart planning and decision making are critical to achieving predefined goals. As they trained vast amount of world knowledge and human examples, LMs are known to have already absorbed rich commonsense that makes possible to propose reasonable
plans conditioned proposed ToT approach extends existing planning formulations by considering multiple potentially feasible plans simultaneously at each problem-solving step, and proceeding with the most promising ones. The integration between thought sampling and value feedback organically integrates planning and decision-making mechanisms, enabling effective search inside solution tree. On the other hand, traditional decision-making procedures usually require training dedicated reward and policy models as in reinforcement learning (for example CHAI (33). whereas we use the LM itself to provide the value estimates for decision making. RAP 9 is a concurrent work that treats language model
problem setting and environmental states 12
42
37
13
35
40 Our
For example, "agend" is an obsolete form of "agendum",, but GPT-4 deems it a typo for "agenda". External retrieval or web interaction could augment LM for problem solving under knowledge uncertainty.
8

---

reasoning as planning with its internal world model, and proposes MCTS- based method similar to ToT. However, its tasks are simpler than ours, and its framework lacks the modularity to incorporate different tree search algorithms.
Using LLMs to assess the viability of their own predictions is becoming in- creasingly important procedure in problem solving. [28 20 24 introduced the "self-reflection" mechanism, in which LMs provide feedback to their generation candidates. 4 improves LMs code generation accuracy by injecting feedback messages generated by the LM itself based on its code execution results. Similarly. [77] also introduces "critic" or review steps over the actions and states, deciding the next action to take in solving computer operation tasks. Another recent work very relevant to ours is "self-eval guided decoding" [39]. Similar our method, self-eval decoding also follows a tree-search procedure with leaves sampled from stochastic beam search decoding, which are then evaluated by L.LM itself with carefully prepared self-eval prompts. Their approach however, uses the PAL formulation [8] which represents thoughts as codes, which makes it difficult to tackle challenging tasks like creative writing which we consider in this paper. Our Tree-of- Tree-of-Thought formulation is thus more versatile and handles challenging tasks which GPT-4 only achieves very low accuracy with standard prompts.
Self-reflection.
Program-guide LLM generation. Our proposal is also related to recent advancements that organize LM's behavior with systematic procedures [1
4 or symbolic program guidance. For example, Schlag et al. [27] embeds LMs in an algorithmic search procedure to help solve problems like question answering step-by-step, in which the search trees are expanded by relevant paragraphs that might provide answers. This approach however differs from ours in that trees are expanded by sampling external paragraphs instead of the LM's own thoughts, and there is no reflection or voting steps. Another approach, LLM+P [18. goes one step further and delegates the actual planning process to classical planner.
Classical search methods. Last but not least, our approach can be treated as a modern rendition of classical search methods for problem solving. For example can be considered as heuristic search algorithm like A* [10), in which the heuristic at each search node is provided by the LM's self- assessment. From this perspective, our method is also related to NeuroLogic A *esque decoding [19]. which is inspired by A search but introduces look-ahead heuristics that are efficient for LMs to improve the beam-search or top-k sampling decoding. This method however constrained to sentence generation tasks, whereas our framework are designed for complex, multi-step problem solving guarded by value feedback.
6 Discussion
Limitations and future directions. Deliberate search such as ToT might not be necessary for many existing tasks that GPT-4 already excels at (see Appendix B.II. and as an initial step this work only explores three relatively simple tasks that challenges GPT-4 (see Appendix B.2 for some GPT-3.5 experiment results) and calls of better search and planning abilities incorporated with LMs. However, as we begin to deploy LMs for more real-world decision making applications (e.g. coding, data analysis, robotics, etc.), more complex tasks could emerge and present new opportunities to study these research questions. Also, search methods like ToT requires more resources (e.g. GPT-4 API cost) than sampling methods in order to improve task performances, but the modular flexibility of ToT allows users to customize such performance-cost tradeoffs, and ongoing open-source efforts (32 should readily reduce such costs in the near future. More details about cost and efficiency are in Appendix B.3 Lastly, this work focuses on using an off-the-shelf LM, and fine-tuning LMs using ToT-style high-level counterfactual decision making (c.g. deliberating over potential choices for the next paragraph, instead of predicting the next token) might present opportunities to enhance the problem-solving capabilities of LMs.
Conclusion. The associative "System 1 of LMs can be beneficially augmented by a "System 2" based on searching a tree of possible paths to the solution to problem. The Tree of Thoughts framework provides a way to translate classical insights about problem-solving into actionable methods for contemporary LMs. At the same time, LMs address a weakness of these classical methods, providing a way to solve complex problems that are not easily formalized, such as creative writing. We see this intersection of LMs with classical approaches to AI as an exciting direction.

---

Broader Impact
ToT is framework that empowers LMs to more autonomously and intelligently make decisions and solve problems, While current tasks are limited to reasoning and search problems, future applications involving interaction with external environments or humans could bring potential danger, e.g. facilitating harmful uses of LMs. On the other hand, ToT also improves the interpretability of model decisions and the opportunity for human alignment, as the resulting representations are readable, high-level language reasoning instead of implicit, low-level token values.
Acknowledgements
SY and KN acknowledge support from Oracle Collaborative Research award and the National Science Foundation under Grant No. 2239363. Any opinions, findings, conclusions, or recommenda- tions expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. SY is also supported by the Harold W. Dodds Fellowship from Princeton.
References
[1] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
[2] C. Browne, E. J. Powley, D. Whitehouse, S. M. M. Lucas, P. Cowling, P. Rohifshagen, S. Tavener, D. Liebana, S. Samothrakis, and S. Colton. survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and Al in Games, 4:1 211-43,222 2012.
[3] M. Campbell, A. J. Hoane Jr, and F-hh Hsu. Deep blue. Artificial intelligence, 134(1-2):57-85) 2002.
[4] X. Chen, M. Lin, N. Schärli, and D. Zhou. Teaching large language models to self-debug, 2023.
[5] A. Chowdhery, S. Narang, J. Devlin, M. Bosma, G. Mishra, A. Roberts, P. Barham, H. W. Chung, C. Sutton, S. Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311, 2022.
[6] A. Creswell and M. Shanahan. Faithful reasoning using large language models. arXiv preprint arXiv:2208. 14271, 2022.
[7] N. D. Daw, Y. Niv, and Dayan. Uncertainty-basee competition between prefrontal and dorsolateral striatal systems for behavioral control. Nature neuroscience, 1(12)1170411111, 2005.
[8] L. Gao, A. Madaan, S. Zhou, U. Alon, P. Liu, Y. Yang, J. Callan, and G. Neubig. Pal: Program- aided language models, 2023.
[9] S. Hao, Y. Gu, H. Ma, J. Hong, Z. Wang, D. Z. Wang, and Z. Hu. Reasoning with language model is planning with world model. arXiv preprint 2355:22305.1992, 2023.
[10] E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100-107, 1968. doi: 10.1009//SC...98. 3000133
[11] E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2):100-107, 1968.
[12] W. Huang, Abbeel, D. Pathak, and Mordatch. Language models as zero-shot planners: Extracting actionable knowledge for embodied agents, 2022.
[13] W. Huang, F. Xia, T. Xiao, H. Chan, J. Liang, P. Florence, A. Zeng. J. Tompson, I. Mordatch, Chebotar, et Inner monologue: Embodied reasoning through planning with language models. arXiv preprint arXi::2007.05608 2022.
10

---

[14] J. Jung. L. Qin. S. Welleck, F. Brahman, C. Bhagavatula, R. L. Bras, and Y. Choi. Maieu- tic prompting: Logically consistent reasoning with recursive explanations. arXiv preprint arXiv:2205. /822, 2022.
[15] D. Kahneman. Thinking, fast and slow. Macmillan, 2011.
[16] D. Kahneman, S. Frederick, et al. Representativeness revisited: Attribute substitution in intuitive judgment. Hearistics and biases: The psychology intuitive judgment,, 49(49-81):74, 2002.
[17] G. Kim, P. Baldi, and S. McAleer. Language models can solve computer tasks, 2023.
[18] B. Liu, Y. Jiang, X. Zhang, Q. Liu, S. Zhang, J. Biswas, and P. Stone. Llm+p: Empowering large language models with optimal planning proficiency, 2023.
[19] X. Lu, S. Welleck, P. West, L. Jiang, J. Kasai, D. Khashabi, R. L. Bras, L. Qin, Y. Yu, R. Zellers, N. A. Smith, and Y. Choi. Neurologic e*esque decoding: Constrained text generation with lookahead heuristics, In North American Chapter of the Association for Computational Linguisticx, 2021.
[20] A. Madaan, N. Tandon, P. Gupta, S. Hallinan, L. Gao, S. Wiegreffe, U. Alon, N. Dziri, Prabhumoye, Yang. S. Welleck, P. Majumder, Gupta, A. Yazdanbakhsh, and P. Clark. Self-refine:
Iterative refinement with self-feedback, 2023.
[21] A. Newell, J. C. Shaw, and A. Simon. Report on general problem solving program. In IFIP congress, volume 256, page 64. Pittsburgh, PA, 1959.
[22] A. Newell, H. Simon, al. Human problem solving. Prentice-Hall, 1972.
[23] OpenAL. Gpt-4 technical report. ArXiv, abs/2303.08774, 2023.
[24] D. Paul, M. Ismayilzada, M. Peyrard, B. Borges, A. Bosselut, R. West, and B. Faltings. Refiner: Reasoning feedback on intermediate representations, 2023.
[25] A. Radford, K. Narasimhan, T. Salimans, I. Sutskever, et al. Improving language understanding by generative pre-training OpenAl blog. 2018
[26] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, I. Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
[27] I. Schlag, S. Sukhbaatar, A. Celikyilmaz, W. tau Yih, J. Weston, J. Schmidhuber, and X. Li. Large language model programs, 2023.
[28] N. Shinn, B. Labash, and A. Gopinath. Reflexion: an autonomous agent with dynamic memory and self-reflection, 2023.
[29] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, et al. Mastering the game of go without human knowledge. nature, 550 (7676):354-35, 2017.
[30] S. A. Sloman. The empirical case for two systems of reasoning. Psychological bulletin, 119(1): 3, 1996.
[31] K. E. Stanovich. Who is rational? Studies of individual differences in reasoning. Psychology Press, 1999.
[32] H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro, F. Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint 2302.1330,,,3 2023.
[33] Verma, J. Fu, S. Yang, and Levine. Chai: chatbot for task-oriented dialogue with offline reinforcement learning. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 4471 1491, 2022.

---

[34] E. Wallace, N. Tomlin, A. Xu, K. Yang, E. Pathak, M. Ginsberg, and D. Klein. Automated crossword solving. arXiv preprint (tt.:220500966.33 2022.
[35] L. Wang, W. Xu, Y. Lan, Z. Hu, Lan, R. K.-W. Lee, and E.-P. Lim. Plan-and-solve prompting: Improving zero-shot chain-of-thought reasoning by large language models, 2023.
[36] X. Wang, J. Wei, D. Schuurmans, Q. Le, E. Chi, and D. Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2233.11171, 2022.
[37] Z. Wang, S. Cai, A. Liu, X. Ma, and Y. Liang. Describe, explain, plan and select: Interactive planning with large language models enables open-world multi-task agents, 2023.
[38] Wei, X. Wang, D. Schuurmans, M. Bosma, Chi, Q. Le, and Zhou. Chain of thought prompting elicits reasoning in large language models. arXiv preprint 2XXi::201.119000 2022.
[39] Y. Xie, K. Kawaguchi, Y. Zhao, X. Zhao, M.-Y. Kan, J. He, and Q. Xie. Decomposition enhances reasoning via self-evaluation guided decoding, 2023.
[40] S. Yang, O. Nachum, Y. Du, J. Wei, P. Abbeel, and D. Schuurmans. Foundation models for decision making: Problems, methods, and opportunities, 2023.
[41] S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y. Cao. ReAct: Synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.03629, 2022.
[42] S. Zhang, Z. Chen, Y. Shen, M. Ding, J. B. Tenenbaum, and C. Gan. Planning with large language models for code generation. In The Eleventh International Conference on Learning Representations, 2023. URL htt.hhtts://// httpps::/ppenreiieeee
[43] D. Zhou, N. Schärli, L. Hou, J. Wei, N. Scales, X. Wang, D. Schuurmans, C. Cui, O. Bousquet, Q Le, et Least-to-most prompting enables complex reasoning in large language models. arXiv preprint 2:X2v:2205.10625, 2022.
[44] X. Zhu, J. Wang. L. Zhang. Y. Zhang, R. Gan, J. Zhang, and Y. Yang. Solving math word problem via cooperative reasoning induced language models. arXiv preprint arXiv:2210.16257, 2022.
12

---

A Code, Prompts, Trajectories
All code is available at http:///ghhhtbccooopppeeeeeeerrr
All prompts are httpa//w..ppppp//...oooooooooooa hieee//aatter//cc//o//rroooooo
at
11m/
Trajectories are available at https://gghhhboooo/////oooootott wtwp:uurtttoottuuuuttt--------
tree/master/logs
B
Additional Experiment Results
Given the motivation of exploring and extending the capability frontier of language models, our experiments in the main paper have focused on a setup with the state-of-the-ar language model (GPT-4), and three hard tasks invented challenge it. Here, we report additional experiments with weaker LLM or easier tasks, and discuss cost and efficiency.
GSM8K
Strategy QA
GPT-4
GPT-3.5
GPT-4
GPT-3.5
10
73
7.3%
10
6.19
4.47
CoT
86
82
CoT
4.0%
3%
CoT
6.93
5.16
ToT
90
83
ToT 74%
19%
ToT
7.56
6.62
Table New tasks with zero-shot ToT and GPT-4.
Table 5: Game of 24 with GPT-4 vs GPT-3.5.
Table 6: Creative Writing with
GPT-4 vs. GPT-3.5.
B.1 Extension to new tasks (GSM8k, Strategy QA) with zero-shot ToT
While more common NLP tasks might be easy for GPT-4 and do require ToT (which is why we considered harder new tasks), we believe applying ToT to new tasks could be straightforward. For example, implemented simple and generic zero-shot ToT-BFS similar creative writing (sample 5 problem solving strategies then vote for the best one; then sample solutions based on the best strategy then for the best one) for GSM8K and StrategyQA with few extra lines of code:
define the answer format of new tasks asm8k_format = ""the answer is n" where is number' strategyga_ 'either "the answer is yes" or "the answer no"
define zero-shot prompting
standard_promps 'Answer the following question with {formath: [input}}
iefine thought format for zero-shot cot and zero-shot tot cot_prompt '' Ansser the following question: (input}
Make a strategy then write. Your output should be of the following format:
Strategy:
Your strategy about how
the question.
Answer:
Your ansver to the question. It should end with (format).
define zero-shot voting used for zero-shot tot vote_prompt ('vvveen an instruction and several choices, decide which choice is most promising.
Analyze each choice in detail, then conclude in the last line "The best choice { where s the integer the choice.
13

---

We evaluated on a subset of 100 random GSM8K test and StrategyQA dev questions. As shown in Table and as expected. ToT improves over CoT on both tasks (but only slightly, given GPT-4 + CoTT is already very good on such tasks, and StrategyQA's bottleneck is external knowledge, not reasoning). Considering computational costs, it is more suitable try smaller L.MSs + ToT for traditional NLP tasks, or GPT44 + ToT for hard tasks that challenge GPT-4 + CoT's reasoning.
B.2 Extension to new LMs (GPT-3.5)
To understand how ToT works with other LLMs, also GPT-3.5-turbo for Creative Writing ( and Game 24 (Table 3). On both tasks, "ToT > CoT > 10" remains true for GPT-3.5. On Creative Writing, we find TPT outperform GPT-4+1O, and similar to GPT-4+CoT, which suggests ToT could also work well on weaker language models.
On Game of 24 (we changed 1-shot proposal prompt to 3-shot make it work), GPT-3.5+ToT's 19% far worse than GPT-4+ToT's 74%. To further understand the importance of generation vs. evaluation, we ran GPT-4 generation GPT-3.5 evaluation (64%) and GPT-3.5 generation + GPT-4 evaluation (31%). This suggests the game's 's bottleneck is thought generation, and different generation/evallutioon language models might attain decent results while reducing costs.
B.3 Cost and efficiency
Running ToT requires significantly more computations than IO or CoT prompting. For example, in Game of 24 (Table beloow,, solving problem with ToT requires 5.5k completion tokens, close to 100 CoT trials (6. 7k tokens). But the performance of ToT is better than best of 100 independent CoT trials.
Game of 24
Generate/Prompt tokens
Cost per case
Success
10 (best of 100)
1.8k 1.0k
$0.13
33%
CoT (best of 100)
6.7k 2.2k
$0.47
49%
ToT
5.5k 1.4k
$0.74
74%
Table 7: Cost analysis on Game of 24.
On Creative Writing (Table below), we found ToT takes around 5x completion tokens and money cost, which is intuitive as 5 and most tokens are generated passages.
Creative Writing
Generate/Prompt tokens
Cost per case
10
0.9k / 0.4k
$0.06
CoT
0.9k / 0.4k
$0.07
ToT
4k 2.9k
$0.32
Table 8: Cost analysis on Game of 24.
So completing Game of and Creative Writing's main ToT experiments cost around 0.74 x 100 0.32 x 100 106 dollars. Crosswords' DFS experiments should be also within 100 dollars. In general, cost and efficiency of ToT highly depend on the prompts and search algorithms used, and could require 5-100 times more generated tokens than COT. Some actionable insights:
We recommend using ToT on tasks requiring deliberate reasoning, on which CoT struggles.
Flexibility of ToT allows some performance-cost tradeoff, c.g., change beam size or vote number in BFS, few-shot vs. zero-shot prompting, GPT-3.5 vs. GPT-4, etc. One could configure the setup based on some resource constraints or performance goal.
There much space for improving efficiency, e.g., BFS could early stop when solution is found, trim down beam size when some thoughts are "impossible".
We believe that more computation is indeed required in order for the model to achieve stronger intelligence, and this should not become a blocking issue as in the long run, (open- source) LMs will become much cheaper and more efficient. also a great direction how to better train/finetune LMs for thought generation and/or evaluation.
14


Reviews:
[{"review_id": "AP2fL2i4ea", "reviewer": "Reviewer_ysyd", "summary": "This paper introduces a new method for prompting large language models (LLMs) for multi-step reasoning tasks. Existing prompting methods are confined to the autoregressive generation scheme, making it difficult for LLMs to finish tasks that require exploration and planning. To alleviate this problem, the authors propose Tree of Thought (ToT), which combines the chain-of-thought (CoT) method with tree-based search.  By prompting LLMs to solve the intermediate step and using the self-evaluations as the heuristics, one can effectively leverage LLMs to finish tasks that require exploration and backtracking. Empirical evaluations on three novel tasks demonstrate the effectiveness of the proposed method.", "questions": "Please see the weakness above.", "limitations": "The authors discussed the limitations and potential negative social impact of their work ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- A novel method to combine LLMs with tree-based search. The proposed method alleviates the shortcoming of directly prompting LLMs to generate answers for some tasks that require explorations and backtracking. Compared to CoT prompting which can only sample one solution path, ToT allows LLMs to explore more potential solutions and find the best one.\n- Automatic and independent reasoning process. ToT fully depends on the LLMs to generate plans, finish intermediate steps, and generate self-evaluation for the current state as heuristics. Without the dependence on external tools or models, ToT enables LLMs to automatically finish complex tasks.", "weaknesses": "More application scenarios. The authors mainly evaluate ToT on the three novel tasks that require exploration and backtracking. It would be better to demonstrate whether ToT can help improve LLMs on commonly-used reasoning tasks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for endorsing our work!\n\n### 1. More application scenarios\n\nThis is a great point. Please check **General Response (1)**, where we show a very simple scheme to apply ToT in common NLP tasks (StrategyQA, GSM8K). However, such tasks might not need GPT-4 + ToT as GPT-4 + COT suffices --- weaker LLMs + ToT could potentially outperform weaker LLMs + CoT and could be studied on such tasks."}, {"review_id": "4wo8DsB7PJ", "reviewer": "Reviewer_fAU5", "summary": "The paper presents a new framework for language model inference called Tree of Thoughts, which aims to improve the ability of language models to solve complex, multi-step problem-solving tasks. \n\nThe framework involves generating a tree of possible plans for solving a given task, with each node in the tree representing a possible step in the plan. The language model then evaluates each node based on its own self-assessment, and the tree is expanded by sampling external paragraphs to generate new nodes. The framework also includes a voting step to determine the best plan to follow. \n\nThe paper argues that this approach is more effective than previous methods for prompting language models, such as Chain of Thought, and can be seen as a modern rendition of classical search methods for problem-solving. The contributions of the paper include a detailed description of the Tree of Thoughts framework, an evaluation of its effectiveness on a range of problem-solving tasks, and a discussion of its potential limitations and future directions for research.\n", "questions": "I raised multiple questions in the weakness section, and I hope the authors could further clarify them. Specifically, some can be reformualted as follows:\n1. How hard is it to apply the proposed method to a more general NLP reasoning dataset, like GSM8K or StrategyQA, or other well-known datasets? If possible, I hope the authors could demonstrate one case using the proposed method to solve a more general task. \n2. How necessary the GPT-4 is in the proposed framework? It seems GPT-4 is very powerful for self-evaluation, and how critical is this component for the success of the tasks?", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The idea of upgrading chain-of-thoughts into tree-of-thoughts seems to be an intuitive extension and necessary step. There are many benefits of tree reasoning, including the ability to look ahead and backtrack to search for better traces. \n2. The formulation of heuristics leverages the recent self-evaluation ability of GPT-4 to reuse the LLM to evaluate the quality of states via prompting. This relieves the necessity of training accurate state values and enables approximate estimation.\n3. The empirical results on three tasks demonstrate the effectiveness of ToT compared with GPT-4 based baselines. The improvement gain is quite large on two tasks, considering GPT-4 based CoT methods don't work well on them.", "weaknesses": "1. Unsurprisingly, the idea of extending linear reasoning to tree reasoning isn't a new thing. Specifically, [1] leverages beam search to guide the chain-of-thought to decode a better reasoning path, which is almost the same as the BFS in this paper. [1] also uses self-evaluation to provide heuristics. [2] also formulates the reasoning as a tree reasoning problem. More importantly, the application of BFS and DFS seems to be ad-hoc, and there could be more principled methods to guide the search. For example, [3, 4] applies MCTS to guide the search, which might have better planning abilities.\n2. While ToT improves CoT naturally, it doesn't come without cost. One major concern is the efficiency issue for querying the expensive GPT-4 multiple times. The paper should give the audience a clearer idea of how cost ToT is compared with CoT, probably with an efficiency comparison between them. More interestingly, the paper should propose or at least discuss potential means to reduce the inference cost, such as using various smaller models for sampling or state evaluation, etc.\n3. The application scope is largely limited. While the authors say they select the three tasks because they are hard, the selected three tasks are arguably narrow with two text games. One possible reason is that the selected tasks make the thought and state formulation easier and demonstrate improvement significantly. Nonetheless, it would be necessary to extend the scope to be more similar to CoT tasks to demonstrate the broader applicability of the proposed methods. \n\n[1]. Xie, Yuxi, et al. \"Decomposition enhances reasoning via self-evaluation guided decoding.\" arXiv preprint arXiv:2305.00633 (2023).\n[2]. Jung, Jaehun, et al. \"Maieutic prompting: Logically consistent reasoning with recursive explanations.\" arXiv preprint arXiv:2205.11822 (2022).\n[3]. Zhu, Xinyu, et al. \"Solving math word problem via cooperative reasoning induced language models.\" arXiv preprint arXiv:2210.16257 (2022).\n[4]. Hao, Shibo, et al. \"Reasoning with language model is planning with world model.\" arXiv preprint arXiv:2305.14992 (2023).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThank you for your thoughtful comments, all of which are very helpful for improving our work!\n\n### 1. Related work and BFS/DFS vs. MCTS\nThank you for pointing out these recent or concurrent papers related to ToT. We will discuss them in our related work section.\n\nWe used BFS and DFS as they are the simplest tree search algorithms that turn out general and effective enough for the studied tasks. Due to the modularity of the ToT framework, application of more advanced algorithms such as MCTS or A* for harder tasks is a clear and promising future direction.\n\n### 2. Cost and potential means to more efficiency\nThese are great points. Please see **General Response (3)**.\n\n### 3. Extend the scope to more CoT tasks\nPlease see **General Response (1)**, where as per your suggestion, we show a very simple scheme to extend ToT to StrategyQA and GSM8K. \n\n### 4. Importance of GPT-4\nPlease see **General Response (2)**."}, {"review_id": "wWbjRdJvjt", "reviewer": "Reviewer_3c3c", "summary": "This paper proposes Tree of Thoughts to promote deliberate problem solving with LLMs. By using a tree-based structure and a four-step process towards problem solving, tree of thoughts successfully address many of the challenges with left-to-right decoding such as looking ahead, backtracking, considering multiple reasoning paths at the same time, and more. Extensive experiments on three reasoning tasks demonstrate the superiority of Tree of Thoughts over ICL, CoT, self consistency, and more.", "questions": "please see above", "limitations": "Limitations are discussed in Section 6.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ the Tree of Thoughts approach is well motivated by the limitations of autoregressive decoding\n+ the four-step formulation is novel and clearly described\n+ experiments on three reasoning tasks are extensive and convincing", "weaknesses": "Overall I like this work and I only have a few comments.\n\n- I wonder if it might be possible to discuss the efforts required to adapt Tree of Thoughts to other tasks and reasoning formats. To me, it seems like other than the search algorithm (BFS/DFS), the other three parts would require some hand-crafted engineering from scratch for a different task.\n\n- I wonder if least to most [1] or decomposed prompting [2] might be possible baselines for the three tasks: they also discuss some sort of iterative problem solving potential.\n\n- In the \"Game of 24\" task, does the base LLM make arithmetic mistakes? If that's the case, would using tool learning strategies [3] further improve Tree of Thoughts in numeric reasoning tasks?\n\n- The supplementary material does not seem to contain an appendix, while some details might be helpful. For example, what is the prompt for GPT-4 zero-shot evaluation in line 213? What are the details of human evaluation for \"Creative Writing\"? (annotator head count, compensation, etc.) Also, it is increasingly common to present all the prompt texts in the appendix to facilitate reproducibility. I wonder if the authors might consider having an appendix to systematically document all details about the approach and experiments.\n\n[1] Zhou, Denny, et al. \"Least-to-Most Prompting Enables Complex Reasoning in Large Language Models.\" The Eleventh International Conference on Learning Representations. 2022.\n\n[2] Khot, Tushar, et al. \"Decomposed Prompting: A Modular Approach for Solving Complex Tasks.\" The Eleventh International Conference on Learning Representations. 2022.\n\n[3] Schick, Timo, et al. \"Toolformer: Language models can teach themselves to use tools.\" arXiv preprint arXiv:2302.04761 (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThank you for finding our work \"well-motivated\", \"novel\", \"clearly described\", and \"convincing\".\n\n### 1. Adapt ToT to other tasks.\n\nThis is a great question. Please see **General Response (1)**, where we show a simple scheme that adapts ToT to StrategyQA and GSM8K with near-zero task-specific hand crafting.\n\n### 2. Least-to-most or decomposed prompting\n\nWe think they might not be effective baslines for our studied tasks, where initial decisions (e.g. first step of game of 24, or first filled word in crosswords) are critical and require exploration. Methods like least-to-most or decomposed prompting might help with compositional generalization via task decomposition, but do not have a way to explore and maintain different decomposition plans. So once the first step is generated wrong, they might fail similarly as CoT. \n\n### 3. Arithmetic mistake and tool use\n\nIn Game of 24, numbers are usually within 50, and GPT-4 rarely makes arithmetic mistakes (weaker models like GPT-3.5 make more mistakes). \n\nAs hinted in Page 8's footnote, we agree it is a great idea and important future direction to enhence ToT with external tool use! We probably need some better and harder tasks that require exploration of both reasoning and acting.\n\n### 4. Appendix\n\nThank you for the reminder! We will include additioanl experiment details and all prompts used in the appendix.\n"}, {"review_id": "f0up3qWEK5", "reviewer": "Reviewer_sEEP", "summary": "The paper introduces an innovative concept of problem-solving that utilizes a tree-like structure of thoughts, constructed and evaluated by the LLM, specifically GPT-4. To illustrate the efficacy of this technique, the authors have incorporated three distinct tasks: the Game of 24, creative writing, and crossword puzzles. These tasks have been chosen as they require different capabilities to be solved. Several iterations of the tree-like structure of thoughts were examined, including those combined with Breadth-First Search (BFS) or Depth-First Search (DFS), along with other variations with different hyperparameters. A comprehensive comparison has been drawn with various other Language Learning Model-based baselines.", "questions": "Necessary things (either to address here or in the paper):\n- Figure 3b:  The title of the figure is “Samples failed at each step”, and there last two bars show success not failures (the one named “Correct”). It is misleading, I first thought that ToT failed mainly at the last step. Another problem with this comparison is that ToT with b=5 vs CoT seems unfair to me (ToT has many samples at each state while CoT does not - it is not surprising that CoT stands no chance). The better comparison would be for example: ToT vs  CoT-SC  or ToT vs CoT-best of 100.\n- In Table 2 and Figure 3 there is no information about the error estimation. It should be at least in text somewhere\nThe total cost of the experiments done during the work on this paper should be stated in the paper or in supplementary materials.\n- line 186. I would change \"left\" to \"remaining\" (numbers). For a while, I was wondering if left refers to \"left to do\" or \"left side\".\n- line 134: dot missing at the end of the sentence\n- Algorithm 2 and line 279: how exactly does the pruning work?\n- lines 222 to 225: Here you describe an iterative-refine method as a baseline. Would such a method be reasonable for baselines in Game of 24?\n\nSuggestions, ideas, and comments:\n-All the tasks presented here could be solved without ToT (and two of them even without LLM).  Maybe you have some intuition for what kind of problems ToT would be necessary? I know that this may be hard or even impossible to answer.\n- It would be very interesting to see a comparison of ToT based on GPT3.5 vs IO GPT4 or CoT GPT4. Can weaker LLM with ToT be stronger than Sota LLM? I think such an experiment would add great value to the paper.\n- The comment at the bottom of page 8 is very interesting\n\n\n\n", "limitations": "The limitations section is sound.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The value of examining the tree-like thinking process performed by LLM is evident to the scientific community. Primarily, the Tree of Thoughts (ToT) could be applicable to other tasks when adequately adapted and it provides an intriguing exploration of GPT-4's capabilities.\n\nThe paper intriguingly selects tasks requiring diverse skill sets:\n- The game of 24 demands fundamental mathematical capabilities and the ability to assess whether success is achievable from a partial solution.\n- Creative writing needs the generation of coherent and sound text under strict constraints.\n- Crossword puzzles necessitate linguistic knowledge and the capacity to search across a vast state space (large word sets that meet given constraints).\n\nThe authors have made a commendable effort to objectively assess the results, with blind tests of text coherency serving as a prime example. The elucidation of the method is lucid, with Figure 1 being particularly illuminating. Additionally, most experiments are presented in a comprehensible manner. A significant strength lies in ToT's performance, which significantly surpasses that of the baseline.\n\nI perceive this paper to be a successful proof-of-concept for ToT. Notably, its significance chiefly stems from the ongoing massive efforts aimed at leveraging LLM's capabilities. A prominent challenge in applying LLMs for deliberate problem solving", "weaknesses": "The biggest weakness of ToT is that the paper lacks the evaluation of some important properties of ToT. Here I put a list:\n\n1. There is no data about the price of ToT compared with baselines (there is a short mention in the Limitations about the price/success rate trade-off). In the best case, I would like to have a graph where there is a success rate on the y-axis and a price on the x-axis. If you think that such a graphical analysis would be too detailed please put some data in a table. The price of GPT-4 may be different in the future, so alternatively you can add information about the number of tokens used by ToT per solution compared with baselines. Probably the best would be to have both information: price and number of tokens. \n\n2. There is no data about the time execution of ToT compared with baselines.\n\nComment on 1. and 2. : Knowing the average price and time is very important for readers who consider building their own methods on top of ToT or consider applying ToT to their task. \n\n3. Some additional comparisons are missing. We know that a single execution of ToT is significantly more powerful than a single execution of baseline (for example IO). However is it possible that running IO or CoT many times (until it finds a solution) is actually cheaper and faster than ToT? ToT will still have scientific value even in the case where the answer to the previous question is positive, but the scientific community will benefit from knowing it. Currently, it is not really known what are the maximum capabilities of properly used LLM and how to maximize its performance. In a search for the most effective methods, we need to know as many properties of each approach as possible. Knowing more about ToT would add great value to the paper. Here is a list of my suggestions for additional comparisons:\n> How many times on average should I run a baseline to find a solution compared with ToT?\n> Can baseline be cheaper or faster than ToT even though it is weaker?\nIf it is impossible to gather detailed data for this comparison, please provide some estimates.\n\n4. While I see value in the creative writing task, I am not very convinced that a task with just one ToT step is meaningful when evaluating tree search algorithms. More precisely: while formally this task falls under the ToT framework, it's hard to think about it in terms of tree search. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThank you for your detailed and constructive feedback!\n\n### 1. Cost and efficiency\nThis is a great point. Please see **General Response (3)**.\n\n### 2. Running IO/CoT baselines many times\n\nWe showed Game of 24 IO/CoT best-of-k results in Table 2 and Figure 3, where CoT best-of-100 has a game success of 49%, which is still much worse than ToT's 74%. We also showed iterative refinement approaches for Game of 24 (Table 2) and Creative Writing (Figure 5). These findings suggest ToT might be a better way to spend more resources in hope to get better results for these tasks, compared with parallel sampling or iterative refinement. \n\n\n### 3. Creative Writing Steps\n\nWe note that the ToT for creative writing has two steps: plans are generated and evaluated, then passages are generated and evaluated based on the best plan. \n\n### 4. What tasks need ToT\n\nThis is a great question! Please see **General Response (1)**, where we show how easy it is to adapt ToT to more tasks. We think GPT-4+ToT is more suitable for hard tasks challenging GPT-4+CoT, while weaker LLMs+ToT can be used for simpler tasks.\n\n### 5. ToT with weaker LLMs\n\nPlease see **General Response (2)**.\n\n### 6. Other smaller questions\n\n- Figure 3b: thanks for the suggestion, we will remove last two \"success\" bars. The figure is not intended to contrast the performances of ToT over CoT, but rather to support the point that CoT mostly fails at the first step of Game of 24 due to the inherent problems of autoregressive decoding, thus exploration around initial decisions is crucial.\n\n- Table 2 and Figure 3: we did not include error estimation as the performance gaps are significant and running GPT-4 experiments are expensive. As detailed in **General Response (3)**, running ToT experiments on Game of 24 and Creative Writing cost around 100 dollars.\n\n- We will fix line 186 and 134, thanks for your careful reading!\n\n- DFS pruning: as stated in line 265-266, a state is pruned if LLM deems any remaining clue as \"impossible\" to fill in (e.g. To heap: tm_s_).\n\n- Iterative refine for Game of 24: We tried it, and as shown in Table 2's IO + Refine (k=10, which is already very expensive due to the culcumative context), it does help a bit, but the performance of 27% is still poor compared to ToT's 74%."}]

Author rebuttal:
We appreciate all reviewer's great feedback, which will significantly strengthen our draft!

The motivation of ToT is simple: **to explore and extend the capability frontier of autoregressive LLMs**. More specifically, given the SoTA LLM (GPT-4) can already solve many existing NLP tasks, what new tasks can raise new challenges? How can we augment LLMs to tackle these challenges? To this end, we contribute three new tasks for LLMs that challenge even GPT-4, and ToT as a framework to augment LLM's deliberate reasoning. **Our paper is thus focused on a setup with SoTA LLM (GPT-4) and hard tasks for it.** 

Here, we report new experiments with weaker LLM or easier tasks, and discuss cost and efficiency concerns.
 
### 1. New Experiments on Other (Easier) Tasks (ysyd, fAU5, 3c3c)

While more common NLP tasks might be too easy for GPT-4 and do not require ToT (which is why we considered harder new tasks), we believe **applying ToT to new tasks could be straightforward**. 
For example, we implemented a simple and generic zero-shot ToT-BFS similar to creative writing (sample 5 problem solving strategies then vote for the best one; then sample 5 solutions based on the best strategy then vote for the best one) for GSM8K and StrategyQA with few extra lines of code:

```python
gsm8k_format = '"the answer is n" where n is a number'

strategyqa_format = 'either "the answer is yes" or "the answer is no"'

standard_prompt = 'Answer the following question with {format}: {input}'

cot_prompt = '''
Answer the following question: {input}

Make a strategy then write. Your output should be of the following format:

Strategy:
Your strategy about how to answer the question.

Answer:
Your answer to the question. It should end with {format}.
'''

vote_prompt = '''Given an instruction and several choices, decide which choice is most promising. Analyze each choice in detail, then conclude in the last line "The best choice is {s}", where s the integer id of the choice.
'''
```

We evaluated on a subset of 100 random GSM8K test and StrategyQA dev questions. As shown below and as expected, ToT improves over CoT on both tasks (but only slightly, given GPT-4 + CoT is already very good on such tasks, and StrategyQA's bottleneck is external knowledge, not reasoning). Considering computational costs, it is more suitable to try smaller LLMs + ToT for traditional NLP tasks, or GPT-4 + ToT for hard tasks that challenge GPT-4 + CoT's reasoning.

|     | GSM8k  | StrategyQA |
| -------- | ------- |------- |
| IO  | 51    | 73    |
| CoT | 86     |  82   |
| ToT | 90    |  83    |

### 2. New Experiments on Other (Weaker) LLM (fAU5, sEEP)

To understand how ToT works with other LLMs, we also ran GPT-3.5-turbo for creative writing, which was reported in the supplementary material. **We find gpt-3.5+ToT outperform gpt-4+IO, and similar to gpt-4+CoT, which suggests ToT could also work well on weaker LLM.**

|Creative Writing| gpt-4 (in paper) | gpt-3.5 | 
|-----|-----|----|
| IO | 6.19| 4.47|
| CoT | 6.93| 5.16|
| ToT | 7.56| 6.62|

We also ran GPT-3.5 for Game of 24 (we changed 1-shot proposal prompt to 3-shot to make it work). Here, GPT-3.5+ToT's 19% is far worse than GPT-4+ToT's 74%.

|  Game of 24  | gpt-4 (in paper) | gpt-3.5 | 
| ---- | ---- |---- |
| IO  | 7.3    | 6    |  
| CoT | 4.0     | 3     |    
| ToT |  74  |  19    |  

To further understand the importance of generation vs. evaluation, we ran gpt-4 gen + gpt-3.5 eval (64%) and gpt-3.5 gen + gpt-4 eval (31%). This suggests the game's bottleneck is thought generation, and different gen/eval LLMs might attain decent results while reducing costs.

|  gen\eval | gpt-4 | gpt-3.5 | 
| ---- | ---- |---- |
| gpt-4  | 74    | 64    |  
| gpt-3.5 | 31     | 19     |    

### 3. Cost and efficiency (fAU5, sEEP)

Running ToT requires significantly more computations than IO or CoT prompting. For example, in game of 24, solving a problem with ToT requires 5.5k completion tokens, close to 100 CoT trials (6.7k tokens). But the performance of ToT is better than best of 100 CoT trials.

|  Game of 24 | completion tokens | prompt tokens | cost per case | success rate | 
| ---- | ---- |---- | ---- |  ---- |
| IO (best of 100) | 1.8k    | 1.0k   | $0.13 | 33% |
| CoT (best of 100) | 6.7k     | 2.2k     | $0.47 | 49%
| ToT | 5.5k    |  1.4k    | $0.74| 74% |

On Creative Writing, we found ToT takes around 5x completion tokens and money cost, which is intuitive as $b=5$ and most tokens are generated passages.

| Creative Writing   | completion tokens | prompt tokens | cost per case | 
| ---- | ---- |---- | ---- |
| IO  | 0.9k    | 0.4k   | $0.06 |  |
| CoT | 0.9k     | 0.4k     | $0.07 |
| ToT | 4k    |  2.9k   | $0.32 | 

So completing Game of 24 and Creative Writing's main ToT experiments cost around $0.74 * 100 + 0.32 * 100 = 106$ dollars. Unfortunately we did not record the usage for crosswords' DFS experiments, but it should be within 100 dollars. In general, cost and efficiency of ToT highly depend on the prompts and search algorithms used, and could require 5-100 times more generated tokens than CoT. 

Some actionable insights:

- We recommend using ToT on complex tasks requiring deliberate reasoning, on which CoT struggles.
- Flexibility of ToT allows some performance-cost tradeoff, e.g. change beam size or vote number in BFS, few-shot vs. zero-shot prompting, GPT-3.5 vs. GPT-4, etc. One could configure the setup based on some resource constraints or performance goal.
- There is much space for improving efficiency --- e.g. BFS could early stop when solution is found, or trim down beam size to $b<5$ when some thoughts are "impossible".
- We believe that more computation is indeed required in order for the model to achieve stronger intelligence, and this should not become a blocking issue as in the long run, (open-source) LLMs will become much cheaper and more efficient. It is also a great direction how to better train/finetune LLMs for thought generation and/or evaluation.



Meta-review: I will recommend this paper for acceptance, because reviewers felt the paper proposed an interesting approach (ysyd, fAU5, 3c3c, sEEP), and showed strong improvements over CoT (fAU5).

There was extensive conversation between reviewers and authors in the rebuttal period. Weak points were raised by reviewers and were predominantly addressed by authors in rebuttal, including (i) more tasks would be nice (ysyd, fAU5, 3c3c) to which rebuttal added more applications (gSM8K and StrategyQA), (ii) efficiency issues (fAU5), (iii) parts of the work aren’t interesting/novel enough (fAU5; “I have no doubt about its influence on the community in the short near future. However, its core novelty of applying (simple) search algorithms to LLM reasoning isn't significant enough.“), (iv) necessity of GPT4 in the pipeline (fAU5, sEEP), which was also addressed in rebuttal. 

Additional baselines were suggested (3c3c, sEEP), but during reviewer and AC discussion, reviewers verified that these were optional, and that the paper meets the bar in their opinions regardless.

Recommendations for the next version of the work: We recommend summarizing discussion from rebuttal in the paper, including regarding the tradeoffs of ToT v. CoT (sEEP) including efficiency trade off of CoT (fAU5), the difficulty of implementing the approach (3c3c, sEEP). The prompt details suggested by 3c3c should also be included in the next version of the paper. It would also be nice to see the results with earlier LMs+ToT included in the final paper.
Decision: Accept (oral)