Auditable Algorithms for Approximate Model Counting

Kuldeep S. Meel, Supratik Chakraborty, S. Akshay

Abstract

Model counting, or determining the number of satisfying assignments for a Boolean formula, is a fundamental problem in computer science with applications ranging from probabilistic reasoning to formal verification. Given the #P-hardness of the problem, research has focused on practical approximate counting algorithms. However, as these algorithms are integrated into critical systems, the need for trust arises. This paper introduces the concept of auditable approximate counters: algorithms that provide not only a count but also a certificate that a verifier with limited computational power can use to check the result. We demonstrate a fundamental complexity tradeoff: by allowing the counting algorithm to access a slightly more powerful oracle ($\Sigma_3^P$ instead of $\Sigma_2^P$), we can significantly reduce the size of the certificate from $O(n^2 \log^2 n)$ to $O(n \log n)$ variables. This work establishes the first framework for trading counting complexity for audit efficiency.

Introduction

Model counting (#SAT) is the task of finding the number of satisfying assignments for a given Boolean formula. While essential for reliability analysis and artificial intelligence, it is computationally intractable for large-scale problems. Modern approximate counters have made significant strides in performance, yet they often operate as "black boxes." In critical applications, simply receiving a numerical output is insufficient; we require a way to verify that the output is within the promised approximation bounds without re-running the entire counting process.

This research addresses the challenge of auditability. An auditable algorithm produces a certificate alongside its count. An independent auditor can then use this certificate to prove the count's validity. The primary bottleneck in this process is the size and complexity of the certificate, which we measure by the number of variables and the power of the logical oracle required for verification.

Methods and Algorithmic Framework

The study explores three primary deterministic approximate counting approaches, each offering different balances between counting effort and audit complexity.

1. Auditing Stockmeyer’s Algorithm

Stockmeyer’s algorithm is the standard for deterministic approximate counting, utilizing a $\Sigma_2^P$ oracle. The authors demonstrate that this algorithm can be made auditable. However, the resulting certificates are "heavy," requiring the auditor to verify formulas over $O(n^2 \log^2 n)$ variables. For large-scale formulas where $n$ is already significant, this quadratic growth makes verification practically difficult.

2. The EqualCells Approach

To address the certificate size, the researchers proposed EqualCellsCounter. This algorithm shifts more of the computational burden to the counting phase by using a $\Sigma_3^P$ oracle. This investment allows the auditor to verify the result using a certificate over $O(n^2)$ variables, a notable improvement over the Stockmeyer-based approach.

3. The AFCounter (Holes Approach)

The most efficient algorithm presented is AFCounter. It utilizes a novel Quantified Boolean Formula (QBF) construction known as $\phi_{holes}$. This formula asserts that for a specific partition of the solution space, every "cell" contains at least one solution. By combining this with the technique of creating multiple independent copies of a formula, AFCounter achieves a massive reduction in audit complexity, requiring only $O(n \log n)$ variables for the certificate.

The Complexity Tradeoff

A central insight of this work is the complexity tradeoff. The research proves that one can "buy" a simpler, more efficient audit by utilizing a more powerful computational oracle during the initial counting phase. Specifically, moving from a $\Sigma_2^P$ oracle to a $\Sigma_3^P$ oracle for counting enables the generation of much smaller certificates.

Furthermore, the authors solve the "False" certificate problem. In many verification contexts, proving a count is not too high is difficult because it requires certifying a negative result. The constructions in this paper are designed so that a "True" result from the auditor's oracle simultaneously establishes both the lower and upper bounds of the approximation.

Key Results

The following table summarizes the hierarchy of auditability established for a 16-factor approximate count:

Algorithm Counting Oracle Audit Oracle Certificate Size (Variables)
Stockmeyer $\Sigma^P_2$ $\Sigma^P_2$ $O(n^2 \log^2 n)$
EqualCellsCounter $\Sigma^P_3$ $\Sigma^P_2$ $O(n^2)$
AFCounter $\Sigma^P_3$ $\Sigma^P_2$ $O(n \log n)$

AFCounter represents a significant step forward, providing a constant-factor approximation while keeping the auditor's task significantly lighter than previous methods.

Conclusion and Future Work

This paper demonstrates that auditable model counting is theoretically feasible and that the complexity of verification can be managed through strategic algorithmic choices. While the requirement of a $\Sigma_3^P$ oracle for counting presents a challenge for current SAT/QBF solvers, the reduction in certificate size to $O(n \log n)$ variables makes independent verification much more accessible for real-world formulas.

Future research will focus on tightening the approximation factors and exploring auditability in the context of randomized (PAC) counters, which are more common in practical high-performance implementations but present unique challenges for deterministic certification.

Summary updated

Abstract

Model counting, or counting the satisfying assignments of a Boolean formula, is a fundamental problem with diverse applications. Given #P-hardness of the problem, developing algorithms for approximate counting is an important research area. Building on the practical success of SAT-solvers, the focus has recently shifted from theory to practical implementations of approximate counting algorithms. This has brought to focus new challenges, such as the design of auditable approximate counters that not only provide an approximation of the model count, but also a certificate that a verifier with limited computational power can use to check if the count is indeed within the promised bounds of approximation. Towards generating certificates, we start by examining the best-known deterministic approximate counting algorithm that uses polynomially many calls to a $\Sigma_2^P$ oracle. We show that this can be audited via a $\Sigma_2^P$ oracle with the query constructed over $n^2 \log^2 n$ variables, where the original formula has $n$ variables. Since $n$ is often large, we ask if the count of variables in the certificate can be reduced -- a crucial question for potential implementation. We show that this is indeed possible with a tradeoff in the counting algorithm's complexity. Specifically, we develop new deterministic approximate counting algorithms that invoke a $\Sigma_3^P$ oracle, but can be certified using a $\Sigma_2^P$ oracle using certificates on far fewer variables: our final algorithm uses only $n \log n$ variables. Our study demonstrates that one can simplify auditing significantly if we allow the counting algorithm to access a slightly more powerful oracle. This shows for the first time how audit complexity can be traded for complexity of approximate counting.
BibTeX
@inproceedings{meel2024auditable,
  author = {Kuldeep S. Meel and Supratik Chakraborty and S. Akshay},
  title = {{Auditable Algorithms for Approximate Model Counting}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i9.28936},
}
Figure