acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 -SAT, where clause density produces cohorts with different coordination demands. At 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 – 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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
combinatorial optimization, GNN, neural architecture, Concpet learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_34UjOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies neural solvers and their evaluation in combinatorial problems like Boolean satisfiability. Specifically, the paper studies the gap between approximation quality (number of satisfied clauses) and exact feasibility. The main setting is 3-SAT with experiments also in NAE-SAT, Max-Cut and 3-coloring. The paper's claims and experiments are based on a fixed GNN architecture, the OptGNN (from previous work), and the paper studies variations of this architecture. The base architecture combines a GNN with an SDP-based relaxation and updates variable embeddings using learned maps which receive gradients from the relaxation objective. The variations introduce tied parameters across updates, changing the loss, and including explicit aggregation from constraints to variables. The main observation is that models perform closely in terms of fraction of satisfied clauses, while differ in the number of instances which are actually solved. To study this, the authors propose probing whether the learned representations encode support (the number of clauses for which a variable is the unique satisfying literal). The paper varies instance hardness and architecture and then studies the approximation-feasibility gap, along with whether support is recoverable from the learned representations.

Critical strengths
  • Although the difference between satisfying many clauses and exact feasibility is generally known, the evaluation problem highlighted by the paper is important. The experiments demonstrate this clearly across different clause densities.
  • The topic is relevant, as ML-based methods for combinatorial problems are gaining more traction.
  • Generalization is tested on instances of varying sizes.
  • Negative results such as performance on other SAT families are reported honestly.
  • The experimental details are given comprehensively
Critical weaknesses

W1: I don't agree with the premise of the paper. The paper claims the studied solvers are approximation equivalent, but this seems like a loose observation. Quickly looking at Figure 1a, one could claim that all methods produce an approximation ratio close to 1, so they are "equivalent". However, for 3-SAT, a random assignment already makes 7/8 clauses satisfied in expectation. With this (87.5%) as the floor, there is a meaningful difference between the different architectures already in the number of clauses satisfied. With n=1000, the approximation ratios of 0.970 and 0.998 correspond to 111 and 7 violated clauses, which is a big (15x) difference.

W2: One of the main take-away messages of the paper is that models should be compared also by the number of satisfied instances, not just the number of satisfied clauses. I fully agree with this, but also think this is already common practice in ML for combinatorial problems.

W3: The paper's claims are quite specific to the OPTGNN architecture and modifications of it. The proposed explanation for the results is not causally backed. Hence, it is unclear what contribution of the paper can be more broadly applied beyond this.

W4: The experimental comparison in the main 3-SAT regime is restricted to variants of the OptGNN architecture, so I assume the proposed variant is not proposed as state of the art for ML-based SAT solvers in this regime. Furthermore, the exact solving results do not extend to other SAT benchmarks (Table 9).

W5: The role of "support" as an explanation for performance is not established convincingly. The experiments show that support can be decoded from OptGNN-Clause's hidden states. However, this seems like a direct consequence of the information added to the message passing architecture. There does not seem to be a relationship between exact solving and support accessibility: OptGNN-Clause keeps the same support access even in the regimes where its solve rate is zero. Aggregation with the SDP objective achieves almost the same probe scores without solving any instances. In general, the experiments seem to show that support can be decoded from the most powerful architecture, not that it is a general, meaningful third axis for analyzing solver behavior.

W6: The experiments use a small number of seeds with large variation between seeds. Table 3 shows that OptGNN-Clause at c=3.7 solves 11, 55, 59, 17 percent of formulas. For such a big variation, using more seeds would be important

W7: The paper introduces specialized terminology for what is standard practice in ML for combinatorial problems. For example, "regime axis" and "behavior evaluation" means varying the parameters of a random instance generator and measuring whether each method solves the resulting instances. In general, this style tends to obscure the empirical findings. The proposed "three-axis" framing seems misleading. Architecture and instance hardness are experimental factors which can be controlled, whereas support accessibility is a property measured from representations.

Questions for authors

Q1: Could you clarify what exactly the relaxed-label output/loss configuration (OptGNN-ogit) version introduces?

Q2: Is there evidence showing that the model actually uses support to solve instances?

Q3: Is support encoded in the representation of weaker models in regimes which they solve successfully?

