- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes SAT-ACT, a novel learning-based framework for improving branching decisions in CDCL SAT solvers. Traditional learning approaches rely on static structural properties or dynamic execution signals, which often fail to capture state-dependent branching effects reliably or force rigid scalar orderings when multiple outcome measures conflict.
To address this, SAT-ACT introduces: 1. Outcome-Derived Action Preferences: Extracts preferences from independent branching action rollouts initiated at the same solver state using three complementary outcome comparison criteria, deliberately leaving comparisons unresolved when evidence is insufficient or contradictory. 2. State-Conditioned Policy Network: Learns branching priorities directly from these preferences to guide CDCL search during inference without incurring the overhead of online action rollouts. 3. Non-Dominated Heuristic Action Supervision: Retains traditional solver-selected heuristic actions as training targets only when they remain non-dominated under the learned preferences.
Critical strengths
-
Principled Preference Extraction: Avoiding forced scalar metrics when rollout evidence is conflicting or insufficient is a robust design choice that prevents noisy supervision from degrading the learned policy.
-
Effective Offline/Online Separation: While data collection leverages rollouts, the inference phase uses a state-conditioned network directly, ensuring that search efficiency is not bottlenecked by online rollout overhead.
-
Strong Empirical Scope: Validation on diverse SAT families combined with competitive results on SAT Competition benchmarks demonstrates practical applicability beyond synthetic distributions.
Critical weaknesses
-
Training Data Generation Overhead: Independent branching action rollouts from identical solver states can be computationally expensive. The paper would benefit from a detailed analysis of the data generation time budget and how it scales with formula hardness.
-
Sensitivity to Comparison Criteria: The reliance on three complementary outcome comparison criteria raises questions about how sensitive the overall framework is to the specific definitions or thresholds used to determine dominance and conflict.
-
Industry Data Test. Thre results should be generalized to a relative large scale.
Questions for authors
-
What is the total computational overhead (in terms of time and resources) required to generate the training data via independent action rollouts, and how does this scaling behave on hard, large-scale instances?
-
How sensitive are the learned policies to the design and stringency of the three complementary outcome comparison criteria? What percentage of state comparisons typically end up left unresolved?
3 comments
Response to Reviewer g6J4 (Part 2)
W2: Sensitivity to Comparison Criteria: The reliance on three complementary outcome comparison criteria raises questions about how sensitive the overall framework is to the specific definitions or thresholds used to determine dominance and conflict.
Q2: How sensitive are the learned policies to the design and stringency of the three complementary outcome comparison criteria? What percentage of state comparisons typically end up left unresolved?
Thank you for raising this question.
The three criteria use fixed comparison rules without additional tunable comparison thresholds. C1 compares completion status, C2 applies Pareto dominance to completed rollouts, and C3 compares terminal-closure levels. Under these definitions, the criteria cannot produce opposite preferences for the same action pair. Comparisons remain unresolved when none of the criteria supports a preference.
We examine the contribution of these rules through the incremental ablations in Table 2 and the leave-one-out ablations in Appendix G.2. We additionally repeated training and evaluation on SR, CA, and PS using three independent random seeds under the 5-call setting. The following results report the mean and sample standard deviation, with standard deviations expressed in percentage points.
| Dataset | Criteria | ΔC ↓ | ΔD ↓ | ΔP ↓ |
|---|---|---|---|---|
| SR | C1 | -28.79% ± 1.82 | -26.23% ± 1.88 | -29.60% ± 1.97 |
| SR | C1 + C2 | -39.30% ± 0.23 | -36.84% ± 0.34 | -38.61% ± 0.23 |
| SR | C1 + C2 + C3 | -40.92% ± 1.27 | -38.30% ± 1.29 | -39.96% ± 1.20 |
| CA | C1 | -9.08% ± 1.06 | -3.73% ± 1.14 | -7.68% ± 1.33 |
| CA | C1 + C2 | -17.85% ± 0.34 | -12.28% ± 0.10 | -15.34% ± 0.97 |
| CA | C1 + C2 + C3 | -20.63% ± 0.14 | -14.23% ± 0.09 | -17.65% ± 0.40 |
| PS | C1 | -31.75% ± 2.22 | -30.50% ± 2.12 | -29.38% ± 2.38 |
| PS | C1 + C2 | -33.35% ± 0.89 | -32.36% ± 0.83 | -30.70% ± 1.16 |
| PS | C1 + C2 + C3 | -35.68% ± 1.25 | -34.60% ± 1.15 | -33.19% ± 1.48 |
Across all three datasets, C1+C2 already yields substantial mean reductions in search costs, while adding C3 provides further improvements. Combining all three criteria achieves the best mean performance across all three search-cost metrics on each dataset. These results support their complementary contributions. We will include these additional experimental results in the revised manuscript.
To further examine the choice of comparison rules, we evaluated a simple completion-plus-cost baseline that prefers completed rollouts over incomplete ones and ranks completed rollouts by propagation counts, with fewer propagations preferred. For this baseline and SAT-ACT (Pref. Only), we held the rollout data, architecture, training budget, pairwise ranking objective, and intervention schedule fixed. We repeated training and evaluation using three independent random seeds. Both methods were evaluated on the same test sets under the same solver configuration, using a 5-call intervention budget.
| Dataset | Method | ΔC ↓ | ΔD ↓ | ΔP ↓ |
|---|---|---|---|---|
| SR | Simple Completion+Cost | -40.05% ± 1.01 | -37.17% ± 0.86 | -39.31% ± 1.03 |
| SR | SAT-ACT (Pref. Only) | -40.92% ± 1.27 | -38.30% ± 1.29 | -39.96% ± 1.20 |
| CA | Simple Completion+Cost | -18.88% ± 0.57 | -13.17% ± 0.55 | -16.10% ± 0.95 |
| CA | SAT-ACT (Pref. Only) | -20.63% ± 0.14 | -14.23% ± 0.09 | -17.65% ± 0.40 |
| PS | Simple Completion+Cost | -33.91% ± 0.95 | -32.85% ± 0.90 | -31.79% ± 1.52 |
| PS | SAT-ACT (Pref. Only) | -35.68% ± 1.25 | -34.60% ± 1.15 | -33.19% ± 1.48 |
SAT-ACT (Pref. Only) achieves greater mean reductions in conflicts, decisions, and propagations than Simple Completion+Cost across all three datasets, supporting the additional value of our preference criteria over the tested single-cost ranking. The reductions achieved by Simple Completion+Cost support the broader supervision approach, while the additional mean gains from SAT-ACT (Pref. Only) support the value of our criteria within this approach. We will add this ablation to the revision.
Finally, Table 5 in the paper reports the coverage of supported preferences, from which we compute the proportions of unresolved action pairs under our data-collection settings:
| Dataset | Unresolved action pairs |
|---|---|
| SR | 22.21% |
| CA | 29.02% |
| PS | 21.16% |
These percentages are computed over candidate action pairs within states retained after supervision filtering. They describe comparisons between actions at the same solver state, rather than comparisons between different states. Such pairs remain unordered and do not contribute to the pairwise ranking loss.
We will clarify these points in the revised manuscript.
Response to Reviewer g6J4 (Part 3)
W3: Industry Data Test. The results should be generalized to a relative large scale.
Thanks for your valuable suggestion.
We have evaluated SAT-ACT on 1,200 SAT Competition Main Track instances from 2023–2025, as reported in Exp-4 and Appendix G.7 of our original paper (Exp-5 in the revised paper). These benchmarks include instances from industrial applications as well as large-scale formulas, extending our evaluation beyond the synthetic SAT families to practical application settings and larger problem scales. The 1,200 instances have median sizes of 13,210 variables and 113,965 clauses.
We additionally conducted three independent training and evaluation runs for SAT-ACT using different random seeds on all 400 SC-2023 instances, with Native CaDiCaL and NeuroCore as baselines. All solver evaluations used the same CaDiCaL configuration and a 5,000-second cutoff. The reported runtimes include neural-call overhead. We report the mean and sample standard deviation below.
| Run | Method | Solved | SAT | UNSAT | PAR-2 (s) |
|---|---|---|---|---|---|
| Run 1 | CaDiCaL (Native) | 251 | 116 | 135 | 4171.07 |
| CaDiCaL (NeuroCore) | 251 | 114 | 137 | 4129.18 | |
| CaDiCaL (SAT-ACT) | 253 | 115 | 138 | 4089.42 | |
| Run 2 | CaDiCaL (Native) | 251 | 115 | 136 | 4145.58 |
| CaDiCaL (NeuroCore) | 252 | 114 | 138 | 4139.74 | |
| CaDiCaL (SAT-ACT) | 253 | 116 | 137 | 4106.71 | |
| Run 3 | CaDiCaL (Native) | 253 | 116 | 137 | 4090.41 |
| CaDiCaL (NeuroCore) | 252 | 116 | 136 | 4135.14 | |
| CaDiCaL (SAT-ACT) | 255 | 116 | 139 | 4040.42 | |
| Mean ± Std. | CaDiCaL (Native) | 251.67 ± 1.15 | 115.67 ± 0.58 | 136.00 ± 1.00 | 4135.69 ± 41.23 |
| CaDiCaL (NeuroCore) | 251.67 ± 0.58 | 114.67 ± 1.15 | 137.00 ± 1.00 | 4134.69 ± 5.29 | |
| CaDiCaL (SAT-ACT) | 253.67 ± 1.15 | 115.67 ± 0.58 | 138.00 ± 1.00 | 4078.85 ± 34.39 |
Across all three runs, SAT-ACT solves more instances and achieves lower PAR-2 than both Native CaDiCaL and NeuroCore. In Run 1, SAT-ACT reduces mean runtime by 13.66% on the 248 instances solved by both SAT-ACT and Native CaDiCaL, covering 96.88% of the 256 instances solved by either of these two methods. These results provide additional evidence of practical benefits on challenging competition benchmarks beyond the small synthetic instances.
We will further clarify the scope and results of this evaluation in the revised manuscript.
Response to Reviewer g6J4 (Part 1)
Thanks for your insightful comment!
We reported data-generation costs in Appendix D and provide a consolidated summary below. Each family contains 20,000 instances, balanced between SAT and UNSAT. Their CNF sizes are summarized below.
Data generation was performed on a dual-socket Intel Xeon Gold 6248 machine with 40 physical cores (80 hardware threads) and 125 GiB of RAM, using 40 parallel workers. Data generation took approximately 5 minutes 8 seconds for CA, 4 minutes 9 seconds for SR, and 5 minutes 12 seconds for PS, or 14 minutes 29 seconds in total. The resulting serialized supervision occupies approximately 6.45 GB for CA, 3.18 GB for SR, and 3.85 GB for PS, totaling approximately 13.48 GB.
To examine scaling on harder and larger formulas, we additionally generated rollout supervision for the hard variants of all three families.
Relative to their corresponding normal datasets, the average numbers of variables and clauses increase by approximately 2.5× for CA, 2.5× for SR, and 2.1× for PS, or approximately 2.4× overall. Generation time increases by approximately 2.8× for CA, 4.6× for SR, and 6.8× for PS, or approximately 4.8× overall. Serialized storage increases by approximately 2.29× for CA, 2.04× for SR, and 1.84× for PS, or approximately 2.10× overall.
The higher generation cost for the hard instances is consistent with the additional solver computation required for state reconstruction and subsequent action evaluation. The increase is most pronounced for PS, whose hard instances exhibit substantially longer action-evaluation tails. Nevertheless, data generation is performed only once before training and can be readily parallelized because rollouts are independent across instances, states, and candidate actions.
Additional offline computation for supervision is also required by existing learning-guided SAT methods, including unsat-core extraction in NeuroCore[R1] and backbone extraction in NeuroBack[R2]. SAT-ACT similarly incurs this cost during data preparation, while its learned policy guides solving without online action rollouts.
We will further clarify this point in the revised paper.
[R1] Daniel Selsam and Nikolaj Bjørner. Guiding High-Performance SAT Solvers with Unsat-Core Predictions. International Conference on Theory and Applications of Satisfiability Testing (SAT 2019), pp. 336–353, 2019.
[R2] Wenxi Wang, Yang Hu, Mohit Tiwari, Sarfraz Khurshid, Kenneth L. McMillan, and Risto Miikkulainen. NeuroBack: Improving CDCL SAT Solving using Graph Neural Networks. International Conference on Learning Representations (ICLR), 2024.