Algorithmic Improvements in Approximate Counting for Probabilistic Inference: From Linear to Logarithmic SAT Calls.

Supratik Chakraborty, Kuldeep S. Meel, Moshe Y. VardiIJCAI 2016 · OpenReview

Abstract

Probabilistic inference via model counting has emerged as a scalable technique with strong formal guarantees, thanks to recent advances in hashing-based approximate counting. State-of-the-art hashing-based counting algorithms use an NP oracle, such that the number of oracle invocations grows linearly in the number of variables $n$ in the input constraint. We present a new approach to hashing-based approximate model counting in which the number of oracle invocations grows logarithmically in $n$, while still providing strong theoretical guarantees. We use this technique to design an algorithm for #CNF with strongly probably approximately correct (SPAC) guarantees, i.e. PAC guarantee plus expected return value matching the exact model count. Our experiments show that this algorithm outperforms state-of-the-art techniques for approximate counting by 1-2 orders of magnitude in running time. We also show that our algorithm can be easily adapted to give a new fully polynomial randomized approximation scheme (FPRAS) for #DNF.

Introduction

Probabilistic inference—calculating the probability of an event given specific evidence—is a cornerstone of modern artificial intelligence, with applications ranging from medical diagnostics to computer vision. However, exact inference is computationally intractable, falling into the #P-complete complexity class.

A powerful modern approach to this problem is to reduce inference to constrained counting (#SAT): counting the number of assignments that satisfy a set of Boolean constraints. State-of-the-art tools like ApproxMC utilize "universal hashing" to partition the solution space into manageable cells. By using a SAT solver to count solutions in a single cell and scaling that number up, these tools provide approximate counts with formal guarantees.

The primary bottleneck in previous iterations of these algorithms was the search for the "right" partition size. Previous algorithms performed a linear search, probing the solution space one step at a time. This required a number of SAT solver calls that grew linearly with the number of variables ($n$). Given that SAT solver calls are the most computationally expensive part of the process, this linear scaling significantly limited the size of problems that could be addressed.

The ApproxMC2 Algorithm

This paper introduces ApproxMC2, which achieves a significant leap in efficiency through three key algorithmic innovations:

  1. Logarithmic Search (LogSATSearch): Instead of a linear search, the algorithm employs a "galloping search" (exponentially increasing the step size) followed by a binary search to identify the optimal hash partition size. This reduces the complexity from $O(n)$ to $O(\log n)$ SAT calls.
  2. Dependent Hash Functions: To enable binary search, the algorithm utilizes "prefix-slices" of hash functions. Unlike previous versions that generated entirely new, independent hash functions for every search step, ApproxMC2 uses a single long hash and takes prefixes of it. This creates a nested structure in the solution cells that allows for efficient searching.
  3. Information Reuse: The algorithm tracks the result of the previous iteration to start its next search. Since the optimal partition size typically does not change drastically between iterations, this heuristic further prunes the search space.

Crucially, the authors prove that despite these dependencies, the algorithm still provides Strongly Probably Approximately Correct (SPAC) guarantees. This ensures the expected value of the count is exactly equal to the true count, and the result remains within a user-defined tolerance ($\epsilon$) with high confidence ($1-\delta$).

Experimental Evaluation

The authors evaluated ApproxMC2 on a diverse suite of benchmarks, including probabilistic inference (grid networks, DQMR networks), physics models (Ising models), and hardware/software verification (bit-blasted SMTLIB benchmarks, ISCAS89 circuits).

Performance and Efficiency

ApproxMC2 demonstrated a dramatic improvement in performance, outperforming the previous state-of-the-art (ApproxMC) by 1 to 2 orders of magnitude in running time across nearly all benchmarks. It successfully solved large instances, such as tutorial3 with approximately 486,000 variables, where the original ApproxMC timed out after 8 hours.

Performance comparison between ApproxMC and ApproxMC2 across various benchmarks.

As shown in the table above, the reduction in SAT solver calls is substantial. For instance, in the progsyn_20 benchmark, the number of calls dropped from 34,815 to just 2,308, resulting in a runtime reduction from over 20,000 seconds to under 1,800 seconds.

Accuracy and Theoretical Guarantees

Despite the reduction in computational effort, ApproxMC2 maintains high accuracy. While the theoretical tolerance was set to $\epsilon=0.8$, the actual observed error was significantly lower, with a geometric mean of just 0.021.

Comparison of ApproxMC2 solution counts against exact count bounds (±1.8x).

The figure above illustrates that ApproxMC2's counts consistently fall within the narrow bounds of the exact solution count, validating the robustness of the SPAC guarantees in practice.

Conclusion

The transition from linear to logarithmic SAT calls represents a major milestone in approximate model counting. By demonstrating that total independence between hash functions is not strictly necessary for rigorous bounds, the authors have unlocked significant scalability. Future work may involve transforming ApproxMC2 into an "anytime" algorithm and combining logarithmic search with shorter XOR constraints to further reduce the load on SAT solvers. Additionally, these improvements can be extended to weighted model counting, broadening their applicability to complex probabilistic graphical models.

Summary updated

Abstract

Probabilistic inference via model counting has emerged as a scalable technique with strong formal guarantees, thanks to recent advances in hashing-based approximate counting. State-of-the-art hashing-based counting algorithms use an NP oracle, such that the number of oracle invocations grows linearly in the number of variables n in the input constraint. We present a new approach to hashing-based approximate model counting in which the number of oracle invocations grows logarithmically in n, while still providing strong theoretical guarantees. We use this technique to design an algorithm for #CNF with strongly probably approximately correct (SPAC) guarantees, i.e. PAC guarantee plus expected return value matching the exact model count. Our experiments show that this algorithm outperforms state-of-the-art techniques for approximate counting by 1-2 orders of magnitude in running time. We also show that our algorithm can be easily adapted to give a new fully polynomial randomized approximation scheme (FPRAS) for #DNF.
BibTeX
@inproceedings{chakraborty2016algorithmic,
  author = {Supratik Chakraborty and Kuldeep S. Meel and Moshe Y. Vardi},
  title = {{Algorithmic Improvements in Approximate Counting for Probabilistic Inference: From Linear to Logarithmic SAT Calls.}},
  booktitle = {IJCAI},
  year = {2016},
  url = {https://openreview.net/forum?id=uOJc-wPelzH},
}
Figure