acceptodds
Under review as a conference paper at ICLR 2027

Transfer Learning from Foundational Optimization Embeddings to Unsupervised SAT Representations

Abstract

Foundational optimization embeddings, such as FORGE, have recently emerged as powerful pre-trained representations for mixed-integer programming (MIP) problems. Prior work showed these embeddings can transfer across optimization problem domains while reducing reliance on solver-generated labels. In this work, we investigate whether such representations generalize beyond optimization to decision problems, focusing on Boolean satisfiability (SAT). We adapt the foundational optimization architecture to SAT by mapping conjunctive normal form (CNF) formulas into the same bipartite constraint–variable graph representation used for MIPs. This enables us to study both direct transfer of MIP-pretrained representations and FORGE-SAT, a variant of the same architecture pretrained directly on SAT instances. Our results show that these embeddings capture structural regularities in SAT instances and support unsupervised tasks such as instance clustering and distribution identification. Beyond clustering, we analyze what the learned discrete codewords encode by generating semantic descriptions, validating them on held-out nodes, and testing whether the same interpretations transfer across SAT difficulty levels. We further evaluate the downstream utility of these representations for satisfiability prediction under held-out distribution shift, showing that frozen FORGE-SAT representations provide useful task-relevant signal. Our findings are a step toward a unified representational framework across optimization and decision problems.

Primary area:
transfer learning, meta learning, and lifelong learning
Keywords:
transfer learning, MIP, SAT, GNN, representation learning, interpretability

Reviews

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

This paper investigates transferring the FORGE representation-learning framework from mixed-integer programming (MIP) to Boolean satisfiability (SAT). Motivated by their shared constraint–variable graph structure and the cost of solver-generated labels, the authors explore direct MIP-pretrained transfer, SAT-specific feature adaptation, and SAT-native unsupervised pretraining. Experiments show that MIP-pretrained embeddings retain structural information, while FORGE-SAT achieves the highest clustering NMI and provides frozen representations with average cross-distribution prediction performance comparable to baselines.

Critical strengths
  1. The paper addresses a question about reusing unsupervised representations across optimization and decision problems. Such reuse could reduce dependence on task-specific training and solver-generated labels.
Critical weaknesses
  1. The technical contribution is limited. Most of proposed techniques reuse the existing FORGE, including model architecture and pretraining tasks.
  2. The benefit of transferring MIP-pretrained model to SAT is not clear enough. In Table 1, Forge-SAT, trained from scratch on SAT, achieves better NMI than the others.
  3. The existing downstream tasks provide limited evidence of practical utility for SAT solving. It only considers satisfiability prediction.
Questions for authors
  1. Please clarify the above weaknesses.
  2. Can the learned representions enhance SAT solver? Please give an example or explanation. If so, what’s the runtime overhead to obtain the embeddings? Does it account for a substantial fraction of the total solving time?
1 comment

Thank you for your review. We appreciate that you recognize the value of reusing unsupervised representations across optimization and decision problems. We address your concerns below.

[W1] Technical contribution. We intentionally reused FORGE to explore what transfers, without labels, between two very different problem classes. The contribution is the evidence that this reuse works to some extent, and we additionally characterize how:

  • FORGE-SAT, which we consider as an architectural-transfer, gives the best clustering in Table 1 (0.81 NMI vs 0.74 for STATIC-SAT and 0.54 for random weights). These values already show cross-dataset generalization (since pretraining and test datasets differ). In this rebuttal period we also tested on real-world SAT Competition 2023 application families never seen in pretraining, where it beats random weights by +0.10 to +0.16 NMI.
  • FORGE-SAT can also help a SAT GNN to an extent. In the past week we initialized NeuroSAT with FORGE-SAT embeddings. It reached the target accuracy in fewer training steps on five of six families (6 fewer on k-Clique) and test AUROC rose by 8.6 points on k-Vercov.
  • We also interpret clause-level codewords and validate structural descriptions that hold on disjoint graphs and harder instances.

These findings show the possibilities and limits of cross-problem transfer, and what a unified MIP–SAT encoder would need, such as width-preserving normalization, with edge weighting and literal polarity as further candidates.

