mlsanityData to 7 Oct 2026

SatLM: Satisfiability-Aided Language Models Using Declarative Prompting

arXiv 2305.09656 ↗First posted 16 May 2023cs.CL cs.AIcited by 100

On the map: LLM reasoning → Reasoning benchmarks and evaluation

Abstract (arXiv)

Prior work has combined chain-of-thought prompting in large language models (LLMs) with programmatic representations to perform effective and transparent reasoning. While such an approach works well for tasks that only require forward reasoning (e.g., straightforward arithmetic), it is less effective for constraint solving problems that require more sophisticated planning and search. In this paper, we propose a new satisfiability-aided language modeling (SatLM) approach for improving the reasoning capabilities of LLMs. We use an LLM to generate a declarative task specification rather than an imperative program and leverage an off-the-shelf automated theorem prover to derive the final answer. This approach has two key advantages. The declarative specification is closer to the problem description than the reasoning steps are, so the LLM can parse it out of the description more accurately. Furthermore, by offloading the actual reasoning task to an automated theorem prover, our approach can guarantee the correctness of the answer with respect to the parsed specification and avoid planning errors in the solving process. We evaluate SATLM on 8 different datasets and show that it consistently outperforms program-aided LMs in the imperative paradigm. In particular, SATLM outperforms program-aided LMs by 23% on a challenging subset of the GSM arithmetic reasoning dataset; SATLM also achieves a new SoTA on LSAT and BoardgameQA, surpassing previous models that are trained on the respective training sets.

Key facts. Cited by 100 papers in the map (data through 7 Oct 2026). Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning. Builds on 50 of its 71 references that are in the map. First posted on arXiv 16 May 2023.

Builds on

50 of 71 references.

Closest ancestors · 8

Same direction, newest first

  1. 2023Improved Logical Reasoning of Language Models via Differentiable Symbolic Programming5 May
  2. 2023STREET: A Multi-Task Structured Reasoning and Explanation Benchmark13 Feb
  3. 2022PAL: Program-aided Language Models18 Nov
  4. 2022PINTO: Faithful Language Reasoning Using Prompt-Generated Rationales3 Nov
  5. 2022Explanations from Large Language Models Make Small Reasoners Better13 Oct
  6. 2022Language Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thought3 Oct
  7. 2022Selection-Inference: Exploiting Large Language Models for Interpretable Logical Reasoning19 May
  8. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Models30 Nov

Other references · 42

  1. 2020Language Models are Few-Shot Learnerscited by 32,199
  2. 2022Training language models to follow instructions with human feedbackcited by 15,712
  3. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  4. 2021Training Verifiers to Solve Math Word Problemscited by 9,743
  5. 2021Evaluating Large Language Models Trained on Codecited by 8,053
  6. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,601
  7. 2022PaLM: Scaling Language Modeling with Pathwayscited by 5,304
  8. 2022Large Language Models are Zero-Shot Reasonerscited by 4,323
  9. 2023Toolformer: Language Models Can Teach Themselves to Use Toolscited by 4,072
  10. 2021Finetuned Language Models Are Zero-Shot Learnerscited by 3,747
  11. 2022OPT: Open Pre-trained Transformer Language Modelscited by 3,464
  12. 2023Self-Refine: Iterative Refinement with Self-Feedbackcited by 3,317
