Parity-Cell Resampling: A Markov Chain for Uniform SAT Sampling Whose Correctness Does Not Depend on Hash Density

Many tasks need random satisfying assignments of a logical formula, drawn uniformly so that no solution is favored. Hardware test generation and testing of configurable software are two examples. The provably correct tools work by hashing. They add random parity constraints, which require that a chosen subset of variables XOR to a random bit. These constraints carve the solution set into small random "cells." The tool then asks a SAT solver to list one cell and picks a solution from it.

The guarantee requires the parity constraints to be long, touching about half the variables in the hashed set. Long parity constraints are exactly what stalls the propagation machinery inside modern SAT solvers. This tension is why provably correct samplers are slow and fast heuristic samplers fail statistical uniformity tests. In this note, a "witness" means a satisfying assignment, and "CDCL" means conflict-driven clause learning, the standard algorithm in modern SAT solvers.

We propose to turn hashing from a one-shot sampler into a Markov chain move. Given the current solution σ, the chain proceeds in three steps:

  1. Draw random parity constraints whose right-hand sides are set so that σ satisfies them.
  2. List every solution in the resulting cell, which is never empty because σ is in it.
  3. Jump to one of those solutions uniformly at random.

Because two solutions share a cell exactly when they share it from either side, the move is symmetric. The uniform distribution over solutions is therefore exactly stationary, whatever the parity constraints look like. Short, sparse parity constraints no longer threaten correctness. They only affect how fast the chain mixes, and they are cheap for the solver. The proposal tests one claim. There is a regime of short parity constraints, defined over the formula's independent support and paired with injected redundant clauses that restore unit propagation, where this chain produces statistically uniform samples at a far lower cost per effective sample than UniGen3.

Core Claim

Let $F$ be a formula with solution set $S$. Let $\mathcal{I}$ be an independent support: a small set of variables whose values determine all the others in every solution. Let $h$ be a random function from assignments of $\mathcal{I}$ to $\{0,1\}^m$, built from $m$ parity constraints. Let $C_h(\sigma)=\{\tau\in S : h(\tau)=h(\sigma)\}$ be the cell containing σ, and let $T$ be a cell-size cap. For $\tau\neq\sigma$ the chain moves with probability

$$P(\sigma,\tau)=\mathbb{E}_h\!\left[\frac{\mathbf{1}\{h(\tau)=h(\sigma)\}\;\mathbf{1}\{|C_h(\sigma)|\le T\}}{|C_h(\sigma)|}\right],$$

and it stays put otherwise. The cap does not break the symmetry, because whenever τ and σ share a cell, that cell and its size are identical for both. The expression is therefore symmetric in σ and τ, and the uniform distribution on $S$ is stationary for any distribution over $h$ and any $m$ fixed in advance. It is also the limiting distribution whenever the chain is irreducible.

Two consequences follow, and both are new relative to the files' prior work.

First, if the hash family is pairwise independent and $m\approx\log_2(|S|/T)$, then any two solutions share a cell with probability $2^{-m}$, and a constant fraction of cells are below the cap. Every transition probability is then on the order of $1/|S|$. This is a one-step minorization, a guarantee that each move already reaches every solution with probability comparable to uniform, so the dense-hash chain mixes in a constant number of steps. This recovers UniGen-style behavior as a special case.

Second, when the parity constraints are sparse, the chain's correctness survives and only the mixing time changes, and the mixing time can be measured directly. A wrong choice of $m$ never biases the stationary distribution. If $m$ is too small, cells exceed the cap and the chain idles. If $m$ is too large, cells are tiny and the moves are local. So $m$ can be estimated once, roughly, by ApproxMC, the approximate model counter from the UniGen line of work.

Relation to Prior Work

Two lines of work motivate this proposal and supply its machinery.

The hashing line supplies the move and the domain it acts on. Near-Uniform Sampling of Combinatorial Spaces Using XOR Constraints introduced cutting solution spaces with random parity constraints. A Scalable and Nearly Uniform Generator of SAT Witnesses and Balancing Scalability and Uniformity in SAT Witness Generator made it scalable with 3-wise independent hashes restricted to an independent support. Arjun made that support cheap to compute. All of these draw independent samples from fresh, unconditioned cells, so their guarantee rests on the hash family's independence properties. Dense parity constraints are therefore unavoidable for them. We condition the cell on the current solution and accept correlated samples. In exchange, the hash density becomes a free efficiency parameter rather than a correctness requirement.

