On Testing of Uniform Samplers

Sourav Chakraborty, Kuldeep S. Meel

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.

Distribution of solution space sizes across the 101 benchmark instances, reaching up to $2^{90}$ solutions.

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.

Performance of Barbarik on selected instances, showing acceptance (A) for UniGen2 and rejection (R) for biased samplers.

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

Abstract

Recent years have seen an unprecedented adoption of artificial intelligence in a wide variety of applications ranging from medical diagnosis, automobile industry, security to aircraft collision avoidance. Probabilistic reasoning is a key component of such modern artificial intelligence systems. Sampling techniques form the core of the state of the art probabilistic reasoning systems. The divide between the existence of sampling techniques that have strong theoretical guarantees but fail to scale and scalable techniques with weak or no theoretical guarantees mirrors the gap in software engineering between poor scalability of classical program synthesis techniques and billions of programs that are routinely used by practitioners. One bridge connecting the two extremes in the context of software engineering has been program testing. In contrast to testing for deterministic programs, where one trace is sufficient to prove the existence of a bug, in case of samplers one sample is typically not sufficient to prove non-conformity of the sampler to the desired distribution. This makes one wonder whether it is possible to design testing methodology to test whether a sampler under test generates samples close to a given distribution. The primary contribution of this paper is an affirmative answer to the above question when the given distribution is a uniform distribution: We design, to the best of our knowledge, the first algorithmic framework, Barbarik, to test whether the distribution generated is ε−close or η−far from the uniform distribution. In contrast to the sampling techniques that require an exponential or sub-exponential number of samples for sampler whose support can be represented by n bits, Barbarik requires only O(1/(η−ε)4) samples. We present a prototype implementation of Barbarik and use it to test three state of the art uniform samplers over the support defined by combinatorial constraints. Barbarik can provide a certificate of uniformity to one sampler and demonstrate nonuniformity for the other two samplers. Erratum: This research is supported in part by the National Research Foundation Singapore under its AI Singapore Programme (Award Number: [AISG-RP-2018-005])
BibTeX
@inproceedings{chakraborty2019testing,
  author = {Sourav Chakraborty and Kuldeep S. Meel},
  title = {{On Testing of Uniform Samplers}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33017777},
}

Loading related content...

Figure