acceptodds
Under review as a conference paper at ICLR 2027

HyperGEN: A Masked Variational Hypergraph Framework for Hard UNSAT Instance Generation

Abstract

Realistic and challenging Boolean satisfiability (SAT) instances are essential for evaluating modern SAT solvers and training learning-based solver components, yet such instances are often scarce in application-specific domains. Existing SAT generators either rely on handcrafted structural priors or generate new formulas through predefined graph transformations, which do not explicitly model how clauses are formed. In this paper, we propose HyperGEN, a masked variational hypergraph framework for hard UNSAT instance generation. HyperGEN represents each formula in conjunctive normal form as a literal-clause hypergraph, where literals are vertices and clauses are hyperedges. It formulates instance generation as masked hyperedge reconstruction. HyperGEN employs a masked variational hypergraph autoencoder that combines a hypergraph neural network for structural encoding with latent variables, and reconstructs each masked clause through arity and membership prediction. Experiments on real-world SAT benchmarks show that HyperGEN consistently generates more challenging instances than existing generative baselines, generalizes to larger unseen instances without retraining, and provides effective data augmentation for downstream solver-runtime prediction.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Boolean satisfiability problem, Graph neural networks, Combinatorial optimization, SAT instance generation

Reviews

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

This work proposes a novel generative model for synthesizing hard UNSAT problems by masking non-core clauses in seed-instances and then training a variational graph autoencoder to generate new clauses to replace the masked ones.

Critical strengths
  1. The paper is exceptionally clear
  2. The paper's experimental procedure is generally in line with the previous work in the field
  3. The paper cites the appropriate related and previous work
Critical weaknesses

1.Some experimental details are left out 2. I don't think that its necessary to invoke hyper graphs for this work, the graph representation used is bi-partite, and the methodology seems to effectively build node-representations for the "hyper-edges" as well as for the literal nodes. 3. There are a couple experiments which might have enriched the paper.

The experimental clarifications I have asked for in the questions section should be simple enough to provide. I am assuming that no deal-breakers will come to light as the authors provide that information (and that they will indeed provide the asked for information). Given this assumption, I am rating this work as a clear accept. Of course, if these things are not provided the rating will necessarily decrease.

Questions for authors

Clarifications:

  1. What is the difference between your proposed graph-representation, which you call a hyper-graph, and the standard literal-clause graph used by a lot of the previous work you reference? While this may be a nitpick, it seems unnecessary to invoke hyper-graphs when the underlying representation is no different than the standard. As you say in line 186, H is the clause-literal graph. For example, “we construct a corrupted hypergraph G by masking the incidence pattern of selected clause hyperedges” would be more simply expressed as “we construct a corrupted graph G by masking out clauses”, which would just as aptly describe your procedure.
  2. How many distinct instances are in MDP and MP1 and MDP-Large?
  3. Table 1 - MP1 results: You indicate that 125% Avg. RH is better than 108.77%. Is this really the case? Presumably the goal is to generate instances which are as realistic as possible relative to the target distribution, as measured by hardness. Meaning that 100% is the ideal.
  4. How many instances were generated for augmentation in the downstream task experiment? Did you set a fixed computation budget, or a universal raw instance-count? When you do augmentation, do you only use training-instances as seeds for your generation procedure?

Nice-to-see new experiments I would ask for: 5. It would be nice to see sensitivity of performance improvement to the size of the augmentation set for Table 3. 6. It would be nice to see solver-specific hardness stats, or metrics on the solver-runtime-ranking distribution of your synthetic vs original datasets. 7. It would be nice to see mean/variance statistics on your rarity-predictor. Interpretable statistics for the membership predictor may be more complicated to present, but would also be nice.

6 comments
AuthorsOpenReview ↗

Response by Authors (1/2)

Thank you for the valuable comments. We provide our responses below and sincerely hope that our rebuttal could address your concerns.

Weaknesses:

W1: Some experimental details are left out.

We have added the relevant experimental details to the revised manuscript, including the number of distinct instances in each dataset, the number of generated instances for downstream task augmentation, the augmentation budget, and the selection of seed instances.

W2: I don't think that its necessary to invoke hyper graphs for this work, the graph representation used is bi-partite, and the methodology seems to effectively build node-representations for the "hyper-edges" as well as for the literal nodes.

Please refer to our response to Q1 below.

W3: There are a couple experiments which might have enriched the paper.

We have conducted the suggested experiments, including the sensitivity analysis of augmentation set size, solver-specific hardness stats, and statistical analysis of the arity predictor. The corresponding results have been added to the revised manuscript. Details are provided in our responses below.

Questions:

Q1: What is the difference between your proposed graph-representation, which you call a hyper-graph, and the standard literal-clause graph used by a lot of the previous work you reference? While this...

We would like to further clarify the motivation for adopting a hypergraph representation in our work and its relationship to the standard bipartite graph representation.

  • Mathematical modeling: From a mathematical modeling perspective, hypergraphs and bipartite graphs are distinct structures. We adopt the hypergraph formulation primarily to emphasize the modeling unit that naturally corresponds to our generation task. A clause is a set of multiple literals. Representing a clause as a hyperedge therefore directly captures the multi-way relationship among the literals that jointly constitute the clause.
  • Task motivation: From a task perspective, a key aspect of our method is learning and generating new clauses. This generation process can be formulated as a variable-cardinality hyperedge reconstruction problem. Specifically, predicting a clause amounts to determining whether a hyperedge connecting a subset of distinct literal vertices should exist. This formulation is adopted to emphasize the need to treat an entire clause as the fundamental unit of generation.
  • Representation choice: A hypergraph can be equivalently represented by its incidence bipartite graph. We do not claim that this representation introduces a fundamentally different incidence structure from the standard literal-clause bipartite graph. Rather, the hypergraph formulation provides a more natural and intuitive modeling abstraction, making the correspondence between the set-based structure of clauses and our generation objective more direct and explicit.