[W2] Benefit of transferring the MIP-pretrained model. The benefit is to show that, to some extent, we don't need SAT training at all. The MIP-pretrained models work for SAT:

  • On G4SATBench Hard, FORGE-MIP and FORGE-MIP-SAT reach 0.76 / 0.77 NMI, above STATIC-SAT (0.74) and a random encoder (0.54).
  • On SAT Competition 2023, FORGE-MIP gives the best clustering on two of three size subsets (0.925 and 0.927 NMI), ahead of FORGE-SAT (0.748 and 0.858).
  • On held-out-family SAT/UNSAT prediction (run during the rebuttal), FORGE-MIP and FORGE-MIP-SAT reach 0.623 and 0.630 AUROC respectively, against 0.600 for FORGE-SAT. Their lead comes from one family, CA, where clause width predicts the label. On the other six, FORGE-SAT is the best FORGE variant (0.616 vs 0.571 / 0.572).

Hence, MIP transfer is a free, label-free starting point, and FORGE-SAT improves clustering on G4SATBench and can be potentially useful for downstream prediction. We attribute the transfer to the MIP-pretrained encoder as a whole and do not separate its design from its weights.

[W3, Q2] Practical utility for SAT solving, and overhead. While preparing this response we found that our GGNN baseline applied a sigmoid twice. Retrained correctly, the supervised GGNN reaches 0.758 held-out AUROC (submitted 0.604), above frozen FORGE-SAT (0.600). The revised paper reports this and positions FORGE-SAT as a label-free, reusable representation, not a replacement for a supervised GNN. This work is about the potential and limits of FORGE transferability across problem classes. Beyond satisfiability prediction, the NeuroSAT result above is the most direct evidence: NeuroSAT is itself a neural SAT solver, and FORGE-SAT embeddings make it train faster on most families. A random-weight FORGE encoder gives a comparable speed-up, so much of it comes from FORGE’s features and architecture (Appendix A.6). We also added real-world clustering by application family, which is relevant to per-instance solver selection.

For Q2, we find that FORGE-SAT is the fastest of the three learned pipelines. Medians per instance (unbatched, GPU, shared machine; indicative):

Easy (1,400)Hard (1,400)
CaDiCaL solve0.27 ms6.9 ms (p90 547 ms; max 493 s)
FORGE-SAT, CNF →\to embedding18.5 ms≈\approx 132 ms
GGNN, CNF →\to prediction33.8 ms≈\approx 140 ms
NeuroSAT, CNF →\to prediction37.5 ms≈\approx 141 ms
Forward pass only: FORGE-SAT / GGNN / NeuroSAT3.6 / 30 / 35 ms4.1 / 28 / 36 ms

FORGE-SAT is about 2×2\times faster than GGNN and NeuroSAT on Easy and slightly faster on Hard, where CNF →\to graph preprocessing dominates all three (105–128 ms) end-to-end. Its forward pass alone is 7–9$\times$ cheaper. On most instances any learned pipeline costs more than solving; on the hardest ones, where learned guidance matters most, it is a small fraction (Hard 3-SAT median solve: 934 ms). The encoder is pretrained once without labels and reused frozen; a new task needs only a small head (about 6.5 s to train). We have not evaluated a solver integration and already list it, with assignment and UNSAT-core prediction, as future work

Hence, our claim is that FORGE representations capture SAT family structure, transfer from MIP with no SAT training, and speed up NeuroSAT training on most families. We hope this clarifies the contribution and would be grateful if you would consider raising the score.

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

The paper adapts FORGE's graph autoencoder from mixed-integer programming to SAT. It compares reusing MIP-pretrained weights, with or without SAT-specific features, against training the same architecture directly on SAT. The experiments look at how instances cluster, what the learned codewords represent, and whether frozen SAT-trained embeddings help predict satisfiability on held-out formula families.

Critical strengths

I like that the authors try to explain what the learned codewords capture and test these explanations on disjoint graphs and harder instances. The held-out node counts and the sampling of validation positives and negatives still need to be clearer.

Critical weaknesses
  1. Limited novelty and incomplete evidence for MIP-to-SAT transfer

I see this as a small methodological step beyond FORGE. The bipartite graph, GNN encoder, discrete codewords, and reconstruction objective are inherited. The adaptation adds a standard SAT-to-MIP encoding and SAT-specific features. The LLM interpretation also adapts an existing procedure (Paulo et al., 2025) to SAT codewords.

