Deductive Beam Search: Decoding Deducible Rationale for Chain-of-Thought Reasoning

Authors: tinghui  zhu
kai  zhang
jian  xie
yu  su
Venue: colmweb_org_COLM_2024_Conference
Published: 2024-03-21 17:50:44

Abstract: Recent advancements have significantly augmented the reasoning capabilities of Large Language Models (LLMs) through various methodologies, especially chain-of-thought (CoT) reasoning. However, previous methods often struggle to address reasoning errors in intermediate steps, which can lead to accumulative errors. In this paper, we propose Deductive Beam Search (DBS), which seamlessly integrates CoT and deductive reasoning with step-wise beam search for LLMs. Our approach deploys a verifier, verifying the deducibility of a reasoning step and its premises, thus alleviating the error accumulation. Furthermore, we introduce a scalable and labor-free data construction method to amplify our model’s verification capabilities. Extensive experiments demonstrate that our approach significantly enhances the base performance of LLMs of various scales (7B, 13B, 70B, and ChatGPT) across 8 reasoning datasets from 3 diverse reasoning genres, including arithmetic, commonsense, and symbolic. Moreover, our analysis proves DBS’s capability of detecting diverse and subtle reasoning errors and robustness on different model scales.

Main paper: 
 deductive beam search: 
 We begin by formulating multi-step CoT reasoning with step-wise beam search before describing DBS. For notation convenience, we denote [n] to be a set of natural numbers from 1 to n, and v[n] = [v 1 , v 2 , ..., v n ] represents the first n elements of v, where v [0] = []representing an empty sequence. Specifically, we denote tokens as y.Standard chain-of-thought reasoning (Wei et al., 2022b) generates the whole reasoning path for the final outcome. Formally, given the question q, CoT formulates the answer distribution Pr LM (a|q) as a product of the rationales generation distribution Pr LM (r [t] |q)and a final answer distribution Pr LM (a|r [t] ), which is:EQUATIONwhere r [t] = [r 1 , r 2 , ..., r t ] is a complete reasoning path, and t is the number of steps required to complete the reasoning process. Each r = [y 1 , y 2 , ...y l ] is an intermediate reasoning step, where l is its token length.Problems in this setting lie in the complexity of navigating the generation of r [t] , which are sampled as a whole directly from language models, a process wherein errors can accumulate (Zhang et al., 2023a) . To avoid error accumulation and navigate the reasoning process, we decompose the process of generating r [t] as:Pr LM (r [t] |q) = Pr LM (r 1 |q) × t-1 ∏ i=1 Pr LM (r i+1 |q, r [i] ) = t-1 ∏ i=0Pr LM (r i+1 |q, r [i] ).(2)As Equation 2 suggested, at timestamp i, the language model generates the next reasoning step r i based on previous premises, which is r i ∼ Pr LM (r i |q, r [i-1] ). This formulation follows the principle of deductive reasoning.Under beam size m, traditional beam search decodes at token level, which stores Topm candidate tokens, and uses them for future decoding. Formally, we denote the logprobability of LM generating the k-th tokens as ϕ(y k ) = log Pr LM (y k |y 1 , y 2 , ...,y k-1 , x) = log Pr LM (y k |y [k-1] ,x), and the log-probability of a solution at timestamp k as Φ(y[k] ) = ∑ i∈[k] ϕ(y i ).Given a set of m previous solutions at timestamp i asY i-1 = {y 1 [i-1] , y 2 [i-1] , ..., y m [i-1]}, beam search generates as:EQUATIONHowever, in reasoning tasks, it is hard to verify whether a single token is deducible. Thus, we assign a reasoning step r as the minimal unit in step-wise beam search. Formally, we denote the log-probability of generating the k-th reasoning step as ψ(r k ) = Φ(y) and the log-probability of a solution at timestamp k to be Ψ(rEQUATIONCombining multi-step CoT reasoning with step-wise beam search balances exploration and exploitation in reasoning tasks. However, confidence scores from language models cannot verify logical consequence between a reasoning step and its premises. To tackle this problem, we propose to constrain the step-wise beam search with deductive scores.To verify the logical coherence between a reasoning step and its premises, we propose to train a deductive verifier since LLM itself often fails to detect reasoning errors (Hong et al., 2023) . Formally, given premises c [i] = [c 1 , c 2 , ..., c i ] and the candidate reasoning step r, the deductive score can be formulated as:s = f (c [i] , r) = Pr f (r|c 1 , c 2 , ..., c i ),where f is the deductive verifier function. The details of the deductive verifier are illustrated in Section 3. Then, we utilize the deductive verifier to constrain the step-wise beam search. To clearly illustrate the process, we show the case how, given one antecedent solution beamr [i-1] ∈ R [i-1]at timestamp i, reasoning steps are sampled and scored.In the exploration phase of beam search, the language model samples a list of potential reasoning steps. Concretely, for sampling times n, the question q and r[i-1] form the current context c [i] = [q, r [i-1] ],and we can sample a set of n possible reasoning steps Ri = {r 1 , r 2 , ..., r n }, where r ∼ Pr LM (r|q,r [i-1] ). Concatenating r ∈ Ri with r [i-1] generates candidate reasoning chains set R[i] = {[r [i-1] , r 1 ], [r [i-1] , r 2 ], ..., [r [i-1] , r n ]} at timestamp i.In terms of exploitation, instead of using the language model probability Pr LM (r|c [i] ) to evaluate these reasoning steps, deductive verification scores S = {s 1 , s 2 , ..., s n } of candidate reasoning paths Ri are applied. Each score s j , j ∈ [n] is calculated by multiplying the score of r [i-1] and the score of each candidate reasoning step, that is:EQUATIONwhich follows the autoregressive factorization form and allows us to apply on the beam search algorithm.Consequently, LM generates n times for each beam at each step, sampling a total number of m × n candidate reasoning steps. After scoring on these steps, the top m of them are selected according to the deductive score. This cycle of exploration and exploitation repeats until the final answer is generated or it reaches the upper limit of reasoning length. 
deductive verifier: 
 As stated above, a deductive verifier evaluates whether the reasoning step can be deduced from previous contexts, which resembles a natural language inference (NLI) task. Thus, we use deberta-v3-large (He et al., 2021), which achieves the best performance across various NLI benchmarks despite its small size, as the backbone. A small scalar head is adopted to predict deductive scores based on embedding the [CLS] token.However, the difficulties of training a deductive verifier primarily reside in the training data quality and the training method. Changing one single token could lead to various errors, which is hard for any model to detect. Furthermore, the lack of high-quality false deductive reasoning step hinges the training of the verifier. To fully understand how LLMs make mistakes, we dive into the incorrect samples generated by LLMs. From the perspective of deductive reasoning, there are two main classes of reasoning errors: grounding errors and logic errors (Ling et al., 2024) . Most grounding errors happening in the reasoning process can be detected by finding the contradiction between the context and the rationales, while the latter ones are illogical reasoning steps deduced from the previous context. simulate typical false reasoning and train the verifier to detect them. In stage 2, the verifier trained from stage 1 is deployed to detect potential false reasoning steps generated by LLMs, bridging the gap between synthetic data and real-world data. Consequently, the model from stage 1 is continue-trained.In the first stage, we require the verifier to detect two general types of reasoning errors: grounding error and logic error. However, such fine-grained step-wise data is hard to annotate. Thus, we propose to synthesize false reasoning steps automatically.Since it is hard to edit natural language to meet our demands, we turn to arithmetic reasoning, which can be viewed as a middle ground between symbols and natural language.In terms of reasoning steps with grounding errors, we randomly replace one of the numbers on the left side of the equation in the gold reasoning step with numbers existing in previous contexts or randomly generated numbers to simulate false grounding or hallucinations. As for logic errors, we randomly select reasoning steps after the current gold reasoning step. Under this circumstance, the reasoning process is reversed and disrupted, making it a logic error. Moreover, to enhance the understanding of the model for this task, we use randomly selected reasoning steps across the whole dataset as an irrelevant false reasoning step. The examples of these errors are shown in Table 1 .To provide fine-grained supervision for error detection, we use margin ranking (Shashua & Levin, 2002) Then, the loss of ranking these reasoning steps is formulated as the weighted sum of three margin ranking losses:EQUATIONwhere m i is the hyper-parameter controlling the margin and α i weighs each loss.In the first stage, we train a general deductive verifier, but the wrong samples synthesized heuristically are less diverse than the ones encountered during inference. To bridge the gap between synthesized data and real-world data, we use the verifier from stage 1 to detect false reasoning steps generated by an actual language model, where we choose Llama2-7b for the generation. The reason why we choose a relatively small language model for the generation is to maximize the diversity and the likelihood of generating incorrect steps.To be concrete, given the verifier f 1 trained by stage 1, we feed context c into the LLM and sample 10 reasoning steps. Then, these steps are scored and ranked by f 1 . From this ranking, we select the reasoning step that exhibits the most significant decrease in the deductive score, designating it as the hard negative sample. We replace r (Talmor et al., 2019) and StrategyQA (Geva et al., 2021) . CommonsenseQA asks the model to choose the best answer from 5 choices, and StrategyQA asks for a True/False answer.Symbolic Reasoning. We use the Coin Flip dataset (Wei et al., 2022b) . The task is to determine which face of the coin is up after a series of operations. 
details: 
 Language Models. We evaluate our method on models of various scales, including Llama2-7b, Llama2-13b, Llama2-70b (Touvron et al., 2023) , and ChatGPT (gpt-3.5-turbo-instruct) (Ope-nAI, 2022). These models represent different levels of reasoning abilities. For the verifier, we choose deberta-v3-large as the backbone of our verifier. The training details are in Appendix B.Prompts. For arithmetic reasoning tasks, we apply one prompt to all tasks. For commonsense reasoning tasks and the symbolic reasoning task, we write a prompt for each task to ensure the model can output the correct answer format. All methods are evaluated by the same prompt on each task. The details of prompts are in Appendix B.3.To prove the effectiveness of DBS, we compare with greedy decoding algorithm (Jurafsky & Martin) and self-consistency (Wang et al., 2022) . For other SOTA baselines, we choose SelfEval (Xie et al., 2023) and Deductive Verification (Ling et al., 2024) , which do not update the parameters of LLMs. The former represents SOTA decoding algorithm, while the latter stands for methods utilizing novel procedure design to conduct deductive reasoning. Since a full-scale experiment requires excessive token cost due to the extensive search and verification of these methods, we provide results on the GSM8K dataset.Inference. During inference, we set beam size m to 5 and sampling times n to 10. For all models and baselines, we use their default parameter settings for generation. 
main result: 
 Table 2 demonstrates the overall performance of the methods. We compare DBS with baselines under two paradigms: single chain setting and multiple chain setting. In multiple chain setting, the generated outcomes are integrated with self-consistency. Table 3 presents a comparative analysis of our approach against SOTA baselines.As shown in Table 2 , DBS improves the performance across models of different scales and diverse reasoning tasks. For the single chain setting, the improvement is substantial. On arithmetic reasoning tasks, taking GSM8K as an example, we observe an increase from 7.6% to 16.6% across models of various scales. Specifically, with Llama2-7b and gpt-3.5-turboinstruct, DBS yields improvements of 9.2% and 7.0%, respectively, affirming the effectiveness of our proposed strategy. On commonsense reasoning tasks and symbolic reasoning tasks, we can expect an average increase of 2.5%/2.0% on models of all scales.Regarding the multiple reasoning chain setting, DBS outperforms naive self-consistency. Concretely, we can see an average of 3.0% improvement on arithmetic reasoning tasks, 0.5% on commonsense reasoning tasks, and 1.0% on symbolic reasoning tasks, respectively. On the SingleEq and StrategyQA datasets, the performance of DBS on ChatGPT is slightly lower (-0.6%/-0.8%). These datasets require fewer reasoning steps for the final answer, as opposed to our paradigm of multiple reasoning steps. Nevertheless, the universal improvements demonstrate the effectiveness of our proposed method. The comparative results, grounded in accuracy and token cost metrics, substantiate our approach's effectiveness and token efficiency. Notably, the self-evaluate pattern performs worse when the scale of the LLM drops. Moreover, it consumes an excessive amount of tokens during evaluation. In contrast, DBS enhances the performance by approximately 10% on Llama2-7b and performs better than the baselines on gpt-3.5turbo-instruct across the paradigms of single and multiple reasoning chains. Furthermore, it consumes much fewer input and output tokens. Consuming 80 times less tokens, DBS outperforms DV on gpt-3.5-turbo-instruct. 
analysis: 
 We conduct a detailed analysis to investigate the verifiability and efficiency of our proposed method. Moreover, we show how our method can adapt to different settings.Method MRR HITS@1 HITS@3 HITS@5 ChatGPT 0.48 0.32 0.49 0.67 Our Verifier 0.59 0.41 0.69 0.86 We comprehensively analyze the verifiability of our proposed verifier on performance (Table 4 ) and score distribution (Figure 3 ).For empirical experiments, we test how our verifier will score the gold reasoning steps compared to synthesized reasoning steps. We randomly sample 500 context-step pairs from the test set of the GSM8K dataset as gold reasoning steps. For each pair, we synthesize nine reasoning steps using Llama2-7b as inferior reasoning steps. The verifier's task is to rank them, and the performance is evaluated by four metrics, namely, Mean Reciprocal Rank (MRR), HITS@1/3/5. MRR evaluates the average rank of the gold reasoning step, and the HITS metrics reflect whether the gold reasoning step will be chosen under beam size setting 1/3/5. To compare with the self-evaluation pattern, we ask ChatGPT to rank these reasoning steps rather than predict scores, leveraging its inherent reranking capabilities (Ma et al., 2023) . The results are listed in Table 4 . Our verifier outperforms ChatGPT across all metrics, evidencing its capability. Notably, our verifier correctly identifies 86% of the gold reasoning steps within the top 5 positions out of 10 samples, affirming the deducibility of the reasoning paths decoded under m = 5, n = 10.Distribution Analysis. To ascertain the reliability of our verifier, we compare the score distributions for correct and wrong predictions between the original LM confidence (gpt-3.5turbo-instruct) and our deductive verification score. We use results from greedy decoding, which naturally produces confidence scores from LM, and ask the verifier to score on them. Figure 3 shows the substantial difference between an LM confidence score and our deductive score. Notably, the LM confidence score demonstrates a mere 4% increase in scores of the correct reasoning paths, whereas our verifier exhibits a 17% increase. This significant difference proves the enhanced verifiability of our verification approach.The cost of sampling multiple times is enormous. We analyze the cost of our methods under different settings and compare them with the baselines. Specifically, we compare our approach with greedy decoding, self-consistency, SelfEval (Xie et al., 2023) , and DV (Ling et al., 2024) . The results are presented in Table 3 and Table 5 . Our analysis reveals that greedy decoding is the most token-economic, as it does not involve any form of sampling, but its performance lags. When m is constrained to 1, the token generation is minimized even further than that required by self-consistency strategies. Still, our method demonstrates higher accuracy. Moreover, DBS proves more effective and token-efficient under the same beam size than those leveraging LLMs' self-evaluation capabilities. Unlike arithmetic or symbolic reasoning tasks, commonsense reasoning tasks leverage the model's intrinsic commonsense. Thus, we introduce a prompt strategy, which asks the model to recall the necessary commonsense via greedy decoding, followed by DBS navigating the reasoning over the elicited contexts. We compare this setting to standard settings and baselines, and the results are shown in Table 6 . The performance varies from different tasks, attributed to the distinct nature of the tasks. Concretely, StrategyQA typically requires a 2-3 step knowledge recall followed by a single reasoning step, whereas CSQA demands a 3-5Question Greedy Ours James decides to run 3 sprints 3 times a week. He runs 60 meters each sprint. How many total meters does he run a week? He runs 3 times a week, which is equal to 3 x 7 = 21 sprints. 0.0102 The distance he runs each sprint is 60 meters, so the total distance is 60 x 21 = 1320 meters. step recall process alongside multiple reasoning steps. Our findings suggest that the recall prompt is more suitable for tasks demanding multi-step reasoning.Table 7 presents two GSM8K examples from Llama2-7b. The first example demonstrates a scenario where hallucination emerges under greedy decoding, which our verifier identifies with an extremely low score, thereby precluding its selection by our deductive decoding strategy. On the contrary, every reasoning step from our reasoning path is deduced from the previous context and is scored much higher than the incorrect steps. In the second example, a grounding error occurs in steps marked by red scores. Although the wrong reasoning steps resemble the correct ones, our verifier detects these minor errors. In both examples, the reasoning path generated by our decoding strategy initiates the reasoning by listing premises, followed by one reasoning step. This pattern strictly follows the principle of deductive reasoning, making the generated results more deducible. 
related work: 
 Answer Aggregation. Sampling techniques of language models, such as temperature sampling (Ackley et al., 1985) , top-k sampling (Fan et al., 2018) , and top-p sampling (Holtzman et al., 2019) , bring diversity to the outcome but also uncertainty to the reasoning process, which is not favored in reasoning tasks. These methods aim to reduce uncertainty in the reasoning process by aggregating answers from sampled reasoning paths. After sampling diverse outputs from LLMs, Wang et al. (2022) propose to use consistency as the metric to aggregate the answers. Other methods evaluate whether the reasoning step can lead to the correct answer by training a verifier (Li et al., 2023; Wang et al., 2023) .Recent research on reducing reasoning errors is inclined to follow the self-verify-then-correct pattern (Dhuliawala et al., 2023; Weng et al., 2022; Zhang et al., 2023b; Ling et al., 2024; Miao et al., 2023) . They design different procedures and prompts to achieve better performance. Taking two typical approaches as examples, Dhuliawala et al. (2023) design a chain-of-verification procedure to verify facts from its outputs, and Miao et al. (2023) ask LLM to detect errors in their step-by-step rationales. However, recent works (Huang et al., 2023; Hong et al., 2023) have pinpointed a critical limitation of LLMs in self-correction during reasoning tasks. Their findings suggest that LLMs indiscriminately alter reasoning steps without external feedback, irrespective of their initial accuracy.Decoding Strategies. Conventional decoding strategies include greedy decoding (Teller, 2000) , which selects tokens with the highest probabilities, and beam search (Graves, 2012) , which stores candidate beams for future prediction. In the era of LLMs, these decoding strategies are implemented at a more coarse-grained level, especially on reasoning tasks involving multiple steps. They decompose the reasoning process into steps (Khot et al., 2022) and apply decoding or search algorithms (Yao et al., 2023; Xie et al., 2023) . 
conclusions: 
 In this paper, we aim to eliminate errors in intermediate reasoning steps in CoT reasoning, making it more reliable. To this end, we propose Deductive Beam Search that integrates CoT with step-wise beam search and scores each reasoning step with a deductive verifier, which verifies whether the reasoning step is a logical consequence. Beam search explores by sampling potential reasoning steps, while the verifier exploits by selecting the most deducible steps. To train such a verifier, we propose a scalable and labor-free data construction method. It initiates by heuristically introducing errors into gold reasoning steps and enhances the diversity and difficulty of training data by synthesizing hard negatives through the verifier trained on those typical wrong steps. Extensive experiments show our method's effectiveness across various model scales and diverse reasoning tasks without changing the standard CoT paradigm and parameters of LLMs. Further analysis proves the verifiability and robustness endowed by our verifier, thereby significantly improving the deducibility of the generated reasoning paths.  
question:: 
 James decides to run 3 sprints 3 times a week. He runs 60 meters each sprint. How many total meters does he run a week?Step 1: He runs 3 times a week, which is equal to 3 x 7 = 21 sprints.Step 2: The distance he runs each sprint is 60 meters, so the total distance he runs is 60 x 21 = 1320 meters. Final Answer: 1320Step 1: Grounding error. 7 does not come from premises.Step 2: Accumulative error. Misled by errors in step 1. Machine reasoning has witnessed tremendous progress thanks to the emergence of Large Language Models (LLMs) (OpenAI, 2023; Google, 2023; Anil et al., 2023; Touvron et al., 2023; McIntosh et al., 2023) . The power of LLMs activates the ability to conduct step-by-step chain-of-thought (CoT) reasoning (Wei et al., 2022b; a) , significantly boosting the performance of reasoning tasks (Wang et al., 2022; Paul et al., 2023; Lyu et al., 2023) .Although CoT reasoning has demonstrated the superiority of step-by-step reasoning, its dependency on intermediate steps inevitably introduces accumulative errors (Du et al., 2023; Yu et al., 2023) in the process, as shown in Figure 1 . Previous research that alleviates these errors lies in two main paradigms: 1) Answer aggregation across multiple rationales. They utilize majority voting (Wang et al., 2022) or deploy a verifier to score on each rationale (Li et al., 2023) . However, these methods do not directly address errors in the reasoning process, undermining the reliability of their outcomes. 2) Intermediate stepThe number of sprints per week is 3 x 3 = 9 sprints.He runs 3 times a week, which is equal to 3 x 7 = 21 sprints.The number of sprints per week is 3 x 3 = 9 sprints. So the total distance he runs is 60 x 21=1320 meters.So the total distance of 9 sprints is 9 x 60 = 540 meters.The distance of each sprint is 60 meters.James decides to run 3 sprints 3 times a week. He runs 60 meters each sprint. How many total meters does he run a week?The distance of each sprint is 60 meters.Therefore, the total distance James runs in a week is 9 x 60 = 540 meters.So the total distance of 9 sprints is 9 x 60 = 540 meters. 540 … …Deductive ScoreLow HighStep 1Step 2Step 3QuestionThe distance of each sprint is 60 meters.So the total distance of 9 sprints is 9 x 60 = 540 meters.VerifierLow deductive score! Aborted The number of sprints per week is 3 x 3 = 9 sprints.Figure 2 : Overview of Deductive Beam Search. We illustrate the process under the configuration of beam size 2 and sampling times 2.correction. This line of works decomposes the reasoning path into reasoning steps and applies self-correction on each step (Weng et al., 2022; Ling et al., 2024; Paul et al., 2023; Xie et al., 2023 ). Yet, recent research finds that, without external feedback, LLMs tend to modify reasoning steps regardless of their correctness (Huang et al., 2023; Hong et al., 2023) .Previous works fail to address reasoning errors in intermediate steps, compromising the ability to conduct systematic reasoning. To mitigate this issue, we embrace the principle of deductive reasoning (Clark, 1969; Johnson-Laird, 1999; 2010) . In deductive reasoning, every step logically follows its premises, where a deducible reasoning step is termed a logical consequence (Dinkmeyer, 1976; Hanson, 1997) . A key attribute of logical consequence is that if the premises hold, the deducible reasoning step is true, suggesting a correct outcome.Inspired by this attribute, we propose to navigate CoT towards a more deducible path.Nonetheless, challenges arise when introducing the principle of deductive reasoning into CoT reasoning without changing the standard prompt paradigm and the parameters of LLMs. 1) Navigation on CoT reasoning. Since LLMs cannot always conduct correct deductive reasoning, they have to explore the potential reasoning space and choose those reasoning steps that are more likely to be deducible, which brings the trade-off between exploration and exploitation (Donoso et al., 2014; Dasgupta et al., 2019) . 2) Verification of deducibility. On one hand, previous research shows it is hard for LLMs to detect reasoning errors (Huang et al., 2023; Hong et al., 2023) . On the other hand, symbolic reasoning engines (Cavada et al., 2014; Li et al., 2018) can reliably verify the correctness. However, transferring natural language to symbolic language without losing generality remains an unsolved problem in machine reasoning.Confronted with these challenges, we propose Deductive Beam Search (DBS), adaptable to all models and settings. The overview of DBS is shown in Figure 2 . For the trade-off challenge, we decompose the reasoning process into reasoning steps and incorporate stepwise beam search. In terms of the verification challenge, we propose a deductive verifier, which takes a reasoning step and its premises as inputs and outputs a deductive score, evaluating the logical coherence between them. Specifically, LLM samples a list of potential reasoning steps to explore. Then, our deductive verifier exploits by selecting steps that are more deducible. To train an effective verifier, we propose a scalable way of synthesizing fine-grained and diverse deductive reasoning errors without human annotation. Initially, the verifier is trained to verify heuristically synthesized wrong steps with typical reasoning error patterns. Subsequently, we ask LLMs to generate reasoning steps where false ones detected by our verifier serve as hard negatives. These hard negatives are adopted to train a deductive verifier with model feedback.As we aim to enable LLMs to decode more deducible reasoning paths, DBS can be integrated with answer-aggregation-based methods. We evaluate our methods across 5 arithmetic reasoning tasks, 2 commonsense reasoning tasks, and 1 symbolic reasoning task in single chain setting and multiple chain setting. The improvements can be expected not only on models of all scales and diverse model families but also under different settings. Concretely, taking arithmetic reasoning tasks as an example, the average improvement is 5.3% / 3.2% on Llama2-7b / ChatGPT under single chain setting and 3.9% / 2.5% under multiple chain setting. Moreover, we comprehensively analyze our verifier, demonstrating its capability of detecting diverse and subtle reasoning errors and robustness on different model scales. 
 
 Appendix: Ablation study on beam size. We conduct experiments on how beam size affects performance. Figure 4 shows the trend of DBS performance under single chain setting and multiple chain setting. The performance steadily grows when the beam size rises.Verifier Robustness. To ensure that our verifier can equally verify reasoning steps generated by different models, we visualize the accuracy under different deductive score thresholds for Llama2-7b and ChatGPT, as depicted in Figure 5 . The lines in the figure represent polynomial fits of the data. Their near-parallel alignment suggests the robustness of performance improvement across these models as the threshold increases. Intriguingly, these lines also offer insights into the inductive reasoning capabilities of the two models. Ideally, the accuracy approaches zero at the deductive score zero. However, the observed non-zero accuracy suggests the models' inductive reasoning capabilities. Although the reasoning process might not align with the deductive reasoning paradigm, LMs can still arrive at correct conclusions, likely by intuitively skipping over specific reasoning steps, which is the act of inductive reasoning. DBS Robustness. To demonstrate that DBS can sustain its accuracy as the length of the reasoning steps increases, we conducted experiments to analyze the impact of reasoning step length on the final outcome's accuracy. The results, presented in Figure 6 , indicate that DBS consistently achieves higher accuracy, even when the reasoning process extends to 15 steps.At stage 1, we choose GSM8K dataset to train the general deductive verifier. The gold rationales provided are decomposed into sentences as gold reasoning steps. After filtering out some steps that cannot be altered into false reasoning steps, we construct a training dataset of 22,362 samples. At stage 2, the verifier from stage 1 is used to generate hard negative reasoning steps as stated in Sec. 3. We choose Llama2-7b as our language model to generate candidate false reasoning steps. For arithmetic reasoning and symbolic reasoning tasks, we 