We have revised Section 4.1.1 to clarify the motivation for adopting the hypergraph formulation.

Q2: How many distinct instances are in MDP and MP1 and MDP-Large?

MP1 contains 567 instances, MDP contains 90 instances, and MDP-Large contains 7 instances. We have added the number of instances in each dataset to Appendix B.1 of the revised manuscript.

Q3: Table 1 - MP1 results: You indicate that 125% Avg. RH is better than 108.77%. Is this really the case? Presumably the goal is to generate instances which are as realistic as possible relative to the target distribution, as measured by hardness. Meaning that 100% is the ideal.

  • Expression clarification: Our goal, as described in the Abstract and Introduction, is to generate challenging SAT instances. The Introduction of the original manuscript used phrases such as "maintaining/preserving hardness" to convey that generated instances should be hard and challenging. These phrases were not intended to imply that the generated instances should have hardness levels close to those of the original instances. To quantify instance hardness, we use solver runtime, decisions, and conflicts as hardness measures, with the corresponding metrics of the original instances serving as normalization references.
  • Evaluation objective: An RH of 100% means that the generated instances have the same average metric values as the original instances. Under our evaluation setting, a higher RH indicates greater solving difficulty, which is also consistent with the explanation provided in the caption of Table 1. Therefore, the RH of 125.53% achieved by HyperGEN on MP1 is better than 108.77%, which is consistent with our objective of generating challenging UNSAT instances.

We have revised the relevant statements to improve the clarity of the manuscript.

AuthorsOpenReview ↗

Response by Authors (2/2)

Q4: How many instances were generated for augmentation in the downstream task experiment? Did you set a fixed computation budget, or a universal raw instance-count? When you do augmentation, do you only use training-instances as seeds for your generation procedure?

  • We generate 40 instances for augmentation in the downstream task experiment.
  • We set a universal raw instance-count. All augmentation methods use the same number of generated instances.
  • Data augmentation is performed only on the original instances in the training set, which serve as seeds for our generation procedure. Validation and test instances are never used as seeds or for data augmentation, and are kept separate from the training process.

We have added these details to Appendix B.2 of the revised manuscript to clarify the experimental setup.

Q5: It would be nice to see sensitivity of performance improvement to the size of the augmentation set for Table 3.

We have added a sensitivity analysis about the performance improvement to the size of the augmentation set. The results are in Table 1.

Table 1: Sensitivity of HyperGEN to augmentation set size on MP1. Training on original instances alone (augmentation size = 0) yields an MAE of 1376.53 s.

Augmentation set size3240485664
MAE of Runtime Prediction (s)1200.951163.021279.911255.151208.75

We have added the sensitivity analysis to Appendix C.5 of the revised manuscript to enrich the paper.

Q6: It would be nice to see solver-specific hardness stats, or metrics on the solver-runtime-ranking distribution of your synthetic vs original datasets.

We have added the solver-specific hardness stats, including runtime, decisions and conflicts. The results are presented in Table 2 below. We have also included these results in Appendix C.6 of the revised manuscript.

Table 2: Solver-specific hardness of HyperGEN across different datasets. Values in parentheses indicate the relative hardness (RH), expressed as a percentage of the corresponding mean value for the original instances under the same solver.

DatasetSolverRuntime (s)DecisionsConflictsAvg. RH (%)
MDPKISSAT-NEW39.81 (98.22%)2880765.06 (98.70%)2213111.44 (98.15%)98.35
MDPMOSS46.74 (92.68%)3164250.38 (91.95%)2574114.06 (92.28%)92.30
MDPUCB47.95 (92.55%)3228434.46 (92.92%)2616606.82 (92.69%)92.72
MDPESA49.11 (96.99%)3277109.92 (96.31%)2658631.80 (96.16%)96.49
MDPMAB-GB48.50 (93.48%)3228216.74 (94.14%)2625765.58 (94.22%)93.94
MP1KISSAT-NEW13.76 (117.00%)614086.92 (103.80%)387548.00 (105.88%)108.89
MP1MOSS72.63 (135.06%)2742732.50 (120.30%)1825156.24 (121.37%)125.58
MP1UCB71.86 (128.34%)2716149.08 (116.54%)1800661.02 (116.52%)120.46
MP1ESA74.43 (150.43%)2790849.48 (132.34%)1866759.86 (134.73%)139.17
MP1MAB-GB72.77 (131.12%)2724917.96 (116.77%)1815453.54 (118.79%)122.23
MDP-LargeKISSAT-NEW221.37 (93.35%)11264950.34 (96.43%)8482680.69 (94.94%)94.90
MDP-LargeMOSS323.75 (84.13%)13645409.40 (88.33%)10540598.89 (88.18%)86.88
MDP-LargeUCB328.11 (102.46%)13804143.43 (97.73%)10661508.20 (98.10%)99.43
MDP-LargeESA354.32 (117.90%)14432577.63 (107.30%)11205427.80 (109.08%)111.43
MDP-LargeMAB-GB338.29 (82.66%)14054590.43 (87.36%)10883484.20 (87.75%)85.92

