Abstract
This paper introduces Barbarik, the first practical algorithmic framework designed to test whether a discrete sampler is truly uniform. Traditional statistical tests, such as the $\chi^2$ test, are infeasible for modern AI applications because their sample complexity scales with the size of the state space. Barbarik overcomes this limitation by leveraging conditional sampling to transform global testing into a series of local checks. Its sample complexity is independent of the state space size, making it a powerful tool for verifying high-dimensional sampling heuristics.
Introduction
Probabilistic reasoning is fundamental to modern AI, used in domains ranging from medical diagnosis to autonomous vehicle control. These systems rely on samplers—algorithms that select representative solutions from complex distributions defined by constraints. However, developers face a "sampler's dilemma": theoretically sound samplers are often too slow for real-world problems, while fast heuristic samplers often lack guarantees and may introduce bias into AI decision-making.
Testing these samplers is notoriously difficult. In deterministic software, a single counterexample can prove a bug. In sampling, one must observe a distribution. Traditional tools require a number of samples proportional to the square root of the state space. For state spaces with $2^{90}$ solutions, such tests are physically impossible to execute.
Methodology: The Barbarik Framework
Barbarik bridges the gap between property testing theory and practical verification. Instead of analyzing the entire distribution at once, it uses conditional sampling to "zoom in" on controlled slices of the state space. The framework operates through two primary subroutines:
- Kernel: This subroutine takes a sample from the Sampler Under Test (SUT) and a sample from a known-good uniform source. It then constructs a synthetic Boolean formula ($\hat{\phi}$) with a very small, specific number of solutions. If the SUT is uniform, it should choose between these solutions with a predictable, balanced probability.
- Bias: This subroutine counts how often the SUT picks a specific solution within the restricted space created by the Kernel. If the frequency deviates significantly from the expected ratio, the sampler is flagged as non-uniform.
By transforming a massive global problem into tiny local tests, Barbarik achieves a sample complexity of $O(1/(\eta - \epsilon)^4)$, which is independent of the number of variables in the formula.
Experimental Evaluation
The authors evaluated Barbarik using a benchmark suite of 101 instances derived from SMTLib, program synthesis, and ISCAS89 circuits. These instances represent massive solution spaces, as illustrated in the distribution of their sizes.
Three state-of-the-art samplers were tested: UniGen2 (which provides theoretical "almost-uniform" guarantees), SearchTreeSampler, and Quicksampler (both high-performance heuristics).
Results and Discussion
Barbarik successfully distinguished between uniform and biased samplers across all benchmarks. It provided a "certificate of uniformity" for UniGen2 and correctly identified that SearchTreeSampler and Quicksampler were non-uniform.
As shown in the results table, Barbarik rejected non-uniform samplers using as few as 250 samples per benchmark. For UniGen2, it required approximately 1.7 million samples to issue an "Accept" certificate—a manageable number for modern hardware, whereas a $\chi^2$ test would have required trillions of years. These results confirm that the test's efficiency is consistent regardless of formula size or solution count.
Conclusion
Barbarik represents a significant advancement in the verification of probabilistic systems by beating the dimensionality curse. While it assumes non-adversarial samplers and is currently specialized for uniform distributions, it provides a scalable foundation for future research into testing arbitrary distributions in deep learning and other complex AI models.
Summary updated