mlsanityData to 7 Oct 2026

Learning a SAT Solver from Single-Bit Supervision

arXiv 1802.03685 ↗First posted 11 Feb 2018cs.AI cs.LG cs.LOcited by 198

Not on the map. Why?

Abstract (arXiv)

We present NeuroSAT, a message passing neural network that learns to solve SAT problems after only being trained as a classifier to predict satisfiability. Although it is not competitive with state-of-the-art SAT solvers, NeuroSAT can solve problems that are substantially larger and more difficult than it ever saw during training by simply running for more iterations. Moreover, NeuroSAT generalizes to novel distributions; after training only on random SAT problems, at test time it can solve SAT problems encoding graph coloring, clique detection, dominating set, and vertex cover problems, all on a range of distributions over small random graphs.

Key facts. Cited by 198 papers in the map (data through 7 Oct 2026). First posted on arXiv 11 Feb 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 35; 2022: 40; 2023: 34; 2024: 28; 2025: 30; 2026: 31.

198 papers.

Sort:

By area:

  1. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 700
  2. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  3. 2021A Survey on Deep Semi-supervised Learningcited by 250
  4. 2022Formal Mathematics Statement Curriculum Learningcited by 141
  5. 2021Proof Artifact Co-training for Theorem Proving with Language Modelscited by 130
  6. 2025MLGym: A New Framework and Benchmark for Advancing AI Research Agentscited by 111
  7. 2021Can You Learn an Algorithm? Generalizing from Easy to Hard Problems with Recurrent Networkscited by 108
  8. 2022On the Paradox of Learning to Reason from Datacited by 93
  9. 2021Graph-based Semi-supervised Learning: A Comprehensive Reviewcited by 79
  10. 2021LTL2Action: Generalizing LTL Instructions for Multi-Task RLcited by 72
  11. 2021Machine Learning for Electronic Design Automation: A Surveycited by 71
  12. 2023A Comprehensive Survey on Applications of Transformers for Deep Learning Taskscited by 70
38 more
  1. 2023Towards Omni-generalizable Neural Methods for Vehicle Routing Problemscited by 68
  2. 2023Harnessing the Power of Large Language Models for Natural Language to First-Order Logic Translationcited by 59
  3. 2022MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solverscited by 48
  4. 2021LIME: Learning Inductive Bias for Primitives of Mathematical Reasoningcited by 46
  5. 2021Learning a Large Neighborhood Search Algorithm for Mixed Integer Programscited by 41
  6. 2023Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNetscited by 40
  7. 2023Transformers Meet Directed Graphscited by 39
  8. 2023Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusioncited by 39
  9. 2021TacticZero: Learning to Prove Theorems from Scratch with Deep Reinforcement Learningcited by 37
  10. 2021DeepGate: Learning Neural Representations of Logic Gatescited by 37
  11. 2023Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learningcited by 37
  12. 2021Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustnesscited by 35
  13. 2023Towards LogiGLUE: A Brief Survey and A Benchmark for Analyzing Logical Reasoning Capabilities of Language Modelscited by 35
  14. 2025Solving Formal Math Problems by Decomposition and Iterative Reflectioncited by 35
  15. 2022Explaining the Explainers in Graph Neural Networks: a Comparative Studycited by 34
  16. 2023Equivariant Deep Weight Space Alignmentcited by 34
  17. 2022End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinkingcited by 33
  18. 2022Formal Specifications from Natural Languagecited by 33
  19. 2022Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent setcited by 33
  20. 2022Path Independent Equilibrium Models Can Better Exploit Test-Time Computationcited by 33
  21. 2022Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxationcited by 32
  22. 2023Neural Algorithmic Reasoning with Causal Regularisationcited by 30
  23. 2021Goal-Aware Neural SAT Solvercited by 27
  24. 2022One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfactioncited by 27
  25. 2021Link Scheduling using Graph Neural Networkscited by 26
  26. 2021Techniques for Symbol Grounding with SATNetcited by 24
  27. 2022Augment with Care: Contrastive Learning for Combinatorial Problemscited by 22
  28. 2022Machine Learning Methods in Solving the Boolean Satisfiability Problemcited by 22
  29. 2021NeuroBack: Improving CDCL SAT Solving using Graph Neural Networkscited by 19
  30. 2023Unsupervised Learning for Combinatorial Optimization Needs Meta-Learningcited by 19
  31. 2021Pushing the Limits of Rule Reasoning in Transformers through Natural Language Satisfiabilitycited by 18
  32. 2022NSNet: A General Neural Probabilistic Framework for Satisfiability Problemscited by 18
  33. 2021Neural Circuit Synthesis from Specification Patternscited by 17
  34. 2022Annealed Training for Combinatorial Optimization on Graphscited by 17
  35. 2023G4SATBench: Benchmarking and Advancing SAT Solving with Graph Neural Networkscited by 17
  36. 2023Controlling Continuous Relaxation for Combinatorial Optimizationcited by 16
  37. 2024LinSATNet: The Positive Linear Satisfiability Neural Networkscited by 16
  38. 2024Can Transformers Reason Logically? A Study in SAT Solvingcited by 16

50 most cited of 198 All 198 (JSON)