Q7: It would be nice to see mean/variance statistics on your rarity-predictor. Interpretable statistics for the membership predictor may be more complicated to present, but would also be nice.

We have added the mean and variance statistics of the arity predictor to Appendix C.7 of the revised manuscript. Specifically, for MP1, the mean predicted clause arity is 2.59, with a population variance of 8.73×10−38.73 \times 10^{-3}; for MDP, the corresponding values are 2.50 and 1.96×10−41.96 \times 10^{-4}, respectively. We do not provide additional statistics for the membership predictor, as interpretable statistics for this predictor are more complicated to present.

Reviewer_61xYOpenReview ↗

runtime hardness metric

With respect to runtime hardness, I don't find the authors' answer particularly satisfying. In the literature AND in the authors' own work, a specific empirical motivation is given for why we want to generate SAT problems. In the text's opening paragraph: " This creates a growing need for generative methods that can produce realistic and challenging SAT instances for solver evaluation and data augmentation." Such a motivation doesn't simply require arbitrarily hard instances, it requires realistically hard instances. I'm not sure why the authors are so resistant to this point, given that even the ``maintain hardness'' objective would still have the proposed method as the strongest performing one in 2/3 datasets on RH, and anyways it provides better downstream performance on runtime prediction.

Reviewer_FinyOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes HyperGEN for generating new hard UNSAT instances from existing hard UNSAT CNF formulas. It represents positive and negative literals as nodes and clauses as hyperedges. During masked reconstruction, a known UNSAT core is preserved, and a variational hypergraph autoencoder reconstructs non-core clauses. The decoder predicts clause arity and literal membership separately, and the full pipeline also applies pre-generation scrambling and hardness refinement using a core detector.

Experiments are conducted across MP1, MDP, and MDP-Large. MDP-Large belongs to the same benchmark family as MDP, and the authors evaluate it using the model trained on MDP without retraining. Hardness is measured by runtime, decisions, and conflicts averaged over five SAT solvers. The reported Avg. RH is 125.53% on MP1, 94.62% on MDP, and 94.94% on MDP-Large. On MP1, augmenting the data with HyperGEN-generated instances reduces SATzilla's runtime-prediction MAE by 15.51% relative to using the original data alone. All these results support the significance of the full pipeline, although it seems that they do not isolate the contribution of the learned clause reconstruction model.

Critical strengths
  1. The full pipeline achieves strong results across all three benchmarks. HyperGEN reports Avg. RH values of 94.62% on MDP, 125.53% on MP1, and 94.94% on MDP-Large, outperforming all baselines with available results. I also appreciate that the evaluation covers five SAT solvers and considers runtime, decisions, and conflicts.

  2. The method accounts for SAT-specific constraints and is evaluated on a downstream task. Preserving the original UNSAT core ensures that the resulting formula remains UNSAT. During clause generation, the procedure samples variables and retains only one polarity for each variable, avoiding clauses that contain both a variable and its negation. HyperGEN also retains nearly the original hardness on MDP-Large without retraining, and augmentation reduces runtime-prediction MAE by 15.51% on MP1.

Critical weaknesses
  1. The paper lacks ablations that isolate the learned generator, and scrambling may confound the diversity results. The default generation ratio is η=0.01\eta=0.01. Under the procedure in Section 4.3, the reconstruction budget is at most about 1% of the original clauses. If a candidate is repeatedly rejected as a duplicate, the original clause is retained, so the actual replacement rate may be lower. The known UNSAT core is preserved throughout, and the full pipeline also includes scrambling and hardness refinement. Tables 1 and 2 therefore show that the overall pipeline produces hard instances, but they do not show whether the learned clause distribution is better than a simpler non-core clause editing strategy.

    • I see that Table 5 reports clause change rates of 90.41% on MP1 and 96.41% on MDP. The paper says that clause Jaccard similarity ignores clause order and literal order within each clause, but it does not explain whether either metric is computed after undoing variable permutations and phase flips and aligning variables with the original formula. It also does not specify how the clause change rate matches clauses after core-clause permutation. Scrambling can change the surface form of many clauses without creating structural differences after equivalent transformations are aligned. It seems that the authors do not separate the effects of scrambling, VHAE reconstruction, and refinement, or report diversity after aligning the variables. Therefore, current hardness and diversity results do not show the independent effect of the learned generator.
  2. The probabilistic formulation and the technical contribution over prior work need clearer definitions. Equation 1 gives a standard conditional ELBO, while training uses a weighted arity MSE, class-balanced per-literal BCE, and a KL term with β≠1\beta \ne 1. At generation time, the arity prediction is rounded, variables are sampled without replacement according to their scores, and the polarity with the higher score is selected. I think the paper does not explicitly define normalized conditional distributions pθ(kj∣zj,G~)p_\theta(k_j\mid z_j,\widetilde G) and pθ(H:,j∣kj,zj,G~)p_\theta(H_{:,j}\mid k_j,z_j,\widetilde G) that match these steps. It also does not clarify whether Eq.8 is the exact negative ELBO for the stated model or a surrogate objective motivated by variational modeling, this might be a gap in the model definition.

    • I also have some questions about novelty. DGMH (Zuo et al., Information Sciences, 2023) already explores hyperedge generation through hyperedge-size prediction and node selection, which seems quite similar to HyperGEN's approach. HeteHG-VAE (Fan et al., TPAMI, 2022) also uses variational hypergraph modeling, although it focuses on link prediction. Neither work directly targets SAT instance generation, so I think comparing with HardSATGEN and HardCore as task-specific baselines is reasonable. Still, I'd like the authors to explain more clearly what is technically new in HyperGEN, especially in its clause reconstruction mechanism, and provide some evidence that these design choices are actually helpful.
