Knowledge Compilation meets Uniform Sampling

Shubham Sharma, Rahul Gupta, Subhajit Roy, Kuldeep S. Meel

Abstract

Generating random satisfying assignments for Boolean formulas is a critical task in software and hardware verification. This paper introduces KUS, a novel algorithm that bridges the gap between theoretical uniformity and industrial scalability. By leveraging knowledge compilation to transform constraints into Deterministic Decomposable Negation Normal Form (d-DNNF), KUS achieves up to a 1000x speedup over existing state-of-the-art tools while maintaining perfect statistical uniformity.

Introduction

In modern system design, Constrained-Random Verification (CRV) is the standard for testing complex systems against logic-based rules. The effectiveness of CRV depends on a "uniform sampler"—a tool capable of selecting random solutions where every valid assignment has an equal probability of being chosen.

Historically, practitioners have faced a difficult trade-off. Industrial heuristic methods are fast but often biased, potentially missing edge-case bugs. Conversely, theoretical methods provide rigorous uniformity but struggle to scale to large, real-world constraints. KUS addresses this challenge by applying knowledge compilation techniques to the sampling problem, offering a tool that is both mathematically sound and industrially performant.

The KUS Algorithm

The core innovation of KUS is the separation of the complex constraint-solving logic from the sampling process. This is achieved through a three-stage pipeline:

1. Compilation

KUS first transforms the Boolean formula (typically provided in Conjunctive Normal Form, or CNF) into a d-DNNF (Deterministic Decomposable Negation Normal Form). This structure is a specialized directed acyclic graph (DAG) that represents the underlying logic of the constraints in a way that makes counting and sampling computationally efficient.

The d-DNNF graph structure allows for efficient logic traversal and counting.

2. Annotation (Bottom-Up Pass)

Once the graph is compiled, KUS performs a bottom-up traversal. Starting from the leaves, it calculates the number of possible satisfying assignments for every node in the graph. This step effectively "pre-computes" the solution space.

3. Sampling (Top-Down Pass)

To generate a sample, KUS performs a top-down traversal from the root. At "AND" nodes, it follows all paths. At "OR" nodes, it performs a Bernoulli trial weighted by the counts generated in the annotation phase to decide which path to follow.

Annotation and sampling logic at OR nodes using weighted Bernoulli trials to ensure uniformity.

Experimental Evaluation

The researchers evaluated KUS against a massive suite of 1,425 benchmarks derived from diverse domains, including Bayesian analysis, circuit design, and software bug synthesis. KUS was compared against leading tools such as SPUR and UniGen2.

Key Results

  • Performance: KUS demonstrated a 1.7x geometric speedup over SPUR and an 8.3x speedup over UniGen2. In specific instances, KUS was three orders of magnitude (1000x) faster.
  • Robustness: KUS successfully solved 1,049 instances within the time limit, outperforming SPUR (980) and UniGen2 (370).
  • Statistical Integrity: KL-divergence tests confirmed that the samples produced by KUS are statistically indistinguishable from an ideal uniform distribution.

Discussion: Amortized Complexity and Incremental Sampling

The primary advantage of KUS is its amortized complexity. While the initial compilation and annotation steps are computationally expensive, they only occur once. Subsequent sampling requests are nearly instantaneous. This makes KUS the "killer app" for incremental sampling, where engineers may request small batches of samples repeatedly. Unlike previous tools that often restart their search from scratch, KUS reuses the compiled graph, maintaining its speed advantage regardless of the sample count.

Conclusion and Future Work

KUS represents a significant leap forward in uniform sampling for Boolean constraints. While the approach is currently limited by the memory requirements of large d-DNNF graphs, its performance scales directly with improvements in underlying compiler technology. Future work includes developing portfolio-based samplers that can dynamically select between different compilers to handle even more complex industrial formulas.

Summary updated

BibTeX
@inproceedings{sharma2018knowledge,
  author = {Shubham Sharma and Rahul Gupta and Subhajit Roy and Kuldeep S. Meel},
  title = {{Knowledge Compilation meets Uniform Sampling}},
  booktitle = {LPAR},
  year = {2018},
  doi = {10.29007/h4p9},
}
Figure