- Rating
- 3(+1)
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This work propose a non-learned, solver-free SAT generation process which is guaranteed to produce correct SAT/UNSAT labels, along with assignment labels for the satisfiable instances and core labels for the unsat instances. It also proposes a bi-partite GNN architecture with a novel residual which is, in principle, inspired by the LP representation of SAT.
Critical strengths
- The work is, with the exception of some clarity issues in the experimental section, well written
- The work’s coverage of the literature is reasonably complete
- While the implicit problem statement (there is no explicit one given) is somewhat different than the traditional literature, the proposed method seems to do a very good job at addressing it
Critical weaknesses
- There are major clarity issues in the experimental section, as indicated in the questions section
- Unless I have seriously misunderstood the experimental procedure, I think there are major elements missing: real topological analysis (not summary graph statistics), comparison to other synthetic procedures (even if a fixed budget is imposed), comparison of the proposed architecture to other architectures, some discussion of the LP-residual ablation in the appendix (appendices shouldn’t go un-referenced in the main text), the use of more non-toy and non-random SAT problems in the evaluation, etc.
For now, I am rating the paper as a weak reject because I think that it is in need of much clarification, and some additional evidence validating the claims and propositions made in the work. With that said, I intend to be responsive during discussion phase, and if the authors can address some of my questions to a satisfactory degree I will surely increase my score. Question 7 may be a lot to ask for, but any preliminary results to that end would be appreciated. Question 8 seems necessary to address in my view, since at the moment I really can’t see a specific, impactful claim to which the proposed GNN architecture is connected. If a meaningful claim+supporting evidence can't be produced in reference to it then I can't see the point of it taking as much space as it does; it could be moved to the appendix in favour of additional experiments on the synthetic instances you generate, for example.
Questions for authors
Clarifications:
- Based on my understanding of the slack variable you define, for different satisfying solutions the slack variable for a given clause will change. How do you fix a single slack value in building the slack distribution of the target benchmark?
- L. 255: “The core is constructed to be structurally similar to the rest of the graph”: How is this done? By what metric/methodology do you measure topological similarity?
- L. 373: “In a standard bipartite SAT graph implementation, constraint nodes act as summaries of clauses”: I don’t think this is totally true. In NeuroSAT I think the most natural interpretation is that clause nodes encode whether the clause is satisfied or not. In any case no claim as to the meaning behind intermediate model representations is really defensible without severe experimentation so while I’m not necessarily contradicting this statement, I think it’s overly strong for the available evidence.
- Table 4: is the synthetic data used to train these models generated by your proposed methodology? It’s a little ambiguous because in most places, you specify target-aware synthetic instances when discussing your method. I don’t understand why you don’t include your proposed LPGNN in these results, since it seems like you can train it on assignment tasks (according you D.3 in the appendix in Table 14 under Loss function)
- Table 3: what model is being trained here? You never specify. Is it a global SAT-classifier or a clause-level classifier? CSR as a metric seems contradictory to BA/AUC in terms of the implied task, which you never explicitly specify.
- In general, are you using only the instances from your train-set to compute the statistics you need for augmentation?
More experimental Results:
- Traditionally, the aim of sat generation papers has been specifically to generate hard instances. Underlying this was the belief that a SAT-family’s hardness profile, specifically in relation to which type(s) of solvers are more effective, was a result of some structural or topological characteristics of that family. For example, it is known that random and industrial instances show different solver-performance rankings. While it’s true that you have successfully demonstrated the utility of your method as an augmentation technique (assuming that you did not use the test-sets to compute your generation statistics), it would be nice to see if your summary statistics actually preserve this topological structure in terms of hardness profiles. Solver ranking comparisons vs target and synthetic data, average runtime comparison between synthetic and target hard instances (solve-time > 50s), behaviour on random vs industrial instances (SATComp families like FPGA, Cryptography, scheduling, Tseitin, etc.), would all be very nice to have in terms of understanding the nature of your proposed methodology’s success. The graph statistics like community structure, modularity etc. have been shown to be weak as measures of a method’s ability to actually capture the topological distribution of a SAT family, and are generally not so difficult to tune for.
- It doesn’t seem like you actually directly compare LPGNN against any other SAT classification/assignment models. While you don’t actually claim that it is better than existing methods, it’s hard to see a point to its introduction without such a claim. Some kind of result to indicate that (a) the model is indeed optimization-aware (as you claim in the introduction), and that (b) an optimization-aware model is better than an optimization un-aware model, would go a long way to justify this element of the paper.
6 comments
Response to Reviewer Am6C (Part 2/2)
Regarding solver rankings and hardness preservation (Q7): We thank the reviewer for this important comment. We have added Appendix A.4: Solver-Based Evaluation of Generated Instances, containing three additional comparisons: solver rankings, hard-instance runtimes, and hardness across random and industrial SAT families. We emphasize that all target statistics used for generation are extracted exclusively from the training sets. All evaluation instances are disjoint from the training data. No test-set statistics or test instances are used for generation.
1. Solver ranking consistency.
We extend the evaluation beyond CaDiCaL to include Glucose and Lingeling solvers, comparing their relative performance on target and generated instances across SAT families. The generated instances preserve 32 of 36 pairwise solver orderings. Lingeling remains the slowest solver throughout.
| Family | Label | Target ranking | Generated ranking |
|---|---|---|---|
| 3-SAT Medium | SAT | G < C < L | C < G < L |
| 3-SAT Medium | UNSAT | G < C < L | C < G < L |
| 3-SAT Hard | SAT | C < G < L | C < G < L |
| 3-SAT Hard | UNSAT | G < C < L | C < G < L |
| 3-SAT >50 s | UNSAT | G < C < L | G < C < L |
| SATLIB uf250 | SAT | C < G < L | C < G < L |
| SATLIB uuf250 | UNSAT | G < C < L | C < G < L |
| ps Medium | SAT | G < C < L | G < C < L |
| ps Medium | UNSAT | G < C < L | G < C < L |
| SATLIB sw | SAT | C < G < L | C < G < L |
| SATLIB bms | SAT | G < C < L | G < C < L |
| SATLIB rti | SAT | G < C < L | G < C < L |
C: CaDiCaL, G: Glucose, L: Lingeling. Solvers are ranked from fastest to slowest by mean runtime.
2. Runtime comparison on hard instances.
We use hard instances requiring 50–120 seconds under CaDiCaL. The generated instances achieve comparable median and mean runtimes to the hard target instances.
| Data | Median runtime (s) | Mean runtime (s) |
|---|---|---|
| Target | 60.4 | 66.6 |
| Generated | 55.5 | 65.2 |
3. Random and industrial SAT families.
We additionally evaluate hardness preservation across random SAT benchmarks and industrial SAT Competition families.
| Type | Family | Target mean (s) | Generated mean (s) |
|---|---|---|---|
| Random | 3-SAT Hard | 4.70 | 5.16 |
| Random | SATLIB uuf250 | 2.84 | 2.68 |
| Industrial | Tseitin | 67.7 | 60.1 |
| Industrial | Scheduling | 90.0 | 112.3 |
Mean CaDiCaL runtimes on UNSAT instances.
Overall, the additional experiments demonstrate that our target-aware generator preserves most relative solver rankings and can generate instances with hardness comparable to their target distributions.
We thank the reviewer again for this comment, which motivated these additional experiments and strengthened our evaluation.
Regarding the LP residual and SAT-specific architecture comparisons (Q8): We thank the reviewer for this comment. We have strengthened Appendix C.2 with additional experiments to evaluate the contribution of the LP residual mechanism and directly compare LPGNN with an existing SAT-specific GNN.
Contribution of the optimization-aware mechanism. Our original ablation compared LPGNN with its underlying GIN backbone, demonstrating that incorporating the LP residual improves assignment quality. To further establish that this improvement comes from the constraint-violation information, we introduce an additional shuffled-residual ablation. In this variant, the right-hand sides of the linear constraints are randomly permuted when computing the LP residual, while keeping the architecture and training configuration unchanged.
The updated results on G4SATBench Medium 3-SAT are:
| Model | CSR (%) ↑ | k/m (%) ↓ |
|---|---|---|
| GIN backbone | 95.1 ± 0.1 | 5.5 ± 0.1 |
| LPGNN (shuffled residual) | 96.1 ± 0.1 | 4.4 ± 0.1 |
| LPGNN (Ours) | 97.0 ± 0.2 | 3.5 ± 0.2 |
LPGNN outperforms both the GIN backbone and the shuffled-residual variant.
Comparison with existing SAT-specific architectures. We have also added a direct comparison with QuerySAT on G4SATBench Medium 3-SAT. Both models are trained on the original training set without synthetic augmentation, using the same training protocol over three seeds.
| Model | BA (%) ↑ | AUC (%) ↑ | CSR (%) ↑ | k/m (%) ↓ |
|---|---|---|---|---|
| QuerySAT | 53.2 ± 0.2 | 53.8 ± 0.2 | 94.6 ± 0.1 | 5.9 ± 0.2 |
| LPGNN (Ours) | 66.2 ± 2.8 | 72.8 ± 2.6 | 97.0 ± 0.2 | 3.5 ± 0.2 |
LPGNN outperforms QuerySAT across all four metrics, demonstrating improved SAT classification and assignment quality.
Together, these experiments establish the contribution of the LP residual mechanism and demonstrate the effectiveness of LPGNN relative to an established SAT-specific architecture. Both comparisons are now included in Appendix C.2 of the updated manuscript.
Response
In general, I find that the authors have made efforts to respond to each question and criticism I raised in my review. For this reason, I will raise my score. I note, however, that the other reviewers correctly pointed out that the work suffers from a serious lack of comparison with other methods. While the authors addressed this partially by adding comparison to GIN backbones and QuerySAT in their response to my review, and a couple other quantified comparisons in their other responses, I have to agree with the other reviewers and so I only raise my score to a 3. I can understand that the proposed method is not directly comparable to many other works because it is produces both a generation and a label, can generate both SAT and UNSAT instances, etc. as described in the added Table 7 (in the Appendix), I certainly think that there are ways to incorporate comparisons. For example, one might compare the downstream value of augmentation using the various generation schemes. Presumably, only being able to generate UNSAT problems, for example, should hurt an augmentation method's performance. Similarly, the ranking results which the authors provided in rebuttal are difficult to interpret without a baseline comparison to other generative methods. In the end, if this paper is rejected, I seriously encourage the authors to add detailed comparisons to other methods both for the generation and classification cases. The methodology itself is quite nice, and with some more careful grounding and comparison to the literature this could be a great paper.
Response to Reviewer Am6C (Part 1/2)
We thank the reviewer for the careful reading and for recognizing that the work is generally well written, that the coverage of prior literature is reasonably complete, and that the proposed method effectively addresses its objective. We appreciate the constructive questions and the willingness to revisit the assessment during the discussion. We hope that our responses below provide the evidence and clarity needed for you to consider raising your score.
Regarding the construction of the target slack distribution (Q1): We thank the reviewer for this question. Indeed, the slack values depend on the satisfying assignment, and different assignments may induce different slack values for the same clause. However, our method does not require a unique slack assignment. For each SAT instance in the target training set, we select one satisfying assignment and compute the corresponding clause slacks. The empirical slack distribution is then obtained by aggregating these values across the training instances. In the updated manuscript, we have clarified this construction in Section 4.1, immediately following Equation (4).
Regarding topological similarity of the UNSAT core (Q2): We thank the reviewer for this observation. The contradiction core guarantees unsatisfiability, while the surrounding filler clauses are generated according to the target benchmark statistics. Our intention was to describe the integration of the core into the generated formula. We have revised Remark 2 in Section 4.2 to describe this construction more precisely.
Regarding the interpretation of clause-associated nodes (Q3): We appreciate the reviewer's comment on this point. Our intended distinction is architectural: in LPGNN, clause-associated nodes explicitly correspond to slack variables that participate in the LP residual computation. In the updated manuscript, we have revised this paragraph in Section 5 to clarify the distinction.
Regarding synthetic data and LPGNN in Table 4 (Q4): We thank the reviewer for the comment. The synthetic instances used in Table 4 are indeed generated using our proposed target-aware methodology, and we have clarified this in Section 6 of the updated manuscript. Regarding LPGNN, Table 4 focuses on NLocalSAT and QuerySAT to demonstrate that the benefits of our generated data extend beyond our proposed architecture. LPGNN is also evaluated with target-aware synthetic data in Table 15 (Appendix B.1) of the revised manuscript, which includes assignment quality metrics on Medium 3-SAT, with additional LPGNN results presented in Tables 3 and 5.
Regarding the model and metrics in Table 3 (Q5): We appreciate the reviewer’s attention to this distinction. Table 3 reports results for LPGNN, as specified in Appendix B.2. The model performs formula-level SAT/UNSAT classification and variable assignment prediction. BA and AUC evaluate the formula-level classification, while CSR and (k/m) measure the quality of the predicted variable assignments. These are complementary evaluation metrics for the same model, and we have clarified this distinction in Section 6 of the updated manuscript.
Regarding use of training-set statistics (Q6): We thank the reviewer for the question. Yes, all target statistics used for data generation are extracted from the corresponding training sets. This was stated in Appendix D.1, and we have now updated this section to make it explicit that the same applies to all target statistics.