Questions for authors

The following questions show the important aspects that affect my assessment of this paper:

  1. Controlled ablations: Could you compare the following settings on the same input formulas, with the same retained UNSAT cores and comparable scrambling seeds: (a) scrambling only, (b) scrambling followed by simple random reconstruction or non-core clause reconstruction matched to empirical clause-length and literal-frequency statistics, and (c) scrambling followed by VHAE reconstruction? For (b) and (c), please also report results with and without hardness refinement. For a fair comparison, could you use the same target clauses and editing budget where possible? It would also help to see how many clauses were actually replaced, how many edits were made during refinement, and how solver hardness changed at each stage. These would help separate the contributions of the individual components without imposing irrelevant editing or refinement requirements on the scrambling-only and no-refinement settings.

  2. Diversity metrics: Table 5 states that clause Jaccard similarity ignores clause order and literal order within a clause. Please explain how clauses are matched for the clause change rate, especially after core-clause permutation, and whether both metrics are computed after undoing variable permutations and phase flips and aligning variables with the original formula. Could you report diversity after scrambling, after VHAE reconstruction, and after refinement, including structural differences after accounting for equivalent scrambling? With the default settings, VHAE reconstructs at most about 1% of the clauses, and the actual replacement rate may be lower. How much of the reported change rate above 90% remains after equivalent scrambling is removed?

  3. Probabilistic model: I'm having some trouble connecting the probabilistic formulation in Eq.5 to the actual training and generation process. Could the authors clarify how the conditional distributions for arity and membership are defined, and how they relate to the weighted MSE, class-balanced BCE, and KL weight β≠1\beta \ne 1? I'm also curious how the rounding, sampling without replacement, and polarity selection fit into these distributions. Is Eq.8 the exact negative ELBO, or is it more of a practical surrogate loss? If it's the latter, I think the paper should make this clearer.

  4. Novelty and necessity: I'm still not quite sure what is new about the clause reconstruction mechanism. DGMH (Zuo et al., Information Sciences, 2023) already uses hyperedge-size prediction and node selection, which seems similar to HyperGEN's arity and membership predictors. HeteHG-VAE (Fan et al., TPAMI, 2022) also uses variational hypergraph modeling, although it focuses on link prediction rather than SAT generation. I think HardSATGEN and HardCore are suitable baselines for this task, but I'd also like to see what the VHAE itself contributes. Could the authors compare it with a matched non-variational decoder or a simpler generator to show why these design choices are useful?

  5. Cost and reproducibility: I also have a few questions about the cost of the full pipeline. Appendix A.4 mentions using CaDiCaL and DRAT-trim to obtain cores for training the core detector, but how is the initial UNSAT core obtained during generation? Is this cost included in the evaluation? I couldn't find the actual values of the scrambling ratios ρvar\rho_{\mathrm{var}}, ρclause\rho_{\mathrm{clause}}, and ρphase\rho_{\mathrm{phase}} defined in Appendix A.3, or the refinement threshold and stopping rule. Could the authors provide these details? I'd also appreciate a breakdown of the runtime for core extraction, preprocessing, scrambling, VHAE reconstruction, and refinement, along with how many clauses are typically modified during refinement.

4 comments
AuthorsOpenReview ↗

Response by Authors (1/2)

Thank you for the valuable comments. We provide our responses below and sincerely hope that our rebuttal could address your concerns.

Weakness 1.

Please refer to our responses to Q1 and Q2 below.

Weakness 2.

Please refer to our responses to Q1, Q3, and Q4 below.

Q1: Controlled ablations.

We have conducted controlled ablation studies, and the results are presented in Table 1. We compare the following settings on the same input formulas, with the same retained UNSAT cores and comparable scrambling seeds: (a) scrambling only, (b) scrambling followed by non-core clause reconstruction matched to empirical clause-length and literal-frequency statistics, and (c) scrambling followed by VHAE reconstruction. For (b) and (c), we also report results with and without hardness refinement. Both reconstructors use the same target clauses and requested reconstruction budget.

Table 1: Controlled ablations of scrambling, clause reconstruction, and hardness refinement on MDP. Parenthesized values are relative hardness (RH) relative to Original. Avg. RH averages the runtime, decisions, and conflicts RH values. HyperGEN combines scrambling, VHAE reconstruction, and hardness refinement.

