Discrete integration is a fundamental problem in computer science that involves computing discrete sums over exponentially large sets. It is a cornerstone of modern AI, essential for tasks like probabilistic inference, network reliability, and verifying the safety of neural networks. Despite intense interest for over three decades, designing scalable techniques with rigorous theoretical guarantees has remained a holy grail for researchers.
In this paper, researchers introduce DeWeight, a novel method that scales discrete integration (weighted counting) by reducing it to unweighted model counting. By cleverly adding auxiliary variables—a counter-intuitive "boon of dimensionality"—DeWeight eliminates the need for crude weight approximations, providing the first scalable technique with rigorous guarantees for complex tasks like neural network verification.
The Bottleneck of Weighted Counting
Discrete integration is #P-complete, making it computationally harder than standard NP-complete problems. While researchers have successfully developed ways to approximate "unweighted" counting (simply counting the number of valid solutions), "weighted" counting has remained a stubborn bottleneck.
Previous state-of-the-art approaches attempted to bridge this gap by reducing weighted problems to unweighted ones. However, they suffered from a fatal flaw: they only worked for dyadic weights (fractions where the denominator is a power of two, such as $1/4$ or $3/8$). If a real-world weight was $1/3$ or $0.1$, it had to be rounded to the nearest dyadic fraction. In large-scale problems, these tiny rounding errors compound into astronomically large inaccuracies, rendering the results useless for sensitive applications like neural network verification.
The DeWeight Solution: Embracing Complexity
The authors introduce DeWeight, a reduction technique that handles any rational weight ($p/q$) without the restrictive dyadic requirement.
- The Exact Reduction: Instead of replacing a variable with a single "chain formula" (the previous standard), DeWeight uses a system of implications and two separate chain formulas to simulate the weights of both the variable and its negation independently.
- The Boon of Dimensionality: Counter-intuitively, DeWeight adds more variables to the problem. While adding dimensions usually makes computational problems harder (the "curse of dimensionality"), here it allows the authors to leverage highly optimized, state-of-the-art unweighted model counters like ApproxMC. The increased dimensionality actually translates the problem into a simpler format for the solver to digest.
- Farey Sequences: For scenarios where memory limits the number of extra variables that can be added, the authors provide an algorithm based on Farey Sequences—an elegant mathematical construct for finding the "best" rational approximations. This allows users to find the most accurate weights possible within a specific "bit budget."
Experimental Setup
The authors evaluated DeWeight on a rigorous suite of 1,056 Boolean formulas derived from the domain of neural network verification. These benchmarks are divided into three categories:
- Robustness: 960 formulas testing if a binarized neural network (trained on MNIST) is susceptible to adversarial perturbations.
- Trojan Attacks: 60 formulas checking if a network has hidden "backdoors" triggered by specific input patterns.
- Fairness: 36 formulas based on the UCI Adult dataset, checking if the network's classification changes based on sensitive features.
These benchmarks are particularly challenging because they involve up to $10^5$ variables, though the "sampling set" (the variables being counted) is limited to around 100.
Key Results
DeWeight demonstrated significant improvements in both coverage and accuracy compared to prior methods.
Better Coverage and Speed
In head-to-head tests, DeWeight solved 622 benchmarks within an 8-hour limit, while the previous "Dyadic" approach only solved 489. The core philosophy of DeWeight—that a slight increase in problem size is a small price to pay for the ability to use much faster, unweighted counting algorithms—proved highly effective in practice.
Superior Accuracy
Precision matters. The paper demonstrates that approximating weights to the nearest dyadic fraction can lead to a multiplicative error of over $10^8$ even in simple settings. DeWeight provides $(\epsilon, \delta)$ guarantees, meaning the answer is mathematically proven to be within a certain error bound with high confidence.
As shown below, the Dyadic approach, due to its compounding rounding errors, often returned estimates that were off by several orders of magnitude compared to DeWeight’s exact reduction.
Ultimately, DeWeight stands as the first tool capable of providing provable guarantees for this specific class of neural network verification benchmarks, which were previously considered beyond the ability of prior work.
Limitations and Future Work
While a significant leap forward, DeWeight has a few limitations that pave the way for future research:
- Bit-Width Sensitivity: The performance of DeWeight depends on the number of bits required to describe the weights. If weights require extremely high precision (many decimal places), the number of auxiliary variables could grow, potentially slowing down the solver.
- Projection Limits: Currently, the method works best when the "sampling set" (the variables of interest) is relatively small (around 100 variables). Scaling to larger sampling sets is a primary goal for future research.
- Broader Domains: While this paper focused on neural networks, the authors suggest that DeWeight could be applied to other log-linear models, such as those found in natural language processing (skip-gram models) and graphical models.
Summary updated