Deductive Verification of Chain-of-Thought Reasoning
Authors: Zhan Ling
Yunhao Fang
Xuanlin Li
Zhiao Huang
Mingu Lee
Roland Memisevic
Hao Su
Venue: NeurIPS 2023 poster (2023)
Keywords: Chain-of-thought
Large language model
Reasoning
TL;DR: We propose Natural Program, a natural language-based deductive reasoning format that enables LLMs to carry out effective self-verification of reasoning chains, thereby significantly enhancing the rigor and trustfulness of LLM generations.

Abstract: Large Language Models (LLMs) significantly benefit from Chain-of-thought (CoT) prompting in performing various reasoning tasks. While CoT allows models to produce more comprehensive reasoning processes, its emphasis on intermediate reasoning steps can inadvertently introduce hallucinations and accumulated errors, thereby limiting models’ ability to solve complex reasoning tasks. Inspired by how humans engage in careful and meticulous deductive logical reasoning processes to solve tasks, we seek to enable language models to perform explicit and rigorous deductive reasoning, and also ensure the trustworthiness of their reasoning process through self-verification. However, directly verifying the validity of an entire deductive reasoning process is challenging, even with advanced models like ChatGPT. In light of this, we propose to decompose a reasoning verification process into a series of step-by-step subprocesses, each only receiving their necessary context and premises. To facilitate this procedure, we propose Natural Program, a natural language-based deductive reasoning format. Our approach enables models to generate precise reasoning steps where subsequent steps are more rigorously grounded on prior steps. It also empowers language models to carry out reasoning self-verification in a step-by-step manner. By integrating this verification process into each deductive reasoning stage, we significantly enhance the rigor and trustfulness of generated reasoning steps. Along this process, we also improve the answer correctness on complex reasoning tasks.

Deductive Verification of Chain-of-Thought Reasoning
Zhan Ling' Yunhao Fang Xuanlin Li' Zhiao Huang'
Mingu Lee²
Roland Memisevic*
Hao Su'
UC San Diego, ?Qualcomm Al Research
Abstract
Large Language Models (LLMs) significantly benefit from Chain-of-Thouge (CoT) prompting in performing various reasoning tasks. While CoT allows models to produce more comprehensive reasoning processes, its emphasis reasoning steps can inadvertently introduce hallucinations and accumulated errors, thereby limiting models' ability to solve complex reasoning tasks. Inspired by how humans engage in careful and meticulous deductive logical reasoning processes solve tasks, seek to enable language models to perform explicit and rigor- ous deductive reasoning, and also ensure the trustworthiness of their reasoning process through self-verification. However, directly verifying the validity of an entire deductive reasoning process is challenging, even with advanced models like ChatGPT. In light of this, propose decompose a reasoning verification process into a series of step-by-step subprocesses, each only receiving their nec- essary context and premises. To facilitate this procedure, we propose Natural Program, a natural language-basee deductive reasoning format. Our approach enables models generate precise reasoning steps where subsequent steps are more rigorously grounded on prior steps. It also empowers language models to carry out reasoning self-verification verification process into each deductive reasoning stage, we significantly enhance the rigor and trustfulness of generated reasoning steps. Along this process, we also improve the answer correctness complex reasoning tasks, Code will be released at
intermediate
step-by-step manner. By integrating this
Introduction
The transformative
power of large language models, enhanced by Chain-of- Thought (CoT) has significantly reshaped the landscape of information process- fostering enhanced abilities across myriad of disciplines and sectors While CoT allows models to produce more comprehensive reasoning processes, its
prompting 50
21
59
42
ing 14. 26
49
56
13
55
23
29
emphasis intermediate reasoning steps inadvertently introduce hallucinations 4 30 16 20
and accumulated errors 4. [ 1. thereby limiting models' ability to produce cogent reasoning processes. [
In fact, the pursuit of reliable reasoning is not a contemporary novelty; indeed, it is an intellectual endeavor that traces its roots back to the time of Aristotle's ancient Greece. Motivated by the desire to establish a rigorous reasoning process, in his "Organon," " Aristotle introduced principles of logic, in particular, syllogism, a form of logical argument that applies deductive reasoning to arrive at a conclusion based on two or more propositions assumed to be true. In disciplines that rigorous reasoning critical, such judical reasoning and mathematical problem solving, documents must be written a formal language with a logical structure to ensure the validity of the reasoning process.
"qqual contribution
"Qualcomm AI Research is an initiative of Qualcomm Technologies. Inc All datasets and models were solcly downloaded and evaluated by the University of California San Diego
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Question
Verilicaiion
Sane ie cone informations "Thre are eaple trees curcently the part. Alles the surters plant Leatyy coes sill be 64 mupls Leuus in the puzk."
cuceuntly
the park, Fark vorkere wtll plant sapla Lzosa Loday, hlen the woskers rintahed there will be 64 rapia treas the park. zow many rapie tceas did the socoaca plant today?
pasewaus *culculace the nimbhe inpple trree the workens will plant. Mumber spple the vorcees sill planes of
information,
13*
Pouble peublerchack the zuesening pcocesa, Labta anelyge Ata poscectsezz, and end vith "yea" dr "bo".
Question-Relates Premisee
Reascring
Ressoning
4 1. Thece are 53 sapla sceas curruncly the park,
5. Ory #2 #il stup 1: Caleulate the number of napie
I 6. Day 14 #5) rinal Staps The original queatiin is 44, soe nang aaple Leees dad the plant todays ne auao
the ixple naple tries.
plant treed, part.
Ros rapla dtd
workere
maple tzess vorkers sill plants 14 a 11
plant.
question naple tzuez today.
plaated
varkece plant today?
Figure I: An overview of our proposed deductive reasoning and verification process. In response to an input question, LLMs generate deductive reasoning chains using the Natural Program format (bottom 3 boxes), natural language-based deductive reasoning approach. The Natural Program format allows individual reasoning steps (an example in purple) and their corresponding minimal set of premises (an example in orange) to be casily extracted. This streamlined extraction process facilitates the step-by-step decomposition and verification of deductive reasoning (top-right box).
Question
Queston-Rellle Premisos
Reasoning
Reasoning
aR. a4 Step- caso ase specaa place
piltt timeer plate tew
Catestater lie totall
Giasse plates cost 26, each, bosca eaca
autsinge needes.
information on the caucltter.
How
toyss
on place astsings.
Quesioo-FRlltted Premore
Ressoning
Rassoning
Area aneds bay beieee plate toulday clrose. doats sacting people ovea ctever plotes 15,00 ane the salad plenes
antiiing thr her holiday dussee.
8 Ory 1P1 step to Cateslate Lte tocal auccinga Roscs ceads
(yy rinsd coagiaas qusttion Aod do stae conantie La Jeeey well apeed
X
J. Yhus as wask dieess place as
c. lire mach will Aeary apand en place
plaat teoot
will place astringer
Reasoning Error
Grounding Enror
Queston- Premisos
Ressoning
Ressoning
santiing toe people.
2., inney needs place
dr B1) Step
B10, By 66 19) Flasi stap: The
celginst question
cuttey tutal planeyy teet
nubbes of place to bey. Theal sester Sabale, to the annvec to ctia Ln avery wel1 apend 3180-00
will out
The bosd $2.00. cost natied pi ate an.00
of yilere vetclson
of the place astedoge.
Figure 2: Through our Natural Program -base deductive reasoning verification approach, we identify and eliminate reasoning chains that contain errors in reasoning and grounding (we define grounding error utilizing information that is not present in cited premises). By alleviating such errors, we significantly enhance the rigor, trustworthiness, and interpretability of the generated reasoning outputs.
We yearn for this sequence of reliable knowledge when answering questions. Our goal is to develop language models that can propose potential solutions through reasoning in logical structures. Si- multaneously, we aim to establish a verifier capable of accurately assessing the validity of these reasoning processes. Despite recent significant explorations in the field, such as [48] 's emphasis on self-consistency and [27 5 's innovative use of codes to represent the reasoning process, these approaches still exhibit considerable limitations. For example, consistency and reliability are not inherently correlated; as for program codes, they are not powerful enough to represent many kinds of reasoning process, e.g., in the presence of quantifiers ("for all", "if there exists") or nuances of natural language (moral reasoning, "likely"....)
We propose leveraging the power of natural language to achieve the deductive reasoning emphasized in ancient Greek logic, introducing "natural program". " This involves retaining natural language for its inherent power and avoiding the need for extensive retraining with large data sets. A natural program

---

represents a rigorous reasoning sequence, akin to computer program. We expect implementations of the idea to have two properties: 1) that natural programs are generated with minimal effort from an existing language model capable of CoT reasoning, preferably through in-context learning; 2) that the natural program can be easily verified for reliability in the reasoning process.
Through a step-by-step investigation, we discovered that large language models have the potential to meet our expectation. Naive CoT prompts like "Let us think step by step." " has many flaws, and entrusting the entire verification process to a large model like ChatGPT can still lead to significant error rates. However, we found that, if the reasoning process is very short, and only based on necessary premises and contexts, the verification of existing large language models is already quite reliable. Therefore, our approach to design prompts that induce CoT processes comprised of rigorous premises/conditions and conclusions with statement labels, and verification can be done by gradually isolating very few statements within the long thought chain. Experimentally, we found that most reasoning that passed the verification was rigorous, and many that did not pass had elements of imprecision in the reasoning process, even if they occasionally arrived at correct answers.
It is worth emphasizing that, we are not looking for a method to just maximize the correctness rate of final answers; instead, we aspire generate a cogent reasoning process, which is more aligned with the spirit of judical reasoning. When combined with sampling- identify low- wwwprobability but rigorous reasoning processes. When repeated sampling fails yield a rigorous reasoning process, we can output "unknown" to prevent hallucinations that mislead users.
methods, our method can
We demonstrate the efficacy of our natural program-based verification approach across a range of arithmetic and common sense datasets on publicly-availaat models like OpenAl's GPT-3.5-turbo. Our key contributions are follows:
We propose a novel framework for rigorous deductive reasoning by introducing a "Natural Program" format (Fig. D. which is suitable for verification and can be generated by just in-context learning;
2. We show that reliable verffeeciiinntion of long deductive reasoning processes written in our Natural Program format can be achieved through step-by-step subprocesses that only cover necessary context and premises;
3. Experimentally, demonstrate the superiority of our framework in improving the rigor, trustwor- thiness, and interpretability of LL.M-generated reasoning steps and answers (Fig. 2
2
Related work
Reasoning with large language models. Recent large language models (LLMs) 3 S 57
47 38 18
9 37l have shown incredible ability in solving complex reasoning tasks. Instead of letting LLMs directly generate final answers as output, prior work have shown that by encouraging step-by-step reasoning through proper prompting, such
Mfain-of-Thoughe (CoT) prompting [50] and many [48 60, 25 [54] LLMs exhibit significantly better performance across diverse reasoning tasks. To further improve the step-by-step reasoning process, some recent studies have investigated leveraging external solvers such as program interpreters (39 5 (7), training and calling external reasoning modules [II], or performing explicit search generate deductive steps 2 46) Parallel to these works, we do not rely on external modules and algorithms, and we directly leverage the in-context learning ability of LLMs generate more precise and rigorous deductive reasonings.
others [21] |59 58 [44
Large language models as verifiers. Using language models evaluate model generations has been a long standing idea [22 36 40) 4). As LLMs exhibit impressive capabilities across diverse tasks, it becomes natural idea to use LLMs as evaluation and verification tools. For example, (10
finetune LLMs to verify solutions and intermediate steps. LLMs aligned with RLHF 32
48
have also been employed to compare different model generations. In addition, recent works like 43 52 28 6 leverage prompt designs to allow LLMs to self-verify, self-refine, and self-debug without the need for finetuning. However, these works do not focus on the rigor and trustworthiness of the deductive reasoning processes at every reasoning step. In this work, we propose natural language-bass deductive reasoning format that allows L.LMs to self-verify every intermediate step of deductive reasoning process, thereby improving the rigor and trustfulness of reasoning.
3

---

Question:
Jerry is rolling a six-sided die. How much more likely is it (expressed percentage) that he rolls number greater than $3 than that he rolls two even numbers in a row? Ground Truth: There are 3 numbers greater than 3 the dice, the chances of rolling one of them are 3 3/6- = 50%. The chance of rolling one even number is 50%, so the chance of rolling two in row is 50% 50% 25%. The difference between these two probabilities is 50%- 25%
= 25%. # 25
There are two possible outcomes for rolling a number greater than out of 6 total outcomes, so the probability is 2 6 or 1 /.. For rolling two even numbers in row, there are three possible outcomes (2-4, 4-6, 6-2) out of total outcomes, so the probability is / 36 or 1/12. To find the difference in probability, we subtract the probability of rolling two even numbers in a row from the probability of rolling a number greater than 3: 1/3 1/122/12222/2222 / /4. This means that it is 25% more likely to roll a number greater than 3 than to roll two even numbers in row.
Output:
Table 1: An example question from GSM8K with a generated CoT reasoning path with GPT- 3.5 (turbo), where the output provides a wrong reasoning chain with the correct answer.
Additionally, while some recent works 12 53 15 34 have proposed methods to verify individual steps in reasoning process, our approach distinguishes from these works in the following perspec- tives: (1) Our approach leverages in-context learning to achieve reasoning verification, without the need for language model finetuning. (2) Our Natural Program- based LLM verification approach not only identifies invalid reasoning steps, but also provides explicit explanations for why they are invalid, detailing the specific reasoning errors involved. (3) Our Natural Program-based reasoning and verification approach is compatible with in-context abstract reasoning tasks where reasoning steps do not possess proof-like entailment structures. For example, our approach is compatible with the Last Letters task, where the L.M is instructed to output the concatenation of the last letters of all words in sequence as the final answer. (4) Our Natural Program approach allows the use of commonsense knowledge not explicitly listed in premises. For example, consider this problem: "Marin eats 4 apples day. How many apples does he eat in November?" Even though "November has 30 days" is not explicitly listed in the premises, Natural Program permits the use of such common knowledge within reasoning step. Our in-context verification process is also capable of handling these implicit premises (e.g.. if LLM outputs "November has 29 days" in reasoning step, it will be marked as invalid).
3 Motivation and Problem Formulation
A reasoning-based question-answeriig (QA) task can be defined tuple (Q,C,O, A)
35 where Q
the target question; C is the context of question, such as the necessary background for answering a question; O- (01, 02,- .... c*) optional answer choices if Q is a K- K-way multiple choice problem; and A is the ground-trute truth answer. Given Q and C as inputs, large language models (LLMs)) B g 47
generate a sequence of tokens T = (t1, t2. ... t.)) to answer the question. Recent works like Chain- of of-Thought (CoT) (50, 21 leverage prompt engineering in the context C' to encourage models to generate the intermediate reasoning process in T, which benefits LLM performance across diverse reasoning tasks. In this case, T consists of a set of m intermediate reasoning steps, which we denote Each step s; can be represented by a subsequence of the generated tokens (4,, (,) C T. In much prior work, a generated solution is "correct" if and only if the predicted final answer in 8m matches the ground truth A, which we call answer correct(ness).
as S = (81, ... (m))
We observe that for all cases where LLMs produce erroncous final answers, there exists at least one mistake among the intermediate reasoning steps S. Morcover, even when the final answer is correct, there might still exist some mistakes among S. This phenomenon, as illustrated in Tab. [ occurs for all LLMs we tested, including state-of-th--a models such as ChatGPT and GPT-4 [3 Since later reasoning steps are conditioned on prior reasoning steps, these mistakes often initiate a snowball effect, causing subsequent mistakes to compound. This significantly diminishes the likelihood of correct problem-solving and impedes the progress towards achieving human-levee complex reasoning.
Therefore, in this work, we place significant emphasis on ensuring the validity of every reasoning step, not just the correctness of the final answer. In particular, we focus on the validity of deductive reasoning, essential component of a logical reasoning process. In deductive reasoning, we are

---

Prompting
Reasoning Correctness
GSM8K
AQuA
MATH
AddSub
Date
Last Letters
Correct
98%
96%
100%
98%
98%
100%
Zero-shot
Incorrect
4%
6%
4%
2%
4%
4%
(Average)
51%
51%
52%
50%
51%
52%
Correct
98%
96%
100%
92%
100%
96%
Two-shot
Incorrect
2%
4%
0%
6%
26%
6%
(Average)
50%
50%
50%
49%
63%
51%
Table 2: Zero-shot and two-shot reasoning chain verification accuracy for GPT-3.5- (ChatGPT), where an entire reasoning chain is verified at once. The two shot prompt we used is presented in Appendix [.I] To generate verification inputs, for each dataset, we perform Shain-of-Thoo prompting and randomly sample 50 reasoning chains that are valid and 50 reasoning chains that exhibit mistakes. We observe that when given an entire reasoning process, where the deductive graphs for all reasoning steps are entangled together, it is challenging even for strong language models like ChatGPT to verify its validity.
(CoT)
given (premise, conclusion) pair, and are interested in determining whether the conclusion follows from the premises. In the context of reasoning based QA tasks, for each reasoning step s,, we define its deductive validity V(s;) as a binary variable. A reasoning step is deductively valid (s:)) 1) if and only if s, can be logically deduced from its corresponding premises ps, which consist of the context C, the question Q, and all the previous reasoning steps 8, أ < i). Then, we can also define the deductive validity for the entire reasoning chain S (SS) = AM (s;). Compared to evaluating answer correctness, which can be accomplished by simple functions such as exact string match, evaluating deductive validity lot more challenging. Thanks to the recent progress on LLMs, which demonstrate impressive in-context learning capabilities across diverse scenarios, we propose to use L.MSs to examine reasoning chains and predict the deductive reasoning validity.
Deductively Verifiable Chain-of-Though, Reasoning
In this section, introduce our specific approaches to performing deductive verification of reasoning chains. Specifically, we first introduce our motivation and method for decomposing a deductive verifi- cation process into a series of step-by-step processes, each only receiving contexts and premises that are necessary. Then, we propose Natural Program, a natural language-based deductive reasoning format, to facilitate local step-by-step verification. Finally, we show that by integrating deductive ver- ification with manimitty-pluralii voting, we can improve the trustworthiness of reasoning processes along with final answers. An overview of our approach is illustrated in Fig. T and Fig.
4.1 Decomposition of Deductive Verification Process
Given a reasoning chain = ($1, ... S,,), ). a straightforward idea to verify its deductive validity is to ask LLMs to examine the entire reasoming chain at once. To assess the effectiveness of this approach, we conduct a preliminary experiment: for dataset problem and its reasoning chain S generated by ChatGPT, we prompt ChatGPT with "Do you think the above reasoning process is correct? Let's 's think step by step" such that its outputs whether there exists any mistake among any reasoning step in S. However, demonstrated in Tab. 2 the verification accuracy is 50% for most datasets, and ChatGPT struggles at finding out mistaken reasonings. Notably, it persistently outputs "Correct" for most reasoning chain queries, regardless of their actual validity.
We conjecture that such phenomenon is caused by the abundance of irrelevant premises for each reasoning step. Recall that the premises pj for reasoning step s; consist of the the question Q. the question context C, along with the prior reasoning steps sgj = {sj : j < i}. For Q and C, we can further extract and decompose Q U C into set of "question-related premises" QC = {gc1, 902, .4mm). where gc; is a premise or condition inferred from Q U C. Then, it is often the case that most elements of p; QC U sıj to erroneous verifications from language models. A very recent work [4]] also observes a similar phenomenon where LLMs easily distracted by irrelevant context.
irrelevant to the validity of st, leading
Hence, we propose decomposition of the reasoning chain verification process into series of step- by-step processes, where each step only considers the premises that are necessary. The overall validity
5