ConfigurationRuntimeDecisionsConflictsAvg. RH
Original49.063,333,326.042,683,798.68100.00%
Scrambling46.06 (93.88%)3,135,862.52 (94.08%)2,528,212.07 (94.20%)94.05%
Scrambling + empirical reconstruction0.16 (0.32%)16,356.64 (0.49%)15,250.38 (0.57%)0.46%
Scrambling + empirical reconstruction + refinement40.48 (82.52%)2,701,433.79 (81.04%)2,184,887.96 (81.41%)81.66%
Scrambling + VHAE0.34 (0.69%)28,195.84 (0.85%)24,553.45 (0.91%)0.82%
HyperGEN46.42 (94.62%)3,155,755.31 (94.67%)2,537,645.94 (94.55%)94.62%
  • Hardness refinement increases the Avg. RH of VHAE-reconstructed instances from 0.82% to 94.62%, highlighting its importance. This is because newly generated clauses may introduce small UNSAT cores, making the resulting instances easier to solve. With refinement, VHAE reconstruction achieves an Avg. RH 12.96 percentage points higher than empirical reconstruction, supporting the benefit of learned reconstruction within the complete pipeline. Overall, these results support the effectiveness of the complete HyperGEN pipeline.

  • Empirical reconstruction and VHAE replace an average of 31.50 clauses per instance. Refinement performs an average of 254.70 edits per instance. The reconstruction budget is 1% of the original clauses. The actual reconstruction rate of HyperGEN is approximately 0.9989% of all clauses.

We have added the controlled ablation studies to Appendix C.9 of the revised manuscript.

Q2: Diversity metrics.

1. Metric interpretation: Both the clause change rate and clause Jaccard similarity of the original manuscript compare the full-pipeline generated instances directly with the original instances. Thus, the reported metrics include the effects of scrambling, without undoing variable permutations or phase flips.

  • The clause change rate uses a position-based comparison: the i-th clause in the generated instance is compared with the i-th clause in the original instance, with each clause treated as a set of signed literals. Thus, this metric ignores literal order within clauses but remains sensitive to clause order.
  • Clause Jaccard similarity compares clause sets without positional matching, ignoring both clause order and literal order within each clause.

2. Stage-wise diversity: We have added the results of the clause change rate, clause Jaccard similarity, and clause change rate after undoing perturbations at each stage, including after scrambling, VHAE reconstruction, and refinement. The results are presented in Table 2.

Table 2: Stage-wise diversity of HyperGEN. Clause change rate and clause Jaccard similarity are reported after scrambling, VHAE reconstruction, and refinement. The last column reports the clause change rate after undoing the scrambling transformations. Values are mean ± sample standard deviation.

StageClause Change RateClause Jaccard SimilarityClause Change Rate After Undoing Perturbations
After Scrambling95.54 ± 1.000.0418 ± 0.00970.00 ± 0.00
After VHAE Reconstruction95.65 ± 1.000.0412 ± 0.00971.00 ± 0.01
After Refinement96.41 ± 0.940.0370 ± 0.00948.04 ± 0.45

We have clarified the diversity metrics and added further diversity analysis in Appendix C.10 of the revised manuscript.

AuthorsOpenReview ↗

Response by Authors (2/2)

Q3: 3. Probabilistic model.

1. Definition of conditional distributions: Eq. (5) factorizes the decoder distribution parameterized by θ\theta into a conditional arity distribution and a conditional membership distribution given the arity.

  • For the arity distribution, given the latent variable zjz_j and the masked graph G~\widetilde{\mathcal{G}}, the continuous output of the arity predictor is rescaled to the original arity range and rounded to obtain the clause arity kjk_j.
  • For the membership distribution, given the clause arity kjk_j, the conditional distribution of the literal-membership vector H:,jH_{:,j} for clause jj is induced by the weighted sampling of variables without replacement and the subsequent polarity selection, as described in the main text.

2. Relationship between conditional distributions and training losses: During training, weighted MSE and class-balanced BCE are used to train the arity and membership predictors, respectively. During generation, their outputs determine the two conditional distributions in Eq.5 through the rounding, weighted sampling without replacement, and polarity selection procedures described above. In addition, latent variables are sampled from the Gaussian variational posterior during training, whereas they are sampled from the standard Gaussian prior during generation. The KL term regularizes the variational posterior toward the prior, while β\beta controls the relative strength of this regularization with respect to the reconstruction losses.

3. Clarification of Eq.8: Based on Points 1 and 2 above, Eq.8 is a practical surrogate loss inspired by variational modeling, rather than an exact negative ELBO.

We have revised the relevant statements to improve the clarity of the manuscript.

Q4: Novelty and necessity.

We compare HyperGEN with HeteHG-VAE and DGMH in terms of variational modeling, reconstruction targets, and generative mechanisms.

  • Variational modeling: Both HeteHG-VAE and HyperGEN employ variational autoencoders (VAEs) to learn latent distributions through variational inference, whereas DGMH adopts an autoencoder-based generative framework without variational inference.
  • Reconstruction target: HeteHG-VAE reconstructs the complete node–hyperedge incidence matrix. DGMH samples new hyperedges from the learned generative distribution. In contrast, HyperGEN reconstructs masked clauses from the masked hypergraph.
  • Generative mechanism: HeteHG-VAE predicts node–hyperedge associations through the inner product of node and hyperedge embeddings. DGMH performs hyperedge generation by sampling latent variables and predicting hyperedge sizes and node compositions. HyperGEN performs conditional clause reconstruction by learning latent distributions from the original hypergraph and reconstructing masked clauses conditioned on the masked hypergraph through Arity prediction and Membership prediction.

Overall, HyperGEN formulates SAT instance generation as a masked conditional generation problem. It employs a variational hypergraph autoencoder to learn latent representations and leverages the masked hypergraph for clause generation. By explicitly modeling clause arity and literal membership and incorporating SAT-specific structural constraints, HyperGEN provides a structured approach to generating SAT instances.

Please refer to our response to Q1 for the comparison with an alternative generator.