3 comments

Thank you for a rigorous review.

Approximation equivalence (W1). Your numbers are correct: at c=3.7 the variants leave 111, 85, 7 and about 1 violated clauses, a real difference in approximation. But there is a larger, more fundamental difference between any approximation and an exact solution. The first three variants solve essentially nothing; a model 7 clauses from a solution is as unsolved as one 111 away. That gap, not the ratio differences, is our main point, and we will emphasize it further. We will report violated-clause counts with the 7/8 floor marked and replace "approximation-equivalent" with this statement.

Solve rate as a metric (W2). Agreed for SAT-trained solvers; we will cite that practice. Relaxation-based solvers (OptGNN, Erdős GNN) are still mostly reported by approximation ratio. Our contribution is attributing the gap to specific components, not the metric itself.

Scope and causality (W3, W4). We make no state-of-the-art claim; OptGNN-Clause is a diagnostic variant. The component claims are causal at the architecture level, backed by interventions:

  • a loss × decoder × aggregation split: solving needs both the relaxed-label loss and clause aggregation (127/300 at c=3.7 even with hyperplane decoding; 0 for every other combination);
  • capacity-matched controls;
  • an 11-density ablation;
  • a replication in QuerySAT, where removing either component drops solving to 0 beyond sparse formulas.

The support claim is correlational, and we will say so (see below). SATLIB: agreed, we will state it as a limitation.

Role of support (W5, Q2). We do not claim that support explains solving or that the model uses it. The probe is a diagnostic: it asks whether a useful quantity is present in the representation, separately from whether the rest of the network can exploit it. Aggregation produces it, as you note, but not as a copy: the hidden state predicts support .08 F1 better than the aggregated clause messages (Table 5). In the hard regime (c≥3.5), solving occurs only where support emerges (Clause .78–.93, QuerySAT .79–.97, others ≤.57). Emergence is not sufficient: your two examples show this, and removing the probe direction hurts no more than removing a random one.

Support in weaker models (Q3). No. We probed OptGNN, IR and Logit at c<3.0, where they do solve. Probe F1 is .43–.55, at the structural baseline and permutation control. The weaker models solve sparse formulas without readable support, as simple algorithms do; support appears only in the configurations that solve the hard regime.

Seeds (W6). We now have six models each of Clause and Logit. Clause solves .35±.25 at c=3.7, and Clause > Logit at every density from c=3.0 to 3.9 (Welch p ≤ .044).

Terminology (W7). Agreed. Architecture and density become experimental factors and the probe a measurement; the "axis" and "behavior evaluation" terminology goes.

OptGNN-Logit (Q1). It changes three things: the readout (one logit per variable instead of a vector), the loss (the expected number of violated clauses instead of the SDP objective) and the decoder (thresholding instead of hyperplane rounding). The split above shows that the loss matters only together with clause aggregation; the decoder modulates the rate.

Thank you for the clarifications.

W1: I agree that an assignment violating seven clauses is still infeasible. However, the paper’s main empirical premise was that models with equivalent approximation performance have different solve rates. Once the difference is acknowledged, the experiments basically show that models with different approximation quality also have different solve rates, which is to be expected.

W2: I agree that this evaluation issue is more relevant for relaxation-based solvers. The paper should still make clear that its proposed contribution is the component analysis.

W3: The core of my concern is that if OptGNN-Clause is only a diagnostic variant, the paper must justify how conclusions drawn from it apply beyond OptGNN. The QuerySAT results are interesting, but I would like to see the detailed experiments added to the appendix to properly evaluate them.

W4: Competitive solver and SATLIB: addressed and fine.

W5: The rebuttal agrees that support does not explain solving. However, the framing of the paper clearly presents support as part of the explanation for solving:

  • "Crossing the three dimensions resolves the paradox"
  • The conclusion says the three factors "explain" why similar models behave differently.
  • support is part of the "representation-and-dynamics account of the gap" The authors agree that encoding support is not necessary in the easier instances. Even limited to the hard instances, I do not see enough evidence to establish that support is what predicts solving.

W6: Increasing the number of seeds is useful. However, a variance such as .35±.25.35\pm.25 is still quite unstable.

W7: The proposed changes would address this concern once incorporated into the paper.

