# Scalable Algorithms for Approximate DNF Model Counting

arXiv: https://arxiv.org/abs/2601.10511 · HTML: https://mlsanity.com/paper/2601.10511/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 33 references that are in the map.
- First posted on arXiv 15 Jan 2026.

## Builds on (most cited first, 6 of 6)

- [ADDMC: Weighted Model Counting with Algebraic Decision Diagrams](https://mlsanity.com/paper/1907.05000/) (2019)
- [Learning to Reason: Leveraging Neural Networks for Approximate DNF Counting](https://mlsanity.com/paper/1904.02688/) (2019)
- [On Hashing-Based Approaches to Approximate DNF-Counting](https://mlsanity.com/paper/1710.05247/) (2017)
- [Engineering an Efficient Approximate DNF-Counter](https://mlsanity.com/paper/2407.19946/) (2024)
- [Improved bounds and algorithms for graph cuts and network reliability](https://mlsanity.com/paper/1602.08730/) (2016)
- [Efficient Online Random Sampling via Randomness Recycling](https://mlsanity.com/paper/2505.18879/) (2025)

## Abstract (arXiv)

Model counting of Disjunctive Normal Form (DNF) formulas is a critical problem in applications such as probabilistic inference and network reliability. For example, it is often used for query evaluation in probabilistic databases. Due to the computational intractability of exact DNF counting, there has been a line of research into a variety of approximation algorithms. These include Monte Carlo approaches such as the classical algorithms of Karp, Luby, and Madras (1989), as well as methods based on hashing (Soos et al. 2023), and heuristic approximations based on Neural Nets (Abboud, Ceylan, and Lukasiewicz 2020). We develop a new Monte Carlo approach with an adaptive stopping rule and short-circuit formula evaluation. We prove it achieves Probably Approximately Correct (PAC) learning bounds and is asymptotically more efficient than the previous methods. We also show experimentally that it out-performs prior algorithms by orders of magnitude, and can scale to much larger problems with millions of variables.