mlsanityData to 7 Oct 2026

Generating Natural Language Proofs with Verifier-Guided Search

arXiv 2205.12443 ↗First posted 25 May 2022cs.CL cs.LG cs.LOcited by 52

Not on the map. Why?

Cited by 29 in LLM reasoning, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

Reasoning over natural language is a challenging problem in NLP. In this work, we focus on proof generation: Given a hypothesis and a set of supporting facts, the model generates a proof tree indicating how to derive the hypothesis from supporting facts. Compared to generating the entire proof in one shot, stepwise generation can better exploit the compositionality and generalize to longer proofs but has achieved limited success on real-world data. Existing stepwise methods struggle to generate proof steps that are both logically valid and relevant to the hypothesis. Instead, they tend to hallucinate invalid steps given the hypothesis. In this paper, we present a novel stepwise method, NLProofS (Natural Language Proof Search), which learns to generate relevant steps conditioning on the hypothesis. At the core of our approach, we train an independent verifier to check the validity of the proof steps to prevent hallucination. Instead of generating steps greedily, we search for proofs maximizing a global proof score judged by the verifier. NLProofS achieves state-of-the-art performance on EntailmentBank and RuleTaker. Specifically, it improves the correctness of predicted proofs from 27.7% to 33.3% in the distractor setting of EntailmentBank, demonstrating the effectiveness of NLProofS in generating challenging human-authored proofs.

Key facts. Cited by 52 papers in the map (data through 7 Oct 2026). Builds on 45 of its 70 references that are in the map. First posted on arXiv 25 May 2022.

Builds on

45 of 70 references.

References · 45

  1. 2020Language Models are Few-Shot Learnerscited by 32,199
  2. 2019Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformercited by 14,491
  3. 2019RoBERTa: A Robustly Optimized BERT Pretraining Approachcited by 13,266
  4. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  5. 2021Training Verifiers to Solve Math Word Problemscited by 9,743
  6. 2021Evaluating Large Language Models Trained on Codecited by 8,053
  7. 2022Large Language Models are Zero-Shot Reasonerscited by 4,323
  8. 2018HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answeringcited by 3,686
  9. 2015A large annotated corpus for learning natural language inferencecited by 1,837
  10. 2020Leveraging Passage Retrieval with Generative Models for Open Domain Question Answeringcited by 1,203
  11. 2021Scaling Language Models: Methods, Analysis & Insights from Training Gophercited by 1,199
  12. 2020BLEURT: Learning Robust Metrics for Text Generationcited by 1,196
33 more
  1. 2020Generative Language Modeling for Automated Theorem Provingcited by 379
  2. 2020ProofWriter: Generating Implications, Proofs, and Abductive Statements over Natural Languagecited by 309
  3. 2016Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Modelscited by 299
  4. 2020Transformers as Soft Reasoners over Languagecited by 265
  5. 2020HoVer: A Dataset for Many-Hop Fact Extraction And Claim Verificationcited by 199
  6. 2019CLUTRR: A Diagnostic Benchmark for Inductive Reasoning from Textcited by 155
  7. 2021Explaining Answers with Entailment Treescited by 148
  8. 2019Multi-hop Reading Comprehension through Question Decomposition and Rescoringcited by 119
  9. 2020A Benchmark for Systematic Generalization in Grounded Language Understandingcited by 108
  10. 2019Learning to Prove Theorems via Interacting with Proof Assistantscited by 107
  11. 2020PRover: Proof Generation for Interpretable Reasoning over Rulescited by 53
  12. 2021ProoFVer: Natural Logic Theorem Proving for Fact Verificationcited by 52
  13. 2020Measuring Systematic Generalization in Neural Proof Generation with Transformerscited by 43
  14. 2015A formal proof of the Kepler conjecturecited by 42
  15. 2019NLProlog: Reasoning with Weak Unification for Question Answering in Natural Languagecited by 36
  16. 2022Natural Language Deduction through Search over Statement Compositionscited by 35
  17. 2022FaiRR: Faithful and Robust Deductive Reasoning over Natural Languagecited by 29
  18. 2021Flexible Generation of Natural Language Deductionscited by 28
  19. 2022Entailment Tree Explanations via Iterative Retrieval-Generation Reasonercited by 26
  20. 2021Multi-Step Reasoning Over Unstructured Text with Beam Dense Retrievalcited by 25
  21. 2021NeuralLog: Natural Language Inference with Joint Neural and Logical Reasoningcited by 24
  22. 2019MonaLog: a Lightweight System for Natural Language Inference Based on Monotonicitycited by 20
  23. 2022METGEN: A Module-Based Entailment Tree Generation Framework for Answer Explanationcited by 17
  24. 2018Exploiting Explicit Paths for Multi-hop Reading Comprehensioncited by 16
  25. 2017Natural Language Inference from Multiple Premisescited by 12
  26. 2019Explore, Propose, and Assemble: An Interpretable Model for Multi-Hop Reading Comprehensioncited by 12
  27. 2020Braid: Weaving Symbolic and Neural Knowledge into Coherent Logical Explanationscited by 11
  28. 2021Learning Symbolic Rules for Reasoning in Quasi-Natural Languagecited by 9
  29. 2022Interpretable Proof Generation via Iterative Backward Reasoningcited by 9
  30. 2021Towards General Natural Language Understanding with Probabilistic Worldbuildingcited by 7
  31. 2021DeepA2: A Modular Framework for Deep Argument Analysis with Pretrained Neural Text2Text Language Modelscited by 7
  32. 2015Reasoning in Vector Space: An Exploratory Study of Question Answeringcited by 3
  33. 2021Probabilistic Graph Reasoning for Natural Proof Generationcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 7; 2023: 18; 2024: 13; 2025: 13; 2026: 1.

