Symbolic Integration Ensures Strict Correctness in Neural Constraint Reasoning

Summary

A position paper accepted at ICML 2026 argues that neural solvers for constraint satisfaction problems cannot guarantee certified correctness without symbolic verification under distribution shift. The paper uses Sudoku as a representative NP-complete testbed. The authors survey existing solution paradigms and propose a multi-agent framework that bidirectionally integrates neural heuristics with symbolic verification.

Why it matters

As neural solvers are increasingly deployed in safety-critical constraint reasoning tasks, the gap between high in-distribution accuracy and the lack of instance-level correctness guarantees becomes a practical liability. The paper's core asymmetry argument—polynomial-time verification versus potentially exponential search—offers a concrete, low-cost verification checkpoint often overlooked in pure learning pipelines. Furthermore, it positions neurosymbolic integration not as a novelty showcase, but as a correctness requirement. This approach sharpens the design criteria for next-generation reasoning systems.

Highlights

• Pure neural CSP solvers can report high confidence while continuing to violate hard constraints under distribution shift. This highlights a reliability gap that pure learning cannot close.
• Sudoku offers a clean testbed because checking a candidate solution is O(n²), while solving it may take exponential time. This structure makes symbolic verification cheap compared to search.
• The proposed multi-agent framework assigns heuristic/perception-to-symbol roles to neural agents and instance-level certification to symbolic agents. The framework targets both efficiency and provable correctness.

Critical take

As a position paper, the contribution is largely argumentative and survey-based. The 'multi-agent certified reasoning framework' is proposed in the summary but not compared against the best neurosymbolic baselines. This leaves practical efficiency gains unverified. Additionally, the cheap verification argument is tightly coupled to Sudoku's grid structure. The transferability of this approach is weak in CSPs where constraint checking itself is expensive. This undermines the general validity of the 'symbolic integration is always the right answer' framing.