MIP-pretrained weights are evaluated through clustering. Among the FORGE variants, only FORGE-SAT, trained from scratch on SAT, is tested downstream. The downstream benefit of MIP pretraining is therefore untested. FORGE's Appendix A.6 (arXiv v5) already reports the 0.76 and 0.77 NMI scores. The submission cites FORGE, but I could not find an explicit acknowledgment that these results were already reported there.

  1. Limited evidence for the added value of the embeddings

STATIC-SAT, the non-learned feature baseline, already forms clear clusters and reaches NMI 0.74 (Table 1; Figure 3). FORGE-SAT reaches 0.81, well above the random encoder's 0.54. Purity moves from 0.63 to 0.66, which is a small gain. As the authors note, the embeddings mainly reflect the generator family. The joint scores do not quantify the gain in SAT/UNSAT separation within each family.

FORGE-SAT improves mean held-out AUROC over RAW (0.600 versus 0.523) and is similar to GGNN (0.604). It outperforms each baseline on five of seven families (Table 3). Cross-family generalization is still uneven: all three are near chance on held-out SR, whose SAT/UNSAT pairs differ in one literal occurrence (Selsam et al., 2019; Li et al., 2024). I suspect some gains depend on simple cues that happen to predict the label in particular generators. I would like more targeted controls for this.

I am still not convinced by the evidence of downstream usefulness. A test of whether the embeddings help a GNN learn faster or with fewer labels could change my assessment.

Questions for authors

Clarifications about the reported results:

  • Which findings are new relative to FORGE Appendix A.6 (arXiv v5)? Were the matching NMI scores reused or recomputed? Please cite that appendix alongside these results.
  • Report the downstream split sizes and per-family seen-distribution results, including SR. Please give uncertainty on paired AUROC differences, beyond variation across training seeds. What do training and prediction-score diagnostics show about GGNN's 0.5000 +/- 0.0000 on 3-SAT?
  • Section 5 (lines 366-367) requires both the description and the combined structural probe to reach AUROC >= 0.80 for a codeword to count as validated. Tables 2 and 5 appear to report only description scores. Where are the corresponding probe scores reported?

Additional experiments that would affect my assessment:

  • Evaluate FORGE-MIP and FORGE-MIP-SAT downstream, and check whether the gains persist across independent pretraining runs.
  • Separate family recovery from SAT/UNSAT separation within each family. How much do the joint clustering scores exceed a control that shuffles SAT labels within families while keeping the clusters fixed?
  • For the downstream task, do gains over RAW persist with regularized logistic regression? How does a frozen random FORGE encoder perform with the same architecture, pooling, and prediction head? Use the same splits and validation protocol.
  • On CA, GGNN reaches 0.976 while FORGE-SAT reaches 0.504. How predictive is clause width alone? If it is associated with SAT status, does performance persist after controlling for it?
  • On separate SR training and test sets, does initializing a NeuroSAT-style GNN with FORGE-SAT node embeddings improve AUROC or help it reach a fixed performance level with less training time, fewer labels, or fewer message-passing rounds? Compare against the same GNN without FORGE features under matched conditions.
3 comments
AuthorsOpenReview ↗

Rebuttal Part 1 of 2

Thank you for your feedback and questions. We appreciate that you liked our interpretability of codewords. We ran all five experiments listed under "Additional experiments that would affect my assessment" ([E1]–[E5]) and answered the three clarifications ([Q1]–[Q3]) in two parts.

[W1, Q1] Novelty and FORGE Appendix A.6. We intentionally reused FORGE to explore what transfers, without labels, between two very different problem classes. We present a controlled study of that transfer. As for Appendix A.6 in FORGE, it does not present an independent evaluation by the FORGE authors. It summarizes initial MIP-to-SAT observations and explicitly attributes the details to a separately cited manuscript. We have given the AC context on that citation that we cannot share here without affecting anonymity. The revised paper cites the appendix in Section 4.2. In addition, the values here are recomputed, not reused: we re-ran both MIP variants and reproduced them. Our FORGE-SAT is also new relative to those observations: it is pretrained on a different dataset, the SAT Competition 2022 Anniversary Track, so G4SATBench is never seen in pretraining, and it is the best clustering method in Table 1. We also have additional contributions on exploring and sharing validated codeword interpretation and downstream prediction. Also, through this rebuttal, we added more results by sharing MIP variants downstream, random-weight controls, the label-shuffle control, a SAT Competition 2023 holdout and NeuroSAT initialization.

[W1, E1, E3] MIP variants downstream and random encoder and logistic regression. We use the same splits, pooling, head and selection for every row, and report held-out AUROC over 3 seeds.