52 papers.

Sort:

By area:

  1. 2023Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoningcited by 379
  2. 2023Automatically Correcting Large Language Models: Surveying the landscape of diverse self-correction strategiescited by 236
  3. 2024When Can LLMs Actually Correct Their Own Mistakes? A Critical Survey of Self-Correction of LLMscited by 230
  4. 2023Deductive Verification of Chain-of-Thought Reasoningcited by 122
  5. 2024Formal Mathematical Reasoning: A New Frontier in AIcited by 80
  6. 2025Evaluating Step-by-step Reasoning Traces: A Surveycited by 62
  7. 2023Natural Language Reasoning, A Surveycited by 61
  8. 2024A Survey on Deep Learning for Theorem Provingcited by 55
  9. 2024Physics of Language Models: Part 2.2, How to Learn From Mistakes on Grade-School Math Problemscited by 49
  10. 2023Vera: A General-Purpose Plausibility Estimation Model for Commonsense Statementscited by 44
  11. 2024Reasoning in Token Economies: Budget-Aware Evaluation of LLM Reasoning Strategiescited by 44
  12. 2022Entailer: Answering Questions with Faithful and Truthful Chains of Reasoningcited by 38
38 more
  1. 2023Ever: Mitigating Hallucination in Large Language Models through Real-Time Verification and Rectificationcited by 38
  2. 2023GRACE: Discriminator-Guided Chain-of-Thought Reasoningcited by 35
  3. 2023Towards LogiGLUE: A Brief Survey and A Benchmark for Analyzing Logical Reasoning Capabilities of Language Modelscited by 35
  4. 2022Language Models as Inductive Reasonerscited by 32
  5. 2023Logical Reasoning over Natural Language as Knowledge Representation: A Surveycited by 32
  6. 2023Language Models can be Logical Solverscited by 24
  7. 2024HumanEvalComm: Benchmarking the Communication Competence of Code Generation for LLMs and LLM Agentcited by 24
  8. 2023Learning Deductive Reasoning from Synthetic Corpus based on Formal Logiccited by 18
  9. 2023RECKONING: Reasoning through Dynamic Knowledge Encodingcited by 17
  10. 2025Dissecting Logical Reasoning in LLMs: A Fine-Grained Evaluation and Supervision Studycited by 17
  11. 2022NELLIE: A Neuro-Symbolic Inference Engine for Grounded, Compositional, and Explainable Reasoningcited by 16
  12. 2023Faithful Question Answering with Monte-Carlo Planningcited by 16
  13. 2024Enhancing Ethical Explanations of Large Language Models through Iterative Symbolic Refinementcited by 16
  14. 2025Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transitioncited by 13
  15. 2022Natural Language Deduction with Incomplete Informationcited by 12
  16. 2024Enhancing Systematic Decompositional Natural Language Inference Using Informal Logiccited by 12
  17. 2025When Does Verification Pay Off? A Closer Look at LLMs as Solution Verifierscited by 11
  18. 2023Learning and Leveraging Verifiers to Improve Planning Capabilities of Pre-trained Language Modelscited by 10
  19. 2025LeanProgress: Guiding Search for Neural Theorem Proving via Proof Progress Predictioncited by 9
  20. 2022RLET: A Reinforcement Learning Based Approach for Explainable QA with Entailment Treescited by 7
  21. 2022MURMUR: Modular Multi-Step Reasoning for Semi-Structured Data-to-Text Generationcited by 7
  22. 2025Instantiation-based Formalization of Logical Reasoning Tasks using Language Models and Logical Solverscited by 7
  23. 2025Multilingual Text-to-SQL: Benchmarking the Limits of Language Models with Collaborative Language Agentscited by 7
  24. 2022Transformers Go for the LOLs: Generating (Humourous) Titles from Scientific Abstracts End-to-Endcited by 6
  25. 2025Helpful Agent Meets Deceptive Judge: Understanding Vulnerabilities in Agentic Workflowscited by 6
  26. 2024HoneyGPT: Breaking the Trilemma in Terminal Honeypots with Large Language Modelcited by 5
  27. 2025Efficient PRM Training Data Synthesis via Formal Verificationcited by 5
  28. 2025Mitigating Spurious Correlations in LLMs via Causality-Aware Post-Trainingcited by 5
  29. 2023Large Language Models Should Ask Clarifying Questions to Increase Confidence in Generated Codecited by 4
  30. 2023Unleashing the Creative Mind: Language Model As Hierarchical Policy For Improved Exploration on Challenging Problem Solvingcited by 4
  31. 2023Deductive Additivity for Planning of Natural Language Proofscited by 3
  32. 2024SEER: Facilitating Structured Reasoning and Explanation via Reinforcement Learningcited by 3
  33. 2024Semi-Instruct: Bridging Natural-Instruct and Self-Instruct for Code Large Language Modelscited by 3
  34. 2024A Logical Pattern Memory Pre-trained Model for Entailment Tree Generationcited by 3
  35. 2023Empirical Investigation of Neural Symbolic Reasoning Strategiescited by 1
  36. 2024From Models to Microtheories: Distilling a Model's Topical Knowledge for Grounded Question Answeringcited by 1
  37. 2025Can Large Language Models Unveil the Mysteries? An Exploration of Their Ability to Unlock Information in Complex Scenarioscited by 1
  38. 2025Deployability-Centric Infrastructure-as-Code Generation: Fail, Learn, Refine, and Succeed through LLM-Empowered DevOps Simulationcited by 1

50 most cited of 52 All 52 (JSON)