My main concerns remain. Adding the new experiments and proposed changes into the paper would make reassessment easier.

Thank you for the thoughtful follow-up. We appreciate the continued engagement.

W1. We agree the differences in approximation are real, and we will make this clearer in the revised version. Our point is that feasibility is all or nothing: an assignment with one violated clause is as infeasible as one with a hundred. Solving therefore does not grow smoothly with approximation. OptGNN, IR and Logit leave 111, 85 and 7 violated clauses on average. Despite a 15× improvement in approximation, none of them solves a single formula. OptGNN-Clause solves 36% exactly. A model can improve its approximation by an order of magnitude and still solve nothing. This is the gap we aim to study, and the revised version will frame it this way.

W2. Agreed. The revised version will state clearly that our contribution is the component analysis.

W3. As requested, here are the QuerySAT results on the same formulas: solve rate by density, three seeds per row.

c=0.51.02.03.03.53.73.9
QuerySAT1.001.001.001.00.93.62.18
no clause-to-variable path0000000
SDP loss1.001.00.160–00

Both components are required in a second, independent family as well. The full experiments, including the probe results, will appear in the appendix of the revised version.

W5. Thank you for pointing to the specific sentences; you are right that they overstate the role of support. We will make this clearer in the revised version. We will remove "resolves the paradox", "explain" and "representation-and-dynamics account", and present support as a diagnostic measurement rather than an explanation of solving.

W6. We agree the between-run variance is large, and the revised version will report it openly. The ordering, however, is stable. Clause outperforms Logit at every density from c=3.0 to 3.9 over six seeds each (Welch p ≤ .044), and every Clause seed solves more than every non-Clause seed (exact permutation p = .0045). Our claims rest on this ordering rather than on the mean rate.

W7. Thank you. These changes will be incorporated in the revised version.

Reviewer_Uxt2OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper sets to investigate why neural constraint solvers fail to produce feasible solutions in slightly more constrained regimes. In particular, they emphasize the issue of these solvers generally achieving something akin to solutions satisfying 99% of the constraints, which in discrete problems is not that helpful because the path towards feasibility is not always straightforward. The authors use a reputable neural solver, OptGNN, a create some variations of this solver to study and to try addressing this gap. The result is a slightly better solver for a slightly more constrained regime, which they call OptGNN-Clause.

Critical strengths

The paper starts on a great note, clearly explaining the issue with neural constraint solvers. I also appreciate how the authors set forth metrics and possible modifications that could help addressing the issue, not biasing themselves towards any of those, and then evaluate them according to their metrics. The top two plots in Figure 1 make it evident what their push meant in terms of improving the performance.

Critical weaknesses

W1) There is a certain contrast between how the paper opens ("let's understand what holds neural constraint solvers back") and how it progressively shifts to another message ("we are proposing a variant of a known neural constraint solver"). First, at no point I have seen the authors acknowledging that they are the ones proposing OptGNN-Clause: you infer that from the context. At first it is actually confusing: why is this particular solver being mentioned out of the blue? Second, by focusing the entire evaluation on a single existing neural solver, it is not clear if their conclusions are immediately transferable to other neural solvers at the state-of-the-art frontier.

W2) Starting at the fifth paragraph of the introduction, the writing style changes dramatically and the authors start assuming a lot of background from the readers, in particular about SAT. As someone with training primarily in integer programming and secondarily in constraint programming (having shifted later in life to machine learning like many and being assigned neural solver papers because someone has to review them), I have a respectful but incomplete knowledge of SAT. For example, when the authors started putting emphasis on the 3.7-clause ratio, I assumed that this would be the first threshold in easy-hard-easy phase transitions widely studied a few decades ago. But it is more nuanced than that, as Google's AI put it: at 3.7, SAT formulas are " almost globally guaranteed to be satisfiable" (near 100% of them can be solved), with the transition actually starting at 3.86. I also never heard of NAE-SAT.

W3) Related to the point above, the introduction is actually a big summary of the paper (this is validated by how often along the paper there is a mention about how something was already explained at the introduction), whereas introductions should ideally help the reader understand the paper question, the concepts involved, and how the study proceeds. Introductions should not require the reader to search for terminology to understand what is going on. The related work section is small and basically a rehash of the same three streams already mentioned in the introduction, with almost nothing new in it.