7-familyExcluding CA
RAW feature means0.5230.548
FORGE-RANDOM (same architecture)0.5660.578
FORGE-MIP0.6230.571
FORGE-MIP-SAT0.6300.572
FORGE-SAT0.6000.616
GGNN (supervised; corrected, see [Q2])0.7580.720

We find that pretraining helps. FORGE-SAT − random encoder (same architecture, pooling and head) is +0.034 [+0.018, +0.050], and FORGE-SAT − RAW is +0.077 [+0.052, +0.102]. As for MIP variants, their 7-family lead comes from CA alone ([E4]). Excluding CA, FORGE-SAT is the best FORGE variant (0.616 vs 0.571 / 0.572). Only one public MIP checkpoint exists, so variance across pretraining runs for FORGE-MIP cannot be measured.

As for E3, with L2-regularized logistic regression, we find that FORGE-SAT is below RAW (−0.059 [−0.089, −0.028]): the gain over raw features needs a non-linear head, and the revised paper states this (Appendix A.2).

[W2, E2] Family recovery and SAT/UNSAT separation. Thank you for your suggestion. We ran the controls, i.e., clusters fixed, SAT labels permuted within each family, 200 permutations 10 seeds. About 95% of FORGE-SAT's joint NMI survives; the excess (+0.039) comes from CA. This quantifies the paper's statement that the embeddings mainly reflect the generator family, and Section 4.2 now reports it.

[Q2] Splits, uncertainty, GGNN on 3-SAT. The splits are 1,600 / 200 / 200 Easy train / valid / test per family, exactly balanced. Each fold trains on 9,600 source instances, selects on 1,200 source-validation instances, and tests once on the held-out family's 200. As for uncertainty, they are paired, class-stratified bootstraps over test instances (10,000 resamples), seeds averaged within each replicate. Per-family held-out and seen results, including SR are in the appendix. While answering Q2, we found that G4SATBench's GGNN already outputs a probability. We realized that we trained it with a with-logits loss and applied a second sigmoid, so all 200 scores mapped to exactly 0.5 (logits −20 to −73). Hence, we retrained with the official loss and everything else identical. GGNN reaches 0.758 (submitted 0.604; 3-SAT 0.616), i.e. +0.158 [+0.132, +0.185] over FORGE-SAT. The revised paper reports this and no longer describes the two as similar. Frozen, label-free FORGE-SAT remains on par with the supervised GGNN on 3-SAT and k-Clique (0.632 vs 0.616; 0.543 vs 0.516).

[E4] CA and clause width. CA SAT instances are 5-uniform, and 95/100 UNSAT instances are 4-uniform. Mean width alone gives 0.975 held-out AUROC, also when trained on the other six families. This explains GGNN's CA score (0.983) and the MIP variants' (0.93–0.98). FORGE-SAT's per-instance normalization maps constant width to 0, hence chance on CA. We now report ex-CA means alongside 7-family means; on these FORGE-SAT is the best FORGE variant.

We will now respond to your [Q3], [E5] concerns and explain our contributions better in part 2.

AuthorsOpenReview ↗

Rebuttal Part 2 of 2

Here’s our continued response to your concerns.

[Q3] Codeword validation: probe scores, counts, sampling. The simulator uses 100 held-out nodes per code (50 positive / 50 negative) on Easy, from graphs disjoint from description generation, and 200 on Hard. Probes train on up to 150,000 nodes and validate on 426,372 clause / 45,253 variable nodes from disjoint graphs.

Thank you for also pointing out about the probe! We have now added combined-probe AUROC (description AUROC in parentheses) in Tables 2 and 9 of the revision. For reference, here are the values:

  • clause: 0-C 1.000 (0.830), 4-C 0.982 (0.699), 5-C 0.960 (0.896), 11-C 1.000 (0.693), 13-C 0.998 (0.926), 14-C 0.999 (0.819), 17-C 1.000 (0.949), 19-C 0.997 (0.994);
  • variable: 1-V 0.768 (0.534), 2-V 0.955 (0.793), 7-V 0.885 (0.804), 14-V 0.999† (0.654), 18-V 0.770 (0.438).

All eight clause codes have probe AUROC 0.96. The two-part criterion gives 6 validated clause codes and 1 validated variable code (7-V), plus 4 partial and 2 unresolved. †Code 14's probe was not split by node type.

