Systematic Parameter Decision in Approximate Model Counting

Jinping Lei, Toru Takisaka (🖂), Junqiang Peng, Mingyu Xiao · 2025

Read Systematic Parameter Decision in Approximate Model Counting by Jinping Lei, Toru Takisaka (🖂), Junqiang Peng, Mingyu Xiao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-05874.txt.

Introduction

Jinping Lei and co-authors set parameters systematically for approximate model counting in this 2025 paper. ApproxMC counts solutions of logical formulas with guaranteed accuracy. Its internal parameters must keep those guarantees while running fast. Until now, tuning relied on heuristics and case by case proof work.

The authors generalize the correctness proof to arbitrary parameter values. Soundness then separates cleanly from speed. The tuning task becomes an optimization problem with a very simple final form. A basic search finds good settings from that form. New parameters sped the latest ApproxMC by 1.6 to 2.4 times in tests. Principled tuning replaces folklore for a core counting tool.

Catalog record

CREATORJinping Lei, Toru Takisaka (🖂), Junqiang Peng, Mingyu Xiao
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE92 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-05874

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Systematic Parameter Decision in Approximate Model Counting Jinping Lei, Toru Takisaka (🖂), Junqiang Peng, Mingyu Xiao Abstract This paper proposes a novel approach to determining the internal parameters of the hashing-based approximate model counting algorithm 𝖠𝗉𝗉𝗋𝗈𝗑𝖬𝖢 \mathsf{ApproxMC} . In this problem, the chosen parameter values must ensure that 𝖠𝗉𝗉𝗋𝗈𝗑𝖬𝖢 \mathsf{ApproxMC} is Probably Approximately Correct (PAC), while also making it as efficient as possible. The existing approach to this problem relies on heuristics; in this paper, we solve this problem by formulating it as an optimization problem that arises from generalizing 𝖠𝗉𝗉𝗋𝗈𝗑𝖬𝖢 \mathsf{ApproxMC} ’s correctness proof to arbitrary parameter values. Our approach separates the concerns of algorithm soundness and optimality, allowing us to address the former without the need for repetitive case-by-case argumentation, while establishing a clear framework for the latter. Furthermore, after reduction, the resulting optimization problem takes on an exceptionally simple form, enabling the use of a basic search algorithm and providing insight into how parameter values affect algorithm performance. Experimental results demonstrate that our optimized parameters improve the runtime performance of the latest 𝖠𝗉𝗉𝗋𝗈𝗑𝖬𝖢 \mathsf{ApproxMC} by a factor of 1.6 to 2.4, depending on the error tolerance. 1 Introduction The model counting problem , also called \mathsf{\#SAT} , is the problem of computing the number of models (or solutions , satisfying assignments ) of a given propositional formula. Model counting is one of the most well-known \mathsf{\#P} -complete problems, where \mathsf{\#P} is the class of counting problems whose decision counterparts are in \mathsf{NP} . Despite its computational hardness, the problem naturally arises in various application areas, such as control improvisation [ 11 ] , network reliability [ 23 , 6 ] , neural network verification [ 1 ] , and probabilistic reasoning [ 17 , 18 , 2 , 8 ] . Therefore, developing an efficient approximate algorithm for model counting is of great interest to both theoreticians and practitioners. One of the standard criteria for correctness in approximate algorithms is the Probably Approximately Correct (PAC) criterion, also referred to as the (\varepsilon,\delta) -correct criterion. In our context, a PAC approximate model counter is a randomized algorithm that receives a triple (F,\varepsilon,\delta) , where F is an input formula, \varepsilon>0 is a tolerance parameter , and \delta\in(0,1] is a confidence parameter , and returns a PAC approximation of the model count of F . That is, with the probability at least 1-\delta (probably correct), the output should be within a factor of (1+\varepsilon)^{\pm 1} of the exact model count of F (approximately correct). The current state-of-the-art in approximate model counting is a hashing-based algorithm called \mathsf{ApproxMC} [ 5 ] . Its high-level idea, which is also illustrated in the accompanying figure, is as follows: Given a formula F with a set of variables \mathsf{Vars}(F) , we first randomly partition the model space \{0,1\}^{|\mathsf{Vars}(F)|} into small subspaces (called cells ) using a hash function. We then compute the exact model count of F within a randomly selected cell, and multiply it by the total number of cells to obtain an approximation of the model count of F . To efficiently achieve an (\varepsilon,\delta) -correct approximation for given \varepsilon and \delta , \mathsf{ApproxMC} iteratively runs a core counter that performs the above estimation with low confidence (but shorter runtime) and returns the median of the collected estimates as its final result. Since its initial proposal in 2013 [ 4 ] , researchers have shown sustained interest in improving the performance of hashing-based techniques [ 7 , 8 , 2 , 13 , 15 , 3 , 21 , 14 , 26 , 25 ] . The most recent update 1 1 1 We take \mathsf{ApproxMC6} [ 27 ] as our baseline, as it is the latest version that works for any \varepsilon and \delta . A newer version [ 16 ] exists, but it supports only \varepsilon>1 ; see also § 7 . to \mathsf{ApproxMC} [ 27 ] significantly improved its efficiency with a novel rounding technique, resulting in the sixth version, \mathsf{ApproxMC6} . A problem of concern: the parameter decision problem. To determine the exact design of \mathsf{ApproxMC} , one must decide the values of its internal parameters, which may depend on the input values. For example, given an input (F,\varepsilon,\delta) , how many times should we run the core counter so that \mathsf{ApproxMC} returns an (\varepsilon,\delta) -correct approximation? Also, the precise meaning of cells being “small” must be specified by fixing another internal parameter \mathsf{thresh} . In addition to these, \mathsf{ApproxMC6} requires yet another parameter \mathsf{rnd} , which is used in the rounding operation introduced in the recent update. All these parameters—which interact in a rather delicate way—must be set so that \mathsf{ApproxMC} is PAC; also, under this constraint, we wish \mathsf{ApproxMC} to be as efficient as possible in its runtime. We call such a problem the parameter decision problem in \mathsf{ApproxMC} . Existing works rely on heuristics to solve this problem. For example, it has been standard in \mathsf{ApproxMC} to set \mathsf{thresh}=9.84(1+\frac{\varepsilon}{1+\varepsilon})(1+\frac{1}{\varepsilon})^{2} (plus one in some old versions). According to our analysis, this value was adopted not to optimize the runtime performance of \mathsf{ApproxMC} , but rather to simplify \mathsf{ApproxMC} ’s correctness proof—it ensures that a certain intermediate parameter in the proof remains constant across different choices of \varepsilon . We are motivated to find a systematic approach to this problem for a couple of reasons. First, recent additions of new features to \mathsf{ApproxMC} have significantly increased the effort required to prove its correctness, and this increased effort could pose a potential threat to its long-term development. With rounding added as a new feature, the key lemma for the correctness of \mathsf{ApproxMC6} [ 27 , Lemma 4] now requires five different case analyses for its proof, demanding more than 8 pages to describe in LNCS format. This means that with every new version of \mathsf{ApproxMC} , we may have to revisit all these case analyses to ensure the correctness proof holds; or even worse, new features in the update may make the situation even more complicated. Second, the heuristic nature of the existing approach suggests that there might be a better parameter choice that improves the algorithm’s efficiency. In fact, existing works do not provide a formal argument for the optimality of their chosen parameters; they have often been assumed without explanation as to why this specific value is used. Third, we would like to make the relationship between the parameter choice and the resulting property of \mathsf{ApproxMC} “visible”. Specifically, we want to understand to what extent internal parameters can be modified while still maintaining \mathsf{ApproxMC} to be PAC, and how such modifications affect the performance of the resulting algorithm. Understanding this inherent nature of \mathsf{ApproxMC} will serve as the basis for its development. Unfortunately, existing studies offer quite limited information about this—they primarily focus on proving the correctness of \mathsf{ApproxMC} under a specific parameter chosen in a top-down manner. Contribution. In this paper, we propose a systematic approach to the parameter decision problem in \mathsf{ApproxMC6} . Our core idea is to recast the problem into an optimization problem. Specifically, we consider the following: (a) A soundness condition , which provides a sufficient condition on the internal parameters of \mathsf{ApproxMC6} for the algorithm to be PAC, and

Read the complete text