Embed and Project, which describes PAWS, applies the same one-shot hashing scheme to weighted distributions. It hashes all variables and solves several fresh instances per sample. We hash only $\mathcal{I}$ and reuse the solver state across steps.

The mixing line motivates the problem and constrains the design. Local moves fail on solution sets that split into isolated islands. SearchTreeSampler showed SampleSAT drawing one solution about half the time when its true probability was under 1%. MC-SAT jumps between islands with slice sampling, but its inner step, SampleSAT, is biased. Hierarchical Bridging and the Path Auxiliary Sampler build heuristic multi-step or partial-assignment shortcuts. The path sampler shows explicitly that parity landscapes defeat single-bit flips.

A parity cell is itself a non-local, solver-certified jump. Its symmetry comes from the cell structure, not from a hand-designed path, and it never proposes invalid states. That last property is the failure mode of continuous relaxations such as SurVAE-augmented MCMC and the GPU sampler of High-Throughput SAT Sampling, which its authors concede lacks uniformity guarantees.

The redundant-constraint line supplies the third ingredient. Several papers find that logically implied clauses can speed solving by triggering propagation. Constructing Minimal Perfect Hash Functions Using SAT Technology found that a larger cubic encoding beats a compact one. Search Space Pruning via Logical Redundancy surveys root-node and mutex constraints. Engineering an Efficient PB-XOR Solver uses Mixed-Watches, which feeds constraints learned from parity reasoning back to the main engine, and cut PAR-2 from 3305 to 1822 seconds. The survey in Removing propagation redundant constraints in redundant modeling warns the other way: redundancy that does not propagate only adds cost.

Sparse parity constraints make injection cheap and targeted in a way that dense ones do not. A parity constraint of length $k$ has a direct clause encoding of $2^{k-1}$ clauses. In addition, short linear combinations found by Gauss-Jordan elimination of the small parity system can be added as clauses. Both are redundant with the parity system, and both give the CDCL engine propagations it would otherwise wait for.

Research Program

We would build the chain on CryptoMiniSat, the solver used by UniGen3, with Arjun computing $\mathcal{I}$. The chain starts from one solution found by an ordinary SAT call. Each step does four things:

  1. It draws $m$ parity constraints over $\mathcal{I}$ from a density-$p$ family, meaning each support variable is included independently with probability $p$, and sets their parities so that σ satisfies them.
  2. It optionally injects redundant clauses.
  3. It enumerates the cell incrementally with blocking clauses, stopping at $T+1$ solutions.
  4. It moves to a uniform member of the cell, or stays if the cap was hit.

The solver is kept alive across steps using assumption literals that switch each step's parity constraints on and off. This lets learned clauses about $F$ itself carry over between steps.

The analysis has two parts. On the theoretical side, we would state the stationarity result above and the dense-hash minorization bound. We would also try to bound the spectral gap, the quantity that controls mixing speed, as a function of $p$ for solution sets with known structure, such as unions of affine subspaces. Intuitively, the gap should be governed by how often a random sparse parity system separates the islands from each other. On the empirical side, we would sweep $p$ and $k$ (expected constraint length) together with $m$ and $T$. For each setting we would measure solver time per step and mixing, and plot cost per effective sample against density. The central quantity is where that curve's minimum lies, and whether it lies at a density low enough to sidestep the CDCL-parity bottleneck.

Baselines

The naive reference point is a single-bit-flip Metropolis chain over $\mathcal{I}$ that checks each proposal with a SAT call. This is the "obvious" restriction of MCMC to the independent support. It gives the cost a chain pays without non-local moves, and we expect it to fail on the XORBarriers and asymmetric-space instances from the SearchTreeSampler suite. It runs on the same solver with the same time budget.

The strongest existing method is UniGen3 with Arjun, as described in Counting, Sampling, and Synthesis: The Quest for Scalability. It was the only sampler to pass all five statistical tests on the Ω dataset in Testing Uniform Random Samplers. With Arjun it solved 319 more of the 1,896 Arjun benchmarks within 5,000 seconds than without it. On or-50-10-7-UC-10 it produced 64 unique solutions per second, against nearly 6 million for the unguaranteed GPU sampler, per High-Throughput SAT Sampling. It is run with the same Arjun support, the same solver version, the same per-instance timeout, and the same total budget for counting and sampling. Beating it means two things together: equal pass rates on Ω and on ScalBarbarik, plus a higher count of effective independent samples per second on the Arjun and BURST suites, or more instances completed under the timeout.

