💻 computer science

Extending CDCL to disjunctions of parity equations

This paper introduces $\text{CDCL}(\oplus)$ , a generalization of the Conflict-Driven Clause Learning framework to XNF formulas that supports parity reasoning and polynomially simulates the $\text{Res}(\oplus)$ proof system, demonstrating significant performance improvements over existing solvers on benchmarks involving parity constraints.

Original authors: Paul Beame, Glenn Sun

Published 2026-05-15

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Paul Beame, Glenn Sun

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

Imagine you are trying to solve a massive, tangled knot of logic puzzles. For decades, the best tool for untangling these knots has been a method called CDCL (Conflict-Driven Clause Learning). Think of CDCL as a very smart detective who makes guesses, follows the clues, and when they hit a dead end (a contradiction), they learn a valuable lesson from that mistake so they don't make the same error again.

However, this detective has a blind spot. They are excellent at solving puzzles involving simple "True/False" statements, but they struggle when the clues involve parity equations—mathematical statements about whether a group of items adds up to an even or odd number (like checking if the number of red marbles in a bag is even).

This paper introduces a new, upgraded detective named CDCL(⊕) (pronounced "CDCL-parity") and a software prototype called Xorcle. Here is how it works, using simple analogies:

1. The Problem: The "Even/Odd" Blind Spot

Standard CDCL detectives look at clues like "If A is true, then B must be false." But some problems are written in a language of "If the number of true items in this group is even..."

The Old Way: Previous attempts to solve these problems tried to translate the "even/odd" math into simple True/False clues. This is like trying to describe a complex 3D sculpture by only drawing flat, 2D shadows. It works, but the drawing becomes huge and messy, making the detective very slow.
The New Way: CDCL(⊕) speaks the "even/odd" language natively. It doesn't translate the clues; it understands them directly.

2. The Superpower: Linear Algebra as a Tool

When the new detective hits a dead end, they don't just look at the specific clues that caused the problem. They use linear algebra (a branch of math dealing with equations) to mix and match clues.

The Analogy: Imagine you have two clues: "The sum of A and B is even" and "The sum of B and C is even." A standard detective might get stuck. The new detective realizes that if you add these two clues together, the "B" cancels out, leaving you with a brand new, powerful clue: "The sum of A and C is even."
This allows the detective to see patterns and shortcuts that the old method completely misses.

3. The Theory: Proving the Detective is Smarter

The authors didn't just build a faster detective; they proved mathematically that this new detective is universally superior for these types of puzzles.

They showed that CDCL(⊕) can simulate any proof that the "parity logic" system (called Res(⊕)) can produce.
The Metaphor: It's like proving that a master chef (CDCL(⊕)) can cook every dish a specific type of grill (Res(⊕)) can cook, but the chef can also do it much faster if they are allowed to make a few strategic choices (restarts and decisions).

4. The Prototype: Xorcle

The team built a working version of this detective called Xorcle (a play on "XOR" and "Oracle").

The Results: They tested Xorcle against the current best detectives (like Kissat and CryptoMiniSAT) on a variety of puzzles.
- On Native Parity Puzzles: Xorcle was significantly faster, solving problems that the others struggled with or couldn't finish in time.
- On "Hard" Standard Puzzles: Even on puzzles that were written in the old "True/False" format (specifically a type called Tseitin formulas), Xorcle was surprisingly fast. While other detectives took an exponentially long time (imagine waiting for the universe to end), Xorcle solved them in a time that grew almost linearly (like walking a straight line).

5. How It "Thinks" (The Mechanics)

To make this work, the authors had to invent new rules for how the detective learns:

Watching Equations: Instead of just watching single variables (like "Is A true?"), the detective watches entire groups of equations.
Basis Changes: When the detective needs to learn from a mistake, they don't just write down a new rule. They rearrange their entire understanding of the problem (changing the "basis") to isolate exactly which part of the math caused the error. This is like a mechanic who, instead of just saying "the engine is broken," reorganizes the engine parts to see exactly which gear is stripped.

Summary

In short, this paper presents a new way to solve logic puzzles that involve "even vs. odd" math. By upgrading the standard solving algorithm to natively understand these equations, the authors created a tool (Xorcle) that is theoretically proven to be more powerful and empirically shown to be much faster than current state-of-the-art solvers on specific, difficult types of problems. They also created a new way to record the detective's thought process (proof logging) so that others can verify the solution.

Technical Summary: Extending CDCL to Disjunctions of Parity Equations

Problem Statement

Conflict-Driven Clause Learning (CDCL) is the dominant method for SAT solving, but it is fundamentally limited by the Resolution proof system. Problems that require exponential proof size in Resolution (such as Tseitin formulas or the bijective pigeonhole principle) are provably hard for CDCL. While some solvers incorporate fragments of stronger proof systems—such as pseudo-Boolean solvers using Cutting Planes or CNF-XOR solvers handling parity equations—these approaches often treat parity reasoning as a separate module or restrict themselves to specific normal forms (e.g., CNF-XOR).

The specific gap addressed by this work is the lack of a CDCL-style algorithm that natively handles XNF (XOR-OR-AND Normal Form) formulas. XNF formulas consist of conjunctions of linear clauses, which are disjunctions of parity equations (e.g., $(x \oplus y) \lor \neg(y \oplus z)$ ). While the Res(⊕) proof system (Resolution generalized to XNF) is known to be exponentially stronger than Resolution for certain problems, existing solvers do not fully integrate Res(⊕) reasoning into the CDCL loop, nor do they provide a theoretical proof that a CDCL-style algorithm can polynomially simulate Res(⊕).