---

of the reasoning chain, denoted as V(S) = 1,,, can be naturally decomposed into individual step validity (s;). However, achieving such decomposition highly challenging without imposing constraints on the format of reasoning chains. Additionally, for each E S, we aim to ensure that it explicidly lists the minimal subset of premises p; S Pt required for deductive reasoning to avoid potential ambiguities during verification. This motivates us to introduce a natural-language- based deductive reasoning format in Section 4.2
4.2 Natural Program Deductive Reasoning Format
As previously mentioned in Sec, 4.1 we desire LLMs to output deductive reasoning processes that can be easily verified by themselves, specifically by listing out the minimal set of necessary premises p: at each reasoning step st. To accomplish its goal, we propose to leverage the power of natural language, which is capable of rigorously representing large variety of reasoning processes and can be generated with minimal effort. In particular, we introduce Natural Program novel deductive reasoning format for LLMs. More formally, Natural Program consists of the following components:
An instruction for models extract question-related premises QC. We use the following in- struction: "First, let's write down all the statements and relationships in the question with labels".
A numbered-list of question-related premises, each prefixed with "rtpremise_numbery
An instruction for models to generate the reasoning chain S based on the question-related premises QC. We use the following instruction: "Next, let's answer the question step by step with reference to the question and reasoning process".
A list of prefixed reasoning steps S,. The prefix has the following format: # #nnumber} (by {list_of of fiit__of_premit off_premissse..m used))) p. Here "number" equals |QC| + i, and jist_oofpremises _uuded" consists of numbers from the smallest subset of premises among QCUssj that are used for the deductive reasoning of s,. In addition, for the last reasoning step 8m we ensure that it (1) includes a special tag Final Step: (2) refers to the premise number of the target question to be answered; (3) explicitly gives the final answer to question.
To encourage language models to reason in the Natural Program format, we have designed one- shot prompts for different datasets, which are shown Appendix D.2 Given that LLM's rea- soning outputs follow the Natural Program format, we can then verify the deductive validity of a single reasoning step s; through an instruction that consists of (1) the full descriptions of premises used for the reasoning of s;; (2) the full description lidity verification, such as "Double-check the reasoning process, let's analyze its correctness, and end with "yes" " or "no"." Note that throughout this verification pro- cess, only retain the minimal necessary premise and context for s;, thereby avoiding irrelevant context distraction and significantly improving the effectiveness of validation. Additionally, we employ one-shot prompt for this verification process, which we find very helpful for improving the verification accuracy. The prompt is shown in Appendix D33
s; (3) an instruction for va-
Figure D provides an overview of the complete Natural Program-based deductive reasoning and verification process. By using the Natural Program approach, we demonstrate that LLMs are capable of performing explicit, rigorous, and coherent deductive reasoning. Furthermore, Natural Program enables LLMs to self-verify their reasoning processes more effectively, enhancing the reliability and trustworthiness of the generated responses.
4.3 Integrating Deductive Verification with Unaninity-Plurality Voting
Given that we can effectively verify a deductive reasoning process, we can naturally integrate verification with LLM's ss sequence generation strategies to enhance the trustworthiness of both the intermediate reasoning steps and the final answers. In this work, we propose Voting, 2-phase sequence generation strategy described as follows. Firstly, similar to prior work like [48), we sample k reasoning chain candidates along with their final answers. In the unanimity phase, we perform deductive validation on each reasoning chain. Recall that chain S is valid (i.e., V(S) = 1) if and only if all of its intermediate reasoning steps are valid (i.e., Vi, Vsx)) = 1). For each intermediate reasoning step s;, we perform majority voting over k' sampled single-step validity
-Plurallyyy

---

