acceptodds
Under review as a conference paper at ICLR 2027

Target-Aware Data Generation for SAT Learning

Abstract

Learning-based methods for NP-hard problems are becoming increasingly effective, but their scalability is often limited by the cost of obtaining labeled training data. For Boolean satisfiability (SAT), standard dataset construction typically requires generating formulas and then invoking a solver to determine their labels, creating a solver-in-the-loop bottleneck that becomes increasingly expensive as problem size grows. In this work, we introduce a target-aware, solver-free framework for SAT data generation that constructs labeled SAT and UNSAT instances directly, without requiring solver-based verification. The generated formulas are designed to match structural properties of a target benchmark, improving their usefulness for downstream learning. We also introduce a linear-programming-aware graph neural network (LPGNN) that incorporates constraint-violation residuals into message passing, allowing the model to exploit the underlying optimization structure of SAT. Together, these components provide a data-centric approach to SAT learning in which scalable, benchmark-aligned data generation complements model architecture. Empirically, our framework achieves orders-of-magnitude faster data generation while producing synthetic instances that effectively improve GNN-based SAT prediction.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
boolean satisfiability, synthetic data generation, solver-free learning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_Am6COpenReview ↗
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
  1. The work is, with the exception of some clarity issues in the experimental section, well written
  2. The work’s coverage of the literature is reasonably complete
  3. 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
  1. There are major clarity issues in the experimental section, as indicated in the questions section
  2. 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:

  1. 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?
  2. 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?
  3. 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.
  4. 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)
  5. 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.
  6. In general, are you using only the instances from your train-set to compute the statistics you need for augmentation?

More experimental Results:

  1. 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.
  2. 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
AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

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.

FamilyLabelTarget rankingGenerated ranking
3-SAT MediumSATG < C < LC < G < L
3-SAT MediumUNSATG < C < LC < G < L
3-SAT HardSATC < G < LC < G < L
3-SAT HardUNSATG < C < LC < G < L
3-SAT >50 sUNSATG < C < LG < C < L
SATLIB uf250SATC < G < LC < G < L
SATLIB uuf250UNSATG < C < LC < G < L
ps MediumSATG < C < LG < C < L
ps MediumUNSATG < C < LG < C < L
SATLIB swSATC < G < LC < G < L
SATLIB bmsSATG < C < LG < C < L
SATLIB rtiSATG < C < LG < 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.

DataMedian runtime (s)Mean runtime (s)
Target60.466.6
Generated55.565.2

3. Random and industrial SAT families.

We additionally evaluate hardness preservation across random SAT benchmarks and industrial SAT Competition families.

TypeFamilyTarget mean (s)Generated mean (s)
Random3-SAT Hard4.705.16
RandomSATLIB uuf2502.842.68
IndustrialTseitin67.760.1
IndustrialScheduling90.0112.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:

ModelCSR (%) ↑k/m (%) ↓
GIN backbone95.1 ± 0.15.5 ± 0.1
LPGNN (shuffled residual)96.1 ± 0.14.4 ± 0.1
LPGNN (Ours)97.0 ± 0.23.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.

ModelBA (%) ↑AUC (%) ↑CSR (%) ↑k/m (%) ↓
QuerySAT53.2 ± 0.253.8 ± 0.294.6 ± 0.15.9 ± 0.2
LPGNN (Ours)66.2 ± 2.872.8 ± 2.697.0 ± 0.23.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.

Reviewer_Am6COpenReview ↗

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.

Reviewer_DSiaOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes an instance-generation technique for Boolean satisfiability and uses the instances to augment training data for a GNN predicting satisfying assignments. The instance generation method is based on planted assignments, where a satisfying assignment is fixed and the formula is constructed by adding clauses consistent with the assignment. The benefit of this approach is that it does not require the formula to be repeatedly solved, making it more efficient computationally. The authors propose a generation method which mimics the structure of a target formula, based on matching a slack distribution of the target formula under a fixed satisfying assignment. The slack of a clause is defined as the number of true literals in a clause minus one, and the slack distribution of a formula is the distribution of clause slacks. In the proposed method, the added clauses are sampled with slack proportional to this distribution. The paper also proposes an architecture combining standard message passing with a linear programming based component. The experiments evaluate efficiency of the instance generator, the distributional claims as well as performance improvements from training data augmentation.