Methodology

The authors propose CDCL(⊕), a generalization of the CDCL algorithm designed to operate directly on XNF formulas. The methodology relies on three core components:

New Inference Rules for Res(⊕):
The authors introduce a new characterization of the Res(⊕) proof system that replaces the standard resolution and weakening rules with addition and change of basis.
- Addition: From $C \lor f$ and $D \lor g$ , deduce $C \lor D \lor (f + g)$ .
- Change of Basis: From $C$ , deduce any $D$ such that $C \equiv D$ (semantically equivalent).
  Crucially, they define an affine resolution rule where equations are "isolated" (via change of basis) to allow cancellation via addition. This eliminates the need for the exponential search space associated with the weakening rule, enabling a polynomial simulation.
Unit Propagation with Linear Algebra:
Unlike classical CDCL, which propagates based on literal assignments, CDCL(⊕) performs unit propagation using linear algebra over $\mathbb{F}_2$ .
- The solver maintains a set of known units (equations) $U$ .
- Propagation checks if a linear clause $C$ implies a new equation $f$ or a contradiction ($1$) given $U$ .
- This is implemented by reducing the "linear negation" of a clause (the subspace of assignments falsifying the clause) against the span of $U$ . If the negation of the clause is contained within the span of $U$ plus a single equation $f$ , then $f$ is deduced.
Clause Learning via Conflict Analysis:
The paper adapts the 1-UIP (First Unique Implication Point) clause learning strategy to the XNF setting. Since implication graphs do not translate directly to linear equations, the learning algorithm operates semantically:
- It starts with the conflict clause (the reason for the contradiction).
- It iteratively applies change of basis to isolate the equation responsible for the most recent decision.
- It applies the addition rule to combine the isolated clause with the reason for the conflict, effectively canceling out the decision variable.
- This process repeats until an asserting clause is found (a clause that forces a propagation at the current decision level).

Key Contributions

Theoretical Contributions

Bidirectional Connection: The paper proves that CDCL(⊕) not only produces Res(⊕) proofs but also polynomially simulates the Res(⊕) proof system, given nondeterministic decisions and restarts. This mirrors the classical relationship between CDCL and Resolution.
New Proof System Characterization: The authors provide a new set of inference rules (addition and change of basis) that are polynomially equivalent to Res(⊕) but lack the weakening rule, making them suitable for algorithmic implementation.
Input Res(⊕) Equivalence: The paper proves that the unit propagation in CDCL(⊕) is equivalent to a fragment of Res(⊕) known as input Res(⊕), generalizing a known result for classical CDCL.
Improved Simulation Factor: The proof of simulation improves the polynomial factor for the classical CDCL/Resolution relationship (matching the result in [7] with a simpler argument) by optimizing how decompositions of clauses are absorbed.

Practical Contributions

Xorcle Implementation: The authors present Xorcle, a proof-of-concept solver for CDCL(⊕).
- It implements efficient linear algebra over $\mathbb{F}_2$ using bit-packing.
- It introduces CSIDS (Clause State Independent Decaying Sum), a new heuristic for clause selection that generalizes VSIDS and CMTF to the XNF context.
- It introduces LRUP(⊕), an extension of the LRUP proof logging format to support parity expressions.
Heuristics for XNF: The paper details adaptations for watched structures (cycling through clauses rather than maintaining complex watchlists due to linear dependencies), decision procedures (branching on random equations from a clause's negation), and phase selection (preferring to falsify clauses).

Experimental Results

The authors evaluated Xorcle on a suite of benchmarks including:

Ascon-128: A cryptography-related 2-XNF family.
Random and Restricted k-XNFs: Synthetic formulas with varying numbers of variables and equations.
Tseitin Formulas: CNF-encoded parity problems known to be hard for Resolution.

Key Findings:

Performance on XNF: Xorcle outperformed existing solvers (Kissat, CryptoMiniSAT, and 2-Xornado) on native XNF benchmarks. Notably, it outperformed 2-Xornado (a dedicated 2-XNF solver) on Ascon-128 instances despite using general XNF reasoning.
Performance on Tseitin Formulas: On Tseitin formulas encoded in CNF, Xorcle demonstrated nearly polynomial scaling in running time, whereas Resolution-based solvers are known to require exponential time. This was achieved without preprocessing, relying solely on the core CDCL(⊕) reasoning.
Decision Quality: Xorcle required significantly fewer decisions than competing solvers, suggesting that the parity-based branching and deduction mechanisms are more effective for these problem classes.

Significance and Claims

The paper claims that CDCL(⊕) provides the first rigorous theoretical framework and practical implementation that fully integrates parity reasoning into the CDCL paradigm.

Theoretical Significance: It establishes that the limitations of CDCL are not inherent to the algorithmic structure but to the underlying proof system (Resolution). By shifting to Res(⊕), CDCL can theoretically solve problems that are exponentially hard for standard CDCL.
Practical Significance: The results suggest that native XNF solving is viable and potentially superior to converting XNF to CNF or CNF-XOR. The ability to solve Tseitin formulas in nearly polynomial time without preprocessing highlights the potential of parity reasoning to overcome known hardness barriers in SAT solving.
Future Directions: The authors modestly note that Xorcle is a proof-of-concept. It currently lacks several standard CDCL optimizations (e.g., clause deletion, advanced restarts, dynamic heuristics) and does not yet fully generalize concepts like "1-UIP" or "clause minimization" to the semantic XNF setting. The work opens the door for further research into heuristics specifically targeting CNF formulas that implicitly require parity reasoning.