# Distribution-Aware Sampling and Weighted Model Counting for SAT

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Apr 2014.

## Built on by (most cited first, 15 of 15)

- [Taxonomy of Machine Learning Safety: A Survey and Primer](https://mlsanity.com/paper/2106.04823/) (2021)
- [On the Hardness of Probabilistic Neurosymbolic Learning](https://mlsanity.com/paper/2406.04472/) (2024)
- [Learning Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023)
- [Rounding Meets Approximate Model Counting](https://mlsanity.com/paper/2305.09247/) (2023)
- [X-MEN: Guaranteed XOR-Maximum Entropy Constrained Inverse Reinforcement Learning](https://mlsanity.com/paper/2203.11842/) (2022)
- [IASCAR: Incremental Answer Set Counting by Anytime Refinement](https://mlsanity.com/paper/2311.07233/) (2023)
- [Solving Projected Model Counting by Utilizing Treewidth and its Limits](https://mlsanity.com/paper/2305.19212/) (2023)
- [Solving Satisfiability Modulo Counting for Symbolic and Statistical AI Integration With Provable Guarantees](https://mlsanity.com/paper/2309.08883/) (2023)
- [Formally Certified Approximate Model Counting](https://mlsanity.com/paper/2406.11414/) (2024)
- [Quantum Algorithms for Weighted Constrained Sampling and Weighted Model Counting](https://mlsanity.com/paper/2407.12816/) (2024)
- [diff-SAT -- A Software for Sampling and Probabilistic Reasoning for SAT and Answer Set Programming](https://mlsanity.com/paper/2101.00589/) (2021)
- [Exploiting complex pattern features for interactive pattern mining](https://mlsanity.com/paper/2204.04242/) (2022)
- [Learning Markov Random Fields for Combinatorial Structures via Sampling through Lov'asz Local Lemma](https://mlsanity.com/paper/2212.00296/) (2022)
- [You-Only-Randomize-Once: Shaping Statistical Properties in Constraint-based PCG](https://mlsanity.com/paper/2409.00837/) (2024)
- [Systematic Parameter Decision in Approximate Model Counting](https://mlsanity.com/paper/2504.05874/) (2025)

## Abstract (arXiv)

Given a CNF formula and a weight for each assignment of values to variables, two natural problems are weighted model counting and distribution-aware sampling of satisfying assignments. Both problems have a wide variety of important applications. Due to the inherent complexity of the exact versions of the problems, interest has focused on solving them approximately. Prior work in this area scaled only to small problems in practice, or failed to provide strong theoretical guarantees, or employed a computationally-expensive maximum a posteriori probability (MAP) oracle that assumes prior knowledge of a factored representation of the weight distribution. We present a novel approach that works with a black-box oracle for weights of assignments and requires only an NP-oracle (in practice, a SAT-solver) to solve both the counting and sampling problems. Our approach works under mild assumptions on the distribution of weights of satisfying assignments, provides strong theoretical guarantees, and scales to problems involving several thousand variables. We also show that the assumptions can be significantly relaxed while improving computational efficiency if a factored representation of the weights is known.