# Natural Language Deduction through Search over Statement Compositions

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 38 references that are in the map.
- First posted on arXiv 16 Jan 2022.

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

- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [A Broad-Coverage Challenge Corpus for Sentence Understanding through Inference](https://mlsanity.com/paper/1704.05426/) (2017)
- [DeBERTa: Decoding-enhanced BERT with Disentangled Attention](https://mlsanity.com/paper/2006.03654/) (2020)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Did Aristotle Use a Laptop? A Question Answering Benchmark with Implicit Reasoning Strategies](https://mlsanity.com/paper/2101.02235/) (2021)
- [Towards Faithfully Interpretable NLP Systems: How should we define and evaluate faithfulness?](https://mlsanity.com/paper/2004.03685/) (2020)
- [Does the Whole Exceed its Parts? The Effect of AI Explanations on Complementary Team Performance](https://mlsanity.com/paper/2006.14779/) (2020)
- [ProofWriter: Generating Implications, Proofs, and Abductive Statements over Natural Language](https://mlsanity.com/paper/2012.13048/) (2020)
- [Evaluating Explainable AI: Which Algorithmic Explanations Help Users Predict Model Behavior?](https://mlsanity.com/paper/2005.01831/) (2020)
- [What Can We Learn from Collective Human Opinions on Natural Language Inference Data?](https://mlsanity.com/paper/2010.03532/) (2020)
- [Explaining Answers with Entailment Trees](https://mlsanity.com/paper/2104.08661/) (2021)
- [Multi-hop Reading Comprehension through Question Decomposition and Rescoring](https://mlsanity.com/paper/1906.02916/) (2019)
- [PRover: Proof Generation for Interpretable Reasoning over Rules](https://mlsanity.com/paper/2010.02830/) (2020)
- [Multi-hop Question Answering via Reasoning Chains](https://mlsanity.com/paper/1910.02610/) (2019)
- [Answering while Summarizing: Multi-task Learning for Multi-hop QA with Evidence Extraction](https://mlsanity.com/paper/1905.08511/) (2019)
- [NLProlog: Reasoning with Weak Unification for Question Answering in Natural Language](https://mlsanity.com/paper/1906.06187/) (2019)
- [Uncertain Natural Language Inference](https://mlsanity.com/paper/1909.03042/) (2019)
- [Conversational Neuro-Symbolic Commonsense Reasoning](https://mlsanity.com/paper/2006.10022/) (2020)
- [Flexible Generation of Natural Language Deductions](https://mlsanity.com/paper/2104.08825/) (2021)
- [Learning with Different Amounts of Annotation: From Zero to Many Labels](https://mlsanity.com/paper/2109.04408/) (2021)
- [NeuralLog: Natural Language Inference with Joint Neural and Logical Reasoning](https://mlsanity.com/paper/2105.14167/) (2021)
- [MonaLog: a Lightweight System for Natural Language Inference Based on Monotonicity](https://mlsanity.com/paper/1910.08772/) (2019)
- [multiPRover: Generating Multiple Proofs for Improved Interpretability in Rule Reasoning](https://mlsanity.com/paper/2106.01354/) (2021)
- [DeepA2: A Modular Framework for Deep Argument Analysis with Pretrained Neural Text2Text Language Models](https://mlsanity.com/paper/2110.01509/) (2021)

## Built on by (most cited first, 30 of 35)

- [Language Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thought](https://mlsanity.com/paper/2210.01240/) (2022)
- [Selection-Inference: Exploiting Large Language Models for Interpretable Logical Reasoning](https://mlsanity.com/paper/2205.09712/) (2022)
- [Faithful Reasoning Using Large Language Models](https://mlsanity.com/paper/2208.14271/) (2022)
- [Deductive Verification of Chain-of-Thought Reasoning](https://mlsanity.com/paper/2306.03872/) (2023)
- [Plug-and-Play VQA: Zero-shot VQA by Conjoining Large Pretrained Models with Zero Training](https://mlsanity.com/paper/2210.08773/) (2022)
- [NaturalProver: Grounded Mathematical Proof Generation with Language Models](https://mlsanity.com/paper/2205.12910/) (2022)
- [A Survey on Deep Learning for Theorem Proving](https://mlsanity.com/paper/2404.09939/) (2024)
- [Generating Natural Language Proofs with Verifier-Guided Search](https://mlsanity.com/paper/2205.12443/) (2022)
- [Vera: A General-Purpose Plausibility Estimation Model for Commonsense Statements](https://mlsanity.com/paper/2305.03695/) (2023)
- [Rainier: Reinforced Knowledge Introspector for Commonsense Question Answering](https://mlsanity.com/paper/2210.03078/) (2022)
- [Entailer: Answering Questions with Faithful and Truthful Chains of Reasoning](https://mlsanity.com/paper/2210.12217/) (2022)
- [Verification and Refinement of Natural Language Explanations through LLM-Symbolic Theorem Proving](https://mlsanity.com/paper/2405.01379/) (2024)
- [Can Retriever-Augmented Language Models Reason? The Blame Game Between the Retriever and the Language Model](https://mlsanity.com/paper/2212.09146/) (2022)
- [Logical Reasoning over Natural Language as Knowledge Representation: A Survey](https://mlsanity.com/paper/2303.12023/) (2023)
- [Deductive Closure Training of Language Models for Coherence, Accuracy, and Updatability](https://mlsanity.com/paper/2401.08574/) (2024)
- [Honest Students from Untrusted Teachers: Learning an Interpretable Question-Answering Pipeline from a Pretrained Language Model](https://mlsanity.com/paper/2210.02498/) (2022)
- [Learning Deductive Reasoning from Synthetic Corpus based on Formal Logic](https://mlsanity.com/paper/2308.07336/) (2023)
- [NELLIE: A Neuro-Symbolic Inference Engine for Grounded, Compositional, and Explainable Reasoning](https://mlsanity.com/paper/2209.07662/) (2022)
- [Faithful Question Answering with Monte-Carlo Planning](https://mlsanity.com/paper/2305.02556/) (2023)
- [Iterated Decomposition: Improving Science Q&A by Supervising Reasoning Processes](https://mlsanity.com/paper/2301.01751/) (2023)
- [Summarization Programs: Interpretable Abstractive Summarization with Neural Modular Trees](https://mlsanity.com/paper/2209.10492/) (2022)
- [Natural Language Deduction with Incomplete Information](https://mlsanity.com/paper/2211.00614/) (2022)
- [Explicit Planning Helps Language Models in Logical Reasoning](https://mlsanity.com/paper/2303.15714/) (2023)
- [Enhancing Systematic Decompositional Natural Language Inference Using Informal Logic](https://mlsanity.com/paper/2402.14798/) (2024)
- [SportsMetrics: Blending Text and Numerical Data to Understand Information Fusion in LLMs](https://mlsanity.com/paper/2402.10979/) (2024)
- [RLET: A Reinforcement Learning Based Approach for Explainable QA with Entailment Trees](https://mlsanity.com/paper/2210.17095/) (2022)
- [MURMUR: Modular Multi-Step Reasoning for Semi-Structured Data-to-Text Generation](https://mlsanity.com/paper/2212.08607/) (2022)
- [Breakpoint Transformers for Modeling and Tracking Intermediate Beliefs](https://mlsanity.com/paper/2211.07950/) (2022)
- [Best-k Search Algorithm for Neural Text Generation](https://mlsanity.com/paper/2211.11924/) (2022)
- [Unleashing the Creative Mind: Language Model As Hierarchical Policy For Improved Exploration on Challenging Problem Solving](https://mlsanity.com/paper/2311.00694/) (2023)

## Abstract (arXiv)

In settings from fact-checking to question answering, we frequently want to know whether a collection of evidence (premises) entails a hypothesis. Existing methods primarily focus on the end-to-end discriminative version of this task, but less work has treated the generative version in which a model searches over the space of statements entailed by the premises to constructively derive the hypothesis. We propose a system for doing this kind of deductive reasoning in natural language by decomposing the task into separate steps coordinated by a search procedure, producing a tree of intermediate conclusions that faithfully reflects the system's reasoning process. Our experiments on the EntailmentBank dataset (Dalvi et al., 2021) demonstrate that the proposed system can successfully prove true statements while rejecting false ones. Moreover, it produces natural language explanations with a 17% absolute higher step validity than those produced by an end-to-end T5 model.