Tree of Thoughts: Deliberate Problem Solving with Large Language Models

Summary

The paper introduces an innovative concept of problem-solving that utilizes a tree-like structure of thoughts, constructed and evaluated by the LLM, specifically GPT-4. To illustrate the efficacy of this technique, the authors have incorporated three distinct tasks: the Game of 24, creative writing, and crossword puzzles. These tasks have been chosen as they require different capabilities to be solved. Several iterations of the tree-like structure of thoughts were examined, including those combined with Breadth-First Search (BFS) or Depth-First Search (DFS), along with other variations with different hyperparameters. A comprehensive comparison has been drawn with various other Language Learning Model-based baselines.

Strengths

The value of examining the tree-like thinking process performed by LLM is evident to the scientific community. Primarily, the Tree of Thoughts (ToT) could be applicable to other tasks when adequately adapted and it provides an intriguing exploration of GPT-4's capabilities. The paper intriguingly selects tasks requiring diverse skill sets: - The game of 24 demands fundamental mathematical capabilities and the ability to assess whether success is achievable from a partial solution. - Creative writing needs the generation of coherent and sound text under strict constraints. - Crossword puzzles necessitate linguistic knowledge and the capacity to search across a vast state space (large word sets that meet given constraints). The authors have made a commendable effort to objectively assess the results, with blind tests of text coherency serving as a prime example. The elucidation of the method is lucid, with Figure 1 being particularly illuminating. Additionally, most experiments are presented in a comprehensible manner. A significant strength lies in ToT's performance, which significantly surpasses that of the baseline. I perceive this paper to be a successful proof-of-concept for ToT. Notably, its significance chiefly stems from the ongoing massive efforts aimed at leveraging LLM's capabilities. A prominent challenge in applying LLMs for deliberate problem solving

Weaknesses

The biggest weakness of ToT is that the paper lacks the evaluation of some important properties of ToT. Here I put a list: 1. There is no data about the price of ToT compared with baselines (there is a short mention in the Limitations about the price/success rate trade-off). In the best case, I would like to have a graph where there is a success rate on the y-axis and a price on the x-axis. If you think that such a graphical analysis would be too detailed please put some data in a table. The price of GPT-4 may be different in the future, so alternatively you can add information about the number of tokens used by ToT per solution compared with baselines. Probably the best would be to have both information: price and number of tokens. 2. There is no data about the time execution of ToT compared with baselines. Comment on 1. and 2. : Knowing the average price and time is very important for readers who consider building their own methods on top of ToT or consider applying ToT to their task. 3. Some additional comparisons are missing. We know that a single execution of ToT is significantly more powerful than a single execution of baseline (for example IO). However is it possible that running IO or CoT many times (until it finds a solution) is actually cheaper and faster than ToT? ToT will still have scientific value even in the case where the answer to the previous question is positive, but the scientific community will benefit from knowing it. Currently, it is not really known what are the maximum capabilities of properly used LLM and how to maximize its performance. In a search for the most effective methods, we need to know as many properties of each approach as possible. Knowing more about ToT would add great value to the paper. Here is a list of my suggestions for additional comparisons: > How many times on average should I run a baseline to find a solution compared with ToT? > Can baseline be cheaper or faster than ToT even though it is weaker? If it is impossible to gather detailed data for this comparison, please provide some estimates. 4. While I see value in the creative writing task, I am not very convinced that a task with just one ToT step is meaningful when evaluating tree search algorithms. More precisely: while formally this task falls under the ToT framework, it's hard to think about it in terms of tree search.

Questions

Necessary things (either to address here or in the paper): - Figure 3b: The title of the figure is “Samples failed at each step”, and there last two bars show success not failures (the one named “Correct”). It is misleading, I first thought that ToT failed mainly at the last step. Another problem with this comparison is that ToT with b=5 vs CoT seems unfair to me (ToT has many samples at each state while CoT does not - it is not surprising that CoT stands no chance). The better comparison would be for example: ToT vs CoT-SC or ToT vs CoT-best of 100. - In Table 2 and Figure 3 there is no information about the error estimation. It should be at least in text somewhere The total cost of the experiments done during the work on this paper should be stated in the paper or in supplementary materials. - line 186. I would change "left" to "remaining" (numbers). For a while, I was wondering if left refers to "left to do" or "left side". - line 134: dot missing at the end of the sentence - Algorithm 2 and line 279: how exactly does the pruning work? - lines 222 to 225: Here you describe an iterative-refine method as a baseline. Would such a method be reasonable for baselines in Game of 24? Suggestions, ideas, and comments: -All the tasks presented here could be solved without ToT (and two of them even without LLM). Maybe you have some intuition for what kind of problems ToT would be necessary? I know that this may be hard or even impossible to answer. - It would be very interesting to see a comparison of ToT based on GPT3.5 vs IO GPT4 or CoT GPT4. Can weaker LLM with ToT be stronger than Sota LLM? I think such an experiment would add great value to the paper. - The comment at the bottom of page 8 is very interesting

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The limitations section is sound.