Decision: The reviewers agreed this is an important research direction and interesting algorithm. Most of the concerns were about baselines and exact sets of experiments, etc. However, the authors were able to directly answer all of the concerns and clarify confusions to my satisfaction, even if one of the reviewers didn't agree.

Reviews: review: paper_summary: paper_summary: In this paper, the authors propose Deductive Beam Search (DBS) to alleviate accumulated errors in LLM CoT reasoning. Specifically, it integrates the step-wise beam search method into LLM CoT and designs a deductive verifier to verify intermediate reasoning step.
Experiments results show that DBS improves the base performance of LLMs on various task and can detect diverse and subtle reasoning errors and robustness on different model scales, proving its superiority over previous methods.
strength_weakness: strength_weakness: 1. Paper does not provide a detailed analysis of how different beam search hyperparameters impact this trade-off and the final performance.
2. The computational efficiency of DBS compared to baselines is not discussed in depth. Given the additional overhead of beam search and verification, an analysis of the inference time would be informative.
3. The paper focuses on the deductive reasoning paradigm, but many real-world reasoning tasks also involve inductive and abductive reasoning. Discussing DBS's potential limitations or extensions to these other forms of reasoning could broaden its impact.
4. There are significant differences among various types of reasoning tasks. DBS is more effective in Arithmetic Reasoning task. The paper lacks analysis and discussion in this regard.
questions: questions: The idea in DBS is straightforward, and the results show that it is a promising approach. I have some questions regarding the DBS method and experiments:

