Self-Evaluation Guided Beam Search for Reasoning
Authors: Yuxi Xie
Kenji Kawaguchi
Yiran Zhao
Xu Zhao
Min-Yen Kan
Junxian He
Qizhe Xie
Venue: NeurIPS 2023 poster (2023)
Keywords: Large Language Models
Multistep Reasoning
Stochastic Beam Search
LLM Self-Evaluation
TL;DR: We propose a decoding approach to enhance LLM reasoning via self-evaluation guided stepwise beam search.

Abstract: Breaking down a problem into intermediate steps has demonstrated impressive performance in Large Language Model (LLM) reasoning. However, the growth of the reasoning chain introduces uncertainty and error accumulation, making it challenging to elicit accurate final results. To tackle this challenge of uncertainty in multi-step reasoning, we introduce a stepwise self-evaluation mechanism to guide and calibrate the reasoning process of LLMs. We propose a decoding algorithm integrating the self-evaluation guidance via stochastic beam search. The self-evaluation guidance serves as a better-calibrated automatic criterion, facilitating an efficient search in the reasoning space and resulting in superior prediction quality. Stochastic beam search balances exploitation and exploration of the search space with temperature-controlled randomness. Our approach surpasses the corresponding Codex-backboned baselines in few-shot accuracy by $6.34$%, $9.56$%, and $5.46$% on the GSM8K, AQuA, and StrategyQA benchmarks, respectively. Experiment results with Llama-2 on arithmetic reasoning demonstrate the efficiency of our method in outperforming the baseline methods with comparable computational budgets. Further analysis in multi-step reasoning finds our self-evaluation guidance pinpoints logic failures and leads to higher consistency and robustness. Our code is publicly available at [https://guideddecoding.github.io/](https://guideddecoding.github.io/).

Self-Evaluation Guided Beam Search for Reasoning
Yuxi Xie!* Kenji Kawaguchi'
Yiran Zhao' James Xu Zhao'
Min-Yen Kan Junxian He
Michael Qizhe Xie
National University of Singapore The Hong Kong University of Science and Technology
Abstract
Breaking down a problem into intermediate steps has demonstrated impressive performance in Large Language Model (LLM) reasoning. However, the growth of the reasoning chain introduces uncertainty and error accumulation, making it challenging to elicit accurate final results. To tackle this challenge of uncertainty in multi-step reasoning, we introduce a stepwise self-evaluation mechanism to guide and calibrate the reasoning process of LLMs. We propose decoding algorithm integrating the self-evaluation guidance via stochastic beam search. The self- evaluation guidance serves as better-calibrated automatic criterion, facilitating efficient search in the reasoning space and resulting in superior prediction quality. Stochastic beam search balances exploitation and exploration of the search space with temperatture-controlled randomness. Our approach surpasses the correspond- baselines in few-shot accuracy by 6.34%, 9.56%, and 5.46% on the GSM8K, AQuA, and Strategy QA benchmarks, respectively. Experiment results with Llama-2 on arithmetic reasoning demonstrate the efficiency of our method in outperforming the baseline methods with comparable computational budgets. Further analysis multi-step reasoning finds our self-evaluation guidance pinpoints logic failures and leads to higher consistency and robustness. Our code is publicly available at http::/guideddeeooding github.io/.
ing
Introduction
The remarkable empirical achievements of Large Language Models (LLMs) have recently ushered in a new era machine reasoning through few-shot prompting techniques (Brown et al., 2020; Chowdhery et al., 2022; Touvron et al., 2023a; OpenAI, 2023). In particular, breaking down problem into intermediate stages, or a reasoning chain, can significantly improve model performance on reasoning tasks (Cobbe et al., 2021). Various prompting approaches have been proposed define these chains, such as scratchpads (Nye et al., 2021), chain-of-thoughh thouth (CoT) (Wei et al., 2022b), least-to-most (Zhou al., 2023), and program-aided language models (PAL) (Gao et al., 2023; Chen et al., 2022). However, as the complexity and length of reasoning chains increase with the difficulty of tasks, LLMs struggle with errors and imperfections that accumulate across multiple intermediate steps (Wu et al., 2016; Guo et al., 2018; Chen et al., 2022). Furthermore, the growing number of steps leads to an exponential growth in the search space for reasoning, making it exceedingly difficult to obtain accurate final outcomes.
Confronted with the challenges of uncertainty in multi-step chaining, several previous studies have worked on different aspects to alleviate the impact of reasoning errors. For instance, Wang et al. (2023) introduce self-consistency as method to determine the final answer through majority voting using multiple sampled reasoning paths, while Li et al. (2022) investigate various prompts to diversify the sampling outcomes. Gao et al. (2023) and Chen et al. (2022) utilize Python programs to
"Correspondence to: Yuxi Xie (xieyuxi edu).. Equal advising. Ordering is determined by dice rolling.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Multi-stop Reasoning Chain
Question
Basic Greedy Decoding
marllyn copllss 88000
ralio - 10
Marlyn's record sold times many copies as Herak's. copiee combined, how many coples did
answer marlly capres ! ratte
marlyy popies 86000
copies mar = total 100
Answer: 3,500
Intal sold 88000
6i0 = 10
answer total sold // marlyn harald rabio
marilyn_oopher poples 10
meriyn harald ratio
answer total sold/ (marllyn harald rallo
Multi-sepp Reasoning Chain
Self-Evaluation Guided Stochastic Beam Search
marlyn harald raloo
answar = total sold (marlyn harald rato +
Generation
LLEX
Evalustion
Answer 8,000
Figure I: Self-Evaluation can calibrate the decoding direction in multi-step reasoning. We illustrate method in the form of stepwise stochastic beam search with the beam size equal to 1. The scale of the self-evaluation score is visualized in the colormap. We adopt Program-Aided Language models (PAL) reasoning (Gao et al., 2023; Chen et al., 2022) for this math word problem.
achieve higher accuracy in mathematical computations. While these approaches have contributed to significant performance improvements in reasoning, the process of generating reasoning chains has been parameterized as a standard autoregressive process and intrinsically faces the challenge of sampling within exponentially large search space.
Motivated by this challenge, we employ LLM self-evaluation (Kadavath et al., 2022) as a better- calibrated criterion to automatically guide the search in the reasoning space, drawing inspiration from prior works on utilizing LLMS for self-evaluation (Rae al., 2021; Paul et al., 2023; Madaan et al., 2023; Shinn al., 2023). We integrate the self-evaluation guidance for reasoning in a stepwise and generalizable manner. Specifically, we formulate the reasoning chain generation as a decoding process consisting of multiple intermediate steps. Unlike traditional text decoding where each step produces a single token, we consider each decoding step as a reasoning logic composed of sequence of tokens. This framework enables us to employ beam search (Jurafsky and Martin, 2009; Graves, 2012) decoding tailored for intermediate steps and guide the beam searching process by controlling the error of each reasoning step to prevent potential error accumulation throughout the chaining. Figure illustrates an example of decoding a chain of program-aided reasoning steps. Furthermore, incorporate cemperature-controlll et al., 2021) into the traditional (deterministic) beam search to balance the quality-divens in searching for better reasoning chains. Our approach has resulted in respectable improvements across various arithmetic, symbolic, and commonsense reasoning tasks. For instance, by guiding the reasoning decoding process of the Codex model (Chen et al., 2021), we achieve accuracies of 85.5%, 64.2%, and 77. 77.2% on the GSM8K, AQuA, and StrategyQA benchmarks, compared to the vanilla reasoning-enhanee enhanced Codex performance of 80.4%, 58.6%, and 73.2%. respectively. Our further analysis on Llama-2 (Touvron et al., 2023b) demonstrates the efficiency of our method in surpassing the seff-consistency baseline under equivalent computational budgets.
randomness (Ackley et al., 1985; Kool al., 2019; Meister
trade-off
2 Self-Evaluation Guided Stochastic Beam Search
Considering the input prompt and question Q represented as æ, we formulate the answer distribution P(a æ) by decomposing it as reasoning chain generation process P(R | x)) and an answer generation process P(a| R, x):
P(a x) = ER-P(R\s)P(aa R,x),
(1)
where R is the intermediate reasoning chain variable that is typically text sequence. P(a R Lafa) max ([AL.Tj where A execute(I)) represents the set of predicted answer(s) interpreted from R. and 1 A is the indicator function of the subset A. In practice, |A| 2 0 can be or larger than when the reasoning R. returns no valid answer or produces more than possible answers. respectively.

---

Timestpp2
Timoopp
Prompting Framework
Reasoning Chain
Predicted Final Answer
Multi-step Reasoning
marllyn total, solld if marilyn haaarlyy_haraad_.ooo
Self-Eval (lmr))
# la the above step rensoning:
Puoti
Stochastic Beam Search
# (A) Correct
* (B) Incorrect
# The above step of reasoning Is:
Auttt)
[B), bacause Marilyn sold 10 as many ...
Kept
S Paths
Seff-Eval
(0P
Decoding at Timestep
Our framework of self-evaluation guided stochastic beam search for multi-step reasoning. The schema of the decoding process is on the left, where we keep k = 2 candidates at each timestep, with the detailed illustration of timestep t at the bottom. Here "Gen" and "Self-Eval" represent the generation and evaluation LLMs, respectively. The corresponding prompt formulations on the right, where the questions Q. reasoning steps R, and evaluation scripts are highlighted in orange, green, and yellow, respectively. Steps in light green (e.g., s²) are for models to generate or evaluate at the current timestep. Specifically, we follow Kadavath et al. (2022) to prompt the L.M evaluation by answering the multiple-choice question, i.e., the lines starting with #
Figure 2:
provided
Prior research has modeled the reasoning chain generation P(R] x)) by prompting LLMs to explicitly elaborate on the required intermediate steps R. Through setting different prompting schemes, the reasoning process P(R z) can be modeled as thhought free-text reasoning (Kojima et al., 2022; Wei et al., 2022b), a two-stage question decomposition and answering pipeline (Zhou et al., 2023), program mrddr reasoning generate python program (Gao et al., 2023; Chen et al., 2022). While effective, previous work mostly uses a single sample of R from the LLMs to approximate the expectation in Eq. 1 the generated reasoning chain is often unreliable and causes incorrect answers. To mitigate this issue, Wang et al. (2023) conduct majority voting to approximate the expectation via sampling and aggregating multiple reasoning chains. Li et al. (2022) take a further step to diversify the sampling and calibrate P(R| x) with task-specific fine-tuned verifier. Another line of work focuses on improving P(a Rt,z) instead. For example. Gao al. (2023) and Chen al. (2022) employ Python programs for more accurate calculations in math word problems.
In this work, focus improving P(R| z)) to enhance the consistency of the sampled reasoning chains. To this end, we propose to explicitly break down the reasoning process into multiple steps, as shown in Figure 2, where each step yields semantically integrated sequence of tokens, representing a single step within the overall reasoning chain. From this perspective, we can approach the task of enhancing P(R æ)) decoding problem over the reasoning chains. Considering the exponentially large search space and the potential unreliability of LLM M-M--rrddued chains in reasoning, we propose a constrained stochastic beam search decoding approach improve the reasoning step by step and obtain high-quality reasoning with a limited number of samples. We detail our approach next.
2.1 Multi-step Reasoning via Stochastic Beam Search
In multi-step reasoning, reasoning chain of T steps is sequentially generated through several timesteps as At - [s- s². .... s = 31: where sf represents a sequence of tokens as the 1-th step. Formally, the reasoning generation process P(R] x)) can be factorized in an autoregressive manner:
P(R I.T x))
II P(s |x, (2,,sit-)))
which resembles the typical token-level autoregressive distribution of language models. Stepwise reasoning allows us to formulate the process as a step-by-step decoding problem, where we can utilize widely-used strategies such as beam search for the generation. Different from the typical text
3

---