Critical strengths

Efficiently generating more labeled SAT instances is an important and underaddressed problem, as ML-based methods for combinatorial problems become more prominent. Furthermore, I believe the distributional guarantees for the generated instances are at the center of what is important. This is a non-trivial problem and there are not many methods (classic or ML based) which succeed in this so far.

Critical weaknesses

W1: There are relevant instance generation baselines which are not evaluated. Planted SAT is not a new approach for generating instances. There are several papers which study this approach, including [1,2]. Table 2 should report some baseline results, and these methods would be a good start. The methods in [1,2] are not target-specific since they do not e.g. take a target slack distribution as input. However, to understand whether being target-specific helps beyond matching the slack distribution, it would be crucial to compare to these baselines. This is especially important since there are no theoretical guarantees in the paper about matching the target formula, beyond the slack distribution (which only works for satisfiable formulas, see below).

W2: The related work discussion omits directly relevant prior work. [3] studies label-preserving augmentations for SAT and the effect of using them to augment the training set. The current discussion focuses on generic graph augmentations which overstates the novelty of this work.

Furthermore, [4] proves that polynomial-time generators for labeled instances necessarily produces instances from an easier family rather than being NP-hard. This means that the augmentation / planted assignment-based approach used in this paper produces formulas from an easier family. Hence the comparison in Table 1 is potentially misleading, since the generated formulas come from an restricted distribution even though they are close to the phase transition.

W3: A new GNN architecture for SAT is proposed, but it is not directly compared to existing SAT-specific GNNs like QuerySAT.

W4: The proposed formula construction does not seem meaningful for unsatisfiable formulas. For satisfiable formulas, picking a satisfying assignment defines a meaningful slack distribution. However, for unsat formulas, the reference assignment is not derived from a real target formula but instead chosen based on the fixed contradiction-core construction.

The target formula could have multiple clauses which do not have any satisfied literals under the fixed assignment, whereas the generated formulas by construction always have an assignment with exactly one unsatisfied clause. Hence the slack distributions cannot match in some cases. Figure 1 excludes s=-1, which feels like the mismatch is being hidden.

The core is constructed to be structurally similar to the rest of the graph, and the surrounding filler clauses are sampled to match the target domain. This target-aware method embeds the contradiction within a statistically similar topology, ensuring that it acts as an inherent part of the global formula.

It is not clear from the paper how to select a core-contradiction which is topologically similar to a given target formula. The paper uses Tseitin formulas, which are fine as an unsatisfiable subformula but there doesn't seem to be any theoretical backing as to why these would be topologically similar. The appendix says that the size of the core is selected to match solving time of the target formula, but this is unrelated to topology.

Table 2 should report results separately for generated satisfiable and unsatisfiable formulas.

[1] Achlioptas, Dimitris, Haixia Jia, and Cristopher Moore. "Hiding satisfying assignments: two are better than one." Journal of Artificial Intelligence Research 24 (2005): 623-639.

[2] Jia, Haixia, Cristopher Moore, and Doug Strain. "Generating hard satisfiable formulas by hiding solutions deceptively." Journal of Artificial Intelligence Research 28 (2007): 107-118.

[3] Duan, Haonan, et al. "Augment with care: Contrastive learning for combinatorial problems." International Conference on Machine Learning. PMLR, 2022.

[4] Yehuda, Gal, Moshe Gabel, and Assaf Schuster. "It’s not what machines can learn, it’s what we cannot teach." International conference on machine learning. PMLR, 2020.

Questions for authors

Q1: Is there a difference between constraint satisfaction rate and violated-clause fraction (as a percentage)? Table 4 uses both but it is not clear why two different notations is needed.

5 comments
AuthorsOpenReview ↗

Response to Reviewer DSia (Part 1/2)

We thank the reviewer for recognizing that efficient generation of labeled SAT instances is an important and underaddressed problem, and that matching the distribution of target instances is a non-trivial and important challenge. We hope that the additional experiments and clarifications presented below will address your concerns and encourage you to reconsider your assessment.

Regarding planted-SAT generation baselines (W1): We thank the reviewer for highlighting these important baselines. We have extended the Related Work section to discuss Achlioptas et al. (2005) and Jia et al. (2007).

