Abstract
Integrating logical reasoning within deep learning architectures has been a major goal of modern AI systems. In this paper, we propose a new direction toward this goal by introducing a differentiable (smoothed) maximum satisfiability (MAXSAT) solver that can be integrated into the loop of larger deep learning systems. Our (approximate) solver is based upon a fast coordinate descent approach to solving the semidefinite program (SDP) associated with the MAXSAT problem. We show how to analytically differentiate through the solution to this SDP and efficiently solve the associated backward pass. We demonstrate that by integrating this solver into end-to-end learning systems, we can learn the logical structure of challenging problems in a minimally supervised fashion. In particular, we show that we can learn the parity function using single-bit supervision (a traditionally hard task for deep networks) and learn how to play 9x9 Sudoku solely from examples. We also solve a "visual Sudoku" problem that maps images of Sudoku puzzles to their associated logical solutions by combining our MAXSAT solver with a traditional convolutional architecture. Our approach thus shows promise in integrating logical structures within deep learning.
Introduction
Deep learning excels at "System 1" tasks—rapid, intuitive pattern recognition such as image classification. However, it often falters on "System 2" tasks that require deliberate logical reasoning governed by hard global constraints. For instance, while a standard Convolutional Neural Network (CNN) can recognize digits on a Sudoku board, it does not inherently understand the underlying rules of the game. If the board's layout is permuted, a CNN's performance typically collapses because it relies on spatial patterns rather than logical ones.
SATNet addresses this gap by introducing a differentiable logical reasoning layer. Unlike traditional neuro-symbolic AI, which often requires human-defined rules, SATNet can discover these rules end-to-end from data, effectively bridging the gap between perception and symbolic reasoning.
The SATNet Layer
The core innovation is the SATNet layer, a differentiable MAXSAT (Maximum Satisfiability) solver. The layer operates by relaxing discrete logical constraints into a continuous optimization framework.
The process involves three key steps:
- Relaxation: Discrete satisfiability problems are transformed into a continuous Semidefinite Programming (SDP) relaxation, making the problem amenable to gradient-based optimization.
- Fast Forward Pass: A coordinate descent approach is employed to solve the SDP efficiently, enabling the layer to be used within deep learning training loops.
- Analytical Differentiation: The authors derived a method to analytically differentiate through the SDP's optimal solution. This allows the network to backpropagate errors and learn the logical weights ($S$) necessary to satisfy the problem's constraints.
Experimental Evaluation
The authors evaluated SATNet on several tasks that are traditionally difficult for standard neural architectures.
Learning Parity
The parity problem (or chained XOR) is a classic challenge for neural networks. SATNet was tasked with learning the parity of sequences of lengths $L=20$ and $L=40$ using only single-bit supervision.
As shown in the results, SATNet achieves near-zero error almost immediately, whereas a standard LSTM fails to perform better than random guessing. This demonstrates SATNet's ability to capture global logical dependencies that sequence models miss.
Sudoku and Visual Sudoku
SATNet was trained to solve 9x9 Sudoku puzzles from 9,000 examples without being provided the rules. It achieved 98.3% accuracy, significantly outperforming a vanilla CNN (15.1%). Crucially, in the permuted Sudoku experiment—where board bits are shuffled to remove spatial locality—SATNet's performance remained unchanged. This confirms the model learns the underlying logical graph rather than simple spatial textures.
In a "Visual Sudoku" task, where inputs were MNIST digit images, SATNet achieved 63.2% accuracy. This represents approximately 85% of the theoretical maximum accuracy possible given the inherent error rate of the underlying digit classifier.
Conclusion
SATNet demonstrates that optimization problems, specifically MAXSAT, can be treated as differentiable layers within larger neural networks. By learning logical structures from scratch, it enables a "declarative" modeling approach where the network learns the goal and the solver determines how to satisfy it. While the current implementation relies on a low-rank approximation that may limit complexity in massive systems, it represents a significant step toward end-to-end neuro-symbolic learning.
Summary updated