Automated Reencoding Meets Graph Theory

Benjamin Przybocki, Bernardo Subercaseaux, Marijn J. H. Heule · 2026

Read Automated Reencoding Meets Graph Theory by Benjamin Przybocki, Bernardo Subercaseaux, Marijn J. H. Heule (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-2603-27774.txt.

Introduction

Przybocki and co-authors explain a SAT preprocessing trick with graph theory. Bounded Variable Addition shrinks formulas in top solvers. Their portrait shows which 2-CNF encodings idealized BVA can build. Clause counts for reencoding get tight new bounds. A constant near 0.396 beats the naive factor of one. No method can push the constant below 0.25. At-most-one constraints need at least 3n minus 6 clauses. Real solvers hit that bound exactly.

Catalog record

CREATORBenjamin Przybocki, Bernardo Subercaseaux, Marijn J. H. Heule
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE109972
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.27774

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Automated Reencoding Meets Graph Theory Benjamin Przybocki, Bernardo Subercaseaux, Marijn J. H. Heule Abstract Bounded Variable Addition (BVA) is a central preprocessing method in modern state-of-the-art SAT solvers. We provide a graph-theoretic characterization of which 2-CNF encodings can be constructed by an idealized BVA algorithm. Based on this insight, we prove new results about the behavior and limitations of BVA and its interaction with other preprocessing techniques. We show that idealized BVA, plus some minor additional preprocessing (e.g., equivalent literal substitution), can reencode any 2-CNF formula with n n variables into an equivalent 2-CNF formula with ( lg ⁡ ( 3 ) 4 + o ⁡ ( 1 ) ) ​ n 2 lg ⁡ n (\tfrac{\lg(3)}{4}+o(1))\,\tfrac{n^{2}}{\lg n} clauses. Furthermore, we show that without the additional preprocessing the constant factor worsens from lg ⁡ ( 3 ) 4 ≈ 0.396 \tfrac{\lg(3)}{4}\approx 0.396 to 1 1 , and that no reencoding method can achieve a constant below 0.25 0.25 . On the other hand, for the at-most-one constraint on n n variables, we prove that idealized BVA cannot reencode this constraint using fewer than 3 ​ n − 6 3n-6 clauses, a bound that we prove is achieved by actual implementations. In particular, this shows that the product encoding for at-most-one, which uses 2 ​ n + o ⁡ ( n ) 2n+o(n) clauses, cannot be constructed by BVA regardless of the heuristics used. Finally, our graph-theoretic characterization of BVA allows us to leverage recent work in algorithmic graph theory to develop a drastically more efficient implementation of BVA that achieves a comparable clause reduction on random monotone 2-CNF formulas. 1 Introduction Providing a satisfactory explanation for the remarkable performance of SAT solvers in practice is a major theoretical challenge. Part of the difficulty of explaining this phenomenon, further detailed in the appropriately titled article “On the Unreasonable Effectiveness of SAT Solvers” by Vardi and Ganesh [ 9 ] , is that modern SAT solvers combine a variety of heuristics, preprocessing and inprocessing techniques, data structures, and so on. We posit that, to make progress on the overall question, we ought to better understand the power and limitations of each of these ingredients. In this paper, we home in on one of these components, namely, Bounded Variable Addition (BVA) [ 21 ] , a preprocessing technique that introduces auxiliary variables to reencode an input formula into an equisatisfiable formula with fewer clauses. In 2023, a successor of BVA named Structured BVA (SBVA) [ 10 ] , led the solver SBVA-CaDiCaL , whose primary innovation was to incorporate SBVA as preprocessing to the state-of-the-art solver CaDiCaL , to win the 1st place in the 2023 SAT Competition [ 4 ] . At the 2024 SAT Competition, many other solvers followed suit by including some variant of BVA as a preprocessing step, including the competition winner kissat-sc2024 [ 13 ] . BVA is now incorporated into the stable versions of CaDiCaL and Kissat under the name factor [ 6 ] . However, despite its empirically demonstrated utility, little is known about BVA and its variants from a theoretical point of view. For example, Biere, one of the authors of the original BVA paper, commented [ 5 ] : In [ 21 ] , we already realized that BVA reencodes [the direct encoding of the at-most-one constraint] into something better. Results were only empirical though and we did not analyze whether in principle BVA can turn the direct encoding into for instance the product or sequential counter encoding. In this paper, we develop a graph-theoretic framework for analyzing BVA, by means of which we can answer these and similar questions about the power and limitations of BVA. Furthermore, our framework allows us to draw on recent work in algorithmic graph theory to develop a drastically more efficient implementation of BVA. Our Results We focus on the behavior of BVA on 2-CNF subformulas. Many formulas of interest, including, e.g., most SAT competition formulas, contain a large 2-CNF subformula that can be reencoded more compactly, leading to faster runtimes. In Section 6 , we justify in more detail why the 2-CNF fragment not only captures the most important aspects of the theoretical analysis but also explains most of BVA’s empirical success. Our primary result is a characterization of which reencodings of a 2-CNF formula are achievable by BVA. Our characterization is in terms of rectifier networks [ 20 , 8 , 15 ] , a graph-theoretic notion that has been studied in the context of circuit complexity. Specifically, we show in Theorem 5 that there is a correspondence between reencodings achievable by BVA and what we call strict polarized rectifier networks . Our characterization holds for an idealized version of BVA that abstracts away implementation-specific heuristics. With this characterization in hand, we first study the class of 2-CNF formulas in general. By generalizing an old result of Nechiporuk [ 22 ] about rectifier networks, we prove the following: 1 1 1 All logarithms in this paper are base 2 unless otherwise specified. Theorem 1 (Informal) . Idealized BVA can reencode every 2-CNF formula with n variables to one with at most (1+o(1))\frac{n^{2}}{\lg n} clauses. Note that, without reencoding, 2-CNF formulas can have \Theta(n^{2}) clauses. We also show that the bound from Theorem 1 is sharp, in the sense that there is some 2-CNF formula that idealized BVA reencodes with at least (1-o(1))\frac{n^{2}}{\lg n} clauses. On the other hand, we describe a simplification routine that one can run before BVA (“pre-preprocessing”), which consists of equivalent literal substitution and a weaker form of failed literal elimination [ 11 ] , and this simplification step improves the worst-case performance of idealized BVA: Theorem 2 (Informal) . Idealized BVA with simplification can reencode every 2-CNF formula with n variables to one with at most (\frac{\lg(3)}{4}+o(1))\frac{n^{2}}{\lg n} clauses. This bound is also sharp. Furthermore, we show that for every reencoding method whose output is 2-CNF, there is some 2-CNF formula that it reencodes with at least (\frac{1}{4}-o(1))\frac{n^{2}}{\lg n} clauses. Thus, with respect to worst-case analysis, idealized BVA is optimal up to a constant factor. An important subset of 2-CNF formulas is the monotone (or antitone) 2-CNF formulas. For example, a direct encoding for finding an independent set in a graph G would include, for every edge \{u,v\}\in E(G) , a clause (\overline{x_{u}}\lor\overline{x_{v}}). We can actually improve the bound from Theorem 1 for monotone 2-CNF formulas: Theorem 3 (Informal) . Idealized BVA can reencode every monotone 2-CNF formula with n variables to one with at most (\frac{1}{4}+o(1))\frac{n^{2}}{\lg n} clauses. This bound is sharp, not merely for idealized BVA but for arbitrary reencoding methods whose output is 2-CNF. Next, we study BVA’s performance on a particular class of 2-CNF formulas, namely the direct encoding of the at-most-one constraint on n variables: \textsf{AtMostOne}(x_{1},\dots,x_{n})\coloneqq\bigwedge_{1\leq i<j\leq n}(\overline{x_{i}}\lor\overline{x_{j}}). Manthey, Heule, and Biere [ 21 ] observed experimentally that their implementation of BVA reencodes \textsf{AtMostOne}(x_{1},\dots,x_{n}) into 3n-6 clauses. We prove in Theorem 11 that, given their heuristics, BVA always achieves this bound. On the other hand, via a combinatorial analysis of strict rectifier networks, we show a matching lower bound, regardless of the heuristics used: Theorem 4 (Informal) . Idealized BVA cannot encode \textsf{AtMostOne}(x_{1},\dots,x_{n}) using fewer than 3n-6

Read the complete text