Introduction
Discrete integration, or weighted model counting, is a fundamental #P-complete problem with critical applications in probabilistic inference and the formal verification of binarized neural networks (BNNs). For instance, verifying that a BNN is robust to adversarial noise or fair across demographic groups requires computing the weighted sum of satisfying assignments under a specific probability distribution. This task is notoriously difficult due to the exponentially large search space.
The Challenge of Dyadic Weights
Existing scalable approaches often reduce weighted model counting to unweighted model counting by introducing auxiliary variables. However, prior state-of-the-art methods were restricted to dyadic weights—fractions with denominators as powers of two (e.g., $3/8$).
Real-world probabilities, such as $1/3$ or $0.1$, had to be rounded to the nearest dyadic fraction. Because the total weight of an assignment is the product of individual literal weights, these small rounding errors compound exponentially. In a sampling set of 100 variables, rounding $1/3$ to a dyadic fraction can result in an error factor exceeding $10^8$, rendering the final estimates practically useless.
Methodology: The DeWeight Framework
This paper introduces DeWeight, a novel reduction framework that enables exact discrete integration for arbitrary rational weights, bypassing the limitations of dyadic rounding.
Exact Rational Reductions
The core innovation lies in moving from logical equivalence to logical implication. While previous methods used a single "chain formula" of auxiliary variables to simulate a dyadic weight, DeWeight utilizes two separate chain formulas linked by implications: $x \rightarrow \text{formula}_1$ and $\neg x \rightarrow \text{formula}_2$. This allows the exact simulation of any rational weight $p/q$ for variable $x$ and $(q-p)/q$ for its negation.
The Boon of Dimensionality
To represent a weight $p/q$, DeWeight adds $\lceil \max(\log_2 p, \log_2(q-p)) \rceil$ fresh variables. Although increasing dimensionality typically complicates SAT problems (the "curse" of dimensionality), mapping the problem into a purely unweighted space allows the authors to leverage highly optimized, state-of-the-art approximate model counters like ApproxMC.
Optimal Approximation via Farey Sequences
When weights require more bits than the available variable budget, DeWeight employs an algorithm based on Farey Sequences. This ensures the selection of the absolute closest $m$-bit rational fraction, providing significantly tighter approximations than standard dyadic rounding.
Experimental Evaluation
The authors evaluated DeWeight on 1056 projected Boolean formulas derived from BNN verification tasks, including robustness (MNIST), Trojan attack effectiveness (MNIST), and fairness (UCI Adult). These formulas typically contain $10^5$ variables with sampling sets of up to 100 variables.
Results
Accuracy and Error Mitigation
DeWeight eliminates the massive approximation errors inherent in dyadic-only reductions. In Experiment 1 (using weights of $1/3$ and $2/3$), DeWeight provided tight theoretical bounds, whereas the dyadic baseline produced bounds inflated by an error factor of at least $1.76 \times 10^8$.
Scalability and Performance
DeWeight significantly outperforms both dyadic baselines and exact solvers. In Experiment 1, DeWeight solved 622 queries within an 8-hour timeout, compared to 489 for the dyadic baseline. In Experiment 2 (random 1-decimal weights), the gap widened: DeWeight solved 394 queries, while the dyadic baseline solved only 108.
Competing exact tools like DSharp and GANAK failed to solve any queries in these weighted settings due to the massive "tilt" (the ratio of largest to smallest weights) present in the benchmarks, which DeWeight handles gracefully.
Conclusion
DeWeight demonstrates that by leveraging the "boon of dimensionality"—mapping weighted problems into higher-dimensional unweighted spaces—one can achieve both exactness for rational weights and superior scalability. While currently limited by the sampling set size of underlying counters (approx. 100 variables), DeWeight is poised to benefit from ongoing advancements in approximate model counting technology.
Summary updated