Towards Real-Time Approximate Counting

Yash Pote, Kuldeep S. Meel, Jiong YangAAAI 2025 · OpenReview

TL;DR

This paper introduces ApproxMC7, a novel approximate model counting algorithm that significantly reduces the number of calls to SAT solvers, enabling real-time applications. By achieving a similar (ε, δ)-guarantee with drastically fewer SAT calls, ApproxMC7 offers substantial speedups and solves more instances than its predecessor, ApproxMC.

What Problem Does This Paper Address?

Model counting, the task of determining the number of satisfying assignments for a Boolean formula, is a fundamental problem with applications in various fields like AI, verification, and biology. However, exact model counting is computationally intractable (#P-complete). While approximate counting methods offer a practical alternative by providing a (1+ε)-factor estimate with a probability of at least 1-δ, current state-of-the-art approaches like ApproxMC require hundreds of calls to SAT solvers for a single query. This high SAT call count becomes a bottleneck, especially in time-constrained scenarios where numerous approximate counts are needed. This paper addresses the challenge of reducing the SAT call overhead in approximate model counting to enable real-time applications.

Methods

The paper proposes ApproxMC7, an approximation scheme designed for demanding applications with low time limits. The core innovation lies in drastically reducing the number of SAT calls required, particularly in the "large-ε" regime. While the previous state-of-the-art, ApproxMC, involves a complex procedure of repeatedly partitioning the solution space and checking cell sizes with SAT solvers until a cell contains a small number of solutions (defined by a threshold thresh), ApproxMC7 simplifies this by setting thresh to one. This allows ApproxMC7 to use a single SAT call to check the cell size.

The algorithm leverages 2-universal hash functions for partitioning the solution space. A key subroutine, ApproxMC7Core, uses a galloping search to find an appropriate split point (m) for the solution space. This search involves a doubling phase to quickly narrow down the range and a binary phase to pinpoint the exact split. The estimate is then derived from the number of cells and the count within a selected cell, scaled by a factor derived from the approximation parameters. The overall algorithm then uses a median trick over multiple estimates to boost confidence and achieve the desired (ε, δ)-guarantee. The proof of correctness for ApproxMC7 is presented as significantly simpler and shorter than that of previous methods.

Datasets

The paper evaluates ApproxMC7 on a comprehensive set of 2,247 instances. These instances are drawn from various applications, including:

  • Quantitative verification of neural networks
  • Model Counting Competitions (2020-2022)
  • Program synthesis
  • Quantitative control improvisation
  • Quantification of software properties
  • Adaptive chosen ciphertext attacks

The authors also mention using CNF formulae from a case study on automating chosen ciphertext attacks, specifically from the work of Beck, Zinkus, and Green (2020). They omit trivial instances that ApproxMC6 could solve within one second from their benchmarks.

Key Insights and Ideas

  • Single SAT Call for Cell Size: The most significant insight is that by setting the solution threshold (thresh) to one, ApproxMC7 can determine if a cell is "small enough" with just a single SAT call. This is a dramatic reduction from hundreds of calls in previous methods.
  • Simpler Proof of Correctness: The simplified approach of ApproxMC7 leads to a much more accessible proof of its (ε, δ)-guarantee, contrasting with the lengthy proofs required for prior algorithms. This simplicity can facilitate adaptation to other use cases.
  • Real-Time Applicability: The drastic reduction in SAT calls directly translates to improved performance, making approximate counting feasible in real-time scenarios where latency is critical.
  • Trade-off Between Accuracy and Calls: The paper demonstrates that a good approximate count can be achieved with a surprisingly small number of SAT calls, challenging the notion that high accuracy necessitates extensive solver invocations.

Key Results

  • Instance Solving: ApproxMC7 solved 1,072 out of 2,247 instances, which is 271 more instances than ApproxMC6 (801 solved).
  • PAR-2 Score: ApproxMC7 achieved a PAR-2 score of 115, representing a 24% improvement over ApproxMC6.
  • Speedup: ApproxMC7 delivered a 2.1x geometric mean speedup over ApproxMC6 on instances solved by both. The maximum individual speedup observed was up to 70x.
  • SAT Call Reduction: The paper highlights a significant reduction in SAT calls, with a heatmap showing ratios up to 18x fewer calls for ApproxMC7 compared to ApproxMC6, especially for larger ε values. In a sampled subset, ApproxMC7 used 10x fewer SAT calls.
  • Approximation Quality: In empirical evaluations, ApproxMC7's estimates satisfied the (ε, δ)-guarantee. Only 6% of estimates fell outside the guaranteed range, which is well within the expected error probability. The observed error was 1.59, significantly smaller than the guaranteed ε of 13.
  • Case Study: In a case study on automating chosen ciphertext attacks, ApproxMC7 achieved a 7x speedup against ApproxMC6.

Limitations and Future Work

  • Low-Accuracy Regime Focus: The paper explicitly focuses on improving performance in the "low-accuracy regime" (large ε). While it offers significant advantages there, its performance in very high-accuracy scenarios might be less dramatically improved compared to existing methods.
  • Future Work: The authors suggest that the simpler proof of correctness for ApproxMC7 makes it more adaptable to other use cases, hinting at potential extensions and applications. The paper also implicitly suggests that further optimizations for approximate counting are possible, building on the insights gained from ApproxMC7.

Summary updated

BibTeX
@inproceedings{pote2025towards,
  author = {Yash Pote and Kuldeep S. Meel and Jiong Yang},
  title = {{Towards Real-Time Approximate Counting}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  url = {https://openreview.net/forum?id=Yt7pGr1F6v},
}
Figure