Some samplers draw satisfying assignments of a Boolean formula with a provable near-uniformity guarantee. The leading ones, UniGen and its successors, work by adding random parity (XOR) constraints. Each constraint cuts the solution set roughly in half, and after enough cuts a solver lists every solution left in the surviving "cell" and returns one at random. How many solutions a cell must hold before it may be listed (the pivot) comes from Chebyshev's inequality. Chebyshev assumes a worst case in which solutions clump together and fall into the same cell. Counters built on the same hashing machinery keep observing that real formulas never come close to this worst case. ApproxMC2 reports a geometric-mean error of 0.021 when the guaranteed tolerance is 0.8. ApproxMC5 reports about 0.05, and pact reports 0.033. Samplers still pay the worst-case price in solver calls. They cannot simply shrink the pivot, because every uncertified shortcut tried so far fails uniformity tests.
This note proposes a way to measure, for each instance, the specific structure that makes the worst case bad. If that structure is absent, the sampler may use a smaller pivot while keeping a guarantee. The key fact is that random affine XOR hashes (a random linear map plus a random offset over GF(2)) are exactly 3-wise independent. The first three moments of a cell's size are therefore known in advance, and the fourth moment departs from its "random-like" value only through additive quadruples: four solutions whose bitwise XOR is zero. The density of such quadruples can be estimated from a few thousand near-uniform witnesses. For each random triple of witnesses $a,b,c$, we ask whether $a\oplus b\oplus c$ is also a solution. Evaluating that question for hundreds of candidate assignments at once is a bit-parallel filtering problem, which modern CPUs handle in machine-word lanes. A fourth-moment tail bound can then replace Chebyshev, and the needed pivot falls roughly with the square root of the failure probability instead of linearly in it.
Core Claim
Write $c$ for the number of solutions in a random cell and $\mu$ for its mean, which is about $|R_F|/2^m$ after $m$ XOR constraints, where $R_F$ is the solution set projected onto the sampling variables. Let $p=\Pr_{a,b,c}[a\oplus b\oplus c\in R_F]$ for witnesses drawn uniformly from $R_F$.
For four distinct points whose XOR is zero, the affine span has dimension two, not three. They therefore land in a given cell together with probability $2^{-3m}$ instead of $2^{-4m}$. Counting these coincidences gives the following, to leading order and up to constants the proof will fix:
$$\mathbb{E}\big[(c-\mu)^4\big] \;\approx\; 3\mu^2 + \mu + \mu^3 p .$$
In words, the fourth moment of the cell size behaves as if the solutions were scattered independently, plus a correction proportional to how often XOR combinations of solutions are themselves solutions. For a scattered solution set, $p$ is about the solution density, which is negligible. For a solution set made of affine subspaces, the adversarial case that forces Chebyshev's conservatism, $p$ approaches 1.
The Markov inequality applied to this fourth moment gives $\Pr[|c-\mu|\ge\beta\mu]\le(3\mu^2+\mu+\mu^3p)/(\beta\mu)^4$, where $\beta$ is the relative deviation the sampler must tolerate. Whenever $p\lesssim 3/\mu$, the dominant term is $3/(\beta^4\mu^2)$. Requiring this to be at most $\delta$ gives $\mu\gtrsim\sqrt{3}/(\beta^2\sqrt{\delta})$. Chebyshev instead requires $\mu\gtrsim 1/(\beta^2\delta)$.
Because the pivot is in the tens, $p$ only needs to be bounded at a resolution of about 0.01 to 0.1. A few thousand triples achieve that with a one-sided binomial confidence bound. The central claim is that this audit is cheap enough, and $p$ small enough on real instances, to cut solver calls per sample well below what UniGen3 needs. On instances with genuine affine clustering, the audit detects the clustering and refuses to shrink the pivot. A blind pivot reduction cannot do that.
Research Program
Theory. We will first make the moment calculation exact for UniGen-style dense XOR hashing over an independent support, meaning a set of variables whose values determine all others. The goal is to prove that the sampler's per-witness output probability remains within $(1+\epsilon)$ of uniform when the pivot is set from an upper confidence bound on $p$.
Two sources of error must be charged against the guarantee. The first is the estimator's confidence level, which enters as an extra failure probability. The second is the fact that the audit witnesses come from a near-uniform sampler rather than an exactly uniform one. UniGen's guarantee bounds each witness's probability within a $(1+\epsilon)$ factor, so the estimate of $p$ is distorted by at most $(1+\epsilon)^3$, and this factor can be folded into the upper bound. Warm-up witnesses are drawn with randomness independent of the later hashing, so the certificate is not circular.
The sparse hash family of ApproxMC5 is not 3-wise independent in the same exact sense. We treat it as a stated extension, not a claim.
Engine. The auditor is built on the tinted propagation idea of BIRD2, which represents variable values as bit-fields and propagates with word-wide AND and POPCNT. We change what the lanes mean. In BIRD2, the lanes carry one search. Here, each of the 64 to 512 lanes carries a different candidate $a\oplus b\oplus c$ restricted to the sampling set. Clauses are evaluated lane-wise, in the spirit of the word-level filtering in Filtering Algorithms Based on the Word-RAM Model and STRbit.
For circuit-derived formulas such as ISCAS or bit-blasted designs, propagation from the support variables fixes every other variable, so membership is decided in a single pass. Lanes that propagation leaves undetermined fall back to incremental SAT calls under assumptions inside CryptoMiniSat. We will report the fraction of lanes that fall back, because the audit is only cheap when propagation settles most of them.
Sampler. The resulting sampler, which we call UniGen-A, runs UniGen3 for a short warm-up. It then audits $p$ and sets the pivot from the fourth-moment bound, or from Chebyshev if that bound is smaller. Finally it samples with BIRD2 as the solver backend. The audit is repeated at a fixed schedule so that its cost amortizes over large sample batches, which is the regime of constrained-random verification.
Baselines
The naive reference point is UniGen3 run with BIRD2 exactly as released, with its default Chebyshev-derived pivot. It is also the strongest method that carries a guarantee. BIRD2 reports that UniGen3 solved 51 more instances than prior samplers on the 1,896-instance suite. Zeyen et al. find it was the only sampler to pass all five statistical tests on the 195-formula Ω dataset, and ScalBarbarik still accepts it at hardness κ=13. High-Throughput SAT Sampling records its throughput as 64 unique solutions per second on or-50-10-7-UC-10. No reported per-sample SAT-call count or pivot value for UniGen3 was found on Lacuna, so we will measure both ourselves.
UniGen-A must beat UniGen3 on throughput and SAT calls per sample, with the same solver build, machine, timeout, and ε. It must also match UniGen3's accept and pass record on the Barbarik and Zeyen tests. Throughput will be counted with audit time included.
The fast heuristic baseline is CMSGen, which is quicker than any hashing sampler. ScalBarbarik reports it accepted on only 41 of 50 instances at κ=11 and rejected on all 50 at κ=13. Zeyen et al. report that it fails the Variable Frequency test with p≈0.000. It defines the throughput ceiling we should not expect to reach. UniGen-A beats it only on test outcomes, not on speed.
The key ablation is a blind small pivot. This is UniGen3 with its pivot manually set to the value UniGen-A would choose, but with no audit. It isolates whether the energy measurement adds anything beyond "use a smaller pivot." A second ablation replaces bit-sliced lane evaluation with one-candidate-at-a-time evaluation, to measure how much the bit-parallel engine contributes to making the audit affordable.
Why not just…?
Why not just shrink the pivot empirically and check the result with Barbarik? This is the most serious alternative. If real instances never have large $p$, a tuned pivot gives the same speed without an audit. Two things argue against settling for it. First, certifying acceptance is expensive: Barbarik needed about 1.7 million samples to accept UniGen2, so per-instance black-box testing costs more than the sampling it is meant to protect. Second, the tuned pivot has no mechanism for detecting the clustered instances where it breaks. Meel's thesis already flags high-tilt spaces as a place where variance spikes. The blind-pivot ablation and the planted-structure experiment below settle the question directly. If the blind pivot is never rejected on any instance, including planted ones, we will report that the contribution is certification alone.
Why not just prove a tighter bound analytically, or use more independent hash families? Worst-case analysis must cover affine-subspace solution sets, where the fourth-moment correction is maximal. No instance-free bound can therefore beat Chebyshev by much with cheap hashes. Meanwhile, Sparse Hashing points out that denser, more independent hashes choke CDCL solvers. The proposal is exactly the instance-dependent version: it keeps UniGen's hash family and proves a bound conditioned on a measured quantity.
Why not just use a faster solver or a GPU sampler? Solver speed is orthogonal to this work. We build on BIRD2, and BIRD2 alone leaves the pivot, and hence the number of solutions enumerated per cell, unchanged. The GPU sampler of Ardakani et al. reaches up to 523.6× UniGen3's throughput, but by its authors' account it has no uniformity guarantee. Heuristic samplers in the same speed class fail the tests cited above.
Proposed Experiments
Measuring $p$ in the wild. The first experiment estimates $p$ across the BIRD2 suite of 1,896 instances, the Barbarik suite of 101, and the Ω dataset of 195. For each instance we compare the estimate against the solution density and against the $3/\mu$ threshold, and report the audit cost and the fraction of lanes that fall back to SAT. If most real instances have $p$ above threshold, the premise fails and we stop there.
Throughput and solver calls. On instances where the audit certifies a smaller pivot, we compare UniGen-A with UniGen3 on samples per second, SAT calls per sample, and PAR-2 score under a 5,000-second timeout. The timeout matches the one used in the ApproxMC5 and GaussMaxHS evaluations.
Uniformity. UniGen-A, UniGen3, CMSGen, and the blind-pivot ablation all go through Barbarik, ScalBarbarik (including GenHard SHA-1 instances at κ=11 and κ=13), and the five Zeyen tests on Ω. The Zeyen tests are Pearson χ², Monobit, Variable Frequency, selected features per configuration, and the Birthday test, combined by the harmonic mean p-value.
The decisive check. We will use formulas whose solution sets are planted unions of affine subspaces, conjoined with ISCAS circuit constraints so that solving them stays realistic. On these formulas $p$ is large by construction. The prediction is sharp. The audit should detect large $p$ and keep UniGen-A's pivot at Chebyshev size, so UniGen-A passes the tests. The blind small-pivot sampler should show measurable per-witness skew that Barbarik or the Birthday test rejects. On real benchmarks, both samplers should pass while UniGen-A retains most of the speedup.
If the blind pivot survives the planted instances, our fourth-moment account of where the accuracy gap comes from is wrong. If UniGen-A is rejected anywhere, the bound or its estimator is wrong. Either outcome is informative.
References
- Algorithmic Improvements in Approximate Counting for Probabilistic Inference: From Linear to Logarithmic SAT Calls.
- Sparse Hashing for Scalable Approximate Model Counting: Theory and Practice
- Approximate SMT Counting Beyond Discrete Domains
- Tinted, Detached, and Lazy CNF-XOR Solving and Its Applications to Counting and Sampling
- Filtering Algorithms Based on the Word-RAM Model
- Optimizing Simple Tabular Reduction with a Bitwise Representation
- Testing Uniform Random Samplers: Methods, Datasets and Protocols
- On Quantitative Testing of Samplers
- High-Throughput SAT Sampling
- On Testing of Uniform Samplers
- Constrained Counting and Sampling: Bridging the Gap between Theory and Practice.
- Gaussian Elimination Meets Maximum Satisfiability