predictions to determine its final validity (s::). We then only retain the verified chain candidates {S: VSS) 1}. In the plurality voting stage, we conduct a majority- voting among the verified chain candidates to determine the final answer. This voting process ensures that the final answer is selected based on consensus among the trustworthy reasoning chains.
5 Experiments
In this section, we perform evaluations to demonstrate the effectiveness of our Natural Program-based deductive reasoning verification approach over diverse reasoning datasets. Firstly, we show that our deductive verification process leads to substantial improvements in the rigor and reliability of reasoning chains. Subsequently, of final answers. Our findings reveal that by adopting our Natural Program reasoning format without verification, we improve answer correctness on challenging benchmarks. Further applying deductive verification leads to slight reductions in final answer accuracy. One reason for this phenomenon is that the verification process effectively identifies and eliminates flawed reasoning chains that still produce correct answers.
will examine the impact of deductive verification
the accuracy
5.1 Experimental Setup
Benchmarks. We evaluate the deductive verification accuracy and the answer correctness of reasoning chains over a diverse set of reasoning tasks: arithmetic reasoning, symbol manipulation, and date understanding. For arithmetic reasoning, we utilize the following benchmarks: 1) AddSub [[]]; 2) GSM8K [10] 3) MATH I7: 4) AQuA 224. Among these benchmarks, the AddSub and GSM8K datasets involve middle school-level multi-step caleulations arrive at single number the final answer. The MATH dataset presents more challenging problems that require expressing the answer mathematical expression in LaTeX format. These problems involve concepts from linear algebra, algebra, geometry, calculus, statistics, and number theory. AQuA also features similarly challenging problems, except that questions in multiple-choice format. For symbol manipulation, Last Letter Concatenation [50), where the model is tasked with concatenate the last letters of all the words provided in the question. For date understanding, we use the one from BIG-bench [45
use
Deductive verfication evaluation setup. For each the above benchmarks, we select 100 reasoning chains, where 50 of them are deductively valid and 50 of them exhibit reasoning mistakes. The ground-truth deductive validity of each reasoning chain is determined by human annotators.
Answer extraction. To extract answers from reasoning solutions, we first perform text splitting based on answer prefix patterns such as "answer is" or "option is". Then, using problem type-specific regular expressions, we extract the final answer. To extract the validity results from deductive verification processes, we only keep the last sentence model response. We then extract the validity answer with regular expressions to obtain attitude words, e.g., "yes" or "no", to determine the validity answer. Sometimes, language models may not provide a direct answer and instead output phrases like "not applicable" at the end of the response. In such cases, we consider the answer from the model as "yes". Please refer to Appendix C for more details.
Model and Hyperparameters. We conduct our main experiments with GPT-3.5-turbe (Chat- GPT) 52. We also present results for the LLama fodel-family (47) in Appendix A where we find the deductive verification accuracy to be worse than larger models even after finetuning. For ChatGPT, we use generation temperature of = 0.7. For Unaaimity-Pluralle
Voting, we set k 10 and k' = 3 by default. We use 1-shot prompting for both reasoning chain generation and deductive verification (except reasoning chain generation for the date understanding task where we use 2-shot). See Appendix D.2 and Appendix D.3 for more details.
5.2 Comparison of Deductive Verification Accuracy
We compare the verification accuracy of reasoning chains using two methods: (1) verifying the entire reasoning chain at once (as described in Section 4.1) without utilizing the Natural Program, and
Most results for Faithful CoT are from their official repository httpps://github wttpt//...ooeeeeeaaaa/aa Faithful- COT, except MATH and AddSub due to the unavailability. For these two datasets, we use our implementation and the same prompt for the math word problems in their paper. The prompt for Last Letters is not available, so leave it blank.
7

---

Verification Method| Reasoning Correctness GSM8K
AQuA
MATH AddSub
Date
Last Letters
Overall
Correct
98%
96%
100%
92%
100%
96%
97%
CoT Two-shot
Incorrect
2%
4%
0%
6%
26%
6%
7%
(Average)
50%
50%
50%
49%
63%
51%
52%
Correct
84%
72%
70%
95%
90%
96%
85%
Natural Program
Incorrect
84%
62%
76%
40%
56%
6%
54%
One-shot
(Average)
84 %
67 %
73%
68 %
73%
51%
69 %
Table 3: Comparison of deductive verification accuracy of reasoning chains for GPT-3.5 (Chat- GPT). We compare two approaches: (1) verifying entire reasoning chains generated by Chain-of- Thought prompting; (2) verifying reasoning chains generated in the Natural Program format with step-by-step decomposition. In the latter casc, when we verify each reasoning step 8;, we only keep the necessary subset of premises S Pt. To calculate verification accuracy, for each dataset, we randomly sample 50 reasoning chains that are deductively valid and 50 reasoning steps exhibiting incorrect reasonings.
Arithmetic
Commonsense
Methods
GSM8K
AQuA
MATH
AddSub
Date
Last Letters
CoT + Voting
87.62%
10.18%
35.93%
92.36%
69.97%
81.60%
Faithful CoT + Voting
75.80%
61.80%
31.78%
88.35%
73.50%
Ours (Natural Program (NP), No Verification)
87.05%
36.75% % 70.34%
93.67% %
72.49% 71.45%
92.98%
Ours (NP Deductive Verification + UPV)
86.01% 1.%%
69.49%
36.48%
93.54%
92.60%
Table 4: Final answer accuracy comparison on GPT-3.5-turbo (ChatGPT), All approaches generate k 10 reasoning chains for each problem before performing majority voting or reasoning chain filtering with our deductive verification approach.
(2) our Natural doggram-based verification approach with step-by-step decomposition. The results, presented in Table indicate that our approach achieves significantly higher reasoning verification accuracy across most datasets. It effectively identifies erroneous reasoning in faulty chains while maintaining low rate of false positives for valid chains. However, we observe that our approach's 's effectiveness limited on the "Last Letters" task. We hypothesize that this is due to the task's nature, where each subsequent reasoning step is conditioned all previous steps, presenting greater challenges for reasoning verification due to the increased dependency among premises.
5.3 Impact of Natural Program and Deductive Verification Final Answer Correctness
We then investigate the impact of our Natural Program reasoning format and our deductive verification process on final answer correctness. We conduct two experiments: (1) for each problem, we instruct language models to generate and perform simple majority voting on final answers, without using deductive verification to filter out reasoning chain candidates; (2) applying our deductive verification approach to filter out reasoning chain candidates, and apply Thanimity-PPuralli final answer. As a reference, we also report the performance of Chain-of-Thougll (CoT) (50 and Faithful CoT (27]. For these baselines, we perform simple answer-based majority voting with & = 10 for fair comparison.
10 reasoning chain candidates in the Natural Program (NP) format
Voting (UPV) along the process to determine the
Results are presented in Tab. 4 While our major goal is to improve the trustworthiness and reliability of deductive reasoning, we find that prompting language models reason in our Natural Program format achieves on-par or better final answer accuracy than baselines over many reasoning tasks. Upon further applying our deductive verification approach to filter out invalid reasoning chains, we observe a slight decrease in final answer accuracy. One major contributing factor to this decrease the filtering out of reasoning chain candidates that provide correct answers but exhibit incorrect reasoning. We illustrate an example in Table 5 where ChatGPT generates the correct final answer but assigns incorrect premise numbers to support the first reasoning step. We note that in many such cases, approach effectively identifies these reasoning errors, thereby enhancing the rigor and
8

---

Question: In March rained 0.81 inches. It rained 0.35 inches less in April than in March. How much did rain in April?
Ground Truth: It rained 0.81 0.35 = 0.46 inches.
GPT-3,5-turbo (ChatGPT))
Question-related premises:
#1. It rained 0.81 inches in March.
#2. It rained 0.35 inches less in April than in March.
#3. How much did
April?
The first reasoning step:
#4. (by #2) Step I: Calculate how much it rained in April by subtracting the difference of 0.35 inches from the amount in March.
Amount of rain in April: 0.35 0.46 inches
Table For this reasoning chain candidate of this GSM8k problem, ChatGPT generates the correct final answer but provides incorrect premise numbers for grounding the first reasoning step. In "Step I", the correct premise numbers should be #1 and #2. Our deductive reasoning verification approach effectively identifies these reasoning errors, enhancing the rigor and trustworthiness of the reasoning process. It is worth noting that removing a correct answer from the candidate reasoning chains has slightly negative impact on the overall final answer correctness.
Premise Context
Shots
Reasoning Correctness
GSMRK
AQuA
MATH
AddSab
Date
Last Letiers
Average
Correct
64%
54%
58%
95%
26%
96%
66%
Premises
Wrong
56%
24%
76%
(Average)
60%
61%
57%
60%
51%
51%
57%
Minimal Premises
Wrong (Average)
26%
12%
28%
20%
20%
80%
31%
55%
55%
Correct
84%
72%
70%
95%
90%
96%
85%
Minimal Premises
Wrong
56%
(Average)
84 %
67%
73%
68%
73%
51%
69 %
Table 6: Ablation study the impact of (1) premise context and (2) zero-shot vs. few-shot scenarios on deductive verification accuracy using our Natural Program-based approach with step-by-step reasoning chain decomposition. To verify each reasoning step 5;, either the full premises p: QC U Sej. j. or use the minimal subset of premises pj C P; necessary as outlined in Sec. [.] The one-shot prompt used is shown in Appendix D.3 For each dataset, randomly sample reasoning chains that are deductively valid and 50 reasoning steps exhibiting incorrect reasonings.
reliability of the language models' reasoning processes, albeit with slight negative impact on the overall final answer correctness. Further discussions are presented in Appendix B
5.4 Ablation Study
In addition, we perform several ablation studies to gain further insights into the designs of our deductive verification approach. In Tab. we compare two different approaches to verify a single reasoning step & E S following our Natural Program format. The first approach utilizes all premises P: QC U Sk, for verification regardless of their relevance to s;, potentially introducing irrelevant contexts. The second approach follows our design Sec. 4.1 and only includes the necessary context and premises p; C p;. We observe that removing irrelevant premises significantly improves the reasoning chain verification accuracy on many datasets, highlighting the importance this technique.
We also ablate on our Chanimity-Pluraliit Voting strategy by investigating the impact of different k' Recall that k determines the number of votes to produce validity predictions single-ster stepe reasoning. Results are shown in Tab. 7 We observe that increasing k generally enhances reasoning validation accuracy, though we note that this is at the expense of more compute.
Limitations
While we have demonstrated the effectiveness of Natural Program-based deductive reasoning verifi- cation to enhance the trustworthiness and interpretability of reasoning steps and final answers, is

---

Answer Correctness k' = 1 k'
3
K'
k'
10
Correct
86%
90%
90%
92%
Wrong
38%
38%
38%
40%
Table Ablation of different values of k' on the verification accuracy of reasoning chains using our Unanimity-Pluralli Voting strategy. Experiments are performed on AddSub using -Prr-3.5tturbo (ChatGPT).
Question: Melanie had 10 quarters and 17 pennies in her bank. Her dad gave her 27 pennies and her mother gave her 19 pennies. How many pennies does Melanie have now? Ground Truth: Melanie have 17 + 27 + 19 = 63 pennies.
ChatGPT's reasoning step:
#5. (by #1) Step 1: Calculate the number of pennies Melanie had initially. Number of pennies in 10 quarters: 10 25 250
Number of pennies initially: 250 + 17 = 267
Table 8: An example question with ambiguous wordings. The term "pennies" in this question can be interpreted as either a type of coin or a unit of currency. In this particular question, "pennies" is treated as a type of coin. However, the initial reasoning step by ChatGPT mistakenly treats "pennies" as unit of currency, resulting in the conversion of all Melanic's 's money into "pennies" (highlighted in red). Consequently, all subsequent reasoning steps follow this flawed logic, leading an incorrect reasoning trace. Our deductive verification is not yet able to detect such errors.
important acknowledge that our approach has limitations. In this section, analyze common source of failure cases to gain deeper insights into the behaviors our approach. The failure case, as shown in Tab. involves the ambiguous interpretation of the term "pennies." which can be understood as either a type of coin or a unit of currency depending on the context. The ground truth answer interprets "pennies" as coins, while ChatGPT interprets it as unit of currency. In this case, our deductive verification process is incapable of finding such misinterpretations. Contextual ambiguities like this are common well-world scenarios, highlighting the current limitation of our approach.
7 Conclusion
In this paper, we aim to enable Large Language Models (LLMs) to perform explicit and rigorous deductive reasoning while ensuring the trustworthiness of their reasoning processes through self- verification. To this end, we have proposed a novel framework based on "Natural Program", a natural language-base based deductive reasoning format that facilitates reasoning verification and can be easily generated through in-context learning. Within this framework, we decompose the verification process of complex reasoning chains into step-by-step subprocesses that focus solely on necessary context and premises, allowing us to significantly enhance the accuracy of verification. Additionally, we introduce a Sonnimity-Pluralie Voting strategy to further improve verification accuracy. Experimentallyy demonstrate the superiority of our framework in improving the rigor, trustworthiness, and interpretability of reasoning steps and answers.
Broader Impact. While our deductive verification approach can mitigate hallucinations and reasoning errors of Large Language Models (LLMs), it does not completely eliminate these phenomena. LLMs can still produce harmful and biased content, make incorrect claims, and produce wrongful advice. This issue becomes particularly significant when LLMs engage in complex reasoning chains, increasing the risk of misleading users. Consequently, it is still crucial for users to exercise great caution when interacting with, deploying, or developing -.-e- applications.
Acknowledgements
We would like to express our sincere gratitude to Tongzhou Mu and Caiwei Xiao from UC San Diego, Kairong Luo from Tsinghua University, and Pulkit Madan, Reza Pourreza, Sunny Panchal, and Apratim Bhattacharyya from Qualcomm for their valuable discussions and feedback.
10

---

References
[1] Kushal Arora, Layla EI Asri, Hareesh Bahuleyan, and Jackie Chi Kit Cheung. Why exposure bias matters: An imitation lcarning perspective of error accumulation in language generation. arXiv preprint urXiv:2204.01 071 2022.
[2] Kaj Bostrom, Zayne Sprague, Swarat Chaudhuri, and Greg Durrett. Natural language deduction through search over statement compositions. arXiv preprint arXiv:2201.0602 2022.
[3] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neclakantan, Pranay Shyam, Girish Sastry, Amanda Askell, al. Language models are few-shot learner.. Advances in neural information processing systems, 13:1877-1 2020.
[4] Sébastien Bubeck, Varun Chandrasckaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, al. Sparks of artificial general intelligence: Early experiments with gpt-4, arXiv preprint arXiv:2303. 2023.
[5] Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W Cohen. Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks. arXiv preprint arXi::2211. 1.15888, 2022.
[6] Xinyun Chen. Maxwell Lin. Nathanael Schärli, and Denny Zhou. Teaching large language models to self-debug, arXiv preprint arXiv:2304.05/222 2023.
[7] Wei-Lin Chiang. Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E. Gonzalez, Ion Stoica, and Eric P. Xing. Vicuma: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality, March 2023.
[8] Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gauray Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint vrXiv2200.00331,, 2022.
[9] Hyung Won Chung. Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, et al. Scaling instraction-finetune language models. arXiv preprint arXiv:22 1416, 2022.
[10] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jenry Tworek, Jacob Hilton, Reichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:21 14166 2021.
[11] Antonia Creswell and Murray Shanahan. Faithful reasoning using large language models. arXiv preprint arXiv:2208.1422 2022.
[12] Antonia Creswell, Murray Shanahan, and Irina Higgins. Selection-inferent Exploiting large language models for interpretable logical reasoning. In The Eleventh International Conference on Learning Repre- sentations, 2023.
[13] Danny Driess, Fei Xia, Mchdi SM Sajjadi, Corey Lynch, Aakanksha Chowdhery, Brian lchter, Ayzaan Wahid, Jonathan Tompson, Quan Vuong, Tianhe Yu, et al. Palm-e: An embodied multimodal language model. arXiv preprint arXiv: 2:33.:3303.03378 2023.
[14] Andrew Drozdov, Nathanacl Schärli, Ekin Akyürck, Nathan Scales, Xinying Song, Xinyun Chen, Olivier Bousquet, and Denny Zhou. Compositional semantic parsing with large language models. arXiv preprint arXiv:2209. 15003, 2022.
[15] Olga Golovneva, Moya Peng Chen, Spencer Poff, Martin Corredor, Luke Zettlemoyer, Maryam Fazel- Zarandi, and Asli Celikyilmaz. Roscoe: A suite of metrics for scoring step-by-step reasoning. In The Eleventh International Conference on Learning Representations, 2022.
[16] Nuno M Guerreiro, Duarte Alves, Jonas Waldendorf, Barry Haddow, Alexandra Birch, Pierre Colombo, and André FT Martins. Hallucinations in large multilingual translation models. arXiv preprint 233iv 16104, 2023.
[17] Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song. and Jacob Steinhardt, Measuring mathematical problem solving with the math dataset. arXiv preprint 2021.
arXiv: 203iv:2103.08::
[18] Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks. Johannes Welbl, Aidan Clark, et al. Training compute -amputteopptmall large language models. arXiv preprint arXiv:2203.15536 2022.

---

[19] Mohammad Javad Hosseini, Hannaneh Hajishirzi, Oren Etzioni, and Nate Kushman. Learning to solve arithmetic word problems with verb categorization. In EMNLP, pages 523-533, 2014.
[20] Ziwei Ji, Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Ye Jin Bang, Andrea Madotto, and Pascale Fung. Survey of hallucination in natural language generation. ACM Computing Surveys, 55(12):1-38, 2023.
[21] Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. arXiv preprint arXiv:2205. / 1916, 2022.
[22] Nate Kushman, Yoav Artzi, Luke Zettlemoyer, and Regina Barzilay. Learning to automatically solve algebra word problems. In Proceedings of the 52nd Anmual Meeting of Association for Computational Linguistics ( (Volume I; Long Papers), pages 271 1221, Baltimore, Maryland, June 2014. Association for Computational Linguistics.
[23] Andrew Lampinen, Ishita Dasgupta, Stephanic Chan, Kory Mathewson, Mh Tessler, Antonia Creswell, James McClelland, Jane Wang, and Felix Hill. Can language models learn from explanations in context? In Findings of the Association for Computational Linguisties: EMNLP 2022, pages 537-563, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.
[24] Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom. Program induction by rationale generation: Learning to solve and explain algehraic word problems. arXiv preprint orXiv: 175.::7055.0444 2017.
[25] Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing. ACM Computing Surveys, 1-35, 2023.
[26] Pan Lu, Swaroop Mishra, Tanglin Xia, Liang Qiu, Kai-Wei Chang, Song-Chin Chun Zhu, Oyvind Tafjord, Peter Clark, and Ashwin Kalyan. Learn to explain: Multimodal reasoning via thought chains for science question answering, Advances in Neural Information Processing Systems, 15:2507-2522 2022.
[27] Qing Lyu, Shreya Havaldar, Adam Stein, Li Zhang, Delip Rao, Erie Wong, Marinnnna Apidianaki. and Chris Callison-Burchh Faithful thain-of-thought reasoning. arXiv preprint arXiv:2301. 2023.
[28] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Layu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with self-feedback. arXiv preprint arXiv:2303.1700 17651, 2023.
[29] Ana Marasovié, Iz Beltagy, Doug Downey, and Matthew E, Peters. Few-shot self-rationalization with natural language prompts. 2022.
[30] Joshua Maynez, Shashi Narayan, Bernd Bohnet, and Ryan McDonald. On faithfulness and factuality in abstractive summarization, arXiv preprint 2rXiv:2005.00661 2020.
[31] OpenAL. Gpt-4 technical report. 2023.
[32] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730-277 27744, 2022.
[33] Debjit Paul, Mete Ismayilzada, Maxime Peyrard, Beatriz Borges, Antoine Bosselut, Robert West, and Boi Faltings. Refiner: Reasoning feedback intermediate representations. arXiv preprint 2iv:2334401194. 2023.
[34] Archiki Prasad, Swarnadeep Saha, Xiang Zhou, and Mohit Bansal, Receval: Evaluating reasoning chains via correctness and informativeness. 2023.
[35] Danilo Ribeiro, Shen Wang, Xianfei Ma, Henry Zhu, Rui Dong, Deguang Kong, Juliette Burger, Anjelica Ramos, William Wang, Zhiheng Huang, et al. Street: A multi-task structured reasoning and explanation benchmark. arXiv preprint arXiv:2302.06722 2023.
[36] Subhro Roy and Dan Roth. Solving general arithmetic word problems. arXiv preprint 1608.0166 2016.
[37] Victor Sanh, Albert Webson, Colin Raffel. Stephen H Bach. Lintang Sutawika, Zaid Alyafeai, Antoine Chaffin, Amaud Stiegler. Teven Le Seao, Arun Raja, et al. Multitask prompted training enables shoo task generalization, arXiv preprint 10.00021 2021.
12

---

[38] Teven Le Scao, Angela Fan, Christopher Akiki, Ellie Pavlick, Suzana Iii,, Daniel Hesslow, Roman Castagné, Alexandra Sasha Luccioni, François Yvon, Matthias Gallé, et al. Bloom: A 176b-parameter open-access multilingual language model. arXiv preprint 1rX00:221..05100, 2022.
[39] Timo Schick, Jane Dwivedi- Yu, Roberto Dessi, Roberta Raileanu, Maria Lomeli, Luke Zettlemayer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves to use tools. arXiv preprint wxXi:23322004761 2023.
[40]
Jianhao Shen, Yichun Yin, Lin Li, Lifeng Shang, Xin Jiang, Ming Zhang, and Qun Liu. Generate & rank: A multi-task framework for math word problems. arXiv preprint arXiv:2109.088: 03034, 2021.
[41] Freda Shi, Xinyun Chen, Kanishka Misra, Nathan Scales, David Dohan, Ed Chi, Nathanacl Schärli, and Denny Zhou. Large language models can be easily distracted by irrelevant context. arXiv preprint axXiv:2302.00093 2023.
[42] Freda Shi, Mirac Suzgun, Markus Freitag, Xuezhi Wang, Suraj Srivats, Soroush Vosoughi, Hyung Won Chung, Yi Tay, Sebastian Ruder, Denny Zhou, et al. Language models are multilingual bhain-of-thought reasoners, arXiv preprint arXiv:2210.03057 2022.
[43] Noah Shinn, Beck Labash, and Ashwin Gopinath. Reflexion: an autonomous agent with dynamic memory and reff-renlcction. arXiv preprint mrXi:23333113366 2023.
[44] Chenglei Si, Zhe Gan, Zhengyuan Yang. Shuohang Wang. Jianfeng Wang. Jordan Boyd-Graber, and Lijuan Wang. Prompting gpt-3 to be reliable. arXiv preprint arXiv:2210.0113 2022.
[45] Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonoo, al. Beyond the imitation game: Quantifying and extrapolating capabilities of language models. arXiv preprint Xiii:220000461555 2022.
[46] Oyvind Tafjord, Bhavana Dalvi, and Peter Clark. Proofwriter: Generating implications, proofs, and abductive statements over natural language. In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli, editors, Findings of the Association for Computational Linguisticy: ACL/JJCNLP 2021, Online Event, August 1-6, 2021, volume ACL/UCCLL 2021 of Findings of ACL, pages 3621-3634. Association for Computational Linguisties, 2021.
[47] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint WxXiv:2002.13977 2023.
[48] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe Le. Ed Chi, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint urXiv:2203. 11171, 2022.
[49] Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, al. Emergent abilities of large language models. arXiv preprint arx:::2006. 07682, 2022.
[50] Jason Wei, Xuczhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoe Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models. arXiv preprint arXiv:2201. 1903, 2022.
[51] Sean Welleck, Ilia Kulikov, Stephen Roller, Emily Dinan, Kyunghyun Cho, and Jason Weston. Neural text generation with unlikelihood training. arXiv preprint 1ttp:1998..331111 2019.
[52] Yixuan Weng, Minjun Zhu, Shizhu He, Kang Liu, and Jun Zhao. Large language models are reasoners with self-verification. arXiv preprint 1xXv:2212.00966. 2022.
[53] Kaiyu Yang, Jia Deng, and Danqi Chen. Generating natural language proofs with verifier-guided search. In Conference on Empirical Methods in Natural Language Processing (EMNLP), 2022.
[54] Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models, arXiv preprint arXiv:2210.03622 2022.
[55] Eric Zelikman, Jesse Mu, Noah D Goodman, and Yuhuai Tony Wu. Star: Self-taught reasoner bootstrapping reasoning with reasoning. 2022.
[56] Andy Zeng, Adrian Wong. Stefan Welker, Krzysztof Choromanski, Federico Tombari, Aveek Purohit, Michael Ryoo, Vikas Sindhwani, Johnny Lee, Vincent Vanhoucke, et al. Socratic models: Composing zero-shot multimodal reasoning with language. arXiv preprint arXiv:2204.005948 2022.
13

---

[57] Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pre-trained transformer language models. arXiv preprint urXiv:2205. 000600 2022.
[58] Zhuosheng Zhang, Aston Zhang, Mu Li, and Alex Smola. Automatic chain of thought prompting in large language models. arXiv preprint arXiv:2210.03492 2022.
[59] Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Olivier Bousquet, Quoe Le, and Ed Chi. Least-to most prompting enables complex reasoning large language models. arXiv preprint arXiv:2205. 10625, 2022.
[60] Hattie Zhou, Azade Nova, Hugo Larochelle, Aaron Courville, Behnam Neyshabur, and Hanie Sedghi. Teaching algorithmic reasoning via in-context learning. arXiv preprint arXiv:2211.09666, 2022.
14

---

A Deductive Verification with Vicuna Models
We further explore the efficacy of deductive verification for open-source models. We select two popular models: Vicuna-7B and Vicuna-13B (7] These models are fine-tuned versions of LLaMA-7B and LLaMA-13B [47] using the ShareGPT data We use the same Natural Program-based one-shot verification method we used in the main paper. Results are shown in the first and the third rows of Table We observe for the original Vicuna models without finetuning, Vicuna-7B exhibits poor performance in deductive verification and fails to find out reasoning mistakes, while the larger Vicuna- exhibits better verification accuracy.
Models
Reasoning Correctness
GSM8K
AQuA
MATH
AddSub
Date
Last Letters
Overall
Correct
80%
86%
96%
98%
96%
80%
89%
Vicuna-7B
Wrong
14%
22%
16%
6%
20%
34%
19%
(Average)
47%
54%
56%
52%
58%
57%
54%
Correct
68%
48%
46%
76%
46%
32%
53%
Vicuna-7B (fine-tuned)
Wrong
72%
86%
54%
60%
72%
68%
69%
(Average)
70%
67 %
50%
68%
61 %
50%
61 %
Correct
86%
82%
92%
96%
72%
74%
84%
Vicuna- 13B
Wrong
32%
36%
20%
20%
34%
30%
29%
(Average)
59%
59%
56%
58%
53%
52%
57%
Correct
74%
50%
56%
86%
72%
12%
58%
Vicuna- 13B (finettuned)
Wrong
72%
76%
72%
68%
62%
96%
74%
(Average)
73%
63%
64%
77%
%
66%
Correct Wrong 84%
84%
72%
70%
95%
90%
96%
85%
ChatGPT (GPT-3.5-Turbo)
62%
76%
40%
56%
6%
54%
(Average)
84%
67%
73%
68%
73%
51%
69%
Table 9: One-shot Deductive Verification Accuracy of Vicuna-7B and Vicuna-13B The models are evaluated with or without finetuning on our deductive verification dataset. For each dataset, we randomly sample 50 reasoning chains that are deductively valid and 50 reasoning steps exhibiting incorrect reasonings.
We therefore conduct additional experiment investigate if the verification accuracy of Vicuna models can be improved by fine-tuning. To this end, we generate a deductive verification dataset, which consists of 2000 reasoning steps evenly distributed between correct and incorrect categories. We automatically generate this dataset using GPT-3.5-turbo since it exhibits a very high accuracy of single-step verification. We first use GPT-3.5-turbo generate solutions for problems in GSM8K's training set. We then execute step-by-step deductive verification on these solutions using GPT-3355 turbo. For solutions that result correct final answers, we retain the reasoning steps that pass deductive verification. For solutions that yield incorrect final answers, we retain the reasoning steps that cannot pass deductive verification. After constructing our dataset, we then fine-tune the Vicuna models using the verifications of the 2000 reasoning steps. Models were fine-tuned with 4 1100-80GB over epochs. Training parameters are shown Table I0
As shown in Tab. 9 we observe that fine-tuning with our dataset can enhance the deductive verification accuracy of Vicuna models not only on the dataset where the training dataset is constructed (GSMSK), but also on many other datasets. However, the accuracy is still worse than non- non-finetin fineffnnteedd GPT-3.5, which suggests that model capacity has significant impact on deductive verification capabilities.
B
More Discussion on Improvements of Deductive Verification Accuracy Versus Improvements on Final Answer Correctness
In the main paper, demonstrated that verification approach significantly improves the verifica- tion accuracy of reasoning chains (Tab. 3 but barely improves the final answer accuracy (Tab. 4).
We further analyze this phenomenon below:
15

---

Hyperparameters
Value
Optimizer
AdamW
learning rate
x 10-a
Weight decay
0.00
Num epochs
3
Batch size 64
Learning rate schedule
Linear
Table 10: Hyperparameters for finetuning Vicuna models with our deductive verification dataset.
Consider the GSM8K dataset as an example (recall that the final answer for a problem is obtained through majority voting). Among all problems, 91.6% of problems have (number of votes received by the correct answer) (largest number of votes received by a single wrong answer)l > 2, and their final answers are unlikely be changed through deductive verification approach. For the rest of the cases (8.4%), where deductive verification is more likely to impact their final answers, we found that:
Among all reasoning chains that arrive at correct answers (these correct-answer chains account for 49.4% of all reasoning chain candidates), 46. 46.2% of reasoning chains are filtered out by our verification process.
Among the reasoning chains that arrive at correct answer but are filtered out by our verifica- tion process, 76.3% indeed exhibit incorrect reasoning.
Among the reasoning chains that arrive at correct answer and are not filtered out by our verification process, 78.0% indeed have correct reasonings.
Among the reasoning chains that do not arrive at correct answer and exhibit incorrect reasonings (these account for 50.6% of all reasoning chain candidates), 40.6% filtered out by our verification process.
The above statistics shows that a significant portion of reasoning chains that arrive at correct answers but exhibit incorrect reasoning are successfully eliminated. Therefore, the reliability and trustfulness of reasoning chains that arrive at the correct answers are significantly improved. Combined with the fact that a significant proportion of reasoning chains that exhibit incorrect answers are climinated, and that our approach's 's verification accuracy significantly improves over naive verification approaches, primary goal to improve LLM reasoning reliability is accomplished.
Nevertheless, the removals of many reasoning chains yielding correct answers (specifically, signifi- cant 46.2% x 49. 44 of all chains) has notable impact. This even exceeds the removals of reasoning chains with incorrect reasonings and answers (40.6% 50.6% of all chains). a result, there are fewer votes for the correct answer when generating final answers through majority voting, which limits the final answer accuracy. the future, we believe that when a greater proportion of incorrect reasoning chains with incorrect answers are filtered out, we can improve the final answer accuracy.
C More Details on Answer Extraction
In this section, we describe our process to extract the final answer from language models' responses. The process begins by selecting the last three non-empty lines. Then, these lines are processed through the following pipeline:
1. Firstly, we use a list of regular expressions to identify "No-Answer" patterns within the text, such as "we cannot answer (thislthe) question". This process helps us ascertain whether the model can provide conclusive answer. If any such patterns appear in the text, we mark "No answer!" as the final answer. However, we don't detect these patterns, we proceed to the next steps for extracting the final answer.
2. Secondly, if any "Answer-Split" patterns are found in the text, we divide the text into several blocks using the identified pattern. The last block of text is then utilized for extracting the answer.
16

---

3. Lastly, we use regular expressions, outlined in Tab. I1 to sean the remaining text for possible final answers. If multiple matches found for the pattern, we select the first match as the final answer. If no pattern matches are found in the remaining text, we default the final response "No answer!".
"No-Answer" Patterns:
"we cannot provide answer to this question with (this the) given informa- tion". "we cannot answer (this|the) question". "we cannot determine". "we can't 't determine", "we do not have enough information to answer (this question", "we do not have enough information to provide definitive answer to (this (he) question", "the answer(. *?)is unknown", "answer is not listed among the answer choices".
"Answer-Split" Patterns: "answer is", "final answer:", "answer the question is". "answer this question is", "concatenated letters are", "concatenate the letters -", "The answer of".
Answer Type
Regular Expression
Number Fractional number
d-?. ]*) (-200d+// /////+/ () yojyss/ no NOJYES)
Date Yes or No
/'d Id / d'd'd d'
Table 11: Regular Expression for extracting the final answers of different kinds of questions.
D Prompts
D.1 Prompt for Direct Reasoning Chain Verification Without Natural Program Format
For the results Tab. of main paper, We use "Do you think the above reasoning process is correct? Let's think step by step." the zero-shot prompt to verify entire reasoning chain at once. We also design a two-shot prompt for reasoning chain verification as shown Tab. [2] which covers one correct reasoning chain and one incorrect reasoning chain.
D.2 Prompts for Reasoning Chain Generation in the Natural Program Format
To instruct models generate reasoning chains in the Natural Program format that facilitates step- by-step deductive verification, we have designed four distinct prompts to address different types of problems. These include:
1. Math word problems, as illustrated in Tab. 13 covering GSM8K, MATH, and AddSub datasets.
2. Math word problems with multiple-choice options, illustrated in Tab. 14 covering the AQuA dataset.
3. Date-related problems, illustrated in Tab. 15
covering the Date dataset.
4. Last Letters problems, illustrated in Tab. 16
covering the Last Letters dataset.
D.3
Prompt for Deductive Verification Following Natural Program Format and Step-by-Step Decomposition
We have designed a general one-shot prompt for the deductive verification a single reasoning step different datasets, shown in Tab. [7 This prompt serves to instruct language models to generate the deductive validity of each reasoning step as illustrated in Sec. [.2 and the top-right box of Fig. of the main paper.
E More Deductive Verification Examples
In this section, we present more deductive verification examples using our Natural Program- based approach single reasoning steps.
17

---

In Tab. 18 we demonstrate that the language model (ChatGPT) not only successfully identifies ungrounded information, but also identifies logical errors within the given solutions.
In Tab. 19 we illustrate case where the language model fails to detect ungrounded premise numbers, mistakenly assuming that these numbers be derived from grounded ones.
Lastly, in Tab. 20, we illustrate case where the language model is sometimes unable to correctly identify grounded numbers.
18

---

Here is math question and its solution: "Question:
Jason had 20 lollipops. He gave Denny some lollipops. Now Jason has 12 lollipops. How many lollipops did Jason give Denny?
Answer:
Jason started with 20 lollipops. Then he had 12 after giving some to Denny. So he gave Denny 20 + 12 =34. The answer 34."
You are a math teacher. Do you think the reasoning process is correct? Let's check the "Answer" step by step, and then end with "yes" or "no".
Answer:
The problem statement is clear, reasoning process has major error in it.
Let's go through it step by step:
"Jason started with 20 lollipops." This is correct according to the problem statement.
"Then had 12 after giving some to Denny." This is also correct as per the problem.
3. "So he gave Denny 20 12 =34, The answer is 34, " This is incorrect. The correct reasoning process should be subtracting the number of lollipops he ended up with from the number he started with. That would 20 lollipops.
So, Jason gave Denny 8 lollipops, not 34. No, the reasoning process is incorrect.
Here is math question and its solution:
"Question:
Olivia has $23. She bought five bagels for $3 each. How much money does she have left?
Answer:
Olivia had dollars. 5 bagels dollars each will be 5 x dollars. she 15 dollars left. 23 15 is 8. The answer is 8."
You math teacher. Do you think the reasoning process is correct? Let's check the "Answer" step by step, and then end with "yes" "no".
Answer:
Let's go through this reasoning process step by step.
"Olivia 23 dollars." This the given starting amount money that Olivia has. This step correct.
2. "5 bagels for 3 dollars each will be 5 3 = 15 dollars." This is correct as well. Olivia spends 3 dollars for each hagel, and she buys 5 of them. So the total cost of the bagels is 3 dollars/bagel 5 bagels 15 dollars.
"So she has 23 dollars left." This statement is also correct. After purchasing the bagels, Olivia have her initial amount of money minus the cost of the bagels.
4. "23 15 8. The answer 8." This step correct well. 23 dollars (Olivia's 's initial amount) 15 dollars (the cost of the bagels) dollars. This means that Olivia dollars left after buying the bagels.
So overall, Olivia has 8 dollars left after buying five bagels for 3 dollars each. Yes, the reasoning process correct.
Table 12: Two-shot prompt for direct reasoning chain verification without Natural Program format.
19

---

Question:
Alice buys apples. Each apple costs her $2. She gets them for 50% off. After she bought she decides she doesn't 't like 2 of them and sells them to her friends for 1. How much money was she out?
Answer:
First, let's write down all the statements and relationships in the question with labels.
#1. Alice gets 5 apples.
#2. Each apple costs $2, but Alice gets apples for 50% off.
#3. Alice sells
apples for 1.
#4. How much money Alice out?
Next, let's answer the question step by step with reference to the question and reasoning process:
#5. (by #2) Step Calculate the price per apple after 50% discount. Original price per apple: $2
Discount: 50%
Price per apple after discount: $2 0.500) = $2 0.50 = $1
#6. (by #1 #5) Step 2: Calculate Alice's cost of the apples after 50% discount. Price per apple after discount: Total apples: 5
Alice's total cost of 5 apples: $1 5 $5
#7. (by #3) Step 3: Calculate the money Alice gets back from selling apples. Money that Alice gets back from selling 2 apples: $1
#8. (by #6 #7) Step 4: Calculate the total amount of money Alice is out. Alice's total cost of 5 apples: $5
Money that Alice gets back from selling 2 apples: $1
Money that Alice is out: $5 $1 $4
#9. (by #4 #8) The original question is #4. How much money Alice out? We do not miss information the rewritten labels. So the answer to this question is Alice out $4.
Please answer the following question by following the above template.
Table 13: One-shot Natural Program prompt for reasoning chain generation on math word problems.
20

---

Question:
Alice buys 5 apples. Each apple costs her $2. She gets them for 50% off. After she bought She decides she doesn't 't like 2 of them and sells them to her friends for 1.
How much money was she out?
Answer Choices:
A)
B) 2
C) None of the above
Answer:
First, let's write down all the statements and relationships in the question with labels.
#1. Alice gets 5 apples.
#2. Each apple costs $2 but Alice gets apples for 50% off.
#3. Alice sells
apples for 1.
#4.
How much money Alice out?
Next, let's answer the question step by step with reference the question and reasoning process:
#5. (by #2) Step Calculate the price per apple after 50% discount. Original price per apple: $2
Discount: 50%
Price per apple after discount: $2 (1-0.50) = $2 0.50 $1
#6. (by #1 #5) Step 2: Calculate Alice's cost of the apples after 50% discount. Price per apple after discount: Total apples: 5
Alice's total cost of 5 apples: $1 5 $5
#7. (by #3) Step 3:
Calculate the money Alice gets back from selling apples. Money that Alice gets back from selling 2 apples: $1
#8. (by #6 #7) Step 4: Calculate the total amount of money Alice is out. Alice's total cost of 5 apples: $5
Money that Alice gets back from selling 2 apples: $1 Money that Alice is out: $5 - $1 = $4
#9. (by #4 #8) The original question is #4. How much money was Alice out? We do not miss information the rewritten labels. So the answer to this question is Alice is out S4. Among all the answer choices, the best option is A) 4.
Please answer the following question by following the above template.
Table 14: One-shot Natural Program prompt for reasoning chain generation on math word problems with multiple choice.
21