(A few other weaknesses are opened up as part of the questions for authors below.)

Questions for authors

Q0) Can you please comment on W1-W3?

Q1) What is the main point of this paper: proposing a neural solver variant or addressing a broader question?

Q2) Assuming that the point of this paper is proposing a neural solver variant, why not benchmark with methods other than its ancestor? Showing that you get better results at a particular constrainedness regime with respect to a single solver does not validate that you have achieved state-of-the-art for that particular constrainedness regime. In this case, you do not need to modify the other methods: just compare with them.

Q3) Assuming instead that you are mainly addressing a broader question, why not evaluate multiple neural solvers for answering it? In this case, you may or may not modify the other methods, depending on how far you would like to establish your modifications as a general improvement for neural solvers.

Q4) The paper proposing OptGNN mainly focuses on optimization problems. Yours is mainly focused on feasibility problems, with exception of MaxCut in both. Why the shift?

Q5) One alternative not mentioned anywhere in the paper, but widely used to address this gap, is to have some sort of repair for the solutions that the neural solver produces. Why did you not mention it? How would you argue that repair is not the right way to go for addressing this gap?

3 comments

Thank you for the detailed and constructive review.

Main point (Q1, W1). The paper addresses a broader question: why do neural constraint solvers reach high approximation but rarely produce feasible solutions? OptGNN-Clause is our own variant, built as a diagnostic that adds one component (clause aggregation). It is not proposed as a new solver. We will state this explicitly when it is first introduced.

Other solvers (Q2, Q3, W1). We make no state-of-the-art claim, but we now report references on the same formulas (solve rate at c=3.7): WalkSAT 1.00, MiniSat (60 s) .40, QuerySAT .98–1.00, OptGNN-Clause .36. To test transfer, we replicated the ablations in a second neural family, QuerySAT. Removing its clause-to-variable path, or replacing its loss with the SDP loss, drops solving to 0 beyond sparse formulas, as in OptGNN.

Why c=3.7 (W2). You are right: the satisfiability threshold is about 4.27, and every test formula at c≤3.7 is certified satisfiable. This is exactly our point: each formula has a perfect solution, yet models trained to optimize the approximation objective do not reach it. The 3.86 you mention is where the solution space breaks into clusters. Local search becomes hard as c approaches it, and the sweep continues through 3.86 and 3.9. Beyond that, empirically every model we tried fails. The rewritten introduction will define 3-SAT, density, the threshold and NAE-SAT (3-SAT where no clause may have all literals equal).

Introduction and related work (W3). Agreed. We will restructure the introduction as question → background → approach → findings, remove the forward summaries, and expand the related work with SAT-trained solvers, repair and decoding.

Why feasibility (Q4). OptGNN itself evaluates Max-SAT; we keep the same problems and change the metric. On satisfiable instances, a user needs a full solution, and there the approximated solution stops being informative: models that satisfy ≥97% of clauses solve nothing. This is our central point: optimizing the approximation objective alone does not carry a solver to the true solution of a Max-SAT instance that has a perfect one. Max-Cut is included for completeness, as a problem with no "perfect" solution, to see how the same components behave when approximation is the real goal.

Repair (Q5). Agreed that it belongs in the paper. We ran min-break repair from each model's output at c=3.7:

Start100 flips1000 flips10^4 flips
OptGNN / IR / Logit≤.01.18–.24~.90
OptGNN-Clause.40.59.94
random assignment00.68

Repair complements the model rather than replacing it. Under cheap repair the component gap persists. Under large budgets the local search solves even from random starts, so it masks the model's contribution instead of explaining it.


I appreciate the detailed follow up on my review. As it stands, my main concern is the following:

If the point of the paper is addressing the broader question, then the evaluation cannot be based on modifying a single method.

Thank you for reading our response so carefully. This is a fair concern, and we see that the paper did not make our setup clear. The evaluation does not rest on modifying a single method. We replicated the ablations in QuerySAT, an independently designed solver whose architecture and loss are not derived from OptGNN. The result transfers: removing QuerySAT's clause-to-variable path, or replacing its loss with the SDP loss, drops solving to 0 beyond sparse formulas, just as in OptGNN. The full results by density are in our reply to Reviewer 34Uj. We will make this clearer in the revised version and add the complete QuerySAT experiments to the appendix.