The fast heuristic reference is CMSGen with its restart variants. At hardness κ=11 it was accepted on 41 of 50 ScalBarbarik instances, and CMSGen500 on 50 of 50, but CMSGen was rejected on all 50 at κ=13, per On Quantitative Testing of Samplers. No reported result was found on Lacuna for CMSGen300 or CMSGen500 at κ=13, so we would run them ourselves. Beating CMSGen means acceptance at κ=13 at a throughput within a stated factor of it.

KUS from Knowledge Compilation meets Uniform Sampling serves as an exact-uniformity oracle on the instances it compiles. It solved 1,049 of its 1,425 benchmarks. MC-SAT serves as the existing solver-in-the-loop MCMC competitor.

Three ablations isolate the ingredients:

  • Hash density. A dense 3-wise family against sparse families, with everything else fixed.
  • Redundant clauses. The direct encoding and the Gauss-Jordan-derived clauses switched on and off.
  • Hash domain. Hashing over $\mathcal{I}$ against hashing over all variables.

The third ablation tests whether the independent support matters for mixing and not only for constraint length.

Why not just…?

Why not just run UniGen3 with short parity constraints? This is the most serious threat. If sparse-hash UniGen happens to pass ScalBarbarik and the Ω tests, our chain's advantage shrinks to a guarantee that practitioners may not value. We include sparse-hash UniGen as a baseline at matched density. The difference is that sparse one-shot hashing has no correctness argument: its bias is unknown and can be concentrated on structured instances. Our chain's bias at stationarity is zero, and its finite-time error is diagnosable with standard tools: autocorrelation, multiple chains, and comparison against KUS. The experiment settles the question by checking whether sparse UniGen fails at κ=13 or on the Variable Frequency test where our chain passes at the same density.

Why not just compile to d-DNNF with KUS? Where KUS compiles, it is exact and fast, and we use it as ground truth rather than competing with it. It failed on 376 of 1,425 instances in its own evaluation because the compiled graphs exhaust memory. Hashing methods reach formulas with 486,193 variables, per UniGen. Our target is the instances KUS cannot compile.

Why not just add restarts to CMSGen? The reported results show that restarts help at moderate hardness but collapse at κ=13. They also do not remove the structural variable bias that the Variable Frequency test detects on Ω (p≈0.000). We rerun CMSGen300 and CMSGen500 at κ=13 to close the unreported cell. If they pass there, the case for our chain rests on its guarantee alone, and we would say so.

Why not just add redundant clauses to UniGen3's dense parity constraints? A dense parity constraint over thousands of support variables has an exponentially large direct encoding. Its Gauss-Jordan combinations are just as long, so injection has nothing short to add. The redundant-clause ablation run on the dense configuration tests this directly. We expect injection to help only in the sparse regime, which is why the three ingredients belong together.

Proposed Experiments

The first decisive check is exactness on small instances. On the SearchTreeSampler XORBarriers and asymmetric-space instances, and on Ω formulas that KUS compiles, we would compare empirical solution frequencies after thinning against exact uniform. We would use Pearson χ² and the five-test harmonic-mean p-value protocol of Testing Uniform Random Samplers, at each density. The single-flip baseline should fail here and every density of our chain should eventually pass.

The second check is the cost-density curve. On the Arjun 1,896 suite and the BURST 128 library from BURST, we would measure solver seconds per step, the integrated autocorrelation time of support-variable indicators and of cell-membership statistics, and their product, which is cost per effective sample. We would compare this product against UniGen3's time per sample, and also record the number of instances completed under 5,000 seconds.

The third check is adversarial hardness. We would run ScalBarbarik on its 50-instance suite at κ from 11 to 13 against UniGen3, CMSGen and its restart variants, and sparse-hash UniGen. Samples from our chain would be thinned at five times the measured autocorrelation time so that the tester's independence assumption is respected.

The proposal fails if no sparse density beats dense hashing on cost per effective sample. That would mean propagation savings are eaten by slower mixing, and the paper becomes a negative result about sparse parity moves. The proposal also fails if redundant clause injection gives no measurable reduction in solver time per step.