Abstract: In this contribution, we provide a comprehensive evaluation of graph neural networks applied to Boolean satisfiability problems, accompanied by an intuitive explanation of the mechanisms enabling the model to generalize to different instances. We introduce several training improvements, particularly a novel closest assignment supervision method that dynamically adapts to the model's current state, significantly enhancing performance on problems with larger solution spaces. Our experiments demonstrate the suitability of variable-clause graph representations with recurrent neural network updates, which achieve good accuracy on SAT assignment prediction while reducing computational demands. We extend the base graph neural network into a diffusion model that facilitates incremental sampling and can be effectively combined with classical techniques like unit propagation. Through analysis of embedding space patterns and optimization trajectories, we show how these networks implicitly perform a process very similar to continuous relaxations of MaxSAT, offering an interpretable view of their reasoning process. This understanding guides our design choices and explains the ability of recurrent architectures to scale effectively at inference time beyond their training distribution, which we demonstrate with test-time scaling experiments.
Introduction
The quest to understand whether artificial neural networks can truly reason or are merely sophisticated pattern matchers often leads to Boolean Satisfiability (SAT). As an NP-complete problem, SAT serves as a primary proving ground for logic and constraint satisfaction. While traditional symbolic solvers are highly optimized, recent research has explored the potential of Graph Neural Networks (GNNs) to tackle these problems. This paper evaluates the design choices that allow GNNs to solve SAT instances and provides a theoretical bridge explaining how these models perform iterative reasoning.
Graph Representations and Architectures
A critical design choice in neural SAT solving is the graph representation of the Boolean formula. The researchers compared two primary approaches: the standard Literal-Clause Graph (LCG) and the more compact Variable-Clause Graph (VCG).
As shown in Figure 1, the LCG uses separate nodes for every literal (variable and its negation), whereas the VCG uses a single node per variable and utilizes edge features to denote polarity. The VCG representation proved to be twice as memory-efficient and significantly faster for large formulas. To enable the model to "think harder" about complex problems, the authors utilized recurrent architectures (RNNs and LSTMs) rather than fixed-depth GNNs. This allows for test-time scaling, where the model can run for more iterations during inference than it encountered during training.
Closest Assignment Supervision
Standard supervision methods often penalize a model if it fails to predict a specific, pre-calculated solution. This is problematic for SAT instances that possess thousands of valid solutions. To address this, the authors introduced "Closest Assignment" training. This method employs a MaxSAT solver during the training loop to dynamically identify the valid assignment closest to the model's current prediction. By providing a more natural learning signal that respects the multi-modal nature of the solution space, this method significantly improved performance on complex benchmarks.
Interpretability: SAT Solving as Continuous Relaxation
One of the paper's most significant contributions is the visualization of the embedding space, which reveals that GNNs perform a process analogous to continuous relaxations of MaxSAT. Variable embeddings begin in a random state and gradually cluster into distinct groups representing "True" and "False" assignments. This behavior mirrors Semidefinite Programming (SDP) relaxations used in classical approximation algorithms. This insight explains why recurrent architectures can scale effectively; they are essentially performing iterative refinement on a continuous optimization surface.
Experimental Results
The models were evaluated on several benchmarks, including the Step-wise Random (SR) generator and 3-SAT formulas at the phase transition. Key findings include:
- Accuracy: On the SR40 dataset, the VCG+RNN architecture achieved 68.8% SAT accuracy and 84.4% decision accuracy.
- Supervision Impact: For the SR100 dataset, the closest assignment training reduced the average gap (number of unsatisfied clauses) from 3.81 to 1.43.
- Hybrid Integration: Combining the neural diffusion model with classical Unit Propagation (UP) improved decision accuracy by approximately 10%.
- Generalization: Models trained on 40 variables successfully generalized to 100 or 200 variables by simply increasing the number of message-passing iterations at test time (e.g., from 25 to 125 iterations).
Conclusion
While neural SAT solvers are not yet competitive with state-of-the-art CDCL solvers on industrial-scale problems, this research clarifies the architectural and supervisory requirements for neural logic. The connection between GNN updates and continuous relaxations provides a theoretical foundation for future hybrid solvers that combine neural intuition with symbolic rigor. Future work will focus on deriving GNN update equations directly from optimization objectives and improving the efficiency of dynamic supervision.
Summary updated