1. The paper only using two relatively weak LLMs to evaluates DBS on eight datasets. Considering the submission time, the state-of-the-art accuracy should have already surpassed the results reported in the paper, which may undermine the persuasiveness of the work.
2. DBS categorizes the errors in the reasoning process into several types, but these do not cover all the errors encountered in real-world scenarios (which is also mentioned in the paper). If the reasoning process is deductive reasoning, DBS aligns with expectations. However, many real-world reasoning tasks also involve inductive and abductive reasoning. Can you discussing DBS's potential limitations or extensions on these other forms of reasoning?
3. What is the model's strategy for handling scenario where multiple errors coexist simultaneously in one intermediate process ?
paper_summary: paper_summary: This paper proposes Deductive Beam Search (DBS), which integrates chain-of-thought (CoT) and deductive reasoning with step-wise beam search for LLMs. To train such verifier, the authors propose labor-free data construction methods by replacing numbers in the equations with randomly generated ones and randomly selecting reasoning steps. The experiments show the effectiveness of the proposed method and the paper is quite easy to understand.
strength_weakness: strength_weakness: * Lack of further analysis of different reasoning steps
paper_summary: paper_summary: This paper propose a new prompting method to improve the reasoning capability of llms. Specifically, instead of using greedy search, this paper proposed to conduce beam search based on the step level with the help of an additional NLI model to provide the beam ranking signal. Experiments on several datasets show that this method can achieve marginal improvement over the majority voting baseline.
strength_weakness: strength_weakness: 1. Combining advanced search algorithms into the reasoning process of large language models is a hot research topic in the community. There are several existing works that applies beam search, tree search, or MCTS into the reasoning process. This paper is missing the comparison of these baselines. I could think of a key difference between this work and other baselines is that the proposed deductive verifier is task-independent while other methods either use signal from the model itself (e.g., PPL) or a task-specific scorer. This is an important feature. However, from the results in table 2, it seems like the proposed verifier is not good enough since the improvement over majority voting is quite marginal. I would suggest the authors to pay more attention to the general verifier and further improve it.
2. Some of the claims in the paper are over-claims. For example, Many existing works are indeed working on addressing the middle errors hence the first claim in the abstract might not be accurate. Also, from the view of a higher level, all the search algorithms (including self-consistency, beam search, ordinary tree search, MCTS) are all trying to alleviate the error caused by the greedy decoding. The key difference is the signal used to conduct the sampling. Hence, one should directly compare these methods instead of adding them together. For the extreme case, one should be able to combine all of these methods together but that is not helpful in a real system since it is too heavy.
questions: questions: 1. What is the generalization capability of the proposed verifier. Can you test on a more general benchmark such as big-bench hard?
2. Can you elaborate more on the implementation of the self-consistency baseline including all the important hyper-parameters?

