Learning a SAT Solver from Single-Bit Supervision
By Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, David L. Dill. 2018
517 citations recorded by the source corpus.
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.
Subfields: Computer Networks and Communications, Information Systems, Management Science and Operations Research, Reinforcement Learning, Program Analysis & Verification
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computer Networks and Communications
- Andrea Lodi
- Raquel Urtasun
- Yoshua Bengio
- Kevin P. Murphy
- Pushmeet Kohli
- Peter Clark
- William L. Hamilton
- Jure Leskovec
In Information Systems
- Hannaneh Hajishirzi
- Jonathan Berant
- Jure Leskovec
- Mohit Bansal
- Percy Liang
- Peter Clark
- Matt Gardner
- William L. Hamilton
In Management Science and Operations Research
- Yoshua Bengio
- Sergey Levine
- Roger Baker Grosse
- Richard S. Zemel
- Mohit Bansal
- Timothy P. Lillicrap
- Quoc V. Le
- Vladlen Koltun
In Reinforcement Learning
- Sergey Levine
- Pieter Abbeel
- Chelsea Finn
- Yuxi Li
- Nicolas Manfred Otto Heess
- Timothy P. Lillicrap
- Shimon Whiteson
- Razvan Pascanu
In Program Analysis & Verification
- Markus Norman Rabe
- Yuhuai Wu
- Christian Szegedy
- William L. Hamilton
- Stanislas Polu
- Wenda Li
- Oyvind Tafjord
- Peter Clark
Citations in the corpus
- Transformers as Soft Reasoners over Language (2020, methodology): “Similarly, there has been work on SAT solving [Selsam et al., 2019], approximate (DNF) model counting [Abboud et al.”
- Analysing Mathematical Reasoning Abilities of Neural Models (2019, background): “…Allamanis et al. (2016) and Evans et al. (2018) use tree networks to predict polynomial or logical equivalence or logical entailment; Selsam et al. (2018) uses message passing networks with a bipartite graph structure to decide satisfiability in formulas in conjunctive normal form,…”
- Generative Language Modeling for Automated Theorem Proving (2020, methodology): “DeepMath [26] explored the use of CNNs and RNNs to predict whether a premise is useful to demonstrate a given conjecture, their results were later improved with FormulaNet [27] by the use of graph neural networks, reminiscent of NeuroSAT [28].”
- Evaluating Models’ Local Decision Boundaries via Contrast Sets (2020, background): “Selsam et al. (2019), Tafjord et al. (2019), Lin et al. (2019), and Khashabi et al. (2020) designed their data collection process to include contrastive examples.”
- Relational inductive biases, deep learning, and graph networks (2018, methodology): “On boolean SAT problems, Selsam et al. (2018) demonstrated generalization both to different problem sizes and across problem distributions: their model retained good performance upon strongly modifying the distribution of the input graphs and its typical local structure.”
- Position-aware Graph Neural Networks (2019, methodology): “, 2019) and developed heuristics to fix the issue: augmenting node features with one-hot encodings (Kipf & Welling, 2017), or making GNNs deeper (Selsam et al., 2019).”
- ProofWriter: Generating Implications, Proofs, and Abductive Statements over Natural Language (2020, methodology): “, 2019; Rocktäschel and Riedel, 2017), or SAT solving (Selsam et al., 2019), these transformers emulate reasoning over language directly, bypassing a formal representation.”
- Formal Mathematics Statement Curriculum Learning (2022, background): “…and lem-mas but very few exercises), we hypothesized that if the difficulty of this set of statements was made varied enough, expert iteration could potentially leverage it to effectively shift our models’ distribution closer to miniF2F ’s, and in turn, improve their eventual performance on it.”
- PRover: Proof Generation for Interpretable Reasoning over Rules (2020, methodology): “, 2016), executing basic compositional programs (Reed and de Freitas, 2016), SAT solving (Selsam et al., 2019), formula embedding (Abdelaziz et al.”
- Teaching Temporal Logics to Neural Networks (2020, methodology): “In contrast to previous work (Selsam et al., 2019), which is restricted to formulas in CNF, we allow an arbitrary formula structure and derived operators.”
- LIME: Learning Inductive Bias for Primitives of Mathematical Reasoning (2021, background): “GNNs also scale to larger formulas in SAT (Selsam et al., 2019; Selsam & Bjørner, 2019; Han, 2020), QBF (Lederman et al.”
- Learning to Reason: Leveraging Neural Networks for Approximate DNF Counting (2019, background): “This is expected, since SAT and TSP are NP-complete and are hard to approximate with strong guarantees.”
- Exact Combinatorial Optimization with Graph Convolutional Neural Networks (2019, background): “[47], who proposed a recurrent GCNN model, NeuroSAT, which can be interpreted as an approximate SAT solver when trained to predict satisfiability.”
- Learning to Solve NP-Complete Problems - A Graph Neural Network for the Decision TSP (2018, methodology): “Interestingly, this behavior is opposite to that of the GNN SAT-solver NeuroSAT (Selsam et al. 2018), which guesses UNSAT by default and changes its prediction only upon Figure 2: The larger the deviation from the optimal cost, the faster the model learns: we were able to obtain > 95% accuracy for 1”
- LTL2Action: Generalizing LTL Instructions for Multi-Task RL (2021, background): “This aligns with other works showing scalability of GNNs to larger formulas (Selsam et al., 2018; Vaezipoor et al., 2020).”
- Neural Guided Constraint Logic Programming for Program Synthesis (2018, background): “The use of graph or tree structure to represent programs [21, 22] and constraints [23] is not unprecedented.”
- Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon (2018, methodology): “For a very general example, Selsam et al. (2018) represent a satis-fiability problem using a bipartite graph on variables and clauses.”