---

Let's work on date computation.
Question:
Yesterday is 02/22/2012. What is the date one week from today? Please answer in format
MM/DD/YYYY.
Answer:
First, let's write down all the statements and relationships in the question with labels.
#1. Yesterday is 02/22/2012.
#2. What is the date one week from today? Please answer in format MM/DD/YYYY.
Next, let's answer the question step by step with reference to the question and reasoning process:
#4. (by #1) Step I: Calculate the date today.
The date of Yesterday 02/22/2012. The date of today is 02/23/2012.
#5. (by #2 #4) Step 2: Calculate the date one week from today and write the answer in MM/DD/YYYY.
Because 2012 is leap year and February in 2012 has 29 days, the date one week from today is 03/01/2012.
Therefore, date one week from today is 03/01/2012.
Question:
Today is 3/2 and Bob is watching NBA 2007. What is the date one week before today? Please answer in format MM/DD/YYYY.
Answer:
First, let's write down all the statements and relationships in the question with labels.
#1. Today is 3/2.
#2. Bob is watching NBA 2007 today.
#3. What is the date one week before today? Please answer in format MM/DD/YYYY.
Next, let's answer the question step by step with reference the question and reasoning process:
#4. (by #1 #2) Step Calculate the date today. Today is 3/2 and Bob is watching NBA 2007 today. Thus, Today is 03/02/2007.
#5. (by #3 #4) Step 2: Calculate the date one week before today and write the answer MM/DD/YYYY.
Because 2007 is not leap year and February in 2007 has 28 days, the date one week from today 02/23/2007. Therefore, the date one week before today is 02/23/2007.
Please answer the following question by following the above template.
Table 15: Two-shot Natural Program prompt for reasoning chain generation on the Date dataset.
22