Comments: comment: Thanks for your prompt reply. We are glad that we have addressed your other major concerns about **performance on self-consistency** and **missing comparisons**. We now would like to clarify the other two arguments.

> Inference Time

Thanks for bringing the inference time up. Actually, “combining DBS with SC adds no time” is the response to your concern about “Methods should directly compare rather than add”. DBS can cache all finished reasoning paths during inference. Thus, users can directly apply self-consistency on the DBS-generated reasoning paths, which makes DBS+SC add no time compared to DBS alone. \
As for your concern on DBS increasing inference time, we admit that applying DBS indeed increases inference time and may be challenging to be deployed as a delay-sensitive system in the near future. Yet, being able to be used directly in the real-world systems is *one of the many forms of metric* to evaluate the scientific contributions. We would like to highlight again that although accurate reasoning is more time-consuming, it catalyzes stronger models [1,2,3,4]. The cited works all use *“time-consuming”* sampling methods, which synthesize accurate reasoning paths, and finally breeds more powerful models. Moreover, as we have discussed in the response to Reviewer 2vf7, we compare the DBS inference time with self-consistency, where the additional time cost is primarily introduced by the small verifier, and verifier inference time is 0.1x of LLM inference time. Ultimately, in terms of future impacts, we believe that accuracy is a critical factor for stronger models. \
Thanks again for pointing out the limitation from the immediate use perspective, we will add more discussions in terms of inference speed in the future revision.

