Satisfiability Solving with LLMs: A Matched-Pair Evaluation of Reasoning Capability
Open Access
- 30 June 2026
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Software Engineering
- Vol. 3 (FSE) , 4599-4621
Abstract
Large language models (LLMs) are increasingly used for tasks that implicitly reduce to Boolean satisfiability (SAT), yet their reasoning ability on SAT remains unclear. We present a systematic study of LLMs on 2-SAT and 3-SAT, together with two canonical reductions—Vertex Cover and a discrete 3D-packing formulation—designed to probe representation-invariant reasoning. Our evaluation begins with the conventional lens (accuracy/precision/recall/F1) and the phase-transition setting. We find that traditional metrics are frequently misleading. Models achieve high scores even though they tend to classify all formulas as satisfiable, fail to reproduce the classical easy--hard--easy signature around the 3-SAT threshold, and degrade sharply as the number of variables N grows. To address this, we introduce a paired-formula protocol (minimally different satisfiable/unsatisfiable instances) and a new measure, Accurate Differentiation Rate (ADR), which requires prediction on both members of each pair correct. ADR cleanly separates reasoning-oriented models from heuristic ones and correlates with witness validity (truth assignments that actually satisfy the formula). Extending beyond CNF, we test cross-representation consistency via standard reductions: (i) Convert CNF to Vertex Cover and (ii) Convert 3-SAT to discrete 3D packing with verifiable placement constraints. Decisions made on CNF and on their graph/packing counterparts agree for most models on >80 percent of instances, revealing stable decision rules across representations. A leading model (e.g., GPT-5) achieves both high invariance and correctness on small N, but still suffers scale-induced degradation. Taken together, our results support the thesis that SAT is a conservative probe for LLM reasoning: performance on SAT predicts transfer to other NP-style reductions, while paired evaluation with ADR provides a faithful, representation-robust assessment beyond conventional metrics.Keywords
All Related Versions
Funding Information
- National Science Foundation (1750886)
This publication has 24 references indexed in Scilit:
- Industrial applications of large language modelsScientific Reports, 2025
- Moving Fast with Software Verification2015
- A few billion lines of code laterCommunications of the ACM, 2010
- Introduction to Information Retrieval2008
- Scalable error detection using boolean satisfiability2005
- GRASP: a search algorithm for propositional satisfiabilityIEEE Transactions on Computers, 1999
- The undecidability of aliasingACM Transactions on Programming Languages and Systems, 1994
- Constant propagation with conditional branchesACM Transactions on Programming Languages and Systems, 1991
- Comparison of the predicted and observed secondary structure of T4 phage lysozymeBiochimica et Biophysica Acta (BBA) - Protein Structure, 1975
- On the complexity of time table and multi-commodity flow problems1975