  Model counting is a fundamental problem which has been influential in many
applications, from artificial intelligence to formal verification. Due to the
intrinsic hardness of model counting, approximate techniques have been
developed to solve real-world instances of model counting. This paper designs a
new anytime approach called PartialKC for approximate model counting. The idea
is a form of partial knowledge compilation to provide an unbiased estimate of
the model count which can converge to the exact count. Our empirical analysis
demonstrates that PartialKC achieves significant scalability and accuracy over
prior state-of-the-art approximate counters, including satss and STS.
Interestingly, the empirical results show that PartialKC reaches convergence
for many instances and therefore provides exact model counting performance
comparable to state-of-the-art exact counters.
