Can Q-Learning with Graph Networks Learn a Generalizable Branching Heuristic for a SAT Solver?

Vitaly Kurin, Saad Godil, Shimon Whiteson, Bryan Catanzaro

Introduction

Boolean satisfiability (SAT) is an NP-complete problem that serves as the backbone for many critical applications, including circuit design, software verification, and automated theorem proving. Modern Conflict-Driven Clause Learning (CDCL) SAT solvers rely heavily on meticulously hand-crafted heuristics to navigate massive search spaces.

The most popular branching heuristic, VSIDS, is counter-based. It tracks how often variables are involved in conflicts and branches on the most active ones. However, VSIDS starts with zero knowledge and makes poor, essentially random decisions during its initial "warm-up" period.

To address this, researchers introduce Graph-Q-SAT, a reinforcement learning-based branching heuristic that uses Graph Neural Networks (GNNs). By replacing the standard VSIDS heuristic during the early stages of search, Graph-Q-SAT reduces the number of solver iterations by 2-3X and demonstrates remarkable zero-shot generalization to larger problems, unsatisfiable instances, and entirely new task families.

The Graph-Q-SAT Approach

The authors frame the SAT branching process as a Markov Decision Process (MDP) and train an agent using Deep Q-Networks (DQN).

  • State Representation: The SAT formula is represented as a bipartite graph where nodes are either variables or clauses, and edges indicate whether a variable appears in a clause (and its polarity). This representation is invariant to variable renaming and permutation.
  • Network Architecture: A GNN processes the graph and outputs Q-values for each unassigned variable node, representing the value of setting that variable to True or False.
  • Integration with MiniSat: Because neural network inference is computationally expensive, Graph-Q-SAT acts as a heuristic inside the open-source MiniSat solver for only the first few decisions (e.g., the first 10 to 100 steps). This "warms up" the solver by pruning the search tree early, after which control is handed back to the lightning-fast VSIDS heuristic.
  • Reward: The agent receives a simple penalty for every non-terminal step and a reward of $0$ for finishing the episode, avoiding the need for complex reward shaping.

Key Insights and Results

Overcoming the Warm-up Bias

VSIDS takes time to gather statistics. Graph-Q-SAT, however, looks at the whole graph immediately, making highly informed early decisions. Using Graph-Q-SAT for just the first 10 to 50 decisions is enough to significantly outperform a purely VSIDS-based approach, triggering more variable propagations per step and forcing the solver to logically deduce more variables per decision.

Iteration improvement plateaus after a small number of initial model decisions, demonstrating Graph-Q-SAT's effectiveness at overcoming the solver's warm-up period.

Generalization and Transfer

  • Size Generalization: Counterintuitively, training on small problems (e.g., 50 variables) and transferring to larger ones (e.g., 100 or 250 variables) yielded better, more stable models than training directly on large problems. RL struggles with long episodes and sparse credit assignment on large graphs; training on small graphs bypasses this, while the GNN architecture ensures the learned logic scales up. A model trained on 50-variable problems successfully generalized to 250-variable problems, achieving nearly 4X fewer iterations than the baseline.
  • SAT to unSAT Transfer: A model trained exclusively on satisfiable (SAT) instances successfully accelerated the solver on unsatisfiable (unSAT) instances. Because the model fundamentally learns how to prune search trees efficiently, this skill transfers even when the end goal is proving no solution exists.
  • Task Transfer: The model successfully transferred zero-shot from random 3-SAT training data to flat graph coloring problems, outperforming the baseline in a majority of dataset sizes.

Extreme Data Efficiency

Because RL allows an agent to explore diverse state-action spaces within a single environment, Graph-Q-SAT can learn a highly generalizable policy from remarkably little data. The authors found that training on literally a single SAT problem instance was sufficient to learn a robust heuristic.

Graph-Q-SAT exhibits extreme data efficiency, showing significant iteration improvements even when the training set size is reduced to a single problem instance.

Limitations and Future Work

The primary limitation of Graph-Q-SAT is the wall-clock time bottleneck. Neural network inference is vastly slower than the simple array lookups used by VSIDS. While Graph-Q-SAT drastically reduces the number of iterations, it does not consistently reduce wall-clock time for smaller problems. It only starts to show wall-clock improvements on larger problems where the massive reduction in iterations outweighs the network overhead.

Future work must focus on engineering optimizations to make this competitive in industrial settings. This includes implementing the GNN in highly optimized C++, using smaller networks, and reducing the network polling frequency. Overall, Graph-Q-SAT serves as a compelling proof-of-concept that RL equipped with GNNs can learn powerful, generalizable heuristics for complex search problems.

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{kurin2020can,
  author = {Vitaly Kurin and Saad Godil and Shimon Whiteson and Bryan Catanzaro},
  title = {{Can Q-Learning with Graph Networks Learn a Generalizable Branching Heuristic for a SAT Solver?}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=2leA9BP0dn},
}
Figure