30 more
  1. 2022Emergent Abilities of Large Language Modelscited by 2,483
  2. 2021Pre-train, Prompt, and Predict: A Systematic Survey of Prompting Methods in Natural Language Processingcited by 2,222
  3. 2022Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language modelscited by 1,970
  4. 2021Multitask Prompted Training Enables Zero-Shot Task Generalizationcited by 1,462
  5. 2022Least-to-Most Prompting Enables Complex Reasoning in Large Language Modelscited by 1,397
  6. 2021Scaling Language Models: Methods, Analysis & Insights from Training Gophercited by 1,199
  7. 2022Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Taskscited by 1,057
  8. 2023Teaching Large Language Models to Self-Debugcited by 963
  9. 2022Decomposed Prompting: A Modular Approach for Solving Complex Taskscited by 554
  10. 2023LLM+P: Empowering Large Language Models with Optimal Planning Proficiencycited by 496
  11. 2022Complexity-Based Prompting for Multi-Step Reasoningcited by 387
  12. 2020ProofWriter: Generating Implications, Proofs, and Abductive Statements over Natural Languagecited by 309
  13. 2022Generate rather than Retrieve: Large Language Models are Strong Context Generatorscited by 296
  14. 2023Faithful Chain-of-Thought Reasoningcited by 285
  15. 2020Neurosymbolic AI: The 3rd Wavecited by 253
  16. 2021The GEM Benchmark: Natural Language Generation, its Evaluation and Metricscited by 239
  17. 2023LEVER: Learning to Verify Language-to-Code Generation with Executioncited by 228
  18. 2022Demystifying Prompts in Language Models via Perplexity Estimationcited by 215
  19. 2023REFINER: Reasoning Feedback on Intermediate Representationscited by 203
  20. 2020The Next Decade in AI: Four Steps Towards Robust Artificial Intelligencecited by 194
  21. 2022Synchromesh: Reliable code generation from pre-trained language modelscited by 156
  22. 2019CLUTRR: A Diagnostic Benchmark for Inductive Reasoning from Textcited by 155
  23. 2023Solving Math Word Problems by Combining Language Models With Symbolic Solverscited by 124
  24. 2021A Recipe For Arbitrary Text Style Transfer with Large Language Modelscited by 107
  25. 2021Jigsaw: Large Language Models meet Program Synthesiscited by 103
  26. 2020Optimal Neural Program Synthesis from Multimodal Specificationscited by 15
  27. 2021Multi-modal Program Inference: a Marriage of Pre-trainedLanguage Models and Component-based Synthesiscited by 12
  28. 2023Explanation Selection Using Unlabeled Data for Chain-of-Thought Promptingcited by 12
  29. 2020Benchmarking Multimodal Regex Synthesis with Complex Structurescited by 10
  30. 2019Just Add Functions: A Neural-Symbolic Language Modelcited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 9; 2024: 24; 2025: 30; 2026: 37.

100 papers.

Sort:

By area:

  1. 2023Large Language Models for Software Engineering: A Systematic Literature Reviewcited by 389
  2. 2023Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoningcited by 379
  3. 2024To CoT or not to CoT? Chain-of-thought helps mainly on math and symbolic reasoningcited by 257
  4. 2023Navigate through Enigmatic Labyrinth A Survey of Chain of Thought Reasoning: Advances, Frontiers and Futurecited by 184
  5. 2023LINC: A Neurosymbolic Approach for Logical Reasoning by Combining Language Models with First-Order Logic Proverscited by 161
  6. 2024Formal Mathematical Reasoning: A New Frontier in AIcited by 80
  7. 2023Harnessing the Power of Large Language Models for Natural Language to First-Order Logic Translationcited by 59
  8. 2023Grammar Prompting for Domain-Specific Language Generation with Large Language Modelscited by 58
  9. 2024A Survey on Deep Learning for Theorem Provingcited by 55
  10. 2025Empowering LLMs with Logical Reasoning: A Comprehensive Surveycited by 51
  11. 2025RepoAudit: An Autonomous LLM-Agent for Repository-Level Code Auditingcited by 47
  12. 2024Planning Anything with Rigor: General-Purpose Zero-Shot Planning with LLM-based Formalized Programmingcited by 35
