Neural Constraint Solvers Need Symbolic Integration for Certified Correctness

A new position paper on arXiv (2608.14569) argues that neural solvers for constraint satisfaction problems, despite high in-distribution accuracy, fail to guarantee correctness under distribution shifts, leading to persistent constraint violations even with high confidence. The authors contend that when hard constraints exist and verification is cheap, symbolic integration must be prioritized over pure learning. Using Sudoku as a representative NP-complete testbed, they highlight the asymmetry between easy verification (polynomial time O(n^2)) and hard solving (exponential search). The paper surveys solving methods including deterministic algorithms, metaheuristic optimization, learning-based approaches, and language-conditioned reasoning, demonstrating that neural-only methods are insufficient. The study emphasizes the need for hybrid approaches that combine neural networks with symbolic reasoning to ensure certified correctness. The paper is categorized as a position paper and was announced as new on arXiv.