Auditable Algorithms for Approximate Model Counting

Kuldeep S. Meel, Supratik Chakraborty, S. Akshay

Abstract

Model counting is a fundamental problem in computer science with broad applications in verification and probabilistic reasoning. While approximate counting algorithms offer a computationally feasible alternative to exact counting, their implementations are often complex and difficult to verify. This paper introduces the concept of "auditability" for approximate model counting, where an algorithm produces both a count and a mathematical certificate that a third-party auditor can use to verify the result. We explore a novel complexity trade-off: by increasing the computational power of the counting oracle from $\Sigma^P_2$ to $\Sigma^P_3$, we can significantly reduce the size and complexity of the audit certificate, achieving an audit complexity of $O(n \log n)$ variables.

Introduction

Determining the number of satisfying assignments for a Boolean formula—known as model counting—is a #P-hard problem. Because exact counting is often intractable for large-scale instances, researchers have developed efficient algorithms for approximate model counting. However, these tools face a significant "trust gap." The software implementations are intricate, and a user has no easy way to verify if a reported count (e.g., $10^{15}$) is even approximately correct without re-executing the entire computation or formally verifying the entire codebase.

This research addresses this challenge by designing auditable algorithms. An auditable algorithm provides a result along with a certificate of correctness. A lightweight auditor can then use this certificate to confirm the result's validity for a specific instance, shifting the burden of trust from the entire software system to a small, verifiable proof.

The Auditability Framework

The authors analyze deterministic approximate counting through the lens of audit complexity, specifically focusing on the number of variables required in the formulas that an auditor must solve. The core technique involves using $k$-wise independent hash functions to partition the solution space into "cells." By proving that these cells are neither too full nor too empty, the algorithm can bound the total count.

Algorithmic Trade-offs

The research highlights a critical relationship between the complexity of the counting algorithm and the efficiency of the audit:

  1. Stockmeyer’s Algorithm (Baseline): The classic Stockmeyer algorithm utilizes a $\Sigma^P_2$ oracle. While it can be audited, the resulting certificate is relatively large, requiring the auditor to verify formulas over $O(n^2 \log^2 n)$ variables.
  2. EqualCellsCounter: By allowing the counter to use a more powerful $\Sigma^P_3$ oracle, the authors demonstrate that the certificate complexity can be reduced to $O(n^2)$ variables.
  3. AFCounter: The final proposed algorithm, AFCounter, also utilizes a $\Sigma^P_3$ oracle but achieves a significantly more efficient audit complexity of $O(n \log n)$ variables.

Key Insights

The Complexity Trade-off

The most significant finding is that audit complexity can be traded for counting complexity. Moving the counter from the $\Sigma^P_2$ class to the $\Sigma^P_3$ class allows for the generation of certificates that are much easier for a low-power auditor to process. This is a counter-intuitive result that suggests that "harder" computation can sometimes produce "simpler" proofs.

Certifying "True" vs. "False"

In traditional approaches, auditors often had to verify why a counter stopped (proving a "False" result from an oracle), which is computationally expensive. The authors' new methodology focuses on certifying "True" statements that simultaneously provide upper and lower bounds, streamlining the verification process.

Fine-Grained Auditing

Rather than relying solely on asymptotic Big-O notation, the paper emphasizes fine-grained complexity. By minimizing the actual number of variables ($n$) in the auditor's formulas, the authors ensure that the auditing process remains practical for real-world solvers where variable count is a primary driver of performance.

Results and Implications

The study successfully demonstrates that auditable approximate counting is possible with a constant-factor approximation (e.g., a 16-factor approximation). The reduction of audit complexity to $O(n \log n)$ variables via the AFCounter algorithm represents a substantial improvement over the $O(n^2 \log^2 n)$ baseline.

However, these gains come with a practical cost: the requirement of a $\Sigma^P_3$ oracle. In practical applications, $\Sigma^P_3$ queries are significantly more difficult to solve than $\Sigma^P_2$ queries, which may limit the performance of the counter on extremely large instances. Furthermore, this framework is currently limited to deterministic algorithms; providing similar certificates for randomized (PAC) algorithms remains a significant open challenge, as a single execution of a randomized process does not inherently prove its own probabilistic guarantees.

Conclusion

This work establishes a rigorous foundation for auditable approximate model counting. By formalizing the trade-off between oracle power and certificate size, the authors provide a path toward more transparent and trustworthy automated reasoning tools. Future research may extend these "auditability" principles to other hard combinatorial problems and explore the feasibility of auditing probabilistic counting methods.

Summary updated

Abstract

The problem of model counting, i.e., counting satisfying assignments of a Boolean formula, is a fundamental problem in computer science, with diverse applications. Given #P-hardness of the problem, many algorithms have been developed over the years to provide an approximate model count. Recently, building on the practical success of SAT-solvers used as NP oracles, the focus has shifted from theory to practical implementations of such algorithms. This has brought to focus new challenges. In this paper, we consider one such challenge – that of auditable deterministic approximate model counters wherein a counter should also generate a certificate, which allows a user (often with limited computational power) to independently audit whether the count returned by an invocation of the algorithm is indeed within the promised bounds. We start by examining a celebrated approximate model counting algorithm due to Stockmeyer that uses polynomially many calls to a \Sigma^2_P oracle, and show that it can be audited via a \Pi^2_P formula on (n^2 log^2 n) variables, where n is the number of variables in the original formula. Since n is often large (10’s to 100’s of thousands) for typical instances, we ask if the count of variables in the certificate formula can be reduced – a critical question towards potential implementation. We show that this improvement in certification can be achieved with a tradeoff in the counting algorithm’s complexity. Specifically, we develop new deterministic approximate model counting algorithms that invoke a \Sigma^3_P oracle, but can be certified using a \Pi^2_P formula on fewer variables: our final algorithm uses just (n log n) variables. Our study demonstrates that one can simplify certificate checking significantly if we allow the counting algorithm to access a slightly more powerful oracle. We believe this shows for the first time how the audit complexity can be traded for the 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