mlsanityData to 7 Oct 2026

Machine Learning Methods in Solving the Boolean Satisfiability Problem

arXiv 2203.04755 ↗First posted 2 Mar 2022cs.AI cs.LG cs.LOcited by 22

Not on the map. Why?

Abstract (arXiv)

This paper reviews the recent literature on solving the Boolean satisfiability problem (SAT), an archetypal NP-complete problem, with the help of machine learning techniques. Despite the great success of modern SAT solvers to solve large industrial instances, the design of handcrafted heuristics is time-consuming and empirical. Under the circumstances, the flexible and expressive machine learning methods provide a proper alternative to solve this long-standing problem. We examine the evolving ML-SAT solvers from naive classifiers with handcrafted features to the emerging end-to-end SAT solvers such as NeuroSAT, as well as recent progress on combinations of existing CDCL and local search solvers with machine learning methods. Overall, solving SAT with machine learning is a promising yet challenging research topic. We conclude the limitations of current works and suggest possible future directions.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). Builds on 22 of its 114 references that are in the map. First posted on arXiv 2 Mar 2022.

Builds on

22 of 114 references.

References · 22

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Inductive Representation Learning on Large Graphscited by 6,284
  4. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
  5. 2015Pointer Networkscited by 882
  6. 2018Link Prediction Based on Graph Neural Networkscited by 829
  7. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  8. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  9. 2015A Critical Review of Recurrent Neural Networks for Sequence Learningcited by 223
  10. 2018Learning a SAT Solver from Single-Bit Supervisioncited by 198
  11. 2018Deep Models of Interactions Across Setscited by 68
  12. 2019Guiding High-Performance SAT Solvers with Unsat-Core Predictionscited by 61
10 more
  1. 2021On Joint Learning for Solving Placement and Routing in Chip Designcited by 44
  2. 2021Goal-Aware Neural SAT Solvercited by 27
  3. 2020NLocalSAT: Boosting Local Search with Solution Predictioncited by 25
  4. 2019G2SAT: Learning to Generate SAT Formulascited by 20
  5. 2020Symbolic Logic meets Machine Learning: A Brief Survey in Infinite Domainscited by 16
  6. 2020Enhancing SAT solvers with glue variable predictionscited by 11
  7. 2017Graph Neural Networks and Boolean Satisfiabilitycited by 8
  8. 2019The Resolution of Keller's Conjecturecited by 8
  9. 2020Neural heuristics for SAT solvingcited by 7
  10. 2017Improve SAT-solving with Machine Learningcited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 7; 2024: 6; 2025: 5; 2026: 2.

22 papers.

Sort:

  1. 2022NSNet: A General Neural Probabilistic Framework for Satisfiability Problemscited by 18
  2. 2023G4SATBench: Benchmarking and Advancing SAT Solving with Graph Neural Networkscited by 17
  3. 2024LinSATNet: The Positive Linear Satisfiability Neural Networkscited by 16
  4. 2022SATformer: Transformer-Based UNSAT Core Learningcited by 14
  5. 2023HardSATGEN: Understanding the Difficulty of Hard SAT Formula Generation and A Strong Structure-Hardness-Aware Baselinecited by 12
  6. 2024Machine Learning Insides OptVerse AI Solver: Design Principles and Applicationscited by 7
  7. 2024Circuit Transformer: A Transformer That Preserves Logical Equivalencecited by 5
  8. 2024GraSS: Combining Graph Neural Networks with Expert Knowledge for SAT Solver Selectioncited by 5
  9. 2023W2SAT: Learning to generate SAT instances from Weighted Literal Incidence Graphscited by 3
  10. 2024Graph Pruning for Enumeration of Minimal Unsatisfiable Subsetscited by 2
  11. 2024Application of AI to formal methods - an analysis of current trendscited by 2
  12. 2025Structure based SAT dataset for analysing GNN generalisationcited by 1
10 more
  1. 2025HyperSAT: Unsupervised Hypergraph Neural Networks for Weighted MaxSAT Problemscited by 1
  2. 2025MILP-SAT-GNN: Yet Another Neural SAT Solvercited by 1
  3. 2025TurboSAT: Gradient-Guided Boolean Satisfiability Accelerated on GPU-CPU Hybrid Systemcited by 1
  4. 2025BDD2Seq: Enabling Scalable Reversible-Circuit Synthesis via Graph-to-Sequence Learningcited by 1
  5. 2026On the Expressive Power of GNNs for Boolean Satisfiabilitycited by 1
  6. 2023Learning Interpretable Heuristics for WalkSATcited by 0
  7. 2023Automatic Algorithm Selection for Pseudo-Boolean Optimization with Given Computational Time Limitscited by 0
  8. 2023Using deep learning to construct stochastic local search SAT solvers with performance boundscited by 0
  9. 2023A Novel Differentiable Loss Function for Unsupervised Graph Neural Networks in Graph Partitioningcited by 0
  10. 2026Hypergraph Neural Networks Accelerate MUS Enumerationcited by 0