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 wide-ranging applications in hardware verification, software security, and automated reasoning. Modern solvers typically employ Conflict-Driven Clause Learning (CDCL), relying on branching heuristics to select the next variable for assignment. The industry-standard heuristic, VSIDS (Variable State Independent Decaying Sum), is history-based, learning from past conflicts. However, VSIDS often performs poorly during the initial "warm-up" phase of the search. This research introduces Graph-$Q$-SAT, a reinforcement learning agent designed to overcome this limitation by learning a structural branching heuristic that makes high-quality decisions from the very first step.
Methodology
Graph-$Q$-SAT treats SAT solving as a sequential decision-making process within a reinforcement learning framework. The solver's state is represented as a bipartite graph, where nodes represent variables and clauses, and edges represent the participation of literals in clauses. This representation ensures invariance to the ordering of variables and clauses.
The architecture employs a Graph Neural Network (GNN) to process this graph, using message passing to build a global understanding of the problem's constraints. The GNN outputs embeddings that are used by a Deep Q-Network (DQN) to predict the value of branching on specific variables. By integrating this neural heuristic into the MiniSat solver, the system maintains "completeness"—it is guaranteed to find a solution or provide a proof of unsatisfiability.
Experimental Results
The agent was primarily trained on random 3-SAT instances with 50 variables and evaluated on its ability to generalize across different problem scales and types.
Iteration Reduction and Generalization
Experimental results demonstrate that Graph-$Q$-SAT significantly outperforms the VSIDS baseline, reducing the number of iterations required to solve problems by 2-3X. A key strength of the model is its zero-shot generalization capability: a model trained on 50-variable instances successfully scales to problems with 250 variables (a 5X increase) and generalizes to unsatisfiable (unSAT) instances without additional training.
Data Efficiency and Transfer Learning
The training process is remarkably data-efficient. Due to the extensive exploration possible within a single search tree, the agent can learn effective heuristics from a very small number of SAT instances. Furthermore, the model exhibits positive transfer to entirely different problem domains, such as flat graph coloring benchmarks, suggesting it learns fundamental properties of logical structures rather than just overfitting to specific datasets.
Discussion and Conclusion
While Graph-$Q$-SAT significantly reduces the iteration count, the computational cost of GNN inference presents a challenge for wall-clock time on smaller instances. However, for larger problems (e.g., SAT-250), the reduction in iterations is substantial enough to yield overall time savings. Future work will focus on optimizing the implementation—potentially through a native C++ GNN integration—and exploring synergies with advanced solver features like restarts and clause deletion. Graph-$Q$-SAT stands as a robust proof-of-concept that deep reinforcement learning can master the complex, discrete logic required for efficient SAT solving.
Summary updated