💻 computer science

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

This paper introduces CSFLOC-WL, a non-CDCL SAT solver that accelerates the original counter-guided full-length clause counting approach by integrating watched-literal prefix propagation and early conflict detection to efficiently identify counter jumps, demonstrating competitive performance on random 3-SAT instances despite lacking the mature caching mechanisms of its predecessor.

Original authors: Gábor Kusper (Eszterházy Károly Catholic University)

Published 2026-08-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Gábor Kusper (Eszterházy Károly Catholic University)

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of computer science, there is a fundamental puzzle known as the satisfiability problem. Imagine a complex lock with thousands of tumblers, each representing a variable that can be set to one of two states. The goal is to find a single combination of settings that opens the lock, satisfying a long list of rules that dictate how the tumblers must align. If no such combination exists, the lock is permanently jammed. This problem is central to everything from verifying the safety of microchips to planning logistics for global shipping. For decades, the most powerful tools for solving this puzzle have relied on a strategy of making a guess, following the logical consequences of that guess, and when a contradiction is found, learning from the mistake to avoid it in the future. This approach, known as conflict-driven learning, has become the standard, highly refined engine behind modern problem-solving software.

However, not every path through the forest of possibilities requires the same map. A researcher has been exploring a different route entirely. Instead of guessing and learning from errors, their method treats the problem as a systematic count. They imagine every possible setting of the lock tumblers as a long line of binary numbers, counting from zero up to the maximum. The goal is to prove that every single number in that line is blocked by at least one rule, meaning no solution exists. The challenge has always been that checking each number one by one is impossibly slow. The researcher needed a way to skip huge chunks of the line at once, jumping over millions of impossible combinations in a single step.

In their latest work, the researcher introduced a new version of their solver, called CSFLOC-WL3, which changes how it finds these massive jumps. The core idea is to look at the rules not as static barriers, but as active guides. As the solver counts through the possibilities, it assigns values to the variables in a fixed order, much like filling out a form from top to bottom. At each step, it checks if the current partial assignment forces any rule to become a single, unavoidable requirement. If a rule is forced to be true or false by the choices made so far, the solver can immediately see that the current path is blocked. The innovation lies in how they track these rules. They use a technique called "watched literals," which is like having a dedicated monitor for the most critical parts of each rule. These monitors only alert the solver when a rule is about to become critical, allowing the system to ignore thousands of irrelevant checks and focus only on the moments where a decision matters.

The most significant discovery in this new approach is a mechanism for spotting conflicts early. In the old method, the solver might walk all the way to the end of a long chain of logic before realizing it had hit a contradiction. With the new system, if the solver finds that the same variable is being forced to be both true and false by two different rules under the same starting conditions, it stops immediately. It then combines the reasons for these two opposing forces into a single, new rule. This new rule acts as a powerful signpost, telling the solver that it can skip not just the current number, but a massive block of numbers that share the same starting pattern. This allows the solver to leap over vast territories of the search space that would have taken a long time to traverse one by one.

The researcher tested this new solver against established competitors on a variety of difficult, unsolvable problems. The results were revealing. On a set of random, unstructured problems, the new solver was dramatically faster, often solving instances in seconds that took the older version minutes or even timed out completely. In these cases, the ability to detect conflicts early and make large jumps proved to be a game-changer. However, on more structured, complex problems, the new solver was slower than its predecessor. The reason was not a flaw in the logic, but a missing piece of engineering. The older solver had a sophisticated memory system that remembered past discoveries and reused them, a feature the new version had not yet fully integrated. The new solver was excellent at finding new paths, but it lacked the library of past shortcuts that the older version possessed.

This work does not claim to have replaced the standard methods used by most computers today. Instead, it demonstrates that a different way of thinking about the problem—one based on systematic counting rather than guessing and backtracking—can be highly effective when equipped with the right tools. The study shows that by borrowing a specific tracking technique from the dominant approach and applying it to this counting method, it is possible to solve certain types of problems with remarkable speed. The path forward is clear: by combining the new early-detection speed with the mature memory systems of the older generation, the researcher believes they can build a solver that is powerful across a wider range of challenges. The work stands as a proof that there are still unexplored territories in the logic of computing, and that sometimes, the best way to move forward is to change the direction of the search entirely.

Technical Summary: A Non-CDCL SAT Solver with Early Conflict Detection

Problem Statement
Propositional Satisfiability (SAT) is a central decision problem in computer science. While high-performance solvers predominantly follow the Conflict-Driven Clause Learning (CDCL) paradigm, this paper investigates an alternative approach: the CSFLOC solver. CSFLOC is a non-CDCL decision procedure based on counting subsumed full-length ordered clauses. The core mechanism involves traversing the ordered space of $2^n$ full-length clauses (clauses containing exactly one literal for every variable) using a monotone counter. If the current full-length clause is not subsumed by the input formula, its negation constitutes a satisfying assignment. If all $2^n$ clauses are subsumed, the formula is unsatisfiable.

The primary bottleneck in the original CSFLOC implementation is the repeated search for a subsuming clause for the current full-length clause. This search requires checking if any clause in the input formula is a subset of the current candidate clause. While previous engineering improvements (such as last-positive-bit observations and learned-cause caches) reduced scanning, the fundamental operation remained a direct subsumption test.