We have further added Appendix A.3: Comparison with Planted-SAT Generators, including experiments with 1-hidden, 2-hidden, and q-hidden generation.

Methodological comparison. These baselines focus on generating challenging satisfiable formulas without conditioning on a target benchmark. Our contribution is different: we incorporate target-specific clause-width, variable-occurrence, and slack statistics, while supporting both SAT and UNSAT generation.

MethodConstructionTarget-awareLabels
1-hiddenStandard solution plantingNoSAT
2-hiddenComplementary solutionsNoSAT
q-hiddenBias-controlled plantingNoSAT
OursTarget-conditioned planting / contradiction coreYesSAT/UNSAT

Generation quality. We additionally compare the methods on G4SATBench Medium 3-SAT, using identical formula sizes and 300 instances per group. Since the planted-SAT baselines generate only satisfiable formulas, this comparison evaluates SAT instances exclusively, unlike Table 2, which includes both SAT and UNSAT instances.

MetricTarget1-hidden2-hiddenq-hiddenOurs
Clause width33333
Modularity0.160.160.160.160.16
Clustering0.260.260.260.260.27
Communities6.36.26.36.36.2
Median CDCL decisions634101231416440
Median solve time (ms)2.20.30.71.41.5

Our generator achieves the closest agreement with the target in both median CDCL decisions and solve time.

The novelty of our framework is not just the use of planted assignments, but their integration into a target-aware, solver-free generation mechanism. We thank the reviewer again for suggesting these comparisons, which have helped us strengthen the evaluation and clarify the distinction from existing planted-SAT approaches.

Regarding relevant prior work (W2): We thank the reviewer for pointing out these relevant studies. We have added both references to the revised manuscript and clarified the discussion of prior work and the interpretation of our generation-efficiency results. Regarding Duan et al. (2022). We have updated the Related Work section to explicitly discuss their approach and clarify the distinction from ours. While their method applies label-preserving transformations to existing formulas, our framework generates new labeled SAT and UNSAT instances from the ground up, matching the structural statistics of target benchmarks. Regarding Yehuda et al. (2020). Our method does not aim to solve arbitrary SAT instances in polynomial time. Rather, its objective is to efficiently generate correctly labeled training data that captures the characteristics of the target distribution. Importantly, this theoretical distinction does not imply that the generated instances are necessarily easy for practical SAT solvers or that they cannot provide useful training data. Our method matches target benchmark statistics, and we evaluate the resulting structural similarity and solver hardness in Tables 2, 8, and 9. Furthermore, the downstream models are evaluated on the original benchmark test sets. We have also clarified Section 6 with a citation to Yehuda et al. The efficiency comparison supports our intended contribution of scalable, target-aware data generation, without making claims about solving NP-hard problems in polynomial time.

AuthorsOpenReview ↗

Response to Reviewer DSia (Part 2/2)

Regarding comparisons with SAT-specific GNNs (W3): We thank the reviewer for this comment. In the updated manuscript, we have added a direct comparison between LPGNN and QuerySAT on G4SATBench Medium 3-SAT in Appendix C.2. Both models are trained on the same original training set without synthetic augmentation and evaluated under the same experimental protocol. The results show that LPGNN outperforms QuerySAT across all four metrics, improving balanced accuracy from 53.2% to 66.2%, AUC from 53.8% to 72.8%, CSR from 94.6% to 97.0%, and reducing the violated-clause fraction from 5.9% to 3.5%. This comparison complements the existing ablation against the GIN backbone (Table 20), which isolates the contribution of the LP residual mechanism.

ModelBA (%) ↑AUC (%) ↑CSR (%) ↑k/m (%) ↓
QuerySAT53.2 ± 0.253.8 ± 0.294.6 ± 0.15.9 ± 0.2
LPGNN (Ours)66.2 ± 2.872.8 ± 2.697.0 ± 0.23.5 ± 0.2