Summary

This paper proposes Tree of Thoughts to promote deliberate problem solving with LLMs. By using a tree-based structure and a four-step process towards problem solving, tree of thoughts successfully address many of the challenges with left-to-right decoding such as looking ahead, backtracking, considering multiple reasoning paths at the same time, and more. Extensive experiments on three reasoning tasks demonstrate the superiority of Tree of Thoughts over ICL, CoT, self consistency, and more.

Strengths

+ the Tree of Thoughts approach is well motivated by the limitations of autoregressive decoding + the four-step formulation is novel and clearly described + experiments on three reasoning tasks are extensive and convincing

Weaknesses

Overall I like this work and I only have a few comments. - I wonder if it might be possible to discuss the efforts required to adapt Tree of Thoughts to other tasks and reasoning formats. To me, it seems like other than the search algorithm (BFS/DFS), the other three parts would require some hand-crafted engineering from scratch for a different task. - I wonder if least to most [1] or decomposed prompting [2] might be possible baselines for the three tasks: they also discuss some sort of iterative problem solving potential. - In the "Game of 24" task, does the base LLM make arithmetic mistakes? If that's the case, would using tool learning strategies [3] further improve Tree of Thoughts in numeric reasoning tasks? - The supplementary material does not seem to contain an appendix, while some details might be helpful. For example, what is the prompt for GPT-4 zero-shot evaluation in line 213? What are the details of human evaluation for "Creative Writing"? (annotator head count, compensation, etc.) Also, it is increasingly common to present all the prompt texts in the appendix to facilitate reproducibility. I wonder if the authors might consider having an appendix to systematically document all details about the approach and experiments. [1] Zhou, Denny, et al. "Least-to-Most Prompting Enables Complex Reasoning in Large Language Models." The Eleventh International Conference on Learning Representations. 2022. [2] Khot, Tushar, et al. "Decomposed Prompting: A Modular Approach for Solving Complex Tasks." The Eleventh International Conference on Learning Representations. 2022. [3] Schick, Timo, et al. "Toolformer: Language models can teach themselves to use tools." arXiv preprint arXiv:2302.04761 (2023).

Questions

please see above

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Limitations are discussed in Section 6.

Summary

The paper presents a new framework for language model inference called Tree of Thoughts, which aims to improve the ability of language models to solve complex, multi-step problem-solving tasks. The framework involves generating a tree of possible plans for solving a given task, with each node in the tree representing a possible step in the plan. The language model then evaluates each node based on its own self-assessment, and the tree is expanded by sampling external paragraphs to generate new nodes. The framework also includes a voting step to determine the best plan to follow. The paper argues that this approach is more effective than previous methods for prompting language models, such as Chain of Thought, and can be seen as a modern rendition of classical search methods for problem-solving. The contributions of the paper include a detailed description of the Tree of Thoughts framework, an evaluation of its effectiveness on a range of problem-solving tasks, and a discussion of its potential limitations and future directions for research.

Strengths

1. The idea of upgrading chain-of-thoughts into tree-of-thoughts seems to be an intuitive extension and necessary step. There are many benefits of tree reasoning, including the ability to look ahead and backtrack to search for better traces. 2. The formulation of heuristics leverages the recent self-evaluation ability of GPT-4 to reuse the LLM to evaluate the quality of states via prompting. This relieves the necessity of training accurate state values and enables approximate estimation. 3. The empirical results on three tasks demonstrate the effectiveness of ToT compared with GPT-4 based baselines. The improvement gain is quite large on two tasks, considering GPT-4 based CoT methods don't work well on them.

Weaknesses