Q5: Cost and reproducibility.

  • Before generating new instances, we use CaDiCaL and DRAT-trim to extract the initial UNSAT core from each input seed formula. The initial core extraction time is excluded from the runtime reported in the hardness evaluation. This runtime measures the time taken by the evaluated solvers to solve the original or generated formulas.
  • We report a breakdown of the runtime for core extraction, preprocessing, scrambling, VHAE reconstruction, and refinement in Table 3.

Table 3: Amortized runtime per generated instance for HyperGEN on MDP. Core extraction and preprocessing costs are amortized over the five variants generated from each seed formula.

StageCore extractionPreprocessingScramblingVHAE reconstructionRefinement
Time(s)41.110.970.102.616.12
  • The scrambling ratios are set to ρvar=0.3\rho_{\mathrm{var}} = 0.3, ρclause=0.3\rho_{\mathrm{clause}} = 0.3, and ρphase=0.2\rho_{\mathrm{phase}} = 0.2. The refinement threshold is set to 0.1. Hardness refinement uses a fixed iteration budget. Specifically, the number of refinement iterations for each instance is set to the number of clauses outside the initial UNSAT core.

We have added the runtime breakdown and additional experimental details to Appendices C.8 and B.2 of the revised manuscript. Please refer to our response to Q1 for the number of modified clauses.

Reviewer_FinyOpenReview ↗

Thanks for your response, and one more question

Thanks to the authors for the detailed response and the additional experiments, the new ablations and diversity analysis have cleared up many of my concerns. :)

Hmm, I still have one question about the variational design: the empirical reconstruction baseline is helpful, but I'm curious whether a simpler non-variational learned decoder could achieve similar results with the same refinement procedure. I think this would help me better understand what the variational component actually adds.

I'm more positive about the paper now. If the authors can address this remaining concern, I'd be happy to raise my score to Weak Accept.

AuthorsOpenReview ↗

Response to the concern

We sincerely appreciate your prompt reply and the acknowledgment of our response. Below we respond to your remaining concern.

We have added a simpler non-variational learned decoder with the same refinement procedure as in HyperGEN. The additional results are included below.

Table 1: Controlled ablations of scrambling, clause reconstruction, and hardness refinement on MDP. Parenthesized values are relative hardness (RH) relative to Original. Avg. RH averages the runtime, decisions, and conflicts RH values. HyperGEN combines scrambling, VHAE reconstruction, and hardness refinement.

ConfigurationRuntimeDecisionsConflictsAvg. RH
Original49.063,333,326.042,683,798.68100.00%
Scrambling46.06 (93.88%)3,135,862.52 (94.08%)2,528,212.07 (94.20%)94.05%
Scrambling + empirical reconstruction0.16 (0.32%)16,356.64 (0.49%)15,250.38 (0.57%)0.46%
Scrambling + empirical reconstruction + refinement40.48 (82.52%)2,701,433.79 (81.04%)2,184,887.96 (81.41%)81.66%
Scrambling + non-variational reconstruction + refinement42.71 (87.06%)2,946,670.56 (88.40%)2,380,276.04 (88.69%)88.05%
Scrambling + VHAE0.34 (0.69%)28,195.84 (0.85%)24,553.45 (0.91%)0.82%
HyperGEN46.42 (94.62%)3,155,755.31 (94.67%)2,537,645.94 (94.55%)94.62%

As shown in Table 1, compared with non-variational reconstruction under the same refinement setting, VHAE reconstruction improves the Avg. RH from 88.05% to 94.62%, an increase of 6.57 percentage points. These results support the benefit of variational learned reconstruction within the complete pipeline.

We hope this response could help address your remaining concern. Your valuable feedback is eagerly anticipated, and we look forward to hearing from you soon.

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

The authors use a hypergraph-level model to make hard SAT instances and show that sat solvers from prev years do not perform well on it. They use the SAT contests + a popular portfolio method called SATzilla from 2008 as the methods of choice, and the latest SAT contests they use are from 2022. The central claim is that the random hard methods they can find are meaningful and stress test these solvers, with some tests for downstream generalization + generalizing to larger families.

Critical strengths

I found the idea of using a hypergraph-based method to generate new hard SAT instances a fairly new take on the topic. There is also some good-to-see tests of downstream relevance.

Critical weaknesses

I find the thrust of the paper deeply confusing. Firstly, the existence of hard problems is obviously not surprising given that this is SAT. There cannot be an universal solver that solves all SAT problems efficiently, and this is proven. Therefore, the existence of these problems or generating them is not meaningful till one can convince the solver maker that these new synthetic problems have equal value as the problems the solver was designed to be good on. This is not tested thoroughly. Generalizing to downstream / SATzilla is not convincing because the SAT contest runs every year (for some reason all the recent SAT contests are mostly ignored) and even SATzilla is from 2008.

Questions for authors
  • Please see weaknesses. In particular, given that there cannot be a theoretically optimal SAT solver for everything anyway, the reasons to care about these synthetic instances is purely empirical, thus please justify the use of a (mostly) outdated suite of benchmark SAT solvers and methods.
4 comments
AuthorsOpenReview ↗

Response by Authors (1/3)

Thank you for the valuable comments. We provide our responses below and sincerely hope that our rebuttal could address your concerns.

Weaknesses

