acceptodds
Under review as a conference paper at ICLR 2027

SAT-ACT: Learning CDCL Branching from Outcome-Derived Action Preferences

Abstract

Learning-based approaches have increasingly been explored for SAT solving, with particular attention to improving branching decisions in conflict-driven clause learning (CDCL) solvers. These approaches derive branching guidance either from static structural properties of SAT formulas or from dynamic signals obtained through solver feedback and execution traces. However, these forms of supervision provide limited evidence about state-dependent branching effects, while different outcome measures may favor different branching choices. To address these limitations, we propose SAT-ACT, an outcome-derived learning framework for CDCL branching. We design three complementary outcome comparison criteria to extract action preferences from independent branching action rollouts initiated at the same solver state. The criteria identify preferences supported by the outcomes and leave comparisons unresolved when the evidence is insufficient or conflicting, instead of forcing an ordering using a predefined scalar metric. A state-conditioned network learns branching priorities from the extracted preferences and uses them to guide CDCL search directly without online action rollouts. We further introduce non-dominated heuristic action supervision, which retains the solver-selected action as a training target only when it remains non-dominated under these preferences. Solver-level experiments show that SAT-ACT consistently reduces CDCL search costs on three SAT families and improves PAR-2 on the SAT Competition benchmarks.

Primary area:
optimization
Keywords:
Boolean Satisfiability, SAT, Learning-based SAT Solving, CDCL Branching

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_g6J4OpenReview ↗
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
  1. 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.

  2. 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.

  3. Strong Empirical Scope: Validation on diverse SAT families combined with competitive results on SAT Competition benchmarks demonstrates practical applicability beyond synthetic distributions.

Critical weaknesses
  1. 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.

  2. 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.

  3. Industry Data Test. Thre results should be generalized to a relative large scale.

Questions for authors
  1. 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?

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

Response to Reviewer g6J4 (Part 1)

W1: 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.

Q1: 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?

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.

FamilyInstancesVariables (min / max / avg.)Clauses (min / max / avg.)
CA20,00040 / 200 / 120.81175 / 2,999 / 1,671.15
SR20,00040 / 200 / 119.78159 / 1,233 / 652.90
PS20,00040 / 200 / 118.70224 / 1,599 / 823.15

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.

Hard familyInstancesVariables (min / max / avg.)Clauses (min / max / avg.)TimeStorage
CA20,000200 / 400 / 299.832,610 / 5,998 / 4,194.6914 min 33 s14.79 GB
SR20,000200 / 400 / 299.71420 / 2,343 / 1,614.8719 min 4 s6.50 GB
PS20,000200 / 300 / 249.921,111 / 2,393 / 1,731.8435 min 24 s7.08 GB

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.

AuthorsOpenReview ↗

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.

DatasetCriteriaΔC ↓ΔD ↓ΔP ↓
SRC1-28.79% ± 1.82-26.23% ± 1.88-29.60% ± 1.97
SRC1 + C2-39.30% ± 0.23-36.84% ± 0.34-38.61% ± 0.23
SRC1 + C2 + C3-40.92% ± 1.27-38.30% ± 1.29-39.96% ± 1.20
CAC1-9.08% ± 1.06-3.73% ± 1.14-7.68% ± 1.33
CAC1 + C2-17.85% ± 0.34-12.28% ± 0.10-15.34% ± 0.97
CAC1 + C2 + C3-20.63% ± 0.14-14.23% ± 0.09-17.65% ± 0.40
PSC1-31.75% ± 2.22-30.50% ± 2.12-29.38% ± 2.38
PSC1 + C2-33.35% ± 0.89-32.36% ± 0.83-30.70% ± 1.16
PSC1 + 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.

DatasetMethodΔC ↓ΔD ↓ΔP ↓
SRSimple Completion+Cost-40.05% ± 1.01-37.17% ± 0.86-39.31% ± 1.03
SRSAT-ACT (Pref. Only)-40.92% ± 1.27-38.30% ± 1.29-39.96% ± 1.20
CASimple Completion+Cost-18.88% ± 0.57-13.17% ± 0.55-16.10% ± 0.95
CASAT-ACT (Pref. Only)-20.63% ± 0.14-14.23% ± 0.09-17.65% ± 0.40
PSSimple Completion+Cost-33.91% ± 0.95-32.85% ± 0.90-31.79% ± 1.52
PSSAT-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:

DatasetUnresolved action pairs
SR22.21%
CA29.02%
PS21.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.

AuthorsOpenReview ↗

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.

RunMethodSolvedSATUNSATPAR-2 (s)
Run 1CaDiCaL (Native)2511161354171.07
CaDiCaL (NeuroCore)2511141374129.18
CaDiCaL (SAT-ACT)2531151384089.42
Run 2CaDiCaL (Native)2511151364145.58
CaDiCaL (NeuroCore)2521141384139.74
CaDiCaL (SAT-ACT)2531161374106.71
Run 3CaDiCaL (Native)2531161374090.41
CaDiCaL (NeuroCore)2521161364135.14
CaDiCaL (SAT-ACT)2551161394040.42
Mean ± Std.CaDiCaL (Native)251.67 ± 1.15115.67 ± 0.58136.00 ± 1.004135.69 ± 41.23
CaDiCaL (NeuroCore)251.67 ± 0.58114.67 ± 1.15137.00 ± 1.004134.69 ± 5.29
CaDiCaL (SAT-ACT)253.67 ± 1.15115.67 ± 0.58138.00 ± 1.004078.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.

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

This paper proposes SAT-ACT, a learning-based framework for improving branching decisions in CDCL SAT solvers. The central idea is to evaluate multiple branching actions through independent rollouts from the same solver state and derive pairwise action preferences from their outcomes. The method introduces three outcome comparison criteria: completion, trajectory Pareto dominance, and terminal closure. These preferences supervise a state-conditioned graph neural network through a pairwise ranking objective. The authors also introduce non-dominated heuristic action supervision to selectively incorporate guidance from the solver's existing branching heuristic. Experiments on three synthetic SAT families and SAT Competition benchmarks demonstrate reductions in CDCL search costs and modest improvements in solving performance. Additional ablations investigate the contribution of individual preference criteria and heuristic supervision.

Critical strengths

1. A meaningful approach to state-dependent CDCL branching.

The paper addresses an important limitation of existing learning-based SAT branching methods by comparing candidate actions from the same dynamic solver state. This provides more direct supervision of branching decisions than relying solely on static formula features or recorded solver trajectories.

2. Solver-level evaluation with practical benchmarks.

The method is integrated into CaDiCaL and evaluated against several established learning-based approaches. The experiments include component ablations, generalization studies, and SAT Competition benchmarks. The reported runtime improvements on commonly solved competition instances provide useful evidence of practical potential.

Critical weaknesses

1. Questionable mathematical motivation for the preference criteria.

The paper emphasizes handling conflicting evidence among three outcome comparison criteria. However, under the stated definitions, such conflicts appear impossible. C1 only compares completed and incomplete rollouts, whereas C2 and C3 compare completed rollouts. Furthermore, the terminal-closure levels in C3 are monotonic with respect to the relevant cost dimensions, so C2 cannot support the opposite preference when C3 favors an action. Thus, the claimed conflict-resolution mechanism appears mathematically redundant. Moreover, C3 imposes predefined priorities over search behavior rather than avoiding subjective trade-offs entirely.

2. Insufficient evidence for the independent contribution of the proposed supervision mechanisms.

According to Table 5, C3 contributes only approximately 0.15%–0.39% additional preference pairs beyond C1 and C2, yet its inclusion produces substantial performance differences. The paper does not adequately explain this disproportionate effect or establish its statistical reliability. Additionally, the non-dominated heuristic supervision gate retains heuristic targets even when no outcome-derived preferences are available. Finally, improvements on the SAT Competition benchmarks are relatively modest, and stronger statistical evidence would help substantiate the practical significance of the proposed mechanisms.

Questions for authors

Q1. Can conflicting preferences actually arise under the proposed criteria?

C1 applies only when completion statuses differ, while C2 and C3 apply to completed rollouts. Moreover, a higher terminal-closure level in C3 appears incompatible with the opposite Pareto dominance relation in C2. Could the authors provide a concrete example in which two criteria support opposite preferences? If such cases cannot occur, what role does the proposed conflict-resolution condition serve?

Q2. What is the independent contribution of terminal closure?

Based on the counts in Table 5, C3 introduces only approximately 0.15%–0.39% additional preference pairs beyond C1 and C2. How does such a small increase in supervision coverage produce the substantial improvements reported in Table 2? Could the authors provide repeated-training results or other evidence to establish the reliability of this contribution? Also, how is the predefined preference for higher closure levels justified when other search-cost measures favor the opposite action?