Regarding UNSAT construction and slack distributions (W4): We thank the reviewer for these observations. Unlike SAT generation, where a satisfying assignment defines the induced slack distribution, UNSAT generation uses a reference assignment to construct the filler clauses, while a contradiction core guarantees unsatisfiability. This distinction is important for interpreting Figure 1. The UNSAT panel illustrates the target-derived distribution used for filler-clause generation: the target statistics are computed over satisfied clauses under random assignments, and the generated values are sampled from this distribution. Since the filler clauses are constructed to be satisfied under the reference assignment, their slack values are nonnegative. Thus, the absence of (s=-1) follows from the scope of this comparison. We have clarified this in the revised figure caption and Section 6. The purpose of our construction is to combine guaranteed UNSAT labels with target-aware generation of the surrounding clauses, rather than guaranteeing exact slack matching for the complete UNSAT formula. The quality of the resulting complete formulas is evaluated separately through structural statistics and solver hardness in Tables 2, 8, and 9, as well as their effectiveness for downstream learning tasks. Regarding the contradiction core, its purpose is to guarantee unsatisfiability, while its size is calibrated to obtain solver hardness comparable to the target benchmark. This calibration concerns computational hardness , and we have revised Remark 2 in Section 4.2 to clarify the respective roles of the contradiction core and target-aware filler clauses. We thank the reviewer again for this comment, which helped us clarify the presentation of our method. We have revised Section 4.2, Remark 2, and the discussion and caption of Figure 1 to more precisely describe the UNSAT construction and the interpretation of the slack distributions.

Regarding CSR and violated-clause fraction (Q1): We thank the reviewer for the question. CSR measures the percentage of satisfied clauses on SAT instances, whereas (k/m) measures the percentage of violated clauses on UNSAT instances. Although the two metrics are complementary, they are reported to evaluate assignment quality on SAT and UNSAT instances. We have clarified their definitions and usage in Section 6 of the updated manuscript.

Thank you for the response and clarifications.

W1: I still have concerns regarding the effectiveness of the conditioning mechanism. I agree that these methods are not target specific. However, they are very close to the proposed method, which is why comparing to them is very important to establish that the proposed conditioning mechanism provides actually improves results for statistics other than the slack distribution. Looking at the generation quality table, it seems like modularity, clustering and communities are similar to the target formulas for all methods, not just the proposed method with the conditioning mechanism. Regarding the hardness of the instances, 1-hidden and 2-hidden variants seem to produce clearly easier instances but q-hidden seems quite similar to the proposed method. Thus, the benefit of the target conditioning mechanism remains unclear.

W2: I consider this as mostly addressed.

As discussed by Yehuda et al. (2020), efficient generation of labeled instances is distinct from solving arbitrary instances of an NP-hard problem

I just want to correct a possible misunderstanding regarding Yehuda et al. I agree that their result does not imply that every generated instance is easy for CDCL or useless for augmentation. However, the reason I pointed to this paper was because the proposed paper presents the runtime comparison in Table 1 in a way that could be interpreted as treating the generated instances as an equal substitute. What Yehuda et al. show is that this cannot be the case. Namely (under common complexity theoretic assumptions), instances generated by augmentations or with the proposed method necessarily come from a a restricted family (NP ∩\cap coNP). This does not imply that individual generated instances cannot be difficult for practical solvers. I still suggest revising the current description of Yehuda et al. to better reflect this distinction.

W3: Addressed.

W4:

the target statistics are computed over satisfied clauses under random assignments

The problem is that if the target distribution is defined by random assignments, the slack distribution does not actually provide target-specific information. Under a random assignment, the number of satisfied literals in a clause with 3 literals is binomially distributed: T∼Binom⁡(3,1/2)T\sim\operatorname{Binom}(3,1/2). After conditioning on the clause being satisfied and defining S=T−1S=T-1 Pr⁡(S=0,1,2∣T≥1)=(37,37,17)\Pr(S=0,1,2\mid T\geq1) = \left(\frac37,\frac37,\frac17\right) These are exactly the values we observe in Figure 1 for unsat instances. Hence, I do not believe this way of conditioning is meaningful for unsat instances.

Regarding the contradiction core, its purpose is to guarantee unsatisfiability, while its size is calibrated to obtain solver hardness comparable to the target benchmark. This calibration concerns computational hardness

Because the UNSAT core size is chosen to match the target’s hardness, runtime agreement is not independent evidence of structural similarity. In particular, since the core size is explicitly selected to match the target solve cost, similar runtimes are expected by construction. Such agreement therefore does not demonstrate that the generated formulas preserve the target’s topological structure.

