- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes an optimization-guided initialization framework for CDCL SAT solvers. Namely, the authors optimize a differentiable MaxSAT objective on a GPU for each input formula and use the resulting assignment preferences and gradient-derived variable scores to initialize phase selection and branching activities in Kissat. The actual CDCL procedure remains unchanged. The same idea is extended to parallel solving by perturbing the optimized logits to obtain different initial phases for a portfolio of solver workers. Experiments on SAT Competition 2024 instances demonstrate improvements over standard Kissat, as well as an advantage over MallobSat on satisfiable instances in the parallel setting.
Overall, I am slightly on the positive side. The paper is easy to follow, the approach is interesting, and the experiments demonstrate some practical benefit. The contribution is somewhat incremental and the evaluation could and should be strengthened, but I think the paper could be accepted.
Critical strengths
-
Overall, the paper is quite well written. Although I am no machine learner and I typically struggle with ML-based approaches to SAT and other combinatorial problems, I found this paper relatively simple to follow. The main concepts are defined and the steps of the approach are explained clearly.
-
The idea of using differentiable optimization to bootstrap the execution of an otherwise standard SAT solver is interesting. In particular, the optimization is performed separately for each formula and does not require a collection of labelled training instances. The resulting "values" are then plugged in to initialize existing heuristics effectively bootstrapping the SAT solver, which makes the approach reasonably simple and preserves the underlying solver's correctness.
-
The authors evaluate the approach with strong practical baselines, including Kissat and MallobSat. The single-threaded improvements are observed on both satisfiable and unsatisfiable instances, and the reported total runtimes include the GPU optimization overhead. While the gains are not particularly large, improving a highly optimized SAT solver is certainly not an easy task. Having said that, it does not strike me that the approach is better aligned with satisfiable instances given that it focuses on optimizing a MaxSAT objective.
Critical weaknesses
-
The relation with traditional static branching and polarity heuristics deserves a much better discussion. Initializing a solver using formula-dependent information is not a new idea: Jeroslow–Wang and literal-count heuristics provide immediate connections, both for choosing variables and for selecting their initial polarities. For example, PicoSAT used Jeroslow–Wang scores for initial phase selection. While Appendix A.1 includes JW, MOMS and degree-based baselines, this connection is largely absent from the main discussion, and the appendix does not explain how these baselines initialize phases and activities. Furthermore, the comparison is restricted to 111 instances selected according to Kissat's runtime, which to my taste does not look satisfactory. A comparison on the full benchmark set would help establish the benefit over these much simpler alternatives. The idea is nice but not particularly deep, and its novelty should be positioned more carefully.
-
The experimental results are positive but somewhat modest. The best individual single-threaded configurations achieve PAR-2 speedups of about 1.18 on SAT and 1.07 on UNSAT instances. These are useful improvements, but I would like a clearer picture of where they come from. PAR-2 penalizes a timeout by twice the cutoff, so a few changes in solved status can substantially affect the overall score. I find the absence of standard cactus plots and, more importantly, pairwise runtime scatter plots hard to justify. These would show the behaviour of the solvers much more clearly than binned speedup distributions.
-
The parallel results require some discussion. The proposed portfolio improves over MallobSat on satisfiable instances, but on unsatisfiable instances it solves 155 cases compared with MallobSat's 168 and has a significantly worse PAR-2 score. The authors acknowledge this limitation and the absence of clause sharing, which is good. However, whether or not the absence of clause sharing is the culprit is yet to be understood. As a result, the parallel results can be seen to add a bit of grain of salt here.
-
The choice of benchmarks leaves much to be desired. Why are only SAT Competition 2024 instances considered? Why not include the 2025 and 2026 benchmarks? Evaluation across several competition years would make the practical conclusions more convincing. The choice of the 368-instance evaluation set should also be explained.
-
The interaction with preprocessing and inprocessing is unclear to me. Kissat may eliminate variables and clauses, substitute variables, and otherwise change the formula before and during search. The paper should explain whether the optimization is applied to the original formula or a preprocessed one, when the phases and activities are injected, and how the variable mapping is maintained. This does not necessarily invalidate the approach, but it may affect how useful the bootstrapping actually is. As far as I can see, the current description does not make this clear.
Questions for authors
-
Can you clarify how JW, MOMS and static initialization in Appendix A.1 are implemented? Do they initialize phases, branching activities, or both? Can you extend this comparison to the full benchmark set?
-
Can you provide cactus and pairwise scatter plots rather than focusing on improved-case speedups?
-
Why was SAT Competition 2024 chosen as the only benchmark source, and how were the 368 instances selected?
-
At what point relative to Kissat's preprocessing are the optimization and heuristic initialization performed? How are eliminated or substituted variables handled?
-
In the parallel setting, how much of the benefit comes from the optimized logits rather than phase diversification alone? A comparison with an otherwise identical portfolio using random initial phases would be useful.
2 comments
Thank you for the answers. I appreciate it.
Answers to questions
Thank you for the comments. We apologize for the delay while we completed the additional experiments on SAT Competition 2026 benchmarks.
JW computes a score for each literal,
J(l) = sum_{C containing l} 2^(-|C|), and selects the polarity with the larger score. MOMS selects the polarity by comparing positive and negative literal counts in the shortest nonempty clauses. Both initialize phases only in our experiments. Degree ranks variables by total occurrence count. For BMM, we follow the method proposed in the original paper. For Degree, BMM, and our method, the top 50 ranked variables receive an initial activity of 10,000. We will discuss the connection to traditional initialization heuristics in the main text and clarify the role of our saliency scoring and degree normalization. Due to limited computing resources and the number of configurations being evaluated, we restricted the comparison to 111 instances. We will state this scope and the instance-selection criterion explicitly in the appendix.We provide separate SAT and UNSAT cactus plots for the 2024 and 2026 experiments: Link to single thread 2024 cactus plot: https://drive.google.com/file/d/1ZsK-iS_Zwm44pWgxczxPRxehZ313r0-B/view?usp=drive_link Link to multi-thread 2024 cactus plot: https://drive.google.com/file/d/1nf0bAUR9avps-1H3oWiqmZAgpCWIuieT/view?usp=sharing Link to single thread 2026 cactus plot: https://drive.google.com/file/d/16UJi0-J6mB6Bv7_zwHG2Je4hMxCfwE43/view?usp=drive_link We will also add pairwise runtime scatter plots, with timeouts marked explicitly. To explain the PAR-2 changes, we will report runtime changes on instances solved by both configurations separately from instances solved by only one.
We evaluated 368 instances, excluding those with more than 10 million variables or 50 million clauses after conversion to 3-SAT. Our implementation reuses GaloisSAT’s GPU optimization code. The size thresholds were chosen to avoid excessive GPU initialization overhead under the memory and compute constraints of our RTX 4090 setup. We apologize for not stating this criterion and will provide the full list of excluded instances. GaloisSAT demonstrates that this optimization can handle substantially larger instances with greater GPU resources. It reports near-linear training speedup when scaling from 2×A100 to 8×A100 (GaloisSAT, Table 3: https://arxiv.org/html/2603.28796#S3.T3). For an instance with approximately 131 million clauses, training time decreased from 884.79 s to 238.18 s. These results support using larger GPU configurations to extend our evaluation beyond the current size limits. We extended our single-thread evaluation to 333 instances from the SAT Competition 2026 benchmark, comprising 172 SAT and 161 UNSAT instances. The table below reports PAR-2 scores with a 5,000-second timeout and a 10,000-second penalty for each unsolved instance. The corresponding SAT and UNSAT cactus plots are provided in our response to Comment 3. | Instances | Number of instances | Kissat PAR-2 (s) / Solved| Ours (Phase+VSIDS norm, mapped) PAR-2 (s) / Solved| | :--- | ---: | ---: | ---: | | SAT | 172 | 3,590.63 / 118 | 3,593.11 / 117 | | UNSAT | 161 | 3,945.46 / 106 | 3,965.09 /107|
Guidance is generated from the CNF supplied to Kissat, before Kissat’s own preprocessing. We map hint variable IDs obtained from GPU to Kissat's internal variables through
solver->import, correcting phase signs and skipping unimported or eliminated variables. Phases are written to the target and best arrays, leaving saved phases unchanged. The same mapping preserves the VSIDS ranking. The top 50 valid variables receive 10,000. Hints are injected once before Kissat’s preprocessing. Subsequent preprocessing and inprocessing proceed normally, without regenerating or reloading guidance.We prioritized the additional SAT Competition 2026 experiments with the available computing resources and have not yet completed the random-phase portfolio comparison. We therefore cannot isolate how much of the benefit comes from optimized logits rather than phase diversification alone. We will also clarify that the absence of clause sharing is a possible explanation for the weaker UNSAT results, but its effect has not been isolated experimentally.