[W2, E5] Faster learning. In your review, you wrote that "a test of whether the embeddings help a GNN learn faster or with fewer labels could change my assessment". We find that it can allow for faster learning for most families. We ran this test under matched conditions, on SR as you specified and on five more families. NeuroSAT's initial states are set from frozen FORGE-SAT node embeddings and compared with the same NeuroSAT without them: same seeds, batches and 1,300-step budget, 3 seeds, separate train/valid/test splits. Rules were fixed before training; test was scored once at the validation-selected checkpoint.

FamilySteps to threshold (valid): standard →\to +FORGE-SATTest AUROC: standard / +FORGE-SATDifference [95% CI]
k-Vercov (0.85)446 →\to 29589.3 / 97.9+8.6 [+5.2, +12.4]
k-Clique (0.80)754 →\to 12187.0 / 87.0+0.0 [−3.4, +3.2]
PS (0.90)143 →\to 7493.1 / 92.2−0.9 [−2.4, +0.4]
SR (0.85)802 →\to 73285.2 / 86.2+0.9 [−2.0, +4.0]
k-Domset (0.85)433 →\to 21799.1 / 91.9−7.1 [−10.6, −4.2]
3-SAT (0.85)589 →\to $>$1,30088.6 / 73.0−15.6 [−22.4, −8.9]

With FORGE-SAT, NeuroSAT reaches the fixed performance level in fewer steps on five of six families: 6 fewer on k-Clique, about 2 on PS and k-Domset, 1.5 on k-Vercov. On k-Vercov and k-Clique this holds in every seed, with test AUROC higher (k-Vercov) or unchanged on average (k-Clique), meeting our pre-fixed criterion. We get +8.6 points AUROC on k-Vercov; unchanged on k-Clique, PS and SR. On k-Domset the early speed-up comes with lower final AUROC; on random 3-SAT the initialization does not help, and with only 10% or 25% of SR labels it lowers test AUROC. A random-weight FORGE encoder gives a comparable speed-up, so much of the gain comes from FORGE's node features and architecture; relative to it, the pretrained encoder is ahead on k-Vercov test AUROC (+1.2 [+0.3, +2.2]) and behind on k-Domset (−2.0 [−3.6, −0.5]) and 3-SAT (−4.1 [−8.0, −0.3]).

Hence, we find that FORGE-SAT embeddings help a NeuroSAT-style GNN learn faster on graph-encoded families, and we report all six families.

Lastly, we would like to explain our contributions better! We ask whether a label-free representation learner built for mixed-integer programming can capture useful structure in Boolean satisfiability, a decision problem with different semantics, constraint types and solvers. With the controls your review asked for, the answer is positive and precise:

  1. Family structure transfers. FORGE organizes SAT instances by problem family better than the same encoder with random weights, on G4SATBench and on SAT Competition 2023 application families never seen in pretraining (+0.10 to +0.16 NMI), and the MIP-pretrained encoder does so with no SAT training.
  2. The codewords are interpretable and validated on disjoint graphs and harder instances.
  3. The embeddings help a SAT GNN train, on five of six families in speed and on one in accuracy.

Note that frozen embeddings do not replace a supervised GGNN for SAT/UNSAT prediction, but they remain valuable as a label-free representation that is trained once and reused across tasks. The controls identify what a unified MIP–SAT encoder needs: width-preserving normalization, with edge weighting and literal polarity as further candidates.

Our revised claim is that label-free FORGE representations capture SAT family structure, are interpretable at the clause level, and speed up NeuroSAT training on most families. We no longer claim parity with a supervised GGNN. We believe an unsupervised study that maps where transfer between two such different problem classes works, with matched controls and reported limits, is a useful contribution, and we would be grateful if the reviewer would consider raising the score.