---

Let's work on date computation.
Question:
Take the last letters of each words in "Apple Is" and concatenate them.
Answer:
First, let's write down all the statements and relationships in the question with labels.
#1. We need take the last letter of the word "Apple".
#2. We need to take the last letter of the word "Is".
#3. We need concatenate the last letters of the words sequentially
Next, let's answer the question step by step with the complete reference the question and reasoning process:
#4. (by #1, #3) Step 1: Taking the last letter of the word "Apple" and concatenate the latter. The last letter of the word "Apple" is "e". The concatenated last letters are "e".
#5. (by #2, #3, #4) Step 2: Taking the last letter of the word "Is" and concatenate the latter. The last letter of the word "Is" is "s" The concatenated last letters are "es".
#6. (by #3, #5) Step 3: Provide the final answer of the concated letter. Therefore, the answer is "es".
Please answer the following question by following the above template.
Table 16: One-shot Natural Program prompt for reasoning chain generation on the Last Letters dataset.
23

---

Here is some information:
"1. Alice gets 2 apples.
2. Alice gets twice as many oranges as bananas.
3. Original price per apple: $2
Discount: 50%
Price per apple after discount: $2 (1 0.50) = $2 0.50 S1"
Based the given information, here is reasoning process: "Calculate Alicc's cost of the apples after 50% discount.
Price per apple after discount: $1
Apples be caten: 3
Oranges be eaten: 6
Total apples:
Total oranges: x
Total bananas: 2x
Alice's total number of fruits: 5 X + 2x = 5 +x
Alice's total cost of 5 apples: $1 * (3 $2
Double-check the reasoning process, let's analyze its correctness, and end with "yes" or "no".
Answer:
Let's think step by step.
Grounding check
Purpose: Find references for numbers in the reasoning process sequentially
Rule: Any ungrounded number makes the check fails
"x" a variable, we not care about variables. "y" is a variable, we do not care about variahles.
"5" is quantity from the given information that represents the number of apples.
"50%" a quantity from given information that represents the discount.
"$1" is quantity from the given information that represents the price per apple after the discount.
"3" is a quantity not from the given information, it is ungrounded.
"6" is a quantity not from the given information, it is ungrounded.
"$2" is quantity from the given information that represents the original price per apple.
Result: Based
check, there are ungrounded numbers, so the grounding check fails.
Reasoning check:
Purpose: Check whether the reasoning logic correctly answers the question
Rule: Any logic error makes the check fails
To calculate the total cost of apples after 50% discount, we should multiply the number of apples by the discounted price. But to answer the question, we do not need to calculate the total number of fruit Alice gets.
Result: Based
check, there are some logic mistakes, so the reasoning check fails.
Calculation check:
Purpose: Check whether the calculation process consistent
Rule: Any inconsistent calculation makes the check fails
calculation1:
equation: $1 3),3), answer: $2
2
21 $2 is consistent with the answer, so the calculation correct.
calculation2:
equation: 5 + 2x, answer: 5 + 4x
x + 2x = 3x
5 3x inconsistent with the answer, the calculation is incorrect.
Result: Based on the check, the calculation process inconsistent, so the calculation check fails.
Check results: Ground check fails, Reasoning check fails, Calculation check fails. Rule: Any failed check makes the reasoning incorrect. So the answer "no".
Table 17:
One-shot prompt for deductive verification of single reasoning step, following our Natural Program format and step-by-step reasoning chain decomposition.

---

Input:
Here is some information:
"For every 25 telephone calls he makes, he gets one person to come into the dealership."
Based on the given information, here is reasoning process:
"Calculate the number of people that would come into the dealership for 15 sales. Number of people needed to sell 15 cars: 15 = 30"
Double-check the reasoning process, let's analyze its conrectness, and end with "yes" or "no".
Answer: Let's think step by step without any assumptions.
Output:
Grounding check:
Purpose: Find references for numbers in the reasoning process sequentially
Rule:
Any ungrounded number makes the check fails
"15" is quantity from the question that represents the number of car sales.
"2" is a quantity not from the given information, it is ungrounded.
"25" is quantity from the given information that represents the number of telephone calls
per one person to come into the dealership.
Result: Based on the check, there are ungrounded numbers, so the grounding check fails.
Reasoning check:
Purpose: Check whether the reasoning logic correctly answers the question
Rule: Any logic error makes the check fails
is not clear how the number of people coming into the dealership relates to the number of car sales. The given information only tells us the ratio of telephone calls people coming into the dealership, but it does not provide any information about the number of telephone calls made for each car sale. Therefore, the reasoning process is not correct.
Result: Based on the check, there is a logic mistake, so the reasoning check fails.
Calculation check:
Purpose: Check whether the calculation process is consistent
Rule: Any inconsistent calculation makes the check fails
calculation1:
equation: 15 * 2, answer: 30
15 2 30 is consistent with the answer, so the calculation is correct.
Result: Based on the check, the calculation process is consistent, but the reasoning incorrect, so the calculation check fails.
Check results: Grounding check fails, Reasoning check fails, Calculation check fails. Rule: Any failed check makes the reasoning incorrect.
So the answer is "no".
Table 18: Successful case: our deductive verification approach successfully discovers ungrounded information and reasoning mistakes.
25

---

Input:
Here some information:
"How many hours would it take for people paint whole house?"
Based the given information, here is reasoning process:
"Calculate the total number of hours it would take for 5 people to paint a whole house.
Total hours for one person to paint whole house: 240 hours
Total number of people: 5
Total hours for 5 people to paint whole house: 240 hours / 5 48 hours"
Double-check the reasoning process, let's analyze its correctness, and end with "yes" or "no".
Answer: Let's think step by step without any assumptions.
Output:
Grounding check
Purpose: Find references for numbers in the reasoning process sequentially
Rule: Any ungrounded number makes the check fails
"240" is quantity not from the given information, it is ungrounded.
"5" a quantity from the given information that represents the number of people.
"48" is quantity calculated from the ungrounded number and grounded number in the reasoning process.
Result: Based on the check, there is one ungrounded number, but it calculated from another grounded number, so the grounding check passes.
Reasoning check:
Purpose: Check whether the reasoning logic correctly answers the question
Rule: Any logic error makes the check fails
The reasoning process correctly calculates the total number of hours for people to paint whole house by dividing the total hours for one person to paint a whole house by 5. Therefore, the reasoning check passes. Calculation check:
Purpose: Check whether the calculation process is consistent
Rule: Any inconsistent calculation makes the check fails
calculation1:
equation: / answer: 48
240 = 48 is consistent with the answer, the calculation correct.
Result: Based on the check, the calculation process is consistent, so the calculation check passes.
Check results: Ground check passes, Reasoning check passes, Calculation check passes. Rule: All checks pass make the reasoning correct.
So the answer is "yes".
Table 19: Failure case: deductive verification process fails to find out ungrounded information in the reasoning step. The number 240 in the reasoning step is ungrounded, but the model states that can be calculated from grounded numbers.
26

---

