WHEN 99% IS FAILURE: DIAGNOSING THE APPROXIMATION–FEASIBILITY GAP IN NEURAL CONSTRAINT SOLVERS

Neural solvers for constraint problems can satisfy nearly all constraints of an instance yet never return a feasible assignment. We exhibit this approximation–feasibility gap in a controlled setting using random $3$-SAT, where clause density produces cohorts with different coordination demands. At $3.7$ clauses per variable—an intermediate, constrained cohort in our density sweep—we evaluate four closely related GNN configurations, each across three independent training runs. All satisfy $97$–$100\%$ of clauses on average, yet three never return a feasible assignment while OptGNN-Clause succeeds on about half of the formulas. We ask why approximation-equivalent architectures differ in exact success, and how that separation changes across the density sweep. Our analysis crosses three axes: architecture, the concept linearly accessible from a network—here support, how firmly each variable's current value is held in place by the clauses it alone satisfies—and generator-defined difficulty regimes. A crossed ablation shows that constraint-level aggregation and the relaxed-label output/loss configuration yield feasible solutions only in combination; aggregation alone makes support accessible in a form that transfers across formulas even in a configuration that solves nothing, and this accessibility persists at densities where solving collapses. NAE-SAT reproduces the pattern, coloring preserves the behavioral advantage on a planted family, and Max-Cut bounds its scope. Evaluating neural solvers therefore requires varying architecture and regime jointly and reporting feasibility alongside approximation, with representation analysis explaining what a design adds and what it still lacks.