Thank you for the detailed response and the new experiments. I appreciate that you report the negative results and fixed the GGNN baseline, even though this changes the main downstream claim. I accept that the manuscript cited in FORGE for the details is a preprint. However, the MIP-to-SAT clustering results themselves (0.76 and 0.77 NMI) are already reported in the published FORGE paper (Appendix A.6). Recomputing them confirms them but does not make them new, so this reduces the contribution of this submission; I leave the weighting of this overlap to the AC as I'm not confident how this should influence the final score.The other new results mostly confirm my concerns. The clustering mainly recovers the problem family (about 95% of the joint NMI survives the within-family label permutation). On SAT Competition 2023, FORGE-SAT beats random weights, but STATIC-SAT is better on all three subsets. With three G4SATBench families held out from pretraining, FORGE-SAT is not clearly above random weights (+0.021 [−0.029, +0.043]) and is well below STATIC-SAT (0.596 vs 0.759). Downstream, the gain over the random encoder is small (+0.034), comes mostly from PS (about +0.013 without it), and was not checked across pretraining runs. FORGE-SAT is below RAW with a logistic-regression head and stays at chance on SR even when SR is in the training set (0.4985 versus 0.818 for GGNN). In the NeuroSAT experiment, a random-weight FORGE encoder gives a similar speed-up. Apart from k-Vertex Cover, the pretrained initialization does not improve test AUROC: it is unchanged on SR (+0.9 [−2.0, +4.0]), lowers it when only 10% or 25% of the SR labels are used, and lowers it on 3-SAT and k-Dominating Set. Overall, I think the learned representations add little beyond simple structural features, so I keep my rating.

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

This paper studies the interesting topic of learning general-purpose representations of SAT instances through unsupervised pretraining. The paper adapts an existing foundational architecture from MIP to SAT through SAT-specific feature adaptation and SAT-native pretraining. The framework first converts CNF formulas into constraint-variable bipartite graphs. A graph encoder generates node embeddings, which are then mapped to discrete codewords through vector quantization. The model learns representations through unsupervised reconstruction of node features and graph edges. The learned representations can be used at the instance, clause, and variable levels. The experimental results show that the learned representations can effectively separate different problem families in G4SATBench.

Critical strengths

S1: This paper studies an interesting topic of learning general-purpose representations of SAT instances through unsupervised pretraining. The paper adapts an existing foundational architecture from MIP to SAT through SAT-specific feature adaptation and SAT-native pretraining, providing a promising direction for learning reusable SAT representations.

S2: The experimental results show that the learned representations can effectively separate different problem families in G4SATBench. The codeword interpretability analysis is also interesting and provides evidence that the learned representations capture meaningful structural patterns in SAT instances.

Critical weaknesses

W1: The novelty of the paper is limited. The original FORGE paper (Appendix A.6) already investigated MIP-to-SAT transfer using the same model variants. The main additions of the current paper are SAT-native pretraining, codeword interpretability analysis, and downstream satisfiability prediction. However, the paper introduces no substantial modifications to the original FORGE architecture or training objectives. Furthermore, the downstream prediction experiments evaluate only SAT-pretrained FORGE-SAT, without examining the MIP-pretrained transfer variants.

W2: The experimental evaluation also has some limitations. First, the clustering experiments are conducted exclusively on G4SATBench, which primarily consists of synthetically generated SAT instances. Although the authors use SAT Competition instances for pretraining, they do not test the learned representations on real-world SAT instances. For example, SAT Competition includes instances from various application domains, such as planning, coloring, scheduling, and software verification. Could the authors consider selecting a subset of these instances for clustering evaluation to further assess the generalizability of the learned representations? Also, how about pretraining on some G4SATBench problem families and evaluating clustering performance on the remaining families? Second, the downstream evaluation is restricted to instance-level SAT/UNSAT prediction. The proposed framework produces embeddings at the instance, clause, and variable levels. However, the paper does not evaluate their effectiveness on other SAT-specific tasks, such as unsat-core prediction or backbone prediction.

Questions for authors

Q1: The clustering experiments are conducted only on G4SATBench. Is there any evidence that the learned representations also generalize to real-world SAT instances? Also, could the authors consider pretraining on some G4SATBench problem families and evaluating clustering performance on the remaining families?

Q2: The downstream SAT/UNSAT prediction experiments evaluate only FORGE-SAT. How would the MIP-pretrained variants (FORGE-MIP and FORGE-MIP-SAT) perform on the same task?

Q3: The framework produces embeddings at the instance, clause, and variable levels, but the downstream evaluation only considers instance-level SAT/UNSAT prediction. Is there any evidence that the clause- and variable-level embeddings are useful for other SAT-specific tasks, such as UNSAT-core prediction or backbone prediction?

Q4: Could the authors consider including more SAT-specific neural models as baselines for the downstream SAT/UNSAT prediction experiments? For example, NeuroSAT (ICLR 2019) and SATformer (ICCAD 2023) could be evaluated under the same cross-distribution setting.

3 comments
AuthorsOpenReview ↗