Input:
Here is some information:
"Calculate the number of doughnuts Derrick makes day.
Number of doughnuts in dozen: 12
Number of doughnuts in dozens: 10 12 = 120
Calculate the revenue from selling one doughnut.
Price per doughnut: $2"
Based on the given information, here is reasoning process:
"Calculate the revenue from selling all the doughnuts in day. Number of doughnuts Revenue from selling all the doughmuts in day: $2 120 $240"
day: 120
Double-check the reasoning process, let's analyze its correctness, and end with "yes" or "no".
Answer: Let's think step by step without any assumptions.
Output:
Grounding check
Purpose: Find references for numbers in the reasoning process sequentially
Rule:
Any ungrounded number makes the check fails
"12" is a quantity from the given information that represents the number doughnuts in a dozen.
"10" is quantity not from the given information, it ungrounded.
"S2" is a quantity from the given information that represents the price per doughnut.
"120" is quantity not from the given information, it is ungrounded.
Result: Based on the check, there are ungrounded numbers, so the grounding check fails.
Reasoning check:
Purpose: Check whether the reasoning logic correctly answers the question Rule: Any logic error makes the check fails
The reasoning process is correct. We have the number of doughnuts Derrick makes in a day, and we have the price per doughnut. Multiplying these two yields the revenue from selling all the doughnuts in a day. Result: Based on the check, the reasoning logic correct.
Calculation check:
Purpose: Check whether the calculation process is consistent Rule: Any inconsistent calculation makes the check fails
calculationl:
equation: 10 12. answer: 120
10 * 12 = 120 is consistent with the answer, so the calculation is correct.
calculation2:
equation: $2 120, answer: $240
$2 * 120 $240 is consistent with the answer, the calculation is correct.
Result: Based on the check, the calculation process is consistent, so the calculation check passes.
Check results: Ground check fails, Reasoning check passes, Calculation check passes. Rule: Any failed check makes the reasoning incorrect. So the answer is "no".
Table 20: Failure case: our deductive verification process sometimes treats grounded information as if they were ungrounded. The number 120 provided in the given information, but the model states that it is ungrounded.
27


