Improving SAT Solver Heuristics with Graph Networks and Reinforcement Learning

Vitaly Kurin, Saad Godil, Shimon Whiteson, Bryan Catanzaro

Abstract

We present Graph-$Q$-SAT, a branching heuristic for a Boolean SAT solver trained with value-based reinforcement learning (RL) using Graph Neural Networks for function approximation. Solvers using Graph-$Q$-SAT are complete SAT solvers that either provide a satisfying assignment or proof of unsatisfiability, which is required for many SAT applications. The branching heuristics commonly used in SAT solvers make poor decisions during their warm-up period, whereas Graph-$Q$-SAT is trained to examine the structure of the particular problem instance to make better decisions early in the search. Training Graph-$Q$-SAT is data efficient and does not require elaborate dataset preparation or feature engineering. We train Graph-$Q$-SAT using RL interfacing with MiniSat solver and show that Graph-$Q$-SAT can reduce the number of iterations required to solve SAT problems by 2-3X. Furthermore, it generalizes to unsatisfiable SAT instances, as well as to problems with 5X more variables than it was trained on. We show that for larger problems, reductions in the number of iterations lead to wall clock time reductions, the ultimate goal when designing heuristics. We also show positive zero-shot transfer behavior when testing Graph-$Q$-SAT on a task family different from that used for training. While more work is needed to apply Graph-$Q$-SAT to reduce wall clock time in modern SAT solving settings, it is a compelling proof-of-concept showing that RL equipped with Graph Neural Networks can learn a generalizable branching heuristic for SAT search.

Introduction

Boolean Satisfiability (SAT) is a fundamental NP-complete problem with critical applications in hardware and software verification. Modern Conflict-Driven Clause Learning (CDCL) solvers rely heavily on branching heuristics, such as VSIDS, to navigate the search space. However, these heuristics often suffer from a "warm-up" period, making suboptimal decisions early in the search before enough conflicts have been observed.

We introduce Graph-Q-SAT, a branching heuristic that leverages Graph Neural Networks (GNNs) and Reinforcement Learning (RL) to perceive the structural properties of a SAT instance from the outset. By training an agent to minimize the number of search steps, we demonstrate that Graph-Q-SAT can significantly outperform traditional heuristics in terms of iteration count and, for larger problems, wall-clock time.

Methodology

Graph-Q-SAT integrates Deep Q-Learning (DQN) with a GNN architecture to learn a policy for variable branching.

Graph Representation

The SAT formula is represented as a bipartite graph where nodes represent variables and clauses. An edge exists between a variable node $x_i$ and a clause node $c_j$ if the variable appears in the clause. To distinguish between positive and negative literals, edges are labeled with a one-hot encoding (e.g., $[1, 0]$ for positive, $[0, 1]$ for negative), allowing the model to capture the exact polarity of variable occurrences.

Bipartite graph representation of a SAT formula with variable nodes (x), clause nodes (c), and literal polarity edge labels.

Architecture and Training

The model uses an "encode-process-decode" framework. The GNN performs message-passing iterations to propagate structural information across the graph, making the model naturally invariant to clause ordering or variable renaming. The RL agent is trained using DQN, where the state is the current partial assignment and the action is the choice of the next variable and its truth value. To encourage efficiency, the agent receives a small negative reward for each step and zero reward upon reaching a terminal state.

Experimental Results

We evaluated Graph-Q-SAT using Random 3-SAT instances from the SATLIB benchmark, training on small instances (50 variables) and testing for generalization on larger instances (up to 250 variables).

Iteration Reduction and Generalization

Graph-Q-SAT achieves a 2-3X reduction in the number of iterations required to solve SAT problems compared to the default MiniSat heuristic. Notably, the model generalizes well to instances five times larger than those seen during training. It also exhibits strong performance on unsatisfiable (unSAT) instances, despite being trained primarily on satisfiable ones. This suggests the model learns fundamental structural features conducive to pruning the search tree, regardless of whether a solution exists.

Iteration improvement relative to the default MiniSat heuristic across various problem sizes and training set sizes, showing strong generalization.

Transfer Learning and Wall-Clock Time

For larger problems (SAT-250), the reduction in iterations is significant enough to overcome the computational overhead of running a neural network, leading to actual wall-clock time speedups. Furthermore, the model demonstrates positive "zero-shot" transfer to different problem families, such as flat graph coloring, without any specific training on those tasks.

Conclusion

Graph-Q-SAT provides a compelling proof-of-concept for using RL and GNNs to improve SAT solver heuristics. By focusing on problem structure rather than historical conflict data, it overcomes the warm-up limitations of traditional heuristics. While the computational overhead of GNN inference currently limits wall-clock speedups to larger instances, future optimizations could make this approach viable for industrial-scale SAT solving.

Summary updated

Abstract

We present Graph-$Q$-SAT, a branching heuristic for a Boolean SAT solver trained with value-based reinforcement learning (RL) using Graph Neural Networks for function approximation. Solvers using Graph-$Q$-SAT are complete SAT solvers that either provide a satisfying assignment or proof of unsatisfiability, which is required for many SAT applications. The branching heuristics commonly used in SAT solvers make poor decisions during their warm-up period, whereas Graph-$Q$-SAT is trained to examine the structure of the particular problem instance to make better decisions early in the search. Training Graph-$Q$-SAT is data efficient and does not require elaborate dataset preparation or feature engineering. We train Graph-$Q$-SAT using RL interfacing with MiniSat solver and show that Graph-$Q$-SAT can reduce the number of iterations required to solve SAT problems by 2-3X. Furthermore, it generalizes to unsatisfiable SAT instances, as well as to problems with 5X more variables than it was trained on. We show that for larger problems, reductions in the number of iterations lead to wall clock time reductions, the ultimate goal when designing heuristics. We also show positive zero-shot transfer behavior when testing Graph-$Q$-SAT on a task family different from that used for training. While more work is needed to apply Graph-$Q$-SAT to reduce wall clock time in modern SAT solving settings, it is a compelling proof-of-concept showing that RL equipped with Graph Neural Networks can learn a generalizable branching heuristic for SAT search.
BibTeX
@inproceedings{kurin2020improving,
  author = {Vitaly Kurin and Saad Godil and Shimon Whiteson and Bryan Catanzaro},
  title = {{Improving SAT Solver Heuristics with Graph Networks and Reinforcement Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=2leA9BP0dn},
}
Figure