> Big Bench Hard

Thanks for the suggestion. We respectfully suggest that BBH may not be indispensable for work focusing on reasoning ability. As you pointed out, “reasoning capability is one of their focuses.” Given the multitude of abilities involved, including natural language understanding, it can be challenging to evaluate **reasoning ability**. Moreover, in recent works focusing on improving reasoning ability [5,6,7,8,9,10], BBH is not necessarily evaluated to demonstrate the effectiveness of reasoning. We are happy to discuss more if you could possible consider elaborating more.

Thanks again for your valuable suggestions and for being willing to discuss, let us know if you have any other questions.

[1] Kexun Zhang, et al. Algo: Synthesizing algorithmic programs with generated oracle verifiers, NeurIPS 2024.

[2] Trieu H. Trinh, et al. Solving olympiad geometry without human demonstrations, Nature, 2024.

[3] Jiaxin Huang, et al. Large Language Models Can Self-Improve. EMNLP 2023

[4] Zelikman Eric, et al. Star: Bootstrapping reasoning with reasoning. NeurIPS 2022

[5] Ning Miao, et al. SelfCheck: Using LLMs to Zero-Shot Check Their Own Step-by-Step Reasoning. ICLR 2024

[6] Terufumi Morishita, et al. Learning Deductive Reasoning from Synthetic Corpus Based on Formal Logic, PMLR 2023

[7] Yuxi Xie, et al. Self-evaluation guided beam search for reasoning, NeurIPS 2024.

[8] Zhan Ling, et al. Deductive verification of chain-of-thought reasoning, NeurIPS 2024.

[9] Shibo Hao, et al. Reasoning with language model is planning with world model, EMNLP 2023.

[10] Xidong Feng, et al. Alphazero-like tree-search can guide large language model decoding and training, 2023
Thanks for the reply. However, I still tend to keep my original rating because the two main arguments do not convince me.

First, "combining DBS with SC adds no time." This comment is not accurate. Increasing the beam size will significantly improve the KV caching and computing power of GPUs. Especially, in DBS, the definition of each step is not very clear to the model. A streaming inference engine cannot know which token to split and merge. Also, the communication between the LM and the verifier model will also significantly increase the delay.

Second, BBH is designed to evaluate how well models can solve complex tasks and reasoning capability is one of their focuses. BBH is also a popular dataset used in many recent LLM evaluation packages.