- 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 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 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.5 | 1.0 | 2.0 | 3.0 | 3.5 | 3.7 | 3.9 | |
|---|---|---|---|---|---|---|---|
| QuerySAT | 1.00 | 1.00 | 1.00 | 1.00 | .93 | .62 | .18 |
| no clause-to-variable path | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| SDP loss | 1.00 | 1.00 | .16 | 0 | – | 0 | 0 |
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.
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:
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.