Testing of Horn Samplers

Ansuman Banerjee, Shayak Chakraborty, Sourav Chakraborty, Kuldeep S. Meel, Uddalok Sarkar, Sayantan SenAISTATS 2023 · OpenReview

Abstract

Sampling over combinatorial spaces is a fundamental problem in artificial intelligence with a wide variety of applications. Since state-of-the-art techniques heavily rely on heuristics whose rigorous analysis remains beyond the reach of current theoretical tools, the past few years have witnessed interest in the design of techniques to test the quality of samplers. The current state-of-the-art techniques, $\mathsf{Barbarik}$ and $\mathsf{Barbarik2}$, focuses on the cases where combinatorial spaces are encoded as Conjunctive Normal Form (CNF) formulas. While CNF is a general-purpose form, often techniques rely on exploiting specific representations to achieve speedup. Of particular interest are Horn clauses, which form the basis of the logic programming tools in AI. In this context, a natural question is whether it is possible to design a tester that can determine the correctness of a given Horn sampler. The primary contribution of this paper is an affirmative answer to the above question. We design the first tester, $\mathsf{Flash}$, which tests the correctness of a given Horn sampler: given a specific distribution $\mathcal{I}$ and parameters $\eta$, $\varepsilon$, and $\delta$, the tester $\mathsf{Flash}$ correctly (with probability at least $ 1-\delta$) distinguishes whether the underlying distribution of the Horn-sampler is “$\varepsilon$-close” to $\mathcal{I}$ or “$\eta$-far” from $\mathcal{I}$ by sampling only $\widetilde{\mathcal{O}}(\mathsf{tilt}^3/(\eta - \varepsilon)^4)$ samples from the Horn-sampler, where the $\mathsf{tilt}$ is the ratio of the maximum and the minimum (non-zero) probability masses of $\mathcal{I}$. We also provide a prototype implementation of $\mathsf{Flash}$ and test three state-of-the-art samplers on a set of benchmarks.

Introduction

In artificial intelligence and formal verification, sampling random solutions from massive sets defined by logical constraints is a critical task. Because finding every possible solution is NP-hard, practitioners rely on heuristic samplers. While fast, these heuristics often lack mathematical guarantees regarding their output distribution. To address this, "testers" are required to verify if a sampler is "honest."

Existing state-of-the-art testers like Barbarik are designed for general Conjunctive Normal Form (CNF) formulas. However, many AI applications, such as power grid modeling and logic programming (Prolog), utilize Horn clauses. Standard CNF-based testers fail for Horn samplers because their internal transformations break the Horn property, rendering the sampler unable to process the modified formulas.

The Flash Tester

We introduce Flash (for weighted samplers) and uFlash (for uniform samplers), the first testers specifically designed for Horn logic. Flash employs a "grey-box" testing methodology. Instead of treating the sampler as a black box—which would require an exponential number of samples—Flash probes the sampler's internal logic by constructing new, specialized Horn formulas.

Key Innovations

  • HornKernel Subroutine: This core component takes two solutions and constructs a new Horn formula where these solutions (plus a specific "nuisance" solution) are the primary outcomes. This allows the tester to verify relative weights efficiently.
  • Horn-chain-formulas: To prevent samplers from simply memorizing solutions, Flash uses linear-sized chains to "blow up" the solution space, forcing the sampler to navigate the combinatorial structure.
  • Handling the Intersection Solution: Unlike CNF, Horn logic dictates that a formula with two solutions must also contain their intersection ($\tilde{0}$). Flash is mathematically designed to account for this third solution during statistical verification.

Experimental Evaluation

The performance of Flash was evaluated using benchmarks derived from real-world power transmission network reliability studies. These benchmarks represent a significant challenge due to their scale and complexity.

Table 1: Characteristics of the Horn benchmarks, showing the massive model counts and the varying tilt values for Benchmark-I and Benchmark-II.

As shown in Table 1, the benchmarks feature model counts ranging from $10^{32}$ to $10^{147}$. A critical parameter in these tests is the tilt—the ratio between the maximum and minimum probability masses. The theoretical sample complexity of Flash is $\widetilde{\mathcal{O}}(\mathsf{tilt}^3/(\eta - \varepsilon)^4)$, making the tilt a primary driver of testing difficulty.

Results and Discussion

Flash demonstrated a massive $10^7$-factor speedup in runtime compared to the theoretical baseline of black-box testing. In testing three state-of-the-art samplers—UniGen3, QuickSampler, and STS—the following was observed:

  • UniGen3 proved to be the most robust, though it encountered timeouts on the most complex formulas.
  • QuickSampler and STS were consistently rejected by Flash, indicating they are "far" from the ideal distribution despite their speed.

The primary limitation identified is the dependence on tilt; extremely skewed distributions require significantly more samples, occasionally leading to Time Limit Exceeded (TLE) errors on benchmarks with very high tilt values.

Conclusion

Flash provides the first theoretically sound and practically efficient method for testing Horn samplers. By maintaining the Horn property throughout the testing process and leveraging a grey-box approach, it bypasses the exponential sample requirements of traditional methods. Future work will focus on optimizing the HornKernel to better handle high-tilt distributions and extending these techniques to other restricted logical fragments.

Summary updated

Abstract

Sampling over combinatorial spaces is a fundamental problem in artificial intelligence with a wide variety of applications. Since state-of-the-art techniques heavily rely on heuristics whose rigorous analysis remains beyond the reach of current theoretical tools, the past few years have witnessed interest in the design of techniques to test the quality of samplers. The current state-of-the-art techniques, $\mathsf{Barbarik}$ and $\mathsf{Barbarik2}$, focuses on the cases where combinatorial spaces are encoded as Conjunctive Normal Form (CNF) formulas. While CNF is a general-purpose form, often techniques rely on exploiting specific representations to achieve speedup. Of particular interest are Horn clauses, which form the basis of the logic programming tools in AI. In this context, a natural question is whether it is possible to design a tester that can determine the correctness of a given Horn sampler. The primary contribution of this paper is an affirmative answer to the above question. We design the first tester, $\mathsf{Flash}$, which tests the correctness of a given Horn sampler: given a specific distribution $\mathcal{I}$ and parameters $\eta$, $\varepsilon$, and $\delta$, the tester $\mathsf{Flash}$ correctly (with probability at least $ 1-\delta$) distinguishes whether the underlying distribution of the Horn-sampler is “$\varepsilon$-close” to $\mathcal{I}$ or “$\eta$-far” from $\mathcal{I}$ by sampling only $\widetilde{\mathcal{O}}(\mathsf{tilt}^3/(\eta - \varepsilon)^4)$ samples from the Horn-sampler, where the $\mathsf{tilt}$ is the ratio of the maximum and the minimum (non-zero) probability masses of $\mathcal{I}$. We also provide a prototype implementation of $\mathsf{Flash}$ and test three state-of-the-art samplers on a set of benchmarks.
BibTeX
@inproceedings{banerjee2023testing,
  author = {Ansuman Banerjee and Shayak Chakraborty and Sourav Chakraborty and Kuldeep S. Meel and Uddalok Sarkar and Sayantan Sen},
  title = {{Testing of Horn Samplers}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=68qnziR1EF},
}
Figure