A New Probabilistic Algorithm for Approximate Model
Counting
Cunjing Ge1,3 , Feifei Ma1,2,3? , Tian Liu4 , Jian Zhang1,3

arXiv:1706.03906v1 [cs.AI] 13 Jun 2017

1

State Key Laboratory of Computer Science,
Institute of Software, Chinese Academy of Sciences
2
Laboratory of Parallel Software and Computational Science,
Institute of Software, Chinese Academy of Sciences
3
University of Chinese Academy of Sciences
4
School of Electronics Engineering and Computer Science, Peking University

Abstract. 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.

1

Introduction

Constrained counting, the problem of counting the number of solutions for a set of
constraints, is important in theoretical computer science and artificial intelligence. Its
interesting applications in several fields include probabilistic inference [25,10], planning [12], combinatorial designs and software engineering [23,15]. Constrained counting for propositional formulas is also called model counting, to which probabilistic
inference is easily reducible. However, model counting is a canonical #P-complete
problem, even for polynomial-time solvable problems like 2-SAT [31], thus presents
fascinating challenges for both theoreticians and practitioners.
There are already a few approaches for counting solutions over propositional logic
formulas and SMT(BV) formulas. Recently, hashing-based approximate counting achieves
both strong theoretical guarantees and good scalability [24]. The use of universal hash
functions in counting problems began in [28,30], but the resulting algorithm scaled
poorly in practice. A scalable approximate counter ApproxMC in [8] scales to large
problem instances, while preserves rigorous approximation guarantees. ApproxMC has
been extended to finite-domain discrete integration, with applications to probabilistic
inference [13,5,2], and improved by designing efficient universal hash functions [19,6]
and reducing the use of NP-oracle calls from linear to logarithmic [9].
?

Corresponding author

The basic idea in ApproxMC is to estimate the model count by randomly and iteratively cutting the whole space down to a small “enough” cell, using hash functions,
and sampling it. The total model count is estimated by a multiplication of the number
of solutions in this cell and the ratio of whole space to the small cell. To determine
the size of the small cell, which is essentially a small-scale model counting problem
with the model counts bounded by some thresholds, a model enumeration in the cell
is adopted. In previous works, the enumeration query was handled by transforming it
into satisfiability queries, which is much more time-consuming than a single satisfiability query. An algorithm called MBound [17] only invokes satisfiability query once for
each cut. Its model count is determined with high precision by the number of cuts down
to the boundary of being unsatisfiable. However, this property is not strong enough to
give rigorous guarantees, and MBound only returns an approximation of upper or lower
bound of the model count.
In this paper, a new hashing-based approximate counting algorithm, with only satisfiability query, is proposed, building on a correlation between the model count and
the probability of the hashed formula being unsatisfiable. Dynamic stopping criterion
for the algorithm to terminate, once meeting the theoretical guarantee of accuracy, are
presented. Like previous works, a theoretical termination bound T is shown. Theoretical insights over the efficiency of a prevalent heuristic strategy called leap-frogging are
also provided.
The proposed approach is a general framework easy to handle various types of constraints. Prototype tools for propositional logic formulas and SMT(BV) formulas are
implemented. An extensive evaluation on a suite of benchmarks demonstrates that (i)
the approach significantly outperforms the state-of-the-art approximate model counters, including a counter designed for SMT(BV) formulas, and (ii) the dynamic stopping criterion is promising. The statistical results fit well with the theoretical bound of
approximation, and it terminates much earlier before termination bound T is met.
The rest of this paper is organized as follows. Preliminary material is in Section 2,
related works in Section 3, the algorithm in Section 4, analysis in Section 5, experimental results in Section 6, and finally, concluding remarks in Section 7.

2

Preliminaries