Methodology: CSFLOC-WL and Early Conflict Detection
The paper introduces CSFLOC-WL, a variant that replaces the explicit subsumption search with watched-literal prefix propagation. The solver maintains the global CSFLOC counter loop but changes how the next counter increment (jump) is discovered.

Watched-Literal Prefix Propagation:
Instead of searching for a clause $D \subseteq C$ (where $C$ is the current full-length clause), the solver assigns variables according to the negation of $C$ (denoted $\alpha$ ) in a fixed order. It utilizes the standard two-watched-literal data structure to propagate unit consequences under this prefix assignment.
- A clause $D$ becomes unit when the propagation reaches the index of its last variable ($last(D)$).
- If the propagation derives a unit literal $u$ that belongs to the current full-length clause $C$ , the reason clause for $u$ serves as a valid counter-jump cause.
Early Conflict Detection (ECD):
The central innovation is the detection of conflicts before the propagation reaches the level of the last variable. If, under a common prefix, propagation derives opposite unit consequences ( $x_i$ and $\bar{x}_i$ ) for the same variable $x_i$ with reason clauses $P$ and $N$ , the solver immediately resolves $P$ and $N$ on $x_i$ .
- Theorem 1 (Early Conflict Detection): The resolvent $D = Res_i(N, P)$ is entailed by the formula and is a subset of the current full-length clause. Crucially, if $D$ is non-empty and non-tautological, its last variable index is strictly less than $i$ .
- This allows the counter to jump to a boundary determined by $last(D)$, potentially skipping a larger block of the search space than waiting for the propagation to reach level $i$ would allow.
Non-CDCL Architecture:
The paper emphasizes that CSFLOC-WL is not a CDCL solver. It does not maintain a decision tree, does not perform backjumping in the CDCL sense, and has no restart policy. The global control remains a monotone traversal of the full-length clause space. The watched-literal structure and resolution are used strictly as engineering tools to discover "jump causes" (clauses that justify skipping intervals of the counter).

Key Contributions
The paper makes three specific contributions:

Formulation: It reformulates the CSFLOC subsumption search as watched-literal prefix propagation over the negation of the current full-length clause.
Theoretical Proof: It states and proves the Early Conflict Detection theorem, demonstrating that resolving opposite unit consequences under a common prefix yields a sound counter-jump cause that may allow for earlier jumps than the standard last-positive-bit search.
Implementation and Evaluation: It presents CSFLOC-WL3, a Java prototype implementation, and compares it against:
- CSFLOC21TU: A mature, cache-oriented CSFLOC implementation (without watched literals).
- CaDiCaL 3.0.0: A state-of-the-art CDCL solver.
- The evaluation includes selected UNSAT instances from SATLIB (random 3-SAT, pigeonhole, Dubois, ssa, etc.).

Experimental Results
The experiments on selected UNSAT SATLIB instances yield mixed results, highlighting both the potential and current limitations of the approach:

Random 3-SAT (uuf family): CSFLOC-WL3 demonstrates significant strength on random instances near the satisfiability threshold. On instances like uuf150-01, uuf175-01, and uuf200-01, CSFLOC-WL3 is substantially faster than CSFLOC21TU (which times out on the larger instances) and competitive with or faster than CaDiCaL. Internal statistics show that CSFLOC-WL3 reduces the number of main-loop iterations by orders of magnitude (e.g., from ~164,000 to ~1,200 on uuf100-01) due to large jumps generated by early conflict detection.
Structured Instances: On structured benchmarks (pigeonhole, Dubois, ssa, bf), CSFLOC21TU generally outperforms CSFLOC-WL3. The paper attributes this to the mature learned-cause cache in CSFLOC21TU, which effectively reuses derived causes. CSFLOC-WL3 currently lacks an equivalent caching mechanism; its reliance on active causes and propagation overhead makes it slower when the prefix propagation does not yield sufficiently large jumps.
Comparison with CaDiCaL: CaDiCaL remains faster on most structured instances. CSFLOC-WL3 is not presented as a general replacement for CDCL solvers but as a viable alternative family that competes well on specific random instances.

Significance and Claims
The paper modestly claims that CSFLOC-WL3 is a step in the development of an alternative solver family, not a replacement for CDCL. Its significance lies in:

Demonstrating that watched-literal propagation and early conflict detection can be effectively adapted to a counter-guided, full-length-clause-counting framework.
Showing that this approach can outperform previous non-CDCL methods (CSFLOC21TU) and even CDCL solvers on specific random 3-SAT instances.
Identifying a clear engineering path forward: the integration of a CSFLOC21TU-style learned-cause cache into the watched-literal implementation. The author concludes that combining the jump-generation power of ECD with the reuse efficiency of a mature cache is the necessary next step to make the solver competitive across a broader range of benchmarks.

The paper also documents two new variable-renaming strategies, T (two-SAT-prefix oriented) and U (unit-oriented), which are part of the current engineering picture but are not the primary focus of the theoretical contribution.

Technical Summary: A Non-CDCL SAT Solver with Early Conflict Detection

More like this