Rebuttal Part 1 of 2

Thank you for your feedback and questions. Below we engage your concerns in detail.

[W1] Novelty and Appendix A.6 clarification. We use the FORGE architecture on purpose since we want to explore what transfers, without labels, from optimization to satisfiability. The paper hence studies different degrees of transfer from one problem class to another, which are zero-change transfer (FORGE-MIP), feature-adapted transfer (FORGE-MIP-SAT) and architectural transfer (FORGE-SAT). We also see this work as a step toward a future unified MIP–SAT representation model.

As for Appendix A.6 of the FORGE paper, it does not present an independent evaluation. The authors summarize initial MIP-to-SAT observations and explicitly attribute the details to a separately cited manuscript. We have given the AC context on that citation that we cannot share here without affecting anonymity. The revised paper now cites the appendix in Section 4.2. Beyond those observations, this paper contributes FORGE-SAT, which is pretrained on SAT instances (the SAT Competition 2022 Anniversary dataset) and gives the best clustering on G4SATBench (for cross-dataset generalizability) in Table 1 (0.81 NMI vs 0.74 for STATIC-SAT), as well as validated codeword interpretation and downstream evaluation. Through this rebuttal, we have now also added further results including MIP variants downstream, real-world SAT Competition 2023 instances, held-out families, a node-level probe and NeuroSAT initialization.

[W1, Q2] MIP-pretrained variants on the downstream task. We evaluate both MIP variants under the same protocol as FORGE-SAT, i.e., 7-fold leave-one-family-out, frozen encoder, same head and selection, 3 seeds. We report the results in Appendix A.2 of the revision.

Model7-family AUROCExcluding CA
FORGE-RANDOM0.5660.578
FORGE-MIP0.6230.571
FORGE-MIP-SAT0.6300.572
FORGE-SAT0.6000.616
GGNN (supervised; also see [Q4])0.7580.720

We find that FORGE-SAT is the best FORGE variant once CA is excluded (0.616 vs 0.571–0.578), so SAT-native pretraining adds downstream value beyond MIP transfer and beyond random weights. As for the MIP variants, their 7-family lead comes from CA alone, where clause width, which is visible in the MIP encoding, nearly determines the label (width alone gives 0.975 AUROC).

[W2, Q1] Real-world instances and held-out families. We clustered SAT Competition 2023 main-track instances that are disjoint from pretraining, i.e., 0 hash or isomorphism matches and 17 of 25 families unseen. We share our findings in Appendix A.4 of the revision. Here are the NMI values for three size subsets:

Subset (n, families)FORGE-SATRandom weightsSTATIC-SATFORGE-MIPFORGE-MIP-SAT
$\leq$10k nodes (31, 6)0.7480.5900.8420.9250.795
$\leq$30k nodes (85, 11)0.8580.7130.9070.9270.889
$\leq$100k nodes (142, 14)0.8350.7370.9220.8880.823

SAT pretraining beats random weights by +0.10 to +0.16 NMI on every subset, including on families unseen in pretraining (0.853 vs 0.809), so the representations do generalize to real-world application domains. FORGE-MIP, with no SAT training at all, gives the best clustering on two of the three subsets (0.925 and 0.927).

Following your second suggestion in Q1, we also pretrained a separate encoder on four G4SATBench families (3-SAT, CA, k-Domset, k-Vercov; 3 seeds) and clustered three unseen ones (SR, PS, k-Clique). It reaches 0.596 NMI vs 0.576 for random weights (difference +0.021 [−0.029, +0.043]). The gain is marginal, so the clearer evidence on unseen families is the SAT Competition result above (Appendix A.5 of the revision).

In the next official comment, we address your [W2, Q3] and [Q4] concerns.

AuthorsOpenReview ↗

Rebuttal Part 2 of 2

Here’s our continued response to your remaining concerns, i.e., [W2,Q3], and [Q4].

[W2, Q3] Clause- and variable-level usefulness. While our downstream SAT/UNSAT experiment operates at the instance level, Section 5 shows the clause- and variable- usefulness by evaluating the information captured by clause- and variable-level representations. We interpret individual codewords using structural descriptions and test whether these descriptions predict codeword membership on held-out nodes and transfer across SAT difficulty levels. These experiments identify interpretable structural patterns, such as clause polarity composition and node degree, and six clause codewords pass both of our validation criteria on disjoint graphs.