There is also still the problem that in an unsat formula generated by the proposed method, there is always an assignment satisfying all but one clause. Therefore, the complete generated and target formulas cannot have matching residual distributions whenever every assignment to the target formula violates more than one clause.

Summary: I still think this paper attempts to solve an interesting and difficult problem. However, in its current form, the method requires major revisions: the benefit of the conditioning mechanism seems incremental compared to the planted baselines. For unsat formulas, the proposed slack conditioning does not seem to encode target specific information.

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

This paper presents a method for generating SAT instances for training GNN models. The main contribution is the target-aware data generation without involving a SAT solver. An LP-aware residual GNN architecture is also proposed. Evaluation is conducted on three perspectives, which show generally good performance.

Critical strengths
  • The data generation process is very efficient, since it doesn't depend on a SAT solver. This solves a problem commonly faced by current SAT data generation approaches.

  • Evaluation has been conducted on three perspectives: generator efficiency, generation quality and downstream utility.

Critical weaknesses
  • While this paper initially sounds like a dataset contribution, later on, the evaluation mainly demonstrated its benefits as a data augmentation technique. While these two objectives are similar, if the method is positioned as a dataset generation process, the contribution needs to be higher, e.g., the dataset quality evaluation should be more comprehensive.

  • There should be more comprehensive comparison with other SAT dataset paper, including NeuroSAT, G4SATBench, HardSATGEN, HardCore, and Fu et al.(2025), on multiple parameters, such as the dataset size, types of SAT problems, distribution, etc., not just the generation speed.

  • A more in-depth discussion should be added about the advantages and disadvantages of the proposed dataset, relatively to these existing ones. Speed is a clear advantage, but the actual properties, problem coverages, etc., can be more important for other researchers who might want to use this dataset. The current discussions in Section 6 are very limited.

  • When analyzing the scaling behavior, how many instances were generated to obtain those results in Tables 3, 4 and 5?

  • While the results demonstrate that it's useful to add the generated data for training GNN models, other data augmentation techniques have not been compared with. Some direct comparisons with other data augmentation methods should be added.

Questions for authors

Please address the weaknesses above.

4 comments
AuthorsOpenReview ↗

Response to Reviewer 6kGT (Part 1/2)

We thank the reviewer for the careful reading and for recognizing the efficiency of our solver-free data generation and the comprehensive evaluation of generator efficiency, generation quality, and downstream utility. We hope that the added comparisons and clarifications will address your concerns and encourage you to reconsider your score.

Regarding the evaluation of generation quality: We thank the reviewer for this observation. We would like to clarify that our primary contribution is a target-aware data-generation framework, rather than the introduction of a new standalone benchmark dataset. The objective is to efficiently produce correctly labeled SAT and UNSAT instances that are useful for training neural SAT models. Accordingly, downstream data augmentation is a natural evaluation of the proposed generator. We agree that evaluating the quality of generated instances independently is important. In addition to downstream performance, we already examine the agreement between generated and target instances in terms of LP slack distributions (Figure 1), structural properties and solver-perceived hardness (Tables 2, 8, and 9), and generation efficiency (Tables 1 and 6). In the updated manuscript, we have clarified this distinction in the Introduction (Section 1).

Regarding comparisons with existing SAT datasets and generation methods: We thank the reviewer for this suggestion. In the updated manuscript, we have added a comparison table in Appendix A.1 covering NeuroSAT, G4SATBench, HardSATGEN, HardCore, and Fu et al. (2025), considering their main objectives, SAT problem coverage, distributions, and data scale.

WorkMain purposeSAT problemsDistributionData scale
NeuroSATNeural SAT trainingSAT/UNSATRandom SRConfigurable
G4SATBenchBenchmarking7 SAT familiesRandom, structured80k pairs/train set
HardSATGENHard instance generationIndustrial SATStructure-awareOn-demand
HardCoreUNSAT augmentationHard UNSATCore-basedOn-demand
StructureSAT (Fu et al., 2025)Generalization benchmark11 SAT domainsStructure-diverseCurated + generator
OursTarget-aware SAT generationGeneral CNF SAT/UNSATTarget-awareOn-demand, solver-free