Let F (x) denote a propositional logic formula on n variables x = (x1 , . . . , xn ). Let
S and SF denote the whole space and the solution space of F , respectively. Let #F
denote the cardinality of SF , i.e. the number of solutions of F .
(, δ)-bound To count #F , an (, δ) approximation algorithm is an algorithm which
on every input formula F ,  > 0 and δ > 0, outputs a number Ỹ such that Pr[(1 +
)−1 #F ≤ Ỹ ≤ (1 + )#F ] ≥ 1 − δ. These are called (, δ)-counters and (, δ)bound, respectively [21].
Hash Function Let HF be a family of XOR-based bit-level hash functions on
Lnthe variables of a formula F . Each hash function H ∈ HF is of the form H(x) = a0 i=1 ai xi ,
where a0 , . . . , an are Boolean constants. In the hashing procedure Hashing(F), a
function H ∈ HF is generated by independently and randomly choosing ai s from a uniform distribution. Thus for an assignment α, it holds that PrH∈HF (H(α) = true) = 21 .

Given a formula F , let Fi denote a hashed formula F ∧H1 ∧· · ·∧Hi , where H1 , . . . , Hi
are independently generated by the hashing procedure.
Satisfiability Query Let Solving(F) denote the satisfiability query of a formula F .
With a target formula F as input, the satisfiability of F is returned by Solving(F).
Enumeration Query Let Counting(F, p) denote the bounded solution enumeration query. With a constraint formula F and a threshold p (p ≥ 2) as inputs, a number s
is returned such that s = min(p − 1, #F ). Specifically, 0 is returned for unsatisfiable
F , or p = 1 which is meaningless.
SMT(BV) Formula SMT(BV) formulas are quantifier-free and fixed-size that combine
propositional logic formulas with constraints of bit-vector theory. For example, ¬(x +
y = 0) ∨ (x = y << 1), where x and y are bit-vector variables, << is the shift-left
operator, is a propositional logic formula ¬A ∨ B that combines bit-vector constraints
A ≡ (x + y = 0) and B ≡ (x = y << 1). To apply hash functions to an SMT(BV)
formula, a bit-vector is treated as a set of Boolean variables.

3

Related Works

[1] showed that almost uniform sampling from propositional constraints, a closely related problem to constrained counting, is solvable in probabilistic polynomial time with
an NP oracle. Building on this, [8] proposed the first scalable approximate model counting algorithm ApproxMC for propositional formulas. ApproxMC is based on a family
of 2-universal bit-level hash functions that compute XOR of randomly chosen propositional variables. Subsequently, [6] presented an approximate model counter that uses
word-level hash functions, which directly leverage the power of sophisticated SMT
solvers, though the framework of the probabilistic algorithm is similar to [8]. In the
current work, the family of hash functions in [8] is adopted, which was shown to be
3-independent in [18], and is revealed to possess better properties than expected by the
experimental results and the theoretical analysis in the current work.
For completeness, ApproxMC [8,11] is listed here as Algorithm 1. Its inputs are
a formula F and two accuracy parameters T and pivot. T determines the number of
times ApproxMCCore invoked, and pivot determines the threshold of the enumeration query. The function ApproxMCCore starts from the formula F0 , iteratively calls
Counting and Hashing over each Fi , to cut the space (cell) of all models of F0 using random hash functions, until the count of Fi is no larger than pivot, then breaks out
the loop and adds the approximation 2i s into list C. The main procedure ApproxMC
repeatedly invokes ApproxMCCore and collects the returned values, at last returning
the median number of list C. The general algorithm in [6] is similar to Algorithm 1, but
could cut the cell with dynamically determined proportion instead of the constant 21 ,
due to the word-level hash functions. [9] improves ApproxMCCore via binary search
to reduce the number of enumeration queries from linear to logarithmic. This binary
search improvement is orthogonal to the proposed algorithm in the current work.

Algorithm 1
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

4

function A PPROX MC(F , T , pivot)
for 1 to T do
c ← ApproxMCCore(F , p, pivot)
if (c 6= 0) then AddToList(C, c)
end for
return FindMedian(C)
end function
function A PPROX MCC ORE (F , pivot)
F0 ← F
for i ← 0 to ∞ do
s ← Counting(Fi , pivot + 1)
if (0 ≤ s ≤ pivot) then return 2i s
Hi+1 ← Hashing(F )
Fi+1 ← Fi ∧ Hi+1
end for
end function

Algorithm

In this section, a new hashing-based algorithm for approximate model counting, with
only satisfiability queries, will be proposed, building on some probabilistic approximate
correlations between the model count and the probability of the hashed formula being
unsatisfiable.
Let Fd = F ∧ H1 ∧ · · · ∧ Hd be a hashed formula resulted by iteratively hashing d
times independently over a formula F . Fd is unsatisfiable if and only if no solution of F
satisfies Fd , thus PrFd (Fd is unsat) = PrFd (Fd (α) = f alse, α ∈ SF ). The following
approximation is a key for the new algorithm
Pr(Fd is unsat) ≈ (1 − 2−d )#F .
Fd

(1)

Based on Equation (1), an approximation of #F is achieved by taking logarithm on
the value of PrFd (Fd is unsat), which is estimated in turn by sampling Fd . However, Equation (1) canQnot be proven directly, since it is equivalent to PrFd (Fd (α) =
f alse, α ∈ SF ) ≈ α∈SF PrFd (Fd (α) = f alse), but HF was only known to be
3-independent.
In the following, we consider a similar but different family of hash functions to
provide
Ln some intuition (not proof) about Equation (1). From the definition H(x) =
a0 i=1 ai xi , it holds that (i) PrH (H(α) = true) = 21 for any assignment α, and (ii)
|SH | = |S|
2 , unless a1 = · · · = an = 0. Now let G be a family of hash functions also
with these properties, defined as follows. Each hash function G in G is of the form
(
true x ∈ SG
G(x) =
.
f alse x 6∈ SG
The solution set SG is generated by sampling |S|
2 points in S without replacement (simple random sample). For any given assignment α, obviously PrG (G(α) = true) = 21 .

Moreover, G is not k-independent for k > |S|
2 , since the probability of more than
variables having the same value is always zero.

|S|
2

Theorem 1. Let Ĝd = G1 ∧ · · · ∧ Gd , where G1 , . . . , Gd are independently sampled
from G, and let Fd0 = F ∧ Ĝd . Then
lim Pr(Fd0 is unsat) = (1 − 2−d )#F .

n→∞ Fd0

(2)

Proof. Since PrG (G(α) = true) = 21 and Gi s are independent, we have PrĜd (Ĝd (α) =
d
true) = 12 . Let SĜd denote the solution space of Ĝd , then the expectation E(|SĜd |)
d
= 12 |S| = 2n−d . Since each Gi is generated by simple random sample and uniquely

determined by its solution set, the number of distinct functions of Ĝd is |S|S| | , and the
Ĝd

F|
. The probability of
number of distinct Ĝd s which are unsatisfiable over SF is |S−S
|S |
Ĝd

SF ∩ SĜd = ∅ is
|S−SF |
|SĜ |
d



 =

|S|
|SĜ |

2n −#F
2n−d

2n
2n−d


=

(2n − #F )!(2n − 2n−d )!
(2n )!(2n − #F − 2n−d )!

d

=

(2n − 2−d 2n − #F + 1)
(2n − 2−d 2n ) (2n − 2−d 2n − 1)
...
. (3)
n
n
2
2 −1
2n − #F + 1

The LHS (left-hand-side) of (3) is also PrFd0 (Fd0 is unsat). The RHS of (3) converges
to (1 − 2−d )#F as n → ∞.
t
u
Since HF and G have some common characteristics, Equations (2) and (1) may also
hold for HF . In practice for finite n, Equation (2) only holds approximately. To make
the value of PrFd0 (Fd0 is unsat) arbitrarily close to (1 − 2−d )#F , dummy variables
can be inserted into F while keeping #F unchanged, such as inserting a new variable
xn+1 with constraint xn+1 = true. These variables and constraints are meaningless for
SAT solvers and ignored at the beginning of the search. Experimental results indicate
that Equation (1) holds even without inserting any dummy variable. Here we assume
Equation (1) holds in convenience of describing our approach.
The pseudo-code for our approach is presented in Algorithm 2. The inputs are the
target formula F and a constant T which determines the number of times GetDepth
invoked. GetDepth calls Solving and Hashing repeatedly until an unsatisfiable
formula Fdepth is encountered, and returns the depth. Every time GetDepth returns a
depth, the value of C[i] is increased, for all i < depth. At line 9, the algorithm picks a
number d such that C[d] is close to T /2, since the error estimation fails when C[d]/T is
close to 0 or 1. The final counting result is returned by the formula log1−(1/2)d counter
T
at line 11. Theoretical analysis of the value of T and the correctness of algorithm are in
Section 5.
Dynamic Stopping Criterion The essence of Algorithm 2 is a randomized sampler over
a binomial distribution. The number of samples is determined by the value of T , which

Algorithm 2 Satisfiability Testing based Approximate Counter (STAC)
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

function STAC(F , T )
initialize C[i]s with zeros
for t ← 1 to T do
depth ← GetDepth(F )
for i ← 0 to depth − 1 do
C[i] ← C[i] + 1
end for
end for
pick a number d such that C[d] is closest to T /2
counter ← T − C[d]
return log1−2−d counter
/* return 0 when d = 0 */
T
end function
function G ET D EPTH (F )
F0 ← F
for i ← 0 to ∞ do
b ← Solving(Fi )
if (b is false) then return i
Hi+1 ← Hashing(Fi )
Fi+1 ← Fi ∧ Hi+1
end for
end function

is pre-computed for a given (, δ)-bound, and we loosen the bound of T to meet the
guarantee in theoretical analysis. However, it usually does not loop T times in practice.
A variation with dynamic stopping criterion is presented in Algorithm 3.
Line 2 to 7 is the same as Algorithm 2, still setting T as a stopping rule and terminating whenever t = T . Line 8 to 16 is the key part of this variation, calculating
the binomial proportion confidence intervalq[L, U ] of an intermediate result M for each

cycle. A commonly used formula q ± z1−δ q(1−q)
[3,32] is adopted, which is justified
t
by the central limit theorem to compute the 1 − δ confidence interval. The exact count
#F lies in the interval [L, U ] with probability 1 − δ. Combining the inequalities presented in line 13, the interval [(1+)−1 M, (1+)M ] is the (, δ)-bound. The algorithm
terminates when the condition in line 13 comes true, and its correctness is obvious. The
time complexity of Algorithm 3 is still the same as the original algorithm, though it
usually terminates earlier.
Satisfiability And Enumeration Query For a propositional logic formula or an SMT
formula, there is a direct way to enumerate solutions with satisfiability queries. For
example, we assert the negation of a solution which is found by satisfiability query, so
that the constraint solver will provide other models. So Counting(F, p) invokes up
to p times Solving(F) by this way. This method is adopted by all previous hashingbased (, δ)-counters [8,11,6].
Leap-frogging Strategy Recall that GetDepth is invoked T times with the same arguments, and the loop of line 15 to 20 in the pseudo-code of GetDepth in Algorithm 2

Algorithm 3 STAC with Dynamic Stopping Criterion
1: function STAC DSC(F , T , , δ)
2:
initialize C[i]s with zeros
3:
for t ← 1 to T do
4:
depth ← GetDepth(F )
5:
for i ← 0 to depth − 1 do
6:
C[i] ← C[i] + 1
7:
end for
8:
for each d that C[d] > 0 do
9:
q ← t−C[d]
t
10:
M ← log1−2−d q
11:
12:
13:
14:
15:
16:
17:
18:

q
)
U ← log1−2−d (q − z1−δ q(1−q)
q t
q(1−q)
L ← log1−2−d (q + z1−δ
)
t
−1
if U < (1 + )M and L > (1 + ) M then
return M
end if
end for
end for
end function

is time consuming for large i. A heuristic called leap-frogging to overcome this bottleneck was proposed in [7,8]. Their experiments indicate that this strategy is extremely
efficient in practice. The average depth d¯ of each invocation of GetDepth is recorded.
In all subsequent invocations, the loop starts by initializing i to d¯ − offset, and sets i to
d¯ − 2 ∗ offset for unsatisfiable Fi repeatedly until a proper i is found for a satisfiable
Fi . In practice, the constant offset is usually set to 5. Theorem 4 in Section 5 shows that
the depth computed by GetDepth lies in an interval [d, d + 7] with probability over
90%. So it suffices to invoke Solving in constant time since the second iteration.
Wilson Score Interval The central limit theorem applies poorly to binomial distributions
for small sample size or proportion close to 0 or 1. The following interval [34]
r
1
z2
z2
q(1 − q)
±z
+ 2]
[q +
z2
2t
t
4t
1+ t
has good properties to achieve better approximations. Note that the overhead of computing intervals is negligible.

5

Analysis

In this section, we assume Equation (1) holds. Based on this assumption, theoretical
results on the error estimation of our approach are presented. Recall that in Algorithm 2,
#F is approximated by a value log1−2−d counter
, based on Equation (1). Let qd denote
T
the value of (1 − 2−d )#F . We will assume that Pr(Fd is unsat) = qd for a randomly

generated formula Fd . This assumption is justified by Equations (1) and (2). Then the
counter in Algorithm 2 is a random variable following a binomial distribution B(T, qd ).
Since the ratio counter
is the proportion of successes in a Bernoulli trial process, it is
T
used to estimate the value of qd .
Theorem 2. Let z1−δ be the 1 − δ quantile of N(0, 1) and
!
z1−δ
z1−δ
2
2
) )e .
) e, d( (1+)−1
T = max d(
2qd (1 − qd )
2(q
− qd )

(4)

d

#F
Then Pr[ 1+
≤ log1−2−d

counter
T

≤ (1 + )#F ] ≥ 1 − δ.

Proof. By above discussions, the ratio counter
is the proportion of successes in a Bernoulli
T
trial process which follows the distribution B(T, qd ). Then weq
use the approximate for-

d)
, i.e., Pr[qd −
mula of a binomial proportion confidence interval qd ± z1−δ qd (1−q
T
q
q
qd (1−qd )
q
(1−q
)
d
d
z1−δ
≤ counter
≤ qd + z1−δ
] ≥ 1 − δ. The log function is
T
T
T
monotone, so we only have to consider the following two inequalities:
r
qd (1 − qd )
log1−2−d (qd − z1−δ
) ≤ (1 + )#F,
(5)
T
r
qd (1 − qd )
(1 + )−1 #F ≤ log1−2−d (qd + z1−δ
).
(6)
T

We first consider Equation (5). By substituting log1−2−d qd for #F , we have
r
qd (1 − qd )
log1−2−d (qd − z1−δ
) ≤ (1 + ) log1−2−d qd
T
r
qd (1 − qd )
(1+)
⇔ qd − z1−δ
≥ qd
T
r
qd (1 − qd )

⇔ qd (1 − qd ) ≥ z1−δ
T
z1−δ
2
⇔T ≥(
) qd (1 − qd ).
qd (1 − qd )
p
1−δ
2
Since 0 ≤ qd ≤ 1, we have qd (1 − qd ) ≤ 21 . Therefore, T = d( 2qdz(1−q
) ) e ≥

1−δ
2
( qd z(1−q
 ) qd (1 − qd ).
d)
We next consider Equation (6). Similarly, we have
r
qd (1 − qd )
log1−2−d (qd + z1−δ
) ≥ (1 + )−1 log1−2−d qd
T
r
qd (1 − qd )
1/(1+)
⇔ qd + z1−δ
≤ qd
T
z1−δ
⇔ T ≥ ( 1/(1+)
)2 qd (1 − qd ).
qd
− qd

So Equation (4) implies Equations (5) and (6).

d

Theorem 2 shows that the result of Algorithm 2 lies in the interval [(1+)−1 #F, (1+
)#F ] with probability at least 1 − δ when T is set to a proper value. So we focus on
the possible smallest value of T in subsequent analysis.
The next two lemmas are easy to show by derivations.
z1−δ
2x(1−x )
− 1

Lemma 1.

and [0, (1 + )

− 1+


)

] respectively.

z1−δ
2(x1/(1+) −x)

Lemma 2.

1

is monotone increasing and monotone decreasing in [(1+)−  , 1]

, 1] and [0, (1 + )

is monotone increasing and monotone decreasing in [(1 +
− 1+


] respectively.

Theorem 3. If #F > 5, then there exists a proper integer value of d such that qd ∈
[0.4, 0.65].
Proof. Let x denote the value of qd = (1 −
( 21

+

1
x #F

2

#F

)

( 12 +

then we have (1 −

1
)#F
2d+1

=

. Consider the derivation
1

d
d#F

1 #F
) ,
2d

x #F
2

1

1

1

1 x #F #F
1 x #F x #F
d
)#F = ( +
) ln ( +
)
ln x
(#F −1 ).
2
2
2
2
2
d#F

1
#F

1
#F

1
#F

Note that ( 21 + x 2 )#F and x 2 are the positive terms and ln ( 12 + x 2 ), ln x and
d
−1
) are the negative terms. Therefore, the derivation is negative, i.e., ( 21 +
d#F (#F
1

x #F
2

)#F is monotone decreasing with respect to #F . In addition, ( 12 +
upper bound when #F ≥ 5.

1

x5 5
2 )

is the

1

1
Let x = 0.4, then (1 − 2d+1
)#F ≤ ( 21 + 0.42 5 )5 ≈ 0.65. Since (1 − 210 )#F = 0 and
1 #F
limd→+∞ (1 − 2d )
= 1 and (1 − 21d )#F is continuous with respect to d, we consider
the circumstances close to the interval [0.4, 0.65]. Assume there exists an integer σ such
1
that (1 − 21σ )#F < 0.4 and (1 − 2σ+1
)#F > 0.65. According to the intermediate value
1
)#F = 0.4. Obviously, we have
theorem, we can find a value e > 0 such that (1 − 2σ+e
1
#F
(1 − 2σ+e+1 )
≤ 0.65 which is contrary with the monotone decreasing property.

From Theorem 3 and Lemma 1 and 2, it suffices to consider the results of Equation (4) when qd = 0.4 and qd = 0.65. For example, T = 22 for  = 0.8 and δ = 0.2,
T = 998 for  = 0.1 and δ = 0.1, etc. We therefore pre-computed a table of the value
of T . The proof of next theorem is omitted.
Theorem 4. There exists an integer d such that qd < 0.05 and qd+7 > 0.95.
Let depth denote the result of GetDepth in Algorithm 2. Then Fd is unsatisfiable
only if d ≥ depth. Theorem 4 shows that there exists an integer d such that Pr(depth <
d) < 0.05 and Pr(depth < d + 7) > 0.95, i.e., Pr(d ≤ depth ≤ d + 7) > 0.9. So in
most cases, the value of depth lies in an interval [d, d + 7]. Also, it is easy to see that
log2 #F lies in this interval as well. The following theorem is obvious now.
Theorem 5. Algorithm 2 runs in time linear in log2 #F relative to an NP-oracle.

6

Evaluation

To evaluate the performance and effectiveness of our approach, two prototype implementations STAC CNF and STAC BV with dynamic stopping criterion for propositional
logic formulas and SMT(BV) formulas are built respectively. We considered a wide
range of benchmarks from different domains: grid networks, plan recognition, DQMR
networks, Langford sequences, circuit synthesis, random 3-CNF, logistics problems and
program synthesis [26,22,8,6]. For lack of space, we present results for only for a subset of the benchmarks. All our experiments were conducted on a single core of an Intel
Xeon 2.40GHz (16 cores) machine with 32GB memory and CentOS6.5 operating system.
6.1

Quality of Approximation

Recall that our approach is based on Equation (1) which has not been proved. So we
would like to see whether the approximation fits the bound. We experimented 100 times
on each instance.
Table 1. Statistical results of 100-times experiments on STAC CNF ( = 0.8, δ = 0.2)
Instance
special-1
special-2
special-3
5step
blockmap 05 01
blockmap 05 02
blockmap 10 01
fs-01
or-50-10-10-UC-20
or-60-10-10-UC-40

n
20
20
25
177
1411
1738
11328
32
100
120

[1.8−1 #F, 1.8#F ]

#F
6

1.0 × 10
1
3.4 × 107
8.1 × 104
6.4 × 102
9.4 × 106
2.9 × 106
7.7 × 102
3.7 × 106
3.4 × 106

5

6

[5.8 × 10 , 1.9 × 10 ]
[0.6, 1.8]
[1.9 × 107 , 6.0 × 107 ]
[4.5 × 104 , 1.5 × 105 ]
[3.6 × 102 , 1.2 × 103 ]
[5.2 × 106 , 1.7 × 107 ]
[1.6 × 106 , 5.2 × 106 ]
[4.3 × 102 , 1.4 × 103 ]
[2.0 × 106 , 6.6 × 106 ]
[1.9 × 106 , 6.1 × 106 ]

Freq. t̄ (s) T̄

Q̄

82
86
82
90
84
89
83
80
77
91

86.7
37.6
90.1
80.5
73.8
87.7
85.0
76.2
86.1
86.0

0.3
0.6
11.2
0.1
1.1
12.7
80.3
0.02
7.7
3.5

12.2
12.6
11.8
11.9
12.0
11.8
12.0
12.6
12.0
12.1

In Table 1, column 1 gives the instance name, column 2 the number of Boolean variables n, column 3 the exact counts #F , and column 4 the interval [1.8−1 #F, 1.8#F ].
The frequencies of approximations that lie in the interval [1.8−1 #F, 1.8#F ] in 100
times of experiments are presented in column 5. The average time consumptions, average number of iterations, and average number of SAT query invocations are presented
in column 6, 7 and 8 respectively, which also indicate the advantages of our approach.
Under the dynamic stopping criterion, the counts returned by our approach should
lie in an interval [1.8−1 #F, 1.8#F ] with probability 80% for  = 0.8 and δ = 0.2.
The statistical results in Table 1 show that the frequencies are around 80 for 100-times
experiments which fit the 80% probability. The average number of iterations T̄ listed
in Table 1 is smaller than the theoretical termination bound T which is 22, indicating
that the dynamic stopping technique significantly improves the efficiency. In addition,

the values of T̄ appear to be stable for different instances, hinting that there exists a
constant upper bound on T which is irrelevant to instances.
In Section 4, we considered a similar but different function family G and proved
Equation (2). It suggests that Equation (1) may hold on H for infinite n. However,
our approach does not insert any dummy variables to increase n. Intuitively, our approach may start to fail on “loose” formulas, i.e., with an “infinitesimal” fraction of
non-models. Instance special-1 and special-3 are such “loose” formulas where
special-1 has 220 models with only 20 variables and special-3 has 225 − 1
models with 25 variables. Instance special-2 is another extreme case which only
has one model. The results in Table 1 demonstrate that STAC CNF works fine even on
these extreme cases.
Table 2. Statistical results of 100-times experiments on STAC CNF ( = 0.2, δ = 0.1)
Instance
special-1
special-2
special-3
5step
blockmap 05 01
blockmap 05 02
blockmap 10 01
fs-01
or-50-10-10-UC-20
or-60-10-10-UC-40

n

[1.2−1 #F, 1.2#F ]

#F

20
20
25
177
1411
1738
11328
32
100
120

6

1.0 × 10
1
3.4 × 107
8.1 × 104
6.4 × 102
9.4 × 106
2.9 × 106
7.7 × 102
3.7 × 106
3.4 × 106

5

6

[8.7 × 10 , 1.3 × 10 ]
[0.8, 1.2]
[2.8 × 107 , 4.0 × 107 ]
[6.8 × 104 , 9.8 × 105 ]
[5.3 × 102 , 7.7 × 102 ]
[7.9 × 106 , 1.1 × 107 ]
[2.4 × 106 , 3.5 × 106 ]
[6.4 × 102 , 9.2 × 102 ]
[3.1 × 106 , 4.4 × 106 ]
[2.8 × 106 , 4.1 × 106 ]

Freq. t̄ (s) T̄

Q̄

86
91
91
96
94
87
93
91
90
92

1023
540
1029
1078
1069
1088
1034
975
925
949

4.0
0.1
138
1.9
17.1
281
1371
0.1
140
66

179
179
178
190
190
193
180
172
166
167

We also considered another pair of parameters  = 0.2, δ = 0.1. Then the interval
should be [1.2−1 #F, 1.2#F ] and the probability should be 90%. Table 2 shows the
results on such parameter setting. The frequencies that the approximation lies in interval
[1.2−1 #F, 1.2#F ] are all around or over 90 which fits the 90% probability.
Table 3. Statistical results of 100-times experiments on STAC BV ( = 0.8, δ = 0.2)
Instance
FINDpath1
queue
getopPath2
coloring 4
FISCHER2-7-fair
case2
case4
case7
case8
case11

TB.
32
16
24
32
240
24
16
18
24
15

[1.8−1 #F, 1.8#F ]

#F
6

4.1 × 10
8.4 × 10
8.1 × 103
1.8 × 109
3.0 × 104
4.2 × 106
3.3 × 104
1.3 × 105
8.4 × 106
1.6 × 104

6

6

[2.3 × 10 , 7.3 × 10 ]
[4.7 × 10, 1.5 × 102 ]
[4.5 × 103 , 1.5 × 104 ]
[1.0 × 109 , 3.3 × 109 ]
[1.7 × 104 , 5.4 × 104 ]
[2.3 × 106 , 7.6 × 106 ]
[1.8 × 104 , 5.9 × 104 ]
[7.3 × 104 , 2.4 × 105 ]
[4.7 × 106 , 1.5 × 107 ]
[9.1 × 103 , 2.9 × 104 ]

Freq.

t̄ (s)

T̄

Q̄

83
75
88
76
79
79
87
83
82
76

27.5
1.7
2.7
51.9
149
16.5
2.2
2.9
14.4
2.1

12.4
12.0
12.2
12.0
11.8
12.4
12.5
12.4
12.1
12.0

88.0
70.6
79.5
96.1
79.8
89.3
85.2
84.1
91.1
81.2

Table 3 similarly shows the results of 100-times experiments on STAC BV. Its column 2 gives the sum of widths of all bit-vector variables (Boolean variable is counted
as a bit-vector of width 1) instead. The statistical results demonstrate that the dynamic
stopping criterion is also promising on SMT(BV) problems.
6.2

Performance Comparison with (, δ)-counters

30000

30000

3000

3000

300

300

SMTApproxMC

ApproxMC2

We compared our tools with ApproxMC2 [9] and SMTApproxMC [6] which are hashingbased (, δ)-counters. Both STAC CNF and ApproxMC2 use CryptoMiniSAT [29],
an efficient SAT solver designed for XOR clauses. STAC BV and SMTApproxMC use
the state-of-the-art SMT(BV) solver Boolector [4].

30

30

3

3

0.3

0.3

0.03

0.03
0.03

0.3

3

30

300

3000

30000

STAC_CNF

Fig. 1. Performance comparison between
STAC CNF and ApproxMC2 with  =
0.8, δ = 0.2 and 8 hours timeout

0.03

0.3

3

30

300

3000

30000

STAC_BV

Fig. 2. Performance comparison between
STAC BV and SMTApproxMC with  =
0.8, δ = 0.2 and 8 hours timeout

We first conducted experiments with  = 0.8, δ = 0.2 which are also used in
evaluation in previous works [9,6]. Figure 1 presents a comparison on performance
between STAC CNF and ApproxMC2. Each point represents an instance, whose xcoordinate and y-coordinate are the running times of STAC CNF and ApproxMC2 on
this instance, respectively. The figure is in logarithmic coordinates and demonstrates
that STAC CNF outperforms ApprxMC2 by about one order of magnitude. Figure 2
presents a similar comparison on performance between STAC BV and SMTApproxMC,
showing that STAC BV outperforms SMTApproxMC by one or two order of magnitude.
Furthermore, the advantage enlarges as the scale grows.
Table 4 presents more experimental results with (, δ) parameters other than (0.8, 0.2).
Nine pairs of parameters were experimented. “Time Ratio” represents the ratio of the
running times of ApproxMC2 to STAC CNF. “#Calls Ratio” represents the ratio of the
number of SAT calls of ApproxMC2 to STAC CNF. The results show that ApproxMC2
gains advantage as  decreases and STAC CNF gains advantage as δ decreases. On the
whole, ApproxMC2 gains advantage when  and δ both decrease. Note that the numbers of SAT calls represent the complexity of both algorithms. In Table 4, #Calls Ratio

Table 4. Performance comparison between STAC CNF and ApproxMC2 with different pairs of
(, δ) parameters

XXX
(, δ)
(0.8, 0.3)
(0.8, 0.2)
(0.8, 0.1)
(0.4, 0.3)
(0.4, 0.2)
(0.4, 0.1)
(0.2, 0.3)
(0.2, 0.2)
(0.2, 0.1)

XXXInstance
XXX
Time Ratio
#Calls Ratio
Time Ratio
#Calls Ratio
Time Ratio
#Calls Ratio
Time Ratio
#Calls Ratio
Time Ratio
#Calls Ratio
Time Ratio
#Calls Ratio
Time Ratio
#Calls Ratio
Time Ratio
#Calls Ratio
Time Ratio
#Calls Ratio

blockmap
05 01 05 02 10 01

fs-01

5step

ran5

ran6

ran7

1.11
22.60
1.84
26.70
2.27
44.88
0.75
17.75
0.77
20.91
1.08
37.16
0.42
13.75
0.57
21.80
0.87
27.86

3.00
19.12
2.80
33.46
5.25
49.40
3.00
16.40
4.50
26.72
4.90
31.99
5.08
13.37
8.42
21.83
16.69
34.17

3.83
23.11
6.05
27.24
12.62
43.03
5.04
27.63
7.70
40.66
7.09
39.36
3.79
19.74
3.37
21.59
3.17
31.58

6.53
22.53
9.61
33.35
9.60
46.12
1.97
21.07
2.82
26.49
3.84
41.02
1.26
25.20
2.07
25.88
3.61
40.81

8.24
21.28
15.41
38.22
9.54
44.84
2.31
27.34
1.77
27.82
3.43
35.88
1.14
19.19
1.50
22.72
2.27
29.01

5.57
23.68
7.37
30.94
8.19
52.63
2.74
21.63
3.02
28.94
3.11
34.11
1.81
20.06
2.45
22.98
2.60
29.90

3.99
39.02
6.16
34.68
7.36
48.26
1.37
36.20
1.44
26.35
2.57
46.28
0.47
20.82
0.92
29.62
0.92
29.91

1.22
17.91
2.44
25.16
3.72
40.01
0.42
14.69
0.86
29.16
1.29
39.40
0.23
24.35
0.26
25.60
0.44
33.36

is more stable than Time Ratio among different pairs of parameters and also different instances. It indicates that the difficulty of NP-oracle is also an important factor of
running time performance.
6.3

Performance Comparison with Bounding and Guarantee-less Counters

Since our approach is not a (, δ)-counter in theory, we also compared STAC CNF with
bounding counters (SampleCount [16], MBound [17]) and guarantee-less counters
(ApproxCount [33], SampleTreeSearch [14]). Table 5 shows the experimental
results.
For SampleCount, we used α = 2 and t = 3.5 so that αt = 7, giving a correctness confidence of 1 − 2−7 = 99%. The number of samples per variable setting, z, was chosen to be 20. Our results show that the lower-bound approximated
by SampleCount is smaller than exact count #F by one or more orders of magnitude. We tried larger z, such as z = 100 and z = 1000, but still failed to obtain a
lower-bound larger than #F/10. Moreover, there are some wrong approximations on
DQMR networks problems, e.g., or-100-20-6-UC-60 only has 2.8 × 107 models
but SampleCount returns a lower-bound ≥ 1.1 × 1029 . SampleCount is more efficient on Langford problems and random 3-CNF problems, but weak on problems with
a large number of variables, such as blockmap problems.
For MBound, we used α = 1 and t = 7 so that αt = 7, also giving a correctness
confidence of 1−2−7 = 99%. MBound also employs a family of XOR hashing function

1411
1738
11328
33035
32

30
40
50
60

RANDOM 3-CNF
ran6
ran12
ran27
ran44
1.2 × 106
3.5 × 108
1.5 × 108
1.1 × 106

2.8 × 107
3.1 × 103
6.8 × 108
6.8 × 107
2.1 × 106
1.2 × 104
1.7 × 107

200
100
100
120
120
140
140

DQMR NETWORKS
or-100-20-6-UC-60
or-50-10-10-UC-40
or-50-20-10-UC-30
or-60-10-10-UC-30
or-60-5-2-UC-40
or-70-10-6-UC-40
or-70-5-2-UC-30

≈ 1.9 × 106
≈ 4.2 × 108
≈ 1.2 × 108
≈ 1.9 × 106

≈ 3.4 × 107
≈ 3.2 × 103
≈ 7.4 × 108
≈ 6.2 × 107
≈ 1.9 × 106
≈ 7.2 × 103
≈ 4.7 × 107

0.6 s
10 m
8m
6s

14 m
0.1 s
35 m
4m
6s
0.1 s
51 s

≈ 3.2 × 105 80 m
—
≥8 h

2.2 × 105
—

LANGFORD PROBS.
lang12
576
lang15
1024

≥ 1.1 × 105
≥ 3.1 × 107
≥ 1.3 × 107
≥ 9.5 × 104

≥ 1.1 × 1029
≥ 2.7 × 102
≥ 6.0 × 107
≥ 1.0 × 1017
≥ 1.0 × 1017
≥ 1.0 × 1020
≥ 1.0 × 1020

0.2 s
0.5 s
18 s
8s

15 s
0.1 s
0.2 s
9s
16 s
7s
10 s

≥ 3.6 × 103 3 m
≥ 4.7 × 105 4 m

≥ 2.8 × 103 4 s
≥ 7.0 × 105 14 s
≥ 1.3 × 106 49 s

116 s
5m
≥8 h
≥8 h
0.2 s

≥ 22
3.6 × 104
—
—
≥ 68

≈ 807
≈ 7.1 × 106
≈ 2.6 × 106
≈ 2.0 × 109
≈ 709
1s
16 s
96 s
41 m
0.1 s

SampleCount
(99% confidence)
L-bound
Time

STAC CNF
( = 0.8, δ = 0.2)
Models
Time

8.1 × 104 ≈ 8.1 × 104 0.2 s
7.3 × 108 ≈ 9.8 × 108 64 m
2.2 × 1011 —
≥8 h

640
9.4 × 106
2.9 × 106
—
768

#F
(if known)

PLAN RECOGNITION
5step
177
tire-1
352
tire-3
577

01
02
01
01

blockmap
blockmap
blockmap
blockmap
fs-01

05
05
10
15

n

9s
5m
9m
≥8 h
2s

> 1.3 × 105
> 6.7 × 107
> 1.7 × 107
> 1.3 × 105

> 4.2 × 106
> 5.1 × 102
> 1.3 × 108
> 1.7 × 107
> 5.2 × 105
> 2.0 × 103
> 2.1 × 106

11 s
15 m
28 m
52 s

6m
4s
3h
38 m
199 s
4s
11 m

> 1.6 × 104 4 h
—
≥8 h

> 8.2 × 103 6 s
> 6.7 × 107 8 h
—
≥8 h

> 64
> 2.1 × 106
> 5.2 × 105
—
> 64

MBound
(99% confidence)
L-bound
Time
7s
13 s
≥8 h
≥8 h
17 s

≈ 8.3 × 105
≈ 2.6 × 108
≈ 5.5 × 107
≈ 3.3 × 105

≈0
≈ 2.1 × 1016
≈ 2.7 × 1016
≈ 2.4 × 1019
≈ 2.3 × 1019
≈0
≈0

≈0
≈0

23 s
23 s
59 s
139 s

17 s
68 s
62 s
83 s
89 s
165 s
165 s

111 s
122 s

= 8.1 × 104 18 s
= 7.3 × 108 48 s
≈ 2.1 × 1011 63 s

= 640
= 9.4 × 106
—
—
≈ 925

71 s
114 s
62 m
≥8 h
0.1 s

≈ 1.3 × 106
≈ 3.9 × 108
≈ 1.1 × 108
≈ 9.1 × 105

≈ 2.8 × 107
≈ 3.1 × 103
≈ 7.9 × 108
≈ 6.5 × 107
≈ 2.1 × 106
≈ 1.2 × 104
≈ 1.7 × 107

0.2 s
0.3 s
0.3 s
0.5 s

0.8 s
0.5 s
0.7 s
1s
0.9 s
0.5 s
0.8 s

≈ 1.9 × 105 101 m
—
≥8 h

≈ 7.5 × 104 1 s
≈ 7.6 × 108 5 s
≈ 1.2 × 1011 5 s

≈ 646
≈ 9.4 × 106
≈ 3.0 × 106
—
≈ 769

Time

Models

Models

Time

SampleTreeSearch

ApproxCount

Table 5. Performance comparison of STAC CNF with existing bounding counters and guarantee-less counters

Instance

which is similar to the function used by our approach. The size of XOR constraints k
should be no more than half of the number of variables n, i.e., k ≤ n/2. We found
that XOR constraints start to fail as k << n/2. So in our experiments, k was chosen
to be close to n/2. Since MBound can only check the bound and may return failure as
the bound too close to the exact count, we implemented a binary search to find the best
lower-bound verified by MBound. The results in Table 5 are the best lower-bounds and
the running times of the whole binary search procedure. Though the lower-bounds are
better than SampleCount, they are still around #F/10. Similar to our approach, the
running times of MBound are also quite relevant to the size of #F .
For ApproxCount, we manually increased the value of “cutoff” as ApproxCount
required. Note that ApproxCount calls exact model counter Cachet [27] and Relsat
[20] after formula simplifications, so it sometimes returns the exact counts, such as
blockmap 05 01, blockmap 05 02, 5step and tire-1. On Langford problems
and DQMR networks problems, wrong approximations were provided. On other instances, the results show that STAC CNF usually outperforms ApproxCount.
For SampleTreeSearch, we used its default setting about the number of samples, which is a constant. The results show that it is very efficient and provides good approximations. Our approach only outperforms SampleTreeSearch on blockmap
problems which consist of a large number of variables. However, there is a lack of analysis on the accuracy of the approximation of SampleTreeSearch, i.e., no explicit
relation between the number of samples and the accuracy.

7

Conclusion

In this paper, we propose a new hashing-based approximate algorithm with dynamic
stopping criterion. Our approach has two key strengths: it requires only one satisfiability
query for each cut, and it terminates once meeting the theoretical guarantee of accuracy.
We implemented prototype tools for propositional logic formulas and SMT(BV) formulas. Extensive experiments demonstrate that our approach is efficient and promising.
Despite that we are unable to prove the correctness of Equation (1), the experimental
results fit it quite well. This phenomenon might be caused by some hidden properties
of the hash functions. To fully understand these functions and their correlation with the
model count of the hashed formula might be an interesting problem to the community.
In addition, extending the idea in this paper to count solutions of other formulas is also
a direction of future research.

References
1. M. Bellare, O. Goldreich, and E. Petrank. Uniform generation of NP-witnesses using an
NP-oracle. Inf. Comput., 163(2):510–526, 2000.
2. V. Belle, G. V. Broeck, and A. Passerini. Hashing-based approximate probabilistic inference
in hybrid domains. In Proc. of UAI, pages 141–150, 2015.
3. L. D. Brown, T. T. Cai, and A. Dasgupta. Interval estimation for a binomial proportion.
Statistical Science, 16(2):101–133, 2001.
4. R. Brummayer and A. Biere. Boolector: An efficient SMT solver for bit-vectors and arrays.
In Proc. of TACAS, pages 174–177, 2009.

5. S. Chakraborty, D. J. Fremont, K. S. Meel, S. A. Seshia, and M. Y. Vardi. Distribution-aware
sampling and weighted model counting for SAT. In Proc of AAAI, pages 1722–1730, 2014.
6. S. Chakraborty, K. S. Meel, R. Mistry, and M. Y. Vardi. Approximate probabilistic inference
via word-level counting. In Proc. of AAAI, pages 3218–3224, 2016.
7. S. Chakraborty, K. S. Meel, and M. Y. Vardi. A scalable and nearly uniform generator of
SAT witnesses. In Proc. of CAV, pages 608–623, 2013.
8. S. Chakraborty, K. S. Meel, and M. Y. Vardi. A scalable approximate model counter. In
Proc. of CP, pages 200–216, 2013.
9. S. Chakraborty, K. S. Meel, and M. Y. Vardi. Algorithmic improvements in approximate
counting for probabilistic inference: From linear to logarithmic SAT calls. In Proc. of IJCAI,
pages 3569–3576, 2016.
10. M. Chavira and A. Darwiche. On probabilistic inference by weighted model counting. Artif.
Intell., 172(6-7):772–799, 2008.
11. D. Chistikov, R. Dimitrova, and R. Majumdar. Approximate counting in SMT and value
estimation for probabilistic programs. In Proc. of TACAS, pages 320–334, 2015.
12. C. Domshlak and J. Hoffmann. Probabilistic planning via heuristic forward search and
weighted model counting. J. Artif. Intell. Res. (JAIR), 30:565–620, 2007.
13. S. Ermon, C. P. Gomes, A. Sabharwal, and B. Selman. Embed and project: Discrete sampling
with universal hashing. In Advances in Neural Information Processing Systems 26, pages
2085–2093, 2013.
14. S. Ermon, C. P. Gomes, and B. Selman. Uniform solution sampling using a constraint solver
as an oracle. In Proc. UAI, pages 255–264, 2012.
15. J. Geldenhuys, M. B. Dwyer, and W. Visser. Probabilistic symbolic execution. In Proc. of
ISSTA, pages 166–176, 2012.
16. C. P. Gomes, J. Hoffmann, A. Sabharwal, and B. Selman. From sampling to model counting.
In Proc. of IJCAI, pages 2293–2299, 2007.
17. C. P. Gomes, A. Sabharwal, and B. Selman. Model counting: A new strategy for obtaining
good bounds. In Proc. of AAAI, pages 54–61, 2006.
18. C. P. Gomes, A. Sabharwal, and B. Selman. Near-uniform sampling of combinatorial spaces
using XOR constraints. In Advances in Neural Information Processing Systems 19, pages
481–488, 2006.
19. A. Ivrii, S. Malik, K. S. Meel, and M. Y. Vardi. On computing minimal independent support
and its applications to sampling and counting. Constraints, 21(1):41–58, 2016.
20. R. J. Bayardo Jr. and R. Schrag. Using CSP look-back techniques to solve real-world SAT
instances. In Proc. of AAAI, pages 203–208, 1997.
21. R. M. Karp, M. Luby, and N. Madras. Monte-carlo approximation algorithms for enumeration problems. J. Algorithms, 10(3):429–448, 1989.
22. L. Kroc, A. Sabharwal, and B. Selman. Leveraging belief propagation, backtrack search, and
statistics for model counting. Annals of OR, 184(1):209–231, 2011.
23. S. Liu and J. Zhang. Program analysis: from qualitative analysis to quantitative analysis. In
Proc. of ICSE, pages 956–959, 2011.
24. K. S. Meel, M. Y. Vardi, S. Chakraborty, D. J. Fremont, S. A. Seshia, D. Fried, A. Ivrii, and
S. Malik. Constrained sampling and counting: Universal hashing meets SAT solving. In
Proceedings of Workshop on Beyond NP(BNP), 2016.
25. D. Roth. On the hardness of approximate reasoning. Artif. Intell., 82(1-2):273–302, 1996.
26. T. Sang, P. Beame, and H. A. Kautz. Performing bayesian inference by weighted model
counting. In Proc. of AAAI, pages 475–482, 2005.
27. Tian Sang, Fahiem Bacchus, Paul Beame, Henry A. Kautz, and Toniann Pitassi. Combining
component caching and clause learning for effective model counting. In Proc. of SAT, 2004.
28. M. Sipser. A complexity theoretic approach to randomness. In Proc. of the 15th Annual
ACM Symposium on Theory of Computing, pages 330–335, 1983.

29. M. Soos, K. Nohl, and C. Castelluccia. Extending SAT solvers to cryptographic problems.
In Proc. of SAT, pages 244–257, 2009.
30. L. J. Stockmeyer. The complexity of approximate counting (preliminary version). In Proc.
of the 15th Annual ACM Symposium on Theory of Computing, pages 118–126, 1983.
31. L. G. Valiant. The complexity of enumeration and reliability problems. SIAM J. Comput.,
8(3):410–421, 1979.
32. S. Wallis. Binomial confidence intervals and contingency tests: Mathematical fundamentals
and the evaluation of alternative methods. Journal of Quantitative Linguistics, 20(3):178–
208, 2013.
33. W. Wei and B. Selman. A new approach to model counting. In Proc. of SAT, pages 324–339,
2005.
34. E. B. Wilson. Probable inference, the law of succession and statistical inference. Journal of
the American Statistical Association, 22(158):209–212, 1927.

