Many hard satisfiability problems contain parity constraints, rules of the form "an odd number of these variables is true." They show up in cryptanalysis, in arithmetic circuits, and most heavily in approximate model counters, which estimate how many solutions a formula has by adding random parity constraints and counting the survivors. Standard clause-learning SAT solvers handle parity badly. The fix is to keep parity constraints as a matrix over the two-element field and run Gauss-Jordan elimination inside the search, which is the design of CryptoMiniSat. Even with that engine, parity handling can still consume most of the runtime. Separately, constraint-programming researchers learned to make table constraints fast by storing, in machine words, which candidate tuples are still alive. Their key tool is the reversible sparse bit-set, which keeps only the non-zero words of a bitset in a compact index. When the search backtracks, one integer is restored instead of the bitset being recomputed.
This note proposes carrying that bookkeeping trick into the parity engine of a SAT solver. The solver would maintain, for each parity row, a reversible sparse index of the words that still contain unassigned variables, and for each matrix a reversible set of rows that can still propagate or conflict. Propagation then touches only live words and live rows, and backtracking costs constant time. The central hypothesis is specific and testable. If this bookkeeping cuts the per-call cost of the parity engine enough, the eager scheduling that Engineering an Efficient PB-XOR Solver found too expensive becomes affordable. That would change which coupling strategy is best for mixed pseudo-Boolean and parity formulas.
What exists and where the gap is
The parity-in-SAT line has already brought word-level parallelism into the elimination engine. BIRD lets the solver's formula simplifications ("inprocessing") run on parity constraints written out as clauses. It then recovers the parity constraints with bitfield signatures and Bloom filters, and it motivates this work by showing that clause-only handling stalls. Tinted, Detached, and Lazy CNF-XOR Solving (BIRD2) packs assignment state into bitfields and uses population counts for propagation. It detaches clauses that the matrix already covers, and it builds explanation clauses only when conflict analysis asks for them. Gaussian Elimination Meets Maximum Satisfiability lays out its matrices in interlaced bit-packed form with SIMD row additions, reporting a cut in elimination time of "up to a third." It keeps a second matrix to produce explanations and splits the system into independent components.
All three speed up the arithmetic on rows. None of them changes which words and rows get scanned, or what must be undone when the search retreats. Those two costs are exactly what the table-filtering line solved. Extending Compact-Table to Negative and Short Tables and Compact-MDD keep live tuples or decision-diagram arcs in reversible sparse bit-sets and skip zero words entirely. Optimizing Simple Tabular Reduction with a Bitwise Representation shows how large the gain from word-level live-set tracking can be over tuple-by-tuple scans: up to 25x over STR3. Those papers supply the method. The parity papers supply the setting and the bottleneck.
One tempting variant is ruled out on first principles. That variant would encode each parity constraint directly as a bit-parallel table, the file's "Gap 2." For a single parity constraint, full arc consistency is trivial: nothing can be deduced until exactly one variable is unassigned, and a counter detects that. A table of $2^{k-1}$ tuples would do the same work more expensively. Tables only add propagation strength over conjunctions of constraints, and elimination already provides that for linear systems. So this note puts the table-filtering idea into the elimination engine's bookkeeping, not into the constraint representation.
Core Claim
We claim two things. First, in hashing-based counting, much of the parity-engine time left after BIRD2 goes to visiting rows and words that can no longer produce anything, together with trail-driven state repair after backjumps. Second, reversible sparse bookkeeping removes this cost without changing which deductions are made. The consequence we care most about follows from this. Engineering an Efficient PB-XOR Solver compared ways of coupling a pseudo-Boolean solver to elimination. It found that calling elimination after every propagation (Eager-GJE) loses to its invocation overhead, while delaying the call (Lazy-GJE) detects conflicts too late. It settled on translating parity deductions into learned pseudo-Boolean constraints (Mixed-Watches). We predict that with cheap invocations, eager calling combined with BIRD2-style lazy explanations matches or beats Mixed-Watches.
This would also resolve an apparent contradiction in the literature. BIRD2's "laziness" concerns when explanations are built. LinPB's "laziness" concerns when conflicts are detected. The two can be separated: eager detection with lazy explanations.
Research Program
The engine will be built inside CryptoMiniSat's elimination module so it plugs into the ApproxMC and UniGen pipelines, and a port will be made into LinPB's pseudo-Boolean core. Each row of the reduced matrix keeps two things. The first is its packed coefficient words. The second is a reversible sparse index of the words in which the row still has an unassigned variable, together with a cached "second unassigned word." That cache is the analogue of Compact-Table's residual supports and of watched literals. When a variable is assigned, only the rows that contain its column are visited, and only their live words are scanned. A row whose live index drops to one word with one set bit propagates. A row whose live index drops to zero either checks consistency or raises a conflict. A matrix-level reversible sparse set tracks rows still capable of propagating, so that satisfied or fully assigned rows cost nothing until a backtrack revives them. Revival is a single limit-pointer restore per decision level.
Row operations that change pivots are equivalence-preserving and are not undone. Only the liveness indices are trailed. Explanations stay lazy, built on demand from the explanation matrix as in BIRD2 and GaussMaxHS.
Before any engineering, the analysis step comes first. We will instrument the unmodified BIRD2 engine to split parity time into four parts: row-word scanning, pivot replacement, explanation construction, and backtrack repair. We will also record how many words per row are live at propagation time. If scanning and repair together account for under roughly a fifth of parity time on the counting suite, the main claim is wrong. We would then redirect effort to pivot replacement before building anything.
Baselines
The naive reference point is clause-only solving. Every parity constraint is expanded to clauses and given to the same CryptoMiniSat build with elimination disabled, under the same counting driver. The file gives a historical anchor for how badly this goes: BIRD reports that ApproxMC2 solved 492 benchmarks, against 1,140 for ApproxMC3 on the 1,896-instance suite. No reported result on Lacuna was found for modern clause-only solvers such as Kissat on that suite.
The strongest existing method for counting and sampling is ApproxMC4 and UniGen3 running on BIRD2 (Tinted, Detached, and Lazy CNF-XOR Solving). It is the strongest because it already includes word-packed propagation, detaching and lazy explanations, so any gain we show must come from bookkeeping alone. On the 1,896-instance suite it reports a timeout-penalized score (PAR-2) that improved "from 4146 to 3701" and 77 more instances solved than ApproxMC3. We will rerun it ourselves on identical hardware, seeds, timeout and hash counts rather than compare against published numbers. Beating it means more solved instances and lower PAR-2 at equal counting tolerance. The key requirement is that the set of deductions per node stays identical, which we will verify by logging.
For pseudo-Boolean plus parity problems, the strongest competitor is ApproxMCPB with Mixed-Watches (Engineering an Efficient PB-XOR Solver). On the 1,076-benchmark neural-network verification suite it reports 912 solved and PAR-2 of 1822 seconds, against 802 solved and 3305 seconds for ApproxMC4. Beating it means Eager-GJE plus our engine plus lazy explanations reaching at least 912 solved with lower PAR-2 on the same machine.
As a secondary stress test with deep backtracking, we will compare against GaussMaxHS on the WISH suite, where Gaussian Elimination Meets Maximum Satisfiability reports 6,120 of 9,628 solved within 5,000 seconds, against 5,473 for MaxHS.
Three ablations isolate the ingredients:
- a variant that skips zero words by rescanning each row, with no index and no reversibility;
- a variant with the sparse index recomputed after each backtrack rather than restored;
- a variant with only the matrix-level live-row set.
Every configuration gets the same tuning budget. That budget is a small grid over one parameter, the minimum row width in words at which the index is used, fixed on the 200-instance-scale development subset and then frozen.
Why not just…?
Why not just expand parity into clauses and use a modern clause-learning solver? Propagation on expanded parity is blind until all but one variable is set (Integrating Equivalency Reasoning into Davis-Putnam Procedure). The clause-only pipelines in the file lose badly on exactly our benchmarks, including the 492 versus 1,140 gap above. We still run this baseline so readers can see the full range. We expect it to lose, and it is not a serious threat.
Why not just rely on BIRD2 and wider SIMD words? This is the real threat. If rows are short, or live words stay dense until very late in search, a vectorized rescan is already nearly free, and our index only adds overhead. That is exactly why profiling comes first. The first ablation, zero-word skipping without an index, is the direct test. If it matches the full engine, the honest conclusion is that reversibility is unnecessary here, and we will report that.
Why not just shrink the matrices with component partitioning, or keep Mixed-Watches? Partitioning, as in GaussMaxHS, lowers elimination cost but does not stop dead rows within a component from being visited, so the two approaches are complementary. We will run both with partitioning enabled. Mixed-Watches may simply remain the best pseudo-Boolean coupling. The eager-versus-Mixed-Watches comparison on the neural-network suite settles that question directly, and a loss there would falsify our secondary claim while leaving the counting result intact.
Why not encode each parity constraint as a bit-parallel table? As argued above, a single parity constraint gains nothing from full arc consistency beyond a counter. Tables would only duplicate what elimination does for linear systems, at exponential size.
Proposed Experiments
The primary experiment runs ApproxMC4 and UniGen3 with the BIRD2 engine against the same drivers with our engine on the 1,896-instance counting suite. It measures solved instances, PAR-2, parity-engine time, words touched per propagation, and observed counting error. The error should match the baseline's, since the approximation guarantee does not depend on propagation order.
The decisive mechanism check is a plot of per-instance speedup against the measured fraction of dead words at propagation time. If the gain comes from where we claim, speedup should rise with that fraction. If it does not, the claim fails even if aggregate numbers improve.
The second experiment is the four-way coupling comparison (Lazy-GJE, Eager-GJE, Mixed-Watches, and Eager-GJE with our engine and lazy explanations) on the 1,076 neural-network benchmarks. It tests whether cheap invocations reverse LinPB's ranking.
The third experiment runs the engine inside GaussMaxHS on the WISH suite. There, frequent deep backtracks should make constant-time restoration matter most. The trail-recompute ablation should show the largest gap on this suite.
References
- Engineering an Efficient PB-XOR Solver
- BIRD: Engineering an Efficient CNF-XOR SAT Solver and Its Applications to Approximate Model Counting
- Tinted, Detached, and Lazy CNF-XOR Solving and Its Applications to Counting and Sampling
- Gaussian Elimination Meets Maximum Satisfiability
- Extending Compact-Table to Negative and Short Tables
- Compact-MDD: Efficiently Filtering (s)MDD Constraints with Reversible Sparse Bit-sets
- Optimizing Simple Tabular Reduction with a Bitwise Representation
- Integrating Equivalency Reasoning into Davis-Putnam Procedure