We would like to further clarify the motivation of this work and provide additional experimental evidence of the practical utility of HyperGEN. This work aims to address the scarcity of challenging SAT instances in specific application domains. SAT instance generation has been an active research area. G2SAT [1], HardSATGEN [2], MixSATGEN [3], and HardCore [4] have all investigated generating new formulas from existing SAT instances and using the generated data for downstream tasks, such as solver hyperparameter tuning and runtime prediction. Building on this line of research, we propose a clause reconstruction framework for instance generation and evaluate the practical utility of the generated instances through hardness evaluation and downstream experiments.

1. Clarification of the solver version and SATzilla setup

We apologize for the ambiguity regarding the solver version and downstream methodology.

  • “KISSAT-NEW” refers to the official Kissat v4.0.4 release (October 2025), not a SAT Competition 2022 version.
  • Our downstream runtime prediction experiment follows the methodology of HardCore [4]. We directly use its publicly available MLP-based regression implementation with 33-dimensional SATzilla-style features, rather than the original SATzilla (Xu et al., 2008) model.

In the revised manuscript, we have clarified the solver version and SATzilla setup, and updated the relevant references.

To further assess the value of the generated instances, we evaluate them from three complementary perspectives: structural statistics examine whether the generated instances preserve relevant structural characteristics of the original formulas; evaluation with recent SAT solvers assesses whether the generated instances are challenging; and downstream prediction and solver hyperparameter tuning experiments examine whether the generated data can support learning tasks and solver configuration optimization.

2. Additional evaluation with recent SAT solvers

  • We have supplemented our evaluation with two recent SAT solvers: satsuma-iter+kissat, the winner of the Main track at SAT Competition 2026 [5], and CaDiCaL 3, a non-Kissat solver from SAT Competition 2026 [5]. We evaluate both the generated instances and the original benchmarks using these two solvers. The results are presented in Tables 1 and 2.
  • The results show that HyperGEN consistently generates more challenging instances than the compared generation methods across both newly added solvers. This extends the original evaluation to recent competition-level solvers and provides additional evidence that the generated instances are challenging to solve.

Table 1: Hardness evaluation using satsuma-iter+kissat. Parenthesized values are relative hardness (RH) relative to Original. Avg. RH averages the runtime, decisions, and conflicts RH values. OOM indicates an out-of-memory failure.

DatasetMethodRuntime (s) ↑Decisions ↑Conflicts ↑Avg. RH ↑
MDPOriginal40.702,918,816.102,254,905.20100.00%
MDPHardSATGEN28.74 (70.60%)2,192,534.54 (75.12%)1,710,862.18 (75.87%)73.86%
MDPHardCore7.55 (18.55%)565,681.80 (19.38%)456,313.70 (20.24%)19.39%
MDPG2SAT0.00 (0.00%)0.00 (0.00%)0.00 (0.00%)0.00%
MDPMixSATGEN0.22 (0.54%)21,111.34 (0.72%)17,527.66 (0.78%)0.68%
MDPHyperGEN39.17 (96.23%)2,845,255.70 (97.48%)2,196,962.68 (97.43%)97.05%
MP1Original12.86627,556.10389,783.90100.00%
MP1HardSATGEN12.27 (95.44%)605,734.76 (96.52%)376,696.94 (96.64%)96.20%
MP1HardCore13.36 (103.92%)636,512.30 (101.43%)400,382.92 (102.72%)102.69%
MP1G2SAT0.00 (0.00%)0.00 (0.00%)0.00 (0.00%)0.00%
MP1MixSATGENOOMOOMOOM---
MP1HyperGEN13.71 (106.61%)649,207.48 (103.45%)409,962.02 (105.18%)105.08%
MDP-LargeOriginal235.8711,682,470.438,934,722.00100.00%
MDP-LargeHardSATGEN25.88 (10.97%)1,807,763.09 (15.47%)1,414,249.14 (15.83%)14.09%
MDP-LargeHardCore31.37 (13.30%)1,941,573.00 (16.62%)1,490,189.80 (16.68%)15.53%
MDP-LargeG2SAT0.00 (0.00%)0.00 (0.00%)0.00 (0.00%)0.00%
MDP-LargeMixSATGEN0.51 (0.21%)40,360.43 (0.35%)32,104.51 (0.36%)0.31%
MDP-LargeHyperGEN210.72 (89.34%)11,341,038.77 (97.08%)8,518,207.09 (95.34%)93.92%
AuthorsOpenReview ↗

Response by Authors (2/3)

Table 2: Hardness evaluation using CaDiCaL 3.

DatasetMethodRuntime (s) ↑Decisions ↑Conflicts ↑Avg. RH ↑
MDPOriginal54.492,488,639.202,014,258.50100.00%
MDPHardSATGEN37.31 (68.47%)1,847,299.82 (74.23%)1,512,742.58 (75.10%)72.60%
MDPHardCore8.97 (16.46%)484,026.10 (19.45%)405,844.26 (20.15%)18.69%
MDPG2SAT0.00 (0.00%)0.00 (0.00%)0.02 (0.00%)0.00%
MDPMixSATGEN0.22 (0.41%)18,488.70 (0.74%)16,099.46 (0.80%)0.65%
MDPHyperGEN54.91 (100.76%)2,503,851.78 (100.61%)2,032,889.36 (100.92%)100.77%
MP1Original16.77695,266.00443,223.20100.00%
MP1HardSATGEN16.88 (100.66%)691,109.88 (99.40%)446,322.98 (100.70%)100.26%
MP1HardCore18.14 (108.15%)722,444.28 (103.91%)466,538.46 (105.26%)105.77%
MP1G2SAT0.00 (0.00%)0.00 (0.00%)0.00 (0.00%)0.00%
MP1MixSATGENOOMOOMOOM---
MP1HyperGEN18.92 (112.80%)749,418.18 (107.79%)485,815.74 (109.61%)110.07%
MDP-LargeOriginal280.3711,233,678.008,495,888.29100.00%
MDP-LargeHardSATGEN26.94 (9.61%)1,576,379.69 (14.03%)1,273,314.26 (14.99%)12.88%
MDP-LargeHardCore34.16 (12.18%)1,736,741.46 (15.46%)1,360,641.74 (16.02%)14.55%
MDP-LargeG2SAT0.00 (0.00%)0.00 (0.00%)0.00 (0.00%)0.00%
MDP-LargeMixSATGEN0.57 (0.20%)35,573.11 (0.32%)30,335.06 (0.36%)0.29%
MDP-LargeHyperGEN266.63 (95.10%)10,896,824.03 (97.00%)8,190,426.97 (96.40%)96.17%

