A Non-CDCL SAT Solver with Early Conflict Detection: The Watched

Computer Science > Logic in Computer Science
[Submitted on 25 Aug 2026]
Title:A Non-CDCL SAT Solver with Early Conflict Detection: The Watched-Literal-Based CSFLOC Solver
View PDFAbstract:CSFLOC is a non-CDCL SAT decision procedure based on counting subsumed full-length ordered clauses. The classical CSFLOC loop traverses the ordered space of full-length clauses by a monotone counter: if the current full-length clause is not subsumed by the input formula, its negation is a satisfying assignment; otherwise, a subsuming clause determines a counter jump. The main bottleneck is the repeated search for such a subsuming clause. This paper presents CSFLOC-WL, and its current implementation CSFLOC-WL3, in which this search is replaced by watched-literal prefix propagation over the negation of the current full-length clause represented by the counter. The central mechanism is early conflict detection: if propagation under a common prefix derives opposite unit consequences for the same variable, then the two reason clauses are resolved immediately and the resolvent is used as a new counter-jump cause. The resulting solver is not a CDCL solver: it has no CDCL decision tree, no restart policy, and no first-UIP backjumping loop. It remains a counter-guided full-length-clause-counting solver, but it imports the watched-literal data structure and reason clauses as engineering tools for discovering jumps. Experiments on selected UNSAT SATLIB instances compare CSFLOC-WL3 with CSFLOC21TU and CaDiCaL 3.0.0. The results are mixed: CSFLOC-WL3 is strong on several random 3-SAT instances near the random-3-SAT satisfiability threshold, whereas CSFLOC21TU remains faster on several structured cases, apparently because it contains a more mature cache mechanism that is not yet present in CSFLOC-WL3.
Submission history
From: EPTCS [view email] [via EPTCS proxy][v1] Tue, 25 Aug 2026 08:49:28 UTC (36 KB)
References & Citations
Loading...
Bibliographic and Citation Tools
Bibliographic Explorer (What is the Explorer?)
Connected Papers (What is Connected Papers?)
Litmaps (What is Litmaps?)
scite Smart Citations (What are Smart Citations?)
Code, Data and Media Associated with this Article
alphaXiv (What is alphaXiv?)
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
DagsHub (What is DagsHub?)
Gotit.pub (What is GotitPub?)
Hugging Face (What is Huggingface?)
ScienceCast (What is ScienceCast?)
Demos
Recommenders and Search Tools
Influence Flower (What are Influence Flowers?)
CORE Recommender (What is CORE?)
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

Facts Only

* CSFLOC is a non-CDCL SAT decision procedure based on counting subsumed full-length ordered clauses.
* The classical CSFLOC loop traverses the space of full-length clauses using a monotone counter.
* If a full-length clause is not subsumed, its negation is a satisfying assignment.
* Subsuming clauses determine counter jumps in the classical method.
* CSFLOC-WL replaces the search for subsuming clauses with watched-literal prefix propagation over the negation of the current full-length clause.
* Early conflict detection resolves reason clauses immediately if propagation yields opposite unit consequences for the same variable, using the resolvent as a new counter-jump cause.
* CSFLOC-WL is not a CDCL solver and lacks a decision tree or first-UIP backjumping loop.
* Experiments compared CSFLOC-WL3 with CSFLOC21TU and CaDiCaL 3.0.0 on UNSAT SATLIB instances.
* CSFLOC-WL3 was strong on random 3-SAT instances near the satisfiability threshold.
* CSFLOC21TU was faster on several structured cases due to a cache mechanism.

Executive Summary

CSFLOC is a non-CDCL SAT decision procedure that operates by counting subsumed full-length ordered clauses. The classical CSFLOC method uses a monotone counter to traverse the space of full-length clauses, where if a clause is not subsumed, its negation implies a satisfying assignment; otherwise, a subsuming clause dictates a counter jump. The primary computational bottleneck in the classical approach is repeatedly searching for these subsuming clauses. CSFLOC-WL addresses this by replacing the search with watched-literal prefix propagation over the negation of the current full-length clause being tracked by the counter. A key innovation is early conflict detection: if propagation results in opposite unit consequences for the same variable, the reason clauses are immediately resolved, and the resulting resolvent triggers a new counter-jump. This method does not incorporate CDCL features like decision trees or backjumping but uses watched-literal data structures to guide conflict discovery. Experiments comparing CSFLOC-WL3 against CSFLOC21TU and CaDiCaL 3.0.0 showed mixed results; CSFLOC-WL3 performed well on random 3-SAT instances near the satisfiability threshold, while CSFLOC21TU was faster on structured cases due to a more mature caching mechanism.

Full Take

The work introduces a specialized optimization—watched-literal prefix propagation combined with immediate conflict resolution—to tackle the inherent search inefficiency of counter-guided full-length-clause counting algorithms like CSFLOC. The core implication lies in engineering a data structure (watched literals) and reasoning mechanism (prefix propagation) to predict potential jumps, moving away from brute-force subsuming searches. The performance comparison suggests that while algorithmic elegance is demonstrated on random instances near thresholds, practical speed on structured problems might depend more heavily on sophisticated caching or memory management strategies (as seen in CSFLOC21TU). This highlights a fundamental tension in SAT solving: whether pure theoretical efficiency translates to real-world speed, depending heavily on the specific problem structure and the implementation of auxiliary structures. The resulting solver remains fundamentally different from mainstream CDCL paradigms, emphasizing that achieving better performance might require accepting algorithmic restrictions over complete decision-making features, pushing the boundary between theoretical complexity reduction and practical heuristic gain.

Sentinel — Human

Confidence

This text exhibits the dense, specific, and structured language typical of peer-reviewed computer science research, suggesting it is a human-authored academic submission rather than synthetic content.

Signals Detected

Sentence length variance is present, though the text is highly technical and dense.

The text flows logically from defining a problem (CSFLOC) to proposing a solution (CSFLOC-WL) and presenting experimental results, indicating coherent structuring.

The presentation of the mechanism, comparison, and results follows a standard academic paper structure; no immediate evidence of verbatim repetition.

References to specific mathematical/algorithmic concepts (CDCL, SATLIB, UNSAT) appear contextually appropriate for the field.

Human Indicators

The inclusion of an arXiv submission format, specific references to prior work (CSFLOC21TU, CaDiCaL 3.0.0), and the nuanced presentation of mixed experimental results strongly suggest an authentic academic context.

The technical density and the focus on subtle performance differences between algorithmic variants are characteristic of genuine research reporting.