decoding process where each step consists of single token, here we view a sequence of reasoning tokens as single step. One of the most severe issues in LLM-based reasoning the potential unreliability and inaccuracy of each reasoning step generated by the model. Furthermore, errors from individual steps may accumulate throughout the reasoning chain, exacerbating the problem. To address the issue, we define a constraint function C(s", s sl:t-1) E [0, 1] within each reasoning step² that outputs the LLM confidence in the correctness of the reasoning sequence of based on the previous context gl:t-1, Then, we present constrained decoding approach that combines the language model probability and the correctness confidence as a new decoding objective function E E(s1:"):
8(st:T)=
= II Ping (s' x, st
where Pr.Mg is the language model distribution 4. À E [o. 1] is a weight hyperparameter to balance the LM score and the confidence score. We will detail the design of C(s") ) in Section 2.2. Eq follows an autoregressive factorization form, and thus traditional token-level decoding methods such as beam search can be applied here on the chain level. As it is desirable to obtain high-quality reasoning chains with limited samples that are scored high by E(sl:T), it is natural to utilize greedy or beam search decoding to approximate the reasoning sequences that maximize E(sl:T).
Additionally, multiple diverse reasoning chains could be aggregated to further improve the final accuracy, suggested by Eq 1 and empirically confirmed by self-consistengs reasoning (Wang et al., 2023). To this end, we propose a variant of stochastic beam search (Kool et al., 2019; Meister et al., 2021) to strike tradeoff between exploration and exploitation. Concretely, for beam size k, each reasoning step we draw n samples of s following PLM, (s* x, 1::-1) for each beam, and we end up with nk chain hypotheses of lit to form the candidate set S, then we perform beam pruning through sampling- we sample & reasoning beams without replacement, rather than finding the arg max k, following distribution defined by the accumulated score:
P Poeam (s (slit) exp(E(s"t)/T), glit E
(4)
where the temperature is a hyperparameter to control the randomness in stochastic beam search; when r + 0, stochastic beam search becomes the vanilla beam search algorithm. The reasoning beams 1i can be sampled efficiently since |S| = nk finite set. To enable fine-grained control of sampling randomness in decoding, we also introduce hyperparameter E [0, 1] so that 7 can decay step by step as T + aT. By annealing 7 with a, we can mitigate the error accumulation due to aggregated randomness throughout chaining. discussed in Section 3.4.
By incorporating controllable randomness, we not only achieve a more reliable single reasoning chain generation by setting randomness to be small, but also leverage multiple diverse reasoning chains with larger variance. Next, we introduce our constraint function C(st, ((st,slit glit-1) that utilizes a self-evaluation scheme to improve the consistency of each reasoning step.
2.2 Self-Evaluation as Correctness Control
Inspired by the recent success of self-evaluation (Kadavath et al., 2022; Shinn et al., 2023; Madaan et al., 2023; Paul et al., 2023), a scheme to prompt LLMS to evaluate their own generation, we use LLMs to judge the correctness of s' based s 1 Specifically, the evaluation and generation models use the same backend LLM with different prompts, which consist of few-shot exemplars. We follow previous works of CoT (Wei et al., 2022b) or PAL (Gao al., 2023) formulate the generation prompts. To construct the in-context exemplars prompt for the self-evaluation LLM LMc, we provide stepwise evaluation examples (as question answering with rationales) in each instance. Inspired by Kadavath et al. (2022), we design prompte in the form of multiple-choie questioning (as shown in Figure 2) to better calibrate the model predictions, where we adopt the token-level probability of option A to represent the correctness score as:
C(*') PLM (A prompt Q 2it)
(5)
FFor ease of notation, we will use C(s²) throughout the paper when there is no confusion.
*We will denote LM generation probability by P throughout the paper for simplification.
"In Appendix I. we justify the approximation error rate of Eq 4, which computes normalized probability on the subset S instead of on the entire set.

---

3 Experiments
3.1 Setup
We present and analyze the results of our self-evaluation guided beam search with different LLM backbones on various reasoning benchmarks. Implementation details including prompt examples and hyperparameter setup can be found in Appendix A.3.
Benchmarks. We evaluate the effectiveness of our approach across three types of reasoning tasks: (1) Arithmetic Reasoning on five math word problem benchmarks, including GSM8K (Cobbe et al., 2021) on math word problems, AQuA (Ling et al., 2017) on algebraic word problems, SVAMP (Patel al., 2021) on structure variations of math word problems, ASDiv (Miao al., 2020) on diverse math word problems, and TabMWP (Lu et al., 2023) on tabular math word problems; (2) Symbolic Reasoning on BIG-Bench (Srivastava et al., 2022), which involves Date Understanding of context- based date inferring and Object Counting of enumerating and counting objects of different types; (3) Commonsense Reasoning on three benchmarks, including CommonsenseQA (Talmor et al., 2019) of commonsense questions that require prior world knowledge to answer, Strategy QA (Geva et al., 2021) of questions that require a multi-hop strategy to answer, and Sports Understanding from BIG-Bendi (Srivastava et al., 2022) determine whether sports-related sentence is plausible.
Baselines. We consider two types of baselines: (1) Chain-of-Thoughh (CoT) (Wei et al., 2022b) prompting in free-text reasoning and (2) Program- Aided Language models (PAL) (Ling al., 2017) and Program-off Thought (PoT) (Chen et al., 2022) prompting in program aided reasoning. We also include their self-consistency (Wang et al., 2023) variants for multiple-chain reasoning. For generation, we follow the few-shot exemplars of baselines. For self-evaluation, we manually create set of few-shot exemplars based on the baseline outputs on corresponding training data. We formulate self-evaluation as a task of multiple-choice question answering, following Kadavath et al. (2022). For baselines, we represent the cost as the number of generated tokens. For the cost of our method, we also include the number of additional input tokens in self-evaluation for fair comparison.
Backboned LLMs. We assess our approach on closed- and open-source LLMs using both PAL and CoT prompting. For closed-source LLMs, we choose Codex ccode-davince 002) (Chen et al., 2021) to report and compare the results on all datasets. We use Llama-2 (13B) (Touvron et al., 2023b) as our open-soure LLM conduct cost perfformmne analysis on different datasets.
3.2 Main Results
Arithmetic and Symbolic Reasoning. Table I shows the results for arithmetic and symbolic reasoning. Our method achieves significant performance improvements on most benchmarks in both single- (T = 0) and multiple-chain scenarios, with PAL as the baseline. For arithmetic reasoning, observe absolute increases in accuracy of 5.3%. 8.3%, and 0.7% on GSMSK, AQuA, and SVAMP, respectively. One possible explanation for this discrepancy in improvements is the reduced diversity in L.M generations due to higher confidence in predictions, as evidenced by the relatively high performance on the tasks. This highlights the importance of incorporating controllable randomness into the candidate generations to expand the search space for self-evaluation guided decoding. We further explore the impact of generation diversity by varying the temperature 7 in Section 3.4.
For symbolic reasoning, our approach also leads to consistent performance gains. However, when the baseline itself performs well on the task (e.g., 96.7% on Object Counting), our approach may not yield substantial improvement. This can also be attributed to the constrained accessible search space for self-evaluation guidance refine the generation distribution. This limit suggests the inherent deficiency in our LLM-based prompting method that it becomes increasingly challenging to calibrate the generation direction when the model LMg is confident in its predictions. In other words, the high baseline performance usually indicates lower diversity in the LLM generations even with a large temperature 7, resulting in limited accessible search space for the model to find better solution.
Commonsense Reasoning, Table 2 compares methods using CoT prompting in commonsense reasoning. Our approach shows consistent performance improvements across several tasks. For example, on StrategyQA, achieve accuracy of 77.2% compared with 73.2% of the baseline.
5

---

Table Result comparison (aceuracy %) on arithmetic and symbolic reasoning tasks. The best result is in bold and the lowest cost is in green. We report methods all with Codex backbone for a fair comparison. Similar to Huang apply weights samples in self-consistency (SC). Other fine-tuning methods include reward-based supervision (Uesato al., 2022) and content-specific training (Lewkowyez al., 2022). We also report the number of tokens (# Tokens) on GSM8K compare the costs of different methods.
(2022), Diverse (Li et al., 2022) fine-tune task-specific verifiers to
Arithmetic
Symbolic
Approach
GSM8K
# Tokens
AQuA
SVAMP
ASDiv
TabMWP
DATE
OBJECT
single reasoning chain
CoT
65.6
0.2k
45.3
74.8
76.9
65.2
64.8
73.0
PoT
71.6
54.1
85.2
73.2
PAL
72.0
0.3k
79.4
79.6
76.2
96.7
Ours-PAL
80.2
27.7k
55.9
89.6
84.9
79.1
78.6
96.8
multiple reasoning chains
COT, SC
78.0
5.3k
52.0
86.8
75.4
CoT, Diverse
82.3
87.0
88.7
POT, SC
80.0
58.6
89.1
81.8
PAL. SC
80.4
7.4k
Ours-PAL
85.5
550.0k
64.2
90.3
85.8
80.9
Table 2: Result comparison (accuracy %) commonsense reasoning tasks, with Codex backbone. Here we only report results in the single reasoning chain scenario following Wei et al. (2022b). We report # Tokens on StrategyQA for cost comparison.
Approach
StrategyQA
Tokens
CommonsenseQA
Sports
CoT
0.06k
77.9
Ours-CoT
77.2
11.6k
78.6
98.4
Human
87.0
88.9
Likewise, the performance of our approach is constrained by the low diversity of LLM generations on Sporting Understanding as we observe on Object Counting in symbolic reasoning.
Computational Cost Overhead. Despite the fact that our approach achieves significant improve- ment various benchmarks, observe an overhead of computational cost compared with the corresponding baselines. For example, the single-chain version our approach using PAL costs about 3 times more than the self-consistence baseline on GSMSK. As detailed in Appendix A.3, this due to a relatively large hyperparameter - the number of rollouts per beam n which we set as 16 for better performance. To strike a balance between performance and cost and present complete and conduct cost cost-performance analysis on our approach Scction 3.3.
picture, we adopt
3.3 Cost Analysis
Table 3 compares the baseline and our approach under comparable computational budgets (measured in Tokens). Our method consistently outperforms self-consistency the arithmetic reasoning tasks even when benchmarked for relatively less computational cost. For example, we achieve 46.1% on GSM8K with a cost of 12.6k tokens, compared with the accuracy of 41.8% of self-consistency which costs 13.9% tokens. Figure 4 further illustrates the cost-efficiency of our approach on GSM8K using different prompting methods under various levels of costs. Our approach significantly outperforms the corresponding equal-cost baseline especially when the computational budget increases, indicating the improvement in the performance upper bound brought by our method.
However, our approach lags behind the CoT baseline on commonsense reasoning. This implies the limitation of our method when applied to shorter reasoning chains, i.e., decreasing the number

---

Table 3: Cost (# Tokens) and result (accuracy %) comparison arithmetic and commonsense reasoning tasks. We base our experiments on Llama-2 (13B) since Codex not available. We show the results of the baseline and our method both in the multiple-chain scenario for a fair comparison. Here we use PAL and CoT prompting for arithmetic and commonsense reasoning, respectively.
Arithmetic (PAL)
Commonsense (CoT) Commonsense
Approach
GSMSK
AQuA
SVAMP
ASDiv
TabMWP
Strategy
Baseline Tokens
41.8
30.7
71.2
66.2
43.7
71.0
74.4
13.9k
6.6k
5.9k
2.7k
1.9k
2.7k
1.2k
Ours
46.1
31.5
74.6
67.7
49.6
70.6
74.0
Tokens
12.6k
6.0k
5.0k
2.5k:
1.2k
2.6k
1.2k
45.2
44.9
43
430
Accuracy
42
42
Accuracy
42
42.9
40.5
40.6
40
38,9
PAL-SC
38
17/
CoT-SC
Ours- (single)
Ours-CoT (single)
364
36
33
Ours- (multiple)
Curs-CoT (multiple)
+54.5
2000
4000
10000 12000 14000 Cost (# Tokens)
6000
8000
2000
4000
8000 Cost (# Tokens)
6000
10000
12000
(a) PAL Prompting Methods on GSM8K
(b) CoT Prompting Methods on GSM8K
Figure 4: Accuracy curves on GSM8K of different methods with the change of the cost. We conduct the performance comparison using both PAL and CoT prompting with Llama-2 (13B) backbone.
overall wrong
0.83
0.88
overall
0.71
0.84
overall
0.76
0.86
correct wrong
1000
0.0
0.2
0.4
0.6
0.8
1.0 0.0
0.2
0.4
0.6
0.5
1.0
0.0
0.2
0.4
0.6
0.8
3.0
generation probability
correctness confidence
score
=i
=
(a) Score distribution of PAL bascline predictions GSM8K.
overall correct
0.63.065 0.65
overall correct
0,75
overall correct
0.66
1000
8.0
0.2
0.4
1.00.0
0.2
0.6
0.8
0.4 score 6 et A
1.0
generation probability
confidence
(b) Score distribution of CoT bascline predictions on StrategyQA.
Figure 5: Distributions the self-evaluation score and its components (i.e., generation confidence P and correctness confidence C) correct/incorrett baseline predictions. We highlight the median scores the positive and negative cases using lines of the same colors respectively.
of intermediate steps weakens the effect of stepwise self-evaluation in beam search in reducing error accumulation. On the other hand. self-consistency can directly improve performance through instance-level aggregation without additional cost for self-evaluation. We analyze how method benefits longer reasoning chains on different tasks in Section 3.4.
3.4 Further Analysis
We now provide detailed analysis of why method achieves significant gains.
Generation and Self-evaluation Calibration. We investigate the distributions of generation confi- dence (i.e., the LM probability P) and conrectness confidence C in our self-evaluation score E. By
7

---

Table Absolute accuracy (in %) increases on instances of different complexity determined by the length of reasoning chains (represented as # Steps).
GSM8K
StrategyQA CoT
# Steps
Ins.
PAL
Ours
AAccu.
# Steps
# Ins.
Ours
AAccu.
437
85.8
91.3
+5.49
637
84.6
84.9
+0.31
E (7. 9]
524
74.8
82.6
+7.82
E
[4,5) 5)
1,301
78.6
79.1
+0.46
2
9
358
72.9
82.6
+9.78
2
351
68.4
71.8
+3.42
(single) PAL (multiple)
42.8
84
80
40-
PAL
Accuracy x
Accuracy
Accuracy
78
38-
7
38.3
82
50.8
Ours PAL (single) Ours-PAL (multiple)
76
Ours-CoT (multiple)
Durs-Co CoT (single)
36
79.1
9 2
74
34
33.4
33.2
78-
71.9
72
4.5
2
0.2
0.5
0.8
1.0
0.5 Sampling temperature T (y- 0.5, 0.5)
0.0
Beam Size (k)
LM temperature y(r- 0.5, 0.5)
(a) effect beam size
(b) effect of generation and sampling diversity
Figure 6: Accuracy curves and distributions of our approach GSM8K with different hyperparameter settings: (a) Changes in performance (Ilama-2 backboned) when the beam size k varies. Methods of the same & have equal computational costs; (b) Accuracy distributions (Codex backboned) with different generation temperature y and sampling temperature (with decay ratio a).
comparing the score distributions for correct and wrong predictions, we aim gain an intuitive understanding of whether these confidence scores are reliable. Figure shows different score dis- tributions on correct and wrong baseline predictions. The difference distribution between the two prediction sets is substantial for arithmetic reasoning, but negligible for commonsense reasoning. Notably, in both instances, correctness confidence more discriminatory than generation confidence.
To achieve a balance between these two confidence scores, we utilize tunable hyperparameter X, setting À 0.5 for all datasets. Nevertheless, varying its value can lead to distinct outcomes. For instance, when setting À to (E C) or 0 (E P), the performance on GSMSK decreases from 80.2% to 74.5% and 77.1%, respectively. This indicates that both scores play crucial role in our final performance. A more comprehensive analysis of À can be found in Appendix A.2.
Reasoning Complexity. We investigate if our approach is more beneficial for instances needing more reasoning steps. Table 4 shows that performance gains (in absolute accuracy % increase) increase as reasoning chains become longer on both GSM8K and StrategyQA. Notably, the improvement on Strategy QA primarily comes from improvements in longer reasoning chains, showcasing the effectiveness of our method in navigating lengthy and intricate reasoning chains.
Hyperparameters in Stochastic Beam Search. We examine the significance of hyperparameters associated with stochastic beam search, including the beam size and the temperatures ry and controlling the generation and sampling diversity, respectively.
Figure shows the trend of performance improvement with the increase of beam size Notably, our beam search approach inherently enables majority voting on the final beam without additional cost, resulting in a more significant performance improvement in the multiple-chain reasoning when the beam size is larger (e.g., 42.8% compared with 35.7% when à 10).
For generation and sampling diversity, is clear that more diversity resulting from higher temperatures generally leads to a decline in performance when only considering single reasoning chain. However, diversity significantly benefits majority voting on multiple reasoning chains 6, This benefit comes
'In this study, we did not explore higher generation temperatures (i... y > 1.0) since this hyperparameter is limited 1.0 in the OpenAl API.

---

[0,] Grace weighs pounds. Alex weighs pounds than times Grace weighs. What are their combined weights in pounds?
[0,1 Mariah and grandma used and 1/2, respeclively, from yards in skein of yern. How many yards of yorn did they use in total? [Ground- Truth o, 273.0
[Ground- Feruun-Trutth-o e, 623.0
iPredikted e 623.0
[Predicted e,1 272.0z |K,, in Python
, in Python
yards_per_ cerss__er_sseiii per_skein
alex_weight grace_wcight
pariih_yand
yards_per__kae per__keinn
answer prace_weight alex_wright
grandra_yards
yards_per_skee _kkinn
answer parrih_yaads. grandsa_yards
[Predleted 6 , Python
Predicted 273.0 1 Python
grace_xeight 125
yamnrarrahh 1/
weight
yarn garm_grandea
weight__ultiilier 4
yards_peer_skein 364
alex tex_total alex_weight weight_sultiplier grace_vright
yare_rariah yarn_grandna
answer grace_weight alex_total
& yards_used total_yards yards_per__seee
(a) Examples of self-cvaluation score distribution of different predictions on the GSM8K datasct.
[2)] Is Freya combiaation [Ground- Truch 4 yes
Aphrodite?
Did Columbus obtain his funding from the rulers of the Portugese Empire?
Truth a
[Espianntion]
Greek goddess Aphrodito was
[Expbaatiion] King Fardinand
isabalia Columbus' voyage. They
godkass love. Fraya the Norse goddiss war love, and fertility.
were the joint rulers of the Iberian Peninsula, which included Spain but excludes
(Predieted
Portugal. King John Portugal rejected Columbus for funding.
in Chain-oo Ioought
Freya Norse goddess.
[Predicted s,l /o [M,)
Thought
and Aphroditc goddesses.
Thus, Fraya not combination of Athena and Aphrodits.
funding
the Spanish Empire
answer
Thus, Columbus didn't obsain his funding Portugese Empire.
[Prodicted sgl yag [ L
answer
Chain-or Ihought
[Predicted s,l
goddess
[+g] Chain-ot Thought
E You can compare these to the Greek gods Athens and Aphrodits.
Columbus was italian and the Portugese Empiro was Portugeso, Columbus didn't oblain
their
Empire.
However, it seems that Freya must have attributes that match both.
So the ansover
yes.
(b) Examples of self-evaluation score distribution of different predictions on the Strategy dataset. We also provide explanations corresponding the ground-truth answers for reference.
Figure 7: Comparisons among predictions of high and low self- eeffevvauuation scores on arithmetic (7a for GSMSK) and commonsense (7b for StrategyQA) reasoning tasks. Scores from low high visualized from orange (0.0). yellow (0.4), green (1.0). Here P, and represent the evaluation confidence, the generation confidence, and their combination as the final score, respectively.
from the improved coverage of the plausible generations and the ensembling effect. Nevertheless, one adjust the sampling-related parameters (iee., and a) to incorporate more randomness into the generations. In practice, we find that moderate temperature decay (e.g., a = 0.5) results improved performance. We conduct further analysis of the effect of sampling diversity in Appendix A.2.
Qualitative Analysis. We examine particular instances investigate the behavior of correctness confidence scores C and generation probabilities P in different scenarios. From the comparison shown in Figure 7, we have the following main observations:
In general, the correctness confidence more effective identifying logical errors, taking into account the accumulated mistakes from prior steps, while the generation probability focuses more on text perplexity as the confidence of the generation L.M.
When comparing arithmetic and commonsense tasks, L.MMs exhibit greater confidence in dealing with structured and objective reasoning chains such as problems in GSMSK, for both generation and self-evaluation, as opposed to reasoning chains in Strategy
Reasoning chains that appear logically plausible can achieve high correctness confidence scores but still result in incorrect answers, as demonstrated R41 in Figure 7b. Moreover, the correctness confidence can be influenced by minor details (e.g., imperfect variable naming in PAL reasoning) and assign low scores regardless of the correctness of the final answers as shown in R22 in Figure 7a.
Incoherence due to sudden jump in reasoning (e.g., Raz in Figure 7b) can lead to low correctness confidence. Additionally, the correctness confidence tends be lower when the generation L.LM makes probability statement with less certainty, such "it seems" as illustrated by R4g in Figure 7b.

---

4 Related Work
Reasoning Formulation. Several studies have attempted to better formulate the reasoning problem. One approach is to generate rationales to enhance model interpretability (Zhou et al., 2020; Wiegreffe and Marasovic, 2021; Wiegreffe et al., 2021). Recently, the focus has shifted towards decomposing the reasoning process into intermediate steps before reaching the final answer (Wei et al., 2022b; Zhou et al., 2023; Gao al., 2023; Chen et al., 2022). Various decomposition techniques have been explored, such as question reduction (Zhou et al., 2023; Yang et al., 2022), iterative prompting (Wang et al., 2022), and chaining the steps (Wu et al., 2022). While incorporating intermediate reasoning steps has resulted in substantial performance improvements, errors or imperfections can accumulate, especially when the chains become longer (Wu et al., 2016; Guo et al., 2018). As such, we utilize L.M self-evaluation as a stepwise criterion to improve the chaining process.
LLM Sofl-avaluation. Recent research on LLM calibration shows that current LLMs' probabilistic predictions correspond well with actual token occurrence frequencies, leading to well-calibrated predictions for specific tasks (Rae al., 2021: Kadavath al., 2022: Guo al., 2017: Kadavath et al., 2022; Jiang et al., 2021; Kuhn et al., 2023). Notably, scaling model size plays a crucial role in enhancing calibration (Rae al., 2021; Wei al., 2022a). As LLMs exhibit good calibration, an increasing number of studies focus on prompting LLMs to perform self self-evaluation as means of verification (Zhang et al., 2023; Shinn et al., 2023; Madaan al., 2023; Paul et al., 2023). Self- evaluation provides an effective and efficient assessment method without requiring task-specific verifier fine-tuning, which typically involves additional annotations (Li et al., 2022). In contrast to existing works that refine generation results through instance-level ceff-evaluation, our approach applies self-evaluation results as a stepwise criterion to calibrate generation at a finer granularity. By focusing on step-by-step self-evaluation, our method enables fine-grained guided decoding, addressing the challenges associated with complex or lengthy reasoning.
Decoding Strategies. A tradeoff typically exists between diversity and quality. Deterministic decoding methods such as greedy decoding and beam search (Jurafsky and Martin, 2009; Graves, 2012) often produce high-qualit results but lack diversity (Stahlberg and Byme, 2019; Meister et al., 2020). Temperature sampling (Ackley al., 1985), top-k sampling (Fan et al., 2018), and top-p sampling (Holtzman et al., 2020) are various techniques used to enhance diversity. The recent work of tree-of-thought (Yao et al., 2023) explores different search algorithms such as breadth-first and depth- first searches tailored for different tasks. Differently, we propose a unified framework of stochastic beam search (Caccia et al., 2020; Kool et al., 2019; Meister et al., 2021), which combines beam search and temperature sampling to balance the quality-diversiy trade-off in multi-step reasoning.
5 Discussion
We have introduced a multi-step decoding method that calibrates reasoning with stepwise self- evaluation guidance via stochastic beam search for current large language models. The empirical success of our method across broad range of tasks, from arithmetic and symbolic to commonsense reasoning, demonstrates its robustness and generalizability in various application areas. The signif- icant performance gains of our method on long reasoning chains also highlight its applicability to other multi-step tasks, such as multi-hop question answering and more complex scenarios involving multi-modal understanding, reasoning, and planning. In future work, we will investigate how to utilize external tools to further enhance the calibration and explore its generalizability on other multi-step scenarios to deal with more complex information such as external knowledge and multimodalities.
Potential Impacts and Limitations
We propose self- evaluatalttion guided stochastic beam search to facilitate multi-stpp reasoning. However, our approach, based on stepwise self-evauuttion guidance, has certain limitations. It requires access to LLM logits to calculate the self-evaluation score, restricting its applicability to more powerful LLMs, such as GPT-4, which do not provide token likelihoods. Plus, multi-step decoding inherently causes additional costs from candidate sampling and self-evaluation. For optimal balance between efficiency and cost, our approach is best applied to longer reasoning chains, where the cumulative effect of calibration across multiple steps can improve the overall performance more significantly.
10

---

Acknowledgments and Disclosure of Funding
The computational work for this article was partially performed on resources of the National Super- computing Centre (NSCC), Singapore'. We would like to thank Prof. Hwee Tou Ng for his insightful discussions that enhanced the depth and quality of our study.
References
David H. Ackley, Geoffrey E. Hinton, and Terrence J. Sejnowski. 1985. A learning algorithm for boltzmann machines. Cognitive Science, 9(1):147-169
Tom B. Brown, Benjamin Mann, Nick Ryder, Melamic Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herhert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020. Language models are few-shot learnrrs. In Advances in Neural Information Processing Systems 33; Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 2020, virtual.
Massimo Caccia, Lucas Caccia, William Fedus, Hugo Larochelle, Joelle Pineau, and Laurent Charlin, 2020. Language gans falling short. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ahaba, Ethiopia, April 26-30, 2020. OpenReview.net.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrow, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Car,, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojeiech Zaremba. 2021. Evaluating large language models trained on code.
Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W. Cohen. 2022. Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks. CoRR, Abs/2211.1255..
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sehastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Baress, Yi Tay, Noam Shazeer, Vinodkumar Prab- hakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin. Toju Duke, Anselm Levskaya, Sanjay Ghemawat, Sunipa Dev. Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus. Denny Zhou, Daphne Ippolito. David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi. David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowyez, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Sacta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Jeff Dean, Slav Petrov, and Noah Fiedel. 2022. Palm: Scaling language modeling with pathways. CoRR, abs/2204.02311.
Douglas Eck,
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert. Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. 2021. Training verifiers to solve math word problems. CoRR, abs/21 10. 14168.
Angela Fan, Mike Lewis. and Yann Dauphin. 2018. Hierarchical neural story generation. In Proceedings of the 56th Annual Meeting the Association for Computational Linguistics (Volume Long Papers), pages 889-898, Melbourne, Australia. Association for Computational Linguistics.
Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig. 2023. PAL: program-aided language models. In International Conference on Machine Learning, JCML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 10764-10799. PMLR.
'htpss//www.nscc.s///
11

---

Mor Geva, Daniel Khashabi. Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant, 2021. Did aristotle a laptop? A question answering benchmark with implicit reasoning strategies. Trans, Assoc. Comput. Linguisticx, 9:346-361.
Alex Graves. 2012. Sequence transduction with recurrent neural networks. CoRR, ahs/1211.3711
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. 2017. On calibration of modern neural networks. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 1230. PMLR.
Jiaxian Guo, Sidi Lu, Han Cai, Weinan Zhang. Yong Yu, and Jun Wang. 2018. Long text generation via adversarial training with leaked information. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1).
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yajin Choi. 2020. The curious case of neural text degeneration. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net.
Jiaxin Huang. Shixiang Shane Gu. Le Hou, Yuexin Wu, Xuezhi Wang. Hongkun Yu, and Jiawei Han. 2022. Large language models self-improve.
Zhenghao Jiang, Jun Araki, Haibo Ding, and Graham Neubig. 2021. How can we know When language models know? on the calibration of language models for question answering. Trams. Assoc. Comput. Linguistics, 9:962-977.
Dan Jurafsky and James H. Martin, 2009. Speech and language processing an introduction to natural language processing, computational linguistics, and speech recognition. Pearson Prentice Hall, Upper Saddle River, N.J.
Saurav Kadavath, Tom Conerly, Amanda Askell, Tom Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer. Zac Hadieed--Dodds, Nova DasSarma, Eli Tran-Johnson, Scott Johnston, Sheer El Showk. Andy Jones, Nelson Elhage, Tristan Hume, Anna Chen, Yuntao Bai, Sam Bowman, Stanislav Fort, Deep Ganguli, Danny Hermandez, Josh Jacobson, Jackson Kernion, Shauna Kravec, Liane Lovitt, Kamal Ndousse, Catherine Olsson, Sam Ringer, Dario Amodei, Tom Brown, Jack Clark, Nicholas Joseph, Ben Mann, Sam McCandlish, Chris Olah, and Jared Kaplan. 2022. Language models (mostly) know what they know. CoRR, abs/2207.00 ,05221.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022. Large language models are zero-shot reasoners. In NeurIPS.
Wouter Knol, Herke van Hoof, and Max Welling. 2019. Stochastic beams and where to find them: The gumbel- top-k trick for sampling sequences without replacement. In Proceedings of the 36th International Conference on Muchine Learning. ICML 2019, 9-15 June 2019, Long Beach. California, USA, volume 97 of Proceedings of Machine Learning Research, pages 3499-3508. PMLR.
Lorenz Kuhn, Yarin Gal, and Sebastian Farquhar. 2023. Semantic uncertainty: Linguistic invariances for uncertainty estimation in natural language generation. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net.
Aitor Lewkowycz, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay V. Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman- Solo. Yuhuai Wu, Behnam Neyshabur, Guy Gur-Ari, and Vedant Misra. 2022. Solving quantitative reasoning problems with language models. In NeurIPS.
Yifei Li. Zeqi Lin. Shizhuo Zhang, Qiang Fu, Bei Chen, Jian-Guang Lou, and Weizhu Chen. 2022. On the advance of making language models better reasoners.
Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom. 2017. Program induction by rationale generation: I Learning to solve and explain algebraic word problems. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, ACL 2017, Vancouver, Canada, July 30- August 4, Volume I: Long Papers, pages 158-167. Association for Computational Linguistics.
Pan Lu, Liang Qiu, Kai-Wei Wei Chang, Ying Nian Wu, ConngChun220 Zhu, Tanmay Rajpurohit, Peter Clark, and Ashwin Kalyan, 2023. Dynamic prompt learning via policy gradient for semi-structured mathematical reasoning. In The Fleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net.
Aman Madaan, Niket Tandon, Prakhar Gupta. Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang. Sean Welleck, Bodhisattwa Prasad Majumder. Shashank Gupta, Amir Yazdanbakhsh, and Peter Clark. 2023. Self-refine Iterative refinement with self feedback. CoRR, abs/2303.1766 17651..
12

---

Clara Meister, Afra Amini, Tim Vieira, and Ryan Cotterell. 2021. Conditional poisson stochastic beam search. CoRR. abs/2109.11034
Clara Meister, Ryan Cotterell, and Tim Vieira. 2020. Best-first beam search. Trans, Assoc. Comput. Linguistics, 8:795-809
Yhen-Yun Miao, Chao-Chun Liang, and Kih- Su. 2020. A diverse corpus for evaluating and developing english math word problem solvers. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, 2020, Online, July 5-10, 2020, pages 975-984, Association for Computational Linguistics.
Maxwell Nye. Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena. 2021. Show your work: Scratchpads for intermediate computation with language models. CoRR, abs/2112.0011 14,
OpenAI. 2023. GPT-4 technical report. CoRR, abs/2303.08874
Arkil Patel, Satwik Bhattamishra, and Navin Goyal. 2021. Are NLP models really able to solve simple math word problems? In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-IILT 2021, Online, June 6-11, 2021, pages 2080 2094. Association for Computational Linguisties.
Debjit Paul, Mete Ismayilzada, Maxime Peyrard, Beatriz Borges, Antoine Bosselut, Robert West, and Boi Faltings. 2023. REFINER: reasoning feedhack on intermediate representations. CoRR, abs/2304.01909 0194..
Jack W. Rac, Schastian Borgeaud, Trevor Cai, Katie Millican, Jordan Hoffmann, H. Francis Song, John Aslanides, Sarah Henderson, Roman Ring. Susannah Young. Eliza Rutherford, Tom Hennigan, Jacob Menick, Albin Cassirer, Richard Powell, George van den Driessche, Lisa Anne Hendricks, Maribeth Rauh, Po- Sen Huang, Amelia Glaese, Johannes Welbl, Sumanth Dathathri, Saffron Huang, Jonathan Uesato, John Mellor, Irina Higgins, Antonia Creswell, Nat McAlcese, Amy Wu, Erich Elsen, Siddhant M. Jayakumar, Elena Buchatskaya, David Budden, Esme Sutherland, Karen Simonyan, Michola Paganini, Laurent Sifre, Lena Martens, Xiang Lorraine Li, Adhiguna Kuncoro, Aida Nematzadch, Elena Gribovskaya, Domenic Donato, Angeliki Lazaridou, Arthur Mensch, Baptistt Lespiau, Maria Tsimpoukelli, Nikolai Grigorev, Doug Fritz, Thibault Sottiaux, Mantas Pajarskas, Toby Pohlen, Zhitao Gong, Daniel Toyama, Cyprien de Masson A'tuume Yujia Li, Tayfun Terzi, Vladimir Mikulik, Igor Babuschkin, Aidan Clark, Diego de Las Casas, Aurelia Guy. Chris Jones, James Bradbury, Matthew J. Johnson, Blake A. Hechtman, Laura Weidinger, lason Gabriel. William Isaac, Edward Lockhart. Simon Osindero. Laura Rimell, Chris Dyer, Oriol Vinyals, Kareem Ayoub, Jeff Stanway. Lorrayne Bennett, Demis Hassabis. Koray Kavukcuoglu, and Geoffrey Irving. 2021. Scaling language models: Methods, analysis & insights from training gopher. CoRR, abs/2112.11 11446.
Noah Shinn, Beck Labash, and Ashwin Gopinath. 2023. Reflexion: autonomous agent with dynamic memory and self-reflection. CoRR, abs/2303. 11366.
Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R. Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso Agnieszka Kluska, Aitor Lewkowycz, Akshat Agarwal, Alethea Power, Alex Ray, Alex Warstadt, Alexander W. Kocurek, Ali Safaya, Ali Tazary, Alice Xiang, Alicia Parrish, Allen Nie, Aman Hussain. Amanda Askell, Amanda Dsouza, Ameet Rahane, Anantharaman S. Iyer, Anders Andreassen, Andrea Santilli, Andreas Stuhlmüller, Andrew M. Dai, Andrew La, Andrew K. Lampinen, Andy Zou, Angela Jiang, Angelica Chen, Anh Vuong, Animesh Gupta, Anna Gottardi, Antonio Norelli, Anu Venkatesh, Arash Gholamidavoodi, Arfa Tabassum, Arul Menezes, Arun Kirubarajan, Asher Mullokandov, Ashish Sabharwal, Austin Herrick, Avia Efrat, Aykut Erdem, Ayla Karakas, and et al. 2022. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. CoRR, abs/2206.04615.
Felix Stahlberg and Bill Byrne. 2019. On NMT search errors and model errors: Cat got your tongue? In Proceedings of the 2019 Conference on Empirical Methods Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLA, pages 3356-3362, Hong Kong, China. Association for Computational Linguistics.
Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. 2019. Commonsenseqa: question answering challenge targeting commonsense knowledge. Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. NAACL- HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume I (Long and Short Papers), pages 4149 4158. Association for Computational Linguisties.
13

---

Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix. Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurélien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. 2023a. Llama: Open and efficient foundation language models. CoRR. abs/2302.13971.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaci, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton-Ferrett Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshom, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee. Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nic, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang. Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Ilyaan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurélien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. 2023b. Llama 2: Open foundation and fine-tuned chat models. CoRR, abs/2307.09228.
Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song. Noah Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins. 2022. Solving math word problems with process- and outcome-based feedback.
Boshi Wang, Xiang Deng, and Huan Sun. 2022. Shepherd pre-trained language models to develop train of thought: An itcrative prompting approach. CoRR, abs/2203.08.. 00.3883.
Xuezhi Wang. Jason Wei, Dale Schuurmans, Quae V. Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2023. Self-consistency improves chain thought reasoning in language models. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net.
Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H. Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus. 2022a. Emergent abilitics of large language models. Trans, Mach. Learn. Res., 2022.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Iehter, Fei Xia, Ed H. Chi, Quoc V. Lc, and Denny Zhou. 2022b. Chain-of-thought prompting elicits reasoning in large language models. In NewrIPS.
Sarah Wiegreffe and Ana Marasovic. 2021. Teach me to explain: A review of datasets for explainable natural language processing. In Proceedings of the Neural Information Processing Systems Track on Dutasets and Benchmarks 1, NeurlPS Datasets and Benchmarks 2021, December 2021, virtual.
Sarah Wiegreffe, Ana Marasovic, and Noah A. Smith. 2021. Measuring association between labels and free-text rationales. In Proceedings of the 2021 Conference Empirical Methods in Natural Language Processing, EMNLP 2021, Virtual Event/ Punta Cana, Dominican Republic, 7-11 November, 2021, pages 10266-10284. Association for Computational Linguistics.
Tongshuang Wu, Michael Terry, and Carrie Jun Cai. 2022. Ai chains: Transparent and controllable human-ai interaction by chaining large language model prompts. Proceedings of the 2022 CIII Conference on Hunan Factors in Computing Systems, CHI '22, New York, NY, USA. Association for Computing Machinery.
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoe V. Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, Jeff Klingner, Apurva Shah, Melvin Johnson, Xiaobing Liu, Lukasz Kaiser, Stephan Gouws, Yoshikiyo Kato, Taku Kudo, Hideto Kazawa, Keith Stevens, George Kurian, Nishant Patil, Wei Wang, Cliff Young. Jason Smith, Jason Riesa, Alex Rudnick, Oriol Vinyals, Greg Corrado, Macduff Hughes, and Jeffrey Dean. 2016. Google's neural machine translation system: Bridging the gap between human and machine translation. CoRR, abs//6609.00 1844444.
Jingfeng Yang, Haoming Jiang, Qingyu Yin. Danqing Zhang, Bing Yin, and Diyi Yang. 2022. SEQZERO:
few-shot compositional semantic parsing with sequential prompts and zero-shot models. In Findings of the Association for Computational Linguistics: NAACL 2022, Searlle WA, United States, July 10-15, 2022, pages 49-60. Association for Computational Linguistics.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas I.. Griffiths, Yuan Cao, and Karthik Narasimhan. 2023. Tree of thoughts: Deliberate problem solving with large language models. CoRR, abs/2305. 10601.
Tianyi Zhang, Tao Yu. Tatsunori Hashimoto, Mike Lewis, Wen-Tau Tau Yih, Daniel Fried, and Sida Wang. 2023. Coder reviewer reranking for code generation. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolud,, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 41832 41846. PMLR.
14

---

Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui. Olivier Bousquet, Quoc V. Le, and Ed H. Chi. 2023. Least-lo-most prompting enables complex reasoning in large language models. The Eleventh International Conference on Learning Reprexentations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net.
Wangchunshu Zhou, Jinyi Hu, Hanlin Zhang, Xiaodan Liang. Maosong Sun, Chenyan Xiong, and Jian Tang. 2020. Towards interpretable natural language understanding with explanations as latent variables. In Advances in Neural Information Processing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 12, 2020, virtual.
15

---

A Appendix
A.1 Theoretical Analysis of Eq.
In Eg. 4, use S sampled from the language model LMg generations. This is approximation for sampling from the infinite set all possible chaining paths. And the finite set S constructed based on generation LM PiMg. which is different from our target distribution as shown in Eq. 4.
Specifically, denote the infinite set of all possible generated completions till the 1-th step as S", we approximate (E(" //x]
where $ is sampling from be (s ) g exp ()/r) via Pream (s (slit) E exp ()()))))/r)
(E(x )/+)
the approximation S with |S| nk M - S.
Define the upper bound and the lower bound g on each exp (E ([((2:))) \T) as 22 exp (E(s*))) /T) 2 & for all T 2 Thus, we can take r S
glit E S", Define the ratio as r = z/g. Note that g 2 since ((s=
We now give the following proposition which shows that Pbeam (st - Poeam (s*t1) decreases at the rate of O( 11 M/ toward as M increases. Note that as M increases toward |S the numerator 1 - M S decreases toward while the factor for the denominator 1 also decreases.
M
Proposition For any shit the difference between Pbeam (s21t) and Pheam (s bounded by
1 M/|S
Pieem (8tit) - Poeam (8 S 72
(6)
M
Proof. We now prove the second statement by analyzing the absolute difference:
P (s"
Poeam (alamm(s")) (s"
(7)
exp (E(""))))
exp exp (E(s
(8)
Eases exp (E(st:t\/T) Enings exp (E(s1:t)
exp (xp( [Saiees exp (E()))t)/7) - Eavee exp exp
(9)
(Enites exp (E(s1it)/T) E Eiitess exp (E(slit)/T))
exp (8() Estres exp (E(s!)*)/))
(10)
Eiiees exp (E(sL:t)/T) Egiles exp (E(sttt\TT)
Since exp (E (E(sti))T) \T) nonnegative, using the upper bound on each exp (E()) we have:
(1S - M)
IPream (s - Pream (s S
(11)
(Etirss exp (E(s)=)/TT) Exirss exp (E(s):)/T)
Similarly, using the lower bound on each exp (E(s (\/T)
(1S* =,² 1-211M/15
M/(8")
PPicam Pream (s (1
(12)
S M
M
16

---

A.2
Extended Experiments
80
80.2
199.4
79 78 8
79.0
78.8
Accuracy
78
Accuracy
78.4
77.9
77
7666
LM temperature y= 0.8
LM temperature y 0.8
74
LM temperature y= 1.0
LM temperature y 1.0
74.1
73.4
0.00
0.25
0.50
0.75 1.00
0.2
0.4
0.6
0.8
1.0
Sampling temperature (a 0.5)
Decay ratio (T = 0.5)
Figure 8: Accuracy curves with different sampling diversity. The two plots show the changes in performance on GSM8K when the sampling temperature and its decay ratio vary, respectively.
Sampling Diversity.
accordance with Figure 6b, observe similar results when ablating the sampling hyperparameters т and a single reasoning chain case, shown Figure Increasing T a generally adds more diversity to the decoding process, but excessive randomness negatively impacts the performance of the single-chain decoding. Generally, moderate temperature decay results in improved performance. Therefore, set 0.5 throughout experiments for simplicity and only tune for randomness control.
0.62
y=
y
0.61
y 0.8
0.2
0.78
0.4
0.76
0.5
0.74
0.2
0.4
0.6
0.8
0.2
0.4 0.6
0.8
(a) X-AUC curves of &s GSM8K (PAL).
(b) X-AUC curves of Ex Strategy (CoT).
Figure 9: The change of AUC scores with different values of À in Ex. We calculate the AUC score as how εx can successfully determine whether the corresponding predicted reasoning chain can produce the ground-truth answer. The predictions here are from the baseline methods (i.e., CoT & PAL) with different LM temperatures 7, as represented by curves of different colors.
1.0
Instancelevel lepel Accuracy
0.8
Instancelereel Accuracy
0.8
0.6
0.4
0.4
0.2
0.0
Predictions Low-scored <0.70) Predictiors
Predictions
(e) Predictions
(a) GSM8K (PAL prompting)
(b) Strategy QA (CoT prompting)
Figure 10: Comparison between predictions of high v.s. low sell-evaluation scores on instance-level accuracy.
17

---

More Analysis on Self-Evaluation. Recall that we use a combination of generation confidence and laithfulness score as Ex C* pp(-AA) with À E [0, 1]. In our experiments. we set À = 0.5 for all tasks for simplicity. However, we investigate its effects here since, intuitively, it is an important hyperparameter for distinguishing correct / incorrect predictions and might require different values for various reasoning tasks and datascts. Its effect is also coupled with the language model temperature ?
Figure demonstrates how À functions on arithmetic (GSM8K) and commonsense (StrategyQA), In general, we observe that the performance remains relatively stable with different choices on different datasets, although fine-tuning this hyperparameter might lead to further improvements. This stability suggests that the choice of A is not overly sensitive across various reasoning tasks and datasets, but exploring its optimal value for specific tasks could potentially lead to even better performances.
To examine the influence of incorporating faithfulness LLM final predictions, plot the distributions of changes different scores, specifically the faithfulness score C, the generation confidence P, and the overall decoding score Ea on the baseline reasoning chains and reasoning chains generated by our method. categorize the data points into 4 sets based on whether our approach changes the final prediction. Since the majority of the data points belong to the "hoth correct" set (in blue), where both baselines and our method generate accurate predictions, particularly highlight the last two sets (in green and red), where our method results in improvement and degradation, respectively.
As shown Figure 11, faithfulness typically works by significantly increasing evaluation confidence C of model predictions, while the generation confidence P remains similar to that of the baseline methods. Specifically, for the evaluation confidence C, our approach corrects the original predictions by increasing the confidence scores. This indicates that evaluation confidence plays crucial role in guiding the decoding toward better reasoning choice decomposed reasoning. The increase is more significant for PAL when compared with COT. This demonstrates LLMs are generally better judging the logic reasoning that more structured, while the free-text intermediate steps (e.g. CoT reasoning) may be challenging to conduct information extraction and soundness checking.
A similar conclusion can be drawn from Figure 10, where the difference in instance-level accuracy distributions between high scored and low-scored predictions is more significant the GSM8K dataset. For StrategyQA. while incorporation faithfulness helps, level the score value does not align well with whether prediction is correct. For example, most of the low-scored predictions can still obtain the correct answers, as shown by the plot on the right of Figure 10b.
18

---

200
correct
both wrong
both wrong
both wrong correct + wrong
correct
100
correct wrong
correct wrong
change in generation probability (AP)
change in correctness confidence (AC) change (66.). - A
wrong correct
wrong correct
wrong correct wrong
wrong
wrong
0.8
change generation probabiitty (AP)
change correctness confidence (&c) change in score (dG)). & c
(a) Distributions of score shifts on GSM8K using PAI. prompting.
both correct
both correct
both correct both wrong
both
both
wrong
wrong
correct wrong
correct wrong
correct - wrong
25
change generation probability (AM
change in correctness confidence (ác) change (AE)), & - -
20
correct
correct
correct wfon
correct wrong
correct wrong
10
-0.4
-0.2
0.0
-0.1
0.0
0.3
-0.1
0.0
0.1
02
0.3
change in generation probabilly (Ar)
change in correctness confidence (Ar) change in score (46)). e² 1
12 D.5
(b) Distributions of score shifts GSM8K using CoT prompting.
150
both correct
both correct wreng wrong correct
both correct wrong wrong correct wrong
both wrong
100
wrong correct
correct wrong
correct wrona
change generation probability (AP)
change confidence change score (AG). & pi 0.5
correct correct wrong
correct wrong
correct + wrong
10
-0.6
-0.4
-0.2
0.0
0.2
0.4
-02
0.0
0.2
0.4
-0.2
-0.1
0.0
0.1
0.2
0.3
change in generation probability (Ar)
change in correctness confidence (&c) change (ds.), c -8
(c) Distributions of score shifts on StrategyQA using CoT prompting.
Figure 11: Distributions of changes in scores from baselines our method. Since the prediction correctness keeps unchanged most of the time (i.e., "both correct/incorreet" in blue/orange), we specifically plot how the scores shift on data points where the predictions get corrected incorrect, as shown in green and red, respectively.
19

---

Table 5: Impact of LLM backends (Codex vs. ChatGPT vs. GPT-4) and prompting methods (PAL vs.
CoT). The results of ChatGPT (gpt-3, 3--trrbo) were obtained on 20 March 2023.
Model
GSM8K
StrategyQA
CoT Codex
65.6
73.2
PAL Codex
72.0
СоТ ChatGPT
80.8
65.9
PAL ChasGPT
78.7
CoT GPT-4
92.0
Ours (CoT) Codex
71.9
77.2
Ours (PAL) Cudex
80.2
LLM Backhone Study. We are interested in how stronger LLMs (i.e., ChatGPT, GPT-4 (OpenAI, 2023))
work, but they are not directly compatible with our approach since the API does not return token logits.
Table compares the results of various backend L.LMs (i.e., Codex, ChatGPT, and GPT-4) on GSM8K. In arithmetic reasoning with PAI. prompting, our Codex-based method achieves competitive results (80.2% 2% vs. 78.7%) even when compared with ChatGPT. The results are consistent across other datasets, including AQuA (55.9% 54).. SVAMP (89.6% vs. 84.1%) 1)). ASDiv (84.9% vs. 84.1%), and TabMWP (79.1% vs. 80.6%). commonsense reasoning, our method using Codex significantly outperforms ChatGPT-based methods across different datasets, including StrategyQA (77.2% vs. 65.9%), CommonsenseQA (78.6% vs. 75.2%) and Sports Understanding (98.4% vs. 95.9%). One possible explanation is that ChatGPT lacks sufficient world knowledge for effective fact checking and commonsense reasoning. Given the significant performance improvement of GPT-4, conduct further analysis about how synergistically combine with method.
The recently launched GPT-4 has demonstrated notable improvements in reasoning capabilities across a variety tasks. In this section, we examine and compare the reasoning skills different large language models (LLMs), specifically Codex and GPT-4, in assessing and determining the accuracy of each step in reasoning chain. We contrast the confidence scores and corresponding explanations for Codex (C) and GPT-4 (8) in the context of both arithmetic and commonsense reasoning, shown in Figure 13 and Figure 14, respectively. For ease of visualization, we employ the same colormap (shown in Figure 12) as in Figure 7 to represent the scale of scores. Since OpenAl has not provided access the token-wise likelihood of generated text, we directly request GPT-4 to score the reasoning steps using binary values Moreover, we report the average of three evaluation results to reduce the variance of sampling discrete values, Le., S (81- S2 33)/3,
GPT-4 Experiments
[0.
As illustrated in Figure 13, GPT-4 demonstrates greater effectiveness in pinpointing the central logical arithmetic reasoning. For instance, we can observe that S < for alex_total aeigh weight_mul ht__uulppplerrr grace_weight and S >> C for answer grace_ grace_weight weight + alex_total where the former leads to an incorrect final answer. Additionally, GPT-4 typically offers detailed explanations and alternative solutions. As seen in the step answer grace_ sosee__eeigge iitttt + teta_tt GPT-4 can correct minor errors even when it arrives the correct final answer. However, GPT-4 may still encounter difficulties in detecting small errors within the text, which can have significant impact on logical consistency. This challenge illustrated by the substantial variance in S for the step alex_ total = alex_ weight weight_mull www.mmliileeeeeeeee * grace_ weight.
The benefits of well well-crafted explanations in GPT-4 become more significant when handling complex reasoning tasks, demonstrated in Figure 14. For instance, in the Ra2 of Q4 shown in Figure 7b, Codex generally assigns high evaluation scores for all steps. Although this reasoning chain leads the correct final answer, makes some overly definitive assumptions without reasonable justification (e.g., "must have attributes match both"). In such cases, GPT-4 can accurately identify these vague statements through meticulous analysis. Moreaver, the comprehensive analysis helps address the growing uncertainty arising from the ambiguity in understanding commonsense questions. For example, in the final step. GPT-4 offers extensive explanations for assigning low S scores, considering the limited information available to comprehend the question.
summary, GPT-4 demonstrates promising improvements LLM evaluation by providing more rigorous and in-depth explanations. While there is significant variation in its generated explanations for some challenging cases, these explanations are typically beneficial as they claborate on understanding and interprctation based on the given information. This suggests the potential for using LLM explanations enhance self-evaluation in future rescarch.
'The results using GPT-4 were obtained on 22 April 2023,
20

---

0.0 0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9 1.0
self-evoluation c PI
Figure 12: Score from low to high values visualized using colormap from orange to green
[e,] Grace weighs 125 pounds. Alex weighs pounds less than times what Grace weighs. What are their combined weights in pounds? (Ground-Truth #I 623.0
[Predicted 1
6
1 in Python
grace @aace_weight 125
C
correct
S
correct
The line code correctly assigns the given weight of Grace (125 pounds) the variable grace weight
S2
The given line code correctly assigns the value 125 variable grace_we weight, representing Grace's weight in pounds.
alex exx ee__eight
C plex_weight should be calculated based grace_wed sengh
alex_ seex_weight should be calculated as times grace peiihg minus 2
The line of code defining alex_ teee_eightt should be calculated as times Grace's weight minus 2, which is (4 grace_wer seice_weight)
S
S2
The calculation for Alex's weight is not correct. It should be calculated as
grace grace_weight 2.
we reright_muliippie
C
correct
The line code correct defines the multiplier for Alex's weight based on Grace's weight.
Correct because assigns the correct value (4) variable weight multiplier, which represents factor by which Grace's weight multiplied calculate Alex's weight.
S
S2
The code correctly assigns the value the variable weighhtmulttpple multiplier, which will used the calculation Alex's weight.
alex_ alex_total alex_ -lex_weight + weight_multipliee
grace_weight
correct formula calculate alex total
The formula used to calculate Alex's weight incorrect.
The above line of code calculates Alex's weight correctly pounds less than 4 times Grace's weight (4 grace_wa sench 2).
S
S
Alex weighs pounds less than times what Grace weighs, not pounds more.
answer
grace_ weich_ alex_total total
C should be the sum of grace grace_weight and alex_weliee weight
The code calculates Alex's weight correctly using the given relationship and adds it to Grace's weight to calculate the combined weight. The only minor issue is the unnecessary use of the separate variable
alex weight which could directly be replaced with the calculation (4 grace_ srace_weight However, this
2).
affect correctness the answer.
The result variable holds the correct combined weight of Grace and Alex, and this line of code correctly calculates the value of answer.
S
S2
The code above correctly calculates the total weight of Grace and Alex based on the given problem statement, The only minor issue is that the alex_ weight variable is initialized as 2, which might be bit confusing. It would be better to directly calculate alex_ total as (4 grace_weight 2). but the current code does not produce an incorrect result.
S
Figure 13: Comparison between Codex (C) and GPT-4 (S) on evaluating the reasoning chains in arithmetic reasoning. The example (R12 for Qi is the same one from Figure 7a. We underline the key statements explanations that justify the judgment of GPT-4.
21

---

10,1 Freya a combination of Athena and Aphrodite? [Ground-Truth "I yes [Explanation] Athena was the Greek goddess of war. Aphrodite was the Greek goddess of love. Freya was the Norse goddess of war, love, and fertility.
[Predicted لrي yes/
,R, in Chain-of- Thought
Freya is the goddess of love, beauty and fertility.
E
correct
Freya indeed is associated with love, beauty, and feriility in Norse mythology. However, It important note that while the comparison to Alhena and Aphrodile is understandable, it is n direct or complete euw.iaaleeee The statement correctly identifles Freya. However, the statement does mention that Freys is a Norse goddess, which could slightly impact the underslanding of the comparison to Greek goddesses Athena and Aphrodite. The statement is mostly correct as Freya is indeed goddess associated with love, beauty, and fertility. However, It might be worth mentioning that she a Norse goddess, while Athena and Aphrodite are Greek goddesses, to provicie more context
S
S
S
S
You can compare these to the Greek gods Athena and Aphrodite.
3
C
correct
It true that Freya be compared the Greek gods Athena and Aphrodite in terms of their respective domains. However, the comparison is not entirely accurate as Freya comes from Norse mythology, and the altribules of the gods may not be an exact match. The comparison Is simplfiiaaionn which why the probability is not higher.
S
The statement establishes comparison between Freya and the Greek goddesses Athena and Aphrodite. While this step reasoning generally correct, It could be improved specifically mentioning that Freya a Norse goddess and by providing more information about roles and attributes Athena and Aphrodite a clearer comparison.
$
S₂
While it true that Freya shares some similarties with Athena and Aphrodite, the compartson is not entirely accurate. Breyaa is a Norse goddess, while Athena Aphrodite are Greek goddesses. The companion correct the sense that they share some domains, but a might be misleading to suggest that Freya is direct "combiration" of these two goddesses.
S
It not clear how their powers exactly compare.
3
C
correct
This stop of reasoning acknowledges that is not entirely clear how the powers of Freya, Athena, and Aphrodite compare. Although there are some similarties, differences between Norse and Greek mythologies make difficult determine whether Freya is direct combination of Athena and Aphrodite, The high pmbaaility refeect the acknowledoment of the uncertainty comgaring powers of the gods across different mvtholosies.
S
The statement acknoweddes that it is not clear how the powers of Freya, Athena, and Aphrodite exactly compare. However, Freya is combination Athena and Aphrodite, which implies synthesis or blending their roles Sg altributes. The reasoning could be improved by specifically mentiening the roles and attribules of Athena and Aphrodile and whether or not they everaa Freva's roles and attributes.
question
The reasoning here more accurate, acknowledging that while there are similariies between Freya and Athena and Aphrodite,
S
goddess and Athena and Aphrodite are Greek goddesses, so their roles, domains. and characteristics may not be direcily comparable.
their powers exactly compare. important consider Freya
However, it seems that Freya must have attributes that match both.
E
C
correct
incorrect because il assumes that Freva must have attributes that match both Athena and Aphrodite. While there may be some similarities their atlributes, not appropriate to conclude that Freya combination and Greek mythologies are distinct, and the delties in these pantheons may have different origins and roles. The stalement acknoweddgs
5
two Greek goddesses. Norse
match both accurate to discuss the specific attributes of Athens and Aphrodite to determine the extent of the similartiess assumes Freya must have attribules malch both Alhena Aphrodile, but may not the case. While there are similarties between these goddesses, they are from different mythologles (Freya - Norse, Athena & Aphrodite - Greek), S and their roles, domains, charadeerisicss may not directly comparable combined. ii accurate to assume that Freva & a combination of Athena and Aphrodite without a more in-decth analysis in their respeclive mythologies.
Freya attribules
and Aphrodile. However,
S
S
So the answer is yes.
3
C
correct
This step of reasoning is incorrect because is just based on some similarilies in their altributes. While there may be some similartties, It not sccurate say Freva combination the Greek goddesses. Norse and Greek mythologies are distinet and the dellies in these pantheons have different origins and roles. Although Freya shares some attributes with both Athena and Aphrodite, combination of the two. The questin seams to imaly that Freya might be a direct mix of the two, but this is not accurate. The concusion that Freys combination of Athena Aphrodite
S
an oversimolilication to claim that
S
S
information grovided. While 5 there are simlariiies between these goddesses, they belong to different mythologies (Freya is Norse, Athena and Aphrodite Greek), and roles, domains, characteristics may be directly comparable or combined.
accurate based
Figure 14: Comparison between Codex (C) and GPT-4 (S) on evaluating the reasoning chains in commonsense reasoning. The example (R42 for Q4) is the same from Figure 7b. We underline the key points in GPT-4 rationales that explain the detailed understanding and analysis on the steps.
22

---

A.3 Implementation Details
Similar to beam search, we maintain & distinct candidates in the beam and sample completions for each one. Thus, for each reasoning step s", the search space has size of k After acquiring k n samples, retain candidates by sampling from Pream as Eq. 4. We set quality and efficiency. The maximum number of steps to decode is capped at 16. To control the computational cost and time complexity, one can also reduce the number of rollouts per beam and the beam size to n = 2 and l E [3, 4] respectively,
5, n 16 with Codex backbone to balance
illustrate with 1lama-2 backhone.
We set generation temperatures differently for various tasks and baselines. Regarding the generation temperature y on Codex, for arithmetic and symbolic reasoning with PAI. using deterministic heam search 0.0), find that y E [0.4, 0.8] generally works well. contrast, for commonsense reasoning with CoT,, lower temperature (7 E [0.1, 0.5)) is more effective, likely due to the increased randomness from the free-text format. Differently, when using L backbone, PAL generally works better with lower generation temperature S 0.5, while CoT tolerate larger 7 > 0.5 with better comparable performance. This difference between Codex and Llama-2 may come from the different training tasks and data adopted for the two models, where the PAL reasoning is especially enhanced in Codex.
In majority voting, higher 7 is preferred to better explore the search space in reasoning. e.g., 2 0.5 for arithmetic reasoning. To further introduce sampling randomness in stochastic beam search for majority voting multiple reasoning chains, choose 0.5 for PAL and 0.2 for CoT, PAL Aypically decomposes the reasoning problem into more steps than CoT. Here we tune v instead of a to he smaller CoT as CoT naturally contains more randomness due to its free-text formulation as we observe in practice, where a smaller is more efficient to balance this randomness.
0.5 for all datasets but different values of 7 for each task. Specifically.
In previous works, majority voting multiple reasoning chains involves sampling N (usually 2 20) reasoning chains and conducting vote to determine the final answer, which can be time-consuming. In approach, we simply perform majority voting among the N candidates in the last step of beam search from only few times (S 10) searching. As a result, our method does not introduce additional time complexity compared to the conventional majority voting method, although we sacrifice some diversity in the final outcomes due to the similarity of candidates within beam.
Prompts.
We show examples of both the generation and evaluation prompts we on different tasks in the following tables. where only show instance for each case. Full prompts and detailed formulations can be found in our code.
23

---

Table Examples of few-shot exemplars of generation and evaluation CoT prompts on GSM8K, We adopt 8-shot and 5-shot learning for generation and evaluation, respectively.
GENERATION
Q: There are 15 trees in the grove. Grove workers will plant trees in the grove today. After they are done, there will be 21 trees. How many trees did the grove workers plant today? A:
There are trees originally. And there were 21 trees after some more were planted.
So 21 15 = 6 trees were planted.
So the answer is 6.
IVALUATION
Q: Allison brought some CDs online. Each CD cost S7. There additional charge of $4 per order for shipping costs. The total came $60. How many CDs did Allison buy?
A:
Each CD cost 7 dollars.
# Is the above step of reasoning:
(A) Correct
(B) Incorrect
# The above step of reasoning is (A)
And there was an additional charge of 4 dollars.
# Is the above step of reasoning:
(A) Correct
(B) Incorrect
# The above step of reasoning is (A)
So the total cost of each CD is 4 11 dollars.
# Is the above step of reasoning:
(A) Correct
# (B) Incorrect
# The above step of reasoning is (B), because each CD costs 7 dollars.
So 60/ [11 5.45.
the above step of reasoning:
(A) Correct
# (B) Incorrect
# The above step of reasoning is (B), because it cost 4 dollars for shipping costs. So the cost of CDs
60 = 56 dollars. So Allison bought 56 / = 8 CDs.
So the answer 5.
# Is the above step of reasoning:
# (A) Correct
# (B) Incorrect
The above step of reasoning is (A), but the value of the number of CDs incorrect.
24

---

Table 7: Examples of few-shot exemplars of generation and evaluation PAL prompts on GSM8K. We adopt 9-shot and 5-shot learning for generation and evaluation, respectively.
GENERATION
Olivia has $23. She bought five bagels for $3 each. How much money does she have left?
def solution():
money_initan 23
bagels
bagel_cost =
money_spent bagels bagel_cost money_left money_initian money_spent result money_left
return result
EVALUATION
Q: A piece of square paper has perimeter of 32 centimeters. Nicky's dog, Rocky, tore off 1/4 of the paper. What is the area of the remaining paper?
def solution():
perimeter 32
Is the above Line of code:
(A) Correct
(B) Incorrect
The above line of code is: (A)
fraction_torm
Is the above line of code:
(A) Correct
(B) Incorrect
The above line of code is: (A)
area_total (perimeter / 4) ** 2
Is the above line of code:
(A) Correct
(B) Incorrect
The above line of code is: (4), because the total of the square + can calculated by (persmeter 4)
area_remaining (1 Fraction_torny area__total
Is the above line of code:
(A) Correct
(B) Incorrect
The above line of code is: (A)
result = area_total
Is the above line of code:
(A) Correct
(B) Incorrect
The above line of code is: (B), because the result should
4 area remaining
return reault
Is the above Line of code:
(A) Correct
(B) Incorrect
The above line of code is: (A), but the value of result is incorrect
25

---

Table 8: Examples of few-shot exemplars of generation and evaluation PAL prompts AQuA. Here represents the same evaluation script as those in the previous steps. We adopt 8-shot and 5-shot learning for generation and evaluation, respectively.
GENERATION
Question: a flight 600 km, an aircraft was slowed down due to bad weather. Its average speed for the trip was reduced by 200 km/hr and the time of flight increased by 30 minutes. The duration of the flight is:
Answer Choices: A)1 hour; B)2 hours; CJ3 hours; D)4 hours; E)5 hours
def solution():
duration Symbol (' ('duration', positive-True)
delay 30 / 60
total_disntace 600
original_speee = lotal_disntace / duration
reduced_speed ootal_disntace (duration delay)
solution colve_it(origina
reduced_speed 200, duration)
duration solution [duration]
result duration
return result
EVALUATION
Question: Two trains of length 150 and 200 m are 100 m apart. They start moving towards each
other parallel tracks, at speeds 54 kmph and 72 kmph. In how much time will the trains each other?
Answer Choices: A)100/7 sec; B)80/7 sec; C)57/7 sec; 10/ see; E)50/7 sec
solution():
train_1_speed 54 / 60
Is the above Line of code:
(A) Correct
(B) Incorrect
The above line of code is: (A)
train_2_spedt
72 / 60
Is the above line of code:
(A) Correct
(B) Incorrect
The above line of code is: (A)
tertaaccebetteer trains - 100
Is the above line of code:
(A) Correct
(B) Incorrect
The above line of code is: (4)
150
Is the above line of code:
(A) Correct
(B) Incorrect
The above line of code is: (A) train_2_length 200
The above line of code is: (A) sime_to_crone distance distance_betReen wwtweeeetteeeaeeeeeeeeeeeeeeeeee trains / (train_ s_apedd + train_2_speed)
....
The above line of code is: (B), because to cross each other, the + total distance should also contain the train length
result = time_to_crose
The above line of code is: (B), because the final result should be in b seconds, and the value of time_ to_ cross is incorrect
return result
The above line of code is: (A), but the value of result is incorrect
26

---

Table Examples of few-shot exemplars of generation and evaluation PAL prompts on SVAMP and ASDiv. Here we utilize the same prompts as they have the same task formulation. We adopt 7-shot and 5hotot learning for generation and evaluation, respectively.
GENERATION
Passage: James bought 93 red and 10 blue stickers, he used 31 red sticker on his fridge and 7 blue stickers his laptop.
Question: How many stickers does James have?
def solution():
original_red_ett stickere
used_red_stickers 31
red_stickers
used_red_sticker
result red_stickers return result
EVALUATION
Passage: A piece of square paper has perimeter of 32 centimeters. Nicky's dog, Rocky, tore off 1/4
of the paper.
Question: What is the area of the remaining paper?
def aolution():
perimeter 32
Is the above line of code:
(A) Correct
(B) Incorrect
The above line of code is: (A)
Aede_length perimeter / 4
Is the above line of code:
(A) Correct
(B) Incorrect
The above line of code is: (A)
area = side_length ** 2
Is the above line of code:
(A) Correct
(B) Incorrect
The above line of code is: (A)
result area
Is the above line code:
(A) Correct
(B) Incorrect
The above line of code is: (B), because should calculate the
4 remasning area after torn off as result
return result
above
of code:
(A) Correct
(B) Incorrect
The aboue line of code is: (A), but the value of result is incorrect
27

---

Table 10: Examples of few-shot exemplars generation and evaluation PAL prompts on TabMWP. We adopt 4-shot and 5-shot learning for generation and evaluation, respectively.
GENERATION
Table of "Coin collections":
Namel Number of coins
Braden 76 V Camilla 94 VA, Rick 186
Hlctor Devin 83
Emily 182 V\ Avery'
Question: Some friends discussed the sizes of their coin collections. What is the mean of the numbers?
def solution():
[76, 94, 86, 84, 80, 83, 82, 87] mean_of _tt_eff___h_______________e___e_ Se__th__ummbere numbers sum (number of_.oo_cooooooo coins_for wwdfferent_person + len (numberr__e _tiiars___ooiooo_eeeeeeeeeeeeeee foons__or_difffeeent different_person result mean_of_ off__hhh__e _nmbber return result
number_od wtt___cinn_fodddfferreeeeeee
EVALUATION
Table of "Roller coasters per amusement park":
Stem
110.0. 1.0.1689/224447788
Question: Rodrigo found list of the number of roller coasters at each amusement park in the state. How many amusement parks have fewer than 40 roller coasters?
def solution():
nusber_of
pack
25,
30, 34, 35, 36, 40, 40, 41, 42, 43,
48
48
49
49
St. 52, 52, 55, 53, 54, 54, 55, 55, 58, 56, 57, 57. 58,
58.
59
59
60
60
61
61
62
62
63
63,
64,
64,
65, 66, 66, 66, 87. 67, 68, 68, 69, 60, 70. 70.
75
74.
72
72,
78
73
74
74
75
76
76,
90, 91, 91, 52,
84, 94, 95, 96,
86,
89,
99]
Is the obove Isne of code:
(4) Correct
Incorment
The shove lese of code sor (8), beacuse valses in the rowe of Stee and Leaf represent the decseal and
4 indiosdnal digsts, respectively
number_op ounber__f__mussementt amusement__paks
taaeer_than__0000 teoeer_tha_40_rollerr
Is the above line of code:
(A) Correct
(B) Incorrect
The above line of code is: (A), because this initialize
of..mmmementt.prks.... fith. thon_40_ corsteresesrr for Bambber_o__rolee__cmm
4 number_of www.amuuueettncmmmmmmmm
in
number ofmbber_offoe ceffffooler_eee wwwolleerccaster_ppeee.. ptt.peeamssmeettppr.....
if wumber_of_rolllee coasters 40:
number_of ottprr/off_.mmmmmtt_paarssss wtwpeeeettttaarssstttteeeeeeee feeee ttt.eorr_ttttteooooreeeeeeeeteee
# Is the above line of code:
# (1) Correct
(B) Incorrect
The above line of code is: (W), the value of
4 number_ roler., coasters_per amusement_pane is incorrect
result = number_of stwarroff_amsemet___aaaae wwtpaaaatsaaaeeeeeeeeeeeeeeeeeee fwwer www.eettaaneeeeeeeeeeeeeeaaaaeee Balaa_AArrolle_ceaaaa
Is the above line of code:
(A) Correct
(B) Incorrect
The above Line of code is: (4), but the value of
number_ of amusement, parks, with. than 40_ wwwlerlleeeco coasters éa incorrect
return result
The above line of code ts: (4), but the value of result is incorrect
28

---

Table 11: Examples of few-shot exemplars of generation and evaluation PAL prompts on Date Understanding from Big-Bench. We adopt 6-shot and 3-shot learning for generation and evaluation, respectively.
GENERATION
Q: def solution():
2015 is coming in 36 hours. What is the date one week from today in MM/DD/YYYY?
If 2015 is coming in 36 hours, then today is 36 hours before. today datetime 1, 1) relativedelta (hlativeeelltaahouu----333 One week from today,
today relaativedelta The answer formatted Xm/Ad/XY result one_week www.weeeffootee fromsf_foottootay wwwooooodaa.sstt....oooo strftime "\m/',d/'XX)) return result
fee_week_from_toode
EVALUATION
Q: Yesterday was April 30, 2021. What is the date yesterday in MM/DD/YYYY? def solution():
Yesterday was April 30, 2021.
yesterday datetime (2021, 4, 30)
Is the above line of code:
(A) Correct
(B) Incorrect
The above line of code is: (4)
Yesterday,
yesterday yesterday relativedelta(dayss:))
above line of code:
(A) Correct
(B) Incorrect
The above line of code is: (B), because the date of yesterday was already got and this is step redundant
The answer formatted
/m/ld/2Y
result = yesterday strftime /m/ "/m/Ka/(X")
Is the above line of code:
(A) Correct
(B) Incorrect
The above line of code is: (A), the value of yesterday is
4 incorrect
return result
Is the above line of code:
(A) Correct
(B) Incorrect
The above line of code is: (4), but the value of result if incorrect
29

---

Table 12: Examples of few-shot exemplars of generation and evaluation PAL prompts on Object Counting from Big-Bench, We adopt 4-shot and 1-shot for generation and evaluation, respectively.
GENERATION
Q: have a drum, a flute, a clarinet, a violin, four accordions, piano, a trombone, and a trumpet. How many musical instruments do I have?
def aolution():
musical, www.iimmettatttooommmmmmm
'drum', : 1,
'flute': 1,
'clarinet's 1,
'violin': 1,
'accordion's 4,
'piano': : 1,
'tromoon'' 1,
'trumpet': 1
sum(muiccal_ hwn.mmmsssall..nttrrrrtttttooooo values ()) result num jum_instruments
num www.muasssisttruuaaaaa
return result
EVALUATION
Q: have peach, onion, two garlies, nectarine, a yam, carrot, potato, head of broccoli, cabbage, banana, and stalk of celery. How many vegetables do I have?
def solution():
note: I'm not counting the peach, nectarine, banana, or celery as vegetables
vegetables_to_coume onion': 1,
The above line of code ds: (A)
'garlic': 2,
The above line of code ia: (A)
yam' 1,
The above Vine of code is: (A)
"carrot': 1,
The above line of code da: (A)
'potato': 1,
The above line of code ist (A)
'boocooi'; 1,
The above Vine of code is: (A)
cabbage';
The above line of code da: (1)
The above line of code is: (B), because celery is vegetable num_vegetables sum som(oeetables_to_comm (o
(4), but the value of vegetables, to count incorrect result num vegetables
(4), but the value of num vegeetbbee is incorrect return result
(4), but the value of result is incorrect
30

---

Table 13: Examples of few-shot exemplars of generation and evaluation CoT prompts on CSQA. We
adopt 7-shot and 3-shot learning for generation and evaluation, respectively.
GENERATION
Q:
What do people absorb extra ink from fountain pen?
Answer Choices: (a) shirt pocket; (b) calligrapher's hand; (c) inkwell; (d) desk drawer; (e) blotter
A:
The answer must be item that can absorb ink. Of the above choices, only blotters are used to absorb ink.
So the answer is (e).
EVALUATION
Q: John's 's took his appointment book with him to checkup but couldn' 't find it anywhere. He looked and he looked but didn't know where was. It wasn't until he bought a new one, went home, took shower that he found it. Where it? Answer Choices: (a) office supply store; (b) wallet; (c) doctor's office; (d) handbag; (e) pocket
A:
The answer must be place where John could have put his appointment book.
# Is the above step of reasoning:
(A) Correct
# (B) Incorrect
step reasoning is: (B), because fails reason out that John will check the place when taking a shower (taking off clothes)
The
Of the above choices, only wallet makes sense.
# Is the above step of reasoning:
# (A) Correct
# (B) Incorrect
The ahove step of reasoning is: (B), because wallet small put his appointment book, and it cannot the only one which makes sense (pocket also plausible)
So the answer is (b).
above step of reasoning:
# (A) Correct
# (B) Incorrect
# The above step of reasoning is: (A), but the previous step is incorrect
31

---

Table 14: Examples few-shot exemplars of generation and evaluation CoT prompts on Strategy QA. We adopt 6-shot and 4-shot learning for generation and evaluation, respectively.
GENERATION
Q: Do hamsters provide food for any animals?
A:
Hamsters prey animals.
Prey animals are food for predators. Thus, hamsters provide food for some animals.
So the answer is yes.
EVALUATION
Q:
While viewing "Scary Movie" the viewer likely to experience an increase in adrenaline?
A:
Adrenaline is hormone that is released when the body is under stress.
# Is the above step of reasoning:
# (A) Correct
# (B) Incorrect
The above step of reasoning is: (A)
Scary movies are designed to make the viewer feel stressed.
# Is the above step of reasoning:
# (A) Correct
Incorrect
# The above step of reasoning is: (B), because Scary Movic is a film that is a comedy take on horror, intended to make viewers laugh
Thus, the viewer is likely to experience an increase in adrenaline.
# Is the above step of reasoning:
# (A) Correct
# (B) Incorrect
# The above step of reasoning is: (A), but the previous step is incorrect
So the answer is yes.
# Is the above step of reasoning:
# (A) Correct
# (B) Incorrect
The above step of reasoning is: (A), but the previous step incorrect
32

---

Table 15: Examples of few-shot exemplars of generation and evaluation CoT prompts on Sports Understanding on Big-Bench. We adopt 8-shot and 2-shot learning for generation and evaluation, respectively.
GENERATION
Q: Is the following sentence plausible?
"KYLE PALMIERI WAS CALLED FOR SLASHING."
A:
Kyle Palmieri is a hockey player. Being called for slashing is part of hockey.
So the answer is yes.
EVALUATION
Q: Is the following sentence plausible?
"ROBIN LEHNER LAUNCHED THE DESPERATION HEAVE"
A:
Robin Lehner is hockey player.
# Is the above step of reasoning:
# (A) Correct
# (B) Incorrect
# The above step of reasoning is: (B), because Robin Lehner is goaltender which is different from
player
Launching the desperation heave is part of hockey.
the above step of reasoning:
# (A) Correct
(B) Incorrect
# The above step of reasoning is: (B), because launching the desperation heave is for player, not
goaltender
So the answer is yes.
# the above step of reasoning:
# (A) Correct
(B) Incorrect
# The above step of reasoning is: (A), but the previous step is incorrect
33


Reviews:
[{"review_id": "4El0r2Jz8z", "reviewer": "Reviewer_pGEM", "summary": "The authors propose a self-evaluation guided strategy to improve the rationale decoding process from CoT sampling. They also explore ways to balance the quality of evaluation with diversity of generation. Overall, their approach work well on existing datasets and improve few-shot accuracy on multiple math and commonsense datasets. Additionally, their approach leads to more robust reasoning.", "questions": "* How are the different hyper-parameters ($\\alpha, \\lambda$, etc.) tuned? Or do you use some generic settings for all datasets?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The ability to guide the rationale generation process via self quality evaluation and temperature-controlled randomness is an effective solution towards improving the decoding time performance and consistency of CoT sampling process\n* The work is timely in the community since CoT is a predominant way to generate rationales using LLMs. This approach can help the effort in improving robustness of these rationales\n", "weaknesses": "* Since the stepwise self-evaluation involves multiple calls to the base LLM, this adds an overall overhead both in terms of compute and cost. There is no discussion regarding this in the paper. This restricts the reader to understand the feasibility of such an approach. Please include some time and cost analysis with and without the self-evaluation based search. I understand that the authors point some of these in the limitations, but I strongly believe they are crucial to have in the paper.\n* Can you consider results on more recent models that do provide logits (say GPT3) to showcase the utility of this approach even in the more recent models? This is optional, but a good to have analysis on a few datasets (say StrategyQA and GSM8K).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful suggestions!\n\n> Please include some time and cost analysis with and without the self-evaluation based search \n\nSure. Please see the global response for this. \n\nFor API call time costs, we have proposed an implementation to accelerate the inference.\nOur method averages $6$ minutes per instance for single-chain reasoning, compared to the $4$ minutes taken by PAL+SC. \nWe provide detailed procedures with the implementation code in the supplementary materials.\n\n\n> Can you consider results on more recent models that do provide logits (say GPT3)\n\nIn the original paper, we utilize Codex (`code-davinci-002`) as the LLM backbone to report our main results. \nCodex actually performs significantly better than GPT-3.5 (InstructGPT -- `text-davinci-003`).\nThe comparisons between Codex and GPT-3.5 are available in the PAL paper (Figures 7 and 8).\n\nWe agree with the reviewer on adding more recent models that provide logits.\nWe run additional experiments on LLaMA 2 as a representative of open-source models.\nWe illustrate the preliminary results in Table 2 of the attached pdf. \nWe will add the complete LLaMA 2 results to the next revision of the paper.\n\n\n> How are the different hyper-parameters tuned? Or do you use some generic settings for all datasets?\n\nMost of the hyperparameters are the same for all datasets.\nFor example, we set $\\lambda=0.5$, beam size $k=5$, number of rollouts $n=16$, and the temperature decay ratio $\\alpha=0.5$. \nWe only tune the sampling temperature for each dataset using the corresponding dev set, since easier and more objective tasks require a higher temperature for more diversified samples. \nPlease refer to Appendix A.2 and A.3 for a detailed breakdown."}, {"review_id": "fhjgJdQJAW", "reviewer": "Reviewer_fpKX", "summary": "This paper proposes to improve the reasoning capability of large language models (LLMs) by decomposing the reasoning task into multiple steps and then performing self-evaluation guided beam search to find the optimal reasoning chain. On a set of arithmetic reasoning, symbolic reasoning, and commonsense reasoning tasks, the proposed method outperforms baselines in most cases. The paper also provided analysis regarding the quality-diversity trade-off in the generation of the reasoning chain. ", "questions": "Please address my concerns and questions in Weaknesses.", "limitations": "The paper included a limitations section.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper proposed a novel and effective stochastic beam search which searches for multi-step reasoning. The approach integrates the LLM probability distribution and the self-evaluation faithfulness score. \n2. The proposed method is evaluated on multiple datasets. The discussion and analyses are helpful.", "weaknesses": "1. The proposed method is very costly, as it requires prompting the LLM for multiple times (when searching for next steps and for self evaluation). Its effectiveness also depends on the LLM search space, e.g., when an LLM is very confident with their (incorrect) reasoning, the potential of locating the correct steps in beam search will become small.\n\n2. Some details are missing or require clarification: \n- How did the framework define one \"step\" in each reasoning dataset? For example, is every step a single statement for PAL and a complete sentence (i.e., ended with a period) for CoT?\n- Figure 4(a) is not referred to in the paper. It is unclear based on which dataset the two plots were drawn. The numbers on the plots also need more explanation. For example, in the left figure, why is PAL+SC so stable when changing the LM temperature (which I believe would end up with very different sets of samples in SC)? Similarly in the right figure, why is CoT+SC changing if it does not involve beam search at all (and hence should be agnostic to the change of the sampling temperature in Eq 4)? \n\n3. Baseline: how does the proposed method compare with self-refinement (Madaan et al., 2023), which, instead of searching for better steps during reasoning, iteratively self-refines the reasoning output?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's insightful suggestions!\n\n\n> The proposed method is very costly\n\nWe recognize the substantial cost associated with beam search.\nPlease refer to the global response for the discussion on this. \n\n\n> Its effectiveness also depends on the LLM search space, e.g., when an LLM is very confident with their (incorrect) reasoning, the potential of locating the correct steps in beam search will become small.\n\nWe appreciate your observation regarding the constraints within the LLM search space.\nHowever, we posit that this limitation is intrinsic to few-shot prompting techniques.\nOur method incorporates self-evaluation to guide and calibrate the generation process.\nThis is based on the insight that LLMs are better at assessing the correctness of an answer than directly producing it (Kadavath et al. 2022).\n\n\n> How did the framework define one \"step\" in each reasoning dataset? \n\nThis depends on the reasoning format.\nFor PAL, reasoning takes the form of a Python program, with each complete statement symbolizing a \"step\". We employed a regex-based method to segment the program into these steps.\nFor CoT, the reasoning is in unstructured text. We directly tokenize the reasoning chain into sentences, with each representing a \"step\".\n\nFor further implementation nuances, kindly check the code in supplementary materials.\n\n\n> Figure 4(a) is not referred to in the paper. \n\nThanks for highlighting the concern.\n\nBoth plots were constructed based on GSM8K. \nThe lines “PAL+SC” and “CoT+SC” represent results reported in the PAL paper. \nWe display them as reference baselines.\nIn this case, “PAL+SC” and “CoT+SC” are illustrated with fixed LM temperature settings.\nSo yes, they should be stable and won't change in the plots.\n\nWe will clarify this in the caption in our revised version.\n\n\n> How does the proposed method compare with self-refinement (Madaan et al., 2023), which, instead of searching for better steps during reasoning, iteratively self-refines the reasoning output?\n\nThanks for bringing up the work on self-refinement.\n\nThis approach conducts instance-level refinement, while our method works on the granular aspects. \nTherefore, our advantages differ based on the problem type and the scale of the output.\nFor example, while self-refinement offers a holistic perspective to diagnose and correct flaws, it may struggle to detect minor yet critical mistakes in longer generations.\n\nFurthermore, it's worth noting that in the rapidly evolving field of AI research, it is indeed challenging to keep abreast of the very latest methods. \nWe acknowledge the importance and relevance of the self-refinement method, and since a direct comparison might be out of scope for this paper, we will consider discussing it regarding the future direction if space permits.\n\n\n---\nLanguage Models (Mostly) Know What They Know (Kadavath et al. 2022)"}, {"review_id": "jZs34LYgSv", "reviewer": "Reviewer_TWEq", "summary": "The authors propose using beam search to guide each reasoning step in chain-of-thought prompting. Functionally, the paper is quite similar to the concurrent \"Tree of Thoughts\" work from Yao et al. (2023).", "questions": "How do you ensure the comparison with the other models is fair? How many beams do you use? For k beams, is it more useful to sample 2*k chains of thought?", "limitations": "Reasonable discussion.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Overall, it's a generally solid work. The experiments are reasonable and fairly comprehensive; the method, while not groundbreaking, is the natural next step of a lot of work in this area and is well-motivated; its figures are good and convey its message well; the results are generally positive - it would be very surprising to me if they weren't.", "weaknesses": "Primary concerns:\n- Because the self-evaluation requires extra inference, it's not entirely obvious that all of the comparisons are fair, so it would be useful to see some discussion around this. There's also the overhead from being unable to cache preceding tokens, but that's an artifact of using an API. The paper doesn't seem to discuss details like the number of tokens generated or the number of beams used, which in general, make comparison hard. \n- The title is very confusing - this paper has little to do with \"decomposition\" since every step taken is sequential. This should really be fixed as it implies a very different message than the one actually made by the paper. Normally this wouldn't be a substantial issue, but in this case, it is especially confusing.\n- The writing could really use work - the phrasing is awkward and often nonstandard, like the first sentence of the abstract \"We endow Large Language Models (LLMs) with fine-grained self-evaluation to refine multi-step reasoning inference.\" In general, the paper reads fairly awkwardly and is unnecessarily wordy.\n\nOther concerns:\n- The novelty of the paper seems to be in the use of model-probability-guided beam search itself, but in my view, the paper somewhat oversells the novelty of using model self-evaluation for selection. Even within the code domain there's lots of work on this, such as \"Coder Reviewer Reranking for Code Generation\" by Zhang et al. (2022). Plus, there is work on evaluating uncertainty with prompting which would probably even be better suited for this, like the concurrent \"Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation\" by Kuhn et al. (2023). This is not to say that the paper is not novel, but the main novelty seems to be the use of self-guided beam search in general and not the \"Self-Evaluation as Faithfulness Constraint.\"\n- This method isn't really possible with recent closed language models that don't expose logprobs (as mentioned), and it's not obvious how to integrate this. I also don't really feel that it's fair to refer to this as faithfulness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments.\n\n> Because the self-evaluation requires extra inference, it's not entirely obvious that all of the comparisons are fair, so it would be useful to see some discussion around this.\n\nThanks for the suggestion. Please see the global response for this. \n\n\n> How many beams do you use? For k beams, is it more useful to sample 2*k chains of thought?\n\nKindly refer to the implementation details in Appendix A.3. \nWe also provide additional discussion on this in the global response.\n\n\n> The title is very confusing - this paper has little to do with \"decomposition\" since every step taken is sequential.\n\nWe appreciate your concern regarding the term \"decomposition\".\n\nWe adopt “decomposition” to highlight that our method calibrates the reasoning chain in a “step-by-step” manner, as illustrated in Figure 1 and discussed in the first part of Section 4 (Related Work).\nWe admit that this may introduce ambiguity, especially since the reasoning process leans more towards sequential generation rather than a hierarchical decomposition of the problem.\nWe will revisit the title to better align it with the paper's content.\n\n\n> This method isn't really possible with recent closed language models that don't expose logprobs (as mentioned), and it's not obvious how to integrate this.\n\nWe illustrated how to extract scores from closed-source LMs, such as GPT-4, in Appendix A.2 under GPT-Experiments.\nWhile the exact logits -- to get the step log-likelihood -- are not available, our case study suggests that GPT-4 scoring serves as a promising metric for evaluating reasoning quality.\nPractically, GPT-4 scores can be directly utilized as evaluation outcomes when implementing our method. \nWe can also leverage the textual feedback from GPT-4 to refine these scores, catering to diverse reasoning criteria.\n\n\n> This is not to say that the paper is not novel, but the main novelty seems to be the use of self-guided beam search in general and not the \"Self-Evaluation as Faithfulness Constraint.\"\n\nThanks for raising your concerns about the novelty and the word “faithfulness”.\n\nWe acknowledge the contributions of previous research, including the conditional likelihood-based consensus solicitation of Zhang et al (2022) and the uncertainty estimation method introduced by Kuhn et al (2023).\nWe will cite these works and compare them with the LLM self-evaluation.\n\nTo clarify, our claim isn't about being the first to introduce self-evaluation. \nOur primary emphasis is on constructing the self-guided beam search framework.\n\nRegarding \"faithfulness\", our original goal is to highlight the calibration ability of self-evaluation based on the consensus between the assessment and the generation.\nAn alternative way to feature this can be \"consistency\" or \"fidelity\".\n\nWe will consider the term used and refine the paper to make our contribution clearer.\n\n\n> The writing could really use work\n\nThanks for the constructive advice. \nWe will improve the clarity in the final version."}, {"review_id": "JSlJrVWkny", "reviewer": "Reviewer_WznY", "summary": "The paper proposes a self-evaluation enhanced beam search for using LLMs on multi-step reasoning tasks. Specifically, in addition to standard beam search that only scores a beam based on the probability, the method further adjusts the score with a self-evaluation-based faithfulness score reflecting the correctness of intermediate reasoning steps. The score is obtained by LLMs using few-shot prompting and is calculated for each rollout. The paper applies this approach on several arithmetic reasoning tasks, symbolic reasoning tasks, and common sense reasoning tasks. The results suggest that the proposed beam search variant achieves better performance compared to greedy decoding. The paper also includes a series analysis on the effectiveness of calibration, sensitivity to hyper-parameters, etc.", "questions": "Can authors provide the exact cost (measured by API cost, or tokens being scored) for PAL and the proposed approach in the single chain setting of Table 1?\n\n\nWhen calculating $P_{LM}$, is the probability of a reasoning step normalized by the number of tokens?\n\n", "limitations": "Some limitations are discussed at the end of the paper; no obvious negative societal impact as far as I know.", "rating": 3, "confidence": 5, "soundness": 1, "presentation": 3, "contribution": 1, "strengths": "The proposed approach shows an application of self-calibration for multi-step reasoning tasks.\n\nThe experiments cover three tasks and multiple datasets. The paper also includes a series of analyses providing more details on the effectiveness of calibration for reasoning tasks.\n\nThe paper is well-written and easy to follow.", "weaknesses": "1. The most critical issue is that the comparison in this paper is misleading.\n\nThe paper draws the majority of attention to the comparison between the proposed beam-search-based approach against greedy decoding. It’s understood that both the greedy decoding and the beam search produce one single chain. But the proposed approach uses *beam search* and self-evaluation (which is also done by few-shot prompting). This is way more expensive than greedy decoding. \n\nSpecifically,  based on the hyper-parameter in Appendix A.3, the model uses beam size (k=5, and use n=16 rollouts for each beam). Assuming we evaluate a problem with steps T=3. In a rough estimation, this approach needs to call the API to generate 5 * 16 * (3 - 1) * 2 = 320 completions (there is a factor 2 because the approach also uses LLM to self-evaluate each rollout, and based on the appendix, the length of the evaluation prompt is at the same magnitude as the length of the few-shot prompt). Not that this estimation follows the way that OpenAI charges API calls, which charges both prompt and completion tokens, see https://openai.com/pricing. In contrast, greedy decoding only requires running 1 completion. There’s a distinct gap in the computation cost (320 vs 1 measured by API cost). Similarly, the computation cost in the multiple reasoning chains setup is also different.\n\nIn short, the experiments and the interpretation of results need substantial refactoring. At least the paper should compare the proposed approach against baselines that uses the same amount of computation instead of producing the same number of reasoning chains. As a result, the improvements in Table 1 are inflated (E.g., considering PAL with 8 samples for self-consistency decoding can get ~78% performance on GSM8K as shown in Figure 12 in PAL).\n\n\n2. At the same time, the core technical contribution of the proposed approach is a straightforward extension of beam search based on self-evaluation, it is hard to judge the empirical merits of the proposed approach without a fair, clear, and thorough comparison.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the insightful feedback.\n\n> Can authors provide the exact cost (measured by API cost, or tokens being scored) for PAL and the proposed approach in the single chain setting of Table 1?\n\nSure. We provide a detailed comparison regarding the cost in Table 1 of the pdf.\nPlease refer to the global response for the discussion on this.\n\n\n> The most critical issue is that the comparison in this paper is misleading.\n\nWe acknowledge the importance of fair comparison in terms of computation costs. \nWe provide further discussion on this in the global response.\n\nHowever, in our original paper, we follow the previous works in reasoning to compare methods using the same number of reasoning chains for self-consistency.\n\nFurthermore, our method also enhances the effect of self-consistency by increasing the performance upper bound when scaling the $N$ in majority voting.\nTheoretically, the upper bound of majority voting (Tangian. 2020) is determined by the number of questions with $p > 0.5$, where $p$ represents the probability of correct prediction for each question (Condorcet's jury theorem).\nIncreasing the computational cost by increasing the members of the majority voting cannot improve this upper bound. \nOn the other hand, our proposed method modifies this $p$ to increase the number of questions with $p > 0.5$, thus increasing the upper bound. \nBy increasing $p$, the effect of a small finite $N$ in the majority voting also improves with our method, since the convergence rate of the majority voting increases as $p$ increases.\nIn the global response, Figure 1 shows the empirical estimation of how our method improves this $p$ significantly. \nThis demonstrates a bonus of our method when combined with majority voting.\nWe will conduct comprehensive experiments on open-source models to further analyze the upper bounds of our method.\n\n\n> At least the paper should compare the proposed approach against baselines that uses the same amount of computation instead of producing the same number of reasoning chains.\n\nWe appreciate your valuable advice.\nAs discussed in the global response for Table 1, our generation cost is equivalent compared to the self-consistenc.\nAlso, our method shows promising enhancement when combined with majority voting.\nWe will conduct comprehensive experiments on this using the open-source LMs.\n\n\n> When calculating, is the probability of a reasoning step normalized by the number of tokens?\n\nYes, the step probability is the geometric mean of the token probabilities.\nThis is to mitigate the difference in probabilities caused by the step length.\n\n\n\n---\nAnalytical Theory of Democracy (Andranik Tangian. 2022)\n\nCondorcet's jury theorem (Wikipedia)"}, {"review_id": "SuvFgnsKxX", "reviewer": "Reviewer_wb7Q", "summary": "The paper proposes using a fine-grained self-evaluation method to refine multi-step reasoning inference of the Large Language Models. The authors propose a novel promting approach that integrates self-evaluation guidance through stochastic beam search. Concretely, to guide the beam search process, they employ LLM self-evaluation as an automatic criterion to offer the guiding signal. And they incorporate temperature-controlled randomness to optimize the traditional beam search algorithm in order to balance the quality-diversity trade-off for better reasoning chains. Experimental results of their methods on various arithmetic, symbolic, and commonsense reasoning tasks show considerable improvements.", "questions": "Authors should concisely introduce the notions when they first use it (e.g., self-evaluation) to make the paper more self-contained. Besides, the details of the different evaluation benchmarks and compared baseline methods should be concisely introduced in the experiment section as well.", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "1. The authors propose a novel and general multi-step decoding method (a beam search variant) which employs LLM self-evaluation and temperature-controlled randomness. The method aims to improve LLM performance on reasoning tasks.\n2. Extensive experiments are conducted on a wide range of reasoning benchmarks and considerable improvements are achieved. Besides, comprehensive ablations and running examples are presented to further demonstrate the effectiveness of their approach.", "weaknesses": "The paper should be more self-contained. For example, the notion of self-evaluation is first used in the introduction section without a concise explanation, which makes it a bit hard to follow. And the details of the evaluation benchmark are not introduced (arithmetic, symbolic, and commonsense reasoning tasks).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your constructive feedback.!\n\n> The paper should be more self-contained.\n\nWe recognize the importance of clearly defining terms and notions when initially introduced. \n\nFor \"self-evaluation\", the notion technically means using the LLM to evaluate its own generation.\nThis includes prompting it to do direct correctness assessment and extracting the output likelihood as the implicit generation confidence.\n\nIn the revised manuscript, we will ensure these terms are succinctly clarified upon the first mention.\n\n\n\n> The details of the different evaluation benchmarks and compared baseline methods should be concisely introduced in the experiment section as well.\n\nThanks for the suggestions. We briefly introduce the benchmarks and baseline methods as follows. We will provide these details in the final paper.\n\n- Evaluation benchmarks\n    * **GSM8K**: math word problems (test - $1,319$)\n    * **AQuA**: algebraic word problems with multiple choice (test - $253$)\n    * **SVAMP**: math word problems with varying structures (test - $1,000$)\n    * **ASDiv**: diverse math word problems (test - $2,096$)\n    * **TabMWP**: table-based math word problems (test - $7,686$)\n    * **Date Understanding**: inferring a date from a given context (test - $369$)\n    * **Object Counting**: answering questions about the number of objects belonging to a certain type (test - $1,000$)\n    * **CommonsenseQA**: commonsense questions about the world involving complex semantics that often require prior knowledge (train/dev/test - $9,741$/$1,221$/$1,140$)\n    * **StrategyQA**: to infer a multi-hop strategy to answer questions (test - $2,290$)\n    * **Sports Understanding**: determining whether a sentence relating to sports is plausible or implausible (test - $1,000$)\n\n- Baseline methods\n    * **PAL**: program-aided language model – using Python program as intermediate reasoning\n    * **CoT**: chain-of-thought – using free-text “rationale” as intermediate reasoning"}]

Author rebuttal:
We appreciate your comments and suggestions.
Below are our responses to the concerns about cost.

We acknowledge that beam search incurs a significant cost.

- In light of reviewers' concern about cost, we conducted a detailed analysis about the cost as shown in Table 1 and Table 2 in the attached pdf, for scenarios using both APIs and open-sourced models. If APIs are used in the multiple chain case, a significant amount of computation is spent on processing identical few-shot prompts for each generation, leading our method to cost $O(n \cdot T)$ times more in computation, where $n$ is the number of rollouts for each beam and $T$ is the number of reasoning steps. While repetitive API calls can lead to increased input prompt costs, these costs can be also largely mitigated by caching past hidden states during inference if we use open-sourced models. In this context, our method's cost is $O(n)$ times greater than the PAL + self-consistency baseline.


- In reasoning, methods are typically compared using the same number of reasoning chains for self-consistency (Wang et al. 2023; Zhou et al. 2023). As such, we aimed to achieve the best performance under the same number of reasoning chains. 
To find a balance between performance and computational cost, we can decrease $n$, the number of rollouts for each beam. By reducing $n$ from $16$ to $8$, the performance slightly drops from $80.2$ to $79.9$, but it is still a substantial improvement over the baseline performance of $72.0$.


- Our method leads to a correct and interpretable reasoning chain while self-consistency only improves the accuracy of the final answer.

We will include the detailed analysis and experiments in our updated version. 

---
Self-Consistency Improves Chain of Thought Reasoning in Language Models (Wang et al. 2023)

Least-to-Most Prompting Enables Complex Reasoning in Large Language Models (Zhou et al. 2023)

Meta-review: This paper proposes an approach to integrate self-evaluation and decoding through stochastic beam search. Authors show that self-evaluation guided stochastic beam search provides a reasonable trade-off between quality and diversity and improves the performance on several well-known reasoning tasks. Reviewers had several concerns regarding the experiment details and fair comparison with prior work which was addressed by authors to a large extent (thanks to authors' great job during the rebuttal period). The main issue is that the amount of changes are significant and the experiment section could benefit from a complete rewrite. That makes this a difficult decision for me. After discussing with reviewers, my final recommendation is to accept the paper. However, I'm urging the authors to take time to rewrite the experiment section, making sure they address reviewers' concerns (and in particular reviewer WznY).
Decision: Accept (poster)