Reviews:
[{"review_id": "p7MUzf3DLJ", "reviewer": "Reviewer_LzaJ", "summary": "The authors present an approach to build easily verifiable prompted systems by proposing a new reasoning format - Natural Program. In this proposed form, LLMs are expected to generate a rationale but additionally also indicate previous steps that led to each step of reasoning. This allows a verifier to only look at these dependent steps and reduce the amount of distraction. This is an interesting idea and as the authors show results in an improvement in verification accuracy (verifiers are prompted LLMs too).\n", "questions": "- Isn't \"unanimity-plurity\" just self-consistency with a deductive validation filter? Not sure if it needs another name.\n\n- I am surprised that CoT + Voting achieves a much higher score than Faithful CoT + voting. Also the reported number here seems to match the base numbers for faithfulCoT (no voting). See https://github.com/veronica320/Faithful-COT.\n\n- I would have preferred that all the tables included accuracy numbers on the datasets (instead of just verification accuracy). \n\n- Also I didn't see the value of splitting the numbers into accuracy on correct vs wrong chains. Note that I do like the evaluation set, but you could just report the F1 score. Currently it is hard to see which approach is better when looking at two numbers. \n\n- Since FaithfulCoT also provides a similar dependency structure, could deductive verification be applied with their approach too (as a baseline)?\n \n- While the authors show that full premises (i.e. w/ distractors) does result in lower verification accuracy, it is unclear that it impacts QA accuracy. E.g. Could CoT with UPV already outperform their approach without needing NP? Basically sample K CoTs, validate each step of the CoT given the entire context using K' generations and then pick the validated CoTs for majority voting. \n", "limitations": "Natural programs can introduce errors via incorrect dependency structure prediction. It would have been nice to see an error analysis in the paper to capture the source of errors with NP.\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- A natural language formalism that allows us for more accurate reasoning verification\n- The approach is well-motivated by showing the inability of ChatGPT to identify errors given the entire reasoning chain. \n- Shows gains compared to self-consistency with two different CoT formats\n", "weaknesses": "- The empirical results could be strengthened with strong baselines. E.g. the paper only has two baselines CoT and FaithfulCoT. See questions for more details. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your constructive feedback! We address the comments and questions below. \n\n> Q1: Include stronger baselines for comparision with \"Natural Program\".\n\nWe'd like to note that our primary goal is to improve the *truthworthiness and reliability* of the reasoning via step-by-step deductive verification. As such, we don't primarily focus on comparing the final answer correctness of \"Natural Program\" with other established prompting techniques. Our choice of CoT and Faithful CoT as baselines in Table 3 stems from two reasons:\n1) When we require the LLMs to generate output in the \"Natural Program\" format, we utilize few-shot prompting. Consequently, we included \"CoT\", which also employs step-by-step few-shot prompting for reasoning.\n2) \"Faithful CoT\" and our proposed \"Natural Program\" both require LLMs to explicitly generate premises for each reasoning step. Unlike \"Natural Program\" that produces step-by-step answers in natural language, \"Faithful CoT\" generates a step-by-step code program as answers and executes the program with interpreters. We empirically find Faithful CoT to underperform Natural Program, suggesting that generating intricate code programs alongside reasoning chains could be challenging, while generating natural language-based reasonings could be comparatively simpler for LLMs.\n\n> Q2: Why \"Unanimity-Plurality Voting\"?\n\nWe named our voting method \"Unanimity-Plurality Voting\" because there are two phases of majority voting: the \"unanimity\" phase and the \"plurality\" phase. \n- The \"unanimity\" phase of the majority voting occurs when verifying a reasoning chain. During this phase, (1) To verify each reasoning step $s_i$ of a reasoning chain $S$, we sample a set of $k'$ validity predictions, and perform majority voting to obtain the validity prediction for $s_i$; (2) For a reasoning chain $S$ to be valid, all its reasoning steps have to be \"unanimously\" valid.\n- The \"plurality\" phase of the majority voting occurs when we produce final answer for problem solving. During this phase, we perform majority final answer voting over the validated reasoning chains from the \"unanimity\" phase.\n\n> Q3: Faithful CoT + Voting result update; Why does \"CoT + Voting\" outperform \"Faithful CoT + Voting\"?\n\nWe have updated Table 3 where the numbers in Faithful CoT reflect majority voting results (please see \"Common Response\"). From the new Table 3, we still find that CoT sometimes outperforms Faithful-CoT. This difference might stem from the nature of the methods: CoT provides natural language answers, whereas Faithful-CoT generates code solutions. For challenging tasks such as MATH and GSM8K, the complexity of correct code programs could be substantial, potentially making natural language solutions simpler for LLMs to generate.\n\n> Q4: Include final answer accuracy to the tables besides verification accuracy.\n\nThanks for your suggestion! We will position Tables 3 (final answer accuracy) and 4 (verification accuracy) on the same page. We'll also add final answer accuracies to Table 2.\n\n> Q5: Report F1 score of deductive verification\n\nThanks for your suggestion! We have updated Tables 2, 4, and 5 to include F1 score. Please see \"Common Response\" for further details.\n\n> Q6: Deductive Verification of \"Faithful CoT\"\n\nThanks for the suggestion! We've conducted an experiment on the GSM8K dataset to show the deductive verification performance of \"Faithful CoT\". In a manner similar to the verification evaluation pipeline for \"Natural Program\", we have manually chosen 100 reasoning chains—50 deductively valid and 50 with reasoning errors. We validated each reasoning step using full premises and minimal premises. Detailed results are presented in the subsequent table. \n\n**Verification results of GSM8K with Faithful CoT and Natural Program**\n| Answer Correctness| Faithful - Full reasoning chain | Faithful - Step-by-step (Minimal premises) | NP - step-by-step (Minimal preimises)|\n|--|---|---|---|\n|Correct|96.00%|96.00%|84.00%|\n|Incorrect|12.00%|18.00%|84.00%|\n|F1|44.15%|49.28%|84.00%|\n\n> Q7: Using UPV with CoT without Natural Program (NP)\n\nThanks for the suggestion! Unfortunately, for reasoning chains generated with vanilla CoT, it is very challenging to extract the actual premises of a single reasoning step because of intertwining reasoning-step dependencies. In contrast, Natural Program allows individual reasoning steps and their minimal set of premises to be easily extracted. Therefore, step-by-step deductive verification is more compatible with answers generated through NP than vanilla CoT. As for UPV, it also depends on step-by-step verification results, and thus has better applicability with NP.\n\n> Limitations\n\nThanks for the suggestion! We'd like to point the reviewer to Sec. 6 and Tab. 7, where we showcase our approach's failures to detect reasoning step errors when encountering ambiguous wordings. We also included more success / failure analysis in Appendix D and Table 12-14 of Appendix."}, {"review_id": "8xFmVCa3TV", "reviewer": "Reviewer_BLD6", "summary": "The authors propose Natural Program, a suite of prompt-based steps to verify the reasoning process generated by LLM by reusing the LLM itself. The key observation used is that LLMs are good verifiers natively if they are presented with just the necessary set of premises to judge the statement. Any distractor can potentially increase error in the verification process. Thus, they show the application of their approach on CoT rationales for mathematical datasets. Overall, the approach leads to more trustful explanations and improved accuracy on the tasks.", "questions": "* Lines 111-112: This statement is too generic. Please note the type of datasets for which it holds. And also back it by pointing to relevant analysis sections or doing some more rigorous analysis.\n* Lines 205-207: This part is not clear. Do you sample yes/no values multiple times with the prompt in lines 1186-187 from the verifier and then do some majority voting? Table 5 suggests that you sample multiple times. If so, does it also show that the LLMs are inherently not good at this task and you are essentially relying on some crude statistical hope that the model will get it right most of the time? Isn't that the whole issue being addressed in the paper?", "limitations": "* A major component of this approach is the increased overhead in terms of cost of API calls. There is no substantial discussion on how cost efficient / harmful this approach is. Please expand upon this in a separate limitations section.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The observation that using only the least set of premises helps LLMs in self-verification is a good observation. Although, this is not a new finding per say, but the authors present it in a new application scenario, which is interesting.\n* The motivation of the problem is well-formulated in the introduction.", "weaknesses": "* While the solution works indeed, it is somewhat circular in nature. Since the main hypothesis here is that we don't trust the generations sampled from LLM, then using the same LLM in pretty much similar manner for verification (basic prompting, without any fine-tuning to probably teach the task better) is not very convincing. The solution also relies on sampling multiple outputs for verification and then some sort of voting (see Q2 for more details).\n* The utility of the intermediate steps involved in the verification system is not clear. The qualitative analysis is not sufficient to understand why these specific design choices were made or how it helped. Please expand on these experiments to show some ablation of the design choices. You can explore slightly different prompt formats where we don't mention the premise numbers (#6 , #9, etc.), or other such ablations.\n* Lines 240-241: There is no justification of this weird design choice of favoring \"yes\" labels. Why would you have to do this at all? Why not just discard these sentences that lead to ambiguity? How frequent is this scenario? What happens if you start favoring \"no\" instead? Does it mean the LLMs are not very sensitive to discriminate between yes and no labels?\n* Overall, designing new prompts for a task (verification of rationales in this case) seems limited in terms of novelty. This work can perhaps be more suitable for some more NLP-focused conference.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your constructive feedback! We address the comments and questions below.\n\n> Circular nature of using LLM for verification\n\nWe'd like to clarify that \"the main hypothesis here is that we don't trust the generations sampled from LLM\" is actually NOT our hypothesis. Not only do we seek when the LLM cannot be trusted, but also **when it can be trusted**. According to our experiments, when LLM is used as a verifier, although it is not trustable if the logic chain to verify is complex and long, it is, indeed, highly trustable for short logic chains (e.g., one-step reasoning). This is the motivation for us to invent the Natural Program which allows us to break complex and long logic chains to short ones so that we can trust the verification result of LLMs. In fact, this well aligns with how humans verify results -- recall the experience when we were elementary school students, teachers ask us to write down reasoning steps in very details so that the logical flaws of the answers can be easily detected.\n    \nThese insights are validated by Table 2 (see \"Common Response\"), which shows poor verification accuracies when naively using the LLM to verify reasoning with entangled premises. Conversely, Table 4 (see \"Common Response\") illustrates how our Natural Program-based approach with decomposition and simplification leads to improved verification accuracy and fewer reasoning errors. \n    \nWe also share the view that constructing comprehensive verification datasets and finetuning LLMs on these datasets can further enhance their verification accuracy. In Appendix Table 3, we finetuned Vicuna using our Natural Program verification framework, achieving better verification accuracies. Our Natural Program format and minimal-premise approach may inspire future verification datasets, improving the reliability of LLM-generated outputs.\n\n> Intermediate steps and premise numbers for verification: ablations and design choices\n\nPremise numbers serve to encourage LLMs to cite the *minimal* set of premises necessary for each generated reasoning step as they work through problem-solving. In this way, when LLMs verify each reasoning step, only the cited premises are utilized as the context for verification. Many irrelevant premises, which can easily confound and distract LLMs, are removed. This process is illustrated in Figure 1 of the paper. Without premise numbers, it is very challenging to remove irrelevant premises when verifying each reasoning step.\n\nIn Table 2 (refer to \"Common Response\"), we perform an ablation by excluding premise numbers from the reasoning generation prompt (prompt in Table 10 in the Appendix). Here, despite LLM attempting to verify each reasoning step, irrelevant premises remain during step verification. In contrast to Table 4 (minimal premises - our approach), verification accuracy experiences a notable decline.\n\nAnother ablation is in Table 4, where we keep the premise numbers in the reasoning chain generation prompt. However, during step verification, premise numbers are disregarded, and all preceding steps are used as verification context (e.g., verifying step \"#6\" includes all prior steps \"#1...#5\" as context). This is seen in the \"Full Premises\" entry, where verification accuracy markedly decreases.\n\n> L240-241 - choice of using \"yes\" as the default verification results when the model does not provide a direct answer\n\nFirstly, LLMs generally output \"yes\" or \"no\" following our few-shot examples and rarely output other answers  (GSM8K: 0.04%; AQuA: 0.19%; MATH: 0.16%; AddSub: 0.00%; Date: 1.30%; Last Letters: 1.3%). Our voting strategy treats outliers as a separate category, further minimizing their impact on our approach's efficacy.\n    \nAdditionally, we manually checked the model's reasoning steps when no direct answer is provided, finding them correct in nearly all cases on our dataset, so the verification answer is 'yes'. This is reasonable, as LLMs can answer most problems in the datasets we use.\n\n> Novelty of prompting\n\nFirstly, we'd like to note that two notable papers accepted by NeurIPS 2022 on LLMs primarily focused on prompting for step-by-step reasoning: \"Chain-of-Thought Prompting Elicits Reasoning in Large Language Models\" with 1010 citations as of Aug 9, and \"Large Language Models are Zero-Shot Reasoners\" with 485 citations as of Aug 9.\n\nWe'd also like to note that our work goes beyond studying prompts for LLM reasoning chain verification. A crucial component of our framework involves simplifying the step-by-step verification process by only keeping necessary premises and contexts for each reasoning step.\n\n> L111-112 too generic\n\nWe acknowledge that this statement is too generic. We'll revise it as \"We observe that for many cases where LLMs produce erroneous final answers through a step-by-step reasoning process, there exists at least one mistake among the intermediate reasoning steps.\"\n\n> L205-207 clarification\n\nWe'd like to clarify that we are NOT \"relying on crude statistical hope that the model will get it right most of the time\", or relying on extensive voting.\n- While we can sample multiple yes/no values for verification and perform majority voting, Table 5 (see \"Common Response\") shows that while multiple votes offer some improvement, the gains are modest compared to using a single vote.\n- Compared to voting, the premises used for verifying of each reasoning step plays a *much* larger role, as shown in Table 4. Removing irrelevant premises that confound LLMs significantly improves verification accuracy.\n\n> Limitations of API calls\n\nWe recognize that including the verification step increases API calls compared to omitting it. Though, in situations like legal cases and answering scientific questions, reliability of reasoning is often prioritized over economic factors. We'll add discussion.\n\nAlso, Table 5 shows that adding more votes for verification provides slightly more benefits, but does not differ much from using one vote."}, {"review_id": "x1oDiZsk7t", "reviewer": "Reviewer_TPbw", "summary": "This paper introduces a format for chain-of-thought reasoning in language models called Natural Programs. In a Natural Program, the model explicitly breaks down the given problem into a numbered list of assumptions. Then, each reasoning step explicitly lists out the premises (starting assumptions or previous steps) that are required to support the conclusion made at that step. The advantage of Natural Programs is that one can verify the reasoning trace by locally verifying each step, extracting the premises and conclusion and asking a language model to assess the validity of that step. A first experiment shows that GPT-3.5 Turbo is not able to do zero-shot verification of full arguments. However, it is much better at catching errors when presented just the minimal set of premises at each step. This allows one to sample multiple Natural Programs and use step-wise verification to select the best among them. The authors experiment on 6 datasets - 4 for mathematical reasoning (GSM8k, AquA, MATH, AddSub) and 2 of commonsense/symbolic reasoning (date manipulation and last latter concatenation), using GPT-3.5 Turbo, showing improvements in final answer accuracy compared to vanilla chain-of-thought with voting and Faithful chain-of-thought.", "questions": "- Line 68: It is implied that GPT-3.5 Turbo has 175B parameters, but as far as I'm aware the size of the model is not publicly known (GPT-3 has been reported by OpenAI to have 175B parameters, but not GPT-3.5 Turbo).\n- Lines 59-61: What empirical results in the paper support the mentions to 'nearly all' in these sentences? It would be useful to refer to those numbers here. As I understand, there are still a significant number of false negatives when verifying Natural Programs.\n- Footnote in Page 7: world problems -> word problems\n- What do the authors think are the most significant differences between Natural Programs and the NLProofS approach?\n- The Faithful CoT paper reports slightly better numbers for GSM8k (~79% with self-consistency). Are there any differences in the evaluation setup that justify this?\n- On average, how many more calls to the model does Natural Programs take, compared to vanilla CoT? This should be mentioned in the paper, since any reader that is a potential user would have this practical question.\n- Does verification necessarily require one call per step, or can multiple steps be batched in a single call to the model? It would be interesting if batching with the Natural Programs format still performs better than asking GPT-3.5 to verify the whole solution all at once.\n- Is it possible to combine Faithful CoT with Natural Programs in the arithmetic tasks? Perhaps that would allow the model to not need to perform arithmetic, and the verification can also remain more high-level (verifying the reasoning rather than the calculations)\n- In line 66, you mention that when all verification fails, the proposed approach can produce \"Unknown\" rather than a likely wrong answer. How often did this happen in the experiments?", "limitations": "Yes, the limitations are clearly discussed in the paper. ", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is clear and easy to follow. The idea is well-motivated and timely: chain-of-thought is the dominant paradigm for using LLMs in a variety of tasks, but by itself it's of course not perfect. Also, the paper builds nicely on top of existing LLMs, so ideas like Natural Programs that enhance trustworthiness of pre-trained LLMs have potential for wider adoption.\n\nThe idea also builds nicely on the flexibility of LLMs, and this is reflected on the range of tasks used in the paper. Many more domains where CoT is applicable are also amenable to Natural Programs without more effort other than writing adequate prompts for the new domains.", "weaknesses": "The paper's first stated contribution is the framework of Natural Programs. However, a similar idea has been proposed in the EMNLP 2022 paper that introduced NLProofS [1]. The idea of NLProofS was also to generate reasoning steps in natural language while having the model explicitly refer to the premises that each step follows from, and then use a verifier to score the validity of each individual step given only the relevant premises. See Figure 1, \"Single-shot generation\" in [1], comparing that to Figure 1 in the Natural Programs paper. While overall there are differences between both works (e.g., NLProofs assumed a hypothesis to be proved or disproved given at the beginning, which is not given in any of the tasks used in the Natural Programs paper), but I believe this undermines the novelty aspect of Natural Programs.\n\nThe authors argue (e.g. line 62, line 253) that their focus is on generating more trustworthy reasoning, rather than just reasoning where the final answer is correct. However, based on the results of Table 4, it does not seem like Natural Programs alone can provide a high level of reliability for GPT-3.5 Turbo. In GSM8k, the best dataset, there's still a 16% false positive rate, then 38% in AQuA, and 60% in AddSub. Thus, it doesn't feel clear to me that this goal has been achieved. I'd thus still place Natural Programs as a means to the end of achieving better final accuracy.\n\nIn terms of final-answer accuracy, the results are arguably mixed. The gains over CoT/Faithful CoT are quite significant in AQuA and Last Letters, but minor in the other 4 datasets.\n\nThe experiments focus only on a single model, GPT-3.5 Turbo. It would strengthen the paper to show that multiple models can benefit from using Natural Programs. The Appendix does have initial results with Vicuna, but the authors seem to only have done the experiment on validation accuracy, not on final answer accuracy. Even if the absolute performance of Vicuna is lower, perhaps there's a higher chance of obtaining larger gains on it.\n\n[1] Yang, Kaiyu, Jia Deng, and Danqi Chen. \"Generating Natural Language Proofs with Verifier-Guided Search.\" Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing. 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your constructive feedback! We address the comments and questions below.\n\n> Differences between NLProofS and our work\n\nThanks for your insightful question and we'll cite the \"NLProofS\" paper. We'd like to highlight several perspectives that distinguish our work from NLProofS:\n- **The central approach of the two papers differ.** Our approach leverages the in-context learning and step-by-step reasoning abilities of LLMs to perform the verification of each step in a reasoning chain, and does not require LLM finetuning. On the other hand, NLProofS finetunes LLMs on specific datasets to score proof tree nodes and search for proof. Such scoring process does not utilize in-context learning.\n- **The focus of these two papers differ.** The primary goal of NLProofS is to propose \"a novel method for stepwise proof generation\", while our primary goal is to propose an effective framework to *verify* deductive reasoning chains. To this end, we explore different designs for our verification framework, ultimately leading us to develop the Natural Program reasoning format and adopt the minimal premise-based verification approach.\n- While NLProofS employs a scoring model to assign a validity score to proof tree nodes, it does not provide explainations for **why** a proof step is invalid. In contrast, our Natural Program-based LLM verification approach not only identifies invalid reasoning steps, but they can also provide explicit explanations for why they are invalid, detailing the specific reasoning errors involved.\n\n> Have we achieved the goal of generating more trustworthy reasoning?\n\nThroughout this work, **we have uncovered valuable insights and discovered a verification framework that *significantly* improves the verification accuracy of reasoning chains over naive approaches, and we believe we have achieved our primary objective of improving LLM reasoning reliability**. We are also NOT asserting that the deductive verification problem is completely solved, but we believe that our proposed framework is a promising avenue to explore.\n\nThe insights from our paper are as follows: naively using LLM to verify complex reasoning chains results in very poor verification accuracies (see Table 2 in “Common Response”) because of intertwining reasoning-step dependencies that confound LLMs. However, when we break down complex and long logic chains into short ones (e.g., one-step reasoning), and more crucially, verify each reasoning step with *only* its minimal context and premises necessary, we can *significantly* improve verification accuracies (see Table 4), thereby enhancing the reliability of LLM-generated reasonings.\n\nMoreover, we experimentally demonstrate the potential to adapt our insights and our verification frameworks to construct comprehensive verification datasets and further improve LLM verification accuracy through finetuning. In Appendix Table 3, we finetuned Vicuna using our Natural Program verification framework, achieving better verification accuracies. Our Natural Program format and minimal-premise approach may inspire future verification datasets, improving the reliability of LLM-generated outputs.\n\n> I'd still place Natural Programs as a means to achieving better final accuracy. Final answer accuracy results are mixed\n\nWhile the final answer accuracy results are mixed, we find that **one major contributing factor is the filtering out of reasoning chain candidates that provide correct answers but exhibit incorrect deductive reasoning.** An example is illustrated in Table 6 of submission, where ChatGPT generates the correct final answer but assigns incorrect premise numbers to support the first reasoning step, and our verification approach effectively identifies many of these reasoning errors. Combined with the fact that our proposed verification approach has significantly improved the verification accuracy over naive approaches, we believe we have achieved our primary goal.\n\n> Final answer accuracy on Vicuna\n\nThanks for your suggestion. We have added final answer accuracy comparision bewteen \"Natural Program\" and \"CoT\" for Vicuna models to complement the verification accuracies in Appendix Tab. 3.\n\n|Models|Methods|GSM8K|AQuA|MATH|AddSub|Date|Last Letters|\n|---|---|---|---|---|---|---|---|\n|Vicuna-7B|CoT|9.26%|25.03%|7.25%|28.33%|21.70%|0.02%|\n||Natural Program|7.79%|23.93%|6.55%|38.10%|27.76%|0.00%|\n|Vicuna-13B|CoT|16.54%|25.26%|7.30%|36.15%|19.79%|1.04%|\n||Natural Program|34.16%|21.01%|7.09%|31.48%|33.88%|2.36%|\n\n> Number of parameters for GPT-3.5 Turbo\n\nThanks for your suggestion. We will remove this number.\n\n> L59-61 statement\n\nThanks for your attention. We'll revise it by replacing \"nearly all\" with \"many\".\n\n> Faithful CoT GSM8K results\n\nWe rerun Faithful CoT with GPT-3.5-turbo using their original repo and have updated Table 3. It achieves a better performance of 81.20% on GSM8K.\n\n> Number of API calls per question for Natural Program and CoT\n\nFor reasoning chain generation, both Natural Program and CoT use 1 API call per question. This is because \"Natural Program\" and \"CoT\" both append few-shot examples before the query question.\n\n> Call per step in verification\n\nFor each reasoning step, we need one call for verification. We can also aggregate multiple queries into one single call by asking model to answer multiple questions. \n\n> Combine Faithful CoT with Natural Programs\n\nThanks for your question. Table 3 shows that Faithful CoT does not perform as well as the CoT baseline or our Natural Program across most tasks, likely because Faithful CoT focuses on code generation, which doesn't provide much benefits for our current arithmatic-focused tasks. Due to limited rebuttal time, we'd like to leave further explorations for future work.\n\n> Frequency of \"Unknown\" (L66)\n\nThe frequency of \"unknown\" is pretty rare (GSM8K: 2.7%; AQuA: 5.0%; AddSub: 2.9%; others: 0%).\n\n> Typo in page 7\n\nThanks for pointing out! We'll fix it."}, {"review_id": "MrdVHjDIw9", "reviewer": "Reviewer_kmTd", "summary": "This paper propose natural program, which a novel method to make verifiable Chain-of-Thoughts reasoning as well as verify each step. The idea is to first generate reasoning steps in the format of '(# by evidences), caculate...'. And then they prompt another LLM to verify each relatively independent step. The paper also propose a method called 'Integrating Deductive Verification with Unanimity-Plurality Voting' to use verification results to improve generation correctness, though they claim it is not their main aim.", "questions": "See weaknesses, especially point 1. If it's my misunderstanding, I will increase my score.", "limitations": "The authors have discussed limitations in Sec. 6, which I think is adequate.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The idea of doing verification on relatively independent steps is good. The results in table 4 shows its verification performance is better than directly using all previous information.", "weaknesses": "1. I happen to have read the arxiv version (https://arxiv.org/pdf/2306.03872.pdf) of the paper. But there is a major mismatch between the arxiv version and the submission. Tab. 4 in the Arxiv version has the results of 'Ours (Natural Program (NP), No Verification)' and 'Ours (NP + Deductive Verification + UPV)', which shows Natural Program is helpful but verification and UPV is not. But the submission removed the row \nof 'Ours (NP + Deductive Verification + UPV)' and rename the row of 'Ours (Natural Program (NP), No Verification)' as 'Ours (Deductive Verification + NP + UPV)', which can lead to a conclusion that NP + Deductive Verification + UPV is helpful to accuracies. Could you explain this? By the way, where is Tab. 5.2 in the 'Answer correctness' paragraph.\n2. I doubt the usefulness of the method. The method cannot be applied to verify reasoning from other generation models, as it requires a specific form of input. The method cannot be used to improve generation accuracy because of the marginal performance gain.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your constructive feedback! We address the comments and questions below.\n\nWe'd like to first clarify that our primary goal is *NOT* to improve the final answer accuracy of reasoning tasks. \n    \nWhen LLMs leverage CoT to carry out problem solving, hallucinations and accumulated errors can often occur in intermediate reasoning steps, even if the final answers are correct (examples illustrated in Tab. 1 of submission). This phenomenon limits the reliability and trustfulness of LLM generations. As a result, we place significant emphasis on ensuring the **validity of every reasoning step**, *not the correctness of the final answer*, such that LLM reasoning outputs become more reliable.\n\nTo this end, we first discover that naively using LLM to verify complex reasoning chains results in very poor verification accuracies (see Table 2 in “Common Response”) because of intertwining reasoning-step dependencies that confound LLMs. We therefore propose our Natural Program-based verification approach, which decomposes the verification of an entire reasoning chain into the verification of individual reasoning steps, and more crucially, the verification process of each reasoning step is based on *only* its necessary contexts and premises. As a result, we have *significantly improved the verification accuracy of reasoning chains* (see Table 4 in “Common Response”), thereby significantly improving the reliability of LLM-generated reasoning steps and achieving our primary goal.\n\n> Clarification of Table 3 in our submission and \"Tab. 5.2\" typo\n\nThank you for pointing it out. \"Tab. 5.2\" is a typo, and it refers to Tab. 3 in our submission. We will revise it in the future. \n\nWe have updated Table 3 to address the submission-arxiv mismatch. For details, please refer to \"Common Response\".\n\n> Does deductive verification improve QA/generation accuracy?\n\nThank you for raising this point. As shown in Table 3, we acknowledge a slight decrease in QA/generation (final answer) accuracy after applying deductive verification on Natural Program reasoning chains. One major contributing factor to this decrease is the filtering out of reasoning chain candidates that provide correct answers but exhibit incorrect deductive reasoning. \n\nHowever, we'd like to note that with our proposed Natural Program and minimal premise-based verification approach, we have *significantly improved the verification accuracy of reasoning chains* (see Table 4 in “Common Response”, and comparison with Table 2), thereby significantly improving the reliability of LLM-generated reasoning steps and achieving our primary goal.\n\n> Can our deductive verification methods be applied to a broader range of cases, such as other models or different formats?\n    \nThank you for your insightful question. Our Natural Program-based verification approach harnesses the power of natural language, making it potentially applicable to a wide range of natural language reasoning tasks along with any LLM with in-context learning capabilities. For abstract reasoning datasets (e.g., Last Letters), our verification method can be applied when the reasoning processes can be articulated in natural language. For datasets centered around shape or object comprehension, new prompts can be devised to translate shapes and objects into symbols and words, enabling natural language reasoning and verification at the symbol level. For code-based datasets, if natural language reasonings used for code generation are accessible, our approach can be used to verify these reasonings as well.\n    \nFurthermore, our verification approach can be applied to fields that naturally demand verification of sequences, such as assessing human reasoning or analyzing arguments in law, which would be interesting for future work."}, {"review_id": "aNci0H6d4x", "reviewer": "Reviewer_bmW6", "summary": "Despite demonstrating appealing reasoning capabilities, Language Models (LLMs) still suffer from erroneous and hallucinated reasoning. In order to enhance the trustworthiness of LLMs' reasoning process, this paper introduces a deductive reasoning framework based on natural language. The framework extracts premises from the context, breaks down the reasoning process into smaller steps (similar to Chain-of-Thought prompting), and explicitly aims to deduce and justify each step using the extracted premises. The framework is based on prompt engineering and does not use external systems, so it can be categorized into self-verification. This work is mainly benchmarked against previous CoT prompting and faithful CoT.", "questions": "- Table 2, what does the Correct/Wrong mean here? By Correct, do you mean that when supplied with correct answer and sampled reasoning chains, the chance of the ChatGPT model giving a yes after being prompted with 'Do you think the above reasoning process is correct? Let’s think step by step'? \n- Table 3, Natural Program appears to be particularly good on the AQuA dataset. Could there be some case analysis here?\n- Table 4, how are minimal premises decided here? In practice, it is always hard to figure out the minimal set of premises to derive a certain proposition, so I assume the actual performance of the framework will be between Full Premises and Minimal Premises, right?", "limitations": "I believe the authors have addressed the limitations well.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Lack of robustness/trustworthiness is surely one of the main drawback in LLMs' reasoning. The paper presents a plausible framework that resemble the idea in classic symbolic theorem proving and incorporate explainability into LLMs' reasoning process. The paper is nicely structured and with well-crafted examples to illustrate the main idea of this paper at a high level. ", "weaknesses": "Though the idea of Natural Program is plausible, it would be nice to see slightly more experiments and case analysis, which could further demonstrate the efficacy of this approach. For example, the cited Faithful-COT paper has several other benchmarks like CLUTRR and StrategyQA, and it has also experimented on GPT-4, which showed an amazing advantage over ChatGPT over the benchmarked tasks. It would be interesting to see how well Natural Program performs on advanced models like GPT4.\n\nAnother line of related work is Selection-Inference [1] and Faithful Reasoning [2]. I know the authors have cited the later but I believe more comparison is needed as both these works and Natural Program have a premise selection phase. It would also be interesting to see if Natural Program continue to work well on datasets like ProofWriter.\n\n[1] Creswell, Antonia, Murray Shanahan, and Irina Higgins. \"Selection-inference: Exploiting large language models for interpretable logical reasoning.\" arXiv preprint arXiv:2205.09712 (2022).\n\n[2] Creswell, Antonia, and Murray Shanahan. \"Faithful reasoning using large language models.\" arXiv preprint arXiv:2208.14271 (2022).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your constructive feedback and your appreciation of our work! We address the comments and questions below.\n\n> Q1: Add experiments over more benchmarks like CLUTRR and StrategyQA.\n    \nThanks for your suggestion. For StrategyQA, we sample 1000 instances from the dataset. We use 7-shot samples for CoT and 1-shot sample for Natural Program. For CLUTRR, we sample 200 instances from the dataset due to limited rebuttal time. We use 8-shot samples for CoT and 2-shot samples for Natural Program. Both datasets are shuffled with random seed 42.\n\n**Final answer accuracy on StrategyQA and CLUTRR**\n|    Methods   |  StrategyQA | CLUTRR |\n| --- | --- | --- |\n| CoT (few-shot) | 72.45% | 39.25% |\n| Natural Program (1-2 shot) | 69.95% | 46.00% |\n    \n> Q2: Add experiments with advanced models like GPT-4\n\nThanks for your suggestion! It would be a great idea to explore more advanced models like GPT-4. However, due to the high costs associated with GPT-4, particularly when combined with majority voting, we'd like to postpone this exploration to future work when GPT-4 becomes more cost-effective.\n    \n> Q3: Related work and comparison with \"Selection-Inference\" family\n\nThanks for bringing attention these works and we'll cite \"Selection-Inference\". We'd also like to note that while both Selection-Inference and Natural Program have premise selection phases, their mechanisms are different. The selection model within the Selection-Inference framework selects facts exclusively from the given context, effectively preventing fact hallucination. On the other hand, Natural Program is more flexible for e.g., instruction-based open-ended reasoning problems, such as Last Letters, which instructs LLMs to output the concatenation of the last letters of all words in a sequence.\n\n> Q4: Evaluate Natural Program on ProofWriter\n\nThank you for your suggestion. We conduct a random sampling of 100 examples with a depth of 3 from the development subset of the ProofWriter CWA dataset. Both Natural Program and CoT are evaluated using GPT-3.5-turbo (ChatGPT) with a one-shot example as a prompt. The results can be found in the table below.\n\n**Final answer accuracy on ProofWriter**\n| CoT | Natural Program |\n| --- |  --- |\n|  87.00% | 93.50% |\n    \n\n> Q5: What is the meaning of \"Correct/Wrong\" in Table 2?\n\nThanks for your question. Yes, your understanding is correct. Results in Table 2 illustrate the percentage of verification validity outputs that align with the answer correctness (\"Correct/Wrong\") of reasoning chains.\n\n> Q6: Results are perticually good over \"AQuA\". \n\nThanks for pointing this out. Upon analysis on AQuA, we found that baseline CoT performed worse than Natural Program mainly because its answer responses were not consistently capitalized (e.g., output can be \"A\" or \"a\"), which is further because the few-shot prompt from the original CoT paper uses small letters while query questions use capitalized letters. Our previous answer parser only considered capitalized answer choices as correct. Therefore, we adjusted our answer parser to accommodate different capitalizations in answer choices, which improved the accuracies of baselines from our previous Table 3. \n    \nWe have updated Table 3 in \"Common Response\". After the update, our Natural Program performs comparably to the CoT baseline on AQuA.\n\n> Q7: How are minimal premises decided in Table 4?\n\nYes, your understanding is correct. \"Minimal premises\" means that when verifying each reasoning step from a Natural Program reasoning chain, we only keep the premises whose numbers are cited by that reasoning step as its context for verification. While we encourage LLMs to cite the minimal set of premises when generating reasoning chains in our Natural Program prompt, LLMs might still cite irrelevant premises during actual problem solving processes, thereby introducing irrelevant premises for verification."}]