3. Additional downstream task: solver hyperparameter tuning

Following the solver hyperparameter tuning task and experimental setup in HardSATGEN [2] and MixSATGEN [3], we have added this downstream task for CaDiCaL 3 to evaluate the practical utility of generated instances for solver configuration optimization. We adopt a Bayesian optimizer HEBO [6] to tune the solver. The tuned hyperparameters include reduce interval, restart interval, and score factor. The detailed experimental settings are provided in the revised manuscript. The best runtime results obtained with the tuned hyperparameters are presented in Table 3. The generated instances by the HyperGEN bring a solver runtime reduction of over 20% to the solver. These results suggest the practical utility of the generated instances.

Table 3: Results of SAT solver hyperparameter tuning for specific data. TgT_g: average runtime on generated instances; TtT_t: average runtime on test instances. Gain is the percentage reduction in TtT_t relative to Default.

MethodHyperparametersTgT_g (s)TtT_t (s)Gain
Default(25, 2, 950)N/A51.47N/A
HyperGEN(10, 1481, 988)40.4639.5723.12%

4. Structural properties analysis

We have further added a comparison of structural statistics between the generated and original instances for reference. We have replicated the experiment that was performed in the HardSATGEN [2]. We report the clustering on the variable-incidence graph and modularity on four graph representations. The results are presented in Table 4.

Table 4: Results of graph structural statistics of generated instances.

MethodVIG clust.mod. VIGmod. LIGmod. VCGmod. LCG
Original0.46450.66990.64640.80510.7997
HardSATGEN0.46350.66710.64460.80370.7985
HardCore0.46210.65320.64110.80010.7950
G2SAT0.08770.73600.89200.79480.9145
HyperGEN0.46230.66140.64240.80280.7973
HyperGEN closeness rank22222

For these statistics, HyperGEN achieves values that are relatively close to those of the original instances, with slightly larger deviations than HardSATGEN. These results suggest that HyperGEN preserves relevant structural characteristics of the original formulas. However, as pointed out in HardCore [4], hardness metrics provide a more meaningful assessment than structural statistics alone, as instances that preserve structural properties but remain easy to solve may still differ substantially from their original instances in solver-relevant aspects. Therefore, our primary objective is to generate challenging instances rather than to match the modularity statistics of the original instances.

AuthorsOpenReview ↗

Response by Authors (3/3)

Overall, these additional evaluations provide further evidence that HyperGEN can generate instances with relevant structural characteristics and solving difficulty, while also demonstrating their practical utility for downstream tasks such as runtime prediction and solver hyperparameter tuning. We have included the corresponding experimental results in Appendices C.3 and C.4 of the revised manuscript.

Questions

Please refer to our response in the Weaknesses section above.

References:

[1] You J, Wu H, Barrett C, et al. G2sat: Learning to generate sat formulas[J]. Advances in neural information processing systems, 2019, 32.

[2] Li Y, Chen X, Guo W, et al. Hardsatgen: Understanding the difficulty of hard sat formula generation and a strong structure-hardness-aware baseline[C]//Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023: 4414-4425.

[3] Chen X, Li Y, Wang R, et al. Mixsatgen: Learning graph mixing for sat instance generation[C]//International Conference on Learning Representations. 2024: 23185-23201.

[4] Cotnareanu J, Zhang Z, Zhen H L, et al. HardCore generation: Generating hard UNSAT problems for data augmentation[J]. Advances in Neural Information Processing Systems, 2024, 37: 62409-62431.

[5] FAZEKAS K, HEULE M J H, ISER A. Proceedings of SAT Competition 2026: Solver and Benchmark Descriptions[C]. Vienna: TU Wien, 2026.

[6] Cowen-Rivers A I, Lyu W, Tutunov R, et al. Hebo: Pushing the limits of sample-efficient hyper-parameter optimisation[J]. Journal of Artificial Intelligence Research, 2022, 74: 1269-1349.

AuthorsOpenReview ↗

It is our pleasure to discuss with you.

Dear Reviewer 9fmX,

We deeply appreciate your time and valuable comments. We sincerely hope that our response could properly address your concerns. If you have any further concerns, we are more than happy to discuss with you and keep improving this work.

Best,

Authors

Comments on the paper

1 comment
Area_Chair_9xnhOpenReview ↗

Author-Reviewer discussion reminder

Dear Reviewers,

Please spend some time reading the rebuttal and indicate whether the authors have clarified your concerns. Please do so before Nov 18 AoE to give the authors the chance to further clarify.

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.