ICML 2026 paper: Neural solvers need symbolic integration for certified correctness

A position paper accepted to ICML 2026 argues that pure neural approaches to constraint satisfaction problems (CSPs) are fundamentally limited when hard constraints and low verification costs are involved. Authors Shufeng Kong, Xiaochuan Zhang, and Caihua Liu (arXiv:2608.14569) point out that neural solvers achieve impressive in-distribution accuracy yet produce persistent constraint violations under distribution shifts—even while reporting high confidence. They advocate for a bidirectional integration: neural methods should assist symbolic solvers by learning heuristics and translating percepts into symbols, while symbolic solvers verify neural outputs to ensure reliability.

The authors use Sudoku as a representative NP-complete testbed because it exposes a sharp asymmetry: verifying a solution takes polynomial time O(n^2), but finding one can require exponential search. Through a comprehensive survey covering deterministic algorithms, metaheuristics, learning-based methods, and language-conditioned reasoning, they demonstrate that neural-only approaches lack instance-level certification. Their proposed multi-agent certified reasoning framework aims to combine computational efficiency with provable correctness, offering a concrete roadmap for building trustworthy neuro-symbolic systems in domains where mistakes are costly.