Scalable Model Counting via XOR Partitioning

This direction is merged into another direction: hashing-based approximate counting, bit-parallel filtering. Its last version stays readable and citable here.

Version 1 of 117 papers21 conceptsfrozen 2026-10-04

In the world of Boolean logic, the Satisfiability (SAT) problem asks a simple question: "Is there at least one assignment of variables that makes this formula true?" While this is NP-complete, modern solvers are remarkably good at finding that one needle in the haystack. However, many real-world applications—from quantifying the reliability of a power grid to sampling representative test cases for software—require something much harder. They require us to count how many needles there are (Model Counting) or to pick one at random (Uniform Sampling).

These tasks belong to the complexity class #P, which is generally considered much harder than NP. The breakthrough that has allowed these problems to scale to industrial dimensions is the use of universal hashing via XOR constraints.

The Intuition of the Sieve

Imagine a massive warehouse filled with boxes, and you want to know how many contain a specific item. Opening every box is impossible. Instead, you could use a "sieve" that randomly lets only 1/2 of the boxes through. If you apply this sieve and find that 50 boxes remain, you can estimate there were originally 100. If you apply a finer sieve that lets only 1/4 through and find 25, your estimate remains 100.

In the context of SAT, Kuldeep S. Meel, Moshe Y. Vardi, and Supratik Chakraborty formalized this in UniWit. They use random parity constraints (XORs) as these sieves. A single random XOR constraint like $x_1 \oplus x_3 \oplus x_7 = 1$ acts as a hash function that cuts the solution space exactly in half with high probability.

By adding $m$ such constraints, we partition the solution space into $2^m$ "cells." If we choose $m$ such that the number of solutions in a single cell is small enough for a standard SAT solver to count them easily, we can multiply that small count by $2^m$ to get a highly accurate estimate of the total. This approach, refined in tools like WeightGen and WeightMC by Chakraborty et al., provides strong theoretical guarantees on the accuracy of the count.

The Parity Bottleneck

While the theory is elegant, it faces a major practical hurdle: standard SAT solvers are designed for Conjunctive Normal Form (CNF)—long lists of OR statements. They are notoriously bad at handling XOR statements. When you translate a single XOR constraint into CNF, it causes an exponential blowup in the number of clauses, or it creates a "dense" structure that defeats the solver's heuristic search.

As Stefano Ermon and Carla P. Gomes noted in their work on the PAWS sampler, these parity constraints often become the primary bottleneck. The solver spends the vast majority of its time struggling with the very constraints added to make the problem easier. This mismatch is even more pronounced in Satisfiability Modulo Theories (SMT), where Meel et al. found that bit-level XORs fail to leverage the "word-level" (bit-vector) reasoning that SMT solvers excel at.

Native XOR Reasoning

To bridge this gap, researchers moved from treating the SAT solver as a "black box" NP-oracle to modifying its internal architecture. The key insight, summarized by Kuldeep S. Meel in Counting, Sampling, and Synthesis, is to integrate Gaussian elimination directly into the solver's core.

Instead of forcing the solver to treat XORs as logical clauses, the solver recognizes them as linear equations over the field $GF(2)$. This allows the solver to:

  1. Simplify constraints: Use linear algebra to reduce the number of variables before the search begins.
  2. Detect conflicts faster: Use Gaussian elimination during the search to identify when a set of parity constraints is unsatisfiable, long before a standard search would find the contradiction.

This "native" support was perfected in the BIRD architecture and the ApproxMC3 counter by Meel and Mate Soos. By using a "Blast-Inprocess-Recover-Destroy" cycle, they allowed the solver to switch between logical reasoning (for the original problem) and algebraic reasoning (for the hash constraints), resulting in performance gains of over two orders of magnitude.

Beyond Simple Counting

The power of XOR-based partitioning extends beyond simple counting. In Solving Marginal MAP Problems, Yexiang Xue and Bart Selman demonstrated that these constraints can "fold" complex optimization-plus-counting problems (like Marginal MAP) into a single task. Similarly, SMTApproxMC showed that by designing hash functions that operate on "words" rather than bits, we can perform probabilistic inference on high-level program variables and complex data structures.

By turning a counting problem into a series of smaller satisfiability checks—and then teaching the solvers how to "speak" the language of parity—this research direction has transformed #P-hard problems from theoretical curiosities into solvable engineering tasks.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_scalable_model_counting_via_xor_partitio_6022619d,
  title = {Scalable Model Counting via XOR Partitioning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scalable-model-counting-via-xor-partitioning/rdr_6022619d972342ee82eb90bd20172d4b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_scalable_model_counting_via_xor_partitio_6022619d_v1,
  title = {Scalable Model Counting via XOR Partitioning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scalable-model-counting-via-xor-partitioning/rdr_6022619d972342ee82eb90bd20172d4b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}