Source-linked AI summary
Deductive Verification of Chain-of-Thought Reasoning
Zhan Ling, Yunhao Fang, Xuanlin Li, Zhiao Huang, Mingu Lee, Roland Memisevic, Hao Su
TL;DR
Chain-of-Thought reasoning can contain hallucinations and accumulated errors, while verifying an entire reasoning chain is difficult. The paper introduces Natural Program and stepwise verification using only necessary premises, reporting improved reasoning rigor and trustworthiness, with contextual ambiguity remaining a limitation.
Problem
Chain-of-Thought reasoning may introduce hallucinations and accumulated errors, and the validity of an entire deductive reasoning process is difficult to verify.
Method
The paper introduces Natural Program and decomposes reasoning verification into step-by-step subprocesses focused on necessary context and premises, with Unanimity-Plurality Voting.
Results
The framework improves the rigor, trustworthiness, and interpretability of generated reasoning steps and answers, while enabling reliable step-by-step self-verification.
Takeaways & Limitations
The approach supports explicit, rigorous deductive reasoning and can output “unknown” when repeated sampling does not yield a rigorous process.
Takeaways & Limitations
The verification process cannot detect some contextual misinterpretations, such as whether “pennies” means coins or a currency unit.
Abstract
from arXiv · showhide
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. Code will be released at https://github.com/lz1oceani/verify_cot.
1 Introduction
The paper addresses hallucinations and accumulated errors in Chain-of-Thought reasoning by introducing Natural Program and decomposed, step-by-step verification. Experiments report improved rigor, trustworthiness, interpretability, and answer quality.
- Chain-of-Thought prompting can introduce hallucinations and accumulated errors through its intermediate reasoning steps.
- The approach extracts individual reasoning steps and minimal premise sets to support step-by-step deductive verification.The process is intended to identify reasoning and grounding errors, where grounding uses information absent from cited premises.
- The method prioritizes cogent reasoning processes and can output “unknown” when repeated sampling fails to produce a rigorous process.This is intended to prevent hallucinations that mislead users.
- Experiments across arithmetic and common-sense datasets demonstrate improved rigor, trustworthiness, interpretability, and answer correctness.The evaluation includes publicly available models such as OpenAI’s GPT-3.5-turbo.
- Natural Program is a natural-language deductive reasoning format designed for rigorous reasoning and verification, generated through in-context learning.It retains natural language while structuring reasoning sequences like computer programs.
- The framework decomposes long-chain verification into subprocesses that use only necessary context and premises.This design addresses erroneous verification caused by irrelevant premises and facilitates local step verification.
2 Related work
Related work covers Chain-of-Thought reasoning, language models used as verifiers, and methods for verifying individual reasoning steps. The paper distinguishes its in-context Natural Program verification from these approaches.
- Chain-of-Thought prompting improves large language models’ performance across diverse reasoning tasks by encouraging step-by-step reasoning.
- Language models have been used to verify solutions and intermediate steps, compare model generations, and support self-verification, self-refinement, and self-debugging.
- A GSM8K example shows GPT-3.5-turbo producing a wrong reasoning chain despite reaching the correct answer.
- Existing work includes methods for verifying individual steps in a reasoning process.
- Natural Program verification uses in-context learning without language-model fine-tuning and provides explicit explanations for invalid reasoning steps.
- The verification process can handle implicit premises such as common knowledge when assessing whether a reasoning step is valid.For example, it can mark “November has 29 days” as invalid despite recognizing the relevant common knowledge.
3 Motivation and Problem Formulation
The paper distinguishes final-answer correctness from deductive validity, emphasizing that intermediate reasoning steps can contain errors even when answers are correct. Because verifying an entire reasoning chain is difficult for LLMs, the paper formulates validity at the individual-step level.
- A generated solution is traditionally considered correct when its final answer matches the ground-truth answer.
- Intermediate reasoning mistakes can occur in every tested LLM, including ChatGPT and GPT-4, even when the final answer is correct.
- The paper therefore emphasizes validating every reasoning step rather than only checking the final answer.
- Whole-chain verification is challenging for ChatGPT when the deductive dependencies among reasoning steps are entangled.
- A reasoning step is deductively valid when its conclusion follows logically from its corresponding premises.
- Chain validity is defined as the conjunction of individual step validities, but evaluating it is substantially harder than exact-match answer evaluation.
4 Deductively Verifiable Chain-of-Thought Reasoning
The paper decomposes reasoning verification into local step checks and introduces Natural Program, a natural-language format that explicitly records the premises used by each step. This structure supports more effective self-verification and consensus-based answer selection.
- 4.1 Decomposition of Deductive Verification Process: The verification process is decomposed into step-level checks that use only premises necessary for each reasoning step.
- 4.2 Natural Program Deductive Reasoning Format: Natural Program explicitly lists the minimal premises required for each step, enabling local deductive verification.
- 4.2 Natural Program Deductive Reasoning Format: The format includes question-related premises, a numbered reasoning chain, and premise references grounding each generated step.
- 4.2 Natural Program Deductive Reasoning Format: Each reasoning step is verified using the full descriptions of its referenced premises, the step itself, and a validity-verification instruction.
- 4.2 Natural Program Deductive Reasoning Format: Natural Program is presented as enabling explicit, rigorous reasoning and more effective self-verification by language models.
- 4.3 Unanimity-Plurality Voting: Unanimity-Plurality Voting first filters sampled chains by step validity, then selects the final answer by majority vote among verified chains.
5 Experiments
Experiments evaluate deductive verification and answer correctness across arithmetic, symbol-manipulation, and date-understanding tasks. Natural Program verification improves reasoning validation across most datasets, while filtering invalid reasoning can slightly reduce final-answer accuracy.
- 5.1 Experimental Setup: The evaluation covers arithmetic reasoning, symbol manipulation, and date understanding benchmarks.
- 5.1 Experimental Setup: Each verification benchmark contributes 100 reasoning chains, split evenly between deductively valid and mistaken chains judged by human annotators.
- 5.2 Comparison of Deductive Verification Accuracy: The study compares whole-chain verification with Natural Program verification using step-by-step decomposition and necessary premise subsets.
- 5.2 Comparison of Deductive Verification Accuracy: Natural Program verification achieves higher reasoning-verification accuracy across most datasets, identifying erroneous chains while maintaining a low false-positive rate for valid chains.
- 5.2 Comparison of Deductive Verification Accuracy: The approach is less effective on Last Letters, where each step depends on all previous steps.
- 5.3 Impact of Natural Program and Deductive Verification on Final Answer Correctness: Natural Program prompting attains on-par or better final-answer accuracy than baselines across many reasoning tasks before deductive filtering.
- 5.3 Impact of Natural Program and Deductive Verification on Final Answer Correctness: Filtering invalid chains slightly decreases final-answer accuracy because some correct-answer candidates contain incorrect reasoning.
- 5.3 Impact of Natural Program and Deductive Verification on Final Answer Correctness: Increasing the number of validity votes generally improves reasoning-validation accuracy but increases computational cost.
6 Limitations
The approach improves reasoning-step trustworthiness but remains vulnerable to contextual ambiguities, such as competing interpretations of “pennies.”
- Table 8 illustrates a failure where ChatGPT interprets “pennies” as currency units although the ground truth treats them as coins.
- The method cannot detect misinterpretations caused by ambiguous wording when the model consistently follows the wrong interpretation.In the reported case, “pennies” may mean coins or currency units, and verification fails to identify the resulting incorrect trace.
- Contextual ambiguity is identified as a current limitation because such ambiguities occur commonly in real-world scenarios.
7 Conclusion
The paper proposes Natural Program-based deductive verification to make LLM reasoning more rigorous, trustworthy, and interpretable. It reports improved reasoning verification, while cautioning that harmful or incorrect outputs are not eliminated.
- Natural Program decomposes complex reasoning verification into subprocesses using only necessary context and premises, with Unanimity-Plurality Voting further improving verification accuracy.
- Experiments report improvements in the rigor, trustworthiness, and interpretability of reasoning steps and answers.
- The approach can mitigate but does not completely eliminate hallucinations, reasoning errors, harmful content, bias, incorrect claims, or wrongful advice.
A Deductive Verification with Vicuna Models
Experiments with Vicuna-7B and Vicuna-13B test one-shot deductive verification with and without fine-tuning on a generated verification dataset. Fine-tuning improves cross-dataset accuracy, but GPT-3.5 remains stronger.
- The experiments evaluate Vicuna-7B and Vicuna-13B with or without fine-tuning using randomly sampled valid and incorrect reasoning examples.
- The verification dataset contains 2,000 reasoning steps evenly divided between correct and incorrect categories.
- Fine-tuning Vicuna models on a 2,000-step deductive verification dataset improves verification accuracy on GSM8K and multiple other datasets.
- Fine-tuned Vicuna models remain less accurate than non-finetuned GPT-3.5, indicating that model capacity affects deductive verification capability.
B More Discussion on Improvements of Deductive Verification Accuracy Versus Improvements on Final Answer Correctness
Deductive verification substantially improves the reliability of reasoning chains but barely changes final-answer accuracy under majority voting. Filtering can remove flawed chains that reach correct answers, reducing correct-answer votes.
- Verification accuracy for reasoning chains improves significantly, whereas final-answer accuracy improves only marginally.
- 91.6% of GSM8K problems have a correct-versus-largest-wrong vote margin above 2, making final answers unlikely to change after verification.
- 46.2% of reasoning chains reaching correct answers are filtered out, and 76.3% of those filtered chains exhibit incorrect reasoning.
- Among correct-answer chains retained by verification, 78.0% have correct reasoning.
- 40.6% of chains with incorrect answers and incorrect reasoning are filtered out.
- Removing many correct-answer chains reduces correct-answer votes under majority voting and limits final-answer accuracy.
C More Details on Answer Extraction
The answer-extraction pipeline processes the final three non-empty response lines, first checking for no-answer patterns, then splitting answer blocks, and finally applying regular expressions.
- The pipeline begins by selecting the last three non-empty lines from the model response.
- No-answer regular expressions map detected refusal or uncertainty phrases to the final answer “No answer!”.If no such pattern appears, extraction proceeds to answer-splitting and regular-expression matching.
- Answer-split patterns divide the text into blocks, and the final block is used for answer extraction.
- Regular expressions scan the remaining text for possible answers, selecting the first match or defaulting to “No answer!” when none is found.
D Prompts
The appendix provides prompts for direct chain verification, Natural Program generation across problem types, and step-by-step verification of individual reasoning steps.
- D.1 Prompt for Direct Reasoning Chain Verification Without Natural Program Format: Direct verification prompts ask models to assess an entire reasoning chain, using zero-shot and two-shot examples.The two-shot prompt includes one correct and one incorrect reasoning chain.
- D.2 Prompts for Reasoning Chain Generation in the Natural Program Format: Natural Program generation uses distinct prompts for math word problems, multiple-choice math, date problems, and Last Letters problems.These prompts cover GSM8K, MATH, AddSub, AQuA, Date, and Last Letters datasets.
- D.2 Prompts for Reasoning Chain Generation in the Natural Program Format: Math word-problem prompts cover GSM8K, MATH, and AddSub datasets.
- D.2 Prompts for Reasoning Chain Generation in the Natural Program Format: A multiple-choice math prompt addresses the AQuA dataset.
- D.2 Prompts for Reasoning Chain Generation in the Natural Program Format: Date and Last Letters prompts target their corresponding specialized reasoning datasets.
- D.3 Prompt for Deductive Verification Following Natural Program Format and Step-by-Step Decomposition: A general one-shot prompt verifies the deductive validity of a single reasoning step after Natural Program decomposition.The prompt instructs models to generate validity judgments for individual steps.
E More Deductive Verification Examples
The examples show that step-by-step deductive verification can identify grounding and logic errors, while also exhibiting failures in detecting ungrounded or misclassified numbers.
- The Natural Program examples apply deductive verification to individual reasoning steps.
- In the successful case, the verifier identifies ungrounded information and logical errors in the supplied reasoning.
- The approach sometimes fails to detect ungrounded premise numbers or incorrectly labels grounded numbers as ungrounded.The documented failures involve the number 240 being treated as derivable and 120 being treated as ungrounded.
- The example reasoning contains ungrounded numbers such as 3 and 6, causing the grounding check to fail.
- The reasoning check fails because it multiplies apples by discounted price while also introducing an unnecessary fruit-count calculation.
- Grounding, reasoning, and calculation checks all fail, so the overall verification marks the answer as “no”.