Deep learning has mastered perception—recognizing faces, translating languages, and identifying objects. However, it still struggles with "hard" logical reasoning, especially when constraints are global and discrete. Traditionally, if you wanted a neural network to follow logical rules, you had to hard-code them.
SATNet, presented at ICML 2019 by researchers from CMU and Bosch, changes this. It introduces a differentiable layer that can learn logical structures (like the rules of Sudoku) directly from data, bridging the gap between the "soft" world of deep learning and the "hard" world of symbolic logic.
TL;DR
SATNet is a differentiable MAXSAT solver that can be dropped into any deep learning architecture as a layer. It allows neural networks to learn discrete logical rules from examples in an end-to-end fashion, outperforming standard architectures on tasks like parity learning and Sudoku.
What Problem Does This Paper Address?
Modern AI is split into two camps: connectionism (deep learning), which excels at pattern recognition from raw data, and symbolism (logic), which excels at rigorous reasoning.
The challenge is that logic is inherently discrete and non-differentiable. You can't "backpropagate" through a traditional SAT solver because a small change in inputs doesn't lead to a smooth change in outputs—it usually leads to a completely different discrete solution or no solution at all. Previous attempts to bridge this gap often required researchers to manually define the logical relationships. SATNet aims to discover these relationships automatically from data.
Methods
The core of SATNet is a differentiable MAXSAT solver.
- SDP Relaxation: The authors take the discrete MAXSAT problem (finding an assignment that satisfies the maximum number of logical clauses) and relax it into a continuous Semidefinite Program (SDP). This turns a "hard" discrete search into a "smooth" optimization problem.
- Coordinate Descent: To make this practical for deep learning, they use a fast, low-rank coordinate descent approach for the forward pass. This makes the solver efficient enough to run on GPUs.
- Analytical Differentiation: Crucially, they show how to analytically differentiate through the solution of this SDP. This allows the network to update the "weights" of the logical layer (which represent the learned clauses) using standard backpropagation.
- The SATNet Layer: The layer takes probabilistic inputs (e.g., "I think this cell is a 5 with 80% certainty"), passes them through the internal MAXSAT solver, and outputs refined probabilistic assignments that satisfy the learned logical constraints.
Datasets
The authors evaluated SATNet on three challenging benchmarks:
- Learning Parity (Chained XOR): A classic "hard" problem for deep networks where the goal is to determine if a bitstring has an even or odd number of ones. They tested lengths $L=20$ and $L=40$.
- 9x9 Sudoku: Learning the rules of Sudoku solely from examples of solved and unsolved boards.
- Permuted Sudoku: A variant where the bits representing the board are randomly shuffled. This removes all spatial "locality" that a standard Convolutional Neural Network (CNN) might exploit, forcing the model to rely purely on logic.
- Visual Sudoku: A hybrid task where the input is an image of a Sudoku board (using MNIST digits). This requires the model to perform perception (digit recognition) and logical reasoning simultaneously.
Key Insights and Ideas
- Learning Rules, Not Just Solutions: Unlike a standard solver that is given rules, SATNet learns the rules. In the Sudoku task, it "discovers" that each row, column, and block must contain unique numbers without being told.
- Implicit vs. Explicit Logic: By wrapping a MAXSAT solver in a differentiable framework, the logic becomes "implicit." The network can learn to reason in a way that is compatible with the "messy" probabilistic outputs of a CNN.
- Locality vs. Logic: The success on Permuted Sudoku is a major "aha" moment. It proves that SATNet isn't just doing fancy pattern matching based on where pixels are; it is truly capturing the underlying logical constraints of the problem.
Key Results
- Parity Learning: SATNet solved the parity problem perfectly, converging to zero error within 20 epochs for both $L=20$ and $L=40$. In contrast, a standard LSTM failed to learn the function, achieving an error rate no better than random guessing (~0.47).
- Sudoku: SATNet achieved 98.3% board-wise accuracy on 9x9 Sudoku. Standard CNNs failed to generalize, getting nearly 0% accuracy on the test set despite seeing 9,000 training examples.
- Visual Sudoku: The model successfully mapped MNIST images to logical solutions with 63.2% accuracy. While this sounds low, the authors note the theoretical "best" possible for their architecture (given MNIST recognition errors) was 74.7%, meaning SATNet reached 85% of its theoretical peak.
Limitations and Future Work
- Scalability: While the low-rank SDP approach is fast, scaling to massive logical systems with millions of variables remains a challenge.
- Hyperparameters: Users must still specify the maximum number of clauses ($m$) the layer can represent, which requires some prior knowledge of the problem's complexity.
- Search vs. Optimization: The solver is an approximation. For extremely "brittle" logical problems where only one exact solution exists among trillions, the continuous relaxation might still struggle compared to discrete combinatorial solvers.
The authors suggest that the next step is integrating SATNet into even larger, more complex pipelines where the "logical" part of the problem is just one small component of a much larger system.
Summary updated