CoChat
Sign Up
PreprintCited by 1,288AI-based Problem Solving and PlanningTopic ModelingNatural Language Processing Techniques

Tree of Thoughts: Deliberate Problem Solving with Large Language Models

Open access
Yao, Shunyu, Yu, Dian, Zhao, Jeffrey, Shafran, Izhak, Griffiths, Thomas L., Cao, Yuan, Narasimhan, Karthik·2023·arXiv
DOI 10.48550/arxiv.2305.10601arXiv 2305.10601
Open this paper in CoChat — free accountOpen PDF

Abstract

Language models are increasingly being deployed for general problem solving across a wide range of tasks, but are still confined to token-level, left-to-right decision-making processes during inference. This means they can fall short in tasks that require exploration, strategic lookahead, or where initial decisions play a pivotal role. To surmount these challenges, we introduce a new framework for language model inference, Tree of Thoughts (ToT), which generalizes over the popular Chain of Thought approach to prompting language models, and enables exploration over coherent units of text (thoughts) that serve as intermediate steps toward problem solving. ToT allows LMs to perform deliberate decision making by considering multiple different reasoning paths and self-evaluating choices to decide the next course of action, as well as looking ahead or backtracking when necessary to make global choices. Our experiments show that ToT significantly enhances language models' problem-solving abilities on three novel tasks requiring non-trivial planning or search: Game of 24, Creative Writing, and Mini Crosswords. For instance, in Game of 24, while GPT-4 with chain-of-thought prompting only solved 4% of tasks, our method achieved a success rate of 74%. Code repo with all prompts: https://github.com/princeton-nlp/tree-of-thought-llm.

AI snapshot

Written from the paper’s full text.

TL;DR

Tree of Thoughts (ToT) generalizes chain-of-thought prompting by letting a language model explore, evaluate, and search over multiple intermediate “thoughts” rather than decoding left-to-right. On three tasks challenging GPT-4, ToT substantially improves success rates, including 74% on Game of 24 versus 4% for chain-of-thought.

Key findings

  • On Game of 24, GPT-4 with IO prompting achieved 7.3%, CoT 4.0%, and CoT-SC (k=100) 9.0%, while ToT achieved 45% with breadth b=1 and 74% with b=5; best-of-100 CoT reached 49%.
  • On Creative Writing, GPT-4 coherency scores averaged 7.56 for ToT versus 6.19 for IO and 6.93 for CoT; in a blind human comparison, ToT was judged more coherent than CoT in 41 cases, CoT more coherent in 21, and similar in 38.
  • On 5×5 Mini Crosswords, ToT reached 78% letter-level, 60% word-level, and 20% game-level success, compared with IO at 38.7%, 14%, and 0%, and CoT at 40.6%, 15.6%, and 1%; ToT solved 4/20 games, and an oracle best-state variant solved 7/20.
  • With GPT-3.5, ToT still beat CoT and IO on tested tasks, but on Game of 24 GPT-3.5+ToT reached only 19% versus GPT-4+ToT’s 74%; GPT-4 generation with GPT-3.5 evaluation reached 64%, while GPT-3.5 generation with GPT-4 evaluation reached 31%.

Methods

  • ToT frames problem solving as search over a tree where each node is a partial solution state; instantiations specify thought decomposition, a thought generator, a state evaluator, and a search algorithm such as BFS or DFS.
  • Experiments used off-the-shelf GPT-4 chat completion at temperature 0.7 with no extra training. Game of 24 used 100 hard games indexed 901–1,000 from 4nums.com with BFS keeping b=5 candidates and evaluating thoughts as sure/maybe/impossible; Creative Writing used 100 inputs from random sentences with depth 2, k=5 plans/passages, and voting; Mini Crosswords used 20 games from GooBix with DFS up to 100 steps, confidence aggregation, and pruning.
  • Baselines included IO prompting, CoT prompting, CoT self-consistency, and iterative refinement; metrics included task success rates, GPT-4 coherency scores, human blind pairwise comparisons, and letter/word/game success for crosswords.

