- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper presents FOCON, a lightweight formula‑conditioned, receiver‑aware router for parallel CDCL SAT solvers. FOCON employs a polarity‑equivariant factor network and an event‑level scorer with latency‑discounted clause reuse, enabling adaptive communication control and robust out‑of‑distribution (OOD) fallback. Evaluations demonstrate strong performance in both solving efficiency and communication overhead, while maintaining correctness and cross‑family generalization.
Critical strengths
- The problem modeling is clear and has practical significance: shifting the clause exchange from "clause quality ranking" to a joint decision of "sender-receiver-formula-search phase." The example in Figure 1 intuitively illustrates the receiver's dependency on utility, providing sufficient motivation.
- The method demonstrates good design in calculating amortization and deployment constraints: formula-level graph inference is performed only once, and online decision-making degrades to low-dimensional inner products, making it suitable for high-frequency clause exchanges. Additionally, budget control and OOD (Out-of-Distribution) fallback are introduced to balance efficiency, communication constraints, and conservativeness under distributional shifts. The experiments also report ablation studies and theoretical analyses.
Critical weaknesses
- The Baseline parallel backend is outdated and has a single scale. The main experiment only used the 8-worker Glucose-Syrup (circa 2014) and did not compare it with modern parallel solvers from the recently SAT Competition (such as MallobSat, Painless-PRS-Kissat, PRS) or 16/32/64-worker setups, making it difficult to assess the method's actual incremental value in the current parallel SAT ecosystem.
- The communication budget is not strictly aligned with the baseline. The FOCON acceptance rate is approximately 20%, but Glucose-Syrup's native lazy clause exchange already has LBD filtering and a budget mechanism; the paper's "20% vs 100%" may overestimate selectivity, as a fair comparison was not conducted under the same candidate stream and equivalent communication budget.
- The presentation of the paper includes a high density of symbols and formula derivations, with relatively limited intuitive explanations. Recommend to optimize the expression to improve readability.
Questions for authors
- Can FOCON be verified on modern parallel backends (MallobSat / Painless / PRS) and with 16~64 workers? Do the benefits perceived by the receiver remain constant as the number of workers increases, and how does the router overhead ratio change? 2.Glucose-Syrup's native sharing strategy already incorporates LBD filtering and budget control. Could we consider adjusting its acceptance rate to approximately 20%, similar to FOCON, and run another end-to-end control experiment? This will allow us to more clearly separate the contributions from "routing selectivity" and "backend differences".
4 comments
Dear Reviewer,
As the discussion period approaches the end, we would be grateful if you could review our rebuttal and let us know whether our responses have adequately addressed your concerns. If any concerns remain, please feel free to share them, and we would be pleased to provide further clarification.
Thank you very much for your time and consideration.
Best regards,
The Authors
The authors have supplemented multi-backend experiments on MalloSAT/Painless/PRS, extended the evaluation to 16/32 workers, and added random-20/LBD-20 budget-matched controls, which substantively address my core concerns. I'll raise my score accordingly.
Dear Reviewer,
Thank you very much for revisiting our response and raising your score. We sincerely appreciate your time, constructive feedback, and positive reassessment of our work.
Best regards,
The Authors
Modern Parallel Solver Integration, Worker Scalability, and Budget-Matched Comparisons
We thank the reviewer for the insightful comments and constructive suggestions, which have helped strengthen the presentation and experimental evaluation. All revisions and additional experiments are highlighted in blue in the updated manuscript. We address the weaknesses (W) and questions (Q) below.
1. [W1/Q1. Modern parallel backends and worker scalability]
Re. We have integrated FOCON into MallobSat, Painless, and PRS at the clause-import interface, preserving native CDCL search, clause export, and communication topology (Appendix D.2). FOCON improves SR and PAR-2 across all four backends, with PAR-2 reductions of 4.80%, 3.47%, 2.23%, and 1.00% on Glucose-Syrup, PRS, Painless, and MallobSat, respectively (Table 5). FOCON further reduces PAR-2 in 7 of 8 backend-timeout configurations on SAT Competition 2025-2026 (Table 23), demonstrating the complementary value of learned routing across modern parallel architectures.
We have also extended the evaluation to 16 and 32 workers on Glucose-Syrup (Appendix E.7, Table 19):
As the portfolio grows, the candidate-event rate increases 4.4 times, from 64290 to 284522 events/s. Although absolute reuse per accepted transfer decreases, FOCON's relative reuse advantage over native sharing increases from a factor of 4.7 to 5.6. At 8 workers, FOCON retains 98.7% of native reuses while accepting only 152.09K of 721.68K clauses (Table 3). The PAR-2 reduction over native sharing increases from 4.8% to 10.6%, while the improvement over LBD-20 remains between 4.8% and 5.6%. These results highlight the increasing value of receiver-aware selection under higher communication loads and the benefit beyond LBD-based selection.
FOCON maintains acceptance near 20%, with online routing accounting for only 1.43-2.21% of solver CPU time.
2. [W2/Q2. Budget-matched comparison with native sharing]
Re. Glucose-Syrup already incorporates LBD-based filtering and communication regulation. The reported 100% acceptance refers to native-eligible transfers after native filtering, rather than all generated learned clauses. FOCON therefore provides an additional layer of receiver-aware selection.
To isolate the contribution of learned selection, we evaluate two budget-matched controls (Table 4, Appendix D.2):
Both controls share FOCON's backend, native eligibility criteria, import interface, and adaptive controller at ρ=0.2, while varying the selection mechanism. Realized candidate streams remain policy-dependent.
Under matched acceptance targets, FOCON reduces PAR-2 by 9.66% and 5.11% over Random-20 and LBD-20, respectively, while achieving higher SR. FOCON also transfers 15.59% less data than LBD-20 and 88.3% less than native sharing, and is the only evaluated 20% policy that improves both SR and PAR-2 over native sharing. Both heuristics fall below native sharing, indicating that a 20% budget alone degrades performance unless transfers are selected by receiver-specific utility. Despite transferring 1.9 times as much data as FOCON, Random-20 exhibits the lowest SR and the highest PAR-2.
On SAT Competition at 1000s (Table 23), Random-20 and LBD-20 solve 5 and 8 fewer instances than native Glucose-Syrup, respectively, whereas FOCON solves 5 additional instances and reduces PAR-2 by 4.27%. These results demonstrate the added value of receiver-aware clause selection under matched communication budgets.
3. [W3. Presentation and notation density]
Re. We have revised Sections 4 and 5 to establish algorithmic intuition before mathematical formalization. Section 4 now introduces three operations linked to Figure 2: formula conditioning, receiver-aware scoring, and support-aware budget control. We clarify the roles of literal and clause embeddings (hℓ, gj), explain how worker-state features (sw) characterize receiver dependence, and explicitly define all training losses (Eqs. 11-12). Section 5 now introduces the main theoretical results before their formal statements and summarizes their practical implications.
We hope that our responses have adequately addressed the reviewer's concerns and helped improve the quality of the paper. We welcome any further questions or discussion.