1. Unsurprisingly, the idea of extending linear reasoning to tree reasoning isn't a new thing. Specifically, [1] leverages beam search to guide the chain-of-thought to decode a better reasoning path, which is almost the same as the BFS in this paper. [1] also uses self-evaluation to provide heuristics. [2] also formulates the reasoning as a tree reasoning problem. More importantly, the application of BFS and DFS seems to be ad-hoc, and there could be more principled methods to guide the search. For example, [3, 4] applies MCTS to guide the search, which might have better planning abilities. 2. While ToT improves CoT naturally, it doesn't come without cost. One major concern is the efficiency issue for querying the expensive GPT-4 multiple times. The paper should give the audience a clearer idea of how cost ToT is compared with CoT, probably with an efficiency comparison between them. More interestingly, the paper should propose or at least discuss potential means to reduce the inference cost, such as using various smaller models for sampling or state evaluation, etc. 3. The application scope is largely limited. While the authors say they select the three tasks because they are hard, the selected three tasks are arguably narrow with two text games. One possible reason is that the selected tasks make the thought and state formulation easier and demonstrate improvement significantly. Nonetheless, it would be necessary to extend the scope to be more similar to CoT tasks to demonstrate the broader applicability of the proposed methods. [1]. Xie, Yuxi, et al. "Decomposition enhances reasoning via self-evaluation guided decoding." arXiv preprint arXiv:2305.00633 (2023). [2]. Jung, Jaehun, et al. "Maieutic prompting: Logically consistent reasoning with recursive explanations." arXiv preprint arXiv:2205.11822 (2022). [3]. Zhu, Xinyu, et al. "Solving math word problem via cooperative reasoning induced language models." arXiv preprint arXiv:2210.16257 (2022). [4]. Hao, Shibo, et al. "Reasoning with language model is planning with world model." arXiv preprint arXiv:2305.14992 (2023).

Questions

I raised multiple questions in the weakness section, and I hope the authors could further clarify them. Specifically, some can be reformualted as follows: 1. How hard is it to apply the proposed method to a more general NLP reasoning dataset, like GSM8K or StrategyQA, or other well-known datasets? If possible, I hope the authors could demonstrate one case using the proposed method to solve a more general task. 2. How necessary the GPT-4 is in the proposed framework? It seems GPT-4 is very powerful for self-evaluation, and how critical is this component for the success of the tasks?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

N/A

Summary

This paper introduces a new method for prompting large language models (LLMs) for multi-step reasoning tasks. Existing prompting methods are confined to the autoregressive generation scheme, making it difficult for LLMs to finish tasks that require exploration and planning. To alleviate this problem, the authors propose Tree of Thought (ToT), which combines the chain-of-thought (CoT) method with tree-based search. By prompting LLMs to solve the intermediate step and using the self-evaluations as the heuristics, one can effectively leverage LLMs to finish tasks that require exploration and backtracking. Empirical evaluations on three novel tasks demonstrate the effectiveness of the proposed method.

Strengths

- A novel method to combine LLMs with tree-based search. The proposed method alleviates the shortcoming of directly prompting LLMs to generate answers for some tasks that require explorations and backtracking. Compared to CoT prompting which can only sample one solution path, ToT allows LLMs to explore more potential solutions and find the best one. - Automatic and independent reasoning process. ToT fully depends on the LLMs to generate plans, finish intermediate steps, and generate self-evaluation for the current state as heuristics. Without the dependence on external tools or models, ToT enables LLMs to automatically finish complex tasks.

Weaknesses

More application scenarios. The authors mainly evaluate ToT on the three novel tasks that require exploration and backtracking. It would be better to demonstrate whether ToT can help improve LLMs on commonly-used reasoning tasks.

Questions

Please see the weakness above.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

The authors discussed the limitations and potential negative social impact of their work

Thanks for the response

Thanks for providing the additional data. The most interesting and promising is that GPT 3.5 with ToT can outperform GPT4 IO.

Thanks for responses and look forward to discussions

We want to thank Reviewers 3c3c and sEEP for responding to our rebuttal, and we look forward to engaging in discussions with Reviewers ysyd and fAU5 and addressing any potential remaining concerns in the remaining 4 days. Thanks in advance!

Thanks for the rebuttal

I appreciate the response and the new experiment results. My score remains the same for the following reasons: 1. Though one pair of experiment comparison shows that gpt-3.5+ToT outperforms gpr4+IO, in most cases, gpt-3.5+ToT doesn't work, esp, when used as the generation model. Therefore, whether the proposed work will be generalized to other models, esp., open-sourced models, is questionable or unanswered for me. If the proposed method can only work when using GPT-4, its cost will be one of the major obstacles for people to use it, also demonstrated by the new cost-efficiency result. 2. This paper is a well-polished one with near ideas implemented very well and I have no doubt about its influence on the community in the short near future. However, its core novelty of applying (simple) search algorithms to LLM reasoning isn't significant enough.