Author rebuttal:
# Common Response

We sincerely thank all reviewers and ACs for their constructive feedback! We're glad that reviewers found our paper well-motivated (`LzaJ, BLD6, TPbw`), our verification framework and ideas plausible (`bmW6`) and good (`kmTd`), our observations intersting (`BLD6`), and our papers clear and easy to follow (`TPbw, bmW6`).

We address common reviewer comments here and provide a revision of our tables.

> Primary goal of this work

We'd like to first clarify that our primary goal is *NOT* to improve the final answer accuracy of reasoning tasks. Our primary goal is to encourage the **validity of each reasoning step**, emphasizing LLM reasoning reliability over final answers.

To this end, we first discover that naively verifying complex reasoning chains with LLMs yields low accuracy (see Table 2) because of intertwining reasoning-step dependencies that confound LLMs. We thus propose Natural Program-based verification, decomposing chains into steps and verifying each step with *only* its necessary context and premises. This significantly improves verification accuracy (see Table 4), enhancing LLM-generated reasoning's reliability and achieving our primary goal.

> Adding F1 metric to Tables 2, 4, 5

We appreciate Reviewer LzaJ's suggestions. We have added F1 scores to Tables 2, 4, and 5. When calculating F1 scores, for reasoning chains that are correct, a "true positive" is defined as a verification approach outputing "yes" for the final validity answer; for reasoning chains that are incorrect, a "true positive" is defined as a verification approach outputing "no" for the final validity answer.

**Table 2**: Two-shot reasoning chain verification accuracy for GPT-3.5-turbo with a naive verification approach, where we input an entire reasoning chain for verification, and premises of different reasoning steps are entangled together. Prompt in Appendix Table 10.

|Answer Correctness|GSM8K|AQuA|MATH|AddSub|Date|Last Letters|
|-|-|-|-|-|-|-|
|Correct|98.00%|96.00%|100.00%|92.00%|100.00%|96.00%|
|Incorrect|2.00%|4.00%|0.00%|6.00%|26.00%|6.00%|
|F1|35.03%|36.58%|33.33%|37.43%|57.13%|38.56%|

**Table 4**: 1-shot deductive verification accuracy for GPT-3.5-turbo using our Natural Program-based approach with step-by-step reasoning chain decomposition. During the verification of each reasoning step, we consider two options: utilizing the complete premises $p_i=QC \cup S_{\le j}$, or keeping the minimal set of premises $\bar{p_i} \subseteq p_i$.

|Premise Context|Answer Correctness| GSM8K|AQuA|MATH|AddSub|Date|Last Letters|
|-|-|-|-|-|-|-|-|
||Correct|64.00%|54.00%|58.00%|95.00%|26.00%|96.00%|
|Full Premises|Incorrect|56.00%|68.00%|56.00%|24.00%|76.00%|5.00%|
||F1|59.94%|60.81%|56.70%|53.66%|47.73%|37.58%|
||Correct|84.00%|72.00%|70.00%|95.00%|90.00%|96.00% 
|Minimal Premises|Incorrect|84.00%|62.00%|76.00%|40.00%|56.00%|6.00%|
||F1|84.00%|66.92%|72.98%|64.84%|72.20%|38.56%|

**Table 5**: Ablation of different values of k′ on the verification accuracy of reasoning chains using our Unanimity-Plurality Voting strategy. Experiments are performed on AddSub using GPT-3.5-turbo.

|Answer Correctness|k′=1|k′=3|k′=5|k′=10|
|---|---|---|---|---|
|Correct|86.00%|90.00%|90.00%|92.00%|
|Incorrect|38.00%|38.00%|38.00%|40.00%|
|F1|59.68%|61.39%|61.39%|63.53%|


> Revision of Table 3

**The major goal of this work is to improve the trustworthiness and reliability of reasoning. Table 3 aims to illustrate that, along this process, our deductive verification approach does not significantly compromise the accuracy of the final answers.**

We update Table 3 results here and will update our submission pdf in the future. For the baselines (CoT and Faithful CoT), we adopt the implementations from their original repositories and report the results. These baselines utilize varying numbers of few-shot samples across datasets, exceeding our approach's usage (we use 2-shot for Date and 1-shot for other datasets). Additionally, for AQuA, we observed an inconsistency in capitalization between the baseline CoT's official few-shot prompt and the AQuA answer choices. This discrepancy led the baseline CoT to generate answers with random capitalizations. Our previous answer parser only considered capitalized answer choices as correct, so we adjusted our answer parser to accommodate different capitalizations, which improved the accuracies of baselines.

We find that prompting language models to reason in our Natural Program format sometimes achieves better final answer accuracy than baselines. Upon further applying our deductive verification approach to filter out invalid reasoning chains, we observe a slight decrease in final answer accuracy. **One major contributing factor to this decrease is the filtering out of reasoning chain candidates that provide correct answers but exhibit incorrect deductive reasoning**. An example is illustrated in Table 6 of our submission, where ChatGPT generates the correct final answer but assigns incorrect premise numbers to support the first reasoning step. We note that in many such cases, our verification approach effectively identifies these reasoning errors, thereby enhancing the rigor and reliability of the language models’ reasoning processes, albeit with a slight negative impact on the overall final answer correctness.

**Table 3**: Final answer accuracy comparison on GPT-3.5-turbo. All approaches generate $k = 10$ reasoning chains for each problem before performing majority voting or reasoning chain filtering with our deductive verification approach.

|Methods| GSM8K|AQuA|MATH|AddSub|Date|Last Letters|
|-------|------|----|----|------|----|------------|
|CoT + Voting, few-shot|87.62%|70.18%|35.93%|92.36%|69.97%|81.60%|
|Faithful CoT + Voting, few-shot|81.20%|61.80%|31.78%|88.35%|73.50%|-|
|Ours (Natural Program (NP), No Verification), 1-2 shot|87.05%|70.34%|36.75%|93.67%|72.49%|92.98%|
|Ours (NP + Deductive Verification + UPV), 1-2 shot|86.01%|69.49%|36.48%|93.54%|71.45%|92.60%|

Meta-review: While the high-level idea of Deductive Verification of CoT motivating this paper is somewhat straightforward, it is far from trivial to work out details that make such a deductive approach work in practice and I (along with many reviewers) are happy to see such contributions along with the experimental results.  Paraphrasing from a reviewer comment: the topic is interesting, the authors test on a variety of interesting domains, and the approach is adaptable.  In the end, the majority of reviewers agreed to recommend acceptance but also recommend the authors to incorporate critical clarifications that came up in the reviews/rebuttal/discussion.

I won't mention all points of clarification, but I do want to highlight two particular key points where clarification on revision will improve the paper:

Reviewer TPbw and BLD6 both raise issues concerning circularity in defining validity in terms of the LLM itself in a zero-shot manner.  As one reviewer states: "the paper could benefit from a better understanding of when and why validity =/=> correctness".  While the reviewer perspective may differ from the author position here, these issues should be acknowledged and discussed on revision along with potential suggestions for future work that may mitigate any concerns.  

Further, the final comments in response to reviewer TPbw w.r.t. NLProofS and reasoning chains are very helpful and should be incorporated in the final revised paper.
Decision: Accept (poster)