Deductive Verification of Chain-of-Thought Reasoning

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.

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. Another 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. [1] Creswell, Antonia, Murray Shanahan, and Irina Higgins. "Selection-inference: Exploiting large language models for interpretable logical reasoning." arXiv preprint arXiv:2205.09712 (2022). [2] Creswell, Antonia, and Murray Shanahan. "Faithful reasoning using large language models." arXiv preprint arXiv:2208.14271 (2022).

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'? - Table 3, Natural Program appears to be particularly good on the AQuA dataset. Could there be some case analysis here? - 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?

Rating

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

Confidence

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

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

I believe the authors have addressed the limitations well.

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.

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 of '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. 2. 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.

Questions

See weaknesses, especially point 1. If it's my misunderstanding, I will increase my score.

Rating

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

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

The authors have discussed limitations in Sec. 6, which I think is adequate.

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.

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. The 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. The 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. In 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. The 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. [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.

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). - 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. - Footnote in Page 7: world problems -> word problems - What do the authors think are the most significant differences between Natural Programs and the NLProofS approach? - 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? - 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. - 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. - 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) - 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?

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

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

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Yes, the limitations are clearly discussed in the paper.

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.

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. * 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). * 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. * 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? * 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.

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. * 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?

Rating

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

Confidence

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

Soundness

3 good

Presentation

3 good

Contribution

3 good

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.

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).

Strengths

- A natural language formalism that allows us for more accurate reasoning verification - The approach is well-motivated by showing the inability of ChatGPT to identify errors given the entire reasoning chain. - Shows gains compared to self-consistency with two different CoT formats

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.

Questions

- Isn't "unanimity-plurity" just self-consistency with a deductive validation filter? Not sure if it needs another name. - 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. - I would have preferred that all the tables included accuracy numbers on the datasets (instead of just verification accuracy). - 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. - Since FaithfulCoT also provides a similar dependency structure, could deductive verification be applied with their approach too (as a baseline)? - 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.

Rating

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

Confidence

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

Soundness

3 good

Presentation

3 good

Contribution

3 good

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.

Response to Authors

Thanks for addressing my concerns and clarifying my doubts. Given the ablations, I'm convinced that the prompt designs in the paper are meaningfully contributing to the performance. While this idea of "simplifying the step-by-step verification process by only keeping necessary premises and contexts for each reasoning step", i.e., selecting relevant information and then using for reasoning, is explored in prior works [1,2], I believe this is a slightly new area where the authors show the benefit of such approach. Overall, I'm inclined to accept the paper. [1] Selection-Inference: Exploiting Large Language Models for Interpretable Logical Reasoning, Creswell et al., 2022 [2] FaiRR: Faithful and Robust Deductive Reasoning over Natural Language, Sanyal, et al., 2022

Thanks

Thanks a lot for the clarification!

Thanks

Thank you for the response. Given the additional emphasis on "encouraging the validity of each reasoning step", this work is better compared with other techniques that evaluate the validity of reasoning e.g. ROSCOE[1], RecEval [2]. These methods also don't rely on any special structure and use models to identify reasoning errors. They could also be used with UPV to improve accuracy. > very challenging to extract the actual premises of a single reasoning step because of intertwining reasoning-step dependencies. I agree and hence my suggestion to view every CoT statement depends on all previous statements. I understand that Table 2 evaluates the validation accuracy but I would also like to see its impact on QA accuracy (assuming you still use UPV) [1] ROSCOE: A Suite of Metrics for Scoring Step-by-Step Reasoning (released last year) [2] ReCEval: Evaluating Reasoning Chains via Correctness and Informativeness (its fair to not compare against this work as it is too new)