Scaling Neuro-symbolic Problem Solving: Solver-Free Learning of Constraints and Objectives
This addresses the challenge of hybridizing discrete reasoning with neural networks for researchers in AI and optimization, offering a scalable method for learning complex problem formulations, though it appears incremental in improving existing neuro-symbolic approaches.
The paper tackles the problem of learning to solve NP-hard reasoning problems from natural inputs by introducing a differentiable neuro-symbolic architecture and a probabilistic loss that learns both constraints and objectives, achieving scalable training and exact inference. Results show it requires a fraction of training time on Sudoku variants, optimizes regret better on a visual Min-Cut/Max-cut task, and efficiently learns protein design formulations.
In the ongoing quest for hybridizing discrete reasoning with neural nets, there is an increasing interest in neural architectures that can learn how to solve discrete reasoning or optimization problems from natural inputs, a task that Large Language Models seem to struggle with. Objectives: We introduce a differentiable neuro-symbolic architecture and a loss function dedicated to learning how to solve NP-hard reasoning problems. Methods: Our new probabilistic loss allows for learning both the constraints and the objective, thus delivering a complete model that can be scrutinized and completed with side constraints. By pushing the combinatorial solver out of the training loop, our architecture also offers scalable training while exact inference gives access to maximum accuracy. Results: We empirically show that it can efficiently learn how to solve NP-hard reasoning problems from natural inputs. On three variants of the Sudoku benchmark -- symbolic, visual, and many-solution --, our approach requires a fraction of training time of other hybrid methods. On a visual Min-Cut/Max-cut task, it optimizes the regret better than a Decision-Focused-Learning regret-dedicated loss. Finally, it efficiently learns the energy optimization formulation of the large real-world problem of designing proteins.