Reviewer_hKQEOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates why neural constraint solvers satisfy nearly all constraints yet fail to return a complete feasible assignment. The authors incrementally extend OPTGNN with iterative refinement, relaxed-label output/loss, and constraint-level aggregation, comparing satisfied-clause ratio, solve rate, and support across difficulty levels. Only the combination of the latter two modifications substantially improves solving, yet models can still fail completely even when support remains readable.

Critical strengths
  1. Reporting both satisfied-clause ratio and exact solve rate across difficulty levels clearly reveals problems that average satisfaction alone would miss.
  2. The cross-ablation helps disentangle contributions of two components, while cross-instance probes and multiple controls also strengthen the credibility of the support analysis.
Critical weaknesses
  1. The relaxed-label configuration changes output, loss, and decoding at once. While the ablation shows it works well with constraint aggregation, it remains unclear which specific change drives the improvement.
  2. Main conclusions come from the OPTGNN family. Cross-problem experiments are valuable but do not yet show the same relationship holds for other neural solvers. The near-absence of complete solutions on SATLIB also limits the practical scope of the conclusions.
Questions for authors
  1. Why was OPTGNN chosen? Could the "support remains readable yet solving fails" phenomenon be verified on NeuroSAT or QuerySAT?
  2. Could the authors confirm that near-boundary formulas in the main test set are satisfiable? As clause density increases, some formulas may be UNSAT, so the solve-rate decline could reflect either the model failing to find an existing solution or the formulas themselves being unsatisfiable. Certification currently relies on a small auxiliary sample and has not covered all main test instances.
2 comments

Thank you for the careful review.

Why OptGNN? It is a strong, recent solver (NeurIPS 2024) with competitive approximation results on Max-Cut and Max-SAT, and it provably captures SDP-optimal approximation. Like most relaxation-based solvers, it is evaluated by approximation ratio, which makes it a natural test of whether high approximation implies feasibility. Its components (SDP loss, vector readout, gradient-only formula access) are separable, so each can be swapped while the rest stays fixed.

Other solvers. NeuroSAT is trained as a SAT/UNSAT classifier and has no constraint loss to swap, so we replicated the design in QuerySAT (three seeds, same formulas):

  • unmodified: solves .62 at c=3.7;
  • without its clause-to-variable path: 0 at every density;
  • with the SDP loss: 0 from c=3.0 on.

Its probe F1 is .79–.97 (controls ≤.57). The final version will add the probe on the ablated models and on seeded retrains at c=3.9, where solving drops to .18.

Satisfiability. CP-SAT certified every P100 and A30 test formula at c≤3.7 (910, full sets, none undecided), so the zeros there are solver failures. Above that, solving only gets harder as c increases, and every model we tried fails at the higher densities; the final version will add these all-zero results. Near the threshold, a fully certified n=250 set confirms the ordering: all formulas at c=3.86 and 3.9 are satisfiable, and OptGNN and IR solve 0, Logit .02–.05, and Clause .29–.32.

Which change matters (W1). A loss × decoder × aggregation split (three seeds per cell) isolates it. At c=3.7:

  • SDP loss, with or without clause aggregation: 0/300 under every decoder.
  • Relaxed-label loss without clause aggregation: 0/300.
  • Relaxed-label loss with clause aggregation: 127/300 (hyperplane decoding), 210/300 (threshold decoding).

Solving needs both the relaxed-label loss and clause aggregation; the decoder only modulates the rate.

Scope (W2). QuerySAT covers the second family. SATLIB: agreed, we will state it as a limitation.

Thank you for the response and additional experiments. The new ablations and satisfiability certification of the main test sets substantially address my main experimental concerns. The QuerySAT results also provide evidence that the component findings extend beyond a single solver family. I therefore maintain my weak acceptance recommendation.

I also agree with the other reviewers about the scope of the contribution. The models should not be described as having equivalent approximation quality, and support is better treated as a diagnostic measure than as an explanation of how the models solve instances. The support analysis across solver families remains incomplete, and there are still inconsistencies in the reported QuerySAT results and gaps in the details of the additional experiments. These limitations do not change my overall positive assessment of the component analysis.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.