Boosting of Thoughts: Trial-and-Error Problem Solving with Large Language Models
Authors: Sijia Chen
Baochun Li
Di Niu
Venue: ICLR 2024 poster (2024)
Keywords: Large Language Models; Prompt Engineering; Boosting Mechanism;
Primary area: generative models

Abstract: The reasoning performance of Large Language Models (LLMs) on a wide range of problems critically relies on chain-of-thought prompting, which involves providing a few chain of thought demonstrations as exemplars in prompts. Recent work, e.g., Tree of Thoughts, has pointed out the importance of exploration and self-evaluation in reasoning step selection for complex problem solving. In this paper, we present Boosting of Thoughts (BoT), an automated prompting framework for problem solving with LLMs by iteratively exploring and self-evaluating many trees of thoughts in order to acquire an ensemble of trial-and-error reasoning experiences, which will serve as a new form of prompting to solve the complex problem. Starting from a simple prompt without requiring examples, BoT iteratively explores and evaluates a large collection of reasoning steps, and more importantly, uses error analysis obtained from the LLM on them to explicitly revise prompting, which in turn enhances reasoning step generation, until a final answer is attained. Our experiments with GPT-4 and Llama2 across extensive complex mathematical problems demonstrate that BoT consistently achieves higher or comparable problem-solving rates than other advanced prompting approaches.

Published as a conference paper at ICLR 2024
BOOSTING OF THOUGHTS: PROBLEM SOLVING WITH LARGE LANGUAGE MODELS
Sijia Chen, Baochun Li Department of Electrical and Computer Engineering
Di Niu
Department of Electrical and Computer Engincering, University of Alberta Edmonton, Alberta, Canada weiiuulbbera.c..
University of Toronto
Toronto, Ontario, Canada
cila.chen@mail il utoronto.caa, tocencc.oooontoed)
ABSTRACT
The reasoning performance of Large Language Models (LL.ss) on a wide range of problems critically relies on chain-of-thougl! prompting, which involves providing a few chain of thought demonstrations as exemplars in prompts. Recent work, e.g. Tree of Thoughts, has pointed out the importance of exploration and self- evaluation in reasoning step selection for complex problem solving. In this paper, present Boosting of Thoughts (BoT), an automated prompting framework for problem solving with LLMs by iteratively exploring and self-evaluating many trees of thoughts in order acquire an ensemble of trial-and-error reasoning experiences, which will serve as a new form of prompting to solve the complex problem. Starting from simple prompt without requiring examples, BoT iteratively explores and evaluates a large collection of reasoning steps, and more importantly, uses error analysis obtained from the LLM on them to explicitly revise prompting, which in turn enhances reasoning step generation, until final answer attained. Our experiments with GPT-4 and Llama2 across extensive complex mathematical problems demonstrate that BoT consistently achieves higher or comparable problem-solving rates than other advanced prompting approaches. The source code is available under the folder examples/BoTReasoniis of //ghthhb. com/ iQua/ 11mpebase
INTRODUCTION
Large language models (LLMs) with the autoregressive paradigm have gained remarkable performance across various tasks due to their potential reasoning ability Brown et al. (2020); Lewkowyez et al. (2022). The guarantee of such ability in complex tasks heavily relies on chain-of- thought (CoT) Wei et al. (2022) prompting, which provides step-by-step reasoning examples. This approach suggests that the reasoning ability can be elicited through a chain of thoughts, where a thought serves intermediate step toward problem solving.
Thus, subsequent studies Fu et al. (2022); Wang et al. (2022); Yao et al. (2024); Besta et al. (2023). especially
(ToT) Yao (2024), have been proposed improve COT. To guarantee effectiveness, the prompt of these approaches generally includes human annotations on one specific task. Such reliance limits their scalability. Recent work that either employs double-check with
LLMs to improve answers Paul et al.] (2023); WWeng et al. (2023): Madaan et al. (2023) or boosts prompts based on feedback Zheng al. Zhang et al. (2023a): Hou al. (2023); Pitis et al.) (2023) has demonstrated significant promise. The existing literature generally tends to discard ineffective thoughts from the prompt. However, humans typically can continuously learn from errors by carefully analyzing them gain experience, thereby gradually improving performance. We therefore ask: whether the thought generation of LLMs can dispense with human annotation and mimic such a problem-solving way of humans to achieve effective reasoning across various tasks?
This paper proposes novel framework, shown in Fig. I referred to as the Boosting of Thoughts (BoT), which achieves the boosting mechanism that embraces aggregation and experience, thereby enabling the progressive refinement of unreliable reasoning steps (weak thoughts) by learning from emors eventually solve various problems. Starting with simple prompt without human annotations

---

Published as a conference paper at ICLR 2024
Step nofiltee Tryshee opentara
Taene un doreeet torg tangeeoat cont rambes,
Skep2 coe retie
namber
+
S.turn 3 noont 24
poosibble anst siroe
www.oooooooooooooaoaoaooo. Choosoon offear
cander ca an
anst sereet snswar 10624 Choose other comrion..
3:p
B.E...
Ecasied
2:4.2/48.5. 5.3. r.reseet
Step 064, 53
Figure 1: Boosting of thoughts iteratively enhances the prompt by adding experience, which comprises the analysis conducted by large language models (LLM or LM) on the generated thought chain. The experience specifically contains the thought chain itself, the corresponding error reports, and detailed advice on revising each reasoning step. Thus, those ineffective thoughts marked with red cross can also contribute to prompt refinement. By accumulating experiences over iterations in the prompt. BoT can eventually yield correct thought chain starting from simple prompt. The examples presented here are extracted from results obtained by applying GPT-4 with BoT on the Game of 24 task.
for LLMs, BoT may get weak thoughts. With aggregation, BoT is capable of deriving a more logical and effective thought chain from them, thereby guiding the subsequent refinement. This guidance in our framework is achieved by tuning the prompt with experience, which is the detailed error reports, advice, and instructions of each reasoning step obtained by exploiting LLMs to analyze the aggregated chain. When such experience accumulates in the prompt, it gradually leads to stronger thoughts.
Specifically, BoT implements such Boosting mechanism as an experience iteration process, as shown in Fig. [ In each iteration, for a given prompt, BoT builds massive simplistic thought structures in parallel with the LLM. We select the tree structure as in ToT Yao et al. (2024) but significantly modify it to weighted binary trees with various growth strategies for our boosting purposes. After extracting the root-to-leaf branch with the highest score per tree, the aggregation component of BoT is performed to aggregate them into one single thought chain. Subsequently, this chain is evaluated by the same LLM to gain the experience, which is added to the prompt as guidance for the thought generation in the next iteration.
Our contributions can be summarized in three folds. First, instead of generating more complicated structures for thoughts with well-designed prompts, this paper shows that it is possible to rely solely on a simple initial prompt, as weak thoughts can be refined progressively based on previous experience toward solving problems. Second, to achieve such a boosting mechanism, we propose Boosting of Thoughts (BoT), a novel framework that performs an experience-drive iterative process. Due to starting from simple prompt, BoT is scalable across various tasks. While guaranteeing effectiveness, BoT is fast as it builds simplistic thought structures in parallel and converges to a solution after few iterations. Finally, with GPT-4 and LlamaV2, we evaluate the performance of BoT on complex mathematical problems. Finally, relying on GPT-44OpenAy (2023) and Llama V2 Touvron et al. (2023), evaluate the performance of BoT complex mathematical problems. The problem- solving rates indicate that Bo',, employing binary tree thought structures, significantly the GSMSK and AQuA while achieving the second-bes results
surpasses the current ofte--of-the-rt on other datasets. Especially on the new challenging task, Game of 24 Yao et al. (0024), BoT is 9.7% higher than the leading approach ToT. Our BoT thus demonstrates that, through enhancing the prompt by accumulating error analysis of ineffective thought chains and the corresponding advice, even without human annotation, LLMs are scalable across various tasks while sustaining high performance.
2 RELATED WORK
Multi-Step Reasoning. The prominent work Chain-of-thought (CoT) prompting Wei et al. (2022) shows that step-by-step reasoning behaviors from LLMs can be elicited by providing intermediate reasoning steps, termed thoughts, within the prompt for each question, as also supported by Self- Consistency Wang et al. (2022) and a series of -bseb work Zhou et al. (2023b); Fu et al. (2022). The recent work, Tree of Thoughts (ToT) Yao et al. (2024), converts the sequential reasoning process into a tree structure, in which each thought (node) may consider previous reasoning paths to produce multiple next-step thoughts. With such backtracking and expanded exploration during reasoning.
2

---

Considering its high Published as a conference paper at ICLR 2024
ToT performs well problems that even challenge GPT-4 OpenAl ability, the base thought structure of BoT largely utilizes this tree thought structure ToT. And, thanks to the boosting framework, the tree structure generated in each iteration of BoT is binary and shallow instead of the ToTs' complex tree, in which each node corresponds to massive child nodes. However, the base structure is not restricted to ToT. In contrast, BoTI' is flexible the hase thought structure can be either ToT, GoT Besta et al. (2023). or CR Zhang et al. (2023b), where Graph of Thoughts (GoT) Besta et al. (2023) the most recent work that expands the thought structure into graph format. This paper will only focus on the ToT as the base thought structure and leave the usage of GoTT for future work.
2023).
Automatic Prompting. Releasing humans from task-specific prompts attracts much attention Shin jet al. 2020)_ To guarantee the reasoning ability of L.MMs, conventional CoT Wei et al. (2022) relies on human priors to manually generate task-specific demonstrations as the prompt. However, the
zero-shot Kojima al. (2022) shows that even without hand-crafted examples, by simply adding "Let's think step by step" to the prompt, LLMs are able perform step-by-step reasoning toward accurate answers. These insights have spurred a series of subsequent studies. Auto-CoT Zhang et al. (2022) eliminates manual efforts by retrieving usable reasoning chains generated by zero-shot CoT. Active-Prompt Diao et al. (2023) first measures the uncertainty of a set of questions and thus selects only the uncertain ones to be annotated by humans. ToT Yao et al. (2024) can also reduce manual efforts, but for each task, it still requires experts to provide possible next-step thoughts in the prompt. Our paper introduces novel boosting approach for manual-free prompting. Starting with a simple prompt, BoT iteratively enhances it based on the analysis of LLMs on thoughts.
Prompt Engineering via Feedback. Utilizing responses from LLMs to the input prompt as feedback for further prompt revisions has garnered much attention. Those who continuously revise the given prompt based on evaluation descriptions from LLMs aim to gain an accurate answer Weng al.) (2023). Using similar higher-level idea of our paper, SELF-REFING Madaan et al. (2023) proposes an iterative self-refinement algorithm to let the I.I.M produce feedback for its output for further refinement. PHP /Zhng et al. (203)) simplifies this process by directly adding solution from the previous answer as a hint to the subsequent prompt. REFINER Paul et al. (2023) is also related to our paper it evaluates each reasoning step feedback to produce a more reasonable one. Another line of research explores ensembles, particularly leveraging the boosting mechanism Freund et al. (1996) to refine the prompt using feedback from a set of examples. They adjust the prompt focus on the unsolved problems in the previous iteration by either adding a few shot examples uncertain in the previous Pitis et al. (003)) or relying on a beedbaack-eflect-refffe
process Zhang al. (2023a). APO Pryzant et al. (2023) iteratively refines prompt, using the performance of the prior prompt to form a natural language for optimization. These works prove the effectiveness of the boosting mechanism in prompt engineering. However, our work is the first to highlight the importance of error analysis in enhancing the prompt toward generating effective reasoning chains. The proposed BoT extends this insight to implement an automated prompting framework by iteratively accumulating an ensemble of trial-and-error reasoning experiences in the prompt.
3 BOOSTING OF THOUGHTS
3.1 BACKGROUND
The objective of prompt engineering is to design a prompt I containing multiple language sequences, such that with this prompt as input, a pre-trained large language model (LLM) denoted as pa parameterized by 0, can obtain the desired language sequence y. Thus, the standard Input-Output (IO) can be formulated as y ~ [y[T (X, Q)) in which I (-) means that the prompt wraps task instructions X and the corresponding question Q.
The prompt can be designed in more delicate way to guide the LLM toward solving a problem in step-by-step manner. Each intermediate reasoning step is denoted as z, (a.k.a thought). CoT Wei et al.) (2022 provides few-shot examples with the answer of each example containing chain of thoughr where N is the number of examples included in Z This leads to y ~ pe (v/ll [Ia...n)** , X, Q)) the prompt.
3

---