38 more
  1. 2024LeanReasoner: Boosting Complex Logical Reasoning with Leancited by 28
  2. 2024Divide and Translate: Compositional First-Order Logic Translation and Verification for Complex Logical Reasoningcited by 27
  3. 2023Language Models can be Logical Solverscited by 24
  4. 2025LogicAD: Explainable Anomaly Detection via VLM-based Text Feature Extractioncited by 24
  5. 2024Logic-of-Thought: Injecting Logic into Contexts for Full Reasoning in Large Language Modelscited by 23
  6. 2024Testing and Understanding Erroneous Planning in LLM Agents through Synthesized User Inputscited by 22
  7. 2024Trust the PRoC3S: Solving Long-Horizon Robotics Problems with LLMs and Constraint Satisfactioncited by 19
  8. 2024CodeUpdateArena: Benchmarking Knowledge Editing on API Updatescited by 18
  9. 2025Improving Chain-of-Thought Reasoning via Quasi-Symbolic Abstractionscited by 17
  10. 2024LOGIC-LM++: Multi-Step Refinement for Symbolic Formulationscited by 14
  11. 2024LogicPro: Improving Complex Logical Reasoning via Program-Guided Learningcited by 14
  12. 2025Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transitioncited by 13
  13. 2025LLM-Guided Probabilistic Program Induction for POMDP Model Estimationcited by 11
  14. 2024Strategies for Improving NL-to-FOL Translation with LLMs: Data Generation, Incremental Fine-Tuning, and Verificationcited by 10
  15. 2025VeriCoT: Neuro-symbolic Chain-of-Thought Validation via Logical Consistency Checkscited by 10
  16. 2024QUITE: Quantifying Uncertainty in Natural Language Text in Bayesian Reasoning Scenarioscited by 9
  17. 2024MCP-Solver: Integrating Language Models with Constraint Programming Systemscited by 9
  18. 2025Logic.py: Bridging the Gap between LLMs and Constraint Solverscited by 9
  19. 2025Grammars of Formal Uncertainty: When to Trust LLMs in Automated Reasoning Taskscited by 9
  20. 2025ProtoReasoning: Prototypes as the Foundation for Generalizable Reasoning in LLMscited by 9
  21. 2025A Neurosymbolic Approach to Natural Language Formalization and Verificationcited by 8
  22. 2023POE: Process of Elimination for Multiple Choice Reasoningcited by 7
  23. 2024DiLA: Enhancing LLM Tool Learning with Differential Logic Layercited by 6
  24. 2026Faithful Autoformalization via Roundtrip Verification and Repaircited by 6
  25. 2023Interpreting User Requests in the Context of Natural Language Standing Instructionscited by 5
  26. 2024MM-PoE: Multiple Choice Reasoning via. Process of Elimination using Multi-Modal Modelscited by 5
  27. 2025Step-Wise Formal Verification for LLM-Based Mathematical Problem Solvingcited by 5
  28. 2024Can Language Models Pretend Solvers? Logic Code Simulation with LLMscited by 4
  29. 2024Solving Zebra Puzzles Using Constraint-Guided Multi-Agent Systemscited by 4
  30. 2024ASSERTIFY: Utilizing Large Language Models to Generate Assertions for Production Codecited by 4
  31. 2025Assessing the Sensitivity and Alignment of FOL Closeness Metricscited by 4
  32. 2025Non-Interactive Symbolic-Aided Chain-of-Thought for Logical Reasoningcited by 4
  33. 2025Simulation to Rules: A Dual-VLM Framework for Formal Visual Planningcited by 4
  34. 2025Personalizing Agent Privacy Decisions via Logical Entailmentcited by 4
  35. 2025What can large language models do for sustainable food?cited by 3
  36. 2025The Road to Generalizable Neuro-Symbolic Learning Should be Paved with Foundation Modelscited by 3
  37. 2025Abductive Logical Rule Induction by Bridging Inductive Logic Programming and Multimodal Large Language Modelscited by 3
  38. 2024Eliciting Problem Specifications via Large Language Modelscited by 2

50 most cited of 100 All 100 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2025SATBench: Benchmarking LLMs' Logical Reasoning via Automated Puzzle Generation from SAT Formulas
  2. 2025SATQuest: A Verifier for Logical Reasoning Evaluation and Reinforcement Fine-Tuning of LLMs
  3. 2025Natural Language Satisfiability: Exploring the Problem Distribution and Evaluating Transformer-based Language Models
  4. 2024Can Large Language Models Reason? A Characterization via 3-SAT
  5. 2025Saturation-Driven Dataset Generation for LLM Mathematical Reasoning in the TPTP Ecosystem
  6. 2026Satisfiability Solving with LLMs: A Matched-Pair Evaluation of Reasoning Capability
  7. 2025Beyond Correctness: Exposing LLM-generated Logical Flaws in Reasoning via Multi-step Automated Theorem Proving
  8. 2025FINEREASON: Evaluating and Improving LLMs' Deliberate Reasoning through Reflective Puzzle Solving