notebooks/2.1-rag-agent.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This example was taken from the langchain docs:\n",
    "# https://python.langchain.com/v0.2/docs/tutorials/rag/\n",
    "# %pip install --upgrade --quiet  langchain langchain-community langchainhub langchain-openai faiss-cpu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from langchain_community.document_loaders import PyPDFLoader\n",
    "\n",
    "loader = PyPDFLoader(\"./assets-resources/papers/tree-of-thoughts.pdf\")\n",
    "documents = loader.load()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Document(metadata={'source': './assets-resources/papers/tree-of-thoughts.pdf', 'page': 0}, page_content='Tree of Thoughts: Deliberate Problem Solving\\nwith Large Language Models\\nShunyu Yao\\nPrinceton UniversityDian Yu\\nGoogle DeepMindJeffrey Zhao\\nGoogle DeepMindIzhak Shafran\\nGoogle DeepMind\\nThomas L. Grifﬁths\\nPrinceton UniversityYuan Cao\\nGoogle DeepMindKarthik Narasimhan\\nPrinceton University\\nAbstract\\nLanguage models are increasingly being deployed for general problem solving\\nacross a wide range of tasks, but are still conﬁned to token-level, left-to-right\\ndecision-making processes during inference. This means they can fall short in\\ntasks that require exploration, strategic lookahead, or where initial decisions play\\na pivotal role. To surmount these challenges, we introduce a new framework for\\nlanguage model inference, “Tree of Thoughts” (ToT), which generalizes over the\\npopular “Chain of Thought” approach to prompting language models, and enables\\nexploration over coherent units of text (“thoughts”) that serve as intermediate steps\\ntoward problem solving. ToT allows LMs to perform deliberate decision making\\nby considering multiple different reasoning paths and self-evaluating choices to\\ndecide the next course of action, as well as looking ahead or backtracking when\\nnecessary to make global choices. Our experiments show that ToT signiﬁcantly\\nenhances language models’ problem-solving abilities on three novel tasks requiring\\nnon-trivial planning or search: Game of 24, Creative Writing, and Mini Crosswords.\\nFor instance, in Game of 24, while GPT-4 with chain-of-thought prompting only\\nsolved 4% of tasks, our method achieved a success rate of 74%. Code repo with all\\nprompts: https://github.com/ysymyth/tree-of-thought-llm .\\n1 Introduction\\nOriginally designed to generate text, scaled-up versions of language models (LMs) such as GPT [ 22,\\n23,1,20] and PaLM [ 5] have been shown to be increasingly capable of performing an ever wider\\nrange of tasks requiring mathematical, symbolic, commonsense, and knowledge reasoning. It is\\nperhaps surprising that underlying all this progress is still the original autoregressive mechanism for\\ngenerating text, which makes token-level decisions one by one and in a left-to-right fashion. Is such\\na simple mechanism sufﬁcient for a LM to be built toward a general problem solver? If not, what\\nproblems would challenge the current paradigm, and what should be alternative mechanisms?\\nThe literature on human cognition provides some clues to answer these questions. Research on “dual\\nprocess” models suggests that people have two modes in which they engage with decisions – a fast,\\nautomatic, unconscious mode (“System 1”) and a slow, deliberate, conscious mode (“System 2”)\\n[27,28,13,12]. These two modes have previously been connected to a variety of mathematical\\nmodels used in machine learning. For example, research on reinforcement learning in humans and\\nother animals has explored the circumstances under which they engage in associative “model free”\\nlearning or more deliberative “model based” planning [ 6]. The simple associative token-level choices\\nof LMs are also reminiscent of “System 1”, and thus might beneﬁt from augmentation by a more\\ndeliberate “System 2” planning process that (1) maintains and explores diverse alternatives for current\\nPreprint. Under review.arXiv:2305.10601v1  [cs.CL]  17 May 2023'),\n",
       " Document(metadata={'source': './assets-resources/papers/tree-of-thoughts.pdf', 'page': 1}, page_content='GĮŔũƜ\\njũƜŔũƜGĮŔũƜ\\njũƜŔũƜʱÊʲˤGjʱæʲˤ\\x1dĵÉGĮŔũƜ\\nˤjũƜŔũƜʱçʲˤ\\x1dĵÉˁ\\x92\\x1dʟʟʟʟaÊĠĵŗƓŤƆˤſĵŤòGĮŔũƜ\\nˤjũƜŔũƜʱíʲˤÉĵÉˤʱĵũŗŝʲʟʟʟʟʟʟˤˤʝˤƛĎĵũĈĎƜ)L[\\x03FRORU\\x03\\x0bE\\\\\\x03<XTLDQ\\x0c0DUN\\x03GLIIHUHQFH\\x03E\\\\\\x03FRORU\\nGĮŔũƜ\\njũƜŔũƜGĮŔũƜ\\njũƜŔũƜGĮŔũƜ\\nˤjũƜŔũƜʱçʲˤ\\x92òĦƙˤ\\x1dĵĮŝƓŝŤòĮçƆˤƀƓƜĎˤ\\x1dĵÉˤʱ\\x1dĵÉˁ\\x92\\x1dʲaÊĠĵŗƓŤƆˤſĵŤòGĮŔũƜ\\nˤjũƜŔũƜʱíʲˤÉŗòòˤĵƙˤ\\x9aĎĵũĈĎŤŝˤʱÉĵÉʲʟʟʟʟʟʟʟʟʟʟˤˤƛĎĵũĈĎƜ\\nʱçʲˤ\\x1dĎÊđĮˤĵƙˤ\\x9aĎĵũĈĎƜˤ\\x89ŗĵĭŔƜđĮĈˤʱ\\x1dĵÉʲʱÊʲˤGĮŔũƜˁjũƜŔũƜˤ\\x89ŗĵĭŔƜđĮĈˤʱGjʲFigure 1: Schematic illustrating various approaches to problem solving with LLMs. Each rectangle\\nbox represents a thought , which is a coherent language sequence that serves as an intermediate\\nstep toward problem solving. See concrete examples of how thoughts are generated, evaluated, and\\nsearched in Figures 2,4,6.\\nchoices instead of just picking one, and (2) evaluates its current status and actively looks ahead or\\nbacktracks to make more global decisions.\\nTo design such a planning process, we return to the origins of artiﬁcial intelligence (and cognitive\\nscience), drawing inspiration from the planning processes explored by Newell, Shaw, and Simon\\nstarting in the 1950s [ 18,19]. Newell and colleagues characterized problem solving [ 18] as search\\nthrough a combinatorial problem space, represented as a tree. We thus propose the Tree of Thoughts\\n(ToT) framework for general problem solving with language models. As Figure 1 illustrates, while\\nexisting methods (detailed below) sample continuous language sequences for problem solving, ToT\\nactively maintains a tree of thoughts, where each thought is a coherent language sequence that serves\\nas an intermediate step toward problem solving (Table 1). Such a high-level semantic unit allows the\\nLM to self-evaluate the progress different intermediate thoughts make towards solving the problem\\nthrough a deliberate reasoning process that is also instantiated in language (Figures 2,4,6). This\\nimplementation of search heuristics via LM self-evaluation and deliberation is novel, as previous\\nsearch heuristics are either programmed or learned. Finally, we combine this language-based\\ncapability to generate and evaluate diverse thoughts with search algorithms, such as breadth-ﬁrst\\nsearch (BFS) or depth-ﬁrst search (DFS), which allow systematic exploration of the tree of thoughts\\nwith lookahead and backtracking.\\nEmpirically, we propose three new problems that challenge existing LM inference methods even with\\nthe state-of-the-art language model, GPT-4 [ 20]: Game of 24, Creative Writing, and Crosswords\\n(Table 1). These tasks require deductive, mathematical, commonsense, lexical reasoning abilities,\\nand a way to incorporate systematic planning or search. We show ToT obtains superior results on\\nall three tasks by being general and ﬂexible enough to support different levels of thoughts, different\\nways to generate and evaluate thoughts, and different search algorithms that adapt to the nature of\\ndifferent problems. We also analyze how such choices affect model performances via systematic\\nablations and discuss future directions to better train and use LMs.\\n2 Background\\nWe ﬁrst formalize some existing methods that use large language models for problem-solving,\\nwhich our approach is inspired by and later compared with. We use pθto denote a pre-trained LM\\nwith parameters θ, and lowercase letters x,y,z,s,···to denote a language sequence , i.e.x=\\n(x[1],···,x[n])where eachx[i]is a token, so that pθ(x) =∏n\\ni=1pθ(x[i]|x[1...i]). We use uppercase\\nlettersS,···to denote a collection of language sequences.\\nInput-output (IO) prompting is the most common way to turn a problem input xinto outputywith\\nLM:y∼pθ(y|promptIO(x)), where promptIO(x)wraps inputxwith task instructions and/or few-\\nshot input-output examples. For simplicity, let us denote pprompt\\nθ(output|input ) =pθ(output|\\nprompt (input )), so that IO prompting can be formulated as y∼pIO\\nθ(y|x).\\n2'),\n",
       " Document(metadata={'source': './assets-resources/papers/tree-of-thoughts.pdf', 'page': 2}, page_content='Chain-of-thought (CoT) prompting [35] was proposed to address cases where the mapping of\\ninputxto outputyis non-trivial (e.g. when xis a math question and yis the ﬁnal numerical answer).\\nThe key idea is to introduce a chain of thoughtsz1,···,znto bridgexandy, where each ziis a\\ncoherent language sequence that serves as a meaningful intermediate step toward problem solving\\n(e.g.zicould be an intermediate equation for math QA). To solve problems with CoT, each thought\\nzi∼pCoT\\nθ(zi|x,z1···i−1)is sampled sequentially, then the output y∼pCoT\\nθ(y|x,z1···n). In\\npractice, [z1···n,y]∼pCoT\\nθ(z1···n,y|x)is sampled as a continuous language sequence, and the\\ndecomposition of thoughts (e.g. is each zia phrase, a sentence, or a paragraph) is left ambiguous.\\nSelf-consistency with CoT (CoT-SC) [33] is an ensemble approach that samples ki.i.d. chains\\nof thought: [z(i)\\n1···n,y(i)]∼pCoT\\nθ(z1···n,y|x) (i= 1···k), then returns the most frequent output:\\narg maxy#{i|y(i)=y}. CoT-SC improves upon CoT, because there are generally different\\nthought processes for the same problem (e.g. different ways to prove the same theorem), and the\\noutput decision can be more faithful by exploring a richer set of thoughts. However, within each\\nchain there is no local exploration of different thought steps, and the “most frequent” heuristic only\\napplies when the output space is limited (e.g. multi-choice QA).\\n3 Tree of Thoughts: Deliberate Problem Solving with LM\\nA genuine problem-solving process involves the repeated use of available informa-\\ntion to initiate exploration, which discloses, in turn, more information until a way\\nto attain the solution is ﬁnally discovered.—— Newell et al. [18]\\nResearch on human problem-solving suggests that people search through a combinatorial problem-\\nspace – a tree where the nodes represent partial solutions, and the branches correspond to operators\\nthat modify them [ 18,19]. Which branch to take is determined by heuristics that help to navigate the\\nproblem-space and guide the problem-solver towards a solution. This perspective highlights two key\\nshortcomings of existing approaches that use LMs to solve general problems: 1) Locally, they do not\\nexplore different continuations within a thought process – the branches of the tree. 2) Globally, they\\ndo not incorporate any type of planning, lookahead, or backtracking to help evaluate these different\\noptions – the kind of heuristic-guided search that seems characteristic of human problem-solving.\\nTo address these shortcomings, we introduce Tree of Thoughts (ToT) , a paradigm that allows LMs to\\nexplore multiple reasoning paths over thoughts (Figure 1(c)). ToT frames any problem as a search\\nover a tree, where each node is a states= [x,z1···i]representing a partial solution with the input and\\nthe sequence of thoughts so far. A speciﬁc instantiation of ToT involves answering four questions:\\n1. How to decompose the intermediate process into thought steps; 2. How to generate potential\\nthoughts from each state; 3. How to heuristically evaluate states; 4. What search algorithm to use.\\n1. Thought decomposition. While CoT samples thoughts coherently without explicit decomposition,\\nToT leverages problem properties to design and decompose intermediate thought steps. As Table 1\\nshows, depending on different problems, a thought could be a couple of words (Crosswords), a line of\\nequation (Game of 24), or a whole paragraph of writing plan (Creative Writing). In general, a thought\\nshould be “small” enough so that LMs can generate promising and diverse samples (e.g. generating\\na whole book is usually too “big” to be coherent), yet “big” enough so that LMs can evaluate its\\nprospect toward problem solving (e.g. generating one token is usually too “small” to evaluate).\\n2. Thought generator G(pθ,s,k).Given a tree state s= [x,z1···i], we consider two strategies to\\ngeneratekcandidates for the next thought step:\\n(a)Sample i.i.d. thoughts from a CoT prompt (Creative Writing, Figure 4): z(j)∼\\npCoT\\nθ(zi+1|s) =pCoT\\nθ(zi+1|x,z1···i) (j= 1···k). This works better when the thought\\nspace is rich (e.g. each thought is a paragraph), and i.i.d. samples lead to diversity;\\n(b)Propose thoughts sequentially using a “propose prompt” (Game of 24, Figure 2; Crosswords,\\nFigure 6): [z(1),···,z(k)]∼ppropose\\nθ(z(1···k)\\ni+1|s). This works better when the thought\\nspace is more constrained (e.g. each thought is just a word or a line), so proposing different\\nthoughts in the same context avoids duplication.\\n3. State evaluator V(pθ,S).Given a frontier of different states, the state evaluator evaluates the\\nprogress they make towards solving the problem, serving as a heuristic for the search algorithm\\nto determine which states to keep exploring and in which order. While heuristics are a standard\\napproach to solving search problems, they are typically either programmed (e.g. DeepBlue [ 3]) or\\n3'),\n",
       " Document(metadata={'source': './assets-resources/papers/tree-of-thoughts.pdf', 'page': 3}, page_content='learned (e.g. AlphaGo [ 26]). We propose a third alternative, by using the LM to deliberately reason\\nabout states. When applicable, such a deliberate heuristic can be more ﬂexible than programmed\\nrules, and more sample-efﬁcient than learned models. Similar to the thought generator, we consider\\ntwo strategies to evaluate states either independently or together:\\n(a)Value each state independently: V(pθ,S)(s)∼pvalue\\nθ(v|s)∀s∈S, where a value\\nprompt reasons about the state sto generate a scalar value v(e.g. 1-10) or a classiﬁca-\\ntion (e.g. sure/likely/impossible) that could be heuristically turned into a value. The basis\\nof such evaluative reasoning can vary across problems and thought steps. In this work, we\\nexplore evaluation via few lookahead simulations (e.g. quickly conﬁrm that 5, 5, 14 can\\nreach 24 via 5 + 5 + 14, or “hot l” can mean “inn” via ﬁlling “e” in “ ”) plus commonsense\\n(e.g. 1 2 3 are too small to reach 24, or no word can start with “tzxc”). While the former\\nmight promote “good” states, the latter could help eliminate “bad” states. Such valuations\\ndo not need to be perfect, and only need to be approximately\\n(b)Vote across states: V(pθ,S)(s) =1[s=s∗], where a “good” state s∗∼pvote\\nθ(s∗|S)is\\nvoted out based on deliberately comparing different states in Sin a vote prompt. When\\nproblem success is harder to directly value (e.g. passage coherency), it is natural to to instead\\ncompare different partial solutions and vote for the most promising one. This is similar\\nin spirit to a “step-wise” self-consistency strategy, i.e. cast “which state to explore” as a\\nmulti-choice QA, and use LM samples to vote for it.\\nFor both strategies, we could prompt the LM multiple times to aggregate the value or vote results to\\ntrade time/resource/cost for more faithful/robust heuristics.\\nAlgorithm 1 ToT-BFS(x,pθ,G,k,V,T,b )\\nRequire: Inputx, LMpθ, thought generator G()\\n& size limitk, states evaluator V(), step limitT,\\nbreadth limit b.\\nS0←{x}\\nfort= 1,···,Tdo\\nS′\\nt←{[s,z]|s∈St−1,zt∈G(pθ,s,k)}\\nVt←V(pθ,S′\\nt)\\nSt←arg maxS⊂S′\\nt,|S|=b∑\\ns∈SVt(s)\\nend for\\nreturnG(pθ,arg maxs∈STVT(s),1)Algorithm 2 ToT-DFS(s,t,pθ,G,k,V,T,v th)\\nRequire: Current state s, stept, LMpθ, thought\\ngeneratorG()and size limit k, states evaluator\\nV(), step limitT, thresholdvth\\nift>T then record output G(pθ,s,1)\\nend if\\nfors′∈G(pθ,s,k)do⊿sorted candidates\\nifV(pθ,{s′})(s)>vthres then⊿pruning\\nDFS(s′,t+ 1)\\nend if\\nend for\\n4. Search algorithm. Finally, within the ToT framework, one can plug and play different search\\nalgorithms depending on the tree structure. We explore two relatively simple search algorithms and\\nleave more advanced ones (e.g. A* [9], MCTS [2]) for future work:\\n(a)Breadth-ﬁrst search (BFS) (Algorithm 1) maintains a set of the bmost promising states\\nper step. This is used for Game of 24 and Creative Writing where the tree depth is limit\\n(T≤3), and initial thought steps can be evaluated and pruned to a small set ( b≤5).\\n(b)Depth-ﬁrst search (DFS) (Algorithm 2) explores the most promising state ﬁrst, until the\\nﬁnal output is reached ( t > T ), or the state evaluator deems it impossible to solve the\\nproblem from the current s(V(pθ,{s})(s)≤vthfor a value threshold vth). In the latter\\ncase, the subtree from sispruned to trade exploration for exploitation. In both cases, DFS\\nbacktracks to the parent state of sto continue exploration.\\nConceptually, ToT has several beneﬁts as a method for general problem-solving with LMs: (1) Gener-\\nality. IO, CoT, CoT-SC, and self-reﬁnement can be seen as special cases of ToT (i.e. trees of limited\\ndepth and breadth; Figure 1). (2) Modularity. The base LM, as well as the thought decomposition,\\ngeneration, evaluation, and search procedures can all be varied independently. (3) Adaptability .\\nDifferent problem properties, LM capabilities, and resource constraints can be accommodated. (4)\\nConvenience. No extra training is needed, just a pre-trained LM is sufﬁcient. The next section will\\nshow how these conceptual beneﬁts translate to strong empirical performance in different problems.\\n4 Experiments\\nWe propose three tasks that are hard even when sampling from the state-of-the-art language model,\\nGPT-4 [ 20], using standard IO prompting or chain-of-thought (CoT) prompting. We show how\\n4'),\n",
       " Document(metadata={'source': './assets-resources/papers/tree-of-thoughts.pdf', 'page': 4}, page_content='Game of 24 Creative Writing 5x5 Crosswords\\nInput 4 numbers (4 9 10 13) 4 random sentences 10 clues (h1. presented;..)\\nOutput An equation to reach 24\\n(13-9)*(10-4)=24A passage of 4 paragraphs\\nending in the 4 sentences5x5 letters: SHOWN;\\nWIRRA; A V AIL; ...\\nThoughts 3 intermediate equations\\n(13-9=4 (left 4,4,10); 10-\\n4=6 (left 4,6); 4*6=24)A short writing plan\\n(1. Introduce a book that\\nconnects...)Words to ﬁll in for clues:\\n(h1. shown; v5. naled; ...)\\n#ToT steps 3 1 5-10 (variable)\\nTable 1: Task overview. Input, output, thought examples are in blue.\\ndeliberate search in trees of thoughts (ToT) produces better results, and more importantly, interesting\\nand promising new ways to use language models to solve problems requiring search or planning.\\nUnless otherwise stated, we perform experiments using a Chat Completion mode GPT-41with a\\nsampling temperature of 0.7.\\n4.1 Game of 24\\nGame of 24 is a mathematical reasoning challenge, where the goal is to use 4 numbers and basic\\narithmetic operations (+-*/) to obtain 24. For example, given input “4 9 10 13”, a solution output\\ncould be “(10 - 4) * (13 - 9) = 24”.\\nʳĵĮòˤòƅÊĭŔĦòʴˤGĮŔũƜʝˤʁˤʆˤɾɽˤɾʀ\\x89ĵŝŝđæĦòˤĮòƅƜˤŝŤòŔŝʝˤˤˤ3URSRVH\\x033URPSWʁˤ̌ˤʆˤ̐ˤɾʀˤʱĦòƙƜʝˤɾɽˤɾʀˤɾʀʲɾɽˤˊˤʁˤ̐ˤʃˤʱĦòƙƜʝˤʃˤʆˤɾʀʲʳʛʛʛĭĵŗòˤĦđĮòŝʟʴ7KRXJKW\\x03*HQHUDWLRQ/0)ſÊĦũÊŤòˤđƙˤĈƓſòĮˤĮũĭæòŗŝˤçÊĮˤŗòÊçĎˤɿʁˤʱŝũŗòʫĦđģòĦƆʫđĭŔĵŝŝđæĦòʲɾɽˤɾʁʝˤɾɽˤ̌ˤɾʁˤ̐ˤɿʁʛˤŝũŗòʳĭĵŗòˤòƅÊĭŔĦòŝʴɾɽˤɾʀˤɾʀ9DOXH\\x033URPSWʱɾʀˤˊˤɾɽʲˤʦˤɾʀˤ̐ˤʀˤʦˤɾʀˤ̐ˤʀʆɾɽˤ̌ˤɾʀˤ̌ˤɾʀˤ̐ˤʀʃ\\x9aĎòŗòˤƓŝˤĮĵˤƀÊƆˤƘĵˤĵæŤÊđĮˤɿʁˤƀƓƜĎˤƛĎòŝòˤĮũĭæòŗŝʛˤđĭŔĵŝŝđæĦò7KRXJKW\\x03(YDOXDWLRQʱæʲʱçʲ/0GĮŔũƜʝˤʁˤʆˤɾɽˤɾʀʁ̌ʆ̐ɾʀʱĦòƙƜʝˤɾɽˤɾʀˤɾʀʲɾɽˁʁ̐ʃʱĦòƙƜʝˤʃˤʆˤɾʀʲʟʟɾʀˁʃ̐ʄʱĦòƙƜʝˤʄˤʆʲɾʀˁʆ̐ʁʱĦòƙƜʝˤʁˤʃʲʟʟʁʦʃ̐ɿʁʱĦòƙƜʝˤɿʁʲʁ̌ʃ̐ɾɽʱĦòƙƜʝˤɾɽʲʟʟʱÊʲ\\nʳĵĮòˤòƅÊĭŔĦòʴˤGĮŔũƜʝˤʁˤʆˤɾɽˤɾʀ\\x89ĵŝŝđæĦòˤĮòƅƜˤŝŤòŔŝʝˤˤˤ\\x0bD\\x0c\\x033URSRVH\\x033URPSWʁˤ̌ˤʆˤ̐ˤɾʀˤʱĦòƙƜʝˤɾɽˤɾʀˤɾʀʲɾɽˤˊˤʁˤ̐ˤʃˤʱĦòƙƜʝˤʃˤʆˤɾʀʲʳʛʛʛĭĵŗòˤĦđĮòŝʟʴ7KRXJKW\\x03*HQHUDWLRQ/0)ſÊĦũÊŤòˤđƙˤĈƓſòĮˤĮũĭæòŗŝˤçÊĮˤŗòÊçĎˤɿʁˤʱŝũŗòʫĦđģòĦƆʫđĭŔĵŝŝđæĦòʲɾɽˤɾʁʝˤɾɽˤ̌ˤɾʁˤ̐ˤɿʁʛˤŝũŗòʳĭĵŗòˤòƅÊĭŔĦòŝʴɾɽˤɾʀˤɾʀ\\x0bE\\x0c\\x039DOXH\\x033URPSWʱɾʀˤˊˤɾɽʲˤʦˤɾʀˤ̐ˤʀˤʦˤɾʀˤ̐ˤʀʆɾɽˤ̌ˤɾʀˤ̌ˤɾʀˤ̐ˤʀʃˤ\\x9aĎòŗòˤƓŝˤĮĵˤƀÊƆˤƘĵˤĵæŤÊđĮˤɿʁˤƀƓƜĎˤƛĎòŝòˤæƓĈˤĮũĭæòŗŝʛˤđĭŔĵŝŝđæĦò7KRXJKW\\x03(YDOXDWLRQ/0GĮŔũƜʝˤʁˤʆˤɾɽˤɾʀʁ̌ʆ̐ɾʀʱĦòƙƜʝˤɾɽˤɾʀˤɾʀʲɾɽˁʁ̐ʃʱĦòƙƜʝˤʃˤʆˤɾʀʲʟʟɾʀˁʃ̐ʄʱĦòƙƜʝˤʄˤʆʲɾʀˁʆ̐ʁʱĦòƙƜʝˤʁˤʃʲʟʟʁʦʃ̐ɿʁʱĦòƙƜʝˤɿʁʲʁ̌ʃ̐ɾɽʱĦòƙƜʝˤɾɽʲʟʟ)L[\\x03FRORU\\x03\\x0bE\\\\\\x03<XTLDQ\\x0c0DUN\\x03GLII\\x03SURPSW\\x03ZLWK\\x03FRORU\\nFigure 2: ToT in a game of 24. The LM is prompted for (a) thought generation and (b) valuation.\\nTask Setup. We scrape data from 4nums.com, which has 1,362 games that are sorted from easy to\\nhard by human solving time, and use a subset of relatively hard games indexed 901-1,000 for testing.\\nFor each task, we consider the output as success if it is a valid equation that equals 24 and uses the\\ninput numbers each exactly once. We report the success rate across 100 games as the metric.\\nBaselines. We use a standard input-output (IO) prompt with 5 in-context examples. For chain-of-\\nthought (CoT) prompting, we augment each input-output pair with 3 intermediate equations, each\\noperating on two remaining numbers. For example, given input “4 9 10 13”, the thoughts could be\\n“13 - 9 = 4 (left: 4 4 10); 10 - 4 = 6 (left: 4 6); 4 * 6 = 24 (left: 24)”. For each game, we sample IO\\nand CoT prompting for 100 times for average performance. We also consider a CoT self-consistency\\nbaseline, which takes the majority output from 100 CoT samples, and an iterative-reﬁne approach on\\ntop of an IO sample for at most 10iterations. At each iteration, the LM is conditioned on all previous\\nhistory to “reﬂect on your mistakes and generate a reﬁned answer” if the output is incorrect. Note\\nthat it uses groundtruth feedback signals about equation correctness.\\nToT Setup. To frame Game of 24 into ToT, it is natural to decompose the thoughts into 3 steps,\\neach an intermediate equation. As shown in Figure 2(a), at each tree node, we exact the “left”\\nnumbers and prompt the LM to propose some possible next steps. The same “propose prompt” is\\nused for all 3 thought steps, though it only has one example with 4 input numbers. We perform a\\nbreadth-ﬁrst search (BFS) in ToT, where at each step we keep the best b= 5candidates. To perform\\ndeliberate BFS in ToT, as shown in Figure 2(b), we prompt LM to evaluate each thought candidate as\\n“sure/maybe/impossible” with regard to reaching 24. The aim is to promote correct partial solutions\\nthat can be verdicted within few lookahead trials, and eliminate impossible partial solutions based on\\n“too big/small” commonsense, and keep the rest “maybe”. We sample values 3times for each thought.\\n1Experiments were done between May 5-16, 2023.\\n5'),\n",
       " Document(metadata={'source': './assets-resources/papers/tree-of-thoughts.pdf', 'page': 5}, page_content='Method Success\\nIO prompt 7.3%\\nCoT prompt 4.0%\\nCoT-SC (k=100) 9.0%\\nToT (ours) (b=1) 45%\\nToT (ours) (b=5) 74%\\nIO + Reﬁne (k=10) 27%\\nIO(best of 100) 33%\\nCoT (best of 100) 49%\\nTable 2: Game of 24 Results.\\n0 25 50 75 1000.20.40.6(a) Success rate with nodes visited\\nIO (best of k)\\nCoT (best of k)\\nToT (b=1...5)\\n1 2 3 4Correct0.00.20.40.6(b) Samples failed at each step\\nCoT\\nToT (b=5) Figure 3: Game of 24 (a) scale analysis & (b) error analysis.\\nResults. As shown in Table 2, IO, CoT, and CoT-SC prompting methods perform badly on the task,\\nachieving only 7.3%, 4.0%, and 9.0% success rates. In contrast, ToT with a breadth of b= 1already\\nachieves a success rate of 45%, whileb= 5 achieves 74%. We also consider an oracle setup for\\nIO/CoT, by calculating the success rate using best of ksamples (1≤k≤100) . To compare IO/CoT\\n(best of k) with ToT, we consider calculating the tree nodes visited per task in ToT across b= 1···5,\\nand map the 5 success rates in Figure 3(a), treating IO/CoT (best of k) as visitingknodes in a bandit.\\nNot surprisingly, CoT scales better than IO, and best of 100 CoT samples achieve a success rate of\\n49%, but still much worse than exploring more nodes in ToT ( b>1).\\nError Analysis. Figure 3(b) breaks down at which step CoT and ToT samples fail the task, i.e. the\\nthought (in CoT) or all bthoughts (in ToT) are invalid or impossible to reach 24. Notably, around\\n60% of CoT samples already failed the task after generating the ﬁrst step, or equivalently, the ﬁrst\\nthree words (e.g. “ 4 + 9 ”). This highlights the issues with direct left-to-right decoding.\\n4.2 Creative writing\\nNext, we invent a creative writing task where the input is 4 random sentences and the output should\\nbe a coherent passage with 4 paragraphs that end in the 4 input sentences respectively. Such a task is\\nopen-ended and exploratory, and challenges creative thinking as well as high-level planning.\\nTask setup. We sample random sentences from randomwordgenerator.com to form 100 inputs, and\\nthere is no groundtruth passage for each input constraint. As we ﬁnd that GPT-4 can follow the\\ninput constraints most of the time, we focus on evaluating passage coherency in two ways: using a\\nGPT-4 zero-shot prompt to provide a 1-10 scalar score, or using human judgments to compare pairs\\nof outputs from different methods. For the former, we sample 5 scores and average them for each task\\noutput, and we ﬁnd these 5 scores usually consistent, with a standard deviation of around 0.56on\\naverage across outputs. For the latter, we employ a subset of the authors in a blind study to compare\\nthe coherency of CoT vs. ToT generated passage pairs, where the order of passages is random ﬂipped\\nover 100 inputs.\\nBaselines. Given the creative nature of the task, both IO and CoT prompts are zero-shot. While the\\nformer prompts the LM to directly generate a coherent passage given input constraints, the latter\\nprompts the LM to ﬁrst make a brief plan then write the passage, i.e. the plan serves as the intermediate\\nthought step. We generate 10 IO and CoT samples per task. We also consider an iterative-reﬁne\\n(k≤5) method on top of a random IO sample for each task, where the LM is conditioned on input\\nconstraints and the last generated passage to decide if the passage is already “perfectly coherent”,\\nand if not generate a reﬁned one.\\nToT setup. We build a ToT with depth 2 (and only 1 intermediate thought step) — the LM ﬁrst\\ngeneratesk= 5plans and votes for the best one (Figure 4), then similarly generate k= 5passages\\nbased on the best plan then vote for the best one. Here the breadth limit b= 1, as only one choice is\\nkept per step. A simple zero-shot vote prompt (“analyze choices below, then conclude which is most\\npromising for the instruction”) is used to sample 5 votes at both steps.\\nResults. Figure 5(a) shows average GPT-4 scores across 100 tasks, where ToT (7.56) is deemed to\\ngenerate more coherent passages than IO (6.19) and CoT (6.93) on average. While such an automatic\\nmetric might be noisy, Figure 5(b) conﬁrms the ﬁnding by showing that humans prefer ToT over\\nCoT in 41 out of 100 passage pairs, while only prefer CoT over ToT in 21 (other 38 pairs are found\\n“similarly coherent”). Lastly, iterative-reﬁne is more effective on this natural language task, where\\n6'),\n",
       " Document(metadata={'source': './assets-resources/papers/tree-of-thoughts.pdf', 'page': 6}, page_content='µŗƓŤòˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòˤĵƙˤʁˤŝĎĵŗƜˤŔÊŗÊĈŗÊŔĎŝʛˤ\\x9aĎòˤòĮíˤŝòĮŤòĮçòˤĵƙˤòÊçĎˤŔÊŗÊĈŗÊŔĎˤĭũŝƜˤæòʝˤɾʛˤGƜˤƓŝĮ˙ƛˤíđƙƙƓçũĦƜˤƘĵˤíĵˤÊˤĎÊĮíŝŤÊĮíˤđƙˤƆĵũˤĠũŝƜˤŝŤÊĮíˤĵĮˤƆĵũŗˤĎÊĮíŝʛˤɿʛˤGƜˤçÊũĈĎƜˤĎđĭˤĵƙƙˤĈũÊŗíˤƛĎÊƜˤŝŔÊçòˤŝĭòĦĦòíˤĵƙˤŝòÊŗòíˤŝŤòÊģʛˤʀʛˤµĎòĮˤŝĎòˤíƓíĮ˒ƛˤĦđģòˤÊˤĈũƆˤƀĎĵˤƀÊŝˤƛŗƆđĮĈˤƘĵˤŔƓçģˤĎòŗˤũŔʜˤŝĎòˤŝŤÊŗŤòíˤũŝđĮĈˤŝƓĈĮˤĦÊĮĈũÊĈòʛˤʁʛˤ)ÊçĎˤŔòŗŝĵĮˤƀĎĵˤģĮĵƀŝˤƆĵũˤĎÊŝˤÊˤíđƙćòŗòĮƜˤŔòŗçòŔƜƓĵĮˤĵƙˤƀĎĵˤƆĵũˤÊŗòʛˤˤɾʛˤGĮƜŗĵíũçòˤÊĮíˤòƅŔĦÊđĮˤƛĎòˤƘòçĎĮƓŖũòˤĵƙˤíĵđĮĈˤÊˤĎÊĮíŝŤÊĮíˤɿʛˤ\\x92ƀƓŤçĎˤƘĵˤÊˤŝŤĵŗƆˤÊæĵũƜˤÊĮˤÊŝƜŗĵĮÊũƜ˙ŝˤƚđŗŝƜˤƛđĭòˤđĮˤŝŔÊçòˤʀʛˤ#òŝçŗđæòˤÊˤŝƓƜũÊƜƓĵĮˤƀĎòŗòˤÊˤƀĵĭÊĮˤũŝòŝˤŝƓĈĮˤĦÊĮĈũÊĈòˤƘĵˤÊſĵƓíˤũĮƀÊĮŤòíˤÊƜŤòĮƜƓĵĮˤʁʛˤ\\x9aĎòˤƚđĮÊĦˤŔÊŗÊĈŗÊŔĎˤòƅŔĦÊđĮŝˤĎĵƀˤòſòŗƆĵĮòˤĎÊŝˤíđƙćòŗòĮƜˤŔòŗçòŔƜƓĵĮŝˤĵƙˤĵƜĎòŗŝɾʛˤGĮƜŗĵíũçƜƓĵĮˤƘĵˤÊĮˤũĮũŝũÊĦˤŝòĦƙˊĎòĦŔˤæĵĵģʜˤĭòĮƜƓĵĮđĮĈˤÊˤĎÊĮíŝŤÊĮíˤÊŝˤÊˤĭòŤÊŔĎĵŗˤƗĵŗˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʛˤɿʛˤ#ƓŝçũŝŝˤƛĎòˤũĮòƅŔòçŤòíˤƛĎđĮĈŝˤĦòÊŗĮòíˤƚŗĵĭˤÊŝƜŗĵĮÊũŤŝʜˤđĮçĦũíđĮĈˤƛĎòˤŝĭòĦĦˤĵƙˤŝŔÊçòʛˤʀʛˤ#òŝçŗđæòˤÊˤƀĵĭÊĮ˙ŝˤçĦòſòŗˤƘÊçƜƓçˤƗĵŗˤÊſĵƓíđĮĈˤũĮƀÊĮŤòíˤÊƜŤòĮƜƓĵĮˤÊƜˤÊˤæÊŗʛˤʁʛˤ\\x1dĵĮŤòĭŔĦÊŤòˤĎĵƀˤíđƙćòŗòĮƜˤŔòŗçòŔƜƓĵĮŝˤĵƙˤĵĮòŝòĦƙˤçÊĮˤŝĎÊŔòˤĵĮò˙ŝˤƓíòĮƜƓŤƆʛʱÊʲˤGĮŔũƜʱæʲˤ\\x89ĦÊĮŝʱʀˤĭĵŗòˤĵĭƓƜŤòíʲʱçʲˤ´ĵŤòŝ\\x01ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\\x1dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝʟˤ\\x1dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤ\\x9aĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛʱɽʫʂˤſĵŤòŝʲ\\x01ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\\x1dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝʟˤ\\x1dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤ\\x9aĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛ\\x01ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\\x1dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝʟˤ\\x1dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤ\\x9aĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛ\\x01ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\\x1dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝʟˤ\\x1dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤ\\x9aĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛ\\x01ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\\x1dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤʳʛʛʛʴˤ\\x1dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤ\\x9aĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛʱʀʫʂˤſĵŤòŝʲʟɾɿGĮŔũƜ\\x89ĦÊĮˤɾ\\x89ĦÊĮˤɿʟʟ\\x89ÊŝŝÊĈòɾ\\x89ÊŝŝÊĈòɿʟʟ)L[\\x03FRORU\\x03\\x0bE\\\\\\x03<XTLDQ\\x0cµŗƓŤòˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòˤĵƙˤʁˤŝĎĵŗƜˤŔÊŗÊĈŗÊŔĎŝʛˤ\\x9aĎòˤòĮíˤŝòĮŤòĮçòˤĵƙˤòÊçĎˤŔÊŗÊĈŗÊŔĎˤĭũŝƜˤæòʝˤɾʛˤGƜˤƓŝĮ˙ƛˤíđƙƙƓçũĦƜˤƘĵˤíĵˤÊˤĎÊĮíŝŤÊĮíˤđƙˤƆĵũˤĠũŝƜˤŝŤÊĮíˤĵĮˤƆĵũŗˤĎÊĮíŝʛˤɿʛˤGƜˤçÊũĈĎƜˤĎđĭˤĵƙƙˤĈũÊŗíˤƛĎÊƜˤŝŔÊçòˤŝĭòĦĦòíˤĵƙˤŝòÊŗòíˤŝŤòÊģʛˤʀʛˤµĎòĮˤŝĎòˤíƓíĮ˒ƛˤĦđģòˤÊˤĈũƆˤƀĎĵˤƀÊŝˤƛŗƆđĮĈˤƘĵˤŔƓçģˤĎòŗˤũŔʜˤŝĎòˤŝŤÊŗŤòíˤũŝđĮĈˤŝƓĈĮˤĦÊĮĈũÊĈòʛˤʁʛˤ)ÊçĎˤŔòŗŝĵĮˤƀĎĵˤģĮĵƀŝˤƆĵũˤĎÊŝˤÊˤíđƙćòŗòĮƜˤŔòŗçòŔƜƓĵĮˤĵƙˤƀĎĵˤƆĵũˤÊŗòʛˤˤɾʛˤGĮƜŗĵíũçòˤÊĮíˤòƅŔĦÊđĮˤƛĎòˤƘòçĎĮƓŖũòˤĵƙˤíĵđĮĈˤÊˤĎÊĮíŝŤÊĮíˤɿʛˤ\\x92ƀƓŤçĎˤƘĵˤÊˤŝŤĵŗƆˤÊæĵũƜˤÊĮˤÊŝƜŗĵĮÊũƜ˙ŝˤƚđŗŝƜˤƛđĭòˤđĮˤŝŔÊçòˤʀʛˤ#òŝçŗđæòˤÊˤŝƓƜũÊƜƓĵĮˤƀĎòŗòˤÊˤƀĵĭÊĮˤũŝòŝˤŝƓĈĮˤĦÊĮĈũÊĈòˤƘĵˤÊſĵƓíˤũĮƀÊĮŤòíˤÊƜŤòĮƜƓĵĮˤʁʛˤ\\x9aĎòˤƚđĮÊĦˤŔÊŗÊĈŗÊŔĎˤòƅŔĦÊđĮŝˤĎĵƀˤòſòŗƆĵĮòˤĎÊŝˤíđƙćòŗòĮƜˤŔòŗçòŔƜƓĵĮŝˤĵƙˤĵƜĎòŗŝɾʛˤGĮƜŗĵíũçƜƓĵĮˤƘĵˤÊĮˤũĮũŝũÊĦˤŝòĦƙˊĎòĦŔˤæĵĵģʜˤĭòĮƜƓĵĮđĮĈˤÊˤĎÊĮíŝŤÊĮíˤÊŝˤÊˤĭòŤÊŔĎĵŗˤƗĵŗˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʛˤɿʛˤ#ƓŝçũŝŝˤƛĎòˤũĮòƅŔòçŤòíˤƛĎđĮĈŝˤĦòÊŗĮòíˤƚŗĵĭˤÊŝƜŗĵĮÊũŤŝʜˤđĮçĦũíđĮĈˤƛĎòˤŝĭòĦĦˤĵƙˤŝŔÊçòʛˤʀʛˤ#òŝçŗđæòˤÊˤƀĵĭÊĮ˙ŝˤçĦòſòŗˤƘÊçƜƓçˤƗĵŗˤÊſĵƓíđĮĈˤũĮƀÊĮŤòíˤÊƜŤòĮƜƓĵĮˤÊƜˤÊˤæÊŗʛˤʁʛˤ\\x1dĵĮŤòĭŔĦÊŤòˤĎĵƀˤíđƙćòŗòĮƜˤŔòŗçòŔƜƓĵĮŝˤĵƙˤĵĮòŝòĦƙˤçÊĮˤŝĎÊŔòˤĵĮò˙ŝˤƓíòĮƜƓŤƆʛʱÊʲˤGĮŔũƜʱæʲˤ\\x89ĦÊĮŝʱçʲˤ´ĵŤòŝ\\x01ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\\x1dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤʳʛʛʛʴˤ\\x1dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤ\\x9aĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛGĮŔũƜ\\x89ĦÊĮˤɾˤ\\x89ĦÊĮˤɿˤˤʟʟ\\x89ÊŝŝÊĈòɾ\\x89ÊŝŝÊĈòɿʟʟɽʫʂˤſĵŤòŝ\\x89ĦÊĮˤɾˤˤˤʟʛʟʛɾʟʛɿʟʟʀʫʂˤſĵŤòŝ\\x89ĦÊĮˤʀˁʂˤˤˤ8VH\\x03UHG\\x12JUHHQ\\x03WR\\x03VKRZ\\x03ILQDO\\x03FKRLFH\\nĮʫʂˤſĵŤòŝ\\x89ĦÊĮˤɿˤˤˤ\\n\\x01ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\\x1dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤʳʛʛʛʴˤ\\x1dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤ\\x9aĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛ\\x01ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\\x1dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤʳʛʛʛʴˤ\\x1dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤ\\x9aĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛ\\x01ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\\x1dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤʳʛʛʛʴˤ\\x1dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤ\\x9aĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛ\\x01ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\\x1dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤʳʛʛʛʴˤ\\x1dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤ\\x9aĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛFigure 4: A step of deliberate search in a randomly picked Creative Writing task. Given the input, the\\nLM samples 5 different plans, then votes 5 times to decide which plan is best. The majority choice is\\nused to consequently write the output passage with the same sample-vote procedure.\\nIO CoT ToT IO\\n+refineToT\\n+refine468\\n(a) GPT-4 coherency scores\\nCoT > ToT Similar ToT > CoT010203040\\n213841(b) Human coherency comparison\\nFigure 5: Creative Writing results.Method Success Rate (%)\\nLetter Word Game\\nIO 38.7 14 0\\nCoT 40.6 15.6 1\\nToT (ours) 78 60 20\\n+best state 82.4 67.5 35\\n-prune 65.4 41.5 5\\n-backtrack 54.6 20 5\\nTable 3: Mini Crosswords results.\\nit improves IO coherency score from 6.19 to 7.67, and ToT coherency score from 7.56 to 7.91. We\\nbelieve it could be thought of as a third approach to thought generation in the ToT framework, where\\nnew thoughts can arise from reﬁning old thoughts instead of i.i.d. or sequentially generated.\\n4.3 Mini Crosswords\\nIn Game of 24 and Creative Writing, ToT is relatively shallow — at most 3 thought steps are needed\\nto reach the ﬁnal output. Here we explore 5×5mini crosswords as a harder search problem involving\\nnatural language. Again, the goal is not just to solve the task, as more general crosswords can be\\nreadily solved with specialized NLP pipelines [ 31] that leverages large-scale retrieval instead of LM.\\nRather, we aim to explore the limit of LM as a general problem solver that explores its own thoughts\\nand guides its own exploration with deliberate reasoning as heuristics.\\nTask Setup. We scrape data from GooBix, which contains 156 games of 5×5mini crosswords. As\\nwe observe adjacent games contain similar clues, we use 20 games with indices 1,6,···,91,96for\\ntesting, and games 136,141,146,151,156for prompting. For each task, the input describes the 5\\nhorizontal clues and 5 vertical clues, and the output should be a board of 5×5 = 25 letters to solve\\nthe crosswords. For evaluation, we consider three levels of success: the portion of correct letters (25\\nper game), words (10 per game), and games.\\nBaselines. We provide 5 example input-output pairs in the IO prompt, and in the CoT prompt\\nadditionally include intermediate words in the order h1..5 then v1..5. We run each prompt for 10\\nsamples and average the results.\\nToT Setup. We leverage a depth-ﬁrst search (Algorithm 2) that keeps exploring the most promising\\nsubsequent word clue until the state is no longer promising, then backtrack to the parent state to\\nexplore alternative thoughts. To make search tractable, subsequent thoughts are constrained not to\\nchange any ﬁlled words or letters, so that the ToT has at most 10 intermediate steps. For thought\\ngeneration, at each state we translate all existing thoughts (e.g. “h2.motor; h1.tasks” for the state\\nin Figure 6(a)) into letter constraints for remaining clues (e.g. “v1.To heap: tm ;...”) and prompt\\na proposal prompt 5times to come up with candidates for where and what to ﬁll in the next word.\\nImportantly, we also prompt the LM to give a conﬁdence level for different thoughts, and aggregate\\n7'),\n",
       " Document(metadata={'source': './assets-resources/papers/tree-of-thoughts.pdf', 'page': 7}, page_content='>\\x0b\\nY\\x16\\x11\\x03HORSH\\n\\x0f\\x03\\x16\\x11\\x15\\x0c\\x0f\\x03\\x0b\\nK\\x15\\x11\\x03YDOXH\\n\\x0f\\x03\\x15\\x11\\x13\\x0c\\x0f\\x03\\x0b\\nK\\x14\\x11\\x03SDUFK\\n\\x0f\\x03\\x14\\x11\\x1c\\x0c\\x0f\\x03\\x0b\\nY\\x18\\x11\\x03FRYHW\\n\\x0f\\x03\\x13\\x11\\x19\\x13\\x13\\x13\\x13\\x13\\x13\\x13\\x13\\x13\\x13\\x13\\x13\\x13\\x13\\x14\\x0c\\x0f\\x03\\x0b\\nK\\x15\\x11\\x03PHULW\\n\\x0f\\x03\\x13\\x11\\x17\\x0c\\x0f\\x03\\x0b\\nY\\x14\\x11\\x03DOORZ\\n\\x0f\\x03\\x13\\x11\\x15\\x0c\\x0f\\x03\\x0b\\nY\\x15\\x11\\x03JULQG\\n\\x0f\\x03\\x13\\x11\\x14\\x0c\\x0f\\x03\\x0b\\nK\\x17\\x11\\x03OHSHU\\n\\x0f\\x03\\x13\\x11\\x14\\x0c@\\nY\\x16\\x11\\x03HORSH\\n0XOWLSOH\\x03UXQV3DUVH\\x0f\\x03ILOWHU\\x03RXW\\x03QRQ\\x10ILYH\\x10OHWWHU\\x0f\\x03VFRUH\\x0f\\x03DJJUHJDWH\\n&KRRVH\\x03\\x0bVRIW\\x03VHOI\\x10FRQVLVWHQF\\\\\"\\x0c\\x14\\x110D[\\x15\\x110D[\\x03ZLWKRXW\\x03YLRODWH\\x16\\x11\\')6\\nGĮŔũƜˤ\\x1dĦũòŝĎɿʛĭĵŤĵŗĎɾʛƘÊŝģŝĎʁʛŝÊĦĵĮƘÊŝģŝƘÊŝģŝ\\nĎʁʛˤŝÊĦĵĮˤʱŝũŗòʲſʂʛˤŝŗíŗƆˤʱĦĵƀʲſʀʛˤŝƜŗđĮĈˤʱĎƓĈĎʲʟʟ7KRXJKW\\x033URSRVDOVÊĈĈŗòĈÊŤòſʀʛˤ\\x89ŗòŤòĮƜƓĵũŝʞˤƚĦĵƀòŗƆʝˤˈˈˈˈˈˤŝũŗò6WDWH\\x03(YDOXDWRU\\x03\\x0bRYHU\\x03HDFK\\x03FOXH\\x0cſɾʛˤÉĵˤĎòÊŔʝˤƛĭˈŝˈˤʳʛʛʛʴˤđĭŔĵŝŝđæĦòſʂʛˤ#òŝƓççÊŤĵŗʞˤĭĵŗòˤíŗƆʝˤŝŗˈĮˈˤʳʛʛʛʴˤĭÊƆæòʟʟʱæÊçģƜŗÊçģʲĎʀʛĈŗÊĮíʟʟʱŝũæƜŗòòˤŔŗũĮòíʲĎʁʛˤŝÊĦĵĮĎʀʛˤĈŗÊĮíſʀʛˤŝƜŗđĮĈʟʟ\\')6\\x032UGHUĎʁʛˤŝÊĦĵĮˤʱŝũŗòʲſʂʛˤŝŗíŗƆˤʱĦĵƀʲſʀʛˤŝƜŗđĮĈˤʱĎƓĈĎʲʟʟ7KRXJKW\\x033URSRVDOVĎʁʛˤŝÊĦĵĮˤʱŝũŗòʲſʂʛˤŝŗíŗƆˤʱĦĵƀʲſʀʛˤŝƜŗđĮĈˤʱĎƓĈĎʲʟʟ7KRXJKW\\x033URSRVDOVĎʁʛˤŝÊĦĵĮˤʱŝũŗòʲſʂʛˤŝŗíŗƆˤʱĦĵƀʲſʀʛˤŝƜŗđĮĈˤʱĎƓĈĎʲʟʟ7KRXJKW\\x033URSRVDOVĎʁʛˤŝÊĦĵĮˤʱŝũŗòʲſʂʛˤŝŗíŗƆˤʱĦĵƀʲſʀʛˤŝƜŗđĮĈˤʱĎƓĈĎʲʟʟ7KRXJKW\\x033URSRVDOVʱÊʲʱæʲƛˤÊˤŝˤģˤŝĭˤĵˤƛˤĵˤŗˈˤˈˤˈˤˈˤˈŝˤÊˤĦˤĵˤĮˈˤˈˤˈˤˈˤˈFigure 6: In Mini Crosswords, (a) how thoughts are proposed and aggregated in a priority queue\\nfor depth-ﬁrst search (DFS), and (b) how a state is evaluated based on the possibility of ﬁlling in\\neach remaining word clue, and pruned if any remaining clue is deemed not possible to ﬁll by the LM.\\nThen DFS backtracks to the parent state and explore the next promising thought for clue.\\nthese across proposals to obtain a sorted list of next thoughts to explore (Figure 6(a)). For state\\nevaluations, we similarly translate each state into letter constraints for remaining clues, then evaluate\\nfor each clue if it is possible to ﬁll given the constraints. If any remaining clue is deemed “impossible”\\nto ﬁll in (e.g. “v1. To heap: tm s”), then the exploration of the state’s subtree is pruned and DFS\\nbacktracks to its parent to explore the next promising thought. We limit DFS search steps to 100, and\\nsimply render the deepest explored state (the ﬁrst explored one if multiple) into the ﬁnal output.\\nResults. As shown in Table 3, IO and CoT prompting methods perform poorly with a word-level\\nsuccess rate less than 16%, while ToT signiﬁcantly improves all metrics, achieving a word-level\\nsuccess rate of 60% and solving 4 out of 20 games. Such an improvement is not surprising, given IO\\nand CoT lack mechanisms to try different clues, make changes to decisions, or backtrack.\\nOracle and ablation studies. When outputting from the oracle best DFS state (instead of the\\nheuristically determined best state) per task, ToT performance is even higher and actually solves\\n7/20 games (Table 3, “+best state”), indicating our simple output heuristics can be readily improved.\\nInterestingly, sometimes when the crosswords game is actually solved, the state evaluator might still\\ndeem some words as “impossible” and prune — possibly because 5×5crosswords by design have\\nsome rare or obselete words that GPT-4 cannot recognize2. Given the state evaluation as a pruning\\nheuristic is imperfect, we also explore ablating the pruning, and ﬁnd the performance generally worse\\n(Table 3, “-prune”). However, it could actually ﬁnd the correct solution for 4/20 games (though only\\noutputting 1 via heuristic), 3 of which are games ToT+pruning cannot solve within 100 steps. Thus,\\nbetter heuristics for DFS pruning are critical for problem solving in this case. Lastly, we conﬁrm the\\nimportance of backtracking by running an ablation that keeps ﬁlling the most promising clue for at\\nmost 20 steps, allowing overwrites. This is similar to a “greedy” BFS search with breadth limit of\\nb= 1, and performs poorly with a word level success of only 20% (Table 3, “-backtrack”).\\n5 Related Work\\nPlanning and decision making. Smart planning and decision making are critical to achieving\\npredeﬁned goals. As they are trained on vast amount of world knowledge and human examples, LMs\\nare known to have already absorbed rich commonsense that makes it possible to propose reasonable\\nplans conditioned on problem setting and environmental states [ 10,39,34,11,32,38,37]. Our\\nproposed Tree-of-Thought approach extends existing planning formulations by considering multiple\\npotentially feasible plans simultaneously at each problem-solving step, and proceeding with the most\\npromising ones. The integration between thought sampling and value feedback organically integrates\\nplanning and decision-making mechanisms, enabling effective search inside a solution tree. On the\\nother hand, traditional decision-making procedures usually require training dedicated reward and\\npolicy models as in reinforcement learning (for example CHAI [ 30]), whereas we use the LM itself\\nto provide the value estimates for decision making.\\n2For example, “agend” is an obsolete form of “agendum”, but GPT-4 deems it a typo for “agenda”. External\\nretrieval or web interaction could augment LM for problem solving under knowledge uncertainty.\\n8'),\n",
       " Document(metadata={'source': './assets-resources/papers/tree-of-thoughts.pdf', 'page': 8}, page_content='Self-reﬂection. Using LLMs to assess the viability of their own predictions is becoming an in-\\ncreasingly important procedure in problem solving. [ 25,17,21] introduced the “self-reﬂection”\\nmechanism, in which LMs provide feedback to their generation candidates. [ 4] improves LMs code\\ngeneration accuracy by injecting feedback messages generated by the LM itself based on its code\\nexecution results. Similarly, [ 14] also introduces “critic” or review steps over the actions and states,\\ndeciding the next action to take in solving computer operation tasks. Another recent work very\\nrelevant to ours is “self-eval guided decoding” [ 36]. Similar to our method, self-eval decoding\\nalso follows a tree-search procedure with leaves sampled from stochastic beam search decoding,\\nwhich are then evaluated by LLM itself with carefully prepared self-eval prompts. Their approach\\nhowever, uses the PAL formulation [ 7] which represents thoughts as codes, which makes it difﬁcult\\nto tackle challenging tasks like creative writing which we consider in this paper. Our Tree-of-Thought\\nformulation is thus more versatile and handles challenging tasks on which GPT-4 only achieves very\\nlow accuracy with standard prompts.\\nProgram-guided LLM generation. Our proposal is also related to recent advancements that or-\\nganize LM’s behavior with symbolic program guidance. For example [ 24] embeds LMs in an\\nalgorithmic search procedure to help solve problems like question answering step-by-step, in which\\nthe search trees are expanded by relevant paragraphs that might provide answers. This approach\\nhowever differs from ours in that trees are expanded by sampling external paragraphs instead of the\\nLM’s own thoughts, and there is no reﬂection or voting steps. Another approach, LLM+P [ 15], goes\\none step further and delegates the actual planning process to a classical planner.\\nClassical search methods. Last but not least, our approach can be treated as a modern rendition\\nof classical search methods for problem solving. For example it can be considered as a heuristic\\nsearch algorithm like A* [ 8], in which the heuristic at each search node is provided by the LM’s\\nself-assessment. From this perspective, our method is also related to NeuroLogic A*esque decoding\\nproposed in [ 16], which is inspired by A* search but introduces look-ahead heuristics that are\\nefﬁcient for LMs to improve the beam-search or top-k sampling decoding. This method however is\\nconstrained to sentence generation tasks, whereas our framework are designed for complex, multi-step\\nproblem solving guarded by value feedback.\\n6 Discussion\\nLimitations and future directions. Deliberate search such as ToT might not be necessary for\\nmany existing tasks that GPT-4 already excels at, and as an initial step this work only explores\\nthree relatively simple tasks that challenges GPT-4 and calls of better search and planning abilities\\nincorporated with LMs. However, as we begin to deploy LMs for more real-world decision making\\napplications (e.g. coding, data analysis, robotics, etc.), more complex tasks could emerge and present\\nnew opportunities to study these research questions. Also, search methods like ToT requires more\\nresources (e.g. GPT-4 API cost) than sampling methods in order to improve task performances,\\nbut the modular ﬂexibility of ToT allows users to customize such performance-cost tradeoffs, and\\nongoing open-source efforts [ 29] should readily reduce such costs in the near future. Lastly, this work\\nfocuses on using an off-the-shelf LM, and ﬁne-tuning LMs using a ToT-style high-level counterfactual\\ndecision making (e.g. deliberating over potential choices for the next paragraph, instead of predicting\\nthe next token) might present opportunities to enhance the problem-solving capabilities of LMs.\\nBroader impact. ToT is a framework that empowers LMs to more autonomously and intelligently\\nmake decisions and solve problems. While current tasks are limited to reasoning and search problems,\\nfuture applications involving interaction with external environments or humans could bring potential\\ndanger, e.g. facilitating harmful uses of LMs. On the other hand, ToT also improves the interpretability\\nof model decisions and the opportunity for human alignment, as the resulting representations are\\nreadable, high-level language reasoning instead of implicit, low-level token values.\\nConclusion. The associative “System 1” of LMs can be beneﬁcially augmented by a “System 2”\\nbased on searching a tree of possible paths to the solution to a problem. The Tree of Thoughts\\nframework provides a way to translate classical insights about problem-solving into actionable\\nmethods for contemporary LMs. At the same time, LMs address a weakness of these classical\\nmethods, providing a way to solve complex problems that are not easily formalized, such as creative\\nwriting. We see this intersection of LMs with classical approaches to AI as an exciting direction for\\nfuture work.\\n9'),\n",
       " Document(metadata={'source': './assets-resources/papers/tree-of-thoughts.pdf', 'page': 9}, page_content='References\\n[1]T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam,\\nG. Sastry, A. Askell, et al. Language models are few-shot learners. Advances in neural\\ninformation processing systems , 33:1877–1901, 2020.\\n[2]C. Browne, E. J. Powley, D. Whitehouse, S. M. M. Lucas, P. I. Cowling, P. Rohlfshagen,\\nS. Tavener, D. P. Liebana, S. Samothrakis, and S. Colton. A survey of monte carlo tree search\\nmethods. IEEE Transactions on Computational Intelligence and AI in Games , 4:1–43, 2012.\\n[3]M. Campbell, A. J. Hoane Jr, and F.-h. Hsu. Deep blue. Artiﬁcial intelligence , 134(1-2):57–83,\\n2002.\\n[4]X. Chen, M. Lin, N. Sch ¨arli, and D. Zhou. Teaching large language models to self-debug, 2023.\\n[5]A. Chowdhery, S. Narang, J. Devlin, M. Bosma, G. Mishra, A. Roberts, P. Barham, H. W.\\nChung, C. Sutton, S. Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv\\npreprint arXiv:2204.02311 , 2022.\\n[6]N. D. Daw, Y . Niv, and P. Dayan. Uncertainty-based competition between prefrontal and\\ndorsolateral striatal systems for behavioral control. Nature neuroscience , 8(12):1704–1711,\\n2005.\\n[7]L. Gao, A. Madaan, S. Zhou, U. Alon, P. Liu, Y . Yang, J. Callan, and G. Neubig. Pal: Program-\\naided language models, 2023.\\n[8]P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of\\nminimum cost paths. IEEE Transactions on Systems Science and Cybernetics , 4(2):100–107,\\n1968. doi: 10.1109/TSSC.1968.300136.\\n[9]P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of\\nminimum cost paths. IEEE transactions on Systems Science and Cybernetics , 4(2):100–107,\\n1968.\\n[10] W. Huang, P. Abbeel, D. Pathak, and I. Mordatch. Language models as zero-shot planners:\\nExtracting actionable knowledge for embodied agents, 2022.\\n[11] W. Huang, F. Xia, T. Xiao, H. Chan, J. Liang, P. Florence, A. Zeng, J. Tompson, I. Mordatch,\\nY . Chebotar, et al. Inner monologue: Embodied reasoning through planning with language\\nmodels. arXiv preprint arXiv:2207.05608 , 2022.\\n[12] D. Kahneman. Thinking, fast and slow . Macmillan, 2011.\\n[13] D. Kahneman, S. Frederick, et al. Representativeness revisited: Attribute substitution in intuitive\\njudgment. Heuristics and biases: The psychology of intuitive judgment , 49(49-81):74, 2002.\\n[14] G. Kim, P. Baldi, and S. McAleer. Language models can solve computer tasks, 2023.\\n[15] B. Liu, Y . Jiang, X. Zhang, Q. Liu, S. Zhang, J. Biswas, and P. Stone. Llm+p: Empowering\\nlarge language models with optimal planning proﬁciency, 2023.\\n[16] X. Lu, S. Welleck, P. West, L. Jiang, J. Kasai, D. Khashabi, R. L. Bras, L. Qin, Y . Yu,\\nR. Zellers, N. A. Smith, and Y . Choi. Neurologic a*esque decoding: Constrained text generation\\nwith lookahead heuristics. In North American Chapter of the Association for Computational\\nLinguistics , 2021.\\n[17] A. Madaan, N. Tandon, P. Gupta, S. Hallinan, L. Gao, S. Wiegreffe, U. Alon, N. Dziri,\\nS. Prabhumoye, Y . Yang, S. Welleck, B. P. Majumder, S. Gupta, A. Yazdanbakhsh, and P. Clark.\\nSelf-reﬁne: Iterative reﬁnement with self-feedback, 2023.\\n[18] A. Newell, J. C. Shaw, and H. A. Simon. Report on a general problem solving program. In IFIP\\ncongress , volume 256, page 64. Pittsburgh, PA, 1959.\\n[19] A. Newell, H. A. Simon, et al. Human problem solving . Prentice-Hall, 1972.\\n10'),\n",
       " Document(metadata={'source': './assets-resources/papers/tree-of-thoughts.pdf', 'page': 10}, page_content='[20] OpenAI. Gpt-4 technical report. ArXiv , abs/2303.08774, 2023.\\n[21] D. Paul, M. Ismayilzada, M. Peyrard, B. Borges, A. Bosselut, R. West, and B. Faltings. Reﬁner:\\nReasoning feedback on intermediate representations, 2023.\\n[22] A. Radford, K. Narasimhan, T. Salimans, I. Sutskever, et al. Improving language understanding\\nby generative pre-training. OpenAI blog , 2018.\\n[23] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, I. Sutskever, et al. Language models are\\nunsupervised multitask learners. OpenAI blog , 1(8):9, 2019.\\n[24] I. Schlag, S. Sukhbaatar, A. Celikyilmaz, W. tau Yih, J. Weston, J. Schmidhuber, and X. Li.\\nLarge language model programs, 2023.\\n[25] N. Shinn, B. Labash, and A. Gopinath. Reﬂexion: an autonomous agent with dynamic memory\\nand self-reﬂection, 2023.\\n[26] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker,\\nM. Lai, A. Bolton, et al. Mastering the game of go without human knowledge. nature , 550\\n(7676):354–359, 2017.\\n[27] S. A. Sloman. The empirical case for two systems of reasoning. Psychological bulletin , 119(1):\\n3, 1996.\\n[28] K. E. Stanovich. Who is rational? Studies of individual differences in reasoning . Psychology\\nPress, 1999.\\n[29] H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozi `ere, N. Goyal,\\nE. Hambro, F. Azhar, et al. Llama: Open and efﬁcient foundation language models. arXiv\\npreprint arXiv:2302.13971 , 2023.\\n[30] S. Verma, J. Fu, S. Yang, and S. Levine. Chai: A chatbot ai for task-oriented dialogue with\\nofﬂine reinforcement learning. In Proceedings of the 2022 Conference of the North American\\nChapter of the Association for Computational Linguistics: Human Language Technologies ,\\npages 4471–4491, 2022.\\n[31] E. Wallace, N. Tomlin, A. Xu, K. Yang, E. Pathak, M. Ginsberg, and D. Klein. Automated\\ncrossword solving. arXiv preprint arXiv:2205.09665 , 2022.\\n[32] L. Wang, W. Xu, Y . Lan, Z. Hu, Y . Lan, R. K.-W. Lee, and E.-P. Lim. Plan-and-solve prompting:\\nImproving zero-shot chain-of-thought reasoning by large language models, 2023.\\n[33] X. Wang, J. Wei, D. Schuurmans, Q. Le, E. Chi, and D. Zhou. Self-consistency improves chain\\nof thought reasoning in language models. arXiv preprint arXiv:2203.11171 , 2022.\\n[34] Z. Wang, S. Cai, A. Liu, X. Ma, and Y . Liang. Describe, explain, plan and select: Interactive\\nplanning with large language models enables open-world multi-task agents, 2023.\\n[35] J. Wei, X. Wang, D. Schuurmans, M. Bosma, E. Chi, Q. Le, and D. Zhou. Chain of thought\\nprompting elicits reasoning in large language models. arXiv preprint arXiv:2201.11903 , 2022.\\n[36] Y . Xie, K. Kawaguchi, Y . Zhao, X. Zhao, M.-Y . Kan, J. He, and Q. Xie. Decomposition\\nenhances reasoning via self-evaluation guided decoding, 2023.\\n[37] S. Yang, O. Nachum, Y . Du, J. Wei, P. Abbeel, and D. Schuurmans. Foundation models for\\ndecision making: Problems, methods, and opportunities, 2023.\\n[38] S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y . Cao. ReAct: Synergizing\\nreasoning and acting in language models. arXiv preprint arXiv:2210.03629 , 2022.\\n[39] S. Zhang, Z. Chen, Y . Shen, M. Ding, J. B. Tenenbaum, and C. Gan. Planning with large\\nlanguage models for code generation. In The Eleventh International Conference on Learning\\nRepresentations , 2023. URL https://openreview.net/forum?id=Lr8cOOtYbfL .\\n11')]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "documents"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "page_content='Tree of Thoughts: Deliberate Problem Solving\n",
      "with Large Language Models\n",
      "Shunyu Yao\n",
      "Princeton UniversityDian Yu\n",
      "Google DeepMindJeffrey Zhao\n",
      "Google DeepMindIzhak Shafran\n",
      "Google DeepMind\n",
      "Thomas L. Grifﬁths\n",
      "Princeton UniversityYuan Cao\n",
      "Google DeepMindKarthik Narasimhan\n",
      "Princeton University\n",
      "Abstract\n",
      "Language models are increasingly being deployed for general problem solving\n",
      "across a wide range of tasks, but are still conﬁned to token-level, left-to-right\n",
      "decision-making processes during inference. This means they can fall short in\n",
      "tasks that require exploration, strategic lookahead, or where initial decisions play\n",
      "a pivotal role. To surmount these challenges, we introduce a new framework for\n",
      "language model inference, “Tree of Thoughts” (ToT), which generalizes over the\n",
      "popular “Chain of Thought” approach to prompting language models, and enables\n",
      "exploration over coherent units of text (“thoughts”) that serve as intermediate steps\n",
      "toward problem solving. ToT allows LMs to perform deliberate decision making\n",
      "by considering multiple different reasoning paths and self-evaluating choices to\n",
      "decide the next course of action, as well as looking ahead or backtracking when\n",
      "necessary to make global choices. Our experiments show that ToT signiﬁcantly\n",
      "enhances language models’ problem-solving abilities on three novel tasks requiring\n",
      "non-trivial planning or search: Game of 24, Creative Writing, and Mini Crosswords.\n",
      "For instance, in Game of 24, while GPT-4 with chain-of-thought prompting only\n",
      "solved 4% of tasks, our method achieved a success rate of 74%. Code repo with all\n",
      "prompts: https://github.com/ysymyth/tree-of-thought-llm .\n",
      "1 Introduction\n",
      "Originally designed to generate text, scaled-up versions of language models (LMs) such as GPT [ 22,\n",
      "23,1,20] and PaLM [ 5] have been shown to be increasingly capable of performing an ever wider\n",
      "range of tasks requiring mathematical, symbolic, commonsense, and knowledge reasoning. It is\n",
      "perhaps surprising that underlying all this progress is still the original autoregressive mechanism for\n",
      "generating text, which makes token-level decisions one by one and in a left-to-right fashion. Is such\n",
      "a simple mechanism sufﬁcient for a LM to be built toward a general problem solver? If not, what\n",
      "problems would challenge the current paradigm, and what should be alternative mechanisms?\n",
      "The literature on human cognition provides some clues to answer these questions. Research on “dual\n",
      "process” models suggests that people have two modes in which they engage with decisions – a fast,\n",
      "automatic, unconscious mode (“System 1”) and a slow, deliberate, conscious mode (“System 2”)\n",
      "[27,28,13,12]. These two modes have previously been connected to a variety of mathematical\n",
      "models used in machine learning. For example, research on reinforcement learning in humans and\n",
      "other animals has explored the circumstances under which they engage in associative “model free”\n",
      "learning or more deliberative “model based” planning [ 6]. The simple associative token-level choices\n",
      "of LMs are also reminiscent of “System 1”, and thus might beneﬁt from augmentation by a more\n",
      "deliberate “System 2” planning process that (1) maintains and explores diverse alternatives for current\n",
      "Preprint. Under review.arXiv:2305.10601v1  [cs.CL]  17 May 2023' metadata={'source': './assets-resources/papers/tree-of-thoughts.pdf', 'page': 0}\n",
      "page_content='GĮŔũƜ\n",
      "jũƜŔũƜGĮŔũƜ\n",
      "jũƜŔũƜʱÊʲˤGjʱæʲˤ\u001dĵÉGĮŔũƜ\n",
      "ˤjũƜŔũƜʱçʲˤ\u001dĵÉˁ\u001dʟʟʟʟaÊĠĵŗƓŤƆˤſĵŤòGĮŔũƜ\n",
      "ˤjũƜŔũƜʱíʲˤÉĵÉˤʱĵũŗŝʲʟʟʟʟʟʟˤˤʝˤƛĎĵũĈĎƜ)L[\u0003FRORU\u0003\u000bE\\\u0003<XTLDQ\f0DUN\u0003GLIIHUHQFH\u0003E\\\u0003FRORU\n",
      "GĮŔũƜ\n",
      "jũƜŔũƜGĮŔũƜ\n",
      "jũƜŔũƜGĮŔũƜ\n",
      "ˤjũƜŔũƜʱçʲˤòĦƙˤ\u001dĵĮŝƓŝŤòĮçƆˤƀƓƜĎˤ\u001dĵÉˤʱ\u001dĵÉˁ\u001dʲaÊĠĵŗƓŤƆˤſĵŤòGĮŔũƜ\n",
      "ˤjũƜŔũƜʱíʲˤÉŗòòˤĵƙˤĎĵũĈĎŤŝˤʱÉĵÉʲʟʟʟʟʟʟʟʟʟʟˤˤƛĎĵũĈĎƜ\n",
      "ʱçʲˤ\u001dĎÊđĮˤĵƙˤĎĵũĈĎƜˤŗĵĭŔƜđĮĈˤʱ\u001dĵÉʲʱÊʲˤGĮŔũƜˁjũƜŔũƜˤŗĵĭŔƜđĮĈˤʱGjʲFigure 1: Schematic illustrating various approaches to problem solving with LLMs. Each rectangle\n",
      "box represents a thought , which is a coherent language sequence that serves as an intermediate\n",
      "step toward problem solving. See concrete examples of how thoughts are generated, evaluated, and\n",
      "searched in Figures 2,4,6.\n",
      "choices instead of just picking one, and (2) evaluates its current status and actively looks ahead or\n",
      "backtracks to make more global decisions.\n",
      "To design such a planning process, we return to the origins of artiﬁcial intelligence (and cognitive\n",
      "science), drawing inspiration from the planning processes explored by Newell, Shaw, and Simon\n",
      "starting in the 1950s [ 18,19]. Newell and colleagues characterized problem solving [ 18] as search\n",
      "through a combinatorial problem space, represented as a tree. We thus propose the Tree of Thoughts\n",
      "(ToT) framework for general problem solving with language models. As Figure 1 illustrates, while\n",
      "existing methods (detailed below) sample continuous language sequences for problem solving, ToT\n",
      "actively maintains a tree of thoughts, where each thought is a coherent language sequence that serves\n",
      "as an intermediate step toward problem solving (Table 1). Such a high-level semantic unit allows the\n",
      "LM to self-evaluate the progress different intermediate thoughts make towards solving the problem\n",
      "through a deliberate reasoning process that is also instantiated in language (Figures 2,4,6). This\n",
      "implementation of search heuristics via LM self-evaluation and deliberation is novel, as previous\n",
      "search heuristics are either programmed or learned. Finally, we combine this language-based\n",
      "capability to generate and evaluate diverse thoughts with search algorithms, such as breadth-ﬁrst\n",
      "search (BFS) or depth-ﬁrst search (DFS), which allow systematic exploration of the tree of thoughts\n",
      "with lookahead and backtracking.\n",
      "Empirically, we propose three new problems that challenge existing LM inference methods even with\n",
      "the state-of-the-art language model, GPT-4 [ 20]: Game of 24, Creative Writing, and Crosswords\n",
      "(Table 1). These tasks require deductive, mathematical, commonsense, lexical reasoning abilities,\n",
      "and a way to incorporate systematic planning or search. We show ToT obtains superior results on\n",
      "all three tasks by being general and ﬂexible enough to support different levels of thoughts, different\n",
      "ways to generate and evaluate thoughts, and different search algorithms that adapt to the nature of\n",
      "different problems. We also analyze how such choices affect model performances via systematic\n",
      "ablations and discuss future directions to better train and use LMs.\n",
      "2 Background\n",
      "We ﬁrst formalize some existing methods that use large language models for problem-solving,\n",
      "which our approach is inspired by and later compared with. We use pθto denote a pre-trained LM\n",
      "with parameters θ, and lowercase letters x,y,z,s,···to denote a language sequence , i.e.x=\n",
      "(x[1],···,x[n])where eachx[i]is a token, so that pθ(x) =∏n\n",
      "i=1pθ(x[i]|x[1...i]). We use uppercase\n",
      "lettersS,···to denote a collection of language sequences.\n",
      "Input-output (IO) prompting is the most common way to turn a problem input xinto outputywith\n",
      "LM:y∼pθ(y|promptIO(x)), where promptIO(x)wraps inputxwith task instructions and/or few-\n",
      "shot input-output examples. For simplicity, let us denote pprompt\n",
      "θ(output|input ) =pθ(output|\n",
      "prompt (input )), so that IO prompting can be formulated as y∼pIO\n",
      "θ(y|x).\n",
      "2' metadata={'source': './assets-resources/papers/tree-of-thoughts.pdf', 'page': 1}\n",
      "page_content='Chain-of-thought (CoT) prompting [35] was proposed to address cases where the mapping of\n",
      "inputxto outputyis non-trivial (e.g. when xis a math question and yis the ﬁnal numerical answer).\n",
      "The key idea is to introduce a chain of thoughtsz1,···,znto bridgexandy, where each ziis a\n",
      "coherent language sequence that serves as a meaningful intermediate step toward problem solving\n",
      "(e.g.zicould be an intermediate equation for math QA). To solve problems with CoT, each thought\n",
      "zi∼pCoT\n",
      "θ(zi|x,z1···i−1)is sampled sequentially, then the output y∼pCoT\n",
      "θ(y|x,z1···n). In\n",
      "practice, [z1···n,y]∼pCoT\n",
      "θ(z1···n,y|x)is sampled as a continuous language sequence, and the\n",
      "decomposition of thoughts (e.g. is each zia phrase, a sentence, or a paragraph) is left ambiguous.\n",
      "Self-consistency with CoT (CoT-SC) [33] is an ensemble approach that samples ki.i.d. chains\n",
      "of thought: [z(i)\n",
      "1···n,y(i)]∼pCoT\n",
      "θ(z1···n,y|x) (i= 1···k), then returns the most frequent output:\n",
      "arg maxy#{i|y(i)=y}. CoT-SC improves upon CoT, because there are generally different\n",
      "thought processes for the same problem (e.g. different ways to prove the same theorem), and the\n",
      "output decision can be more faithful by exploring a richer set of thoughts. However, within each\n",
      "chain there is no local exploration of different thought steps, and the “most frequent” heuristic only\n",
      "applies when the output space is limited (e.g. multi-choice QA).\n",
      "3 Tree of Thoughts: Deliberate Problem Solving with LM\n",
      "A genuine problem-solving process involves the repeated use of available informa-\n",
      "tion to initiate exploration, which discloses, in turn, more information until a way\n",
      "to attain the solution is ﬁnally discovered.—— Newell et al. [18]\n",
      "Research on human problem-solving suggests that people search through a combinatorial problem-\n",
      "space – a tree where the nodes represent partial solutions, and the branches correspond to operators\n",
      "that modify them [ 18,19]. Which branch to take is determined by heuristics that help to navigate the\n",
      "problem-space and guide the problem-solver towards a solution. This perspective highlights two key\n",
      "shortcomings of existing approaches that use LMs to solve general problems: 1) Locally, they do not\n",
      "explore different continuations within a thought process – the branches of the tree. 2) Globally, they\n",
      "do not incorporate any type of planning, lookahead, or backtracking to help evaluate these different\n",
      "options – the kind of heuristic-guided search that seems characteristic of human problem-solving.\n",
      "To address these shortcomings, we introduce Tree of Thoughts (ToT) , a paradigm that allows LMs to\n",
      "explore multiple reasoning paths over thoughts (Figure 1(c)). ToT frames any problem as a search\n",
      "over a tree, where each node is a states= [x,z1···i]representing a partial solution with the input and\n",
      "the sequence of thoughts so far. A speciﬁc instantiation of ToT involves answering four questions:\n",
      "1. How to decompose the intermediate process into thought steps; 2. How to generate potential\n",
      "thoughts from each state; 3. How to heuristically evaluate states; 4. What search algorithm to use.\n",
      "1. Thought decomposition. While CoT samples thoughts coherently without explicit decomposition,\n",
      "ToT leverages problem properties to design and decompose intermediate thought steps. As Table 1\n",
      "shows, depending on different problems, a thought could be a couple of words (Crosswords), a line of\n",
      "equation (Game of 24), or a whole paragraph of writing plan (Creative Writing). In general, a thought\n",
      "should be “small” enough so that LMs can generate promising and diverse samples (e.g. generating\n",
      "a whole book is usually too “big” to be coherent), yet “big” enough so that LMs can evaluate its\n",
      "prospect toward problem solving (e.g. generating one token is usually too “small” to evaluate).\n",
      "2. Thought generator G(pθ,s,k).Given a tree state s= [x,z1···i], we consider two strategies to\n",
      "generatekcandidates for the next thought step:\n",
      "(a)Sample i.i.d. thoughts from a CoT prompt (Creative Writing, Figure 4): z(j)∼\n",
      "pCoT\n",
      "θ(zi+1|s) =pCoT\n",
      "θ(zi+1|x,z1···i) (j= 1···k). This works better when the thought\n",
      "space is rich (e.g. each thought is a paragraph), and i.i.d. samples lead to diversity;\n",
      "(b)Propose thoughts sequentially using a “propose prompt” (Game of 24, Figure 2; Crosswords,\n",
      "Figure 6): [z(1),···,z(k)]∼ppropose\n",
      "θ(z(1···k)\n",
      "i+1|s). This works better when the thought\n",
      "space is more constrained (e.g. each thought is just a word or a line), so proposing different\n",
      "thoughts in the same context avoids duplication.\n",
      "3. State evaluator V(pθ,S).Given a frontier of different states, the state evaluator evaluates the\n",
      "progress they make towards solving the problem, serving as a heuristic for the search algorithm\n",
      "to determine which states to keep exploring and in which order. While heuristics are a standard\n",
      "approach to solving search problems, they are typically either programmed (e.g. DeepBlue [ 3]) or\n",
      "3' metadata={'source': './assets-resources/papers/tree-of-thoughts.pdf', 'page': 2}\n",
      "page_content='learned (e.g. AlphaGo [ 26]). We propose a third alternative, by using the LM to deliberately reason\n",
      "about states. When applicable, such a deliberate heuristic can be more ﬂexible than programmed\n",
      "rules, and more sample-efﬁcient than learned models. Similar to the thought generator, we consider\n",
      "two strategies to evaluate states either independently or together:\n",
      "(a)Value each state independently: V(pθ,S)(s)∼pvalue\n",
      "θ(v|s)∀s∈S, where a value\n",
      "prompt reasons about the state sto generate a scalar value v(e.g. 1-10) or a classiﬁca-\n",
      "tion (e.g. sure/likely/impossible) that could be heuristically turned into a value. The basis\n",
      "of such evaluative reasoning can vary across problems and thought steps. In this work, we\n",
      "explore evaluation via few lookahead simulations (e.g. quickly conﬁrm that 5, 5, 14 can\n",
      "reach 24 via 5 + 5 + 14, or “hot l” can mean “inn” via ﬁlling “e” in “ ”) plus commonsense\n",
      "(e.g. 1 2 3 are too small to reach 24, or no word can start with “tzxc”). While the former\n",
      "might promote “good” states, the latter could help eliminate “bad” states. Such valuations\n",
      "do not need to be perfect, and only need to be approximately\n",
      "(b)Vote across states: V(pθ,S)(s) =1[s=s∗], where a “good” state s∗∼pvote\n",
      "θ(s∗|S)is\n",
      "voted out based on deliberately comparing different states in Sin a vote prompt. When\n",
      "problem success is harder to directly value (e.g. passage coherency), it is natural to to instead\n",
      "compare different partial solutions and vote for the most promising one. This is similar\n",
      "in spirit to a “step-wise” self-consistency strategy, i.e. cast “which state to explore” as a\n",
      "multi-choice QA, and use LM samples to vote for it.\n",
      "For both strategies, we could prompt the LM multiple times to aggregate the value or vote results to\n",
      "trade time/resource/cost for more faithful/robust heuristics.\n",
      "Algorithm 1 ToT-BFS(x,pθ,G,k,V,T,b )\n",
      "Require: Inputx, LMpθ, thought generator G()\n",
      "& size limitk, states evaluator V(), step limitT,\n",
      "breadth limit b.\n",
      "S0←{x}\n",
      "fort= 1,···,Tdo\n",
      "S′\n",
      "t←{[s,z]|s∈St−1,zt∈G(pθ,s,k)}\n",
      "Vt←V(pθ,S′\n",
      "t)\n",
      "St←arg maxS⊂S′\n",
      "t,|S|=b∑\n",
      "s∈SVt(s)\n",
      "end for\n",
      "returnG(pθ,arg maxs∈STVT(s),1)Algorithm 2 ToT-DFS(s,t,pθ,G,k,V,T,v th)\n",
      "Require: Current state s, stept, LMpθ, thought\n",
      "generatorG()and size limit k, states evaluator\n",
      "V(), step limitT, thresholdvth\n",
      "ift>T then record output G(pθ,s,1)\n",
      "end if\n",
      "fors′∈G(pθ,s,k)do⊿sorted candidates\n",
      "ifV(pθ,{s′})(s)>vthres then⊿pruning\n",
      "DFS(s′,t+ 1)\n",
      "end if\n",
      "end for\n",
      "4. Search algorithm. Finally, within the ToT framework, one can plug and play different search\n",
      "algorithms depending on the tree structure. We explore two relatively simple search algorithms and\n",
      "leave more advanced ones (e.g. A* [9], MCTS [2]) for future work:\n",
      "(a)Breadth-ﬁrst search (BFS) (Algorithm 1) maintains a set of the bmost promising states\n",
      "per step. This is used for Game of 24 and Creative Writing where the tree depth is limit\n",
      "(T≤3), and initial thought steps can be evaluated and pruned to a small set ( b≤5).\n",
      "(b)Depth-ﬁrst search (DFS) (Algorithm 2) explores the most promising state ﬁrst, until the\n",
      "ﬁnal output is reached ( t > T ), or the state evaluator deems it impossible to solve the\n",
      "problem from the current s(V(pθ,{s})(s)≤vthfor a value threshold vth). In the latter\n",
      "case, the subtree from sispruned to trade exploration for exploitation. In both cases, DFS\n",
      "backtracks to the parent state of sto continue exploration.\n",
      "Conceptually, ToT has several beneﬁts as a method for general problem-solving with LMs: (1) Gener-\n",
      "ality. IO, CoT, CoT-SC, and self-reﬁnement can be seen as special cases of ToT (i.e. trees of limited\n",
      "depth and breadth; Figure 1). (2) Modularity. The base LM, as well as the thought decomposition,\n",
      "generation, evaluation, and search procedures can all be varied independently. (3) Adaptability .\n",
      "Different problem properties, LM capabilities, and resource constraints can be accommodated. (4)\n",
      "Convenience. No extra training is needed, just a pre-trained LM is sufﬁcient. The next section will\n",
      "show how these conceptual beneﬁts translate to strong empirical performance in different problems.\n",
      "4 Experiments\n",
      "We propose three tasks that are hard even when sampling from the state-of-the-art language model,\n",
      "GPT-4 [ 20], using standard IO prompting or chain-of-thought (CoT) prompting. We show how\n",
      "4' metadata={'source': './assets-resources/papers/tree-of-thoughts.pdf', 'page': 3}\n",
      "page_content='Game of 24 Creative Writing 5x5 Crosswords\n",
      "Input 4 numbers (4 9 10 13) 4 random sentences 10 clues (h1. presented;..)\n",
      "Output An equation to reach 24\n",
      "(13-9)*(10-4)=24A passage of 4 paragraphs\n",
      "ending in the 4 sentences5x5 letters: SHOWN;\n",
      "WIRRA; A V AIL; ...\n",
      "Thoughts 3 intermediate equations\n",
      "(13-9=4 (left 4,4,10); 10-\n",
      "4=6 (left 4,6); 4*6=24)A short writing plan\n",
      "(1. Introduce a book that\n",
      "connects...)Words to ﬁll in for clues:\n",
      "(h1. shown; v5. naled; ...)\n",
      "#ToT steps 3 1 5-10 (variable)\n",
      "Table 1: Task overview. Input, output, thought examples are in blue.\n",
      "deliberate search in trees of thoughts (ToT) produces better results, and more importantly, interesting\n",
      "and promising new ways to use language models to solve problems requiring search or planning.\n",
      "Unless otherwise stated, we perform experiments using a Chat Completion mode GPT-41with a\n",
      "sampling temperature of 0.7.\n",
      "4.1 Game of 24\n",
      "Game of 24 is a mathematical reasoning challenge, where the goal is to use 4 numbers and basic\n",
      "arithmetic operations (+-*/) to obtain 24. For example, given input “4 9 10 13”, a solution output\n",
      "could be “(10 - 4) * (13 - 9) = 24”.\n",
      "ʳĵĮòˤòƅÊĭŔĦòʴˤGĮŔũƜʝˤʁˤʆˤɾɽˤɾʀĵŝŝđæĦòˤĮòƅƜˤŝŤòŔŝʝˤˤˤ3URSRVH\u00033URPSWʁˤ̌ˤʆˤ̐ˤɾʀˤʱĦòƙƜʝˤɾɽˤɾʀˤɾʀʲɾɽˤˊˤʁˤ̐ˤʃˤʱĦòƙƜʝˤʃˤʆˤɾʀʲʳʛʛʛĭĵŗòˤĦđĮòŝʟʴ7KRXJKW\u0003*HQHUDWLRQ/0)ſÊĦũÊŤòˤđƙˤĈƓſòĮˤĮũĭæòŗŝˤçÊĮˤŗòÊçĎˤɿʁˤʱŝũŗòʫĦđģòĦƆʫđĭŔĵŝŝđæĦòʲɾɽˤɾʁʝˤɾɽˤ̌ˤɾʁˤ̐ˤɿʁʛˤŝũŗòʳĭĵŗòˤòƅÊĭŔĦòŝʴɾɽˤɾʀˤɾʀ9DOXH\u00033URPSWʱɾʀˤˊˤɾɽʲˤʦˤɾʀˤ̐ˤʀˤʦˤɾʀˤ̐ˤʀʆɾɽˤ̌ˤɾʀˤ̌ˤɾʀˤ̐ˤʀʃĎòŗòˤƓŝˤĮĵˤƀÊƆˤƘĵˤĵæŤÊđĮˤɿʁˤƀƓƜĎˤƛĎòŝòˤĮũĭæòŗŝʛˤđĭŔĵŝŝđæĦò7KRXJKW\u0003(YDOXDWLRQʱæʲʱçʲ/0GĮŔũƜʝˤʁˤʆˤɾɽˤɾʀʁ̌ʆ̐ɾʀʱĦòƙƜʝˤɾɽˤɾʀˤɾʀʲɾɽˁʁ̐ʃʱĦòƙƜʝˤʃˤʆˤɾʀʲʟʟɾʀˁʃ̐ʄʱĦòƙƜʝˤʄˤʆʲɾʀˁʆ̐ʁʱĦòƙƜʝˤʁˤʃʲʟʟʁʦʃ̐ɿʁʱĦòƙƜʝˤɿʁʲʁ̌ʃ̐ɾɽʱĦòƙƜʝˤɾɽʲʟʟʱÊʲ\n",
      "ʳĵĮòˤòƅÊĭŔĦòʴˤGĮŔũƜʝˤʁˤʆˤɾɽˤɾʀĵŝŝđæĦòˤĮòƅƜˤŝŤòŔŝʝˤˤˤ\u000bD\f\u00033URSRVH\u00033URPSWʁˤ̌ˤʆˤ̐ˤɾʀˤʱĦòƙƜʝˤɾɽˤɾʀˤɾʀʲɾɽˤˊˤʁˤ̐ˤʃˤʱĦòƙƜʝˤʃˤʆˤɾʀʲʳʛʛʛĭĵŗòˤĦđĮòŝʟʴ7KRXJKW\u0003*HQHUDWLRQ/0)ſÊĦũÊŤòˤđƙˤĈƓſòĮˤĮũĭæòŗŝˤçÊĮˤŗòÊçĎˤɿʁˤʱŝũŗòʫĦđģòĦƆʫđĭŔĵŝŝđæĦòʲɾɽˤɾʁʝˤɾɽˤ̌ˤɾʁˤ̐ˤɿʁʛˤŝũŗòʳĭĵŗòˤòƅÊĭŔĦòŝʴɾɽˤɾʀˤɾʀ\u000bE\f\u00039DOXH\u00033URPSWʱɾʀˤˊˤɾɽʲˤʦˤɾʀˤ̐ˤʀˤʦˤɾʀˤ̐ˤʀʆɾɽˤ̌ˤɾʀˤ̌ˤɾʀˤ̐ˤʀʃˤĎòŗòˤƓŝˤĮĵˤƀÊƆˤƘĵˤĵæŤÊđĮˤɿʁˤƀƓƜĎˤƛĎòŝòˤæƓĈˤĮũĭæòŗŝʛˤđĭŔĵŝŝđæĦò7KRXJKW\u0003(YDOXDWLRQ/0GĮŔũƜʝˤʁˤʆˤɾɽˤɾʀʁ̌ʆ̐ɾʀʱĦòƙƜʝˤɾɽˤɾʀˤɾʀʲɾɽˁʁ̐ʃʱĦòƙƜʝˤʃˤʆˤɾʀʲʟʟɾʀˁʃ̐ʄʱĦòƙƜʝˤʄˤʆʲɾʀˁʆ̐ʁʱĦòƙƜʝˤʁˤʃʲʟʟʁʦʃ̐ɿʁʱĦòƙƜʝˤɿʁʲʁ̌ʃ̐ɾɽʱĦòƙƜʝˤɾɽʲʟʟ)L[\u0003FRORU\u0003\u000bE\\\u0003<XTLDQ\f0DUN\u0003GLII\u0003SURPSW\u0003ZLWK\u0003FRORU\n",
      "Figure 2: ToT in a game of 24. The LM is prompted for (a) thought generation and (b) valuation.\n",
      "Task Setup. We scrape data from 4nums.com, which has 1,362 games that are sorted from easy to\n",
      "hard by human solving time, and use a subset of relatively hard games indexed 901-1,000 for testing.\n",
      "For each task, we consider the output as success if it is a valid equation that equals 24 and uses the\n",
      "input numbers each exactly once. We report the success rate across 100 games as the metric.\n",
      "Baselines. We use a standard input-output (IO) prompt with 5 in-context examples. For chain-of-\n",
      "thought (CoT) prompting, we augment each input-output pair with 3 intermediate equations, each\n",
      "operating on two remaining numbers. For example, given input “4 9 10 13”, the thoughts could be\n",
      "“13 - 9 = 4 (left: 4 4 10); 10 - 4 = 6 (left: 4 6); 4 * 6 = 24 (left: 24)”. For each game, we sample IO\n",
      "and CoT prompting for 100 times for average performance. We also consider a CoT self-consistency\n",
      "baseline, which takes the majority output from 100 CoT samples, and an iterative-reﬁne approach on\n",
      "top of an IO sample for at most 10iterations. At each iteration, the LM is conditioned on all previous\n",
      "history to “reﬂect on your mistakes and generate a reﬁned answer” if the output is incorrect. Note\n",
      "that it uses groundtruth feedback signals about equation correctness.\n",
      "ToT Setup. To frame Game of 24 into ToT, it is natural to decompose the thoughts into 3 steps,\n",
      "each an intermediate equation. As shown in Figure 2(a), at each tree node, we exact the “left”\n",
      "numbers and prompt the LM to propose some possible next steps. The same “propose prompt” is\n",
      "used for all 3 thought steps, though it only has one example with 4 input numbers. We perform a\n",
      "breadth-ﬁrst search (BFS) in ToT, where at each step we keep the best b= 5candidates. To perform\n",
      "deliberate BFS in ToT, as shown in Figure 2(b), we prompt LM to evaluate each thought candidate as\n",
      "“sure/maybe/impossible” with regard to reaching 24. The aim is to promote correct partial solutions\n",
      "that can be verdicted within few lookahead trials, and eliminate impossible partial solutions based on\n",
      "“too big/small” commonsense, and keep the rest “maybe”. We sample values 3times for each thought.\n",
      "1Experiments were done between May 5-16, 2023.\n",
      "5' metadata={'source': './assets-resources/papers/tree-of-thoughts.pdf', 'page': 4}\n",
      "page_content='Method Success\n",
      "IO prompt 7.3%\n",
      "CoT prompt 4.0%\n",
      "CoT-SC (k=100) 9.0%\n",
      "ToT (ours) (b=1) 45%\n",
      "ToT (ours) (b=5) 74%\n",
      "IO + Reﬁne (k=10) 27%\n",
      "IO(best of 100) 33%\n",
      "CoT (best of 100) 49%\n",
      "Table 2: Game of 24 Results.\n",
      "0 25 50 75 1000.20.40.6(a) Success rate with nodes visited\n",
      "IO (best of k)\n",
      "CoT (best of k)\n",
      "ToT (b=1...5)\n",
      "1 2 3 4Correct0.00.20.40.6(b) Samples failed at each step\n",
      "CoT\n",
      "ToT (b=5) Figure 3: Game of 24 (a) scale analysis & (b) error analysis.\n",
      "Results. As shown in Table 2, IO, CoT, and CoT-SC prompting methods perform badly on the task,\n",
      "achieving only 7.3%, 4.0%, and 9.0% success rates. In contrast, ToT with a breadth of b= 1already\n",
      "achieves a success rate of 45%, whileb= 5 achieves 74%. We also consider an oracle setup for\n",
      "IO/CoT, by calculating the success rate using best of ksamples (1≤k≤100) . To compare IO/CoT\n",
      "(best of k) with ToT, we consider calculating the tree nodes visited per task in ToT across b= 1···5,\n",
      "and map the 5 success rates in Figure 3(a), treating IO/CoT (best of k) as visitingknodes in a bandit.\n",
      "Not surprisingly, CoT scales better than IO, and best of 100 CoT samples achieve a success rate of\n",
      "49%, but still much worse than exploring more nodes in ToT ( b>1).\n",
      "Error Analysis. Figure 3(b) breaks down at which step CoT and ToT samples fail the task, i.e. the\n",
      "thought (in CoT) or all bthoughts (in ToT) are invalid or impossible to reach 24. Notably, around\n",
      "60% of CoT samples already failed the task after generating the ﬁrst step, or equivalently, the ﬁrst\n",
      "three words (e.g. “ 4 + 9 ”). This highlights the issues with direct left-to-right decoding.\n",
      "4.2 Creative writing\n",
      "Next, we invent a creative writing task where the input is 4 random sentences and the output should\n",
      "be a coherent passage with 4 paragraphs that end in the 4 input sentences respectively. Such a task is\n",
      "open-ended and exploratory, and challenges creative thinking as well as high-level planning.\n",
      "Task setup. We sample random sentences from randomwordgenerator.com to form 100 inputs, and\n",
      "there is no groundtruth passage for each input constraint. As we ﬁnd that GPT-4 can follow the\n",
      "input constraints most of the time, we focus on evaluating passage coherency in two ways: using a\n",
      "GPT-4 zero-shot prompt to provide a 1-10 scalar score, or using human judgments to compare pairs\n",
      "of outputs from different methods. For the former, we sample 5 scores and average them for each task\n",
      "output, and we ﬁnd these 5 scores usually consistent, with a standard deviation of around 0.56on\n",
      "average across outputs. For the latter, we employ a subset of the authors in a blind study to compare\n",
      "the coherency of CoT vs. ToT generated passage pairs, where the order of passages is random ﬂipped\n",
      "over 100 inputs.\n",
      "Baselines. Given the creative nature of the task, both IO and CoT prompts are zero-shot. While the\n",
      "former prompts the LM to directly generate a coherent passage given input constraints, the latter\n",
      "prompts the LM to ﬁrst make a brief plan then write the passage, i.e. the plan serves as the intermediate\n",
      "thought step. We generate 10 IO and CoT samples per task. We also consider an iterative-reﬁne\n",
      "(k≤5) method on top of a random IO sample for each task, where the LM is conditioned on input\n",
      "constraints and the last generated passage to decide if the passage is already “perfectly coherent”,\n",
      "and if not generate a reﬁned one.\n",
      "ToT setup. We build a ToT with depth 2 (and only 1 intermediate thought step) — the LM ﬁrst\n",
      "generatesk= 5plans and votes for the best one (Figure 4), then similarly generate k= 5passages\n",
      "based on the best plan then vote for the best one. Here the breadth limit b= 1, as only one choice is\n",
      "kept per step. A simple zero-shot vote prompt (“analyze choices below, then conclude which is most\n",
      "promising for the instruction”) is used to sample 5 votes at both steps.\n",
      "Results. Figure 5(a) shows average GPT-4 scores across 100 tasks, where ToT (7.56) is deemed to\n",
      "generate more coherent passages than IO (6.19) and CoT (6.93) on average. While such an automatic\n",
      "metric might be noisy, Figure 5(b) conﬁrms the ﬁnding by showing that humans prefer ToT over\n",
      "CoT in 41 out of 100 passage pairs, while only prefer CoT over ToT in 21 (other 38 pairs are found\n",
      "“similarly coherent”). Lastly, iterative-reﬁne is more effective on this natural language task, where\n",
      "6' metadata={'source': './assets-resources/papers/tree-of-thoughts.pdf', 'page': 5}\n",
      "page_content='µŗƓŤòˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòˤĵƙˤʁˤŝĎĵŗƜˤŔÊŗÊĈŗÊŔĎŝʛˤĎòˤòĮíˤŝòĮŤòĮçòˤĵƙˤòÊçĎˤŔÊŗÊĈŗÊŔĎˤĭũŝƜˤæòʝˤɾʛˤGƜˤƓŝĮ˙ƛˤíđƙƙƓçũĦƜˤƘĵˤíĵˤÊˤĎÊĮíŝŤÊĮíˤđƙˤƆĵũˤĠũŝƜˤŝŤÊĮíˤĵĮˤƆĵũŗˤĎÊĮíŝʛˤɿʛˤGƜˤçÊũĈĎƜˤĎđĭˤĵƙƙˤĈũÊŗíˤƛĎÊƜˤŝŔÊçòˤŝĭòĦĦòíˤĵƙˤŝòÊŗòíˤŝŤòÊģʛˤʀʛˤµĎòĮˤŝĎòˤíƓíĮ˒ƛˤĦđģòˤÊˤĈũƆˤƀĎĵˤƀÊŝˤƛŗƆđĮĈˤƘĵˤŔƓçģˤĎòŗˤũŔʜˤŝĎòˤŝŤÊŗŤòíˤũŝđĮĈˤŝƓĈĮˤĦÊĮĈũÊĈòʛˤʁʛˤ)ÊçĎˤŔòŗŝĵĮˤƀĎĵˤģĮĵƀŝˤƆĵũˤĎÊŝˤÊˤíđƙćòŗòĮƜˤŔòŗçòŔƜƓĵĮˤĵƙˤƀĎĵˤƆĵũˤÊŗòʛˤˤɾʛˤGĮƜŗĵíũçòˤÊĮíˤòƅŔĦÊđĮˤƛĎòˤƘòçĎĮƓŖũòˤĵƙˤíĵđĮĈˤÊˤĎÊĮíŝŤÊĮíˤɿʛˤƀƓŤçĎˤƘĵˤÊˤŝŤĵŗƆˤÊæĵũƜˤÊĮˤÊŝƜŗĵĮÊũƜ˙ŝˤƚđŗŝƜˤƛđĭòˤđĮˤŝŔÊçòˤʀʛˤ#òŝçŗđæòˤÊˤŝƓƜũÊƜƓĵĮˤƀĎòŗòˤÊˤƀĵĭÊĮˤũŝòŝˤŝƓĈĮˤĦÊĮĈũÊĈòˤƘĵˤÊſĵƓíˤũĮƀÊĮŤòíˤÊƜŤòĮƜƓĵĮˤʁʛˤĎòˤƚđĮÊĦˤŔÊŗÊĈŗÊŔĎˤòƅŔĦÊđĮŝˤĎĵƀˤòſòŗƆĵĮòˤĎÊŝˤíđƙćòŗòĮƜˤŔòŗçòŔƜƓĵĮŝˤĵƙˤĵƜĎòŗŝɾʛˤGĮƜŗĵíũçƜƓĵĮˤƘĵˤÊĮˤũĮũŝũÊĦˤŝòĦƙˊĎòĦŔˤæĵĵģʜˤĭòĮƜƓĵĮđĮĈˤÊˤĎÊĮíŝŤÊĮíˤÊŝˤÊˤĭòŤÊŔĎĵŗˤƗĵŗˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʛˤɿʛˤ#ƓŝçũŝŝˤƛĎòˤũĮòƅŔòçŤòíˤƛĎđĮĈŝˤĦòÊŗĮòíˤƚŗĵĭˤÊŝƜŗĵĮÊũŤŝʜˤđĮçĦũíđĮĈˤƛĎòˤŝĭòĦĦˤĵƙˤŝŔÊçòʛˤʀʛˤ#òŝçŗđæòˤÊˤƀĵĭÊĮ˙ŝˤçĦòſòŗˤƘÊçƜƓçˤƗĵŗˤÊſĵƓíđĮĈˤũĮƀÊĮŤòíˤÊƜŤòĮƜƓĵĮˤÊƜˤÊˤæÊŗʛˤʁʛˤ\u001dĵĮŤòĭŔĦÊŤòˤĎĵƀˤíđƙćòŗòĮƜˤŔòŗçòŔƜƓĵĮŝˤĵƙˤĵĮòŝòĦƙˤçÊĮˤŝĎÊŔòˤĵĮò˙ŝˤƓíòĮƜƓŤƆʛʱÊʲˤGĮŔũƜʱæʲˤĦÊĮŝʱʀˤĭĵŗòˤĵĭƓƜŤòíʲʱçʲˤ´ĵŤòŝ\u0001ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\u001dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝʟˤ\u001dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛʱɽʫʂˤſĵŤòŝʲ\u0001ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\u001dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝʟˤ\u001dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛ\u0001ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\u001dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝʟˤ\u001dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛ\u0001ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\u001dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝʟˤ\u001dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛ\u0001ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\u001dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤʳʛʛʛʴˤ\u001dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛʱʀʫʂˤſĵŤòŝʲʟɾɿGĮŔũƜĦÊĮˤɾĦÊĮˤɿʟʟÊŝŝÊĈòɾÊŝŝÊĈòɿʟʟ)L[\u0003FRORU\u0003\u000bE\\\u0003<XTLDQ\fµŗƓŤòˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòˤĵƙˤʁˤŝĎĵŗƜˤŔÊŗÊĈŗÊŔĎŝʛˤĎòˤòĮíˤŝòĮŤòĮçòˤĵƙˤòÊçĎˤŔÊŗÊĈŗÊŔĎˤĭũŝƜˤæòʝˤɾʛˤGƜˤƓŝĮ˙ƛˤíđƙƙƓçũĦƜˤƘĵˤíĵˤÊˤĎÊĮíŝŤÊĮíˤđƙˤƆĵũˤĠũŝƜˤŝŤÊĮíˤĵĮˤƆĵũŗˤĎÊĮíŝʛˤɿʛˤGƜˤçÊũĈĎƜˤĎđĭˤĵƙƙˤĈũÊŗíˤƛĎÊƜˤŝŔÊçòˤŝĭòĦĦòíˤĵƙˤŝòÊŗòíˤŝŤòÊģʛˤʀʛˤµĎòĮˤŝĎòˤíƓíĮ˒ƛˤĦđģòˤÊˤĈũƆˤƀĎĵˤƀÊŝˤƛŗƆđĮĈˤƘĵˤŔƓçģˤĎòŗˤũŔʜˤŝĎòˤŝŤÊŗŤòíˤũŝđĮĈˤŝƓĈĮˤĦÊĮĈũÊĈòʛˤʁʛˤ)ÊçĎˤŔòŗŝĵĮˤƀĎĵˤģĮĵƀŝˤƆĵũˤĎÊŝˤÊˤíđƙćòŗòĮƜˤŔòŗçòŔƜƓĵĮˤĵƙˤƀĎĵˤƆĵũˤÊŗòʛˤˤɾʛˤGĮƜŗĵíũçòˤÊĮíˤòƅŔĦÊđĮˤƛĎòˤƘòçĎĮƓŖũòˤĵƙˤíĵđĮĈˤÊˤĎÊĮíŝŤÊĮíˤɿʛˤƀƓŤçĎˤƘĵˤÊˤŝŤĵŗƆˤÊæĵũƜˤÊĮˤÊŝƜŗĵĮÊũƜ˙ŝˤƚđŗŝƜˤƛđĭòˤđĮˤŝŔÊçòˤʀʛˤ#òŝçŗđæòˤÊˤŝƓƜũÊƜƓĵĮˤƀĎòŗòˤÊˤƀĵĭÊĮˤũŝòŝˤŝƓĈĮˤĦÊĮĈũÊĈòˤƘĵˤÊſĵƓíˤũĮƀÊĮŤòíˤÊƜŤòĮƜƓĵĮˤʁʛˤĎòˤƚđĮÊĦˤŔÊŗÊĈŗÊŔĎˤòƅŔĦÊđĮŝˤĎĵƀˤòſòŗƆĵĮòˤĎÊŝˤíđƙćòŗòĮƜˤŔòŗçòŔƜƓĵĮŝˤĵƙˤĵƜĎòŗŝɾʛˤGĮƜŗĵíũçƜƓĵĮˤƘĵˤÊĮˤũĮũŝũÊĦˤŝòĦƙˊĎòĦŔˤæĵĵģʜˤĭòĮƜƓĵĮđĮĈˤÊˤĎÊĮíŝŤÊĮíˤÊŝˤÊˤĭòŤÊŔĎĵŗˤƗĵŗˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʛˤɿʛˤ#ƓŝçũŝŝˤƛĎòˤũĮòƅŔòçŤòíˤƛĎđĮĈŝˤĦòÊŗĮòíˤƚŗĵĭˤÊŝƜŗĵĮÊũŤŝʜˤđĮçĦũíđĮĈˤƛĎòˤŝĭòĦĦˤĵƙˤŝŔÊçòʛˤʀʛˤ#òŝçŗđæòˤÊˤƀĵĭÊĮ˙ŝˤçĦòſòŗˤƘÊçƜƓçˤƗĵŗˤÊſĵƓíđĮĈˤũĮƀÊĮŤòíˤÊƜŤòĮƜƓĵĮˤÊƜˤÊˤæÊŗʛˤʁʛˤ\u001dĵĮŤòĭŔĦÊŤòˤĎĵƀˤíđƙćòŗòĮƜˤŔòŗçòŔƜƓĵĮŝˤĵƙˤĵĮòŝòĦƙˤçÊĮˤŝĎÊŔòˤĵĮò˙ŝˤƓíòĮƜƓŤƆʛʱÊʲˤGĮŔũƜʱæʲˤĦÊĮŝʱçʲˤ´ĵŤòŝ\u0001ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\u001dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤʳʛʛʛʴˤ\u001dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛGĮŔũƜĦÊĮˤɾˤĦÊĮˤɿˤˤʟʟÊŝŝÊĈòɾÊŝŝÊĈòɿʟʟɽʫʂˤſĵŤòŝĦÊĮˤɾˤˤˤʟʛʟʛɾʟʛɿʟʟʀʫʂˤſĵŤòŝĦÊĮˤʀˁʂˤˤˤ8VH\u0003UHG\u0012JUHHQ\u0003WR\u0003VKRZ\u0003ILQDO\u0003FKRLFH\n",
      "ĮʫʂˤſĵŤòŝĦÊĮˤɿˤˤˤ\n",
      "\u0001ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\u001dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤʳʛʛʛʴˤ\u001dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛ\u0001ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\u001dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤʳʛʛʛʴˤ\u001dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛ\u0001ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\u001dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤʳʛʛʛʴˤ\u001dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛ\u0001ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\u001dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤʳʛʛʛʴˤ\u001dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛFigure 4: A step of deliberate search in a randomly picked Creative Writing task. Given the input, the\n",
      "LM samples 5 different plans, then votes 5 times to decide which plan is best. The majority choice is\n",
      "used to consequently write the output passage with the same sample-vote procedure.\n",
      "IO CoT ToT IO\n",
      "+refineToT\n",
      "+refine468\n",
      "(a) GPT-4 coherency scores\n",
      "CoT > ToT Similar ToT > CoT010203040\n",
      "213841(b) Human coherency comparison\n",
      "Figure 5: Creative Writing results.Method Success Rate (%)\n",
      "Letter Word Game\n",
      "IO 38.7 14 0\n",
      "CoT 40.6 15.6 1\n",
      "ToT (ours) 78 60 20\n",
      "+best state 82.4 67.5 35\n",
      "-prune 65.4 41.5 5\n",
      "-backtrack 54.6 20 5\n",
      "Table 3: Mini Crosswords results.\n",
      "it improves IO coherency score from 6.19 to 7.67, and ToT coherency score from 7.56 to 7.91. We\n",
      "believe it could be thought of as a third approach to thought generation in the ToT framework, where\n",
      "new thoughts can arise from reﬁning old thoughts instead of i.i.d. or sequentially generated.\n",
      "4.3 Mini Crosswords\n",
      "In Game of 24 and Creative Writing, ToT is relatively shallow — at most 3 thought steps are needed\n",
      "to reach the ﬁnal output. Here we explore 5×5mini crosswords as a harder search problem involving\n",
      "natural language. Again, the goal is not just to solve the task, as more general crosswords can be\n",
      "readily solved with specialized NLP pipelines [ 31] that leverages large-scale retrieval instead of LM.\n",
      "Rather, we aim to explore the limit of LM as a general problem solver that explores its own thoughts\n",
      "and guides its own exploration with deliberate reasoning as heuristics.\n",
      "Task Setup. We scrape data from GooBix, which contains 156 games of 5×5mini crosswords. As\n",
      "we observe adjacent games contain similar clues, we use 20 games with indices 1,6,···,91,96for\n",
      "testing, and games 136,141,146,151,156for prompting. For each task, the input describes the 5\n",
      "horizontal clues and 5 vertical clues, and the output should be a board of 5×5 = 25 letters to solve\n",
      "the crosswords. For evaluation, we consider three levels of success: the portion of correct letters (25\n",
      "per game), words (10 per game), and games.\n",
      "Baselines. We provide 5 example input-output pairs in the IO prompt, and in the CoT prompt\n",
      "additionally include intermediate words in the order h1..5 then v1..5. We run each prompt for 10\n",
      "samples and average the results.\n",
      "ToT Setup. We leverage a depth-ﬁrst search (Algorithm 2) that keeps exploring the most promising\n",
      "subsequent word clue until the state is no longer promising, then backtrack to the parent state to\n",
      "explore alternative thoughts. To make search tractable, subsequent thoughts are constrained not to\n",
      "change any ﬁlled words or letters, so that the ToT has at most 10 intermediate steps. For thought\n",
      "generation, at each state we translate all existing thoughts (e.g. “h2.motor; h1.tasks” for the state\n",
      "in Figure 6(a)) into letter constraints for remaining clues (e.g. “v1.To heap: tm ;...”) and prompt\n",
      "a proposal prompt 5times to come up with candidates for where and what to ﬁll in the next word.\n",
      "Importantly, we also prompt the LM to give a conﬁdence level for different thoughts, and aggregate\n",
      "7' metadata={'source': './assets-resources/papers/tree-of-thoughts.pdf', 'page': 6}\n",
      "page_content='>\u000b\n",
      "Y\u0016\u0011\u0003HORSH\n",
      "\u000f\u0003\u0016\u0011\u0015\f\u000f\u0003\u000b\n",
      "K\u0015\u0011\u0003YDOXH\n",
      "\u000f\u0003\u0015\u0011\u0013\f\u000f\u0003\u000b\n",
      "K\u0014\u0011\u0003SDUFK\n",
      "\u000f\u0003\u0014\u0011\u001c\f\u000f\u0003\u000b\n",
      "Y\u0018\u0011\u0003FRYHW\n",
      "\u000f\u0003\u0013\u0011\u0019\u0013\u0013\u0013\u0013\u0013\u0013\u0013\u0013\u0013\u0013\u0013\u0013\u0013\u0013\u0014\f\u000f\u0003\u000b\n",
      "K\u0015\u0011\u0003PHULW\n",
      "\u000f\u0003\u0013\u0011\u0017\f\u000f\u0003\u000b\n",
      "Y\u0014\u0011\u0003DOORZ\n",
      "\u000f\u0003\u0013\u0011\u0015\f\u000f\u0003\u000b\n",
      "Y\u0015\u0011\u0003JULQG\n",
      "\u000f\u0003\u0013\u0011\u0014\f\u000f\u0003\u000b\n",
      "K\u0017\u0011\u0003OHSHU\n",
      "\u000f\u0003\u0013\u0011\u0014\f@\n",
      "Y\u0016\u0011\u0003HORSH\n",
      "0XOWLSOH\u0003UXQV3DUVH\u000f\u0003ILOWHU\u0003RXW\u0003QRQ\u0010ILYH\u0010OHWWHU\u000f\u0003VFRUH\u000f\u0003DJJUHJDWH\n",
      "&KRRVH\u0003\u000bVRIW\u0003VHOI\u0010FRQVLVWHQF\\\"\f\u0014\u00110D[\u0015\u00110D[\u0003ZLWKRXW\u0003YLRODWH\u0016\u0011')6\n",
      "GĮŔũƜˤ\u001dĦũòŝĎɿʛĭĵŤĵŗĎɾʛƘÊŝģŝĎʁʛŝÊĦĵĮƘÊŝģŝƘÊŝģŝ\n",
      "ĎʁʛˤŝÊĦĵĮˤʱŝũŗòʲſʂʛˤŝŗíŗƆˤʱĦĵƀʲſʀʛˤŝƜŗđĮĈˤʱĎƓĈĎʲʟʟ7KRXJKW\u00033URSRVDOVÊĈĈŗòĈÊŤòſʀʛˤŗòŤòĮƜƓĵũŝʞˤƚĦĵƀòŗƆʝˤˈˈˈˈˈˤŝũŗò6WDWH\u0003(YDOXDWRU\u0003\u000bRYHU\u0003HDFK\u0003FOXH\fſɾʛˤÉĵˤĎòÊŔʝˤƛĭˈŝˈˤʳʛʛʛʴˤđĭŔĵŝŝđæĦòſʂʛˤ#òŝƓççÊŤĵŗʞˤĭĵŗòˤíŗƆʝˤŝŗˈĮˈˤʳʛʛʛʴˤĭÊƆæòʟʟʱæÊçģƜŗÊçģʲĎʀʛĈŗÊĮíʟʟʱŝũæƜŗòòˤŔŗũĮòíʲĎʁʛˤŝÊĦĵĮĎʀʛˤĈŗÊĮíſʀʛˤŝƜŗđĮĈʟʟ')6\u00032UGHUĎʁʛˤŝÊĦĵĮˤʱŝũŗòʲſʂʛˤŝŗíŗƆˤʱĦĵƀʲſʀʛˤŝƜŗđĮĈˤʱĎƓĈĎʲʟʟ7KRXJKW\u00033URSRVDOVĎʁʛˤŝÊĦĵĮˤʱŝũŗòʲſʂʛˤŝŗíŗƆˤʱĦĵƀʲſʀʛˤŝƜŗđĮĈˤʱĎƓĈĎʲʟʟ7KRXJKW\u00033URSRVDOVĎʁʛˤŝÊĦĵĮˤʱŝũŗòʲſʂʛˤŝŗíŗƆˤʱĦĵƀʲſʀʛˤŝƜŗđĮĈˤʱĎƓĈĎʲʟʟ7KRXJKW\u00033URSRVDOVĎʁʛˤŝÊĦĵĮˤʱŝũŗòʲſʂʛˤŝŗíŗƆˤʱĦĵƀʲſʀʛˤŝƜŗđĮĈˤʱĎƓĈĎʲʟʟ7KRXJKW\u00033URSRVDOVʱÊʲʱæʲƛˤÊˤŝˤģˤŝĭˤĵˤƛˤĵˤŗˈˤˈˤˈˤˈˤˈŝˤÊˤĦˤĵˤĮˈˤˈˤˈˤˈˤˈFigure 6: In Mini Crosswords, (a) how thoughts are proposed and aggregated in a priority queue\n",
      "for depth-ﬁrst search (DFS), and (b) how a state is evaluated based on the possibility of ﬁlling in\n",
      "each remaining word clue, and pruned if any remaining clue is deemed not possible to ﬁll by the LM.\n",
      "Then DFS backtracks to the parent state and explore the next promising thought for clue.\n",
      "these across proposals to obtain a sorted list of next thoughts to explore (Figure 6(a)). For state\n",
      "evaluations, we similarly translate each state into letter constraints for remaining clues, then evaluate\n",
      "for each clue if it is possible to ﬁll given the constraints. If any remaining clue is deemed “impossible”\n",
      "to ﬁll in (e.g. “v1. To heap: tm s”), then the exploration of the state’s subtree is pruned and DFS\n",
      "backtracks to its parent to explore the next promising thought. We limit DFS search steps to 100, and\n",
      "simply render the deepest explored state (the ﬁrst explored one if multiple) into the ﬁnal output.\n",
      "Results. As shown in Table 3, IO and CoT prompting methods perform poorly with a word-level\n",
      "success rate less than 16%, while ToT signiﬁcantly improves all metrics, achieving a word-level\n",
      "success rate of 60% and solving 4 out of 20 games. Such an improvement is not surprising, given IO\n",
      "and CoT lack mechanisms to try different clues, make changes to decisions, or backtrack.\n",
      "Oracle and ablation studies. When outputting from the oracle best DFS state (instead of the\n",
      "heuristically determined best state) per task, ToT performance is even higher and actually solves\n",
      "7/20 games (Table 3, “+best state”), indicating our simple output heuristics can be readily improved.\n",
      "Interestingly, sometimes when the crosswords game is actually solved, the state evaluator might still\n",
      "deem some words as “impossible” and prune — possibly because 5×5crosswords by design have\n",
      "some rare or obselete words that GPT-4 cannot recognize2. Given the state evaluation as a pruning\n",
      "heuristic is imperfect, we also explore ablating the pruning, and ﬁnd the performance generally worse\n",
      "(Table 3, “-prune”). However, it could actually ﬁnd the correct solution for 4/20 games (though only\n",
      "outputting 1 via heuristic), 3 of which are games ToT+pruning cannot solve within 100 steps. Thus,\n",
      "better heuristics for DFS pruning are critical for problem solving in this case. Lastly, we conﬁrm the\n",
      "importance of backtracking by running an ablation that keeps ﬁlling the most promising clue for at\n",
      "most 20 steps, allowing overwrites. This is similar to a “greedy” BFS search with breadth limit of\n",
      "b= 1, and performs poorly with a word level success of only 20% (Table 3, “-backtrack”).\n",
      "5 Related Work\n",
      "Planning and decision making. Smart planning and decision making are critical to achieving\n",
      "predeﬁned goals. As they are trained on vast amount of world knowledge and human examples, LMs\n",
      "are known to have already absorbed rich commonsense that makes it possible to propose reasonable\n",
      "plans conditioned on problem setting and environmental states [ 10,39,34,11,32,38,37]. Our\n",
      "proposed Tree-of-Thought approach extends existing planning formulations by considering multiple\n",
      "potentially feasible plans simultaneously at each problem-solving step, and proceeding with the most\n",
      "promising ones. The integration between thought sampling and value feedback organically integrates\n",
      "planning and decision-making mechanisms, enabling effective search inside a solution tree. On the\n",
      "other hand, traditional decision-making procedures usually require training dedicated reward and\n",
      "policy models as in reinforcement learning (for example CHAI [ 30]), whereas we use the LM itself\n",
      "to provide the value estimates for decision making.\n",
      "2For example, “agend” is an obsolete form of “agendum”, but GPT-4 deems it a typo for “agenda”. External\n",
      "retrieval or web interaction could augment LM for problem solving under knowledge uncertainty.\n",
      "8' metadata={'source': './assets-resources/papers/tree-of-thoughts.pdf', 'page': 7}\n",
      "page_content='Self-reﬂection. Using LLMs to assess the viability of their own predictions is becoming an in-\n",
      "creasingly important procedure in problem solving. [ 25,17,21] introduced the “self-reﬂection”\n",
      "mechanism, in which LMs provide feedback to their generation candidates. [ 4] improves LMs code\n",
      "generation accuracy by injecting feedback messages generated by the LM itself based on its code\n",
      "execution results. Similarly, [ 14] also introduces “critic” or review steps over the actions and states,\n",
      "deciding the next action to take in solving computer operation tasks. Another recent work very\n",
      "relevant to ours is “self-eval guided decoding” [ 36]. Similar to our method, self-eval decoding\n",
      "also follows a tree-search procedure with leaves sampled from stochastic beam search decoding,\n",
      "which are then evaluated by LLM itself with carefully prepared self-eval prompts. Their approach\n",
      "however, uses the PAL formulation [ 7] which represents thoughts as codes, which makes it difﬁcult\n",
      "to tackle challenging tasks like creative writing which we consider in this paper. Our Tree-of-Thought\n",
      "formulation is thus more versatile and handles challenging tasks on which GPT-4 only achieves very\n",
      "low accuracy with standard prompts.\n",
      "Program-guided LLM generation. Our proposal is also related to recent advancements that or-\n",
      "ganize LM’s behavior with symbolic program guidance. For example [ 24] embeds LMs in an\n",
      "algorithmic search procedure to help solve problems like question answering step-by-step, in which\n",
      "the search trees are expanded by relevant paragraphs that might provide answers. This approach\n",
      "however differs from ours in that trees are expanded by sampling external paragraphs instead of the\n",
      "LM’s own thoughts, and there is no reﬂection or voting steps. Another approach, LLM+P [ 15], goes\n",
      "one step further and delegates the actual planning process to a classical planner.\n",
      "Classical search methods. Last but not least, our approach can be treated as a modern rendition\n",
      "of classical search methods for problem solving. For example it can be considered as a heuristic\n",
      "search algorithm like A* [ 8], in which the heuristic at each search node is provided by the LM’s\n",
      "self-assessment. From this perspective, our method is also related to NeuroLogic A*esque decoding\n",
      "proposed in [ 16], which is inspired by A* search but introduces look-ahead heuristics that are\n",
      "efﬁcient for LMs to improve the beam-search or top-k sampling decoding. This method however is\n",
      "constrained to sentence generation tasks, whereas our framework are designed for complex, multi-step\n",
      "problem solving guarded by value feedback.\n",
      "6 Discussion\n",
      "Limitations and future directions. Deliberate search such as ToT might not be necessary for\n",
      "many existing tasks that GPT-4 already excels at, and as an initial step this work only explores\n",
      "three relatively simple tasks that challenges GPT-4 and calls of better search and planning abilities\n",
      "incorporated with LMs. However, as we begin to deploy LMs for more real-world decision making\n",
      "applications (e.g. coding, data analysis, robotics, etc.), more complex tasks could emerge and present\n",
      "new opportunities to study these research questions. Also, search methods like ToT requires more\n",
      "resources (e.g. GPT-4 API cost) than sampling methods in order to improve task performances,\n",
      "but the modular ﬂexibility of ToT allows users to customize such performance-cost tradeoffs, and\n",
      "ongoing open-source efforts [ 29] should readily reduce such costs in the near future. Lastly, this work\n",
      "focuses on using an off-the-shelf LM, and ﬁne-tuning LMs using a ToT-style high-level counterfactual\n",
      "decision making (e.g. deliberating over potential choices for the next paragraph, instead of predicting\n",
      "the next token) might present opportunities to enhance the problem-solving capabilities of LMs.\n",
      "Broader impact. ToT is a framework that empowers LMs to more autonomously and intelligently\n",
      "make decisions and solve problems. While current tasks are limited to reasoning and search problems,\n",
      "future applications involving interaction with external environments or humans could bring potential\n",
      "danger, e.g. facilitating harmful uses of LMs. On the other hand, ToT also improves the interpretability\n",
      "of model decisions and the opportunity for human alignment, as the resulting representations are\n",
      "readable, high-level language reasoning instead of implicit, low-level token values.\n",
      "Conclusion. The associative “System 1” of LMs can be beneﬁcially augmented by a “System 2”\n",
      "based on searching a tree of possible paths to the solution to a problem. The Tree of Thoughts\n",
      "framework provides a way to translate classical insights about problem-solving into actionable\n",
      "methods for contemporary LMs. At the same time, LMs address a weakness of these classical\n",
      "methods, providing a way to solve complex problems that are not easily formalized, such as creative\n",
      "writing. We see this intersection of LMs with classical approaches to AI as an exciting direction for\n",
      "future work.\n",
      "9' metadata={'source': './assets-resources/papers/tree-of-thoughts.pdf', 'page': 8}\n",
      "page_content='References\n",
      "[1]T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam,\n",
      "G. Sastry, A. Askell, et al. Language models are few-shot learners. Advances in neural\n",
      "information processing systems , 33:1877–1901, 2020.\n",
      "[2]C. Browne, E. J. Powley, D. Whitehouse, S. M. M. Lucas, P. I. Cowling, P. Rohlfshagen,\n",
      "S. Tavener, D. P. Liebana, S. Samothrakis, and S. Colton. A survey of monte carlo tree search\n",
      "methods. IEEE Transactions on Computational Intelligence and AI in Games , 4:1–43, 2012.\n",
      "[3]M. Campbell, A. J. Hoane Jr, and F.-h. Hsu. Deep blue. Artiﬁcial intelligence , 134(1-2):57–83,\n",
      "2002.\n",
      "[4]X. Chen, M. Lin, N. Sch ¨arli, and D. Zhou. Teaching large language models to self-debug, 2023.\n",
      "[5]A. Chowdhery, S. Narang, J. Devlin, M. Bosma, G. Mishra, A. Roberts, P. Barham, H. W.\n",
      "Chung, C. Sutton, S. Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv\n",
      "preprint arXiv:2204.02311 , 2022.\n",
      "[6]N. D. Daw, Y . Niv, and P. Dayan. Uncertainty-based competition between prefrontal and\n",
      "dorsolateral striatal systems for behavioral control. Nature neuroscience , 8(12):1704–1711,\n",
      "2005.\n",
      "[7]L. Gao, A. Madaan, S. Zhou, U. Alon, P. Liu, Y . Yang, J. Callan, and G. Neubig. Pal: Program-\n",
      "aided language models, 2023.\n",
      "[8]P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of\n",
      "minimum cost paths. IEEE Transactions on Systems Science and Cybernetics , 4(2):100–107,\n",
      "1968. doi: 10.1109/TSSC.1968.300136.\n",
      "[9]P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of\n",
      "minimum cost paths. IEEE transactions on Systems Science and Cybernetics , 4(2):100–107,\n",
      "1968.\n",
      "[10] W. Huang, P. Abbeel, D. Pathak, and I. Mordatch. Language models as zero-shot planners:\n",
      "Extracting actionable knowledge for embodied agents, 2022.\n",
      "[11] W. Huang, F. Xia, T. Xiao, H. Chan, J. Liang, P. Florence, A. Zeng, J. Tompson, I. Mordatch,\n",
      "Y . Chebotar, et al. Inner monologue: Embodied reasoning through planning with language\n",
      "models. arXiv preprint arXiv:2207.05608 , 2022.\n",
      "[12] D. Kahneman. Thinking, fast and slow . Macmillan, 2011.\n",
      "[13] D. Kahneman, S. Frederick, et al. Representativeness revisited: Attribute substitution in intuitive\n",
      "judgment. Heuristics and biases: The psychology of intuitive judgment , 49(49-81):74, 2002.\n",
      "[14] G. Kim, P. Baldi, and S. McAleer. Language models can solve computer tasks, 2023.\n",
      "[15] B. Liu, Y . Jiang, X. Zhang, Q. Liu, S. Zhang, J. Biswas, and P. Stone. Llm+p: Empowering\n",
      "large language models with optimal planning proﬁciency, 2023.\n",
      "[16] X. Lu, S. Welleck, P. West, L. Jiang, J. Kasai, D. Khashabi, R. L. Bras, L. Qin, Y . Yu,\n",
      "R. Zellers, N. A. Smith, and Y . Choi. Neurologic a*esque decoding: Constrained text generation\n",
      "with lookahead heuristics. In North American Chapter of the Association for Computational\n",
      "Linguistics , 2021.\n",
      "[17] A. Madaan, N. Tandon, P. Gupta, S. Hallinan, L. Gao, S. Wiegreffe, U. Alon, N. Dziri,\n",
      "S. Prabhumoye, Y . Yang, S. Welleck, B. P. Majumder, S. Gupta, A. Yazdanbakhsh, and P. Clark.\n",
      "Self-reﬁne: Iterative reﬁnement with self-feedback, 2023.\n",
      "[18] A. Newell, J. C. Shaw, and H. A. Simon. Report on a general problem solving program. In IFIP\n",
      "congress , volume 256, page 64. Pittsburgh, PA, 1959.\n",
      "[19] A. Newell, H. A. Simon, et al. Human problem solving . Prentice-Hall, 1972.\n",
      "10' metadata={'source': './assets-resources/papers/tree-of-thoughts.pdf', 'page': 9}\n",
      "page_content='[20] OpenAI. Gpt-4 technical report. ArXiv , abs/2303.08774, 2023.\n",
      "[21] D. Paul, M. Ismayilzada, M. Peyrard, B. Borges, A. Bosselut, R. West, and B. Faltings. Reﬁner:\n",
      "Reasoning feedback on intermediate representations, 2023.\n",
      "[22] A. Radford, K. Narasimhan, T. Salimans, I. Sutskever, et al. Improving language understanding\n",
      "by generative pre-training. OpenAI blog , 2018.\n",
      "[23] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, I. Sutskever, et al. Language models are\n",
      "unsupervised multitask learners. OpenAI blog , 1(8):9, 2019.\n",
      "[24] I. Schlag, S. Sukhbaatar, A. Celikyilmaz, W. tau Yih, J. Weston, J. Schmidhuber, and X. Li.\n",
      "Large language model programs, 2023.\n",
      "[25] N. Shinn, B. Labash, and A. Gopinath. Reﬂexion: an autonomous agent with dynamic memory\n",
      "and self-reﬂection, 2023.\n",
      "[26] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker,\n",
      "M. Lai, A. Bolton, et al. Mastering the game of go without human knowledge. nature , 550\n",
      "(7676):354–359, 2017.\n",
      "[27] S. A. Sloman. The empirical case for two systems of reasoning. Psychological bulletin , 119(1):\n",
      "3, 1996.\n",
      "[28] K. E. Stanovich. Who is rational? Studies of individual differences in reasoning . Psychology\n",
      "Press, 1999.\n",
      "[29] H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozi `ere, N. Goyal,\n",
      "E. Hambro, F. Azhar, et al. Llama: Open and efﬁcient foundation language models. arXiv\n",
      "preprint arXiv:2302.13971 , 2023.\n",
      "[30] S. Verma, J. Fu, S. Yang, and S. Levine. Chai: A chatbot ai for task-oriented dialogue with\n",
      "ofﬂine reinforcement learning. In Proceedings of the 2022 Conference of the North American\n",
      "Chapter of the Association for Computational Linguistics: Human Language Technologies ,\n",
      "pages 4471–4491, 2022.\n",
      "[31] E. Wallace, N. Tomlin, A. Xu, K. Yang, E. Pathak, M. Ginsberg, and D. Klein. Automated\n",
      "crossword solving. arXiv preprint arXiv:2205.09665 , 2022.\n",
      "[32] L. Wang, W. Xu, Y . Lan, Z. Hu, Y . Lan, R. K.-W. Lee, and E.-P. Lim. Plan-and-solve prompting:\n",
      "Improving zero-shot chain-of-thought reasoning by large language models, 2023.\n",
      "[33] X. Wang, J. Wei, D. Schuurmans, Q. Le, E. Chi, and D. Zhou. Self-consistency improves chain\n",
      "of thought reasoning in language models. arXiv preprint arXiv:2203.11171 , 2022.\n",
      "[34] Z. Wang, S. Cai, A. Liu, X. Ma, and Y . Liang. Describe, explain, plan and select: Interactive\n",
      "planning with large language models enables open-world multi-task agents, 2023.\n",
      "[35] J. Wei, X. Wang, D. Schuurmans, M. Bosma, E. Chi, Q. Le, and D. Zhou. Chain of thought\n",
      "prompting elicits reasoning in large language models. arXiv preprint arXiv:2201.11903 , 2022.\n",
      "[36] Y . Xie, K. Kawaguchi, Y . Zhao, X. Zhao, M.-Y . Kan, J. He, and Q. Xie. Decomposition\n",
      "enhances reasoning via self-evaluation guided decoding, 2023.\n",
      "[37] S. Yang, O. Nachum, Y . Du, J. Wei, P. Abbeel, and D. Schuurmans. Foundation models for\n",
      "decision making: Problems, methods, and opportunities, 2023.\n",
      "[38] S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y . Cao. ReAct: Synergizing\n",
      "reasoning and acting in language models. arXiv preprint arXiv:2210.03629 , 2022.\n",
      "[39] S. Zhang, Z. Chen, Y . Shen, M. Ding, J. B. Tenenbaum, and C. Gan. Planning with large\n",
      "language models for code generation. In The Eleventh International Conference on Learning\n",
      "Representations , 2023. URL https://openreview.net/forum?id=Lr8cOOtYbfL .\n",
      "11' metadata={'source': './assets-resources/papers/tree-of-thoughts.pdf', 'page': 10}\n"
     ]
    }
   ],
   "source": [
    "for doc in documents:\n",
    "    print(doc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tree of Thoughts: Deliberate Problem Solving\n",
      "with Large Language Models\n",
      "Shunyu Yao\n",
      "Princeton UniversityDian Yu\n",
      "Google DeepMindJeffrey Zhao\n",
      "Google DeepMindIzhak Shafran\n",
      "Google DeepMind\n",
      "Thomas L. Grifﬁths\n",
      "Princeton UniversityYuan Cao\n",
      "Google DeepMindKarthik Narasimhan\n",
      "Princeton University\n",
      "Abstract\n",
      "Language models are increasingly being deployed for general problem solving\n",
      "across a wide range of tasks\n",
      "GĮŔũƜ\n",
      "jũƜŔũƜGĮŔũƜ\n",
      "jũƜŔũƜʱÊʲˤGjʱæʲˤ\u001dĵÉGĮŔũƜ\n",
      "ˤjũƜŔũƜʱçʲˤ\u001dĵÉˁ\u001dʟʟʟʟaÊĠĵŗƓŤƆˤſĵŤòGĮŔũƜ\n",
      "ˤjũƜŔũƜʱíʲˤÉĵÉˤʱĵũŗŝʲʟʟʟʟʟʟˤˤʝˤƛĎĵũĈĎƜ)L[\u0003FRORU\u0003\u000bE\\\u0003<XTLDQ\f0DUN\u0003GLIIHUHQFH\u0003E\\\u0003FRORU\n",
      "GĮŔũƜ\n",
      "jũƜŔũƜGĮŔũƜ\n",
      "jũƜŔũƜGĮŔũƜ\n",
      "ˤjũƜŔũƜʱçʲˤòĦƙˤ\u001dĵĮŝƓŝŤòĮçƆˤƀƓƜĎˤ\u001dĵÉˤʱ\u001dĵÉˁ\u001dʲaÊĠĵŗƓŤƆˤſĵŤòGĮŔũƜ\n",
      "ˤjũƜŔũƜʱíʲˤÉŗòòˤĵƙˤĎĵũĈĎŤŝˤʱÉĵÉʲʟʟʟʟʟʟʟʟʟʟˤˤƛĎĵũĈĎƜ\n",
      "ʱçʲˤ\u001dĎÊđĮˤĵƙˤĎĵũĈĎƜˤŗĵĭŔƜđĮĈˤʱ\u001dĵÉʲʱÊʲˤGĮŔũƜˁjũƜŔũƜˤŗĵĭŔƜđĮĈˤʱGjʲFigure 1: Schematic\n",
      "Chain-of-thought (CoT) prompting [35] was proposed to address cases where the mapping of\n",
      "inputxto outputyis non-trivial (e.g. when xis a math question and yis the ﬁnal numerical answer).\n",
      "The key idea is to introduce a chain of thoughtsz1,···,znto bridgexandy, where each ziis a\n",
      "coherent language sequence that serves as a meaningful intermediate step toward problem solving\n",
      "(e.g.zicould be an interme\n",
      "learned (e.g. AlphaGo [ 26]). We propose a third alternative, by using the LM to deliberately reason\n",
      "about states. When applicable, such a deliberate heuristic can be more ﬂexible than programmed\n",
      "rules, and more sample-efﬁcient than learned models. Similar to the thought generator, we consider\n",
      "two strategies to evaluate states either independently or together:\n",
      "(a)Value each state independently: V(\n",
      "Game of 24 Creative Writing 5x5 Crosswords\n",
      "Input 4 numbers (4 9 10 13) 4 random sentences 10 clues (h1. presented;..)\n",
      "Output An equation to reach 24\n",
      "(13-9)*(10-4)=24A passage of 4 paragraphs\n",
      "ending in the 4 sentences5x5 letters: SHOWN;\n",
      "WIRRA; A V AIL; ...\n",
      "Thoughts 3 intermediate equations\n",
      "(13-9=4 (left 4,4,10); 10-\n",
      "4=6 (left 4,6); 4*6=24)A short writing plan\n",
      "(1. Introduce a book that\n",
      "connects...)W\n",
      "Method Success\n",
      "IO prompt 7.3%\n",
      "CoT prompt 4.0%\n",
      "CoT-SC (k=100) 9.0%\n",
      "ToT (ours) (b=1) 45%\n",
      "ToT (ours) (b=5) 74%\n",
      "IO + Reﬁne (k=10) 27%\n",
      "IO(best of 100) 33%\n",
      "CoT (best of 100) 49%\n",
      "Table 2: Game of 24 Results.\n",
      "0 25 50 75 1000.20.40.6(a) Success rate with nodes visited\n",
      "IO (best of k)\n",
      "CoT (best of k)\n",
      "ToT (b=1...5)\n",
      "1 2 3 4Correct0.00.20.40.6(b) Samples failed at each step\n",
      "CoT\n",
      "ToT (b=5) Figure 3: Game of 24 (a\n",
      "µŗƓŤòˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòˤĵƙˤʁˤŝĎĵŗƜˤŔÊŗÊĈŗÊŔĎŝʛˤĎòˤòĮíˤŝòĮŤòĮçòˤĵƙˤòÊçĎˤŔÊŗÊĈŗÊŔĎˤĭũŝƜˤæòʝˤɾʛˤGƜˤƓŝĮ˙ƛˤíđƙƙƓçũĦƜˤƘĵˤíĵˤÊˤĎÊĮíŝŤÊĮíˤđƙˤƆĵũˤĠũŝƜˤŝŤÊĮíˤĵĮˤƆĵũŗˤĎÊĮíŝʛˤɿʛˤGƜˤçÊũĈĎƜˤĎđĭˤĵƙƙˤĈũÊŗíˤƛĎÊƜˤŝŔÊçòˤŝĭòĦĦòíˤĵƙˤŝòÊŗòíˤŝŤòÊģʛˤʀʛˤµĎòĮˤŝĎòˤíƓíĮ˒ƛˤĦđģòˤÊˤĈũƆˤƀĎĵˤƀÊŝˤƛŗƆđĮĈˤƘĵˤŔƓçģˤĎòŗˤũŔʜˤŝĎòˤŝŤÊŗŤòíˤũŝđĮĈˤŝƓĈĮˤĦÊĮĈũÊĈòʛˤʁʛˤ)ÊçĎˤŔòŗŝĵĮˤƀĎĵˤģĮĵƀŝˤƆĵũˤĎÊŝˤÊˤíđƙćòŗòĮƜˤŔòŗçòŔƜƓĵĮˤĵƙˤƀĎĵˤƆĵũˤÊŗòʛˤˤɾʛˤGĮ\n",
      ">\u000b\n",
      "Y\u0016\u0011\u0003HORSH\n",
      "\u000f\u0003\u0016\u0011\u0015\f\u000f\u0003\u000b\n",
      "K\u0015\u0011\u0003YDOXH\n",
      "\u000f\u0003\u0015\u0011\u0013\f\u000f\u0003\u000b\n",
      "K\u0014\u0011\u0003SDUFK\n",
      "\u000f\u0003\u0014\u0011\u001c\f\u000f\u0003\u000b\n",
      "Y\u0018\u0011\u0003FRYHW\n",
      "\u000f\u0003\u0013\u0011\u0019\u0013\u0013\u0013\u0013\u0013\u0013\u0013\u0013\u0013\u0013\u0013\u0013\u0013\u0013\u0014\f\u000f\u0003\u000b\n",
      "K\u0015\u0011\u0003PHULW\n",
      "\u000f\u0003\u0013\u0011\u0017\f\u000f\u0003\u000b\n",
      "Y\u0014\u0011\u0003DOORZ\n",
      "\u000f\u0003\u0013\u0011\u0015\f\u000f\u0003\u000b\n",
      "Y\u0015\u0011\u0003JULQG\n",
      "\u000f\u0003\u0013\u0011\u0014\f\u000f\u0003\u000b\n",
      "K\u0017\u0011\u0003OHSHU\n",
      "\u000f\u0003\u0013\u0011\u0014\f@\n",
      "Y\u0016\u0011\u0003HORSH\n",
      "0XOWLSOH\u0003UXQV3DUVH\u000f\u0003ILOWHU\u0003RXW\u0003QRQ\u0010ILYH\u0010OHWWHU\u000f\u0003VFRUH\u000f\u0003DJJUHJDWH\n",
      "&KRRVH\u0003\u000bVRIW\u0003VHOI\u0010FRQVLVWHQF\\\"\f\u0014\u00110D[\u0015\u00110D[\u0003ZLWKRXW\u0003YLRODWH\u0016\u0011')6\n",
      "GĮŔũƜˤ\u001dĦũòŝĎɿʛĭĵŤĵŗĎɾʛƘÊŝģŝĎʁʛŝÊĦĵĮƘÊŝģŝƘÊŝģŝ\n",
      "ĎʁʛˤŝÊĦĵĮˤʱŝũŗòʲſʂʛˤŝŗíŗƆˤʱĦĵƀʲſʀʛˤŝƜŗđĮ\n",
      "Self-reﬂection. Using LLMs to assess the viability of their own predictions is becoming an in-\n",
      "creasingly important procedure in problem solving. [ 25,17,21] introduced the “self-reﬂection”\n",
      "mechanism, in which LMs provide feedback to their generation candidates. [ 4] improves LMs code\n",
      "generation accuracy by injecting feedback messages generated by the LM itself based on its code\n",
      "execution results.\n",
      "References\n",
      "[1]T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam,\n",
      "G. Sastry, A. Askell, et al. Language models are few-shot learners. Advances in neural\n",
      "information processing systems , 33:1877–1901, 2020.\n",
      "[2]C. Browne, E. J. Powley, D. Whitehouse, S. M. M. Lucas, P. I. Cowling, P. Rohlfshagen,\n",
      "S. Tavener, D. P. Liebana, S. Samothrakis, and S. Colton. A su\n",
      "[20] OpenAI. Gpt-4 technical report. ArXiv , abs/2303.08774, 2023.\n",
      "[21] D. Paul, M. Ismayilzada, M. Peyrard, B. Borges, A. Bosselut, R. West, and B. Faltings. Reﬁner:\n",
      "Reasoning feedback on intermediate representations, 2023.\n",
      "[22] A. Radford, K. Narasimhan, T. Salimans, I. Sutskever, et al. Improving language understanding\n",
      "by generative pre-training. OpenAI blog , 2018.\n",
      "[23] A. Radford, J. Wu, R. C\n"
     ]
    }
   ],
   "source": [
    "for doc in documents:\n",
    "    print(doc.page_content[:400])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from langchain_community.vectorstores import FAISS\n",
    "from langchain_openai import OpenAIEmbeddings\n",
    "from langchain_text_splitters import CharacterTextSplitter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "text_splitter = CharacterTextSplitter(chunk_size=1000, chunk_overlap=200)\n",
    "texts = text_splitter.split_documents(documents)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "embeddings = OpenAIEmbeddings()\n",
    "db = FAISS.from_documents(texts, embeddings)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "VectorStoreRetriever(tags=['FAISS', 'OpenAIEmbeddings'], vectorstore=<langchain_community.vectorstores.faiss.FAISS object at 0x142693f90>)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "retriever = db.as_retriever()\n",
    "from langchain.tools.retriever import create_retriever_tool\n",
    "\n",
    "retriever"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Tool(name='tree_of_thoughts', description='Searches and returns excerpts from the tree of thoughts paper.', args_schema=<class 'langchain_core.tools.RetrieverInput'>, func=functools.partial(<function _get_relevant_documents at 0x142380540>, retriever=VectorStoreRetriever(tags=['FAISS', 'OpenAIEmbeddings'], vectorstore=<langchain_community.vectorstores.faiss.FAISS object at 0x142693f90>), document_prompt=PromptTemplate(input_variables=['page_content'], template='{page_content}'), document_separator='\\n\\n'), coroutine=functools.partial(<function _aget_relevant_documents at 0x142380860>, retriever=VectorStoreRetriever(tags=['FAISS', 'OpenAIEmbeddings'], vectorstore=<langchain_community.vectorstores.faiss.FAISS object at 0x142693f90>), document_prompt=PromptTemplate(input_variables=['page_content'], template='{page_content}'), document_separator='\\n\\n'))"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "retriever_tool = create_retriever_tool(\n",
    "    retriever,\n",
    "    \"tree_of_thoughts\",\n",
    "    \"Searches and returns excerpts from the tree of thoughts paper.\",\n",
    ")\n",
    "\n",
    "retriever_tool"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "tools = [retriever_tool]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[SystemMessagePromptTemplate(prompt=PromptTemplate(input_variables=[], template='You are a helpful assistant')),\n",
       " MessagesPlaceholder(variable_name='chat_history', optional=True),\n",
       " HumanMessagePromptTemplate(prompt=PromptTemplate(input_variables=['input'], template='{input}')),\n",
       " MessagesPlaceholder(variable_name='agent_scratchpad')]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from langchain import hub\n",
    "\n",
    "prompt = hub.pull(\"hwchase17/openai-tools-agent\")\n",
    "prompt.messages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "AIMessage(content=\"I'm just a computer program, so I don't experience fatigue or emotions. How can I assist you today?\", response_metadata={'token_usage': {'completion_tokens': 21, 'prompt_tokens': 11, 'total_tokens': 32, 'prompt_tokens_details': {'cached_tokens': 0}, 'completion_tokens_details': {'reasoning_tokens': 0}}, 'model_name': 'gpt-4o-2024-08-06', 'system_fingerprint': 'fp_90354628f2', 'finish_reason': 'stop', 'logprobs': None}, id='run-d2f594a8-7a2b-4025-91b3-a8604b447633-0', usage_metadata={'input_tokens': 11, 'output_tokens': 21, 'total_tokens': 32})"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from langchain_openai import ChatOpenAI\n",
    "\n",
    "llm = ChatOpenAI(model='gpt-4o', temperature=0)\n",
    "\n",
    "llm.invoke(\"Are you tired?\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "from langchain.agents import AgentExecutor, create_tool_calling_agent\n",
    "\n",
    "agent = create_tool_calling_agent(llm, tools, prompt)\n",
    "agent_executor = AgentExecutor(agent=agent, tools=tools, verbose=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "\u001b[1m> Entering new AgentExecutor chain...\u001b[0m\n",
      "\u001b[32;1m\u001b[1;3m\n",
      "Invoking: `tree_of_thoughts` with `{'query': 'tree of thoughts technique'}`\n",
      "\n",
      "\n",
      "\u001b[0m\u001b[36;1m\u001b[1;3mTree of Thoughts: Deliberate Problem Solving\n",
      "with Large Language Models\n",
      "Shunyu Yao\n",
      "Princeton UniversityDian Yu\n",
      "Google DeepMindJeffrey Zhao\n",
      "Google DeepMindIzhak Shafran\n",
      "Google DeepMind\n",
      "Thomas L. Grifﬁths\n",
      "Princeton UniversityYuan Cao\n",
      "Google DeepMindKarthik Narasimhan\n",
      "Princeton University\n",
      "Abstract\n",
      "Language models are increasingly being deployed for general problem solving\n",
      "across a wide range of tasks, but are still conﬁned to token-level, left-to-right\n",
      "decision-making processes during inference. This means they can fall short in\n",
      "tasks that require exploration, strategic lookahead, or where initial decisions play\n",
      "a pivotal role. To surmount these challenges, we introduce a new framework for\n",
      "language model inference, “Tree of Thoughts” (ToT), which generalizes over the\n",
      "popular “Chain of Thought” approach to prompting language models, and enables\n",
      "exploration over coherent units of text (“thoughts”) that serve as intermediate steps\n",
      "toward problem solving. ToT allows LMs to perform deliberate decision making\n",
      "by considering multiple different reasoning paths and self-evaluating choices to\n",
      "decide the next course of action, as well as looking ahead or backtracking when\n",
      "necessary to make global choices. Our experiments show that ToT signiﬁcantly\n",
      "enhances language models’ problem-solving abilities on three novel tasks requiring\n",
      "non-trivial planning or search: Game of 24, Creative Writing, and Mini Crosswords.\n",
      "For instance, in Game of 24, while GPT-4 with chain-of-thought prompting only\n",
      "solved 4% of tasks, our method achieved a success rate of 74%. Code repo with all\n",
      "prompts: https://github.com/ysymyth/tree-of-thought-llm .\n",
      "1 Introduction\n",
      "Originally designed to generate text, scaled-up versions of language models (LMs) such as GPT [ 22,\n",
      "23,1,20] and PaLM [ 5] have been shown to be increasingly capable of performing an ever wider\n",
      "range of tasks requiring mathematical, symbolic, commonsense, and knowledge reasoning. It is\n",
      "perhaps surprising that underlying all this progress is still the original autoregressive mechanism for\n",
      "generating text, which makes token-level decisions one by one and in a left-to-right fashion. Is such\n",
      "a simple mechanism sufﬁcient for a LM to be built toward a general problem solver? If not, what\n",
      "problems would challenge the current paradigm, and what should be alternative mechanisms?\n",
      "The literature on human cognition provides some clues to answer these questions. Research on “dual\n",
      "process” models suggests that people have two modes in which they engage with decisions – a fast,\n",
      "automatic, unconscious mode (“System 1”) and a slow, deliberate, conscious mode (“System 2”)\n",
      "[27,28,13,12]. These two modes have previously been connected to a variety of mathematical\n",
      "models used in machine learning. For example, research on reinforcement learning in humans and\n",
      "other animals has explored the circumstances under which they engage in associative “model free”\n",
      "learning or more deliberative “model based” planning [ 6]. The simple associative token-level choices\n",
      "of LMs are also reminiscent of “System 1”, and thus might beneﬁt from augmentation by a more\n",
      "deliberate “System 2” planning process that (1) maintains and explores diverse alternatives for current\n",
      "Preprint. Under review.arXiv:2305.10601v1  [cs.CL]  17 May 2023\n",
      "\n",
      "Chain-of-thought (CoT) prompting [35] was proposed to address cases where the mapping of\n",
      "inputxto outputyis non-trivial (e.g. when xis a math question and yis the ﬁnal numerical answer).\n",
      "The key idea is to introduce a chain of thoughtsz1,···,znto bridgexandy, where each ziis a\n",
      "coherent language sequence that serves as a meaningful intermediate step toward problem solving\n",
      "(e.g.zicould be an intermediate equation for math QA). To solve problems with CoT, each thought\n",
      "zi∼pCoT\n",
      "θ(zi|x,z1···i−1)is sampled sequentially, then the output y∼pCoT\n",
      "θ(y|x,z1···n). In\n",
      "practice, [z1···n,y]∼pCoT\n",
      "θ(z1···n,y|x)is sampled as a continuous language sequence, and the\n",
      "decomposition of thoughts (e.g. is each zia phrase, a sentence, or a paragraph) is left ambiguous.\n",
      "Self-consistency with CoT (CoT-SC) [33] is an ensemble approach that samples ki.i.d. chains\n",
      "of thought: [z(i)\n",
      "1···n,y(i)]∼pCoT\n",
      "θ(z1···n,y|x) (i= 1···k), then returns the most frequent output:\n",
      "arg maxy#{i|y(i)=y}. CoT-SC improves upon CoT, because there are generally different\n",
      "thought processes for the same problem (e.g. different ways to prove the same theorem), and the\n",
      "output decision can be more faithful by exploring a richer set of thoughts. However, within each\n",
      "chain there is no local exploration of different thought steps, and the “most frequent” heuristic only\n",
      "applies when the output space is limited (e.g. multi-choice QA).\n",
      "3 Tree of Thoughts: Deliberate Problem Solving with LM\n",
      "A genuine problem-solving process involves the repeated use of available informa-\n",
      "tion to initiate exploration, which discloses, in turn, more information until a way\n",
      "to attain the solution is ﬁnally discovered.—— Newell et al. [18]\n",
      "Research on human problem-solving suggests that people search through a combinatorial problem-\n",
      "space – a tree where the nodes represent partial solutions, and the branches correspond to operators\n",
      "that modify them [ 18,19]. Which branch to take is determined by heuristics that help to navigate the\n",
      "problem-space and guide the problem-solver towards a solution. This perspective highlights two key\n",
      "shortcomings of existing approaches that use LMs to solve general problems: 1) Locally, they do not\n",
      "explore different continuations within a thought process – the branches of the tree. 2) Globally, they\n",
      "do not incorporate any type of planning, lookahead, or backtracking to help evaluate these different\n",
      "options – the kind of heuristic-guided search that seems characteristic of human problem-solving.\n",
      "To address these shortcomings, we introduce Tree of Thoughts (ToT) , a paradigm that allows LMs to\n",
      "explore multiple reasoning paths over thoughts (Figure 1(c)). ToT frames any problem as a search\n",
      "over a tree, where each node is a states= [x,z1···i]representing a partial solution with the input and\n",
      "the sequence of thoughts so far. A speciﬁc instantiation of ToT involves answering four questions:\n",
      "1. How to decompose the intermediate process into thought steps; 2. How to generate potential\n",
      "thoughts from each state; 3. How to heuristically evaluate states; 4. What search algorithm to use.\n",
      "1. Thought decomposition. While CoT samples thoughts coherently without explicit decomposition,\n",
      "ToT leverages problem properties to design and decompose intermediate thought steps. As Table 1\n",
      "shows, depending on different problems, a thought could be a couple of words (Crosswords), a line of\n",
      "equation (Game of 24), or a whole paragraph of writing plan (Creative Writing). In general, a thought\n",
      "should be “small” enough so that LMs can generate promising and diverse samples (e.g. generating\n",
      "a whole book is usually too “big” to be coherent), yet “big” enough so that LMs can evaluate its\n",
      "prospect toward problem solving (e.g. generating one token is usually too “small” to evaluate).\n",
      "2. Thought generator G(pθ,s,k).Given a tree state s= [x,z1···i], we consider two strategies to\n",
      "generatekcandidates for the next thought step:\n",
      "(a)Sample i.i.d. thoughts from a CoT prompt (Creative Writing, Figure 4): z(j)∼\n",
      "pCoT\n",
      "θ(zi+1|s) =pCoT\n",
      "θ(zi+1|x,z1···i) (j= 1···k). This works better when the thought\n",
      "space is rich (e.g. each thought is a paragraph), and i.i.d. samples lead to diversity;\n",
      "(b)Propose thoughts sequentially using a “propose prompt” (Game of 24, Figure 2; Crosswords,\n",
      "Figure 6): [z(1),···,z(k)]∼ppropose\n",
      "θ(z(1···k)\n",
      "i+1|s). This works better when the thought\n",
      "space is more constrained (e.g. each thought is just a word or a line), so proposing different\n",
      "thoughts in the same context avoids duplication.\n",
      "3. State evaluator V(pθ,S).Given a frontier of different states, the state evaluator evaluates the\n",
      "progress they make towards solving the problem, serving as a heuristic for the search algorithm\n",
      "to determine which states to keep exploring and in which order. While heuristics are a standard\n",
      "approach to solving search problems, they are typically either programmed (e.g. DeepBlue [ 3]) or\n",
      "3\n",
      "\n",
      "Self-reﬂection. Using LLMs to assess the viability of their own predictions is becoming an in-\n",
      "creasingly important procedure in problem solving. [ 25,17,21] introduced the “self-reﬂection”\n",
      "mechanism, in which LMs provide feedback to their generation candidates. [ 4] improves LMs code\n",
      "generation accuracy by injecting feedback messages generated by the LM itself based on its code\n",
      "execution results. Similarly, [ 14] also introduces “critic” or review steps over the actions and states,\n",
      "deciding the next action to take in solving computer operation tasks. Another recent work very\n",
      "relevant to ours is “self-eval guided decoding” [ 36]. Similar to our method, self-eval decoding\n",
      "also follows a tree-search procedure with leaves sampled from stochastic beam search decoding,\n",
      "which are then evaluated by LLM itself with carefully prepared self-eval prompts. Their approach\n",
      "however, uses the PAL formulation [ 7] which represents thoughts as codes, which makes it difﬁcult\n",
      "to tackle challenging tasks like creative writing which we consider in this paper. Our Tree-of-Thought\n",
      "formulation is thus more versatile and handles challenging tasks on which GPT-4 only achieves very\n",
      "low accuracy with standard prompts.\n",
      "Program-guided LLM generation. Our proposal is also related to recent advancements that or-\n",
      "ganize LM’s behavior with symbolic program guidance. For example [ 24] embeds LMs in an\n",
      "algorithmic search procedure to help solve problems like question answering step-by-step, in which\n",
      "the search trees are expanded by relevant paragraphs that might provide answers. This approach\n",
      "however differs from ours in that trees are expanded by sampling external paragraphs instead of the\n",
      "LM’s own thoughts, and there is no reﬂection or voting steps. Another approach, LLM+P [ 15], goes\n",
      "one step further and delegates the actual planning process to a classical planner.\n",
      "Classical search methods. Last but not least, our approach can be treated as a modern rendition\n",
      "of classical search methods for problem solving. For example it can be considered as a heuristic\n",
      "search algorithm like A* [ 8], in which the heuristic at each search node is provided by the LM’s\n",
      "self-assessment. From this perspective, our method is also related to NeuroLogic A*esque decoding\n",
      "proposed in [ 16], which is inspired by A* search but introduces look-ahead heuristics that are\n",
      "efﬁcient for LMs to improve the beam-search or top-k sampling decoding. This method however is\n",
      "constrained to sentence generation tasks, whereas our framework are designed for complex, multi-step\n",
      "problem solving guarded by value feedback.\n",
      "6 Discussion\n",
      "Limitations and future directions. Deliberate search such as ToT might not be necessary for\n",
      "many existing tasks that GPT-4 already excels at, and as an initial step this work only explores\n",
      "three relatively simple tasks that challenges GPT-4 and calls of better search and planning abilities\n",
      "incorporated with LMs. However, as we begin to deploy LMs for more real-world decision making\n",
      "applications (e.g. coding, data analysis, robotics, etc.), more complex tasks could emerge and present\n",
      "new opportunities to study these research questions. Also, search methods like ToT requires more\n",
      "resources (e.g. GPT-4 API cost) than sampling methods in order to improve task performances,\n",
      "but the modular ﬂexibility of ToT allows users to customize such performance-cost tradeoffs, and\n",
      "ongoing open-source efforts [ 29] should readily reduce such costs in the near future. Lastly, this work\n",
      "focuses on using an off-the-shelf LM, and ﬁne-tuning LMs using a ToT-style high-level counterfactual\n",
      "decision making (e.g. deliberating over potential choices for the next paragraph, instead of predicting\n",
      "the next token) might present opportunities to enhance the problem-solving capabilities of LMs.\n",
      "Broader impact. ToT is a framework that empowers LMs to more autonomously and intelligently\n",
      "make decisions and solve problems. While current tasks are limited to reasoning and search problems,\n",
      "future applications involving interaction with external environments or humans could bring potential\n",
      "danger, e.g. facilitating harmful uses of LMs. On the other hand, ToT also improves the interpretability\n",
      "of model decisions and the opportunity for human alignment, as the resulting representations are\n",
      "readable, high-level language reasoning instead of implicit, low-level token values.\n",
      "Conclusion. The associative “System 1” of LMs can be beneﬁcially augmented by a “System 2”\n",
      "based on searching a tree of possible paths to the solution to a problem. The Tree of Thoughts\n",
      "framework provides a way to translate classical insights about problem-solving into actionable\n",
      "methods for contemporary LMs. At the same time, LMs address a weakness of these classical\n",
      "methods, providing a way to solve complex problems that are not easily formalized, such as creative\n",
      "writing. We see this intersection of LMs with classical approaches to AI as an exciting direction for\n",
      "future work.\n",
      "9\n",
      "\n",
      "learned (e.g. AlphaGo [ 26]). We propose a third alternative, by using the LM to deliberately reason\n",
      "about states. When applicable, such a deliberate heuristic can be more ﬂexible than programmed\n",
      "rules, and more sample-efﬁcient than learned models. Similar to the thought generator, we consider\n",
      "two strategies to evaluate states either independently or together:\n",
      "(a)Value each state independently: V(pθ,S)(s)∼pvalue\n",
      "θ(v|s)∀s∈S, where a value\n",
      "prompt reasons about the state sto generate a scalar value v(e.g. 1-10) or a classiﬁca-\n",
      "tion (e.g. sure/likely/impossible) that could be heuristically turned into a value. The basis\n",
      "of such evaluative reasoning can vary across problems and thought steps. In this work, we\n",
      "explore evaluation via few lookahead simulations (e.g. quickly conﬁrm that 5, 5, 14 can\n",
      "reach 24 via 5 + 5 + 14, or “hot l” can mean “inn” via ﬁlling “e” in “ ”) plus commonsense\n",
      "(e.g. 1 2 3 are too small to reach 24, or no word can start with “tzxc”). While the former\n",
      "might promote “good” states, the latter could help eliminate “bad” states. Such valuations\n",
      "do not need to be perfect, and only need to be approximately\n",
      "(b)Vote across states: V(pθ,S)(s) =1[s=s∗], where a “good” state s∗∼pvote\n",
      "θ(s∗|S)is\n",
      "voted out based on deliberately comparing different states in Sin a vote prompt. When\n",
      "problem success is harder to directly value (e.g. passage coherency), it is natural to to instead\n",
      "compare different partial solutions and vote for the most promising one. This is similar\n",
      "in spirit to a “step-wise” self-consistency strategy, i.e. cast “which state to explore” as a\n",
      "multi-choice QA, and use LM samples to vote for it.\n",
      "For both strategies, we could prompt the LM multiple times to aggregate the value or vote results to\n",
      "trade time/resource/cost for more faithful/robust heuristics.\n",
      "Algorithm 1 ToT-BFS(x,pθ,G,k,V,T,b )\n",
      "Require: Inputx, LMpθ, thought generator G()\n",
      "& size limitk, states evaluator V(), step limitT,\n",
      "breadth limit b.\n",
      "S0←{x}\n",
      "fort= 1,···,Tdo\n",
      "S′\n",
      "t←{[s,z]|s∈St−1,zt∈G(pθ,s,k)}\n",
      "Vt←V(pθ,S′\n",
      "t)\n",
      "St←arg maxS⊂S′\n",
      "t,|S|=b∑\n",
      "s∈SVt(s)\n",
      "end for\n",
      "returnG(pθ,arg maxs∈STVT(s),1)Algorithm 2 ToT-DFS(s,t,pθ,G,k,V,T,v th)\n",
      "Require: Current state s, stept, LMpθ, thought\n",
      "generatorG()and size limit k, states evaluator\n",
      "V(), step limitT, thresholdvth\n",
      "ift>T then record output G(pθ,s,1)\n",
      "end if\n",
      "fors′∈G(pθ,s,k)do⊿sorted candidates\n",
      "ifV(pθ,{s′})(s)>vthres then⊿pruning\n",
      "DFS(s′,t+ 1)\n",
      "end if\n",
      "end for\n",
      "4. Search algorithm. Finally, within the ToT framework, one can plug and play different search\n",
      "algorithms depending on the tree structure. We explore two relatively simple search algorithms and\n",
      "leave more advanced ones (e.g. A* [9], MCTS [2]) for future work:\n",
      "(a)Breadth-ﬁrst search (BFS) (Algorithm 1) maintains a set of the bmost promising states\n",
      "per step. This is used for Game of 24 and Creative Writing where the tree depth is limit\n",
      "(T≤3), and initial thought steps can be evaluated and pruned to a small set ( b≤5).\n",
      "(b)Depth-ﬁrst search (DFS) (Algorithm 2) explores the most promising state ﬁrst, until the\n",
      "ﬁnal output is reached ( t > T ), or the state evaluator deems it impossible to solve the\n",
      "problem from the current s(V(pθ,{s})(s)≤vthfor a value threshold vth). In the latter\n",
      "case, the subtree from sispruned to trade exploration for exploitation. In both cases, DFS\n",
      "backtracks to the parent state of sto continue exploration.\n",
      "Conceptually, ToT has several beneﬁts as a method for general problem-solving with LMs: (1) Gener-\n",
      "ality. IO, CoT, CoT-SC, and self-reﬁnement can be seen as special cases of ToT (i.e. trees of limited\n",
      "depth and breadth; Figure 1). (2) Modularity. The base LM, as well as the thought decomposition,\n",
      "generation, evaluation, and search procedures can all be varied independently. (3) Adaptability .\n",
      "Different problem properties, LM capabilities, and resource constraints can be accommodated. (4)\n",
      "Convenience. No extra training is needed, just a pre-trained LM is sufﬁcient. The next section will\n",
      "show how these conceptual beneﬁts translate to strong empirical performance in different problems.\n",
      "4 Experiments\n",
      "We propose three tasks that are hard even when sampling from the state-of-the-art language model,\n",
      "GPT-4 [ 20], using standard IO prompting or chain-of-thought (CoT) prompting. We show how\n",
      "4\u001b[0m\u001b[32;1m\u001b[1;3mThe \"Tree of Thoughts\" (ToT) technique is a framework designed to enhance the problem-solving capabilities of large language models (LLMs) by allowing them to explore multiple reasoning paths. This approach generalizes the \"Chain of Thought\" (CoT) method, enabling LLMs to perform deliberate decision-making by considering various reasoning paths and self-evaluating choices to decide the next course of action. The technique involves:\n",
      "\n",
      "1. **Thought Decomposition**: Breaking down the problem-solving process into intermediate steps or \"thoughts\" that are coherent units of text. These thoughts serve as partial solutions or steps towards the final solution.\n",
      "\n",
      "2. **Thought Generation**: Generating potential thoughts from each state using strategies like sampling independent thoughts or proposing thoughts sequentially.\n",
      "\n",
      "3. **State Evaluation**: Evaluating the progress of different states towards solving the problem, which helps in deciding which states to explore further.\n",
      "\n",
      "4. **Search Algorithm**: Employing search algorithms like breadth-first search (BFS) or depth-first search (DFS) to explore the tree of thoughts, allowing for planning, lookahead, and backtracking.\n",
      "\n",
      "The ToT framework is inspired by human problem-solving, where people explore a combinatorial problem-space, akin to a tree, with nodes representing partial solutions and branches representing possible actions. This method allows LLMs to perform more complex tasks that require exploration and strategic planning, such as creative writing or solving puzzles, by leveraging a more deliberate \"System 2\" planning process alongside the associative \"System 1\" of LMs.\u001b[0m\n",
      "\n",
      "\u001b[1m> Finished chain.\u001b[0m\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'The \"Tree of Thoughts\" (ToT) technique is a framework designed to enhance the problem-solving capabilities of large language models (LLMs) by allowing them to explore multiple reasoning paths. This approach generalizes the \"Chain of Thought\" (CoT) method, enabling LLMs to perform deliberate decision-making by considering various reasoning paths and self-evaluating choices to decide the next course of action. The technique involves:\\n\\n1. **Thought Decomposition**: Breaking down the problem-solving process into intermediate steps or \"thoughts\" that are coherent units of text. These thoughts serve as partial solutions or steps towards the final solution.\\n\\n2. **Thought Generation**: Generating potential thoughts from each state using strategies like sampling independent thoughts or proposing thoughts sequentially.\\n\\n3. **State Evaluation**: Evaluating the progress of different states towards solving the problem, which helps in deciding which states to explore further.\\n\\n4. **Search Algorithm**: Employing search algorithms like breadth-first search (BFS) or depth-first search (DFS) to explore the tree of thoughts, allowing for planning, lookahead, and backtracking.\\n\\nThe ToT framework is inspired by human problem-solving, where people explore a combinatorial problem-space, akin to a tree, with nodes representing partial solutions and branches representing possible actions. This method allows LLMs to perform more complex tasks that require exploration and strategic planning, such as creative writing or solving puzzles, by leveraging a more deliberate \"System 2\" planning process alongside the associative \"System 1\" of LMs.'"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result = agent_executor.invoke(\n",
    "    {\n",
    "        \"input\": \"what is the tree of thoughts technique?\"\n",
    "    }\n",
    ")\n",
    "\n",
    "result[\"output\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "from langchain_core.tools import tool\n",
    "\n",
    "@tool\n",
    "def create_file(content, filename):\n",
    "    \"\"\"\n",
    "    Create a file with the given content.\n",
    "    \"\"\"\n",
    "    with open(filename, \"w\") as f:\n",
    "        f.write(content)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "tools = [retriever_tool, create_file]\n",
    "agent = create_tool_calling_agent(llm, tools, prompt)\n",
    "agent_executor = AgentExecutor(agent=agent, tools=tools, verbose=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "\u001b[1m> Entering new AgentExecutor chain...\u001b[0m\n",
      "\u001b[32;1m\u001b[1;3m\n",
      "Invoking: `tree_of_thoughts` with `{'query': 'performance evaluation'}`\n",
      "\n",
      "\n",
      "\u001b[0m\u001b[36;1m\u001b[1;3mµŗƓŤòˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòˤĵƙˤʁˤŝĎĵŗƜˤŔÊŗÊĈŗÊŔĎŝʛˤĎòˤòĮíˤŝòĮŤòĮçòˤĵƙˤòÊçĎˤŔÊŗÊĈŗÊŔĎˤĭũŝƜˤæòʝˤɾʛˤGƜˤƓŝĮ˙ƛˤíđƙƙƓçũĦƜˤƘĵˤíĵˤÊˤĎÊĮíŝŤÊĮíˤđƙˤƆĵũˤĠũŝƜˤŝŤÊĮíˤĵĮˤƆĵũŗˤĎÊĮíŝʛˤɿʛˤGƜˤçÊũĈĎƜˤĎđĭˤĵƙƙˤĈũÊŗíˤƛĎÊƜˤŝŔÊçòˤŝĭòĦĦòíˤĵƙˤŝòÊŗòíˤŝŤòÊģʛˤʀʛˤµĎòĮˤŝĎòˤíƓíĮ˒ƛˤĦđģòˤÊˤĈũƆˤƀĎĵˤƀÊŝˤƛŗƆđĮĈˤƘĵˤŔƓçģˤĎòŗˤũŔʜˤŝĎòˤŝŤÊŗŤòíˤũŝđĮĈˤŝƓĈĮˤĦÊĮĈũÊĈòʛˤʁʛˤ)ÊçĎˤŔòŗŝĵĮˤƀĎĵˤģĮĵƀŝˤƆĵũˤĎÊŝˤÊˤíđƙćòŗòĮƜˤŔòŗçòŔƜƓĵĮˤĵƙˤƀĎĵˤƆĵũˤÊŗòʛˤˤɾʛˤGĮƜŗĵíũçòˤÊĮíˤòƅŔĦÊđĮˤƛĎòˤƘòçĎĮƓŖũòˤĵƙˤíĵđĮĈˤÊˤĎÊĮíŝŤÊĮíˤɿʛˤƀƓŤçĎˤƘĵˤÊˤŝŤĵŗƆˤÊæĵũƜˤÊĮˤÊŝƜŗĵĮÊũƜ˙ŝˤƚđŗŝƜˤƛđĭòˤđĮˤŝŔÊçòˤʀʛˤ#òŝçŗđæòˤÊˤŝƓƜũÊƜƓĵĮˤƀĎòŗòˤÊˤƀĵĭÊĮˤũŝòŝˤŝƓĈĮˤĦÊĮĈũÊĈòˤƘĵˤÊſĵƓíˤũĮƀÊĮŤòíˤÊƜŤòĮƜƓĵĮˤʁʛˤĎòˤƚđĮÊĦˤŔÊŗÊĈŗÊŔĎˤòƅŔĦÊđĮŝˤĎĵƀˤòſòŗƆĵĮòˤĎÊŝˤíđƙćòŗòĮƜˤŔòŗçòŔƜƓĵĮŝˤĵƙˤĵƜĎòŗŝɾʛˤGĮƜŗĵíũçƜƓĵĮˤƘĵˤÊĮˤũĮũŝũÊĦˤŝòĦƙˊĎòĦŔˤæĵĵģʜˤĭòĮƜƓĵĮđĮĈˤÊˤĎÊĮíŝŤÊĮíˤÊŝˤÊˤĭòŤÊŔĎĵŗˤƗĵŗˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʛˤɿʛˤ#ƓŝçũŝŝˤƛĎòˤũĮòƅŔòçŤòíˤƛĎđĮĈŝˤĦòÊŗĮòíˤƚŗĵĭˤÊŝƜŗĵĮÊũŤŝʜˤđĮçĦũíđĮĈˤƛĎòˤŝĭòĦĦˤĵƙˤŝŔÊçòʛˤʀʛˤ#òŝçŗđæòˤÊˤƀĵĭÊĮ˙ŝˤçĦòſòŗˤƘÊçƜƓçˤƗĵŗˤÊſĵƓíđĮĈˤũĮƀÊĮŤòíˤÊƜŤòĮƜƓĵĮˤÊƜˤÊˤæÊŗʛˤʁʛˤ\u001dĵĮŤòĭŔĦÊŤòˤĎĵƀˤíđƙćòŗòĮƜˤŔòŗçòŔƜƓĵĮŝˤĵƙˤĵĮòŝòĦƙˤçÊĮˤŝĎÊŔòˤĵĮò˙ŝˤƓíòĮƜƓŤƆʛʱÊʲˤGĮŔũƜʱæʲˤĦÊĮŝʱʀˤĭĵŗòˤĵĭƓƜŤòíʲʱçʲˤ´ĵŤòŝ\u0001ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\u001dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝʟˤ\u001dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛʱɽʫʂˤſĵŤòŝʲ\u0001ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\u001dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝʟˤ\u001dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛ\u0001ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\u001dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝʟˤ\u001dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛ\u0001ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\u001dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝʟˤ\u001dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛ\u0001ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\u001dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤʳʛʛʛʴˤ\u001dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛʱʀʫʂˤſĵŤòŝʲʟɾɿGĮŔũƜĦÊĮˤɾĦÊĮˤɿʟʟÊŝŝÊĈòɾÊŝŝÊĈòɿʟʟ)L[\u0003FRORU\u0003\u000bE\\\u0003<XTLDQ\fµŗƓŤòˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòˤĵƙˤʁˤŝĎĵŗƜˤŔÊŗÊĈŗÊŔĎŝʛˤĎòˤòĮíˤŝòĮŤòĮçòˤĵƙˤòÊçĎˤŔÊŗÊĈŗÊŔĎˤĭũŝƜˤæòʝˤɾʛˤGƜˤƓŝĮ˙ƛˤíđƙƙƓçũĦƜˤƘĵˤíĵˤÊˤĎÊĮíŝŤÊĮíˤđƙˤƆĵũˤĠũŝƜˤŝŤÊĮíˤĵĮˤƆĵũŗˤĎÊĮíŝʛˤɿʛˤGƜˤçÊũĈĎƜˤĎđĭˤĵƙƙˤĈũÊŗíˤƛĎÊƜˤŝŔÊçòˤŝĭòĦĦòíˤĵƙˤŝòÊŗòíˤŝŤòÊģʛˤʀʛˤµĎòĮˤŝĎòˤíƓíĮ˒ƛˤĦđģòˤÊˤĈũƆˤƀĎĵˤƀÊŝˤƛŗƆđĮĈˤƘĵˤŔƓçģˤĎòŗˤũŔʜˤŝĎòˤŝŤÊŗŤòíˤũŝđĮĈˤŝƓĈĮˤĦÊĮĈũÊĈòʛˤʁʛˤ)ÊçĎˤŔòŗŝĵĮˤƀĎĵˤģĮĵƀŝˤƆĵũˤĎÊŝˤÊˤíđƙćòŗòĮƜˤŔòŗçòŔƜƓĵĮˤĵƙˤƀĎĵˤƆĵũˤÊŗòʛˤˤɾʛˤGĮƜŗĵíũçòˤÊĮíˤòƅŔĦÊđĮˤƛĎòˤƘòçĎĮƓŖũòˤĵƙˤíĵđĮĈˤÊˤĎÊĮíŝŤÊĮíˤɿʛˤƀƓŤçĎˤƘĵˤÊˤŝŤĵŗƆˤÊæĵũƜˤÊĮˤÊŝƜŗĵĮÊũƜ˙ŝˤƚđŗŝƜˤƛđĭòˤđĮˤŝŔÊçòˤʀʛˤ#òŝçŗđæòˤÊˤŝƓƜũÊƜƓĵĮˤƀĎòŗòˤÊˤƀĵĭÊĮˤũŝòŝˤŝƓĈĮˤĦÊĮĈũÊĈòˤƘĵˤÊſĵƓíˤũĮƀÊĮŤòíˤÊƜŤòĮƜƓĵĮˤʁʛˤĎòˤƚđĮÊĦˤŔÊŗÊĈŗÊŔĎˤòƅŔĦÊđĮŝˤĎĵƀˤòſòŗƆĵĮòˤĎÊŝˤíđƙćòŗòĮƜˤŔòŗçòŔƜƓĵĮŝˤĵƙˤĵƜĎòŗŝɾʛˤGĮƜŗĵíũçƜƓĵĮˤƘĵˤÊĮˤũĮũŝũÊĦˤŝòĦƙˊĎòĦŔˤæĵĵģʜˤĭòĮƜƓĵĮđĮĈˤÊˤĎÊĮíŝŤÊĮíˤÊŝˤÊˤĭòŤÊŔĎĵŗˤƗĵŗˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʛˤɿʛˤ#ƓŝçũŝŝˤƛĎòˤũĮòƅŔòçŤòíˤƛĎđĮĈŝˤĦòÊŗĮòíˤƚŗĵĭˤÊŝƜŗĵĮÊũŤŝʜˤđĮçĦũíđĮĈˤƛĎòˤŝĭòĦĦˤĵƙˤŝŔÊçòʛˤʀʛˤ#òŝçŗđæòˤÊˤƀĵĭÊĮ˙ŝˤçĦòſòŗˤƘÊçƜƓçˤƗĵŗˤÊſĵƓíđĮĈˤũĮƀÊĮŤòíˤÊƜŤòĮƜƓĵĮˤÊƜˤÊˤæÊŗʛˤʁʛˤ\u001dĵĮŤòĭŔĦÊŤòˤĎĵƀˤíđƙćòŗòĮƜˤŔòŗçòŔƜƓĵĮŝˤĵƙˤĵĮòŝòĦƙˤçÊĮˤŝĎÊŔòˤĵĮò˙ŝˤƓíòĮƜƓŤƆʛʱÊʲˤGĮŔũƜʱæʲˤĦÊĮŝʱçʲˤ´ĵŤòŝ\u0001ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\u001dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤʳʛʛʛʴˤ\u001dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛGĮŔũƜĦÊĮˤɾˤĦÊĮˤɿˤˤʟʟÊŝŝÊĈòɾÊŝŝÊĈòɿʟʟɽʫʂˤſĵŤòŝĦÊĮˤɾˤˤˤʟʛʟʛɾʟʛɿʟʟʀʫʂˤſĵŤòŝĦÊĮˤʀˁʂˤˤˤ8VH\u0003UHG\u0012JUHHQ\u0003WR\u0003VKRZ\u0003ILQDO\u0003FKRLFH\n",
      "ĮʫʂˤſĵŤòŝĦÊĮˤɿˤˤˤ\n",
      "\u0001ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\u001dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤʳʛʛʛʴˤ\u001dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛ\u0001ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\u001dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤʳʛʛʛʴˤ\u001dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛ\u0001ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\u001dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤʳʛʛʛʴˤ\u001dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛ\u0001ĮÊĦƆƏđĮĈˤòÊçĎˤçĎĵƓçòˤđĮˤíòŤÊƓĦʝˤˤ\u001dĎĵƓçòˤɾʜˤƀĎƓĦòˤđĮçĵŗŔĵŗÊƜđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝʜˤŝòòĭŝˤƘĵˤĦÊçģˤÊˤçĦòÊŗˤçĵĮĮòçƜƓĵĮˤæòŤƀòòĮˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤʳʛʛʛʴˤ\u001dĎĵƓçòˤɿˤĵƙćòŗŝˤÊĮˤđĮŤòŗòŝƜđĮĈˤŔòŗŝŔòçƜƓſòˤæƆˤũŝđĮĈˤƛĎòˤŗòŖũđŗòíˤòĮíˤŝòĮŤòĮçòŝˤƘĵˤŔŗòŝòĮƜˤÊˤŝòĦƙˊĎòĦŔˤæĵĵģ˙ŝˤçĵĮŤòĮƜʛˤGƜˤçĵĮĮòçŤŝˤƛĎòˤŔÊŗÊĈŗÊŔĎŝˤƀƓƜĎˤƛĎòˤƛĎòĭòˤĵƙˤŝòĦƙˊđĭŔŗĵſòĭòĮƜˤÊĮíˤòĭæŗÊçđĮĈˤçĎÊĦĦòĮĈòŝʜˤĭÊģđĮĈˤƗĵŗˤÊˤçĵĎòŗòĮƜˤŔÊŝŝÊĈòʛˤˤʳʛʛʛʴˤĎòˤæòŝƜˤçĎĵƓçòˤƓŝˤɿʛFigure 4: A step of deliberate search in a randomly picked Creative Writing task. Given the input, the\n",
      "LM samples 5 different plans, then votes 5 times to decide which plan is best. The majority choice is\n",
      "used to consequently write the output passage with the same sample-vote procedure.\n",
      "IO CoT ToT IO\n",
      "+refineToT\n",
      "+refine468\n",
      "(a) GPT-4 coherency scores\n",
      "CoT > ToT Similar ToT > CoT010203040\n",
      "213841(b) Human coherency comparison\n",
      "Figure 5: Creative Writing results.Method Success Rate (%)\n",
      "Letter Word Game\n",
      "IO 38.7 14 0\n",
      "CoT 40.6 15.6 1\n",
      "ToT (ours) 78 60 20\n",
      "+best state 82.4 67.5 35\n",
      "-prune 65.4 41.5 5\n",
      "-backtrack 54.6 20 5\n",
      "Table 3: Mini Crosswords results.\n",
      "it improves IO coherency score from 6.19 to 7.67, and ToT coherency score from 7.56 to 7.91. We\n",
      "believe it could be thought of as a third approach to thought generation in the ToT framework, where\n",
      "new thoughts can arise from reﬁning old thoughts instead of i.i.d. or sequentially generated.\n",
      "4.3 Mini Crosswords\n",
      "In Game of 24 and Creative Writing, ToT is relatively shallow — at most 3 thought steps are needed\n",
      "to reach the ﬁnal output. Here we explore 5×5mini crosswords as a harder search problem involving\n",
      "natural language. Again, the goal is not just to solve the task, as more general crosswords can be\n",
      "readily solved with specialized NLP pipelines [ 31] that leverages large-scale retrieval instead of LM.\n",
      "Rather, we aim to explore the limit of LM as a general problem solver that explores its own thoughts\n",
      "and guides its own exploration with deliberate reasoning as heuristics.\n",
      "Task Setup. We scrape data from GooBix, which contains 156 games of 5×5mini crosswords. As\n",
      "we observe adjacent games contain similar clues, we use 20 games with indices 1,6,···,91,96for\n",
      "testing, and games 136,141,146,151,156for prompting. For each task, the input describes the 5\n",
      "horizontal clues and 5 vertical clues, and the output should be a board of 5×5 = 25 letters to solve\n",
      "the crosswords. For evaluation, we consider three levels of success: the portion of correct letters (25\n",
      "per game), words (10 per game), and games.\n",
      "Baselines. We provide 5 example input-output pairs in the IO prompt, and in the CoT prompt\n",
      "additionally include intermediate words in the order h1..5 then v1..5. We run each prompt for 10\n",
      "samples and average the results.\n",
      "ToT Setup. We leverage a depth-ﬁrst search (Algorithm 2) that keeps exploring the most promising\n",
      "subsequent word clue until the state is no longer promising, then backtrack to the parent state to\n",
      "explore alternative thoughts. To make search tractable, subsequent thoughts are constrained not to\n",
      "change any ﬁlled words or letters, so that the ToT has at most 10 intermediate steps. For thought\n",
      "generation, at each state we translate all existing thoughts (e.g. “h2.motor; h1.tasks” for the state\n",
      "in Figure 6(a)) into letter constraints for remaining clues (e.g. “v1.To heap: tm ;...”) and prompt\n",
      "a proposal prompt 5times to come up with candidates for where and what to ﬁll in the next word.\n",
      "Importantly, we also prompt the LM to give a conﬁdence level for different thoughts, and aggregate\n",
      "7\n",
      "\n",
      "learned (e.g. AlphaGo [ 26]). We propose a third alternative, by using the LM to deliberately reason\n",
      "about states. When applicable, such a deliberate heuristic can be more ﬂexible than programmed\n",
      "rules, and more sample-efﬁcient than learned models. Similar to the thought generator, we consider\n",
      "two strategies to evaluate states either independently or together:\n",
      "(a)Value each state independently: V(pθ,S)(s)∼pvalue\n",
      "θ(v|s)∀s∈S, where a value\n",
      "prompt reasons about the state sto generate a scalar value v(e.g. 1-10) or a classiﬁca-\n",
      "tion (e.g. sure/likely/impossible) that could be heuristically turned into a value. The basis\n",
      "of such evaluative reasoning can vary across problems and thought steps. In this work, we\n",
      "explore evaluation via few lookahead simulations (e.g. quickly conﬁrm that 5, 5, 14 can\n",
      "reach 24 via 5 + 5 + 14, or “hot l” can mean “inn” via ﬁlling “e” in “ ”) plus commonsense\n",
      "(e.g. 1 2 3 are too small to reach 24, or no word can start with “tzxc”). While the former\n",
      "might promote “good” states, the latter could help eliminate “bad” states. Such valuations\n",
      "do not need to be perfect, and only need to be approximately\n",
      "(b)Vote across states: V(pθ,S)(s) =1[s=s∗], where a “good” state s∗∼pvote\n",
      "θ(s∗|S)is\n",
      "voted out based on deliberately comparing different states in Sin a vote prompt. When\n",
      "problem success is harder to directly value (e.g. passage coherency), it is natural to to instead\n",
      "compare different partial solutions and vote for the most promising one. This is similar\n",
      "in spirit to a “step-wise” self-consistency strategy, i.e. cast “which state to explore” as a\n",
      "multi-choice QA, and use LM samples to vote for it.\n",
      "For both strategies, we could prompt the LM multiple times to aggregate the value or vote results to\n",
      "trade time/resource/cost for more faithful/robust heuristics.\n",
      "Algorithm 1 ToT-BFS(x,pθ,G,k,V,T,b )\n",
      "Require: Inputx, LMpθ, thought generator G()\n",
      "& size limitk, states evaluator V(), step limitT,\n",
      "breadth limit b.\n",
      "S0←{x}\n",
      "fort= 1,···,Tdo\n",
      "S′\n",
      "t←{[s,z]|s∈St−1,zt∈G(pθ,s,k)}\n",
      "Vt←V(pθ,S′\n",
      "t)\n",
      "St←arg maxS⊂S′\n",
      "t,|S|=b∑\n",
      "s∈SVt(s)\n",
      "end for\n",
      "returnG(pθ,arg maxs∈STVT(s),1)Algorithm 2 ToT-DFS(s,t,pθ,G,k,V,T,v th)\n",
      "Require: Current state s, stept, LMpθ, thought\n",
      "generatorG()and size limit k, states evaluator\n",
      "V(), step limitT, thresholdvth\n",
      "ift>T then record output G(pθ,s,1)\n",
      "end if\n",
      "fors′∈G(pθ,s,k)do⊿sorted candidates\n",
      "ifV(pθ,{s′})(s)>vthres then⊿pruning\n",
      "DFS(s′,t+ 1)\n",
      "end if\n",
      "end for\n",
      "4. Search algorithm. Finally, within the ToT framework, one can plug and play different search\n",
      "algorithms depending on the tree structure. We explore two relatively simple search algorithms and\n",
      "leave more advanced ones (e.g. A* [9], MCTS [2]) for future work:\n",
      "(a)Breadth-ﬁrst search (BFS) (Algorithm 1) maintains a set of the bmost promising states\n",
      "per step. This is used for Game of 24 and Creative Writing where the tree depth is limit\n",
      "(T≤3), and initial thought steps can be evaluated and pruned to a small set ( b≤5).\n",
      "(b)Depth-ﬁrst search (DFS) (Algorithm 2) explores the most promising state ﬁrst, until the\n",
      "ﬁnal output is reached ( t > T ), or the state evaluator deems it impossible to solve the\n",
      "problem from the current s(V(pθ,{s})(s)≤vthfor a value threshold vth). In the latter\n",
      "case, the subtree from sispruned to trade exploration for exploitation. In both cases, DFS\n",
      "backtracks to the parent state of sto continue exploration.\n",
      "Conceptually, ToT has several beneﬁts as a method for general problem-solving with LMs: (1) Gener-\n",
      "ality. IO, CoT, CoT-SC, and self-reﬁnement can be seen as special cases of ToT (i.e. trees of limited\n",
      "depth and breadth; Figure 1). (2) Modularity. The base LM, as well as the thought decomposition,\n",
      "generation, evaluation, and search procedures can all be varied independently. (3) Adaptability .\n",
      "Different problem properties, LM capabilities, and resource constraints can be accommodated. (4)\n",
      "Convenience. No extra training is needed, just a pre-trained LM is sufﬁcient. The next section will\n",
      "show how these conceptual beneﬁts translate to strong empirical performance in different problems.\n",
      "4 Experiments\n",
      "We propose three tasks that are hard even when sampling from the state-of-the-art language model,\n",
      "GPT-4 [ 20], using standard IO prompting or chain-of-thought (CoT) prompting. We show how\n",
      "4\n",
      "\n",
      "Self-reﬂection. Using LLMs to assess the viability of their own predictions is becoming an in-\n",
      "creasingly important procedure in problem solving. [ 25,17,21] introduced the “self-reﬂection”\n",
      "mechanism, in which LMs provide feedback to their generation candidates. [ 4] improves LMs code\n",
      "generation accuracy by injecting feedback messages generated by the LM itself based on its code\n",
      "execution results. Similarly, [ 14] also introduces “critic” or review steps over the actions and states,\n",
      "deciding the next action to take in solving computer operation tasks. Another recent work very\n",
      "relevant to ours is “self-eval guided decoding” [ 36]. Similar to our method, self-eval decoding\n",
      "also follows a tree-search procedure with leaves sampled from stochastic beam search decoding,\n",
      "which are then evaluated by LLM itself with carefully prepared self-eval prompts. Their approach\n",
      "however, uses the PAL formulation [ 7] which represents thoughts as codes, which makes it difﬁcult\n",
      "to tackle challenging tasks like creative writing which we consider in this paper. Our Tree-of-Thought\n",
      "formulation is thus more versatile and handles challenging tasks on which GPT-4 only achieves very\n",
      "low accuracy with standard prompts.\n",
      "Program-guided LLM generation. Our proposal is also related to recent advancements that or-\n",
      "ganize LM’s behavior with symbolic program guidance. For example [ 24] embeds LMs in an\n",
      "algorithmic search procedure to help solve problems like question answering step-by-step, in which\n",
      "the search trees are expanded by relevant paragraphs that might provide answers. This approach\n",
      "however differs from ours in that trees are expanded by sampling external paragraphs instead of the\n",
      "LM’s own thoughts, and there is no reﬂection or voting steps. Another approach, LLM+P [ 15], goes\n",
      "one step further and delegates the actual planning process to a classical planner.\n",
      "Classical search methods. Last but not least, our approach can be treated as a modern rendition\n",
      "of classical search methods for problem solving. For example it can be considered as a heuristic\n",
      "search algorithm like A* [ 8], in which the heuristic at each search node is provided by the LM’s\n",
      "self-assessment. From this perspective, our method is also related to NeuroLogic A*esque decoding\n",
      "proposed in [ 16], which is inspired by A* search but introduces look-ahead heuristics that are\n",
      "efﬁcient for LMs to improve the beam-search or top-k sampling decoding. This method however is\n",
      "constrained to sentence generation tasks, whereas our framework are designed for complex, multi-step\n",
      "problem solving guarded by value feedback.\n",
      "6 Discussion\n",
      "Limitations and future directions. Deliberate search such as ToT might not be necessary for\n",
      "many existing tasks that GPT-4 already excels at, and as an initial step this work only explores\n",
      "three relatively simple tasks that challenges GPT-4 and calls of better search and planning abilities\n",
      "incorporated with LMs. However, as we begin to deploy LMs for more real-world decision making\n",
      "applications (e.g. coding, data analysis, robotics, etc.), more complex tasks could emerge and present\n",
      "new opportunities to study these research questions. Also, search methods like ToT requires more\n",
      "resources (e.g. GPT-4 API cost) than sampling methods in order to improve task performances,\n",
      "but the modular ﬂexibility of ToT allows users to customize such performance-cost tradeoffs, and\n",
      "ongoing open-source efforts [ 29] should readily reduce such costs in the near future. Lastly, this work\n",
      "focuses on using an off-the-shelf LM, and ﬁne-tuning LMs using a ToT-style high-level counterfactual\n",
      "decision making (e.g. deliberating over potential choices for the next paragraph, instead of predicting\n",
      "the next token) might present opportunities to enhance the problem-solving capabilities of LMs.\n",
      "Broader impact. ToT is a framework that empowers LMs to more autonomously and intelligently\n",
      "make decisions and solve problems. While current tasks are limited to reasoning and search problems,\n",
      "future applications involving interaction with external environments or humans could bring potential\n",
      "danger, e.g. facilitating harmful uses of LMs. On the other hand, ToT also improves the interpretability\n",
      "of model decisions and the opportunity for human alignment, as the resulting representations are\n",
      "readable, high-level language reasoning instead of implicit, low-level token values.\n",
      "Conclusion. The associative “System 1” of LMs can be beneﬁcially augmented by a “System 2”\n",
      "based on searching a tree of possible paths to the solution to a problem. The Tree of Thoughts\n",
      "framework provides a way to translate classical insights about problem-solving into actionable\n",
      "methods for contemporary LMs. At the same time, LMs address a weakness of these classical\n",
      "methods, providing a way to solve complex problems that are not easily formalized, such as creative\n",
      "writing. We see this intersection of LMs with classical approaches to AI as an exciting direction for\n",
      "future work.\n",
      "9\n",
      "\n",
      "GĮŔũƜ\n",
      "jũƜŔũƜGĮŔũƜ\n",
      "jũƜŔũƜʱÊʲˤGjʱæʲˤ\u001dĵÉGĮŔũƜ\n",
      "ˤjũƜŔũƜʱçʲˤ\u001dĵÉˁ\u001dʟʟʟʟaÊĠĵŗƓŤƆˤſĵŤòGĮŔũƜ\n",
      "ˤjũƜŔũƜʱíʲˤÉĵÉˤʱĵũŗŝʲʟʟʟʟʟʟˤˤʝˤƛĎĵũĈĎƜ)L[\u0003FRORU\u0003\u000bE\\\u0003<XTLDQ\f0DUN\u0003GLIIHUHQFH\u0003E\\\u0003FRORU\n",
      "GĮŔũƜ\n",
      "jũƜŔũƜGĮŔũƜ\n",
      "jũƜŔũƜGĮŔũƜ\n",
      "ˤjũƜŔũƜʱçʲˤòĦƙˤ\u001dĵĮŝƓŝŤòĮçƆˤƀƓƜĎˤ\u001dĵÉˤʱ\u001dĵÉˁ\u001dʲaÊĠĵŗƓŤƆˤſĵŤòGĮŔũƜ\n",
      "ˤjũƜŔũƜʱíʲˤÉŗòòˤĵƙˤĎĵũĈĎŤŝˤʱÉĵÉʲʟʟʟʟʟʟʟʟʟʟˤˤƛĎĵũĈĎƜ\n",
      "ʱçʲˤ\u001dĎÊđĮˤĵƙˤĎĵũĈĎƜˤŗĵĭŔƜđĮĈˤʱ\u001dĵÉʲʱÊʲˤGĮŔũƜˁjũƜŔũƜˤŗĵĭŔƜđĮĈˤʱGjʲFigure 1: Schematic illustrating various approaches to problem solving with LLMs. Each rectangle\n",
      "box represents a thought , which is a coherent language sequence that serves as an intermediate\n",
      "step toward problem solving. See concrete examples of how thoughts are generated, evaluated, and\n",
      "searched in Figures 2,4,6.\n",
      "choices instead of just picking one, and (2) evaluates its current status and actively looks ahead or\n",
      "backtracks to make more global decisions.\n",
      "To design such a planning process, we return to the origins of artiﬁcial intelligence (and cognitive\n",
      "science), drawing inspiration from the planning processes explored by Newell, Shaw, and Simon\n",
      "starting in the 1950s [ 18,19]. Newell and colleagues characterized problem solving [ 18] as search\n",
      "through a combinatorial problem space, represented as a tree. We thus propose the Tree of Thoughts\n",
      "(ToT) framework for general problem solving with language models. As Figure 1 illustrates, while\n",
      "existing methods (detailed below) sample continuous language sequences for problem solving, ToT\n",
      "actively maintains a tree of thoughts, where each thought is a coherent language sequence that serves\n",
      "as an intermediate step toward problem solving (Table 1). Such a high-level semantic unit allows the\n",
      "LM to self-evaluate the progress different intermediate thoughts make towards solving the problem\n",
      "through a deliberate reasoning process that is also instantiated in language (Figures 2,4,6). This\n",
      "implementation of search heuristics via LM self-evaluation and deliberation is novel, as previous\n",
      "search heuristics are either programmed or learned. Finally, we combine this language-based\n",
      "capability to generate and evaluate diverse thoughts with search algorithms, such as breadth-ﬁrst\n",
      "search (BFS) or depth-ﬁrst search (DFS), which allow systematic exploration of the tree of thoughts\n",
      "with lookahead and backtracking.\n",
      "Empirically, we propose three new problems that challenge existing LM inference methods even with\n",
      "the state-of-the-art language model, GPT-4 [ 20]: Game of 24, Creative Writing, and Crosswords\n",
      "(Table 1). These tasks require deductive, mathematical, commonsense, lexical reasoning abilities,\n",
      "and a way to incorporate systematic planning or search. We show ToT obtains superior results on\n",
      "all three tasks by being general and ﬂexible enough to support different levels of thoughts, different\n",
      "ways to generate and evaluate thoughts, and different search algorithms that adapt to the nature of\n",
      "different problems. We also analyze how such choices affect model performances via systematic\n",
      "ablations and discuss future directions to better train and use LMs.\n",
      "2 Background\n",
      "We ﬁrst formalize some existing methods that use large language models for problem-solving,\n",
      "which our approach is inspired by and later compared with. We use pθto denote a pre-trained LM\n",
      "with parameters θ, and lowercase letters x,y,z,s,···to denote a language sequence , i.e.x=\n",
      "(x[1],···,x[n])where eachx[i]is a token, so that pθ(x) =∏n\n",
      "i=1pθ(x[i]|x[1...i]). We use uppercase\n",
      "lettersS,···to denote a collection of language sequences.\n",
      "Input-output (IO) prompting is the most common way to turn a problem input xinto outputywith\n",
      "LM:y∼pθ(y|promptIO(x)), where promptIO(x)wraps inputxwith task instructions and/or few-\n",
      "shot input-output examples. For simplicity, let us denote pprompt\n",
      "θ(output|input ) =pθ(output|\n",
      "prompt (input )), so that IO prompting can be formulated as y∼pIO\n",
      "θ(y|x).\n",
      "2\u001b[0m\u001b[32;1m\u001b[1;3m\n",
      "Invoking: `create_file` with `{'filename': 'performance_evaluation.txt', 'content': \"The performance of the Tree of Thoughts (ToT) technique was evaluated through a series of experiments involving tasks that are challenging even for state-of-the-art language models like GPT-4. The evaluation focused on three main tasks: Game of 24, Creative Writing, and Mini Crosswords.\\n\\n1. **Game of 24 and Creative Writing**: In these tasks, ToT was used to generate coherent outputs by sampling multiple plans and voting to decide the best plan. The performance was measured by comparing the coherency scores of the outputs generated by ToT against those generated by other methods like Input-Output (IO) prompting and Chain-of-Thought (CoT) prompting. ToT showed superior results by achieving higher coherency scores.\\n\\n2. **Mini Crosswords**: This task involved solving 5x5 mini crosswords, which is a more complex problem requiring deeper search. The evaluation considered three levels of success: the portion of correct letters, words, and games. ToT was compared against baseline methods, and its performance was measured by the success rate in correctly solving the crosswords. ToT achieved higher success rates compared to other methods, demonstrating its effectiveness in handling complex search problems.\\n\\nThe evaluation also involved systematic ablations to understand the impact of different components of the ToT framework on performance. The results showed that ToT's ability to explore and evaluate different thoughts systematically contributed to its superior performance across the tasks.\"}`\n",
      "\n",
      "\n",
      "\u001b[0m\u001b[33;1m\u001b[1;3mNone\u001b[0m\u001b[32;1m\u001b[1;3mThe performance evaluation details have been written to a file named `performance_evaluation.txt`.\u001b[0m\n",
      "\n",
      "\u001b[1m> Finished chain.\u001b[0m\n"
     ]
    }
   ],
   "source": [
    "result = agent_executor.invoke(\n",
    "    {\"input\": \"How did they evaluated the performance of the technique? Write the answer to a file.\"}\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'The performance of the Tree of Thoughts (ToT) technique was evaluated through a series of experiments involving tasks that challenge existing language model inference methods, even with state-of-the-art models like GPT-4. The tasks included:\\n\\n1. **Game of 24**: This task required mathematical reasoning to reach a target number using a set of given numbers and operations.\\n\\n2. **Creative Writing**: This task involved generating coherent and creative text based on given prompts.\\n\\n3. **Mini Crosswords**: This task involved solving 5x5 mini crosswords, which required lexical reasoning and systematic planning.\\n\\nThe evaluation involved comparing the ToT approach with other methods such as Input-Output (IO) prompting and Chain-of-Thought (CoT) prompting. The performance metrics included success rates in terms of correct letters, words, and games for the Mini Crosswords task, as well as coherency scores for the Creative Writing task.\\n\\nThe ToT approach demonstrated superior results across these tasks by leveraging a tree of thoughts, where each thought is a coherent language sequence serving as an intermediate step toward problem-solving. The method involved generating and evaluating diverse thoughts using search algorithms like breadth-first search (BFS) and depth-first search (DFS), allowing systematic exploration with lookahead and backtracking.\\n\\nThe results showed that ToT significantly improved success rates and coherency scores compared to other methods, highlighting its effectiveness in handling complex, multi-step problem-solving tasks.'"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result[\"output\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "oreilly-agents",
   "language": "python",
   "name": "oreilly-agents"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}