Q3. How is heuristic supervision justified when preference evidence is absent?

According to Eqs. (9)–(12), when the preference set is empty, every sampled action is non-dominated, and the heuristic supervision gate remains active. Does this contradict the intended principle of retaining only outcome-compatible heuristic targets? How frequently does this situation occur, and would requiring positive preference evidence change the results?

Q4. How robust are the real-world performance improvements?

The SAT Competition experiments show a net increase of five solved instances across 1,200 benchmarks, with PAR-2 improvements varying across years. Could the authors provide uncertainty estimates or additional statistical analysis of the runtime gains? It would also be useful to clarify whether the benefits persist across independent training seeds and different solver configurations.

6 comments
AuthorsOpenReview ↗

Response to Reviewer W6MZ (Part 1)

W1: Questionable mathematical motivation for the preference criteria. The paper emphasizes handling conflicting evidence among three outcome comparison criteria. However, under the stated definitions, such conflicts appear impossible ... Thus, the claimed conflict-resolution mechanism appears mathematically redundant. Moreover, C3 imposes predefined priorities over search behavior rather than avoiding subjective trade-offs entirely.

Q1. Can conflicting preferences actually arise under the proposed criteria?

Thank you for your valuable comments.

Our preference criteria (C1-C3) do not produce conflicting preferences. We have clarified the corresponding description in the revised manuscript. In addition, our discussion of conflicting evidence concerns trade-offs among the raw search-cost measures, rather than contradictory preferences produced by different comparison criteria. Specifically, CDCL solver outcomes are characterized by several statistics, including the numbers of conflicts (constraint violations under the current assignment, distinct from “conflicting evidence” above), propagations, decisions, and restarts. Relying on any single measure may be insufficient to assess the relative quality of different branching actions, as these measures may favor different actions. For example, one branching action may result in fewer conflicts but more propagations than another. In such cases, neither action necessarily dominates the other across all search-cost dimensions. Our motivation is to derive supported action preferences from these multiple measures without combining them into a scalar score. Moreover, when both rollouts are complete, C3 favors the action with the higher terminal-closure level. This explicit preference for more direct termination allows C3 to distinguish some action pairs that C2 leaves unordered. The additional ablation results reported in our response to Q2 support the effectiveness of adding C3 to C1+C2.

We have revised the relevant wording in the manuscript to make this distinction explicit.

AuthorsOpenReview ↗

Response to Reviewer W6MZ (Part 2)

W2 (1): According to Table 5, C3 contributes only approximately 0.15%–0.39% additional preference pairs beyond C1 and C2, yet its inclusion produces substantial performance differences. The paper does not adequately explain this disproportionate effect or establish its statistical reliability.

Q2. What is the independent contribution of terminal closure? Based on the counts in Table 5, C3 introduces only approximately 0.15%–0.39% additional preference pairs beyond C1 and C2. How does such a small increase in supervision coverage produce the substantial improvements reported in Table 2? Could the authors provide repeated-training results or other evidence to establish the reliability of this contribution? Also, how is the predefined preference for higher closure levels justified when other search-cost measures favor the opposite action?

Thanks for your valuable comments.

We repeated training and evaluation on SR, CA, and PS using three independent random seeds under the 5-call setting. The table below reports the mean and sample standard deviation, with standard deviations expressed in percentage points.

DatasetCriteriaΔC ↓ΔD ↓ΔP ↓
SRC1-28.79% ± 1.82-26.23% ± 1.88-29.60% ± 1.97
SRC1 + C2-39.30% ± 0.23-36.84% ± 0.34-38.61% ± 0.23
SRC1 + C2 + C3-40.92% ± 1.27-38.30% ± 1.29-39.96% ± 1.20
CAC1-9.08% ± 1.06-3.73% ± 1.14-7.68% ± 1.33
CAC1 + C2-17.85% ± 0.34-12.28% ± 0.10-15.34% ± 0.97
CAC1 + C2 + C3-20.63% ± 0.14-14.23% ± 0.09-17.65% ± 0.40
PSC1-31.75% ± 2.22-30.50% ± 2.12-29.38% ± 2.38
PSC1 + C2-33.35% ± 0.89-32.36% ± 0.83-30.70% ± 1.16
PSC1 + C2 + C3-35.68% ± 1.25-34.60% ± 1.15-33.19% ± 1.48

