Metraipolis › archive › dc_ce2cd60d8c52

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.41290
License (as archived)
CC0-1.0
Archived
2026-11-02T07:38:50.843Z
SHA-256 of the archived text
eea9baca1631141efe5a1084505975e41d9dbafe6fbd5b21e1e9733fff944f00
Stable URL of this page
https://metraipolis.com/documento/dc_ce2cd60d8c52

How to cite

SAT-ACT: Learning CDCL Branching from Outcome-Derived Action Preferences — arXiv:2610.41290 — arXiv (en), https://arxiv.org/abs/2610.41290 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ce2cd60d8c52 (Metraipolis archive dc_ce2cd60d8c52, sha256 eea9baca1631141efe5a1084505975e41d9dbafe6fbd5b21e1e9733fff944f00)
BibTeX
@misc{dcce2cd60d8c52,
  title = {SAT-ACT: Learning CDCL Branching from Outcome-Derived Action Preferences — arXiv:2610.41290},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.41290},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ce2cd60d8c52; sha256 eea9baca1631141efe5a1084505975e41d9dbafe6fbd5b21e1e9733fff944f00},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41290. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.AI, nuovi lavori del giorno).
Categorie arXiv: Artificial Intelligence (cs.AI) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2610.41290 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-02T07:37:00.476Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).