Extending CDCL to disjunctions of parity equations
Paul Beame, Glenn Sun · 2026
Read Extending CDCL to disjunctions of parity equations by Paul Beame, Glenn Sun (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-15002.txt.
Introduction
Paul Beame and Glenn Sun extend conflict-driven clause learning, the engine behind modern SAT solvers, to disjunctions of parity equations. Since CDCL proofs sit inside Resolution, problems hard for Resolution stay hard for CDCL. The pair's CDCL system for XNF formulas both produces proofs in the stronger Res system and polynomially simulates it under nondeterministic decisions and restarts. New inference rules carry clause-learning tricks, including 1-UIP learning, into the parity setting.
Catalog record
| CREATOR | Paul Beame, Glenn Sun |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 84020 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.15002
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Extending CDCL to disjunctions of parity equations Paul Beame, Glenn Sun Abstract Because CDCL produces proofs in the Resolution proof system, problems provably hard for Resolution are also provably hard for CDCL. Exponentially shorter proofs can sometimes be found using stronger proof systems such as Res ( ⊕ ) \Res(\oplus) , a generalization of Resolution to XNF formulas, whose constraints are disjunctions of parity equations (“linear clauses”) such as ( x ⊕ y ) ∨ ¬ ( y ⊕ z ) (x\oplus y)\lor\lnot(y\oplus z) . While some modern solvers like CryptoMiniSAT reason on Boolean clauses with separate parity equations, reasoning about more general linear clauses is less explored. We present CDCL ( ⊕ ) \CDCL(\oplus) , a generalization of CDCL to XNF formulas, and prove a bidirectional connection with Res ( ⊕ ) \Res(\oplus) : CDCL ( ⊕ ) \CDCL(\oplus) not only produces Res ( ⊕ ) \Res(\oplus) proofs, but also polynomially simulates Res ( ⊕ ) \Res(\oplus) given nondeterministic decisions and restarts, mirroring the classical relationship between CDCL and Resolution. Our key technical tool is a new set of inference rules for Res ( ⊕ ) \Res(\oplus) that helps us translate Resolution-based subroutines such as 1-UIP clause learning. Altogether, CDCL ( ⊕ ) \CDCL(\oplus) ’s parity reasoning includes branching on arbitrary parity equations, linear-algebraic reasoning during unit propagation, and learning linear clauses through conflict analysis. We provide a proof-of-concept implementation of CDCL ( ⊕ ) \CDCL(\oplus) called Xorcle , which includes adaptations of existing CDCL heuristics to XNF formulas and an extension of LRUP proof logging that we call LRUP ( ⊕ ) \LRUP(\oplus) . On a selected suite of benchmarks focusing on native XNF formulas, Xorcle outperforms existing solvers such as Kissat and CryptoMiniSAT. Additionally, on Tseitin formulas written in CNF, even without preprocessing, Xorcle ’s running time appears to scale nearly polynomially. University of Washington, USA and https://homes.cs.washington.edu/˜beame/site/ [email protected]://orcid.org/0000-0002-2666-3545University of Washington, USA and https://www.glennsun.com [email protected]://orcid.org/0000-0001-6510-2508 {CCSXML} <ccs2012> <concept> <concept_id>10003752.10003790.10003794</concept_id> <concept_desc>Theory of computation Automated reasoning</concept_desc> <concept_significance>500</concept_significance> </concept> <concept> <concept_id>10003752.10003777.10003785</concept_id> <concept_desc>Theory of computation Proof complexity</concept_desc> <concept_significance>500</concept_significance> </concept> </ccs2012> Parts of the source code were written with OpenAI Codex. All source code has been manually reviewed and tested. ccs Theory of computation Automated reasoning ccs Theory of computation Proof complexity keywords SAT, CDCL, Proof Complexity, Parity Reasoning † † runningauthor: P. Beame and G. Sun † † copyright: Paul Beame and Glenn Sun † † related-version: Conference Version : https://doi.org/10.4230/LIPIcs.SAT.2026.5 † † supplement: Software: https://github.com/glenn-sun/xorcle † † funding: This work was supported by NSF grant CCF-2422205. 1 Introduction Although conflict-driven clause learning (CDCL) is the dominant method today for SAT solving, it also has known limitations. Because CDCL produces proofs of unsatisfiability in the Resolution proof system, all problems with exponential lower bounds for Resolution proof size must also be hard for CDCL [ 6 ] . These limitations have led some solvers to incorporate ideas and fragments of stronger proof systems: For example, pseudo-Boolean solvers [ 10 , 45 , 54 ] use ideas from Cutting Planes proofs [ 28 , 15 , 17 ] , bounded variable addition [ 39 ] includes a fragment of Extended Resolution [ 52 ] , and CNF-XOR solvers [ 48 ] include some parity reasoning present in \Res(\oplus) (“ \Res -parity”) [ 32 , 33 ] . In contrast to these situations where solvers apply some aspects of the corresponding proof system, the relationship between classical CDCL and Resolution is bidirectional : not only does CDCL produce Resolution proofs, but with the right choice of heuristic decisions, any Resolution proof can also be turned into a CDCL execution [ 44 ] . More precisely, when we view the non-deterministic versions of CDCL solvers as proof systems in their own right, they can polynomially simulate (i.e., p -simulate [ 16 ] ) Resolution proofs. In this work, we define a CDCL-style algorithm that not only uses \Res(\oplus) reasoning, but also p -simulates all of \Res(\oplus) , providing the same precise understanding that we have for classical CDCL. \Res(\oplus) handles formulas with constraints involving XORs, which occur in a variety of areas including cryptanalysis and model counting [ 4 , 26 ] . A widely studied special case of \Res(\oplus) -based solving, known as CNF-XOR solving [ 5 , 13 , 34 , 35 ] , reasons with standard Boolean clauses in conjunction with parity equations : expressions involving only \oplus and negation, such as \lnot(x\oplus y\oplus z) , which can be written in equation form as [x\oplus y\oplus z=0] . CryptoMiniSAT [ 48 , 49 , 47 , 46 ] is a particularly important CNF-XOR solver, which both performs parity reasoning such as Gaussian elimination on parity equations and also detects short parity equations encoded in Boolean clauses. Although CNF-XOR solvers use \Res(\oplus) reasoning, \Res(\oplus) is more expressive in general. In \Res(\oplus) , instead of separate Boolean clauses and parity equations, there is only one kind of object that generalizes both: a linear clause is a disjunction of parity equations, such as (x\oplus y)\lor\lnot(y\oplus z) . A conjunction of linear clauses is sometimes called an XOR-OR-AND normal form (XNF) formula [ 1 ] . Not only is XNF more expressive than CNF-XOR, but \Res(\oplus) can also succinctly prove some problems, such as the bijective pigeonhole principle [ 32 , 29 ] , that have no known polynomial-length proofs in CNF-XOR systems. While XNF-solving has received less attention than CNF and CNF-XOR solving, some proposed algorithms for XNF-solving exist. In their original paper defining \Res(\oplus) [ 32 ] , Itsykson and Sokolov outlined a backtracking search procedure and proved that it is equivalent to the tree-like fragment of \Res(\oplus) . Horáček [ 31 ] defined an algebraic version of unit propagation in a proof system denoted SRES, inspired by Gröbner basis algorithms and equivalent to \Res(\oplus) , yielding an analogue of DPLL when combined with the algorithm of [ 32 ] . Two other proposed algorithms use different methods entirely: (1) a brute-force search through possible ways to apply SRES inference rules [ 30 ] , and (2) a graph-based approach to solve 2-XNF formulas (the XNF analog of 2-CNF formulas) called 2-Xornado [ 1 ] . Most recently, in work that is concurrent and independent of ours, Danner and Kreuzer [ 20 , 19 ] show how to use clause learning with XNF formulas. They also implement a restricted version that only makes Boolean decisions and inferences, and is designed for sparse parity equations. While our clause learning procedures are similar, we provide distinct contributions. On the theory side, we are able to prove that our algorithm p -simulates \Res(\oplus) , using a new characterization of \Res(\oplus) that also illuminates how our clause learning algorithm is a direct analogue of classical 1-UIP learning. On the practical side, our implementation efficiently uses dense parity equations for both decisions and inferred constraints, allowing greater flexibility and potential to improve over classical CDCL on CNF formulas. We also propose new XNF-specific heuristics and incorporate proof logging. Our contributions Our algorithm \CDCL(\oplus) (“CDCL-parity”) generalizes CDCL to XNF formulas, by branching on arbitrary parity constraints, performing linear-algebraic reasoning during unit propagation, and learning linear clauses through conflict analysis.