Studies in Solution Sampling

Vibhav Gogate, Rina DechterAAAI 2008 · OpenReview

Abstract: We introduce novel algorithms for generating random solutions from a uniform distribution over the solutions of a boolean satisfiability problem. Our algorithms operate in two phases. In the first phase, we use a recently introduced SampleSearch scheme to generate biased samples while in the second phase we correct the bias by using either Sampling/Importance Resampling or the Metropolis-Hastings method. Unlike state-of-the-art algorithms, our algorithms guarantee convergence in the limit. Our empirical results demonstrate the superior performance of our new algorithms over several competing schemes.

Introduction

Generating uniform random solutions for complex logic problems, such as Boolean Satisfiability (SAT), is a fundamental challenge in computer science. This task is critical for applications in hardware verification, automated planning, and probabilistic reasoning. However, it is notoriously difficult, as it is closely related to the #P-complete problem of counting solutions.

Existing approaches typically fall into two categories: exact methods, which provide perfectly uniform samples but suffer from exponential time and memory requirements, and approximate methods, which are faster but often produce biased results. For instance, the SampleSearch algorithm is efficient at finding solutions but tends to favor certain areas of the solution space based on variable assignment order. This paper bridges the gap by introducing methods that maintain the efficiency of approximate search while providing mathematical guarantees of convergence to a uniform distribution.

Methodology: Correcting Search Bias

The proposed approach utilizes a two-phase framework. In the first phase, the SampleSearch algorithm acts as a "proposal engine," using randomized backtracking guided by approximate inference to find solutions. Because this search is inherently biased, it samples from what is termed the backtrack-free distribution.

Figure 4: Illustration of the search space and backtrack-free distribution (b, c) for a sample SAT problem (a).

To correct this bias, the authors implement two statistical techniques in the second phase:

  1. SampleSearch-SIR (Sampling/Importance Resampling): This method generates a large pool of solutions and assigns a weight to each based on how much it was over- or under-represented during the search. A subset is then resampled according to these weights.
  2. SampleSearch-MH (Metropolis-Hastings): This creates a Markov chain of solutions. Starting from an initial solution, the algorithm proposes moves to new solutions found via SampleSearch. An acceptance rule ensures that, over time, the chain converges to a uniform distribution.

The key innovation lies in the ability to mathematically define the bias of the underlying search path, allowing these statistical tools to effectively "cancel out" the search bias and produce high-quality samples.

Experimental Results

The researchers evaluated the new algorithms against state-of-the-art competitors like SampleSAT and pure SampleSearch across several hard SAT benchmarks, including grid pebbling, logistics planning, and circuit verification. Performance was measured using KL Distance, which quantifies the difference between the generated sample distribution and the true uniform distribution (where lower values indicate higher accuracy).

Figure 5: KL Distance over time for various sampling algorithms on a grid pebbling benchmark (sat-grid-pbl-0025.cnf).

As shown in the experimental data, the SIR and MH variants consistently achieved significantly lower KL distances than competing schemes. For example, on a specific pebbling instance (grid-pbl-10), SampleSearch-SIR reached a KL distance of 0.002, whereas SampleSAT remained much higher at 0.110. Even with the added computational overhead of calculating weights and thinning samples, these new methods proved more efficient within a fixed time limit.

Conclusion and Future Work

This study demonstrates that combining randomized search with statistical correction techniques provides a robust path toward uniform solution sampling. While these algorithms are guaranteed to converge in the limit, practical challenges remain. The researchers observed that error rates sometimes plateau before dropping further, a behavior that warrants future investigation. Additionally, improving "finite-time" convergence—ensuring the error drops rapidly in the initial stages of execution—remains a primary goal for future research in the field.

Summary updated

Abstract

We introduce novel algorithms for generating random solutions from a uniform distribution over the solutions of a boolean satisfiability problem. Our algorithms operate in two phases. In the first phase, we use a recently introduced SampleSearch scheme to generate biased samples while in the second phase we correct the bias by using either Sampling/lmportance Resampling or the Metropolis-Hastings method. Unlike state-of-the-art algorithms, our algorithms guarantee convergence in the limit. Our empirical results demonstrate the superior performance of our new algorithms over several competing schemes.
BibTeX
@inproceedings{gogate2008studies,
  author = {Vibhav Gogate and Rina Dechter},
  title = {{Studies in Solution Sampling}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
  url = {https://openreview.net/forum?id=S1NSqCxdWH},
}
Figure