# A New Probabilistic Algorithm for Approximate Model Counting

arXiv: https://arxiv.org/abs/1706.03906 · HTML: https://mlsanity.com/paper/1706.03906/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jun 2017.

## Built on by (most cited first, 1 of 1)

- [Approximate SMT Counting Beyond Discrete Domains](https://mlsanity.com/paper/2507.18612/) (2025)

## Abstract (arXiv)

Constrained counting is important in domains ranging from artificial intelligence to software analysis. There are already a few approaches for counting models over various types of constraints. Recently, hashing-based approaches achieve both theoretical guarantees and scalability, but still rely on solution enumeration. In this paper, a new probabilistic polynomial time approximate model counter is proposed, which is also a hashing-based universal framework, but with only satisfiability queries. A variant with a dynamic stopping criterion is also presented. Empirical evaluation over benchmarks on propositional logic formulas and SMT(BV) formulas shows that the approach is promising.