To further assess consistency, we computed paired differences in ΔC between C1+C2+C3 and C1+C2 within each training seed. The differences are expressed in percentage points, with negative values indicating improvement after adding C3.

DatasetRun 1Run 2Run 3Mean ± SD
SR-2.26-2.24-0.35-1.62 ± 1.10
CA-2.84-2.47-3.02-2.78 ± 0.28
PS-2.23-1.06-3.68-2.32 ± 1.31

Across all three datasets, C1+C2 already yields substantial mean reductions in search costs, while adding C3 provides further improvements. The paired analysis further shows that C3 reduces conflicts in all three training seeds on each dataset. Mean decisions and propagations also decrease across all three datasets. These repeated-training results support an additional benefit from C3, although the magnitude of the improvement varies across training runs. We will include these additional experimental results in the revised manuscript.

The proportion of additional preference pairs may not fully reflect their contribution to the learned policy. C3 introduces additional preferences for some action pairs that remain unordered under C2, while preserving the Pareto-dominance relations established by C2. We favor higher closure levels because they capture how directly a branching choice leads to a terminal result. For example, if propagation alone completes the search after the selected action, that choice was sufficient for the solver to finish without another branching decision. This provides a structural basis for preferring the action when C2 leaves the comparison unresolved. Our repeated-training results further support this design choice. Adding C3 to C1+C2 reduced mean conflict, decision, and propagation counts on each of the three datasets.

We will clarify these points in the revised manuscript.

AuthorsOpenReview ↗

Response to Reviewer W6MZ (Part 3)

W2 (2): Additionally, the non-dominated heuristic supervision gate retains heuristic targets even when no outcome-derived preferences are available.

Q3. How is heuristic supervision justified when preference evidence is absent? According to Eqs. (9)–(12), when the preference set is empty, every sampled action is non-dominated, and the heuristic supervision gate remains active. Does this contradict the intended principle of retaining only outcome-compatible heuristic targets? How frequently does this situation occur, and would requiring positive preference evidence change the results?

Thank you for raising this question.

First, the gate retains heuristic targets whenever no evaluated action is preferred to them, as explained after Eq. (9). Here, outcome compatibility means that the available preferences do not contradict the heuristic target. It does not require evidence that the heuristic action outperforms another candidate.

In our reported training datasets, states without supported preference pairs are filtered out during data preparation (Table 5 and Appendix G.6 of the revised manuscript). Thus, no training states have an empty preference set.

Second, the heuristic action is the branching action selected by the CDCL solver’s native heuristic at the current solver state. When the preference set is empty or no preference pair involves the heuristic action, the heuristic supervision amounts to imitation learning of the solver’s action choice. This is similar in spirit to ImitSAT (ICLR 2026), which learns branching decisions from solver behavior.

Our ablation study evaluates using heuristic actions as the sole supervision signal (Heur. Only in Table 3). The results show reductions in conflicts, decisions, and propagations across all three datasets:

DatasetΔC ↓ΔD ↓ΔP ↓
SR-30.84%-27.80%-31.91%
CA-9.42%-3.03%-5.43%
PS-16.30%-15.59%-13.41%

These results demonstrate that learning from heuristic actions alone can improve search efficiency. The gate retains this supervision when it is compatible with the available outcome-derived preferences.

We will clarify these points in the revised paper.

Reviewer_W6zdOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

SAT-ACT learns CDCL branching decisions from offline rollouts of alternative variable–polarity actions initiated at the same solver state. It constructs pairwise preferences using completion status, Pareto dominance over search costs, and a terminal-closure criterion. Evaluation includes three synthetic SAT families, component ablations, harder-instance transfer, and a separately trained model evaluated on SAT Competition benchmarks.

Critical strengths

The strongest positive is the construction of action comparisons from a shared solver state. The replay protocol changes one backtrackable branching decision while preserving the starting search context, providing a reasonably controlled basis for comparing subsequent outcomes.