Limitations

  • Stated: ToT may not be necessary for tasks GPT-4 already excels at; the paper explores only three relatively simple tasks that challenge GPT-4; ToT requires more resources and API cost than sampling methods; and the work uses an off-the-shelf LM without fine-tuning.
  • Stated/evident: cost and efficiency depend heavily on prompts and search algorithms, and ToT can require 5–100 times more generated tokens than CoT; for Game of 24, ToT used 5.5k completion tokens and cost $0.74 per case versus CoT best-of-100 at 6.7k tokens and $0.47.
  • Evident from text: the state evaluator is imperfect—sometimes pruning states for crosswords that are actually solvable, possibly due to rare or obsolete words—and output heuristics can be improved, since oracle best-state selection raised Mini Crosswords game success from 4/20 to 7/20; ablating pruning or backtracking generally worsened performance.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

DataCite · 10.48550/arxiv.2305.10601

Cites

0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Claims the paper makes

0 of 34 cited sources checked · 0 supported · 0 flagged

  • Findingown data

    ToT (7.56) generates more coherent passages than IO (6.19) and CoT (6.93) on average in creative writing.

    “Figure 5(a) shows average GPT-4 scores across 100 tasks, where ToT (7.56) is deemed to generate more coherent passages than IO (6.19) and CoT (6.93) on average.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: The LM's self-evaluations of states need only be approximately helpful for decision making, not perfect.
    • Rests on an assumption: The GPT-4 zero-shot 1-10 scalar score is a valid measure of passage coherency.
  • Findingown data

    Around 60% of CoT samples failed Game of 24 after generating the first step.

    “Notably, around 60% of CoT samples already failed the task after generating the first step, or equivalently, the first three words (e.g.”
    Quote in the paperSubstantial claim
  • Findingown data

    ToT significantly enhances language models' problem-solving abilities on three novel tasks requiring non-trivial planning or search: Game of 24, Creative Writing, and Mini Crosswords.

    “Our experiments show that ToT significantly enhances language models' problem-solving abilities on three novel tasks requiring non-trivial planning or search: Game of 24, Creative Writing, and Mini Crosswords.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: The LM's self-evaluations of states need only be approximately helpful for decision making, not perfect.
  • Findingown data

    GPT-4 can follow the input constraints most of the time in the creative writing task.

    “As we find that GPT-4 can follow the input constraints most of the time, we focus on evaluating passage coherency in two ways: using a GPT-4 zero-shot prompt to provide a 1-10 scalar score, or using human judgments to compare pairs of outputs from different methods.”
    Quote in the paperSubstantial claim
  • Findingown data

    IO and CoT prompting methods perform poorly on Mini Crosswords with a word-level success rate less than 16%.

    “As shown in Table 3, IO and CoT prompting methods perform poorly with a word-level success rate less than 16%, while ToT significantly improves all metrics, achieving a word-level success rate of 60% and solving 4 out of 20 games.”
    Quote in the paperSubstantial claim
  • May combine two claims. 30
  • Classified as probably not a substantial claim. 33

  • May combine two claims.

    Findingown data

    Without pruning, ToT can find the correct solution for 4/20 Mini Crosswords games, though only outputting 1 via heuristic; 3 of these are games ToT+pruning cannot solve within 100 steps.

    “However, it could actually find the correct solution for 4/20 games (though only outputting 1 via heuristic), 3 of which are games ToT+pruning cannot solve within 100 steps.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data

    IO, CoT, and CoT-SC prompting methods perform badly on Game of 24, achieving 7.3%, 4.0%, and 9.0% success rates respectively.

    “As shown in Table 2, IO, CoT, and CoT-SC prompting methods perform badly on the task, achieving only 7.3%, 4.0%, and 9.0% success rates.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data

    ToT with breadth b=1 achieves 45% success on Game of 24, while b=5 achieves 74%.

    “In contrast, ToT with a breadth of b = 1 already achieves a success rate of 45%, while b = 5 achieves 74%.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: The LM's self-evaluations of states need only be approximately helpful for decision making, not perfect.

  • May combine two claims.

    Findingown data

    ToT significantly improves all metrics on Mini Crosswords, achieving a word-level success rate of 60% and solving 4 out of 20 games.

    “As shown in Table 3, IO and CoT prompting methods perform poorly with a word-level success rate less than 16%, while ToT significantly improves all metrics, achieving a word-level success rate of 60% and solving 4 out of 20 games.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: The LM's self-evaluations of states need only be approximately helpful for decision making, not perfect.

  • May combine two claims.

    Findingown data

    In Game of 24, GPT-4 with chain-of-thought prompting solved 4% of tasks, while ToT achieved a success rate of 74%.

    “For instance, in Game of 24, while GPT-4 with chain-of-thought prompting only solved 4% of tasks, our method achieved a success rate of 74%.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: The LM's self-evaluations of states need only be approximately helpful for decision making, not perfect.

  • May combine two claims.

    Findingown data

    CoT scales better than IO on Game of 24, and best of 100 CoT samples achieve 49% success, but still much worse than exploring more nodes in ToT (b>1).

    “Not surprisingly, CoT scales better than IO, and best of 100 CoT samples achieve a success rate of 49%, but still much worse than exploring more nodes in ToT (b > 1).”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Findingown data

    The 5 GPT-4 coherency scores are usually consistent, with a standard deviation of around 0.56 on average across outputs.

    “For the former, we sample 5 scores and average them for each task output, and we find these 5 scores usually consistent, with a standard deviation of around 0.56 on average across outputs.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data

    In human coherency comparison, CoT > ToT for 21 pairs, Similar for 38, ToT > CoT for 41.

    “CoT > ToT Similar ToT > CoT 0 10 20 30 40 21 38 41 (b) Human coherency comparison”
    Quote in the paperSubstantial claim
    • Rests on an assumption: The subset of authors used for human judgments is representative of human readers.

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Findingnone given

    Search methods like ToT require more resources, such as GPT-4 API cost, than sampling methods in order to improve task performances.

    “Also, search methods like ToT requires more resources (e.g.GPT-4 API cost) than sampling methods in order to improve task performances”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data

    GPT-4 generation + GPT-3.5 evaluation achieves 64% on Game of 24, and GPT-3.5 generation + GPT-4 evaluation achieves 31%.

    “To further understand the importance of generation vs. evaluation, we ran GPT-4 generation + GPT-3.5 evaluation (64%) and GPT-3.5 generation + GPT-4 evaluation (31%).”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Findingreasoning

    Completing Game of 24 and Creative Writing's main ToT experiments cost around 106 dollars.

    “So completing Game of 24 and Creative Writing's main ToT experiments cost around 0.74 × 100 + 0.32 × 100 = 106 dollars.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data

    On Creative Writing, GPT-3.5+ToT outperforms GPT-4+IO and is similar to GPT-4+CoT.

    “On Creative Writing, we find GPT-3.5+ToToutperform GPT-4+IO, and similar to GPT-4+CoT”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data

    ToT improves over CoT on GSM8K and StrategyQA, but only slightly.

    “As shown in Table 4 and as expected, ToT improves over CoT on both tasks (but only slightly, given GPT-4 + CoT is already very good on such tasks, and StrategyQA's bottleneck is external knowledge, not reasoning).”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data

    In general, cost and efficiency of ToT highly depend on the prompts and search algorithms used, and could require 5-100 times more generated tokens than CoT.

    “In general, cost and efficiency of ToT highly depend on the prompts and search algorithms used, and could require 5-100 times more generated tokens than CoT.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S4 (based).

    Interpretationnone given

    ToT requires no extra training; a pre-trained LM is sufficient.

    “Convenience.No extra training is needed, just a pre-trained LM is sufficient.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    Scaled-up LMs such as GPT and PaLM have been shown capable of performing an ever wider range of tasks requiring mathematical, symbolic, commonsense, and knowledge reasoning.

    “Originally designed to generate text, scaled-up versions of language models (LMs) such as GPT [25,26,1,23] and PaLM [5] have been shown to be increasingly capable of performing an ever wider range of tasks requiring mathematical, symbolic, commonsense, and knowledge reasoning.”
    Quote in the paperNot a substantial claim0 of 5 sources checked
    • cites [25]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

    • cites [26]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

    • cites [1]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

    • cites [23]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

    • cites [5]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Classified as probably not a substantial claim.

    Interpretationnone given

    ToT frames any problem as a search over a tree, where each node is a state representing a partial solution with the input and the sequence of thoughts so far.

    “ToT frames any problem as a search over a tree, where each node is a state s = [x, z 1•••i ] representing a partial solution with the input and the sequence of thoughts so far.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S4 (based).

    Interpretationnone given

    ToT is general in that IO, CoT, CoT-SC, and self-refinement can be seen as special cases of ToT (trees of limited depth and breadth).

    “Generality.IO, CoT, CoT-SC, and self-refinement can be seen as special cases of ToT (i.e.trees of limited depth and breadth; Figure 1).”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    Chain-of-thought prompting was proposed to address cases where mapping input to output is non-trivial by introducing a chain of thoughts as intermediate steps.

    “Chain-of-thought (CoT) prompting [38] was proposed to address cases where the mapping of input x to output y is non-trivial (e.g. when x is a math question and y is the final numerical answer).”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [38]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

    Premisecitation

    RAP is a concurrent work that treats language model reasoning as planning with its internal world model and proposes an MCTS-based method similar to ToT.

    “RAP [9] is a concurrent work that treats language model reasoning as planning with its internal world model, and proposes a MCTS-based method similar to ToT.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [9]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    More general crosswords can be readily solved with specialized NLP pipelines that leverage large-scale retrieval instead of LM.

    “Again, the goal is not just to solve the task, as more general crosswords can be readily solved with specialized NLP pipelines [34] that leverages large-scale retrieval instead of LM.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [34]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Classified as probably not a substantial claim. May combine two claims.

    Interpretationnone given

    The three tasks require deductive, mathematical, commonsense, lexical reasoning abilities, and a way to incorporate systematic planning or search.

    “These tasks require deductive, mathematical, commonsense, lexical reasoning abilities, and a way to incorporate systematic planning or search.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim.

    Premisecitation

    Research on dual process models suggests people have two modes: a fast, automatic, unconscious mode (System 1) and a slow, deliberate, conscious mode (System 2).

    “Research on”
    Quote in the paperSubstantial claim0 of 4 sources checked
    • cites [30]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

    • cites [31]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

    • cites [16]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

    • cites [15]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

    Study design and conductown data

    The paper employs a subset of the authors in a blind study to compare the coherency of CoT vs. ToT generated passage pairs, with the order of passages randomly flipped over 100 inputs.

    “For the latter, we employ a subset of the authors in a blind study to compare the coherency of CoT vs. ToT generated passage pairs, where the order of passages is random flipped over 100 inputs.”
    Quote in the paperNot a substantial claim

  • Classified as probably not a substantial claim.

    Premisecitation

    Newell and colleagues characterized problem solving as search through a combinatorial problem space, represented as a tree.

    “Newell and colleagues characterized problem solving [21] as search through a combinatorial problem space, represented as a tree.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [21]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Probably not a substantial claim: may not pass S4 (based).

    Premisenone given

    Language models are still confined to token-level, left-to-right decision-making processes during inference.

    “Language models are increasingly being deployed for general problem solving across a wide range of tasks, but are still confined to token-level, left-to-right decision-making processes during inference.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Premisecitation

    CoT-SC improves upon CoT because there are generally different thought processes for the same problem and the output decision can be more faithful by exploring a richer set of thoughts.

    “CoT-SC improves upon CoT, because there are generally different thought processes for the same problem (e.g.different ways to prove the same theorem), and the output decision can be more faithful by exploring a richer set of thoughts.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [36]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • May combine two claims.

    Interpretationreasoning

    Within each CoT chain there is no local exploration of different thought steps, and the most frequent heuristic only applies when the output space is limited.

    “However, within each chain there is no local exploration of different thought steps, and the”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationnone given

    ToT extends existing planning formulations by considering multiple potentially feasible plans simultaneously at each problem-solving step and proceeding with the most promising ones.

    “Our proposed ToT approach extends existing planning formulations by considering multiple potentially feasible plans simultaneously at each problem-solving step, and proceeding with the most promising ones.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim.

    Interpretationreasoning

    ToT actively maintains a tree of thoughts, where each thought is a coherent language sequence that serves as an intermediate step toward problem solving.

    “ToT actively maintains a tree of thoughts, where each thought is a coherent language sequence that serves as an intermediate step toward problem solving (Table 1).”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationreasoning

    The simple associative token-level choices of LMs are reminiscent of System 1 and might benefit from augmentation by a more deliberate System 2 planning process.

    “The simple associative token-level choices of LMs are also reminiscent of”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Premisecitation

    Traditional decision-making procedures usually require training dedicated reward and policy models as in reinforcement learning, whereas ToT uses the LM itself to provide value estimates for decision making.

    “On the other hand, traditional decision-making procedures usually require training dedicated reward and policy models as in reinforcement learning (for example CHAI [33]), whereas we use the LM itself to provide the value estimates for decision making.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [33]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • May combine two claims.

    Interpretationreasoning

    Tree of Thoughts (ToT) generalizes over Chain of Thought prompting and enables exploration over coherent units of text (thoughts) that serve as intermediate steps toward problem solving.

    “we introduce a new framework for language model inference,”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S4 (based).

    Premisenone given

    The underlying mechanism for generating text in LMs is still the original autoregressive mechanism, making token-level decisions one by one and left-to-right.

    “It is perhaps surprising that underlying all this progress is still the original autoregressive mechanism for generating text, which makes token-level decisions one by one and in a left-to-right fashion.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationreasoning

    ToT allows LMs to perform deliberate decision making by considering multiple reasoning paths and self-evaluating choices, and by looking ahead or backtracking when necessary.

    “ToT allows LMs to perform deliberate decision making by considering multiple different reasoning paths and self-evaluating choices to decide the next course of action, as well as looking ahead or backtracking when necessary to make global choices.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim.

    Interpretationnone given

    ToT is modular: the base LM, thought decomposition, generation, evaluation, and search procedures can all be varied independently.

    “Modularity.The base LM, as well as the thought decomposition, generation, evaluation, and search procedures can all be varied independently.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S4 (based). May combine two claims.

    Interpretationnone given

    Such a deliberate heuristic can be more flexible than programmed rules, and more sample-efficient than learned models.

    “When applicable, such a deliberate heuristic can be more flexible than programmed rules, and more sample-efficient than learned models.”
    Quote in the paperNot a substantial claim
    • The authors state this as an assumption: The LM's self-evaluations of states need only be approximately helpful for decision making, not perfect.

  • Classified as probably not a substantial claim. May combine two claims.

    Interpretationnone given

    ToT is adaptable to different problem properties, LM capabilities, and resource constraints.

    “Adaptability.Different problem properties, LM capabilities, and resource constraints can be accommodated.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

    Premisecitation

    Self-eval guided decoding follows a tree-search procedure with leaves sampled from stochastic beam search decoding, which are then evaluated by the LLM itself with carefully prepared self-eval prompts.

    “Similar to our method, self-eval decoding also follows a tree-search procedure with leaves sampled from stochastic beam search decoding, which are then evaluated by LLM itself with carefully prepared self-eval prompts.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [39]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • May combine two claims.

    Premisecitation

    Schlag et al.'s approach differs from ToT in that trees are expanded by sampling external paragraphs instead of the LM's own thoughts, and there is no reflection or voting steps.

    “This approach however differs from ours in that trees are expanded by sampling external paragraphs instead of the LM's own thoughts, and there is no reflection or voting steps.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [27]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Interpretationnone given

    The modular flexibility of ToT allows users to customize performance-cost tradeoffs.

    “but the modular flexibility of ToT allows users to customize such performance-cost tradeoffs”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    NeuroLogic A*esque decoding is inspired by A* search but introduces look-ahead heuristics efficient for LMs to improve beam-search or top-k sampling decoding.

    “From this perspective, our method is also related to NeuroLogic A*esque decoding [19], which is inspired by A* search but introduces look-ahead heuristics that are efficient for LMs to improve the beam-search or top-k sampling decoding.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [19]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    Schlag et al. embeds LMs in an algorithmic search procedure to help solve problems like question answering step-by-step, in which search trees are expanded by relevant paragraphs that might provide answers.

    “For example, Schlag et al. [27] embeds LMs in an algorithmic search procedure to help solve problems like question answering step-by-step, in which the search trees are expanded by relevant paragraphs that might provide answers.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [27]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Probably not a substantial claim: may not pass S4 (based).

    Interpretationnone given

    ToT is a framework that empowers LMs to more autonomously and intelligently make decisions and solve problems.

    “ToT is a framework that empowers LMs to more autonomously and intelligently make decisions and solve problems.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Interpretationreasoning

    Crosswords' DFS experiments should be also within 100 dollars.

    “Crosswords' DFS experiments should be also within 100 dollars.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Study design and conductnone given

    This work only explores three relatively simple tasks that challenge GPT-4.

    “as an initial step this work only explores three relatively simple tasks that challenges GPT-4”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Premisecitation

    NeuroLogic A*esque decoding is constrained to sentence generation tasks, whereas ToT is designed for complex, multi-step problem solving guarded by value feedback.

    “This method however is constrained to sentence generation tasks, whereas our framework are designed for complex, multi-step problem solving guarded by value feedback.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [19]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Interpretationcitation

    ToT can be considered a heuristic search algorithm like A*, in which the heuristic at each search node is provided by the LM's self-assessment.

    “For example it can be considered as a heuristic search algorithm like A* [10], in which the heuristic at each search node is provided by the LM's selfassessment.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [10]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Interpretationnone given

    LMs address a weakness of classical methods by providing a way to solve complex problems that are not easily formalized, such as creative writing.

    “At the same time, LMs address a weakness of these classical methods, providing a way to solve complex problems that are not easily formalized, such as creative writing.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Premisecitation

    Self-eval guided decoding uses the PAL formulation, which represents thoughts as codes, making it difficult to tackle challenging tasks like creative writing.

    “Their approach however, uses the PAL formulation [8] which represents thoughts as codes, which makes it difficult to tackle challenging tasks like creative writing which we consider in this paper.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [8]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based). May combine two claims.

    Interpretationreasoning

    ToT improves the interpretability of model decisions and the opportunity for human alignment, as the resulting representations are readable, high-level language reasoning instead of implicit, low-level token values.

    “On the other hand, ToT also improves the interpretability of model decisions and the opportunity for human alignment, as the resulting representations are readable, high-level language reasoning instead of implicit, low-level token values.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Premisenone given

    RAP's tasks are simpler than ToT's, and its framework lacks the modularity to incorporate different tree search algorithms.

    “However, its tasks are simpler than ours, and its framework lacks the modularity to incorporate different tree search algorithms.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [9]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Interpretationown data

    Deliberate search such as ToT might not be necessary for many existing tasks that GPT-4 already excels at.

    “Deliberate search such as ToT might not be necessary for many existing tasks that GPT-4 already excels at (see Appendix B.1)”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S2 (checkable).

    Interpretationreasoning

    The Tree of Thoughts framework provides a way to translate classical insights about problem-solving into actionable methods for contemporary LMs.

    “The Tree of Thoughts framework provides a way to translate classical insights about problem-solving into actionable methods for contemporary LMs.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationreasoning

    The Tree-of-Thought formulation is more versatile and handles challenging tasks on which GPT-4 only achieves very low accuracy with standard prompts.

    “Our Tree-of-Thought formulation is thus more versatile and handles challenging tasks on which GPT-4 only achieves very low accuracy with standard prompts.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    LLM+P delegates the actual planning process to a classical planner.

    “Another approach, LLM+P [18], goes one step further and delegates the actual planning process to a classical planner.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [18]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

56 of 56

  • The authors state this as an assumption.

    The LM's self-evaluations of states need only be approximately helpful for decision making, not perfect.

    “Such valuations do not need to be perfect, and only need to be approximately helpful for decision making.”

  • The paper relies on this without support.

    The GPT-4 zero-shot 1-10 scalar score is a valid measure of passage coherency.

    “we focus on evaluating passage coherency in two ways: using a GPT-4 zero-shot prompt to provide a 1-10 scalar score, or using human judgments to compare pairs of outputs from different methods.”

  • The paper relies on this without support.

    The subset of authors used for human judgments is representative of human readers.

    “we employ a subset of the authors in a blind study to compare the coherency of CoT vs. ToT generated passage pairs, where the order of passages is random flipped over 100 inputs.”
3 of 3

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Memory modules maintain internal states for reasoning to ensure coherence of thought.

    “First, these modules maintain internal states for reasoning to ensure the coherence of thought (Yao et al., 2023; Sun et al., 2025c);”

    From From Storage to Experience: A Survey on the Evolution of LLM Agent Memory Mechanisms (2026) · cites this paper as Yao et al., 2023

    Section 3 describes Tree of Thoughts as a search over states that contain the input and the sequence of thoughts so far, supporting the internal-state part of the claim. The paper does not describe these states as memory modules or say that maintaining them ensures coherence of thought. (LLM, conf=0.82)

    Experimental — accuracy not yet measured

  • Augmentations such as the ReAct framework or Tree-of-Thoughts introduce pseudo-recursive reasoning but remain fundamentally heuristic and lack true internal models of time, causality, or state evolution.

    “Although augmentations such as the ReAct framework [136] or Tree-of-Thoughts [164] introduce pseudo-recursive reasoning, they remain fundamentally heuristic and lack true internal models of time, causality, or state evolution.”

    From AI Agents vs. Agentic AI: A Conceptual taxonomy, applications and challenges (2026) · cites this paper as [164]

    Section 3 describes ToT as searching over partial-solution states and heuristically evaluating which to explore; the Introduction describes lookahead and backtracking. These passages support the characterization of ToT as a heuristic reasoning augmentation, but the paper does not say that it lacks true internal models of time, causality, or state evolution. This verdict concerns ToT, not the separately cited ReAct framework. (LLM, conf=0.85)

    Experimental — accuracy not yet measured

  • Research on language agent decision-making has progressed from simple action proposal to intermediate reasoning/retrieval to complex iterative proposal and evaluation.

    “Empirically, many early language agents simply use LLMs to propose an action (Schick et al., 2023), a sequence of actions (Huang et al., 2022b), or evaluate a fixed set of actions (Ahn et al., 2022) without intermediate reasoning or retrieval. Followup work (Yao et al., 2022b; Shinn et al., 2023; Xu et al., 2023b; Lin et al., 2023; Wang et al., 2023a; Park et al., 2023) has exploited intermediate”

    From Cognitive Architectures for Language Agents (2023) · cites this paper as Yao et al., 2023

    The Introduction and Section 3 describe Tree of Thoughts as generating, evaluating, and searching multiple intermediate reasoning paths with lookahead and backtracking. Section 5 contrasts this with earlier planning approaches, but our copy does not establish the claimed progression through intermediate retrieval or the full history of language-agent action selection. (LLM, conf=0.84)

    Experimental — accuracy not yet measured

  • Tree of Thoughts has no long-term memory, and only reasoning in its internal action space.

    “It has no long-term memory, and only reasoning in its internal action space, but differs from all previous agents in its deliberate decision-making.”

    From Cognitive Architectures for Language Agents (2023) · cites this paper as Yao et al., 2023

    Section 3 describes ToT as searching over states made up of the input and thoughts generated so far, supporting the description of reasoning within a thought space. The Broader Impact section says interaction with external environments is a future application. Our copy does not establish that ToT has no long-term memory. (LLM, conf=0.84)

    Experimental — accuracy not yet measured

  • Tree of Thoughts can be seen as a special kind of language agent with only one external action: submitting a final solution to a reasoning problem.

    “Tree of Thoughts (ToT) (Yao et al., 2023) can be seen as a special kind of language agent with only one external action: submitting a final solution to a reasoning problem (game of 24, creative writing, crosswords puzzle).”

    From Cognitive Architectures for Language Agents (2023) · cites this paper as Yao et al., 2023

    Section 3 describes ToT as a language-model framework that searches over intermediate thoughts, and Sections 4.1–4.3 describe final outputs for Game of 24, creative writing, and mini crosswords. The paper does not characterize ToT as a language agent or establish that submitting a final solution is its only external action. (LLM, conf=0.82)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

Each contradiction between two passages listed here was confirmed by an independent check.

  • DFS pruning evaluates the parent instead of the candidate state

    Minor

    Algorithm 2 supplies the candidate state s′ to the evaluator but requests a value for its parent s. This conflicts with the stated definition of the evaluator, which assigns values to states in the supplied set, and does not test whether s′ should be pruned.

1 of 1

Cites

The publisher hasn’t deposited this paper’s reference list.

Research works printed but not linked: 4

  1. P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2):100-107, 1968.
  2. A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, I. Sutskever, et al. Language models are unsupervised multitask learners. OpenAI blog, 1(8):9, 2019.
  3. S. A. Sloman. The empirical case for two systems of reasoning. Psychological bulletin, 119(1): 3, 1996.
  4. K. E. Stanovich. Who is rational? Studies of individual differences in reasoning. Psychology Press, 1999.

Cited by

Sorted by citations

Authors
Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T. L., Cao, Y., & Narasimhan, K.
ORCID
Venue
arXiv
Publisher
arXiv
Published
2023
Pages
11809-11822
ISSN
1049-5258 (ISSN-L)
DOI
10.48550/arxiv.2305.10601
arXiv
2305.10601
OpenAlex
W7133209886
Cited by
1,158
References
0
Citations by year
2026: 476 · 2025: 320 · 2024: 284 · 2023: 77 · 2020: 1
FWCI
206.23
Type
conference paper
Language
en
Open access
Licence
Locations
  • neural information processing systems (publishedVersion)
  • arXiv (Cornell University) (submittedVersion, cc-by)
  • arXiv (Cornell University) (cc-by)
Funders
National Science Foundation (2239363)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › AI-based Problem Solving and Planning
  • Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
  • Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
Keywords
tree-of-thought, large language models, chain-of-thought prompting

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Claims read by deepseek-v4.1-flash under definition version 3 (extract-v3) on 2026-10-23.

Classified by jev-1.13-20260917 (gold-guideline-v0.2) on 2026-10-23.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review