# Certified Deductive Reasoning with Language Models

arXiv: https://arxiv.org/abs/2306.04031 · HTML: https://mlsanity.com/paper/2306.04031/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 28 of its 37 references that are in the map.
- First posted on arXiv 6 Jun 2023.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

## Builds on (most cited first, 28 of 28)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them](https://mlsanity.com/paper/2210.09261/) (2022)
- [STaR: Bootstrapping Reasoning With Reasoning](https://mlsanity.com/paper/2203.14465/) (2022)
- [MM-REACT: Prompting ChatGPT for Multimodal Reasoning and Action](https://mlsanity.com/paper/2303.11381/) (2023)
- [LM-Nav: Robotic Navigation with Large Pre-Trained Models of Language, Vision, and Action](https://mlsanity.com/paper/2207.04429/) (2022)
- [Language Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thought](https://mlsanity.com/paper/2210.01240/) (2022)
- [A Simple Language Model for Task-Oriented Dialogue](https://mlsanity.com/paper/2005.00796/) (2020)
- [ProofWriter: Generating Implications, Proofs, and Abductive Statements over Natural Language](https://mlsanity.com/paper/2012.13048/) (2020)
- [Towards AI-Complete Question Answering: A Set of Prerequisite Toy Tasks](https://mlsanity.com/paper/1502.05698/) (2015)
- [Autoformalization with Large Language Models](https://mlsanity.com/paper/2205.12615/) (2022)
- [ReClor: A Reading Comprehension Dataset Requiring Logical Reasoning](https://mlsanity.com/paper/2002.04326/) (2020)
- [Language models show human-like content effects on reasoning tasks](https://mlsanity.com/paper/2207.07051/) (2022)
- [End-to-End Differentiable Proving](https://mlsanity.com/paper/1705.11040/) (2017)
- [Synchromesh: Reliable code generation from pre-trained language models](https://mlsanity.com/paper/2201.11227/) (2022)
- [NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics](https://mlsanity.com/paper/2112.08726/) (2021)
- [NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints](https://mlsanity.com/paper/2010.12884/) (2020)
- [On the Paradox of Learning to Reason from Data](https://mlsanity.com/paper/2205.11502/) (2022)
- [LAMBADA: Backward Chaining for Automated Reasoning in Natural Language](https://mlsanity.com/paper/2212.13894/) (2022)
- [Learning Reasoning Strategies in End-to-End Differentiable Proving](https://mlsanity.com/paper/2007.06477/) (2020)
- [DAGN: Discourse-Aware Graph Network for Logical Reasoning](https://mlsanity.com/paper/2103.14349/) (2021)
- [Peano: Learning Formal Mathematical Reasoning](https://mlsanity.com/paper/2211.15864/) (2022)
- [Explicit Planning Helps Language Models in Logical Reasoning](https://mlsanity.com/paper/2303.15714/) (2023)

## Built on by (most cited first, 8 of 8)

- [LeanReasoner: Boosting Complex Logical Reasoning with Lean](https://mlsanity.com/paper/2403.13312/) (2024)
- [Conditions for Length Generalization in Learning Reasoning Skills](https://mlsanity.com/paper/2311.16173/) (2023)
- [Automated Theorem Provers Help Improve Large Language Model Reasoning](https://mlsanity.com/paper/2408.03492/) (2024)
- [Self-Imagine: Effective Unimodal Reasoning with Multimodal Models using Self-Imagination](https://mlsanity.com/paper/2401.08025/) (2024)
- [Let's Be Self-generated via Step by Step: A Curriculum Learning Approach to Automated Reasoning with Large Language Models](https://mlsanity.com/paper/2410.21728/) (2024)
- [Reasoning over Uncertain Text by Generative Large Language Models](https://mlsanity.com/paper/2402.09614/) (2024)
- [Categorical Syllogisms Revisited: A Review of the Logical Reasoning Abilities of LLMs for Analyzing Categorical Syllogism](https://mlsanity.com/paper/2406.18762/) (2024)
- [Steamroller Problems: An Evaluation of LLM Reasoning Capability with Automated Theorem Prover Strategies](https://mlsanity.com/paper/2407.20244/) (2024)

## Abstract (arXiv)

Language models often achieve higher accuracy when reasoning step-by-step in complex tasks. However, even when arriving at a correct final answer, their rationales are often logically unsound or inconsistent. This is a major issue when reliable reasoning traces are needed, such when fine-tuning on model-generated reasoning for self-improvement. To tackle these issues, we introduce a class of tools for language models called guides, that use state and incremental constraints to guide generation. A guide can be invoked by the model to constrain its own generation to a set of valid statements given by the tool. In turn, the model's choices can change the guide's state. We show how a general system for logical reasoning can be used as a guide, which we call textscLogicGuide. Given a reasoning problem in natural language, a model can formalize its assumptions for textscLogicGuide and guarantee that its step-by-step reasoning is sound. In experiments on PrOntoQA, ProofWriter and Syllogism Validity datasets, textscLogicGuide significantly improves the performance of GPT-3, GPT-3.5 Turbo and LLaMA (accuracy gains up to 35%), while drastically reducing content effects -- the interference between unwanted prior assumptions and reasoning, which humans and language models suffer from. We then explore bootstrapping GPT-3.5 Turbo and LLaMA using their own reasoning traces. We find that LogicGuide is critical: by training only on certified self-generated reasoning, models can self-improve, avoiding learning from their own hallucinations. Moreover, bootstrapped models enjoy significant boosts on ReClor, a challenging real-world reasoning dataset, even when not relying on formalization at inference time.