Critical weaknesses
  1. The central preference-design justification is overstated, and its contribution is not adequately isolated. The paper emphasizes resolving conflicting evidence without imposing predefined tradeoffs, but the stated criteria cannot actually conflict.

  2. The evidence for a robust practical advantage is insufficient. The main benchmarks contain only 40–200 variables, and Appendix G.6 explicitly acknowledges that neural overhead outweighs the runtime savings from reduced search counts. Practical runtime evidence therefore rests primarily on the SAT Competition experiment. Table 4 shows PAR-2 reductions of approximately 0.49%, 0.92%, and 2.83%, with net gains of zero, two, and three solved instances out of 400 per year. The reported 10.15% runtime reduction on the 752 commonly solved instances is useful evidence, but concerns a subset and does not replace the full-benchmark assessment. Crucially, the competition evaluation includes neither learned competitors nor component ablations, and reports no uncertainty estimates across training seeds or repeated timing measurements. These omissions make it difficult to establish the robustness of the gains or attribute them to the proposed methodological contributions. The current evidence is insufficient to support acceptance.

Questions for authors

With rollout data, architecture, training budget, and intervention schedule held fixed, how does SAT-ACT compare against simpler completion-plus-cost rankings or imitation of the best rollout action? Can the authors provide per-instance competition runtimes, uncertainty estimates across independent training seeds and repeated evaluations, and a competitive learned baseline under the same solver configuration?

2 comments
AuthorsOpenReview ↗

Response to Reviewer W6zd (Part 1)

W1: The central preference-design justification is overstated, and its contribution is not adequately isolated. The paper emphasizes resolving conflicting evidence without imposing predefined tradeoffs, but the stated criteria cannot actually conflict.

Thank you for your valuable comments.

Our preference criteria (C1-C3) do not produce conflicting preferences. We have clarified the corresponding description in the revised manuscript. In addition, our discussion of conflicting evidence concerns trade-offs among the raw search-cost measures, rather than contradictory preferences produced by different comparison criteria. Specifically, CDCL solver outcomes are characterized by several statistics, including the numbers of conflicts (constraint violations under the current assignment, distinct from “conflicting evidence” above), propagations, decisions, and restarts. Relying on any single measure may be insufficient to assess the relative quality of different branching actions, as these measures may favor different actions. For example, one branching action may result in fewer conflicts but more propagations than another. In such cases, neither action necessarily dominates the other across all search-cost dimensions. Our motivation is to derive supported action preferences from these multiple measures without combining them into a scalar score.

We have revised the relevant wording in the manuscript to make this distinction explicit.

Q1: how does SAT-ACT compare against simpler completion-plus-cost rankings or imitation of the best rollout action?

Thanks for your valuable suggestion.

We additionally evaluated a simple completion+cost baseline that prefers completed rollouts over incomplete ones and ranks completed rollouts by their 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. The table reports the mean and sample standard deviation, with standard deviations expressed in percentage points.

DatasetMethodΔC ↓ΔD ↓ΔP ↓
SRSimple Completion+Cost-40.05% ± 1.01-37.17% ± 0.86-39.31% ± 1.03
SRSAT-ACT (Pref. Only)-40.92% ± 1.27-38.30% ± 1.29-39.96% ± 1.20
CASimple Completion+Cost-18.88% ± 0.57-13.17% ± 0.55-16.10% ± 0.95
CASAT-ACT (Pref. Only)-20.63% ± 0.14-14.23% ± 0.09-17.65% ± 0.40
PSSimple Completion+Cost-33.91% ± 0.95-32.85% ± 0.90-31.79% ± 1.52
PSSAT-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. In addition, our contribution includes both constructing action-ranking supervision from rollouts initiated at the same solver state and designing complementary criteria for extracting supported preferences. 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.

Regarding imitation of the best rollout action, SAT-ACT learns from pairwise preferences and therefore does not require a single best action as a supervision target. When several actions remain non-dominated, our criteria alone cannot identify a unique best action among them. The completion-plus-cost ranking provides one possible selection rule under which a top-ranked action could serve as an imitation target. The completion-plus-cost baseline we evaluated already incorporates this best-action information through pairwise comparisons that favor top-ranked actions over lower-ranked candidates. It also uses comparisons among the remaining candidates whenever the ranking distinguishes them.

We will clarify this in the revised paper.

AuthorsOpenReview ↗

Response to Reviewer W6zd (Part 2)

W2: The main benchmarks contain only 40–200 variables, and Appendix G.6 explicitly acknowledges that neural overhead outweighs the runtime savings from reduced search counts.