Published as a conference paper at ICLR 2024
Stage
Thought Chain Analysis Feedback
Reasoning stpp: 1
apecation
multipiicahin, number setis:
these stops: Stop obtalned bring closer the torget of Step 2 Step are not correct becruse there are more nombers the new set in Step 3, ootained new number set is 36 and 5, which does not us cleser to the target of 24. My achice for the (Slep to Addition or Multiilicatonn (Stop 2/ should contain numbers My advice for the (Step 3l is to other anthmetiic opecations for two numbers
conctusion is possibie should reviso some stoes Reasons
the noo numbers ae: 3 and 4, the anthmetic opecation mutisicarion, and the new number set 3, Fand 12
own number 4, which
17
LM
5 anthmeeeiii opecation
suttrctioon number and
2
Thought Anggrtures.gggraaatton
Simple Prompt
Descriptions
Information Question
Stago
Experience: p
V/ 0.
Stage
*Z...
Foodback (error analysi, advicc,
Next Thought Goneration
Reasoring Plachhldde: [C.
Heterogeneous Tree Structures
Impur for root nodes
Figure 2: The overview of the pipeline in each iteration of BoT. To show how boosting is achieved in this experience-driven iteration process, we present detailed intermediate results obtained from an experiment on ChapGPT-4 on the Game of 24 dataset. Given Q : "The given four numbers arc: 2, 4, 5, 5", BoT performs three stages sequentially. With the simple prompt I' as input, The Thought Structures Generation (Stage 1) outputs massive heterogeneous tree thought structures. Thought Structures Aggregation (Stage 2) aggregated them into thought chain Σi...n, which is analyzed in Stage to produce experience further enhance the prompt.
Instead of pre-preeppe pre-preparing examples in the prompt, more adaptive way is to design prompts to guide the LLMs to gradually generate the thought 2; during the reasoning process. This can be formalized 23 po (z;[T (=1...-11 X, Q)). Finally, the solution is formalized y ~ po (=1..n X, Q)) The representative approach, ToT Yao et al. (2024). further extends this sequential reasoning steps into a tree structure in which C next-step thoughts be generated. Thus, the thought structure can be chain or tree.
3.2 FRAMEWORK
Existing literature that aims to generate the prompt with correct CoT examples or design delicate thought generation structures has three limitations. First, ineffective thoughts in those approaches generally ignored or discarded. However, a human, who is not an expert in one field, particularly relies on analyzing previous errors to collect more experience perform correctly on the next try. Second, they are less scalable because, for each task, an example of generating the next thoughts, such (=1 z0. X, Q), should be provided in the prompt. Finally, the thought structure, such the tree Yao et al. 22024). is generated to be overly complex to explore more reasoning steps for better solution. This is largely due the obtained solution may not be further revised.
In this paper, we argue that the prompt can be enhanced by continuously collecting the analysis of LLMs on those ineffective thoughts wrong reasoning steps in chain of thought. Therefore, even simple prompt, such as I [X, Q), potentially leading to ineffective thoughts, can be progressively refined by relying on such analysis to gain powerful thoughts toward the solution.
We propose Boosting of Thoughts (BoT), an automated prompting framework incorporating, which achieves prompt boosting with an experience-driven iteration process commencing with a simple prompt. As summarized in Fig. 2 each iteration of BoT includes three stages. The Thought Structures Generation stage is able to fully explore reasoning chains generated by LLMs with the input prompt ll'. In the second stage, these thought structures chain, which to be analyzed by LLMs in the third stage to produce feedback containing error reports and detailed revision advice. Combining the aggregated reasoning chain with the feedback results in a new experience, denoted as F*. Thus, the prompt is enhanced by accumulating these experiences Fl... over iterations.
aggregated to form a reasoning
4

---

Published as a conference paper at ICLR 2024
Simple Prompt. For any task, in iteration t 0, we create simple initial prompt I (S, Q. {G:)). where S represents task-agnostic descriptions while the terms and Q respectively denote the task information and the question. The experience part of the prompt is denoted as FO, which should be empty at the beginning. {Gi} is placeholder that is waiting to be filled during building thought structures. In other words, when generating the next thought 2,, {G.}
will be substituted with the preceding chain of thoughts 21.,,i-1-
Thought Structures Generation. After collecting experience F* the prompt in the iteration t can be I' (S, X, F".. (G,)). Based this prompt, BoT generates M thought structures in parallel. BoT is inherently capable of embracing any thought structure, such as the chain [Wei] al. (2022) tree Yao al. (2024) structure. Considering the exploration of reasoning steps and experimental results, we investigate the tree thought structure. However, BoT introduces two novel modifications to make it better suited for the boosting framework.
Weighted Binary Tree. With a simple prompt in each round, BoT builds the weak thoughts structured in low complexity as they can be further revised in the boosting mechanism. Thus, each thought structure of BoT is a shallow weighted binary tree. For simplicity, we retain the notation 2 represent the thoughts from the root to the parent of node i. In addition to providing each node i with one thought 2; and its thought evaluation score Vi ~ Po (21...i, Il,, X: Q), we incorporate the edge score V ~ po (2:-1, 2,, Ie. X, Q) between a child node and its parent node, where 1e and L. refer to the instructional descriptions for thought and edge evaluations. V1-1, represents the LLMs' confidence level generating this reasoning step. Thus, the next thought generation of BoT in this tree structure is formalized as pe (2s] (V--1, V,, (,,1,,,))) ()).
Tree Heterogeneity. Unlike ToT Yao et al. (2024). which seeks to search for a solution in one large and complex tree, BoT aims to build highly heterogeneous tree thought structures. As result, complete reasoning chains with various logical in trees of BoT are subsequently assessed as experience. Therefore, to increase heterogeneity, thought structure generation embraces different tree growth strategies, such level-wise growth and leaf-wiss wise growth. The former emphasizes exploration but less exploitation Chen & Guestrin (2016), while the latter does the opposite Ke et al. (017). Thus, the leaf-wise strategy tends to continue reasoning from the current best thought to reach a better final thought as compared to level-wise growth, but also tends to get monotonous reasoning chains. Besides, different temperature and Top-p settings of LLMs are applied. Finally, we use a small max_depth value in BoT and label node as a leaf when its V1-1, and Vú values are outside the specified range [0.3, 0.8).
Thought Structures Aggregation. Upon obtaining M thought structures. BoT aggregates them into one thought chain denoted as 2 To achieve this, for each thought structure with index m. BoT first selects the chain with the highest evaluation score as 2 Rmm = arg max = E V + V,-1,; where 7. denotes the set of all thought chains of m-th tree. Subsequently, two strategies exist to obtain 1
Best-First Aggregation. BoT relies on arg max ...... (Zz mm E Vi+VV, V2-1, 1.a to choose the best one 2 from M thought structures. This algorithm is fast but may lead to an unreasonable chain that is hard to guide the following refinement.
Greedy Aggregation. BoT is allowed to perform a greedy search on (Z.) J==1 { to assemble new thought chain that may not exist and is globally optimal. Starting from the initial thought, generally the root node of the tree, BoT obtains _ = arg max { m=1
V,
Vj Vj- Subsequently, to obtain ž, for -;-1, BoT searches all thoughts where the previous step is 2 in ( 1d Ad Jm=1-
Thought Chain Analysis. To gain insights into what should be adjusted to enhance the prompt to generate better thoughts, BoT utilizes the self-evaluation ability Weng al. (2023) of LLMs assess Zi.... Specifically, with the prompt 1,, (Z X, Q) as input, LLM outputs a feedback paragraph containing issues report of this thought chain _ and detailed advice This feedback will be added to FL...... F-....!-1 as new experience in thought generation, resulting Fl.....!
5

---

Published as a conference paper at ICLR 2024
Iterative Refinement. Through boosting mechanism, F!....t is employed to iteratively enhance the prompt, resulting in [++1 (S, Q, (,,
{G+t) for the (t + 1)-th iteration. As the iterations progress, Fl.... may encompass many typical, unreasonable thought chains alongside those closer to solution, all with well-defined analysis outcomes. Therefore, even when starting with simple prompt, BoT iteratively refines this prompt to produce the correct reasoning steps leading to the accurate solution. After 7' iterations, utilize the I[ as input prompt for the LLM to gain the final answer.
EXPERIMENTS
Datasets. Experiments are performed on benchmark datasets with diverse mathematical problems,
including MMLU U Hendrycks al. (2021a), SVAMP Patel et al. (2021), GSMBK Cobbe et al. (202T). AQuA Ling et al. (2117) and MATH Hendrycks et al. (2021b). Besides, we include a challenging
mathematical reasoning task, Game of 24 Yao et al. (2024), where the goal is use four numbers
and basic arithmetic operations (addition, subtraction, multppiccation, and division) to obtain 24 in 1
equation. Thus, the solution includes intermediate steps.
Competitors. Apart from the benchmark approach, standard Input-output (IO), the comparison
approaches include Chain-of-thought (CoT) Wei et al. (2022). CoT-SC Wang et al. (2022) and
Complex CoT Fu et al. (2022). in which the input prompt contains few-shot examples (8) with human annotations. Also, BoT is also compared with related works, such as Tree of thoughts (ToT)
Yao et al. (2024) with the breadth limit 5, Progressive-Hine Prompting (PHP) Zheng et al. (2023) and the sfate-of-the-ard CSV Zhou et al. (2023a).
Large I Language Models. We conduct experiments on the two most recent models: GPT-4/OpenA. (2023) and Llama2 Touvron et al. (2023). GPT-4 is accessed via OpenAI APIs, while the llama- 2-13b-chat model is downloaded from MetaAl to perform experiments locally. To construct the heterogeneous tree thought structures, BoT randomly chooses the temperature from the range of [0.2, 0.6, 0.7, 0.9, 1.1, 1.5] and the top-p from the range of [0.1, 0.3, 0.5, 0.7, 0.9].
Settings. If not explicitly stated, BoT, in all experiments, performs = 10 iterations of rumning and builds M = 15 thought structures, each being weighted binary tree because this tends to achieve optimal results. Besides, for those benchmark datasets, we set the depth of the tree to be 5 while the corresponding depth in Game of 24 is 3. BoT+CoT means simple prompt includes 5 examples from CoT Wei et al. (2022). In the ablation study, when no experience is accumulated in BoT, 8 examples of CoT will be provided in the prompt.
Metrics. All experiments report the Solve Rate (%) of the task as the evaluation results. To extract
target answers from the output o of BoT, we specifically set the formatted description of the answer for LLMs. For commonly used datasets, the desired answer format is "The answer "" For the Game of 24, we utilize "Step idx, Current set: Selected two numbers: Operation: Computed new number: Remaining numbers: New set: ". Thus, we directly compare the ground truth with the number presented in the new set. Following ToT Yao Yao et (2024), we report the Solving Rate across 100 hard games as the metric.
4.1 MAIN RESULTS
The primary experimental results are summarized in Table. Sable.[anc and Fig. 3 where we present insights into the overall performance of BOT. Our findings indicate that the proposed BoT with Boosting mechanism 1). obtains competitive problem-sole -ooevinn rates in most datasets without human annotations; 2). is capable of reaching a new ofate-of-the--eee on GSMBK and AQuA when provided with CoT examples. However, experimental results also demonstrate that BoT heavily relies on experience, thus is sensitive to the ability of L.LMs.
Specifically, in Table. [ BoT, starting from simple initial prompt and performing basic chatting. eventually obtains a GSM8K solve rate 0.1% higher than the current state-of-the-art (SOTA) CSV Zhou et al. (2023a), which heavily relies code interpreter of GPT-4. Considering AQuA, BoT is 2.5% higher than SOTA. This demonstrates that by adding error analysis and advice to the prompt without human annotations, LLMs able to perform well on complex reasoning. The main reason is that a simple prompt can be iteratively refined by accumulating prior experience towards accurate problem-solving. After including CoT examples in the prompt, BoT+CCT outperforms SOTA by

---

Published as a conference paper at ICLR 2024
Table I: Utilizing BoT with GPT-4, without human annotations, yields notable performance enhancement. the simple initial prompt BoT contains CoT examples, corresponding approach BoT+CoT exhibits even higher solving rates. Our framework is also evaluated against leading methods such as Model Selection Zhao et al. (2023), PHP[Zheng ct al. (203)), and CSV Zhou et (202aa), cach achieving state-of-the-ard (SOTA) performance the SVAMP, AQuA, and GSM8K & MATH datasets, respectively.
No need
Datasets
Methods
Average
Human Annotation
SVAMP
GSMBK
AQuA
MATH
SOTA Standard
93.7
97
79.9
84.3
88.7
68.7
87.1
40.6
42.5
59.7
77.6
92
74.0
48.93
73.1
Zero-shot CoT
74.3
89.6
73.2
47.7
Complex-CoT
90.5
94.9
77.5
50.4
78.3
РHP Complex-CoT
91.9
95.5
79.9
53.9
80.3
BoT BoT CoT
92.7 ( I)
97.1 0.1)
81.4 (1 2.5)
62.5 () 21.8)
83.7 (L 7.6)
94.9 (1 1.2)
98.7 ( 1.7)
84.9 5)
66.3 (4 18)
86.2 2.5)
Salving Rates
off bet.5 moe
Number Trees
Number
Number Trees
Selving
23-
Number of Trees
Number Trees
Number Trees
(a) GSM8K.
(b) MATH.
MMLU.
Figure 3: Evaluating solve rates by applying BoT and BoT+CoT in GPT-40penAA) (0233 and Llama2 Touvron
et al. 2023)
1.3% average in GSM8X and AQuA datasets. We argue that the CoT examples can be regarded as the success cases in the experience, directly guiding the subsequent thought structures generation of BoT. Thus, cooperating with the iteration refinement, BoT+CoT reaches new SOTA. It also deserves to show that because BoT can gradually collect analysis of various reasoning chains (bad or good) as experience, it is consistently close to the BoT+CoT. However, BoT and BoT+CoT, especially BoT, are at least 18% lower than SOTA in MATH. This observation means weak LLMs may not perform well with BoT due their lower ability to analyze reasoning chains for an effective experience, as supported by Fig.
Fig. presents that with BoT, GPT-4 and Llama2 are respectively improved by 11.6% and 4.4% on average in three datasets. The two numbers show a clear trend that when the LLM is weaker, BoT's performance drops significantly. With powerful GPT-4, as presented in Fig. 3 BoT and BoT-CoT behave similarly to those shown in Table. Additionally, their performance escalates along similar trend as the number of trees varies from to 20. As Llama2 weaker, BoT unable to benefit from its analysis to perform the experience-driven iteration process, which is particularly shown by Fig. (a). When provided with valid success cases, i.c., 5-shots, BoT, through progressive refinement, can still help Llama2 to solve more problems than the baseline even though the improvement is limited.
7

---

Published as a conference paper at ICLR 2024
4.2
GAME OF 24
Method
Solving
Standard
7.3
Standard (bost
33
Salving Rate
CoT prompt
4
CoT prompi (best of 100)
49
Solving
CoT-SC (2-100)
9
ToT
74
BoT
83.7
BoT+CoT
84,9
Number Trees
Number of Iterations
Table 2:
Results on Game of
24 where the settings of different
Figure 4: Comparison of three approaches across varying numbers approaches follow those ToT Yao trees and iterations.
et al. 2024).
Table 3: Showing aggregated thought chains and ohtained experiences in iterations 1, 5, and 8. The given four numbers are: 2, 7, 8,
Two numbers
Arithmetic operation
New number
Experience
Judgement
iteration
The new set does not bring us closer to the target of 24.
2, 8
multiplication
16, 7,
Try other numbers and operations. his step does not follow the rules of combining the remaining numbers and the obtained new number into a new set. Adjust the new set. many numbers the set. More steps required reach the target of 24.
9,7
addition
7, 16, 16
Possible but more subsequent steps are required
F
multiplication
112
The "Evaluation Score: 0,5" is low. Increase the score.
9.7
addition
16, 8
It is not possible to further manipulate numbers reach 24.
16, 8
addition
2, 24
Possible but should revise some steps Can choose other two numhers.
Choose different numbers.
The new set is not correct.
2, 24
subtraction
22
9,7 7
addition
16, 1,, 2, 8
16, 2
multiplication
32,
Possible
32, 8
subtraction
24
Due to the hardness of the Game of 24 problem, GPT-4 and Llamaa both perform badly this task, even incorporating the CoT, and CoT-SC approaches. The Llama2 model even fails to follow the correct rules of addressing the problem, making the solve rate applying BoT, which relies on the experience, to Llama2, all results are lower than 5% without significant improvement. Thus, we only report the performance of BoT with GPT-4. To maintain fair comparison, we follow the settings proposed by ToT Yao et al. (0044).
lower. Especially when
As shown in Table 2, BoT without human annotations is 9.7% higher than ToT, which relies on one example showing all possible next steps. Besides, BoT+CoT, which contains CoT shots in the initial prompt, is 1.2% higher than BoT. Such close performance between BoT and BoT+CoT is attributed to the boosting mechanism, which progressively revises weak thoughts, as discussed in subsection 4.1 Adopting an experience-driven iterative process, BoT exhibits enhanced performance as the number of trees M and the number of iterations T increment. Also shown by Fig. 4 compared to BoT+CoT, BoT relies more on and T as it requires to collect experience from a better thought chain or longer iterations. Another observation is that when enabling ToT to operate iteratively with the prompt enriched by experience, the problem-soo solving rate escalates from 72.5% in the initial iteration to 80.2% by the 10-th iteration. This demonstrates that experience the analysis of previous reasoning chains can be used by LLMs to significantly improve the solve rate. However, the score obtained by ToT is still 3.5% lower than BoT. This is attributed the fact that the aggregation stage
8

---

Published as a conference paper at ICLR 2024
of BoT will produce the most representative reasoning chain in the current iteration, thus leading to more meaningful experience to enhance the prompt. We verify this in the ablation study section.
To better present how BoT learns from emror and previous advice, we show in Table 3 that GPT-4 able to avoid previous errors and produce more specific advice with the increase of iteration and eventually obtain the correct solution. In the first iteration, with the simple prompt, L.Mss even make a mistake in following the task rules as the new set is wrong in step 3. After analyzing, it presents correct advice on this mistake. However, the analysis at the initial iteration is vague, such as "try other numbers and operations". After five iterations, BoT aggregates multiple such analyses, deriving more potent prompt, making the LLMs select the right numbers and 7. Also, the advice is more concrete and useful. The advice for this right selection is to increase the corresponding evaluation score. Through the continuous accumulation such experiences, BoT progressively refines the prompt, culminating in the direct generation of correct solution in the 8-th iteration.
4.3
ABLATION STUDY
Table 4: Comparison of BoT variations applied GPT-4 on the Game of 24 and AQuA Datasets.
Experience pi...
Accumulation Type
AguA
Issues
Advice
Replace
Add
BoT (Best fisst)
BoT (Greedy)
BoT (No)
BoT (Best first)
BeT (Greody)
BoT (No)
/
81.2
83.7
67.1
81.4
56.2
74.7
78.2
70
47.3
56.8
44.9
72.8
74.1
70.2
52.4
62.7
46.3
69.2
70.7
67.6
54.1
40.3
74.9
76.9
72.7
68.3
74.2
71.9
77.9
80
72.4
73.6
77
64.1
Experience consistently leads to thought revision, but too much can have the opposite effect. When the prompt accumulates issues and advice by the "adding" type, both aggregation strategies can lead to high solve rates. Maintaining a complete experience is important for revising thoughts, especially for the AQuA dataset, which includes wider mathematical reasoning problems. However, BoT (No), which does not perform aggregation but directly uses all reasoning chains from generated trees, suffers the worst performance all cases, especially when the experience accumulation type is "adding". As BoT builds 15 trees each iteration, putting them all together into a prompt may cover core information, not to mention that most such experiences are invalid or harmful.
Advice is more important to generate thoughts than others. In all cases of Table BoT variations that embrace advice as experience achieve the top solve rate. For example, with the same "adding" type, when the experience does not contain advice, the performance drops by more than 10% and 20% in Game of 24 and AQUA, respectively. On the contrary, including issues in the experience serves auxiliary mechanism for performance improvement. Only by cooperating issues the BoT with advice gain the best solve rate; for example, the number grows by 4.4% for BoT (Greedy) in AQuA.
Greedy aggregation can be the only required choice for performance purposes. As compared the Best-first that selects one from existing thought chains and no aggregation that maintains all thought chains, greedy aggregation adaptively merges tree structures into one better thought chain that may exist in the current iteration. By doing so, LLM is able perform more meaningful analysis on a stronger thought chain, thus producing important experiences to enhance the prompt. As shown in Table once the Greedy aggregation is used, BoT improves by more than 2% in all cases. In AQUA, containing more math problems, this number is even 10%. Besides, as our discussion in Fig. 4 ToT with a similar experience-driven boosting mechanism reaches 80% but still lags behind the BOT. This may be attributed to the inability to execute the greedy aggregation within its singular tree structure.
5 CONCLUSION
This paper verified that a simple prompt can be enhanced by gradually accumulating analysis on its generated thoughts to address complex tasks. We have proposed a novel framework, the Boosting of Thoughts (BoTT), implement such progressive prompt enhancement for effective thought generation

---

Published as a conference paper at ICLR 2024
with experience-driven iteration process. Iteratively exploring and self-evaluating the generated simplistic trees of thoughts enables a simple initial prompt to be gradually enhanced by an ensemble of trial-and-erron reasoning experiences, resulting in accurate solutions. Our extensive experiments demonstrated that Bo'I' capable of achieving state-of-the-al on multiple benchmark datasets while outperforming the alternative leading approach in Game of 24, which is challenging mathematical reasoning task.
REFERENCES
Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Michal Podstawski, Hubert Niewiadomski, Piotr Nyczyk, et al. Graph of thoughts: Solving elaborate problems with large language models. arXiv preprint arXiv:2308. 09687, 2023.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et Language models are few-shot learners. Advances in neural information processing systems, 33:1877- 2020.
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proc. the 22nd acm sigkdd international conference on knowledge discovery and data mining, pp. 785-794, 2016.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, al. Training verifiers solve math word problems. arXiv preprint arXiv:2110.1416 2021.
Shizhe Diao, Pengcheng Wang, Yong Lin, and Tong Zhang. Active prompting with chain-of-thouge for large language models. arXiv preprint arXiv:2302. 12246, 2023.
Yoav Freund, Robert E Schapire, et al. Experiments with new boosting algorithm. In icml, volume 96, pp. 148-156. Citeseer, 1996.
Yao Fu, Hao Peng, Ashish Sabharwal, Peter Clark, and Tushar Khot. Complexity-bure -bssed prompting for multi-step reasoning. Proc. The Eleventh International Conference on Learning Representations, 2022.
Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. Proceedings of the International Conference Learning Representations (ICLR), 2021a.
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. arXiv preprint (txXi:22103.38874,, 2021b.
Bairu Hou, Joe O' connor, Jacob Andreas, Shiyu Chang, and Yang Zhang. Promptboosting: Black-box text classification with ten forward passes. In International Conference on Machine Learning, pp. 13309-13324. PMLR, 2023.
Guolin Ke, Qi Meng. Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie- Yan Liu. Lightghm: highly efficient gradient boosting decision tree. Advances in neural information processing systems, 30, 2017.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35: 22199-22213. 2022.
Aitor Lewkowycz, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Soll al. Solving quantitative reasoning problems with language models. arXiv preprint arXiv:2206.1488 2022.
Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom. Program induction by rationale generation: Learning to solve and explain algebraic word problems. arXiv preprint 1r05v:/705.04111 2017.
10

---

Published as a conference paper at ICLR 2024
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with self-feedback. arXiv preprint 2:X1::230331655122222
OpenAl. Gpt-4 technical report. arXiv preprint 2rXin:2303.08774, 2023.
Arkil Patel, Satwik Bhattamishra, and Navin Goyal. Are nlp models really able to solve simple math word problems? arXiv preprint arXiv:2103.0719/, 2021.
Debjit Paul, Mete Ismayilzada, Maxime Peyrard, Beatriz Borges, Antoine Bosselut, Robert West, and Boi Faltings. Refiner: Reasoning feedback on intermediate representations. arXiv preprint arXiv:2304.01904 2023.
Silviu Pitis, Michael R Zhang, Andrew Wang, and Jimmy Ba. Boosted prompt ensembles for large language models. arXiv preprint urXiv:2344.05970. 2023.
Reid Pryzant, Dan Iter, Jerry Li, Yin Tat Lee, Chenguang Zhu, and Michael Zeng. Automatic prompt optimization with "gradient descent" and beam search. arXiv preprint arXiv:2305.03499 2023.
Taylor Shin, Yasaman Razeghi, Robert L Logan IV, Eric Wallace, and Sameer Singh. Autoprompt: Eliciting knowledge from language models with automatically generated prompts. In Proc. Conference on Empirical Methods in Natural Language Processing, pp. 4222-4235, 2020.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09228. 2023.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le. Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain thought reasoning language models. In Proc. International Conference on Learning Representations, 2022.
Jason Wei, Xuezhi Wang. Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 01224244-44835 2022.
Yixuan Weng, Minjun Zhu, Fei Xia, Bin Li, Shizhu He, Shengping Liu, Bin Sun, Kang Liu, and Jun Zhao. Large language models are better reasoners with self-verification. In Proc. Conference on Empirical Methods in Natural Language Processing, pp. 2550-2575, 2023.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Proc. Advances in Neural Information Processing Systems, volume 36, 2024.
Chenrui Zhang, Lin Liu, Jinpeng Wang, Chuyuan Wang, Xiao Sun, Hongyu Wang, and Mingchen Cai. Prefer: Prompt ensemble learning via foedback-reffect-refine arXiv preprint arXiv:2308. 12033, 2023a.
Yifan Zhang, Jingqin Yang, Yang Yuan, and Andrew Chi-Chih Yao. Cumulative reasoning with large language models. arXiv preprint arXiv:2308.04:: 04377, 2023b..
Zhuosheng Zhang, Aston Zhang, Mu Li, and Alex Smola. Automatic chain of thought prompting in large language models. In Proc. International Conference Learning Representations, 2022.
Xu Zhao, Yuxi Xie, Kenji Kawaguchi, Junxian He, and Qizhe Xie. Automatic model selection with large language models for reasoning. arXiv preprint arXiv:2305.. 14333, 2023.
Chuanyang Zheng, Zhengying Liu, Enze Xie, Zhenguo Li, and Yu Li. Progressive-hint prompting improves reasoning in large language models. arXiv preprint urXiv:2304.09797. 2023.
Aojun Zhou, Ke Wang, Zimu Lu, Weikang Shi. Sichun Luo, Zipeng Qin, Shaoqing Lu, Anya Jia. Linqi Song, Mingjie Zhan, et al. Solving challenging math word problems using gpt-4 code interpreter with code-based self-verification. arXiv preprint arXiv:2308. 07921, 2023a.
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc Le, et al. seast-to-man prompting enables complex reasoning in large language models. In Proc. International Conference Learning Representations, 2023b.

---

Published as a conference paper at ICLR 2024
A
BASIC PROMPTS AND REASONING PIPELINE OF BOT
A.1 THOUGHT GENERATION PART OF BoT
This subsection presents the basic prompts used by the reasoning generation the proposed Boosting of Thoughts (BoT). For details, one can also access the source code hammplleeBBoosinggoooouuuuuuuu reasonerpy.
System prompt S:
expert mathematical problems. Perform step-by-step reasoning toward problem solving by first learning from an ensemble trial-and and-error reasoning experiences. Such aaal-ond-error reasoning experience specifically contains error reports and detailed advice how to revise historical reasoning steps. Always recall these listed experiences before generating a reasoning step, thereby avoiding making the same mistakes and reusing correct steps generate better reasoning steps to solve the task.
You
Prompt for the next thought generation:
f"
(task prompt). \n First of all Recall historical reasoning experience: \n'n experiences } 'n'n Please make one step of reasoning to generate only one next possible reasoning step. This next reasoning step is the subsequential step from the following ordered previous steps, accompanied by their evaluated scores (A higher score means the reasoning step is more likely to complete the task :): \n)tf chain prompt] (n Based on listed previous reasoning steps (ignore them when the above space empty), generate one single next possible step following the Task rule. (Emphasize: Please generate only one single next possible reasoning step of the given steps.) .
where the task. -orompt contaings the X and Q for the task, experiences is the historical reasoning experience Fl...t, and chain.prompt is the {G:}, which is placeholder to be replaced by the preceding chain of thoughts 2 of the current thought 2,
Prompt for the thought evaluation:
f""
prompppr | Below are the generated reasoning steps, presented order, accompanied by their evaluated scores (A higher score means the reasoning step is more likely to complete the task .) ()::nncchiinnpp >::p/chhiin_poompt) n (tthought) n' is your evaluation score for the logic, correctness. and benefit to reaching final solution for these reasoning steps? Please select one value from [0.1, 0.3, 0.5, 0.7, 0.9, 1.0] as the score, where higher score means better reasoning steps The score should be placed after EEvaluation score: for users to read. "..7
where the thought is the current thought 2;-
A.2 EXPERIENCE GENERATION PART OF BOT
To generate feedback for the aggregated chain, LLMs use the following basic prompts.Fo details, one can also access the source code scamples/oosxiingg//oouuuuuuhh h
System prompt S: You are an expert Al checker for math answers, dedicated evaluating the reasoning chain generated towards addressing the mathematical problem. Judge each reasoning step of this reasoning chain by providing detailed analyses on whether the current step a logical inference of the previous step and whether the reasoning step is beneficial to the correct solution. Provide advice and suggestions for each reasoning step with errors. Provide recommendation or rejection descriptions for each correct reasoning step.
Prompt for the feedback:
GnnGGivn task: (ik::(tas) task maaskpprompt.....
n))n Please evaluate this reasoning chain by giving detailed comments containing the following content. 1.{
chain feedback format J. 2.{ step feedback format ). 3.{ confidence feedback format }- n in Notice: (Notice}.
12

---

Published as a conference paper at ICLR 2024
where the chain.prompt is the aggregated thought chain 1......
chain feedback format: Can this reasoning chain complete the task and reach the target correctly by executing its reasoning steps? why? Write a analysis report with conclusion under 'Anlysis Report:".
For each reasoning step, please provide a detailed analysis of whether the current step is logical inference of the previous step and whether the reasoning step is beneficial to the correct solution. For each reasoning step with errors, please provide an error report and the corresponding advice revision. For each reasoning step, please provide recommendation or rejection descriptions. Comments should be brief and follow the format: Reasoning step (idr). Analysis report: Advice: Recommendation Reject description:
step feedback format:
What is your confidence score on these your evaluations and comments? Please select one value from [0.1, 0.3, 0.5, 0.7, 0.9, 1.0]. The score should be placed after "Confidence score:" for users to read."
confidence feedback format:
With the feedback prompt, LLMs generate reasoning experience F' containing conclusion and analysis on the reasoning chain and each reasoning step.
A.3 REASONING PIPELINE
To facilitate the understanding of the proposed Boosting Thoughts, we summarize the reasoning pipeline in Algorithm Table [1] The source code for this pipeline can be found in the file core.py.
Scample/BoosiinggfTouuuug core.p.
Algorithm 1:
Main reasoning pipeline of BoT
Input: Number of iterations T', Number of tree structures M, Question Q.
Output: Aggregated chain zf....-
Initialize simple prompt 1 (, Q0 F ( where F will be an empty string. for each iteration 1, 2, ..., do
Use LLMs with the prompt --~1 (S. (G.)) to create AM heterogeneous tree thought structures through Thought Structure Generation.
Extract thought chains { m=1 from the M thought structures where each = the best thought chain of m-tt tree structure.
Aggregate { m= into a single thought chain of.... by using either Best-First
M
Aggregation or Greedy aggregation.
Perform Thought Chain Analysis on zi... with LLMS to obtain the feedback, which is combined with z to obtain experience F
Update the prompt by accumulating Ft, leading to (8, Q, Ft-14, F. (G.)).
end
Obtain the solution =
B INSIGHTS FOR BOOSTING OF THOUGHTS
Boosting of Thoughts derives from our insights that the reasoning ability of large language models (LLMs) for addressing mathematical problems comes directly from experience, which contains the accumulation of the analysis and advice on previous mistakes. Once the prompt embraces valid historical reasoning experience to be recalled by LLMs before performing reasoning, the produced reasoning steps are generally more logical and reasonable. as shown in the comparison between Table and 6 Such insights also made us consider that L.MMs do not need rely heavily on well-prepared prompt with human annotations (a few chains of thought demonstrations as exemplars in prompts) for each task. Yet, as LLMs are able to learn from experience, we can start from simple prompt without examples or manually designed content to gradually collect experience during the reasoning process. Eventually, by accumulating experiences in the prompt, LLMs achieve strong reasoning toward addressing complex problems. With these insights, the Boosting of Thoughts is designed as an automated prompting framework, which iteratively collects an ensemble of trial-and- error reasoning experiences for problem-solving with L.MMs. We argue that the proposed BoT is not
13

---

Published as a conference paper at ICLR 2024
an application of LLMs to specific tasks but rather builds upon the insights that LLMs' reasoning ability can be derived directly from the experience gained by analyzing incorrect reasoning chains, without relying human priors.
To emphasize our insights, we share three key observations derived from applying gpt-3.5-turbo with temperature of 0.7 and top.p p value of 0.7 on the Game of 2 4 dataset below.
The prompt with experience encourages LLMs to explore more logic in the responses. As shown in Table [5] when no experience is included in the prompt, the model generates the same reasoning step five times. This observation shows one of the common problems of LLMs, which is the lack of self-motivation explore different reasoning logics. Thus, despite their strong potential for reasoning, LLMs may become trapped in a cycle of beginning with the simplest reasoning step, which may never culminate in finding the final solution. The 'Obtained reasoning chain' part of the wrong reasoning chain. We believe that as Tree of Thoughts Yao et al. (2024) generates multiple responses as thoughts to build the nodes of the Tree, such a duplicated reasoning step may lead to the failure of this algorithm in some cases. However, in the second iteration of BoT, the introduction of experience into the prompt leads to the generation of distinct initial reasoning steps, as illustrated in Table 6 The final reasoning chain can ultimately arrive at the correct solution by commencing with a wider range of potential logic. Weng et al. (2023)
LLMs avoid making similar mistakes emphasized by the experience of the prompt. Without including experience, which contains the error analysis, in the prompt, LLMs will make many mistakes, such deviations from the task's rules and regressing to the initial reasoning step in the final process, as shown by Table5]s 'Obtained reasoning chain' part. After analyzing this reasoning chain and incorporating the feedback
the experience into the prompt for the second iteration of BoT, it becomes evident from Table [ that LLMs will fully learn from the experience before engaging in reasoning. First, none of the responses replicate the same erroneous reasoning step. as illustrated by the diverse initial reasoning steps in the "Five responses from the gpt-3.5-turbo Second, LLMs successfully circumvent all previously identified mistakes by rigorously adhering to task rules, eliminating incorrect reasoning, and executing logical reasoning steps. Third, it eventually leads to the correct solution for the I 4 6' Game of 24 task. Other work, such as Weng et al.) (2023); MMdaan Maddann et al. p; Zheng al. (2023). also highlighted the importance of enhancing the prompt with the feedback, which is self-evaluation of previous answers. Nevertheless, BoT is the pioneering work founded the insight that embracing error analysis for learning empowers LLMs to attain formidable reasoning capabilities.
Without human annotations, LLMs automatically organize effective reasoning chain toward solving complex problems based on experience containing error analysis. BoT is the pioneering initiative that proposes automated prompting framework, leveraging the insight that LLMs can acquire effective reasoning skills for problem-solving solely through error analysis and guidance, all without the need for human annotations. As shown in Table which shows the first iteration of BoT, the initial prompt only contains the basic task guidance and the question without any in-context learning examples like what in COT. Even though the reasoning chain obtained by LLMs with such a prompt contains numerous eтrогs and invalid reasoning steps. its error analysis and advice can be included as the experience in the input prompt to benefit the reasoning for the second iteration, as shown in Table 6.. It can be observed that with no prior human guidance on correct reasoning procedures, LLMs can acquire knowledge from experience that includes error analysis and guidance from previously generated reasoning chains, leading to a progressive improvement in reasoning for problem-solving.
Therefore, our BoT provides long-term guidance for research it demonstrates the importance of recalling error analysis and advice when enabling LLMs to generate effective reasoning processes for complex tasks. With these insights, the research of prompt engineering on inducing the reasoning ability of LLLMs can focus on how to generate experience instead of introducing more human priors.
C THOUGHT STRUCTURES GENERATION
BoT is automated prompting framework that iteratively accumulates the experience derived from the analysis of reasoning chains. Consequently, BoT is generalized to various thought generation methods and L.MSs capable of generating and evaluating reasoning steps. And the performance of
14

---

Published as a conference paper at ICLR 2024
BoT depends on the effectiveness of its thought generation structure. Thus, BoT utilizes the tree of thoughts (ToT) Yao et al. (2024). the most recent structure, as its base model to generate reasoning chains in each iteration. As mentioned in the main paper, the base thought generation model can also be the Graph of Thoughts (Go'T) Besta et al. (2023), i.e., BoT with GOT.. However, due to time constraints and the fact that the current GoT has not been applied to mathematical problems, BoT design exclusively embraces ToT. Furthermore, when employed as the base model within a boosting mechanism, thought structures in each iteration can remain lightweight. Ultimately, the proposed BoT generates heterogeneous tree structures, with each tree being shallow- whaghte-weighted binary tree.
C.I NEXT THOUGHT GENERATION AND EDGE WEIGHTS COMPUTATION
Utilizing the Prompt for the next thought generation discussed in Section A LLMs can generate the next possible thought for the reasoning step 2; by incorporating the experience F'...t and replacing }G;} with 21. For reasoning step 2;, LLMs utilize Prompt for the thought evaluation to generate the evaluation score as the edge weight between 2; and 1 For a detailed procedure, the reasoner.py. In direct example of BoT applied to the "3 5 6 8' in the Game of 24, using gpt-3. 3.5-turbo, Table 7 and Table 8 present the thought generation while the Table 9 show how to compute the computation.
source code is available in
C.2 THE NECESSITY OF HETEROGENEOUS TREE STRUCTURES
In each iteration BoT, the heterogencous tree structures with different tree growth strategies and various temperature and Top p settings of LLMs are be built to explore more reasoning search space and improve the robustness. As can be seen in the source code Boosting(ffThoughhti under the examples/, the temperature and T values for LLMs within each tree chosen from the ranges [0.2, 0.4, 0.6, 0.7, 0.9, 1.1, 1.5] and 10.1, 0.3, 0.5, 0.7, 0.9]. respectively. And the tree growth strategy can either be level-wise growth or leaf-wise growth. We observed the following two benefits of guaranteeing such Heterogeneity.
core.py
Heterogeneity extends the reasoning search space, thus increasing the convergence speed. When different trees are constructed for distinct purposes, such as exploration with a level-wise strategy or exploitation with a leaf-wise strategy, and are based on LLMs with varying configurations for being random or deterministic, the generation of reasoning steps and the resulting reasoning chains can exhibit significant differences, effectively covering wider range of reasoning possibilities. For example, in one iteration, when LLMs generate the next thought with more confidence, similar thoughts will be explored continuously; otherwise, LLMs with more randomness tend to generate diverse thoughts. It is generally challenging predict whether deterministic reasoning randomness can contribute to the solution. Therefore, incorporating heterogeneity by mixing different types and logical reasoning steps allows to comprehensively explore the reasoning space within single iteration, ultimately facilitating subsequent iterations. In the ablation study, we compare the performance of BoT between Heterogencous and homogeneous tree structures.
Heterogeneity reduces the possibility of producing invalid or wrong reasoning chains, thus enhancing the robustness. Unlike heterogeneity, in trees with homogeneous settings, individual trees tend to generate thoughts following consistent logic and build reasoning chains with the same tree structures. Then, when the logic is wrong or the underlying structure is invalid for the current question, reasoning chains obtained by all trees of BoT in each iteration can only contain noisy and incorrect reasoning steps. Even after aggregating them to obtain more refined reasoning chain for evaluation in BoT, the experience may still diverge significantly from providing suitable problem-solving suggestions. Therefore, designing tree thought structures to be heterogeneous can be way to reduce the possibility that there are no effective reasoning chains to be evaluated for subsequent BoT's iteration. Therefore, designing tree thought structures to be heterogeneous can help mitigate the possibility of having effective reasoning chains available for evaluation in subsequent BoT iterations. This enhancement of robustness allows BoT to tackle questions of varying difficulty levels.
15

---

Published as a conference paper at ICLR 2024
Algorithm 2: Best-First Aggregation and Greedy aggregation
Input: M reasoning chains where the reasoning steps of m-th chain are denoted 2/=11 Output: Aggregated chain L
Best-FFirs Aggregation
for each chain = 1,2, M do
Compute the sum of edge weights for m-th chain as V Li=m 1
end
Get the best chain among M chains by performing m = argmazm ( {V")
Assign the aggregated chain as the best chain, 1 == ci=1
2n
Greedy Aggregation
2 := z where m = -argnazm (VTT).
for each aggregation step i 2, .... 72 do
10
for each chain m = 2, .... M do
Collect Jm = {j, sim (zi-1,27] 27th > 0.7; E ]
11
j jegmazje.m (V
13
end
14
Get the best next reasoning step by performing: ž, = where
2jo+1
j+ (fj {VM
15
end
16
Obtain the aggregated chain 1
D THOUGHT STRUCTURES AGGREGATION
After completing the reasoning in Heterogeneous Tree Structures, the aggregation process of BoT first extracts the best reasoning chain from each and then combines them using either the Best-First or Greedy aggregation method into a single reasoning chain. More details of these two aggregation methods can be accessed the source code
hoogh/// aggregator.py.
As shown in the first block of the algorithm 16 the Best- first aggregation is straightforward approach for aggregation
directly extracts the chain with the highest sum of edge weights. This method is fast and stable. It typically guarantees competitive performance as the subsequent experience able to be generated by analyzing the best chain among obtained reasoning chains. However, can only select existing chains without making effective adjustments. Greedy aggregation is more advanced as it combines reasoning steps from different chains to produce a new, better reasoning chain with the highest edge weights. The greedy aggregation procedure in algorithm contains two steps. It first collects reasoning steps that are similar to the aggregated reasoning step 2;-1. Thus, the next aggregated reasoning step is selected from the next reasoning steps of this collected set by maximizing the edge weights. And, sim is the similarity function that uses L.MMs to assess the percentage of identical words and mathematical numbers shared between paragraphs. 0.7 is empirical threshold obtained from experiments.
E INFLUENCE OF THE BAD FEEDBACK
The feedback obtained by evaluating the aggregated reasoning chain with LLMs may include analysis of limited usefulness and completely incorrect conclusions and error reports. This issue typically arises due to the nature of L.I.Ms which are language models and do not inherently verify the accuracy of the generated text. Additionally, the capabilities of LLMs, such as gpt-3.5-turbo, are constrained when used as validators for mathematical problems.
A direct example is presented in Table 7 The analysis report concludes that "The final result obtained in Step 3 is 80, which is mathematically equal to 24." Even worse, the experience further contains that "the reasoning chain is correct" and "No emors were found in the reasoning steps.". Using the prompt with this experience as the input in the first iteration, BoT is misled to generate wrong reasoning steps, and the corresponding aggregated chain can be seen at the beginning of Table It is evident
16

---

Published as a conference paper at ICLR 2024
that the aggregated chain is logically incorrect and does not adhere any of the rules of the Game of 24.
However, argue that spurious feedback will not be amplified over iterations; instead, thanks the iterative mechanism of BoT, its negative impact on the generated reasoning steps can be mitigated or even entirely rectified in subsequent iterations. The main reason is that the generated wrong reasoning steps will be further analyzed to produce new experiences to be added to the prompt. Specifically, as these reasoning steps contain obvious mistakes that are easy identify, LLMs are prone to generating correct error analysis and providing effective advice for revisions. With this new experience included in the prompt, BoT is capable of generating correct reasoning steps. As demonstrated by the experience in Table [ BoT produces detailed error reports and revision suggestions, resulting a rational thought generation process illustrated in Table
The advantage of BoT, which leverages iterations to mitigate the detrimental effects of erroneous feedback, is evident in Figure [ Notably, the performance of BoT exhibits consistent enhancement with an increasing number of iterations. This underscores both the significance of accumulating experience iteratively and the capacity of subsequent experiences to rectify prior errors.
F
MORE RESULTS ON MATH
11X
71.3
11A
76.1
516
Overall #samples: 5000
Preaigebra Asamples:
Algebra #samples:
12.9
5L9
664
18.
55-
Solving Rake
solving
22.3
15-
16-
Counting & Probabiity samples: 474
Number Theory @samplesi 540
Geometry #samplesi 479
GPT4 ComplexCoT
GPT4 PHP+ComplexCoT
GPT4 BoT wo/experience
Selving Rate
282
GPT4 BoT
GPT4 BoT+CoT
15.7
GPT3.5
15.0 144 132
GPT3.5 ComplexCoT
GPT3.5 BoT
GPT3.5 BoT (GPT4)
Precaiculus #samples: 546
Intormediate Alge #samples: 903
Methods
Figure 5: Solving rates on all the problems from different categories of the MATH dataset with different methods. The comparsion between these methods are performed the categories. including PreAlgebra. Algebra, Counting Probability, Number Thcory, Geometry, Precalculus, and Intermediate Algebra, of the test set. The sub-figure with the 'Overall' shows the solving rate computed on all the problems across all categories.
we provide the solving rate of different methods in each category of the MATH dataset. The diverse range of mathematical problems in these categories poses a significantly more challenging benchmark for mathematical reasoning. Thus, the complexity and diversity of the problems in MATH require a wide spectrum of reasoning capabilities for solutions. Consequently, a detailed examination of our approach and its comparison with other methods in this context yields valuable insights.
In Figure 5
17

---

Published as a conference paper at ICLR 2024
LLMs. The experiments conducted on the MATH dataset employed prominent large language models (LLMs), namely, GPT-3.5-Turbe hereafter abbreviated as GPT3.5, and GPT-4, denoted as GPT4 for brevity. We directly utilized the release APIs of OPENAI.
Competitors.
GPT4 ComplexCoT. This is the GPT4 model employing greedy decoding (i.e. temperature = =0) with the ComplexCoT Fu et al. (2022) prompting method. The reasoning examples utilized in the prompt for reasoning are derived from the corresponding Complex CoT publication Fu et al. (2022). As greedy decoding is used, we do not follow the self- consistency method Wang et al. (2022) to sample reasoning paths.
GPT3.5. With the standard prompt, the GPT3.5 model is used to generate the answer.
GPT3.5 ComplexCoT. Similar to the GPT4 ComplexCoT but change the model to GPT3.5.
GPT4 PHP+CompleXCoT. This is the GPT4 model employing greedy decoding (i.e. temperature O) with the PHP Zheng al. (2023) ColFuu et al. (0022). Specifically, in the Phen et al.] (2023) tramework, the Complex CoT prompt is used to generate initial base answers, from which the PHP+Complex CoT can then develop the subsequent answer generation prompts. Thus, at the beginning of the interaction, by passing a concatenation the base prompt of Complex CoT and the current question to the LLM, the base answer can be generated. Then, relying on the Complex CoT prompts revised into the PHP version with additional hint sentences, the progressive-hint prompting framework is performed on this base answer update the hint over interactions generate the right answer. We refer to this as the PHP+Complex CoT corresponding to the Progressive-Hime Prompting Complex CoT (PHP-Complex CoT) in the original work Zheng et al. (0223). The number of shots from Complex CoT is 8.
GPT4 BoT wo/ experience. The GPT4 model is used to perform reasoning with the proposed BoT framework without the experience accumulation. The basic settings of BoT follow those presented in the main paper. Therefore, after one iteration, the aggregated chain will be used as the solution.
GPT4 BoT. The GPT4 is used to perform reasoning with the full version of BoT as shown in the main paper.
GPT4 BoT COT. Apart from the BoT framework, 5 reasoning examples from the Weil let al. (2022) publication are included in the prompt. Therefore, in each iteration, the prompt contains not only experience but also additional 5 CoT reasoning examples.
GPT3.5 BoT. Similar to the GPT4 BoT but change the model to GPT3.5.
GPT3.5 BoT (GPT4). In this experiment, we utilize the GPT3.5 to perform reasoning, thus generating thought chains in the Thought Structure Generation. However, when performing the thought evaluation and the experience generation in the aggregated Thought Chain Analysis, the GPT4 model is used to get the evaluation and the analysis feedback.
We obtain the following additional observations from the results in Figure 5
The top performance of BoT on challenging problems derives from the accumulation of experience. BoT-related methods, such as GPT4 BoT and GPT4 BoT + CoT, consistently achieve the highest problem-solving rate on different sub-categories of MATH. Specifically, GPT4 BoT outperforms the current best GPT4 PHP+CompleXCoT by 8.6%. while GPT4 BOT CoT is even 12.4% higher. In all seven categories, GPT4 BoT is at least 0.8% higher than GPT4 PHP+ComplexCoT. and the corresponding number on the Algebra problems is even 12.5%. Similar for GPT3.5 BoT and GPT3.5 5 BoT + CoT. However, when no experience is accumulated in the BoT framework, the performance drops significantly on all mathematical problems, as shown by the GPT4 BoT wo/ experience.
In addition to experience with error analysis, including correct examples, such as simple CoT instances, is essential for improving the problem-solving efficiency of the BoT in challenging mathematical problems.. GPT4 BoT outperforms the GPT4 PHP+ComplexCoT by a large margin on the first five sub-categon categoriss of MATH problems. Nevertheless, in the domains of Precalculus and Intermediate Algebra, which demand more intricate reasoning and complex logical steps for solutions, BoT exhibits only marginal improvement of 0.8% and 2.4%, respectively. These gains
18

---

Published as a conference paper at ICLR 2024
are limited compared to the more substantial enhancements observed in simpler problem categories. After directly adding 5 correct CoT examples into the prompt, GPT-4 BoT + CoT demonstrates significant performance boost, surpassing GPT-4 BoT by 7.7% and 11.5% in Precalculus and Intermediate Algebra domains, respectively. This basic conclusion from these observations is that to guarantee the top performance of BoT in complex mathematical problems, relying on trial-and-error analysis to learn how to reason is not sufficient; instead, the correct answers should also be provided in the prompt for LLMs.
While GPT3.5 with BoT may initially fall behind GPT-4 CoT, leveraging GPT-4 as the evaluator and analyzer generate experience allows GPT-3.5 BoT (GPT-4) to outperform GPT-4 Complex CoT. With the GPT3.5, which has less capacity than GPT4, as the LLM, the solving rate obtained by BoT at least 7.7% (on Algebra) lower than GPT4 ComplexCoT. It is evident that when less powerful LLMs produce lower-quality trial-and-error analyses, the BoT is unable to outperform GPT4 ComplexCoT. Thus, after using the GPT4 in the experience generation part while GPT3.5 is only used to generate reasoning steps, GPT3.5 5 BoT (GPT4) shows significant improvement in all categories, leading to a solving rate of 55. 85, which outperforms GPT4 ComplexCoT by 5.5% and is even 1.9% higher than the current state-of-tee of-the-art art GPT4 PHP+CompleXCoT. These observations further demonstrate that the accumulation of experience over iterations in the prompt constitutes the primary factor contributing the success of the BoT framework.
G REASONING RESULTS OF "GAME OF 24"
First, in Table 5 Table we present the detailed prompts that BoT used during the reasoning process, thus providing a comprehensive understanding of what BoT does within each iteration. Then, starting from Table I0] we show some exact examples containing the whole reasoning process of BOT. Following the basic settings shown in the experiment section, these experiments are obtained using BoT with the GPT-3.5-turbo model.
Table S: Reasoning steps generated by gpt-3.5-turbo when experience is included in the input prompt. We first let model generate one step of reasoning five times to check the diversity and then present the final reasoning chain after finishing the first iteration of BoT.
Prompi of Game of 24 without experience
the 24, you given four numbers, and the poal is bask aniihmelli operations (+. *.i) combine numbers and oétain resal of 24, You can only use number caes, and pareatieess can used to change the order of operations. Analysis format of each step: Step. . Current set:, Selected two nambens Operation: Computed new mumber. Remaining numbers: New set:
The given four mambers are: 144
think step sep.
Recall histoctcal reasoning experience Uggnore when experience empty): www.eereeeneeeeeeeeeee..
Pay anention to analysus and conctusion in the experience to avoud making similar mistakes by following the advice.
Below oedered reusoning steps, accomspanied by their evaluased
higher
reasoning step likely complete the task.).
Rased on listed reasoning stops only within the shove" " subsecquemtaal possible reasoning step.
(i.., Not the ones in the experience block), please make one stop of reasoning generate only one
responses
ypt-33--turbu
Step I.
Current set: 1146, Sclected two numbers: 11, Opention: +, Computed new number: 2. Remaining nimbers: 46, New set: 24.6.
Step 1. Cuureat set: 6,
Sclected two mumbers: 11, Opention: Computed new mimber Remaining minheer: 466, New ket: 24 6. Oyention: Computed new number: Remaining
Step Cunrear
6,
Solezted numbers:
New
Simp Current set: 6,
Selected two monbers:
Opention: Computed new number: Remaining mumbere 46, New
Step I. Cancerr set: 1 6, Sclested two mimhers: 11, Opention: Computed new mimber: 2, Remaining maniers: 6, New set: 246
Obtaimed reasnnig chain after aggresation
Step Currea set:
Selested two mombers:
Opention: Computed new mumber:
Remaining mumbers 6, New
Evaluste Score:
Step 2, Cuncear set: 1.6., Sclested two mumbers: 14, Opention: Computed new mubber Remnining numbers: 1., New set: 4 6., Evaluste Seace: 0.7
Siep Current set: 1 6, Selected two numbers:
Openaioo:: Computed number
Remaining numbers: 4 New 144 Evaluste Score: 0.7
H REASONING RESULTS OF "GSM8K"
BoT uses similar basic prompts and the specific format as shown in Table Table Only the task prompt will be changed, as shown in Table 15] Then, starting from Table [6] we show some exact examples containing the whole reasoning process of BOT. Following the basic settings shown in the experiment section, these experiments are obtained using BoT with the GPT-3.5- --ttubo model.
19

---

Published as a conference paper at ICLR 2024
Table 6: Reasoning steps generated by gpt-3. --ttubo when experience is included the input prompt. This experience is the analysis on the reasoning chain of Ta With this experience in the prompt, we present five responses from the model and the final reasoning chain after finishing the second iteration of BoT.
Prompt of Game of 24 with experience
Fiest of alll Recall histortcal reasening experfence: 4440444 The 1-th Reusoning Chuin with Comments **AMAyy
Below a reasoning chain containing reisowing steps preseneed in onder
Step Current set: 114 Selected two numbers: Opention: Computed new number: Remaining numbers
6. Evalistte 0.7
Step 2. Currett set: 6. Selected two mombers: Opention: Computed new nimber: Remsining numbers: New sett 4 6., Foshuste Score: 0.7
Step I, Current set: 1 6. Selected two numbers: 1 I, Operatio: Computed new number. I. Remaining numberr; 4 6, New set: 14 6. Evaluate Score: 0.7
complete the talk and nech target connectly. The reavoring steps ernors that prevent the Reasoning Siep I: This step is lugical inference of the previous step since it follows the rule of selecting two zumbers, performing an operation, and upčating the set accordingy. However, the ressoning step is not beneficial to the correct solution The computed new number 2 does not lead to the desired resuli of 24. Advice: Try different operaticess combinations of sumbers to ohtain new number that is closer to 24.
Analysis Repert: This ressoning chain
solution.
Recommenaation Reject description: Reject.
Remsoning Step 2: There is an errer in the rensoning step description. is mentioned (wice as "Reasoning Step 2", However, assuming it is unique step, is logical inference of the previous step. The operation of multipiiction (*) is applied correclly to the selected numbers, and the new mumber of 4 obtained. The remaining numbers
updated accordingly.
Recommennation Reject description: Recommend.
Reusoning Step 3: There is an error in the ceasuning step description. It is mentioned as "Reasoning Step 1" instead of "Reasoning Step 3", This step is not a logicall inference of the previous step. The uperation of muliplication (*) is applied to the same numbers in Reasoning Step I, but the compused new number of I different. The remoining numbers updated accordingly.
Error Report: The computation in step incorrect. The correct computation should =I
Advice: Double-choit the computation and make sure il accurate.
Recommennation or Reject description: Reject.
Confidence score: 0,7
Five responses from the upé-3.5-turbo
Step Current set: I1 6. Selected numbers: Operatiun: Compuled number. Remanning numbers: New set: 1 6...
Step 1. Curreat set: 6, Sclected two numbers: Openaion:: Computed new number: Remaining numbers: 4, New 1 7
Step 1, Curreat set: 1 6. Solecsed two numbers: 1. Operation:" Computed new mumber. 1. Remaining numbers: 4 66 New set: 1 6.,
Step 1. Current set: 1 6. Selected two numbers: 14, Operation: I. Computed new number: 0.25, Remaining numbers; I New set: 0.25 6...
Step Currear
Solected numbers: Opention: Campated
number; Kemaining numbers: 6, New set:
Obtained remoning chain after aggregation
Step I, Cuurear set: 1 6, Sclected two mumbers: I, Opention: Computed new mimber. Remaining numberrs 4 6. New set: 1 6., Evaluste Seoce: 0.9
Step Curreat set: Selecsed numbers: Operation Computed new number: Ramaining numbers: New
Evaauute Score: Step 3, Currest set: 46, Selected two numbers: Operation: Cocaputed new number: Remaining numbens: New set: 24. Evaluate Scure:
Table 7: An example of how BoT generates the next possible thought for the reasoning step 2/
Frompl
thought generation
In the game of 24, you are given four numbers, and the goal is to use bask arithmetic operations it. v, ".1 to combune these numbers and obtain a resulk of 24. You can only use each number ones, and paremtheses can be used to change the order of operations.
Analysis format each step: Step. Cureen Selected nambers: Operation:, Computed mimber. Remaining sumbers New set:
The given numbers are: 3.5
Let's think step by step.
First of all, Recail historical reasoning experfence:
threeeee The 1-th Reascning Chain with Comments #itheeey Below a ressoning chain containing reasoning steps presested order:
Step 1. Current set 3566 8, Selected two numbers: 6, Operation: + Computed new number: 20, Remaining numbers: 3 New set: 30 8. Evaluute Score: 0.9
Stop 2. Curreat set: 30 Selected numbers: 30 Opention: Computed mumber. 10, Remaining aumbers: New 10 Evviltate Score:
Step 3, Currest set: 10 Selected two numbers; 8, Operation: Computed new number. 80, Remaining numbers; None, New set: Evallatt Score: Q.9.
Analysis Repoct This reasoning chain can complete the task and reach the turget correctly by exccuting its ceesoning steps. The final resalt obtained in Step. 3 is 80, which mathematically equal
Rensoninn Stop I: This renseeing step a logical infereace the previons stop. The numbers 5 are selected from the currest (3 6 8) multiplied together to obtnin the new numbe: 30. The remaining numbers are 3 and This rensoning stop is beseticial to the correct solution as it reduces the number of elements in the set and generates new number.
Ressceinn Stop 2: This ressoning step a logical inference of previous step. The numbers and selected from current (30 8) and divided obtain the new number 10. The remaining sumber This reasoning step beneticial to the correct solution funther roduces the numter elements the set and generates a new number.
Rensoning Steg 3: This ressoning step a logical inference of the previous step. The aumbers 10 and 8 are selected from the current ser (10 8) and moshippied together obtain
sumber Since
romaining numbers, the result reasoning chein This reasoning step beneficial to conrec
solurion as il generstes the final resalt.
Advice: No encoss were found in the reasoning steps.
Recommmendation Reject Description: All reasoning steps are recommended as they are correct and contribute to reaching the correct solution. Cor Confiilence
0.9
sanocuee 2-th Ressoning Chain with Comments strancee To be continue, in the Table satauesssssssavee htw.://aaaaaeeeseessesseeeeee.ee Masssaausaa
Pay anention andlysis and conclusion the experience avoid making similar mistakes following the advice.
Below a list of orlered rensoning stops, acccesponied by fheir evalusted scores (A higher score means rensoning step more likely complete task.):
Step 1. Carrent sct 356 R, Selected two sunbers: 8, Operation: 4, Computed new number. 11, Remaining numbers; 5 6, New ser. 11.5 6. Evaluste Score: 0.2 Step
set: Selected numbers: Operation: Computed number: Remaining numbers: 11, New
II. Evaluste Score: 0.9
Based on lssed reasoning steps only within the ahove" sissequeniaal possible masoning step.
(ie., Not the ones in the experience block), please make one step of reasoning to generate only ose
The generated
Step 3, Currerr set. 30 11, Selested two mumbers: 11, Opention: -, Computed new number: 19, Romaining manibers. New 19.,
20

---

Published as a conference paper at ICLR 2024
Table 8: The 2-th Reasoning Chain with Comments of Table
RhRocese The 2-th Retorninng Chain with Comments #сRaнасс
Below reasoning chein containing reasoning stepe presented order:
Step 1, Carrent sct: 10 Selecsed two mimbers 8, Ogention: Comyuted new number. 1.25, Remaining numbers: Nose, New set: 1.25, Evaluzte Score: 08. Evaluste Score: 0.8 Stop 2. Curen set: 10 8, Selected numbers: 10 8. Operation: Computed number: 1,25, Remaining sumbers: Nose, New 1.25.. Evaluate Score: 0.8
Step 5, Current set: 10 8, Selected numbers: 10 8, Operation: Computed new number: 1.25, Remaining sumbers: Nose, Now set: 1.25. Exaluate Score: D.8
Analysis Report: This reasoning chain connot complette the took and reach the tirger concactly The ressoning stegs provided are incorrect and do nor lead to the solution dotaining result of
Ressoning Step This reasoning step is incorret. selected numbers, 10 and 8, not present in the given number set 3, 5, 6, and 8, Additionaly. the opention of division (f) does not realt in the compuieed new mumber of 1.25. The romaining mimbers are also not coereefly slemified.
Error Report: - The selected two numbers are not present in the given number set. The operation and computed new number are inconeet. - The remaining numbers cocrectly idemitied.
Advioe: Fissue that selected two numbers are present the given namber set. Use the conrect opentioo that will result in desired computed new number. Accurately sieniify the remaining numbers.
Recommmenatioon Reject Descripton: Reject This reasoning stop incorrect and does not contribute to the correct solutoon
Reasoning Step This reasoning step's is repetition of Reasoning
are present this step as presious step. Euror Report: - selected two sumbers are not present in gives sumber set. The operation and computed new number are incorvet. The remaining numbers are not corneclly identfiedd
therefore
Advioe: Eesure that the selected two numbers are presert the given namber set. Use the conrect opentrio thet will result in the desired computed new number. -Aecurately isentify the remaining numbers. Recommmennation Reject Description: Reject This reasoning step incorret and does not contrilute to the correct solution.
Ressoning Step. 3. This reasoning step is a rejetition of Ressoving Step I and Rensceing Step 2. The same crmes are present in this step as in the previous steps. present in the given number set. The uperation and compuled
Eroe Report:- - The selected two numbers
number incorvet. The remaining
numbers coreeclly idemtiied.
Advioe: Fasure that selected two sumbers are present the given number set. Use the conrect operation that will result in desired computte new number.
Accurately sdeniify the remaining numbers.
rnvoemmnndtioon Rejoct Descriptin:: Rejoct This remsoning stop incorret and does not contribute to the corret solution.
Confidence Score:
Table 9: Computation of edge weight between (the step 2) and - (the step 3)
Prompi for the thought evalsation
the game 24, you are given four nambers, and the goal is use basac aritmmeticc operations (+.r, ".fi to combone these mumbers and obtain resalt or You can only use each mumber ones, and parcatheees can he used to change the order of operations Analysis format of each step: Step Current set; Selected two mambers Openation Computed new manter. Remaining sunbeers New set:.
The given four numbers are: 3 &
Lat's think step by step. Below are the genemtte ceasoning steps. presented in coder, accompacied d by their evaluated scores (A higher score means the reasoning step is more likely to complete the teck))
Step I, Carrent set 3.5 8. Selected sunthers 8, Operation: 4, Computed new number. Remaining numbers: 6, set. 11.5 G. Evaluste Score: 0.2
Step 2. Current set: 11 5 Selected two nimbers: 6, Openaioo: + Computed now namber: 30, Remaining numbers: 11, New set: 30 11. Eealuste Seor: 0.9
Step 3, Currear sen: 30 11, Selected two mumbers; 30 11, Opention: Computed new number: 19, Remaining mimberree New set: 19.
What your evalustion score the logic, comectsess, and benefit reaching a final solition these ressoning stops? Pimos select oe value from [0.1, 033,0.5, 0.7, 0.9, 1.0 as the score, where a higher scare mests bettar reasoning steps. The score should he placed after 'Evaluation score!" for users to read.
The generated evaluation socre
Evalustion scure:
Table 10: Format of prompts used in Game of 24.
Prumpl Format for Next Thought Generation
the game 24, you are given four mambers, and the gool la use basic arithnetic operations (+.,, "./) lo combinc these mimbers and obtain revult You cun only use each number oaes, and pareathesess can he used to change the order of operations. Anilysis formut of each step: Slep. Current Selectod two nambere Operation Computed new nember. Remaining sumbers: New set:.
The given nambeer Let's think stop by stpp.
6,9.4.
Recall historical reasoming experience (Tgnore when experience empty): www.eessssssssssssssssssesaaseee
Pay anention analysis conclusion the experience avoid making similar mistakes following the advice.
Below a list of ordered rensoning stops, accorppnnied by fheir evalusted scores (A higher score means rensoring step more likely complete task.):
Rased listed ressuning steps only within the ahove" " subssequnttall possible ressoning step.
Not the
experience black), please make step of ressoning generate only one
Giiven taskinn the pame you are given mimbers Prompt Format for Experience Generation
goal
basic srithmetic opersiions (+.., 5,7) comhine these mimbers and oltain result
24, You can only use euch number once, and parentheses can be used change the onder of operations. The given four numbers ore: 4.5 10 11. Let's think step by step. Below is reasoning chuin containing reavoning steps prosented in order:
Please evaluate this ressoning chain by giving detailed comments comtining the following content: I. Can this rensoning chuin complete the took and reach the targer comeerly by eseruting its ressoning stepel why? Write a andlyis report with concitsion under 'Anly Report 2. For each ressoeing step, pleise provide a logical inference of the provious step and whether the reasoning step beneficial the each ressoeing stops please prwide cosommennation or rejection descripcius. Comments should be brief, avoid repeating the same andlsis in different steps and follow the format: Reasoning step jidx;, Analsis report: Advice: Recommencationn or Reject description:. 3. What is your confidenue store un these your evaluation and comments? Please select one value from [0.1. 0.31,..,,0 0.5. 0.7. 0.9, 1 The sovee should he placed after Conffdenne sovee" for users rend..
detailed amiysiss of whether the current
solution, For
reasening step crnea, please penvide errer report and cvnespeeding
revision.
21

---

Published as a conference paper at ICLR 2024
Table 11: BoT's success reasoning process for "4. 10 11".
Experience obtained Iteration 1
Sknocese The 1-th Renocning Chain with Comments #ttaraсe
Below reasoning shain containing retsoning steps presented onder:
Step I. Current sct: 4.5 10 11, Selecred two numbers: 5. Operation: 9, Computed new numher: 20, Remeining numbens 10 11, New ser: 20 10 11., Evaluate
Score: 0.7
Step Carnent 0.7
Selectal mumberee 10 Operation: Computed sumber: Remaining numbers: 20,
Fualutte Score:
Stap 3, Current set: 110 20, Selected two number: 110 20, Operation A. Computed new sumber 5.5, Remaining mumben:: None, New set: S.S., Evaluste Seore 0.9
Amilsis Report:
This masoning chain can complete the task and neach the taggst convently by executing its ressoning stepa, The finel result is 5.5, which is muthematically equal to
24.
Recsoning step This step lopical inforence of given mumbers. The numbers and selected from current and the operaiio is applied obtain the new number The remaining nambers are and 11, This ressoning step is heneficial the correct solution as it reduces mumher eloments the set.
Ressoning step This step is logical inference of the prosious The mimbers 10 and II are selected from the cument sei, and the operation + spplied solution funther roduces the namber elements the
obtiin the sumber 110. The romaining number 20. rensoning step heneficial sel.
This step is logical inference of the previous step. The nimbers 110 and 20 are selected from the current set, and the operation is applied to obtain the number 5.5. There equal to
Ressoning step 3:
remaining numbers, which the reasoning chain resched the result. The final result of 5.5 is matbematically
Advice: No erros were found in reasoning chain. The steps are cornectly executed and lead to the cornect solution.
Recommennaaion Reject description: The reasening chain recommended. as it successfallly reaches the target and provides the vorrect solution.
Confidence scun: 0.9
Experience obtained in Iteration 2
KARAcuue The 2-th Reasening Chuin with Commenis 44AMsаy
Below reasoning chain comsining reasoning steps presented order:
Step I. Current set: 4.5 10 11, Selected two numbers: 10, Operation: Computed new number. 40, Kemaining numbers: 5 11, New set: 40 IL. Evaluate
Score: 0.9
Step 2. Carreni set: 11, Selected two number:: 11, Operation: Computed new number: Remaining numbers: New
Evaluste Scure: 0.9 Step I. Current set: 4.5 10 11, Selected two numbers: 10, Operation: Computed new number. 40, Remaining numbers: 11, New set: 40 5 11., Evaluate
Score: 0.9
Ankysis Report: This reasoning chain cannot complete and reach target correcll. The reasening steps are repetitive and not to desired result of
Reasoning step 1: This step is logical inference of the given numbers and follows the rules of the game. Matiplying and 10 gives 40, and the remaining solution reaching 24. Reasoning step 2: This step is repetition step selects remaining numbers Again, this step does not lead to the target of 24, Reasoning step This step is repetition of step 1. It does not provide any new information er progress towards the target, The result the same in step I. Advice: The reasoning steps comeet solution.
numbers
How
step does contribute
multiplies them to get new becomes
revised and aijusted find different approach that leads the larget of Repetiiive steps will help reaching the
Recommenndaion Reject description: The reasening chain is rejected due to repetitive steps and lack progress towards the target.
Confidence scure: 0.7
Experience obtained Herationn 3
Whnooece The 3-th Rensoning Chain with Comments #tnnrece Below reasoning chain comsainng reasoning stegs presented ooder:
Step 1. Current set: 4.5 10 11, Selected two sumbers: 4.5 Operation: 4, Computed new number. 9, Kemzining mumbers: 10 11, New set: 9 10 11., Evaluate Score: 0.7
Stop 2. Carrent
Selocted mimbers: 10, Opention: 1, Computed new sumber: Remaining mumbers: 11, New Step Caneat set: Selected two numbers; 90 11, Operation: 1, Computed new number. 8.181518181818182, Kemaining sumbers: New sec: Evaluate Score: 0.7
Evalunte Score: 0.7
Analysis Report: This reasoning chain cannot complese task and reach the target coneecly. final result obrained in Step is 8.ISI818ISSS1S1E2 which not equal to targst number Therefore, this reasoning chain incorvest.
Resscning step I: This step is a logical inforesce of the previcus step. Two aumbers, and 5, are selected from the enreent set 5 10 11) and added together to obtain new number, 9. The remaining numbers are 10 and 11, and the new set becomes 10 11. This step is beneficial to the correct solution as it combines two numbers and reduces Recommenndation Reject description: Recommend,
size the
Reasoning step 2: This step is lopical inference of the previcus step. Two numbers, and 10, are selected from the current set 19 10 11)) and multiplied togother to obtain new sumber, 90. The romaining numiher is and the new set hocomes 90 11. This stop heneficial to the correct solution as comihines two mumbers and roduces Recommmendation Reject description:
the
Rocommend.
Ressening stop This step is a logjcal inforenee of the previcus step. Two numbess 90 and are selected from the carrent sot (90 11) and divided to abtain a new mumber, 8.18 1111811188811888 Since there are remzating nanbeers, this the final resalt, However, the obtained result is not egual to the target mumber 24. obtained rosili equal to the target number.
repoet: masoning stop incoerect
Advice:: Try different operations or combinatioss of sumbers to obtain a resalt closer the target mamieer.
Coufideence score: 0.?
continue in Table
22

---

Published as a conference paper at ICLR 2024
Table 12: BoTss success reasoning process for 54.5 10 11".
Experience obiained in Iteration 4
AMRAUU The Reusoning Cluin with Commenis #eMAlaau
Below a reasoning chain containing rensoning steps presented onler
Step I. Current set: 4.5 10 11, Selected two numbens 10, Operation: Computed new number 40, Remaining numbers: 11, New sett 40.5 II., Evalinate
Score: 0.7
Stop 2, Carrent set: 40 11, Selested two munbee:: Openitio:: 4, Computed new numher Remaiining numbers: 11, New set: 11., Evaluste Soore: 0.7
Step 3, Current set 45 11, Selected two numbers: 45 11, Opention: Computed new number: 34, Remaining numbenc. New sel: 34,, Evalusic Soom:: 0.9
complese task reach the larget coreeclyy by evecting reasening steps. The final step computes number which the desined resall of 24 when using the given four numbers and the specified anilhmetic operaaiions. Remsoning stop I: The current set 4 10 11 Two nimbes, 4 and 10, are solested. The openaioo chesen is multiplication (*), resulting in a compusted now becomes 5 Logical inforence; The selected numbers valid elements from the current computes
Asulyas Report:
ressoning
number of 40, The remaiinng numbers are and 11. The
solution: Yes, step reduces number elements the number can used subsoquent stops. Recommenciaioon: Accept
set, the operaionn
valid unthmmticc opention Beneficial the
Reasoning step 2: The curreni sot is 40 5 II. Two number. 40 and are selected. The operation chusen is addition (+), resulting in computed new number of 45. The remsining number 1I. The now becomes 45 11. Logical inference: The selected numbers valid elements from the current set, and the operation is arithmetic operation. Beneficial
solutoo: Yos, step futther reduces the mamber of cloments be used subsequent steps. Recommembtioo: Accept. Remsoning step S: The curent set is 45 11 Two numbers 45 and 1I, selected. The operation chosen is subtmaction (-), resulting in a computed new number of 34, There operation a urishmetic operation. Beneficial the correct solutio:: this step computes the final result 34, which not equall to larget Recommeenttioo:: Accept.
computes new number that
remaining numbers. The new becomes 34, Logical inference: The selected numbers valid elements from the current and the
Confidence scure: 0.9
Experience obtaimer Heration 5
*AAnoose The 5-th Reasoning Chain with Comments *hAieaae
Below is reasoning chain containing reasoning steps presented in onder
Step I. Current sett 4.5 10 11, Selected two numbens: 10, Openation: * Computed new number. 40, Remaining numbers: 11, New set: 40 5 11., Evaluste
Score: 0.9
Stop 2. Curren set: 40 11. Selected two number:: 5 11. Operation: s Computed number: 55, Remaining numbers: 40, New 40., Evaluate Score: 0.9
Step 3, Carreni set Selected number: 55 Operation: +, Computed new number 95, Remaining numbers; Nome, set: 95., Evalsante Soore:
Asulydi Report: This reasoning chain can which
the task and reach the targel correclly by executing its reasoning steps. The final result obtained in Step 3 is 95, to 24 machemaicalll. Therefore, this reasoning chain does not provide the correct solnion.
Reasoning step The current step is logical inference the grevious step, as follows the rule of selecting two aumbers
the current set and perfocming the opeeratio. The reasoning step is beneticial to the correct solution as it generates a new number and updates the set for the next step.
Reasoning step 2: The carrent step is logical inference of the grevious step, as it follows the rile of selecting two aumbers from the carrent set and perfocming the the
opeeation. The reasoning step beseficial the correct solution
generates new namber and equal 24 muthematically
step. How the reasoning step
benelicial
correct solution, as final result obtained
which
Keasoning step 3: The earrent step is logical inference of the previous step, as follows the rule of selecting two sumbers from the carrent set and perfocming the operation, However, the reasoning step is not beneficial to the correct solution, as the final result ubrained is 95, which is not equal to 24 machematically. Advice: In Step 2. instead of performing the a operation. different operasion should chosen obtain number. In Step 3, instead of performing the operation, different operation should chosen obtain new sumber that can be combined with remaining numberis] reach the target of Recommeendation Reject description: Step I: Recommendutoon Step 2: Reject Step 3: Reject
Confidence scure: 0.9
Experience obtained Heration 6
Rhnooece The 6-th Rensoning Chain with Comments vsnnrece
Below reasoning chain comsainigg reasoning stegs presented ooder:
Step I: Current sec: 45 10 11, Selected two numbers: 4 10, Operation: Computed new sumber: 40, Remaininn numbers: 11, New set: 40 5 11., Evallate
Score: 0.9
Stop Curicot set: 40 11, Selected aumbers: 5 11, Opention: Compoted new namher, Remaining mumbers: New
Evaluate Score: 0.9
Step 3: Current set 16 40, Selected two mumbers: 40, Openation: 1, Computed new number: 56, Komaining numbers: Nose, New set: Isvaluate Score: 0.9
Analysis Report This ressoning chain can complete the task and reach the taggtt coerectly by exccuting is reasoning steps. The final result obtained in the last step which is equal the target number 24.
are multiplied to obtoin new rumber 40. The remnining numbers, 5 and 11, are correctly incladed the new set. This step beneficial the correct solution as it roduces the number of elessents in the and grogresses towards the target.
Step 1: This step a logical inference the given numbers the goal of the game. The selected nos mimbers
Step 2: This stop logical inference the prosions step. The selested twn number, and 11, added abrain the namber 16. remeining number, comeetll included the new set. This step beneticial to concet solation redaces the number elements is set and progresses towards the target. Step 3: This step is logical inference of the previous step. The selacted two numbers. 16 and 40, are added to obtain the new number 56. Since there are no remaining numbers, the resoening clain ands here. However, the obtained reault of 56 does not mutch the target mumber of 24, Therefore, this ressoning step incomect.
The reasoning step Step 3 incocrect because the obtained resalt of does not match the turget number of Advice: To correct the ressoning step in Step a different operation or comsiination of mamieers should he chosen to obtain new sumber that is closer to the target of 24.
hiror Report:
Recommeencaioon Reject desoription: Stop Recommended Step Recommesded Step Rejocted Confidence score:
To be continor in Table
23

---

Published as a conference paper at ICLR 2024
Table 13: BoT's success reasoning process for 54. 10 11".
Experience oblaimed Nirratin?? 7
*ahreete The 7-th Reasoning Chuin with C Comments #hineeet
Below a reasoning chain containing reasoning steps presessed ander:
Step Current 4 11, Selected two numbers: 10, Operation: Computed new sumber: 40, Romaining numbers: 11, New sett 40 5 Evaluate
Score: 0.9
Step 2: Current set: 40 11, Selected two aumbers: 5 11, Openaion: 1, Computed new number: 16, Kemaining numbers; 40, New sec. 16 40., Evaluate Score: 0.9
Step Current 16 Selected numbers: 40, Operation: Computed sumbor Romaining numbers Nonz, New
Evalunte Score: 0.9
Analysis Repoat: This reasoning chain can complese the task and reach the target correctly by executing its reasoning steps. The final result obtained in the lust step is 34, which is muthemirreeilly equil to the target mumber 34
Step 1: This step logical inferesee the given sumbers and goal the game. The selected numbers, 4 and multiplied obtain The remaining numbers, and 11, are correctlly inclated the new set, This step beneticial the correct solution as reduces the number of elessents the act and progresses towards the target.
zumber
Step 2: This step a logical inference of the previons stop. The selettd two numthers and 11, are added to obcain the new namber 16. The remzining sumber, 40l, coreenlly included the now This step beneficial
solution reduces the sumber elements in the and progresses towards the target. previous step. The selested two mumbers, and 40, are substracted to ottain the now number 24. Since there are no
Step 3: This stop a logical inforence remaining numbers, the reasoning chain ends here. The final result of 24 is mathematically equal to 24.
No ernors were found in this ressonnng chais. The are corcaity exceuted and lead to the cornect soletion. Recomurencation Reject description: reasening chein recammendal os successfullly reaches the turgr and provides the solution. Confidence score:
Experience obtuimed Iteration 8
SARACUL The 8-th Rensening Chuin with Comments ччллнлу
Below a reasoning chain containing rensoning stee presessed in onder:
Step Current
11, Selected numbers: 10, Operation: Computed new number: Remaining numbers: 11, New seu 40 5 Evallatt
Score: 0.9
Siep 2: Current set: 40 5 11, Selected two sumbers: 5 1I, Openation: +, Computed new nimber: 16, Remaining number: 40, New set: 16 40.. Evalutte Scure: 0.9
Step 3: Carrent set 16 40, Selected two mumbers: 40, Operation: Computed new sumber: 24, Romoining numbers None, New set: 24, Foaluste Scor: 0.9
This reasoning chain can successfully complete the task and nuch the largel cornectly by executing its rensoning steps. The final reselt of mothheentiaally connect and equil to 24.
Amiysis Report:
Reasoning step I: This reasoning step a logical inference of the given task rule. It follows the rale of selecting mumbers and 10) and performing the reasoning step
opensioo mulliplication obtain
(40). The remaining numbers (5 and 11) aru commuily updateed
new set (40 5
beneficial cornect solution.
Reasoning step 2: This reasoning step is a logical inference of the previous step. It follows the rule of selecting two numbers (5 and I1) and performing the operation of addition to ohtain new number (16). The remaining mimber (40) correctly updated to the new set (16 40). This reasoning step is beneficial the concet solutio..
Reasoming step 3: This reasoming step is logical inference of the previous step. It follows the rule of selecting two mumbers (16 and 40) and performing the operation of subtraction to obiain a new number (24). Since there are no remaining numbers, the new set empty. The final result of 24 is mathematically corres and equil to 24. This ressoning stop heneficial the correct solution
Advice: No emons were found in reasening chain. The steps are cornectly executed acconling to given task rule. Recommennation Reject description: All reasoning steps in this reasoning chain are recommendedl as they are correct and contribuse to the corret solution. Confidence score: 0.9
Experience obiuined lerration 9
*AAMoUAe The 9-th Reasoning Chain with Comments *hAida
Below is massning chain containing remsoning steps presented in onder
Step I:
Current set: 45 10 11, Selected two numbers: 10, Operation + Computed new number: 40, Remaining numbers: 11, New set: 40 5 11., Evaluate Score: 0.9
Stop 2: Current set: 40 11, Selected two sumbers: 5 11. Operation: Cumputed new number: Remaining numbers: 40, New set: 16 40., Evaluste Score: 0.9
Step 3: sot: 16 Selected two numbers: 40, Operation: Computed new sumber: Remuining number: None, set: Evalusie Score: 0.9
This reasoning chain can sucuessfully complete the task and reach the target correctly by executing its reasoning steps. The final result of 24 is mathemotically cornect and equils when evalusted.
Analysia Repoct:
Reasoning step 1: This step a logical inference
previous stop as follows task rule selecting two numbers and 10) from the current net and performing the opuration to obtuin a new number (40). The remaining numbers (5 and 11) are correctly updited, and the new set (40 5 11) is formed. This step is beneticial to the correct sulution it reduces the number of elements in the set.
Reasoning step 2: This step logical inference of previous step follows the task rule of selecting numbers and from the current and performing the operation ubiain a new number (16).
remaining number (40) is correctly updated, the new sei 40) formed. step is beneficial to the cornet solution it furiher roduces the number of elemenis in the set.
Reasoning step 2: This step a logical inference of the previous step as it follows the task rale of selecting two numbers (16 and 40) from the current set and formed with only the computed number (24).
perfurming the operation obtain This stop beneficial the correct solution as reachis the final result.
number (24). Since there
remaining numbers. the
Advice: No errurs were found in the reasaning steps.
Recommennation or Reject description: All reasoning steps are recommended as they follow the task rules and contribute to reaching the cornect solution. Confidence score:
Experience obtained in lteration 16
RAnrovee The 10 Reasoning Chan with Comments hnneree Below reasoning chain comsining reasoning steps presented order:
Step 1:
Current set: 45 10 11, Selected two numbers: 4 10, Operation: Computed new number: 40, Remaining numbers: 5 11. New set: 40 IL., Evaluate
Score: 0.9
Stop 2: Current set: 40 11, Sclected two sumbers: 11, Openation 1, Computed new nanter: Remaining mumbers: 40, Now set.
Evaluate Score: 0.9
Step 3: Current set: 15 40, Selected two numbers: 16 40, Operation: v, Computed new zumber: 24, Remaining numbers: Nons, New set: 24. Eivalunte Score: 0.9
Analysis Report: This reasoning chain complete the task and reach target conrectly by executing reasoning steps. The final result reasoning chain is which is mathemaicclll correct.
Rensoning step I: This step is logical inforence of the gives task is follows the mlee of selecting two mumbers and performing an operation to obtain a new number. in this case, 4 and 10 are selected, and the operation is maltiplication ('). The computed new number 40, and the remaining numbers are 5 and 11. This ressoning step beneficial the Renscning step This step is logical inference the previous step as it follows the number. In this case. 5 and 11 are selected, and the operation is addrion (+). The computed new sumber is 16, and the remaining number is 40. This reasoning step is heneficial to the connect solution step is logical inference the previous step as follows number, this case. and are selected, and operation suberaction (-). The computed new number is there are no remaining numbers. reasoning step is heneficial to the correct solution as it produces the final result of 24, which is the teger sumber Contidencc score: L.B tnterreenteee www.wrwwwwooeeeeeee............e
wolution
reduces the momber clements the and produces new namber.
selecting two numbers and performing operation ottain new
fürther rollices the number of elements in the set and produces a new number.
Ressoning step
selecting
munberss performing operation obtain
24

---

Published as a conference paper at ICLR 2024
Table 14: BoT's incorrect reasoning process for "2 5.666 6". This is special case that BoT fails to solve the issues brought by the fake feedback but seems to believe that the number not equal to is correct; thus repeating the wrong reasoning chains after the second iteration.
Experience obtained in Iteration
1
RAnvoeve The 1-th Reascning Chain with Comments #hineevv Below is reasoning comaining reasoning stepe presensed order:
Step I, Current set: 2 6. Selecsed two numbers: 5 2, Operation: Computed new number: 3, Remaining numbers: 6 New set: 6 6., Evaluate Score: 1.0
reasoning chain can potemiialy reach the target conrecll by executing its reasoning seps, However, sance we only have one reasoning step provided, we cannet decermine whether the chain can be complesed successfullly or not. Reasoning step I: The reasoning step is logical inforence of the previous step, as it follows the given task zule of selecting two numbers (5 and 2) from the current perfoemingg the subtraction openation.
Analysis Report:
computed new number 3, and the remaining sumbers are 'hhe becomse 6, This step beneticial correct solution as reduces the sumber of elements the provides a new number for further operations. Advice: No ertuss or revisions are needed for this reasoning step. Recommmendation Reject description: Recommendzzion.
Confidence score: 0,9
Experience obloined in Iteration 2
RARRGUEE The 2-th Resocning Chain with Comments #itanses
Below is reasoning chain containing reasoning stegs presessed arder:
Step 1. Curreat set: 2.5 666 Sclected two numbers: 2 Opention: Computed new number: Remaining minbers: 6 6, New set: 7.66.. Evalnate Score: 0.9
Invallatto Score: Step 3, Curreat set: 426 6, Selected two numbers; 6, Operation: Computed new number: Remaining numbers. New set: Evallute Score: 0.9
Step 2. Curreat
Selected numbers: Operation Computed new number. Remaining aumbers: New
Analysi Repoct This reasoning chain can successflly complete the tisk and reach the turget correctly by executing it reasoning steps. The final result is which muthematically agual to
Ressoning step The current set
Two numbers, and are selected
opentiin is performed. computed new namber is 7. remaining
numbers are 6.. The new set 7 6 6. Logical inference: The reasoning step is logical inference of the previous step because follows the task cule of selecting two numbers, performing in operation, and updating the current set accondingly. Reneficial to the correct solution: Yos, this reasoning stop heneficial as generates new number.
soduces the number of elements the cureent is
Ressoning step number is The new set is 42& 6. Logical inforence. The reasoning step is logical inference of the presious stop becusse it follows the task rule of solecting two aunbers, perfomming opention, and updating the currest set accordingly. Benefiiial to the conrect solution. Yes, this rensoning reduces the number of elements Rensoning step ressaining numbers. The new set is 7. Logical inference: The ressoning step is logical inference of the previons step bocause it follows the tack rule of selecting two numbers, performing an operation, and updating the current set accondingly. Reneficial to the correct solution: Yos, this reasoning stop beneficial as generates final resalt which mathematically equal 24. Confidence score:
Two numbers,?
6, selected and the operation performsed computed new number is 42. remaining
beneficial is it further
generates new number.
current set 6, Two numhers, 42 and are selected and the opention is perforsed. The computed new mimber 7. There
Experience obtained Iteration 5
AbRAGUL4 The 5-th Rensoning Chain with Commenss 444A0a4
Step 1. Clament sct 2.5 6, Selected two numbers: 6, Ogeration: 1, Computed new number: 30, Remaining numbers: 2 New set, 30-2 G. Evaluate Seare: 0:9
Slep 2. Current set: 30 Selected numbers: 30 Openaioo: Computed mumber: 15, Remaining numbers: New 156, Evaluatt
Step 3. Cuneer set: 15 6, Selected two mumbers: Opention: Computaal new manieer 90, Remaining numbers: None, New set: 90. Evallste Score: 0.9
Analycis Report This reasoning chain can complete the task and reach the correctly by executing its ressoning The final reult obtained in Step is 90, which mathemrrically equil
Reasoning step This step a logical inference of the preious step becouse follows the task mile of selecting (wo mimbers (5 and 6) from the current set (2 5.6 6). performing the operation of multipliaaioon and chtaining new number (30). The remmining numbers and 6) are correctly upditted in the now set (30 266).
This ressoning stop heneficial to the correct soluton as it relinces the number of elements in the izt
slep a logical infermmee 6). performing operation of division, and obeaining a new mimber (15). The remaining number (6) is correctly updited the new sot (15 6). This ressoning step is heneficial to the correct solution as it farther reduces the mimber of elements in the set.
Reasoning step
previous step
follows iask rfle selecting two numbers (30 and from current set 2
Reasoning siep 3: This step is logical inference of the previous step bocause follows the task rule of selecting two numbers (15 and 6) from the current porforning
opersiion of multippication, and obtaining computed new number (90). This ressening step is beneficial to the currect solution as it simplifies the set a single number, which is the final result.
mumber (90). Since
no remaining mumbers, the
updattal just the
Advice: No emons or revissonss are neaded for the reasoning steps in this reasening cisin. Recommevaation or Reject description: All rensoning steps in this rensoning chain are recremeedda as they are logical inferences of the peevious steps and commrbbte the cornect solution.
Confidence scon: 0.9
Experience obtained Herration 9
SARAqUEe The 9-th Rensoning Clain with Comments #48аdлу Below is ressoning choin contanning rensoning steps presented onder
Siep 1, Cumrent set: 2.5 3366 6. Selected two numbers: 2 Openatio:: Computed new number: Remaining mimbere 6 6, New 766.. Evaluste Scure: 0.9
Step 2, Currest set: Selected two numbers: 6, Operation: Computed new number. Remaining sumbers: New set Evaluate Score: 0.9
Step 3, Current set 42 6, Selcoted two numbers: 42 6, Openation: Computed new number: 7, Remaining mumbers. NNw set: 7., Evaluate Score: 0.9
Analysis Report: This reasoning chii successdully completes the and reaches the turget conrectly by executing reasoning steps. The final computed number step is which mathematically equal tungei number 24.
Reusening step I: The current set 2 5.6 6. Two numbers, 2 and are selected, The operation is addition (+). The computed new mumber is The remaining numbers are 6 and 6, The new 7 6 Logical infermnce: The selected numbers correclyy chosen from the current and the operation performed correctly. The compused new number is the concet result of operation.
Benedit to the correct solution: This step reduces the size of the current sei and generates a new set for the subsequent reasoning steps.
Recommencation: Accept. The current set is 6 Two sumbers. and selected. The operation is mulippication The computed mimber The remaining
Reasoning new set
number
Logical inference: The selected two numbers are corretly chosen from the current set, and the operation performed correctly. The compused new number is the contect result of the operation.
Benefit the correct solution: This step further reduces the size the current and generates set for the subsequent reasoning steps.
Recommenéiioo:: Aucept
Reasoning step 3: The curent set 42 6. Two mumbers, 42 and 6. are selected. The operation is division (/). The computed new number is 7. There are no remaining number. The new sei is 7, Logical inference: conrect result of operation.
selected numbers conectly chosen from curcet and opentiin performed cornectly. computed number the
Benedit to the correct solution: This step completes the reasoming chain as there are no remaining numbers. The computed new number is the final result.
Recommenndation: Accepe
Confidence score:
2,5

---

Published as a conference paper at ICLR 2024
Table 15: Format of prompts used in GSMSK. The reasoning process of the "Question" is shown in Table 16
Prompt Format for Next Thought Generation
Question: Juses decides to run sprints fimess week. He runs meters cach sprint, How many total meters does run week??
Answer: Let's think step by step.
Recall historical reaswning experience (igaore when experience empty): www.rreeeeeeeeeeeeeeeeeeee Pay atcention to analysis and conctusion the experience avood making similar mistakes followang the advice.
Below a list of ordered renooiing stege, acccrspanied by their evalusred seores (A higher score means the reseoniing step more likelyy to complete the task.).
Based listed ressnning stops only within the shove" subsequemtia possible reasoning step.
(i.. Not the ones in experience block), please make one stop of reasoning to generate only ase
Prompt Furmal Experience Generation
Question:: Jusees decides to sprints fimles week. He runs meters eachs sprint. How many total meters does run week?
Answer: Let's think step by step. Below is reasoning chain contiiing ceasoning steps presented order.
Please ecaluate this ressoning thain by gaving ditailed comments contining the following content: I. Can this rensoning chain complete the taok and reach the targer conectly by executing its ressoning stepe? why? Write a analyis repert with concltson under 'Aulysi Report".. 2. For each ressceingg step. platse provide detailed anilysas of whether the currest stop a logical inference of the previous step and whether the reasoning step benefleial to the conrect solition. For each reasening step with ceness or rejaction descriptions. Comments shoukd be hrief, aviid reyeating report: Advice: Recommendaaton or Rejeet description: .. 3. What is your coufdaace score on these your evalnations and comments? Please select one value from (0.1,0.3,0 0.5.0 0.9, L.) The soree should he placod after Coodfidnnc sove!" for users to read.
penvide
report and euliggeeddng savice revision. For each ressoning step, please prwide cosommendaiion
same anilysis different steps and follow the formut Reasoning step jidx,. Analysis
Table 16: BoT's success reasoning process.
Experience obtaimed Ituration I
AAMAOOUN 1-th Reasoning Chain with Commenis #hrndeety
Below a reasoning chain comaining remsoning steps presented in onder:
Step Firstly, need to calculate the total distance Jumes each time sprints. Since he runs 60 meters each sprins, and be does this 3 times week, auttipll by Hvaluate Score: 0.7
Step 2: After calvulating the total distance Jumes runs each time he sprints, we need to calculats the total distance he runs a week. Since he runs 3 times a week, we multiply the total distance be runs each time by 3. Evaluate Scure: L.0
Analysis Report: The reasoning chain can complete task reach target conreclly by exocuting its reasoning steps. The reasoning chain correct and logical. and saccesfuully solves the problem by calcalating the local distance James runs in a week.
Analyus: This time be speints, However, description slightly misleading. James does week. The maltiplication should be between distance each speint and the mumber of spriats each time. Advice: description should be revised to "Since he runs 6l meters each sprint, and he does this times each time he nuss, we multigly 60 by 3 Reeommennttion The reasoning step is correct, but the description needs to be revised for clarity.
Reasoning
logically correct. It accurselly interpeets the problem idemtifingg the need calculate the total distance James runs each speints
week, be sprints each time. and this happens 3 times
Ressoning step Analyis: This stop logical inforence from the previous step. correcty colculates the sotal distance James total distance he runs each by the mumber of times runs a week. Advice: No revision needed. Recommnendation: The reasoning step correct should be accepted.
week multiplying the
Confidence score: 0.9 www.eeennnnnneeneeeeeeeee
Experience obiuined in Iteration 2
Whnooese The 2-th Rensoning Chain with Comments #snnreey
Below reasoning chain containing ressoning steps presented onler
Step I: Firsty, we need to colculate the toral distance James rans each time he runs, Since he rans 66 metors each sprint, and he does this 3 times each time he runs, we multiply 60 3. Fvallttt Score: 1.0
Analysis Report:
The gaven reasoning chain can partially complete the tosk and reach the target. However, it incomplete stops after calculatiin the distance James muns each time he nins, does not continue calculate the total distaace Jimes nins a wook.
Ressoning step The first step correctly calculates the tocal distance James rans each time he runs. logicailly infers from the problem that since Jumes runs 60 metors each speint, and does this
he
total distance he each time 60 This step beneficial the solution
necossary calculation towards finding the distance James runs in week.
Advioz: The reasoning chain needs to he contimued to include the calculation of the totall distance James russ in a week. This can be dose by multiplying the total distance lames nuns each lime he nuns (which was caleulated in
the number of times he runs in woek. Resommendutio: Accege reasoning step conectly calculates toral distance Jumes each time he However, the reasoning chain needs contimeed include the calculation the total distance James runs in week.
Con felncc score: 0.9
Experience obtained lieration 3
RARacuse The 3-th Renoening Choin with Comments #bRadace Relow a massning chiin containing rensowing steps presented in onter:
Step Ideetify the elements the problem. James nunning sprints in week., Posluste Soore:
week, with each sprint being moters. need total distance
Siep 2: Calculate the local distance James runs in single day. Since be runs 3 sprints each day and each sprin. 60 moters, the total distance in single day would be 3 sprints 60 mettrrspprint = 180 meters. Evaluste Scurc: 0.9. Evaluste Score: 0,9 Stop Now, calealate total distanee James be 3 days/week 150 meters/dyy = 540 meters. Evalunte Score: 1.0
werk, Since
week and each time he meters, total distance week would
Analyss Repeet: The reasoning chain does complete the tnck and reach the target cornectly. Faach logically follows from the previous one and contributes the solution of peoblem.
Reasening step The first step correcly idlentffes the elements of the problem and the task hund correctly interpmets the problem statement and sets up the busis for the next steps. Advice None. Recommendaion: Accept this step as it correctly identifies the problem and what needs to be done.
Reasoning step This logically follows from the finst li curreilly calculates the tocal distance lames rums in single day muksiplynng the number of sgrint, This step heneficial to soluton beeaks down the preblem into smaller, manageable parts. Advice: None. Recommmendatio:: Accept this step as correctly calculates the daily running distance.
sprinis he by the
Reasoning step 3. This step is logical inference from the provoous step. It correctly calculates the total disiance James rims a week by multiplying the discance he nins eich time the number of times he rons in week This is beneficial to the solation completes the colculation and provides the anower to the problem. Advice: None. Recommendation: Accept this step corectly calculates the weekly running distance.
Confidence scure: 1.0
Ignore the suhsequent Herations the correct reasoning chain has been obdainod.
26

---

Published as a conference paper at ICLR 2024
Table 17: BoT's half success reasoning process for "Toulouse has twice as many sheep as Charleston. Charleston has 4 times as many sheep as Seattle. How many sheep do Toulouse, Charleston, and Seattle have together Seattle has 20 sheep?". The obtained reasoning chain is only halfway to the solution. This is generally caused by the LLMs used by BoT failing to understand the question correctly. Thus, even though BoT performs a correct reasoning process, the full reasoning chain toward the correct answers not be obtained. Therefore. such reasoning chain is still regarded as a success of BoT as correctly solves the problem captured by the LLM.
Exporieace obtainer Heration
Whnovece The 1-th Reasoning Ch Chain with Comments #btnrece
Below reasoning chain commining remsonig stege presented ooder:
Step 1: if Seattle has 20 sheop, then we cun use the given ratios to calculate the number of shoop in Charleston and Youlouse, According to the problem, Charleston has 4 times many sheep as Seattle. Therefore, Charlesion has 4 20 = 80 sheep. Evaliate Score: 1.0
The reasoning chain the correct path to solve the problem. The stop cornectly inteppees the problem statement and accurasely calculates the number sheep in Charlesion based on the given information. ues the vorrect mathematical operation (mulliptication) to devermine the number of sheep in Charleston, which is logical inference from the problem statement.
Analysis Nopart:
Reasoning step 1: This step logical inference from the given problem statement. The problem
Chastesion has 4 times many sheap Seattic.
Given Seattle
sheep. correct mulliply 20 accumtely calcalates the nimber of sheep in Charleston, which seeded to find the tonal number of shoep in all three cities, There are so eaross in this step.
number sheep Charleston. stop is beneficial to correct solution as
Advice: No advice is seeded for this step it correct.
Recommendaioo:: This reasoning
recommended correctly interpeets the problem statement and accurately calculates the number of sheep in Charleston.
Confidence score:
Experience obtained Iteration 3
Ranoovee 3-th Reasoning Chain Comments minneote
Below is reasoning chain comsining reasoning steps presensed onder:
Stop if Seattle has 20 sheep, than
the given ratios calculate the number of sheep Charieston and Toulouse. According the problem, Charleston 80 sheep. Evaluate Score:
has 4 times many shorp is Scottle Therefore, Charleston has
Analysis Report: The reasoning chain can complete the task and reach the turget correctly by executing its reasoning steps. The task requires dinding out the total number sheep Toalouse, Charlsston, and Scatle, given Seutle his 20 sheep and the other cities have sleep problem
ratio Scatiie. The reasoning
uses the given Keasoning stop I: The first step correctly uses the information provided in the problem statement. logically infers that since Charleston has times as many sheep is Seattl and Senttle has 20 shoep. Charleston his 4t 20 80 sheep. This step is heneficial to the cornect solution as it conrectly caleuilates the mamieer of sheep Charleston
chain conrectly interpeees
caleslate number sheep at Charleston.
given
number sheep Scattl. There step as conecnty ressonal calenlated.
reasening step.
Advice: advice sealed
Recammendation or Reject desesiption: resommmend this rensoning step as it conrectly interprets the peoblem statement, uses the given miii, and coerectly calculates the number of sheep in Charleston.
Con Peeficencc
Experience obtained in Iteration 5
RARAGUSe The 5-th Resooning Chain with Comments #snanses
Below is reasoning chain containing rensoning steps presensed onder:
Step I: If Seatle has 20 sheep, then we can use the given ratios to calculate the number of sheep in Charleston and Toulonse. According to the problem, Charleston times many sheep Scatile. Therefore, Charlesion
sheep. Evaliate Score:
Analysi Report This reasoning chiin concetly applies the inforuatio given in the problem to determine the mimber of sheep in Charleston. It logically infers from the given information that if Charleston has timex ressaiing stop beneficial the Ressoning step The stop logically coenect and follows from problem statemett The step uses the given ratio sheep betwees Charleaton and Scattle to calculste the number of sheep in Charlesion. This step is beneficial to the correct solution as il correctly upplies the given ratio to lind the number of shoep in Charleston. There are no erross in this stop.
shoep Seatile, and Sentile his 20 shoep. then Charlesion must have * 20 80 sheep. This solution securately calculates number shrep Charlesten based the given information.
Advice: advice sccded
sep logieally concet and baneficial the solution.
Recommennatioon This step recommeneed as correclly applies the given ratio and calculates the mumber of shorp in Churleston.
Confilence score: 1.0
Experience obtuined Heraatonn 9
*ARMoUSe The 9-11 Reasoning Chain with Comments *stseate
Below is reasonngg chain containing remsning presemted onder:
Siep I: Since Charleston has 4 times as many sheep as Seottle and Seatile has 20 sheep. we can calculate the number of sheep in Charleston by multiplying by 20. Evalustic Score: L.D
Analysi Report: reasuning the number shoep in Charleston. This step is crucial for solving the problem as establishes the number of shoep in Charleston, which is then med determine the mumber of sheep in Toulouse.
Step accurate and logically sound. correctly upplies the information given problem siatement deternine
The step is logical inference from the given problem statement. It correctly interpeets the information that Charleston has times sheep Scutlle, applies this information caleulate number sheep in Clurlesion. This stup heneficial the correct solution provides the necessary information to calculate the cocal number of sheep in all three locatios. Advice: No advice is mecessary for this step as it corretlyy reasoned and accurslely caloslated Recommendationn I recommend acoepting this ressoning
Reasoning
is correctly reasoned and sccurately caleulited.
Confidence scure:
27

---

Published as a conference paper at ICLR 2024
BoT's success reasoning process for "Mariah's grandma was teaching her to knit. Mariah used 1/4 of a skein of yarn. Her grandma used 1/2 of skein of yarn. There are 364 yards a skein of yarn. How many yards of yarn did they use altogether?" ".
Table 18:
Experience obtained in Iteration 1
RAnVoeve The 1-th Reasoning Chain with Comments #htnevvv Below is reasoning comaining reasoning stepe presensed order:
Step I:
Convert the fractions of the skein of yam used by Mariah and ber grandmaa into yurds. Mariah used 1/4 of a skein, which equals 114 364 yards. Her grandma used 1/2 a skein, which equals 1/2 - 364 yurds. Evaliate Score: 1.0
Step 2: Calculate
total yards yam used by both Manah her grandma by adding the yards of yam Mirish used the yards of yara heer grandma used.
Evaluate Score: L.0
Siep I: Com the fractions of the skrin of sam used by Marich and her grandma into yards. Mariab used 1/d of a skein, which equals 1/ 364 yurls = 91 yands. Her grandma used of skein, which equals 364 yards- 182 yards. Evaluate Score: 1.0
The reasoning chain can vomplete the task and reach the larget correctly by executing iis reasoning steps. The steps are logical. follow a clear pengression, and are necessary for solving the problem. The steps convert the fractions of the skein of yam used into yards, which necessary desermine the tocal amount used. Then, they add these quantiies logether find the total amount of yarn used by both Matiah and her grandma.
Amalyii Report:
a logical inferesce of problem statement and beneficial to the correct solution as it transtates the problem into the same unit yyards), making it possible to add the quaatiies together. Advice: None. Recommenddaton:: This step correct and should be kept
Ressoning step
step cocnectly convens the fractions the skeia of yam used by Marih and her grandma into yards.
Resscning step
stop logically follows from the presicus step,
involves adding together the quanities of yam used Mariah and her grandmss, which the previsus step. This step beneficial to correct solution it calculates the tocal amoure of yara used, which as the
have been com ested into the sume objective of the problem. Advice: None. Recommendation: This step is correct and should be kept as is. Renioning stop (repeated). This step a regetition of the flrst step, but with the colculations complesed. It a logical inference of the problem statement and beneticial the correct solution. However, should solution, Advioe: Remove repested step from the reasoning clain, Recommendation This step is conrect but rodundant, and should be removed from the reasoning chain.
repeased the reasoning chain does not add information contribtc the progression
Confidence score: 1.0
Experience oblaimed liuration 2
SARAGUGe The 2-th Resorninng Chain with Comments #tRanace
Below reasoning chein containing ressoning steps presented onder:
Step 1: Calealate the amount of yarn Marish and her grandma used segurately by mulliplying the fraction of the skein they used by the total yards in skein.. Evalunte Score: L.
Step Hint, we need calculase the total yands in skein, Mirish used 1/4 364 yands of yam
of yara Mariah and her grandma used seporately, do this,
multiply the fraction of skein they used grandma usad 1/2 564 yunls of yom. Evalunt Soore: 1.0
Step I: First, we ueed to calculize the amouut of yara Mariah and her grandma used separately, To do this, we eaa multiply the fraction of the skein they used by the lotal yards in skein. So, Marish used 1/4 364 yorls of yam and her grandma used 1/2 a 364 yinls of yam. Fvalunte Soom: 1.0
Step After calcalating the
yam Mariah
grandma used separtely. 364 yards) to get total amount of yam usad.. Evaiuate Scare:
add these
tagether find total amount of yam they
So, we add Marish's yam (1/4 364 yards)
grandina's is yarn
Step I: First, we need to calealire the amount of yar Marish and her grandms msd sejuratlly To do this, we can mulliply the fraction of the skein they usad by the total yards a skein, So, Murish used 1/4 " 364 yards of yam and her grandma used 1/2 i 364 yands of yum. Evalunte Semre: 1.0
The masooing chain repetitive and contains a rodumdancy error, with Step being repeated throe times, Howevrr the steps themselves ore logieallly corcect and lead to the correct solution of the problem.
Anilysis Report:
Reasoning stop I. The linst step logically cornect. It cornectly identifies the need to colculate the amount of yamn Marish and her gaandma used separstely by they by total yards
This stop beneficial the solution forms the basis calcallaing the tocal anount yana used. Advice; None Recommendation: Approved
multippyyngg the fraction the
sepurately, is logical Reasoning step 2. The sccond step is legical inference from the find step. After finding out how much yarn Marish and her grandmu used sead to add these amouees together find the lotal amount of yum nsed. This step heneficial to the coerect solution it allows for the colculation the total smount yarn used. Advice None Recemmendaaion: Approsed
Frror report: The repetitiion of Step ihree times unncoesary and does not contribute the solution. should be recised avoid redundinny. Advice: Fliminste the repetttion of Step I. The rensoning chain should only contain unique steps that contribute to the solition of the problemm
Confidence scone: 0.9
Experience obiaimed in Iteration 3
Aaaooqe The 3-th Reasening Chuin with Commenis 4saasau
Below reasoning shiin containing ressoning steps presented onler
Step I: First, we need to calculiic the total amount of yam Marish and her grandma used in terms of the skein, Marish used 1/ af skein and her grandma used 1/2 a skein. To find the total amount of skoin they used, we neal sdd 1/4 and 1/2., Foahute Score: 1.0 Step 2: After finding the lotal amount skein they used, convert to find the lotal yanls (273) of yam they used.. Evaluste Soom: 1.0
yands. know I skein is equal 364 yards. So, mulkiply the skein used by 364
Anulysis Repurt: The masonnng chain can curreelyy complete the task and reach the target. The tack to find out how many yards skeins used by Mariah
Mariah and her grandms grandma. then
used aloegother. The reasoning chain calculates total skeins yam by adding the fractions
converts this total skein amount into yards, which is the final answer required.
Reasoning siep The fins step is logical inference as il corretlyy idenlifies that the first step to solving the problem is to add the fractions of the skeins used by Mariih and her gredmna This step benelicial to the cornect solution it sets the stage for the convensoon of skeins to yards the next step. No erress are found this step. Advice: No advice needed as this step is correctly ressened. Recommendation recommend this step as it cornectly identifies the need to calculate the lotal skeins used linst.
Reasoning step 2: The second step is logical inference of the first step. It correctly ideerifiee that the total skeins used noeds to be converted into yandis to answer the question. This this step is correctly reasomed. Recommeniation: recommend this step comeecly identifies need to convert total skeins used into yands.
is beneficial to the correct solution leads directly the final answer. No errors are found this Advice: No advice needed
Confidence score: 1.0
Experience obtained Heraaionn 6
*hnrocse The thth Reasoning Chain with C Comments ennneetw
Below a reasoning shain comtaining remsoning steps presented in onder:
Step Calculate how many yards yurn Mariah by multiplyng the yurds a skein by the fraction used, which is Similarly, calculate many yards of yarn her gradma used by makiplying the total yurds a skein by the fraction ahe used, which is 1/2. Mariah used: 1/4 364 = yands, Grandmaa used: 1/2 364 182 yards. Evaluate Score: 1.0
Step 2: Step 2: Add the
of yam Marish used and the amount her grandma used find total amount of yarn used. Tocal yarn used 273 yunds. Evalunte
Score:
Stap 3: State the total amount of yam used by Marish and her grandma, Mariah and her z grandma used total of 273 yards of yum.. Evalunte Score: 1.0
Analysis Repact The reasoning chain logically sound and cocrectly compleses the task. The reasoning chain starts calculating how yarn Mariah and her grandma used individually, then these amounts together to the total amouns yarn used, finally states total amouns.
Reasoning step I. The first step is logical as it directly applies the information given in the problem, and it beneficial to the correct solution as peovides the individual amounts of yarn medd Recommentarion: The step is correct and should be kept.
Ressoning
used find total amoune. This stop beneficial the correct solution as it directly leads the answer. Reco gendation:: step correct and should kept.
The second step logical inforence from previous step. as combines the individual amounts
Reasoning step 3. The third step is to state the total amount of yarn used. Recommestation: The step is correct and should be kept.
Confidence score: 1.0


Reviews:
[{"review_id": "1lDRac9ePM", "reviewer": "Reviewer_x4s4", "summary": "The paper proposes a new framework Boosting of Thoughts (BoT) with large language models (LLMs) for task-specific prompting. It provides how to construct prompts and use the trial-and-error reasoning approach to interact with the LLM to generate the final responses. The experiments show the effectiveness of the proposed method.", "questions": "- In Section 3.2, it is not quite clear how to calculate the weights for the weighted binary tree.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- Prompt engineering is a non-trivial task, and crafting effective prompts may require specialized training for human experts. The paper introduces an innovative framework for iterative prompting, leveraging LLM's feedback on its own reasoning, thereby reducing the need for human prompt engineering.\n\n- Addressing complex problems is crucial in LLM applications. This approach effectively demonstrates the power of prompt engineering and expands the capabilities of LLMs without the need for retraining or fine-tuning. Experiments conducted on multiple datasets show competitive performance compared to other prompting approaches.", "weaknesses": "- I agree that prompt engineering is crucial for LLM applications. However, it's worth noting that prompt engineering is often model-dependent, and the techniques may evolve as LLM capabilities improve. This may not offer long-term guidance for research unless it uncovers fundamental insights. This distinction is critical in differentiating academic research from practical production. Therefore, while the paper does offer valuable techniques for prompting the model and achieving good results on evaluation sets, it lacks in-depth discussion of the underlying reasons. This makes the paper better suited for application-oriented conferences rather than ICLR.\n\n- LLMs can be unstable and prone to hallucination, which could result in bad or incorrect feedback when using the Boosting of Thoughts (BoT) iterative prompting framework. Is there analysis on the impact of \"bad\" LLM feedback? Further, as the iterative produces are automatic, spurious feedback could get amplified over iterations. Some discuss may be necessary.\n\n-  Details are lacking on key components like aggregation strategies and generating edge weights for trees. More analysis or ablation studies are also helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZNU7d8MOkM", "reviewer": "Reviewer_dFck", "summary": "The paper presents an extension of the Chain of Thought (CoT) and Tree of Thoughts (ToT) method, named Boosting of Thoughts (BoT). BoT refines the problem-solving process in large language models (LLMs). BoT harnesses error analysis to improve the LLM's problem-solving accuracy iteratively. The \"Boosting of Thoughts\" (BoT) procedure is a two-step process that first generates a diversity of reasoning paths from a Large Language Model (LLM) in the form of a weighted binary tree, enhancing problem-solving by creating a hierarchy of potential solutions. Then, it employs a novel aggregation strategy that iteratively refines and combines these paths. Through best-first and greedy aggregations, BoT selects and optimizes the most promising chain of thought, using iterative feedback to progressively improve the LLM's performance on complex problem-solving tasks. The paper reports improved performance on complex mathematical problems when tested with GPT-4 and LLAMA2, compared to CoT and ToT.", "questions": "Q1: In the prompt, I wonder whether the “error input” are included, or only the “experience” is included? From figure 1, I only see “error report” like “step 1 is not closer to 24”, no “error input” like what is step 1, 2, 3. How the LLM know what step 1 mean, and how can LLM learn from error, if LLM does not know specific input?\nQ2: How about you consider the entire (input, error analysis) as an In-context Learning example? Then the entire method is similar to CoT, meaning that you can manually construct an exemplar consisting of (input, error analysis) pair. Then use the CoT idea to follow the strategy to generate analysis and think about the correct answer.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. This is an innovative extension of the Chain-of-Thought (CoT) and Tree-of-Thought (ToT) methods. Compared to CoT and ToT, the author adopts the idea on leveraging error analysis to refine the LLM. This can be a limitation of CoT and ToT, as they do not conduct error analysis and more importantly, learn from errors. The motivation is intuitive and clear.\n\n2. Unlike ToT, which expands multiple reasoning tree branches, the BoT method iteratively refines a single line of thought. This focus on iteration rather than expansion allows for a more concentrated and efficient improvement of the reasoning path. The computation moves from exploring the tree into learning from erroneous trials. \n\n3. The Boosting of Thoughts (BoT) concept shows a clear advancement in problem-solving methodologies within large language models. It effectively combines generation and evaluation steps to progressively enhance reasoning, demonstrating a significant leap in the model's ability to handle complex tasks. \n\n4. The experiments are clear, the results are effective. And all experiments are classic experiments from CoT and ToT, so it is clear to compare BoT’s performance over CoT and ToT.", "weaknesses": "The mauscript need polished in their figures' presentation, e.g., the authors need give more detailed examples in Fig1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Cw9UmirZBD", "reviewer": "Reviewer_VMbH", "summary": "The paper proposes a Boosting of Thoughts (BoT) framework, which aims to achieve the boosting mechanism that embraces aggregation and experience, thereby enabling the progressive refinement of unreliable reasoning steps (weak thoughts) by learning from errors to solve various problems, eventually.", "questions": "Please review the weakness section", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper reiterates their proposition that a simple prompt can be enhanced by gradually accumulating error analysis on its generated thoughts to address complex tasks.  The authors present a novel framework, the Boosting of Thoughts (BoT), to implement such progressive prompt enhancement for effective thought generation with an experience-driven iteration process. Iteratively exploring and self-evaluating the generated simplistic trees of thoughts enables a simple initial prompt to be gradually enhanced by an ensemble of trial-and-error reasoning experiences, resulting in accurate solutions. \nThis work seems like a quite comprehensive investigation with well-structured and easy to read sections.", "weaknesses": "The paper is based on the motivation that starting with a simple prompt without human annotations for LLMs, BoT may get weak thoughts. However, with aggregation, BoT is capable of deriving a more logical and effective thought chain from them, thereby guiding the subsequent refinement.\n\nCould the authors expand on this statement \"Experience consistently leads to thought revision, but too much can have the opposite effect.\"? If one is looking to recreate the study, are there any guidelines or steps one could adopt to as where should be the stopping point?\n\nVery interesting findings, however Experimental results reported are limited. The authors evaluated LLM models only on a single testing procedure. However, the analysis doesn't seem concrete due to the smaller sample set considered and it would truly be insightful if the analysis was done on a larger dataset to infer results.\nFurther experiments should be performed using statistical metrics, and statistical distribution of the results should be extracted. These outcomes help better support the conclusions' claims.\nThe paper would be greatly strengthened if the proposed algorithm would outperform state-of-the-art methods", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "w7bvJ5iRWP", "reviewer": "Reviewer_pKnK", "summary": "This paper proposes a new framework called Boosting of Thoughts (BoT) for complex problem solving with large language models. BoT aims to iteratively explore many possible trees of thoughts and learn from ineffective thoughts/errors to progressively refine the prompt and elicit effective reasoning from LLMs. It aggregates the best reasoning chains from the trees and analyzes them with the LLM to gain experience on errors and revisions. Experiments on mathematical reasoning show BoT matches or exceeds previous SOTA approaches without needing human annotations.", "questions": "1. As for the statement on page 3, 'Our paper embraces ToT due to its high ability and leaves GoT and BoT for future work,' is 'BoT' a typo error here? Or you mean combining BoT method with GoT? Regardless, I believe that including GoT in the comparison would make this work more interesting and informative.\n2. In the 'Competitors' paragraph in experiments, could you clarify how many reasoning chains are sampled for Complex-CoT and PHP respectively?\n3. The study conducts experiments based on GPT-4, which can lead to substantially high experimentation costs. Have the authors considered or utilized more cost-effective options like GPT-3.5-turbo? I'm aware of the recent variability in performance of this model. However, if there are experimental results showing that GPT-3.5 combined with BoT can outperform GPT-4 with CoT/CoT-SC, it would render the study's findings more convincing.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper proposes a novel framework, Boosting of Thoughts (BoT), that utilizes an iterative trial-and-error approach to refine prompting and elicit complex reasoning from LLMs. The key idea of learning from errors/ineffective thoughts is creative and mimics human problem-solving.\n2. Authors involve interesting techniques like weighted binary trees and heterogeneous growth strategies to generate diverse, shallow thought structures from a simple prompt.\n3. Evaluations on mathematical reasoning benchmarks demonstrate effectiveness of BoT. It matches or exceeds state-of-the-art methods without needing human annotated prompts. Also, the authors conduct ablation studies to further explain the mechanisms.", "weaknesses": "1. Although this article proposes several practical strategies, its reasoning framework remains inherently reliant on the Tree-of-thoughts model, thereby limiting its novelty. BoT's structure is restricted to binary trees. Expanding to more complex graph structures will further improve reasoning but is not explored.\n2. For analysis, the prompts used to seed BoT could introduce biases and variances. More evaluations on OOD data would be useful to assess the robustness and generalizability of the improvements.\n3. The evaluations are mainly limited to mathematical reasoning. For generality, testing BoT's performance on other domains like commonsense reasoning or symbolic reasoning is needed.\n4. In the 'Competitors' paragraph, authors mentioned incorporating CoT-SC and Complex CoT as  baselines, yet CoT-SC is not shown in the 'mathematical reasoning' part. I hold the view that comparing the proposed method with prevailing baselines like SC(5) or SC(10) will offer a more direct reflection of BoT's efficacy. If it can outperform Complexity-based SC with fewer resources, it would make the work more solid.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Fv3pXWd41e", "reviewer": "Reviewer_kjxP", "summary": "The paper looks at optimizing prompting for GPT-4 and Llama2 for solving mathematical problems. They provide an iterative strategy to prompting models for complex problems. The key challenges are SVAMP (1000 tasks), GSM8K (8500 tasks), AQUA (100 000 tasks), and MATH (12 500 tasks). The BoT, especially when enhanced with CoT, outperforms alternative methods.", "questions": "Do I understand correctly that T 10 was maximum 10 prompts and M 15 consisted of 15 instances that generated binary trees that you then averaged over?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "When we reach the limits by simply increasing language models, optimal interaction becomes increasingly interesting. Exploring new ways of pushing the models to do more complex tasks can get more value out of existing LLMs and is highly relevant. \n\nThe paper provides code that is easy-to-read (although a Readme would be a nice addition).\n\nThe method shows that BoT and CoT perform above the comparisons.", "weaknesses": "The use of the term 'boosting' in the context of refining 'weak thoughts' introduces some ambiguity. In traditional machine learning, boosting involves the iterative enhancement of quantifiably weak learners. In the BoT framework, the concept of a 'weak thought' is more abstract, and its \"weakness\" is not as straightforward to measure. This led me to perceive the process more as a 'pruning of weak thoughts' rather than 'boosting' in the conventional sense. It would be beneficial for the paper to clarify how the model aggregates and refines these thoughts in the tree structure, and how the \"weakness\" of a thought is determined and improved upon.\n\nI think the paper comes across unnecessarily complicated, compared to the code the text is hard to fully grasp. The figures all depict Game of 24, adding examples from both a successful and a failed example of BoT for the other tasks would be beneficial.\n\nFor complete reproducibility and clarity, it would be beneficial to provide the full codebase, including modules like 'llmpebase’s residual_tree_of_thoughts', which is referenced several times but not included.\n\nThe title suggests a general problem-solving approach using Large Language Models. However, the content is specifically focused on mathematical problems. It might be beneficial to make the domain-specific nature of the research clearer in the title or early in the abstract to set accurate expectations for readers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)