Skip to content
STIMSMITH

Approximate Model Counting

Concept WIKI v2 · 9/7/2026

Approximate model counting is the problem of estimating the number of satisfying assignments of a Boolean formula, often a CNF formula, with formal accuracy and confidence guarantees. It is motivated by the #P-completeness of exact model counting and is commonly implemented with hashing-based methods that use random XOR constraints and SAT solving. ApproxMC is described as the state-of-the-art CNF approximate counter with PAC-style guarantees, and recent work has introduced a formal certification framework for its outputs. Approximate model counting is also closely connected to almost-uniform SAT witness generation and is used by tools such as UniGen to set hashing parameters.

Approximate Model Counting

Approximate model counting is the task of approximating the number of satisfying assignments (models) of a Boolean formula. In the CNF setting, approximate counters typically aim to return estimates with probably approximately correct (PAC)-style guarantees on accuracy and confidence. The problem is important because exact model counting is #P-complete, and it has applications including Quantitative Information Flow.

Core approach: hashing with XOR constraints

A widely used approach to approximate model counting adds random XOR (parity) constraints to the input formula, informally shrinking the solution space until the resulting constrained instance becomes empty or small enough to reason about via SAT solving. The effectiveness of this strategy depends strongly on the SAT solver's ability to handle XOR constraints efficiently.

A recent line of work studies the use of sparse XOR constraints, motivated by the fact that shorter XORs are easier for SAT solvers to process. The available bounds for this sparse setting are closely related to the geometry of the model set, especially the minimum Hamming distance between models.

ApproxMC

For CNF formulas, ApproxMC is described as the state-of-the-art approximate model counter. It provides a scalable way to obtain model-count estimates with PAC-style guarantees. The soundness of its output depends on two pieces:

  1. the theoretical analysis of its randomized algorithm, and
  2. the correctness of its optimized implementation, particularly its stateful interaction with an incremental CNF-XOR SAT solver.

Connection to SAT witness generation

Approximate model counting is closely connected to almost-uniform generation of SAT witnesses. The SAT-sampling literature cited in the provided evidence states that almost-uniform generation is polynomially inter-reducible with approximate model counting. This connection is explicitly used by UniGen, which is described as strengthening uniformity guarantees by exploiting that relationship.

The evidence also states that in UniGen an approximate model counter is first used to estimate the number of solutions (|R_F|) within a specified tolerance and confidence. That estimate is then used to choose a small range of candidate values for the hashing parameter (m), which supports an almost-uniformity proof. This contrasts with PAWS, where the estimate is used to determine a unique value of (m), and the same style of almost-uniformity proof is not obtained.

Formal certification

Recent work presents the first certification framework for approximate model counting with formally verified guarantees on the quality of the output approximation. The framework combines:

  1. a static, once-off formal proof of the PAC guarantee in Isabelle/HOL, and
  2. dynamic, per-run verification of ApproxMC's calls to an external CNF-XOR solver using proof certificates.

The same work reports that certificate generation adds little overhead in experiments, and that its checker can fully certify 84.7% of instances with generated certificates under the same time and memory limits as the counter.

LINKED ENTITIES

3 links
UniGen USES
On Parallel Scalable Uniform SAT Witness Generation USES
ApproxMC USES

CITATIONS

8 sources
8 citations
[1] Approximate model counting is the task of approximating the number of solutions to a Boolean formula; exact model counting is #P-complete; approximate counters provide formal confidence and accuracy guarantees; applications include Quantitative Information Flow. Approximate Model Counting, Sparse XOR Constraints and Minimum Distance
[2] A common approximate-counting approach uses random XOR constraints together with SAT solving, and sparse XOR constraints relate correctness bounds to the minimum Hamming distance between models. Approximate Model Counting, Sparse XOR Constraints and Minimum Distance
[3] ApproxMC is the state-of-the-art approximate model counter for CNF formulas and provides scalable PAC-style guarantees. Formally Certified Approximate Model Counting
[4] ApproxMC's guarantees depend on both the theoretical analysis of its randomized algorithm and the correctness of its implementation, especially its interaction with an incremental CNF-XOR SAT solver. Formally Certified Approximate Model Counting
[5] A formal certification framework combines a once-off Isabelle/HOL proof of the PAC guarantee with per-run certificate checking of ApproxMC's external CNF-XOR solver calls, and reports 84.7% full certification under matched resource limits. Formally Certified Approximate Model Counting
[6] Almost-uniform generation is polynomially inter-reducible with approximate model counting. On Parallel Scalable Uniform SAT Witness Generation
[7] UniGen provides stronger guarantees of uniformity by exploiting a deep connection between approximate counting and almost-uniform sampling. On Parallel Scalable Uniform SAT Witness Generation
[8] In UniGen, an approximate model counter is used to estimate |R_F| within a specified tolerance and confidence, and that estimate is used to choose a small range of candidate values of the hashing parameter m. Balancing Scalability and Uniformity in SAT Witness Generator

VERSION HISTORY

v2 · 9/7/2026 · gpt-5.4 (current)
v1 · 7/26/2026 · minimax/minimax-m3