Crucially, the competition evaluation includes neither learned competitors nor component ablations, and reports no uncertainty estimates across training seeds or repeated timing measurements. These omissions make it difficult to establish the robustness of the gains or attribute them to the proposed methodological contributions. The current evidence is insufficient to support acceptance.

Q2: Can the authors provide per-instance competition runtimes, uncertainty estimates across independent training seeds and repeated evaluations, and a competitive learned baseline under the same solver configuration?

Thank you for these insightful comments.

The SR, CA, and PS experiments assess search efficiency and the contributions of individual components. To assess practical runtime benefits with neural overhead included, we provide additional SAT Competition results below.

1. Repeated evaluations and learned baseline

We conducted three independent training and evaluation runs for SAT-ACT using different random seeds, each covering all 400 SAT Competition 2023 instances, and evaluated NeuroCore under the same setting as a learned baseline. All solver evaluations used the same CaDiCaL configuration and a 5,000-second cutoff. SAT-ACT was allowed at most three neural requests per instance, and the reported runtimes include neural inference overhead for both SAT-ACT and NeuroCore. We report the mean and sample standard deviation below.

RunMethodSolvedSATUNSATPAR-2 (s)
Run 1CaDiCaL (Native)2511161354171.07
CaDiCaL (NeuroCore)2511141374129.18
CaDiCaL (SAT-ACT)2531151384089.42
Run 2CaDiCaL (Native)2511151364145.58
CaDiCaL (NeuroCore)2521141384139.74
CaDiCaL (SAT-ACT)2531161374106.71
Run 3CaDiCaL (Native)2531161374090.41
CaDiCaL (NeuroCore)2521161364135.14
CaDiCaL (SAT-ACT)2551161394040.42
Mean ± Std.CaDiCaL (Native)251.67 ± 1.15115.67 ± 0.58136.00 ± 1.004135.69 ± 41.23
CaDiCaL (NeuroCore)251.67 ± 0.58114.67 ± 1.15137.00 ± 1.004134.69 ± 5.29
CaDiCaL (SAT-ACT)253.67 ± 1.15115.67 ± 0.58138.00 ± 1.004078.85 ± 34.39

Across all three runs, CaDiCaL (SAT-ACT) obtains higher solved counts and lower PAR-2 values than both CaDiCaL (Native) and CaDiCaL (NeuroCore). We will include these additional experimental results in the revised manuscript.

2. Analysis of competition instance runtimes

We further decompose the 81.64-second PAR-2 reduction observed in Run 1 across all 400 SC-2023 instances. CaDiCaL (Native) and CaDiCaL (SAT-ACT) both solve 248 instances, CaDiCaL (SAT-ACT) alone solves 5, CaDiCaL (Native) alone solves 3, and both time out on 144. Among the 256 instances solved by at least one method, 248 (96.88%) are solved by both. For the remaining 144 instances, both methods reach the same 5,000-second cutoff and are therefore assigned identical runtimes in the comparison.

  • On the 248 commonly solved instances, faster runtimes with CaDiCaL (SAT-ACT) save 23,540.43 s cumulatively and reduce the full-benchmark PAR-2 by 58.85 s. CaDiCaL (SAT-ACT) is faster on 151 instances, saving 37,493.55 s cumulatively and contributing a 93.73-second reduction to the full-benchmark PAR-2. CaDiCaL (Native) is faster on the remaining 97 instances, where CaDiCaL (SAT-ACT) incurs 13,953.12 s of additional cumulative runtime, corresponding to a 34.88-second increase in PAR-2. Combining these two groups gives a cumulative saving of 23,540.43 s, or a 58.85-second PAR-2 reduction over all 400 instances. Within the commonly solved set, mean runtime decreases from 695.05 s to 600.13 s, corresponding to a 13.66% reduction.

  • On the 144 mutual-timeout instances, both methods reach the same 5,000-second cutoff and receive identical 10,000-second PAR-2 penalties. These instances therefore contribute zero to the paired PAR-2 difference.

  • Among the eight instances solved by only one method, CaDiCaL (SAT-ACT) solves five while CaDiCaL (Native) solves three, producing a net gain of two solved instances. These discordant cases reduce the cumulative PAR-2 cost by 9,117.49 s and contribute an additional 22.79-second reduction to the full-benchmark PAR-2.

We will clarify these results in the revised paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.