UNSAT-core and backbone prediction are complementary evaluations of task-specific node-level utility. As a first step, we ran the UNSAT-core test you suggested: frozen node embeddings probed for DRAT-trim core membership on 7,000 Easy UNSAT instances (G4SATBench has no backbone labels). Frozen FORGE-SAT embeddings did not improve on random weights there. Hence, our node-level claim is interpretable structure, and the revised paper states in its limitations that task-specific node-level utility is not established. The submission already lists assignment prediction, UNSAT-core prediction and solver-guided heuristics as future directions, and we view them as natural extensions of this study.

[Q4] NeuroSAT and SATformer. We find that NeuroSAT learns faster on most families when initialized with FORGE-SAT (Appendix A.6 of the revision). We set NeuroSAT's initial literal and clause states from frozen FORGE-SAT node embeddings and compared with the same NeuroSAT without them: same seeds, batches and 1,300-step budget, 3 seeds, separate train/valid/test splits. Rules were fixed before training; test was scored once at the validation-selected checkpoint.

FamilySteps to threshold (valid): standard →\to +FORGE-SATTest AUROC: standard / +FORGE-SATDifference [95% CI]
k-Vercov (0.85)446 →\to 29589.3 / 97.9+8.6 [+5.2, +12.4]
k-Clique (0.80)754 →\to 12187.0 / 87.0+0.0 [−3.4, +3.2]
PS (0.90)143 →\to 7493.1 / 92.2−0.9 [−2.4, +0.4]
SR (0.85)802 →\to 73285.2 / 86.2+0.9 [−2.0, +4.0]
k-Domset (0.85)433 →\to 21799.1 / 91.9−7.1 [−10.6, −4.2]
3-SAT (0.85)589 →\to $>$1,30088.6 / 73.0−15.6 [−22.4, −8.9]

With FORGE-SAT, NeuroSAT reaches the threshold in fewer steps on five of six families: 6 fewer on k-Clique, about 2 on PS and k-Domset, 1.5 on k-Vercov. On k-Vercov test AUROC also rises by 8.6 points; on k-Clique, PS and SR it is unchanged. On k-Domset the early speed-up comes with lower final accuracy, and on random 3-SAT the initialization does not help. We report all six families. A random-weight FORGE encoder gives a comparable speed-up, so much of the gain comes from FORGE’s node features and architecture; the pretrained encoder is ahead of it on k-Vercov (+1.2 [+0.3, +2.2]) and behind on k-Domset and 3-SAT (Appendix A.6).

As for SATformer, we ran it on 3-SAT in an exploratory run of a similar design and found no significant difference (−3.3 [−7.1, +0.2] points). Because it is exploratory, we do not include it in the paper. A full 7-family leave-one-family-out study of NeuroSAT and SATformer did not fit the response period, so we tested them in the way most relevant to this paper, i.e., whether FORGE-SAT helps these models.

While adding baselines, we found that our GGNN baseline applied a sigmoid twice (G4SATBench's model already outputs a probability). Retrained with the official loss and everything else identical, GGNN reaches 0.758 mean held-out AUROC (submitted 0.604), and the revised paper reports this value. Frozen, label-free FORGE-SAT is on par with it on 3-SAT and k-Clique (0.632 vs 0.616; 0.543 vs 0.516) and below it elsewhere.

Lastly, to summarize: with the experiments suggested, the paper now shows that FORGE representations can organize SAT instances by family, beyond random weights, on G4SATBench and on unseen real-world application families (+0.10 to +0.16 NMI); transfer from MIP with no SAT training, and improve further on G4SATBench with SAT-native pretraining. We also show a way to interpret and validate the clause-level codewords. Lastly, we show that we can speed up NeuroSAT training on five of six families and raise its accuracy on k-Vercov. Our revised claim is exactly this list. We no longer claim parity with a supervised GGNN for SAT/UNSAT prediction, but frozen embeddings remain valuable as a label-free representation that is trained once and can be reused across tasks. The study also yields design lessons for a unified MIP–SAT encoder (width-preserving normalization, with edge weighting and literal polarity as candidates). We hope this addresses your concerns and would be grateful if you would consider raising the score.

Reviewer_sY1SOpenReview ↗

Official Comment by Reviewer sY1S

I appreciate the authors' efforts in conducting additional experiments. While these results help strengthen the evaluation, I still have some reservations about the overall contribution and experimental evaluation. Therefore, I will maintain my original rating.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.