This comparison highlights the distinction between existing SAT datasets and generation approaches and our target-aware, solver-free framework. Rather than introducing a fixed benchmark dataset, our method generates labeled SAT and UNSAT instances aligned with the statistical properties of a given target distribution, supporting scalable data augmentation for downstream learning.

Regarding advantages and coverage relative to existing methods: We thank the reviewer for this comment. Beyond generation speed, our framework provides correctly labeled SAT and UNSAT instances without solver-based verification, while matching structural properties of a target benchmark. As demonstrated in our experiments, the generated instances reproduce key structural characteristics and solver-perceived hardness across different SAT families (Tables 2, 8, and 9). Furthermore, we evaluate the method across SAT families from G4SATBench and SATLIB. In the updated manuscript, we have added a discussion at the end of Section 6 to better explain how our framework compares with existing SAT benchmarks and generation methods, highlighting its advantages and applicability across different SAT families

Regarding the number of generated instances: We thank the reviewer for the comment. As for Table 4, the number of generated instances is explicitly reported in the table itself (500, 1,000, 5,000, and 10,000). We have also updated Section 6 of the manuscript to state the number of generated instances used in Tables 3 and 5. We note that this information was already provided for Table 3 in Appendix B.2, but we have now included it in the main text to make the experimental setup clearer and easier to follow.

AuthorsOpenReview ↗

Response to Reviewer 6kGT (Part 2/2)

Regarding alternative data augmentation approaches: We thank the reviewer for this comment. To address this, we have added a direct comparison with two alternative data augmentation approaches in Appendix C.1: (i) label-preserving perturbations, obtained by randomly flipping variable polarities in existing training formulas, and (ii) solver-labeled random 3-SAT instances generated using the G4SATBench construction and CaDiCaL. We compare the methods under a similar generation-time budget. All methods augment the same original G4SATBench Medium 3-SAT training set, over three random seeds. Our results are presented in the table below:

Training dataBA (%) ↑AUC (%) ↑
Original data66.2 ± 2.872.8 ± 2.6
+ Label-preserving perturbation69.8 ± 0.874.9 ± 3.2
+ Solver-labeled random 3-SAT67.2 ± 1.971.9 ± 2.7
+ Target-aware (Ours)70.2 ± 0.879.3 ± 0.2

Our target-aware generation achieves the highest mean balanced accuracy and AUC among the compared augmentation strategies, demonstrating its effectiveness under a comparable generation-time budget. These results have been included in Appendix C.1 of the updated manuscript.

The rebuttal has provided some clarifications about the method contributions and comparisons. I don't have a strong opinion at this stage whether this paper should be accepted or rejected. Overall, I think the contribution could be higher if there are more direct comparisons between this and other datasets, as well as other data generation approaches.

AuthorsOpenReview ↗

Response to Reviewer 6kGT

We thank the reviewer for the feedback and for considering the additional evidence presented in our responses. Regarding comparisons with existing datasets and generation approaches, we would like to highlight the comparisons presented in the revised manuscript and throughout the discussion.

We have expanded the comparison with existing SAT datasets and generators, including NeuroSAT, G4SATBench, HardSATGEN, HardCore, and StructureSAT (Fu et al., 2025), considering their objectives, problem coverage, distributions, and data scale. We have also added quantitative comparisons with planted-SAT generators (1-hidden, 2-hidden, and q-hidden), evaluated generation quality and solver hardness across random and structured SAT families, and compared against alternative augmentation methods, including label-preserving perturbations and solver-labeled generation.

In particular, we compared our generator with q-hidden and the same generator without target conditioning (Generic) on two satisfiable-only SATLIB families. With generated-data augmentation, our method achieved the highest CSR on both rti (97.4% vs. 94.6% for Generic and 89.4% for q-hidden) and bms (96.1% vs. 94.3% and 89.2%, respectively), demonstrating the downstream benefit of target-aware generation.

We hope these results address your remaining concerns and that you will consider raising our score. We would also be happy to provide further clarifications while the discussion remains open.

Comments on the paper

1 comment

Dear reviewers,

As the authors have posted their responses, I would encourage you to actively parcitipate in the dicussion.

Thank you.

Best,

AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.