A uniform sampler for a Boolean formula should return every satisfying assignment with equal probability. Its output should therefore depend only on which assignments satisfy the formula, not on how the formula is written. This proposal turns that observation into a test. Take a formula, add redundant clauses (clauses already implied by the formula, so the set of solutions is unchanged), and run the sampler on both versions. Any statistically detectable difference between the two output distributions proves the sampler is not uniform on at least one of them. The test needs no exact counter, no reference uniform sampler, and no assumptions about how the sampler behaves on restricted sub-problems.
This matters because fast samplers without guarantees are the ones practitioners actually run. CMSGen is the speed/uniformity "sweet spot" in the BURST comparison, and GPU gradient samplers reach millions of solutions per second. Both are known or suspected to be biased, and the testers that catch this are heavy machinery. Redundant constraints are usually studied as a way to make solvers faster. Here they become a measuring instrument. The same experiments also tell us something practical: whether a modeler who adds a redundant clause to speed up a solve is silently changing the samples a verification flow sees.
Core Claim
Let $F$ be a formula with solution set $S$, and let $R$ be a set of clauses implied by $F$, so $F \wedge R$ has the same solution set $S$. A sampler $A$ is uniform on both formulas only if its output distributions $P_A(F)$ and $P_A(F \wedge R)$ are both the uniform distribution on $S$, and therefore equal to each other. A two-sample test between those outputs is a sound falsifier: rejection certifies non-uniformity. The test is one-sided, since a sampler equally biased on both formulas passes.
Our claim is that, for current heuristic samplers, this one-sidedness is not the limiting factor in practice. These samplers decide where to go using syntax: clause-violation counts in local search, propagation order in solvers that learn from conflicts, circuit structure in differentiable samplers. Choosing $R$ adversarially, aimed at the region of solution space the sampler over-visits, should expose bias with far fewer samples and less machinery than oracle-based testers. Sound samplers (UniGen3, KUS) should provably pass at the nominal false-rejection rate. Their guarantees depend only on $S$ and the hash family, so redundancy can only change their speed.
The mechanism has strong motivation in the literature. Redundant constraints are known to reshape solver behavior drastically:
- adding reachability mutexes turned a 6.5-minute planning solve into 7 seconds in the planning-encoding study;
- a cubic redundant encoding beat a compact one for minimal perfect hashing;
- a redundant "at least one root" clause rescued bounded-treewidth Bayesian network learning;
- adding resolvents sharpens the gradients that local search follows (Cha and Iwama).
These works measure only time-to-first-solution. If redundancy moves search trajectories this much, it should move where a heuristic sampler lands. That is a distributional effect nobody has measured.
Relation to Existing Testers and Samplers
The Barbarik family supplies the competing methodology, and we position the new test against it.
- Barbarik2 tests samplers by conditioning on pairs of solutions using chain formulas.
- ScalBarbarik adds a tunable hardness knob $\kappa$ built from SHA-1 pre-image instances.
- Barbarik3 uses probability bucketing with a pair-conditioning oracle.
All of them query the sampler on modified sub-formulas. They inherit a "subquery-consistency" assumption, which the authors themselves list as a limitation: the sampler must behave on conditioned formulas the way it behaves on the original. Our test never conditions. It asks the sampler only about formulas with the full original solution set. It is weaker, because it is one-sided, but it rests on fewer assumptions. We treat it as a cheap first-line screen, not a replacement.
The hashing samplers that define soundness supply the invariance we rely on. These are:
- XORSample, which cuts the space with random parity constraints;
- UniGen, which adds PAC-style guarantees over an independent support;
- UniGen3 on the BIRD2 solver;
- KUS, which samples exactly from a compiled circuit.
BIRD2 is the closest work touching redundancy inside sampling. It removes clause copies of parity constraints that Gaussian elimination already covers, for speed. It never asks whether redundancy changes distributions, and for a sound sampler it cannot.
The samplers we expect to fail are:
- local-search walkers, which Erenrich et al. show are biased by orders of magnitude;
- the high-throughput GPU sampler, which rewrites clauses into circuits and explicitly disclaims uniformity guarantees;
- CMSGen.
Propagation-redundancy theory constrains the design. Clauses whose deductions are already subsumed by other constraints should leave propagation-driven samplers untouched. We therefore expect only non-subsumed redundancy to be informative, and we test that prediction.
Research Program
Generating redundant clauses. We build three generators, each guaranteed to produce only implied clauses.
- Syntactic. Clause duplication and resolvents of existing clauses. Duplication is the cheapest possible redundancy, yet it doubles a clause's weight in any violation-count energy.
- Learned. Clauses learned by a conflict-driven solver run on $F$. Each is implied by $F$; we verify each one by a refutation check.
- Structural. Domain invariants where the benchmark has known structure, such as forward mutexes on planning encodings and at-most-one constraints on feature models.
Adversarial targeting. This is the key ingredient.
- Draw a pilot batch from the sampler on $F$.
- Compute per-variable marginals over the independent support.
- Pick the literals the sampler most over-represents relative to a small reference batch from UniGen3.
- From the generated pool, select redundant clauses that mention those literals, so that conflicts and energy are concentrated where the sampler over-visits.
Building the test statistic. The pilot batches are used only for selection. Fresh samples are then drawn on $F$ and $F \wedge R$. We compare them with two statistics:
- a two-sample test on independent-support marginals, Bonferroni-corrected across variables;
- a test on histograms of solutions bucketed by a shared random parity hash into $2^m$ cells, with $m$ chosen small.
Detecting a marginal shift of size $\Delta$ needs on the order of $1/\Delta^2$ samples per side. This follows from Hoeffding's bound and does not depend on the number of solutions, unlike identity tests over the full solution space. The pilot/test split keeps rejection rates valid despite adaptive selection of $R$.
Measuring speed as a by-product. Because sound samplers must pass, the same runs also measure how redundancy changes UniGen3 and KUS runtime and d-DNNF size. This is the open question of whether redundancy helps or hurts sound pipelines. We report it but do not make it the headline.
Baselines
The naive reference point is the "change nothing meaningful" rewrite: randomly permute clause order, literal order, and variable names, then apply the same two-sample test. This is also metamorphic and costs nothing. If permutation exposes bias as often as redundancy does, redundancy adds nothing. We run it with identical sample budgets, statistics, and pilot/test splits.
The strongest existing competitor is Barbarik3 for its scalability, together with ScalBarbarik on its own hardness-controlled instances. Barbarik3 is reported to terminate on all 87 real-life benchmarks, against 16 for Barbarik2, and to use 450× fewer samples than Barbarik2 when testing wSTS (On Scalable Testing of Samplers). ScalBarbarik reports that CMSGen was accepted on 41 of 50 instances at $\kappa=11$ and rejected on all 50 at $\kappa=13$ (On Quantitative Testing of Samplers).
Both testers are run on the same instances, samplers, and wall-clock budgets as ours, with their published parameters. The file reports Barbarik3's results mainly on weighted samplers. For the plain uniform case we found no reported per-instance sample count on Lacuna, so we measure it ourselves. Beating these baselines means one of two things:
- rejecting the same non-uniform samplers at comparable rates using an order of magnitude fewer total samples and solver calls; or
- rejecting samplers on instances where the Barbarik testers time out.
In both cases we must also keep false rejections of UniGen3 and KUS at the nominal level.
The ablation that isolates the key ingredient replaces adversarial clause selection with uniformly random selection from the same redundancy pool, at equal clause count. A second ablation restricts the pool to propagation-redundant clauses. Theory predicts these should be nearly inert for solver-based samplers.
Why not just…?
Why not just shuffle and rename the formula? This is the most serious threat, and it is a baseline above. Our reason to expect redundancy to be stronger is that many samplers already randomize variable order and polarity internally, which partly washes out renaming. Redundant clauses instead change what is propagated and what counts as violated, and no internal randomization can undo that. If the experiments show permutation matches redundancy, we will report the metamorphic test as a permutation test and drop the redundancy framing.
Why not just run Barbarik3? When the pair-conditioning oracle is available and subquery consistency holds, Barbarik3 is the more complete tester. It is two-sided in the sense that it can accept. Our test is meant for regimes it handles poorly:
- samplers that cannot accept conditioned queries cheaply, such as GPU circuit samplers;
- large feature models from BURST;
- auditing whether a specific modeling change, adding redundancy, alters a deployed sampler's outputs.
The head-to-head comparison on shared instances settles which is cheaper per rejection.
Why not just use a sound sampler and skip testing? Sound samplers remain far slower. The GPU sampler reports 33.6× to 523.6× speedups over CPU samplers and about 6 million solutions per second against UniGen3's 64 on or-50-10-7-UC-10 (High-Throughput SAT Sampling). Users will keep choosing fast samplers, so a cheap falsifier of their bias has value. Our speed measurements on UniGen3 and KUS also show whether redundancy narrows that gap.
Proposed Experiments
The instance suites are:
- the 128 BURST models (Linux, BusyBox, JHipster feature models and competition instances);
- the ScalBarbarik GenHard instances at $\kappa \in \{11, 13\}$;
- a subset of the KUS and BIRD2 suites with known model counts;
- the XORSample logistics instance with exactly 512 solutions and the 48-solution random 3-SAT instance from Gomes et al..
On the two small instances we can enumerate the solutions and compute exact distributions, giving ground truth. There, SampleSAT reached only 256 of the 512 logistics solutions, so we can check directly whether redundancy shifts which half it finds.
The samplers are:
- sound: UniGen3 and KUS;
- heuristic: CMSGen (default and its slower-restart variants), QuickSampler, STS, a SampleSAT/WalkSAT walker, and the GPU gradient sampler.
The metrics are:
- rejection rate per sampler and instance at $\alpha = 0.05$;
- total samples and solver calls to rejection;
- false-rejection rate on sound samplers;
- KL divergence from uniform on enumerable instances;
- runtime and compiled-circuit size changes for UniGen3 and KUS.
Four decisive checks determine the outcome:
- UniGen3 and KUS must be rejected at no more than about 5%. Otherwise the pipeline is broken.
- On GenHard at $\kappa = 13$, where ScalBarbarik rejects CMSGen on all 50 instances, the adversarial redundancy test should reject on most of them using markedly fewer samples. Failure here would mean the test is too weak to matter.
- Adversarial selection must beat both random selection and the permutation baseline at equal budgets. Otherwise the key ingredient is not doing the work.
- On the 512-solution instance, the exact distribution shift induced by redundancy should be large for local search and CMSGen and zero for KUS. This directly confirms that the formula's syntax, not just its solution set, steers heuristic samplers.
References
- BURST: Benchmarking uniform random sampling techniques
- Investigating the Effect of Relevance and Reachability Constraints on SAT Encodings of Planning
- Constructing Minimal Perfect Hash Functions Using SAT Technology
- Learning Optimal Bounded Treewidth Bayesian Networks via Maximum Satisfiability
- Performance Test of Local Search Algorithms Using New Types of Random CNF Formulas
- On Testing of Samplers
- On Quantitative Testing of Samplers
- On Scalable Testing of Samplers
- Near-Uniform Sampling of Combinatorial Spaces Using XOR Constraints
- Balancing Scalability and Uniformity in SAT Witness Generator
- Tinted, Detached, and Lazy CNF-XOR Solving and Its Applications to Counting and Sampling
- Knowledge Compilation meets Uniform Sampling
- Sampling Combinatorial Spaces Using Biased Random Walks
- High-Throughput SAT Sampling
- Removing propagation redundant constraints in redundant modeling