mlsanityData to 7 Oct 2026

SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver

arXiv 1905.12149 ↗First posted 29 May 2019cs.LG cs.AI stat.MLcited by 173

Not on the map. Why?

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

Abstract (arXiv)

Integrating logical reasoning within deep learning architectures has been a major goal of modern AI systems. In this paper, we propose a new direction toward this goal by introducing a differentiable (smoothed) maximum satisfiability (MAXSAT) solver that can be integrated into the loop of larger deep learning systems. Our (approximate) solver is based upon a fast coordinate descent approach to solving the semidefinite program (SDP) associated with the MAXSAT problem. We show how to analytically differentiate through the solution to this SDP and efficiently solve the associated backward pass. We demonstrate that by integrating this solver into end-to-end learning systems, we can learn the logical structure of challenging problems in a minimally supervised fashion. In particular, we show that we can learn the parity function using single-bit supervision (a traditionally hard task for deep networks) and learn how to play 9x9 Sudoku solely from examples. We also solve a "visual Sudok" problem that maps images of Sudoku puzzles to their associated logical solutions by combining our MAXSAT solver with a traditional convolutional architecture. Our approach thus shows promise in integrating logical structures within deep learning.

Key facts. Cited by 173 papers in the map (data through 7 Oct 2026). First posted on arXiv 29 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 27; 2022: 31; 2023: 33; 2024: 26; 2025: 25; 2026: 31.

173 papers.

Sort:

By area:

  1. 2021Implicit Behavioral Cloningcited by 442
  2. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  3. 2021DC3: A learning method for optimization with hard constraintscited by 181
  4. 2021End-to-End Constrained Optimization Learning: A Surveycited by 154
  5. 2023Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunitiescited by 129
  6. 2021Implicit MLE: Backpropagating Through Discrete Exponential Family Distributionscited by 97
  7. 2022On the Paradox of Learning to Reason from Datacited by 93
  8. 2021On Training Implicit Modelscited by 73
  9. 2023Dirichlet Diffusion Score Model for Biological Sequence Generationcited by 73
  10. 2023Scallop: A Language for Neurosymbolic Programmingcited by 63
  11. 2021Neuro-Symbolic Artificial Intelligence: Current Trendscited by 54
  12. 2021CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraintscited by 49
38 more
  1. 2022Deep Equilibrium Approaches to Diffusion Modelscited by 42
  2. 2022Sub-Task Decomposition Enables Learning in Sequence to Sequence Taskscited by 41
  3. 2022Deep Learning Methods for Abstract Visual Reasoning: A Survey on Raven's Progressive Matricescited by 37
  4. 2024Artificial Kuramoto Oscillatory Neuronscited by 37
  5. 2024Learning Iterative Reasoning through Energy Diffusioncited by 36
  6. 2021From Machine Learning to Robotics: Challenges and Opportunities for Embodied Intelligencecited by 35
  7. 2022NeuPSL: Neural Probabilistic Soft Logiccited by 34
  8. 2022Towards Data-and Knowledge-Driven Artificial Intelligence: A Survey on Neuro-Symbolic Computingcited by 34
  9. 2021Enforcing Policy Feasibility Constraints through Differentiable Projection for Energy Optimizationcited by 31
  10. 2022Backpropagation through Combinatorial Algorithms: Identity with Projection Workscited by 29
  11. 2021Implicit Normalizing Flowscited by 28
  12. 2021Constraint-based graph network simulatorcited by 27
  13. 2022Beyond backpropagation: bilevel optimization through implicit differentiation and equilibrium propagationcited by 26
  14. 2023Recurrence without Recurrence: Stable Video Landmark Detection with Deep Equilibrium Modelscited by 26
  15. 2021Techniques for Symbol Grounding with SATNetcited by 24
  16. 2022Alternating Differentiation for Optimization Layerscited by 22
  17. 2023LION: Implicit Vision Prompt Tuningcited by 22
  18. 2022SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problemscited by 21
  19. 2023Learning to Solve Constraint Satisfaction Problems with Recurrent Transformercited by 21
  20. 2023A Pseudo-Semantic Loss for Autoregressive Models with Logical Constraintscited by 21
  21. 2022Deep Symbolic Learning: Discovering Symbols and Rules from Perceptionscited by 20
  22. 2021A global convergence theory for deep ReLU implicit networks via over-parameterizationcited by 17
  23. 2023Landscape Surrogate: Learning Decision Losses for Mathematical Optimization Under Partial Informationcited by 17
  24. 2024Softened Symbol Grounding for Neuro-symbolic Systemscited by 16
  25. 2024Imperative Learning: A Self-supervised Neuro-Symbolic Learning Framework for Robot Autonomycited by 16
  26. 2024LinSATNet: The Positive Linear Satisfiability Neural Networkscited by 16
  27. 2021Joint inference and input optimization in equilibrium networkscited by 15
  28. 2022The Curse of Unrolling: Rate of Differentiating Through Optimizationcited by 15
  29. 2022Neural Set Function Extensions: Learning with Discrete Functions in High Dimensionscited by 14
  30. 2023On Learning Latent Models with Multi-Instance Weak Supervisioncited by 13
  31. 2025Shortcuts and Identifiability in Concept-based Models from a Neuro-Symbolic Lenscited by 13
  32. 2026ToolGate: Contract-Grounded and Verified Tool Execution for LLMscited by 13
  33. 2022Certifiable 3D Object Pose Estimation: Foundations, Learning Models, and Self-Trainingcited by 12
  34. 2022Adaptive Perturbation-Based Gradient Estimation for Discrete Latent Variable Modelscited by 12
  35. 2023Semantic Strengthening of Neuro-Symbolic Learningcited by 12
  36. 2023Injecting Logical Constraints into Neural Networks via Straight-Through Estimatorscited by 12
  37. 2024Neuro-symbolic Learning Yielding Logical Constraintscited by 12
  38. 2021Neuro-algorithmic Policies enable Fast Combinatorial Generalizationcited by 11

50 most cited of 173 All 173 (JSON)