# Lifted Algorithms for Symmetric Weighted First-Order Model Sampling

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 56 references that are in the map.
- First posted on arXiv 17 Aug 2023.

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

- [Lifted Variable Elimination: Decoupling the Operators from the Constraint Language](https://mlsanity.com/paper/1402.0565/) (2014)
- [Symmetric Weighted First-Order Model Counting](https://mlsanity.com/paper/1412.1505/) (2014)
- [Weighted First-Order Model Counting in the Two-Variable Fragment With Counting Quantifiers](https://mlsanity.com/paper/2007.05619/) (2020)
- [Skolemization for Weighted First-Order Model Counting](https://mlsanity.com/paper/1312.5378/) (2013)
- [New Liftable Classes for First-Order Probabilistic Inference](https://mlsanity.com/paper/1610.08445/) (2016)
- [Weighted model counting beyond two-variable logic](https://mlsanity.com/paper/1804.10185/) (2018)
- [Lifted Inference with Linear Order Axiom](https://mlsanity.com/paper/2211.01164/) (2022)
- [A Scalable and Nearly Uniform Generator of SAT Witnesses](https://mlsanity.com/paper/1304.1584/) (2013)
- [Uniform Sampling through the Lov'asz Local Lemma](https://mlsanity.com/paper/1611.01647/) (2016)
- [Domain Recursion for Lifted Inference with Existential Quantifiers](https://mlsanity.com/paper/1707.07763/) (2017)
- [Sampling Constraint Satisfaction Solutions in the Local Lemma Regime](https://mlsanity.com/paper/2011.03915/) (2020)
- [On the Complexity and Approximation of Binary Evidence in Lifted Inference](https://mlsanity.com/paper/1311.6591/) (2013)
- [Uniform generation of random regular graphs](https://mlsanity.com/paper/1511.01175/) (2015)
- [Perfect Sampling for (Atomic) Lov'asz Local Lemma](https://mlsanity.com/paper/2107.03932/) (2021)
- [On Exact Sampling in the Two-Variable Fragment of First-Order Logic](https://mlsanity.com/paper/2302.02730/) (2023)
- [Approximate Weighted First-Order Model Counting: Exploiting Fast Approximate Model Counters and Symmetry](https://mlsanity.com/paper/2001.05263/) (2020)

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

- [Bridging Weighted First Order Model Counting and Graph Polynomials](https://mlsanity.com/paper/2407.11877/) (2024)
- [Towards Practical First-Order Model Counting](https://mlsanity.com/paper/2502.12278/) (2025)
- [Model Enumeration of Two-Variable Logic with Quadratic Delay Complexity](https://mlsanity.com/paper/2505.19648/) (2025)
- [Tractable Weighted First-Order Model Counting with Bounded Treewidth Binary Evidence](https://mlsanity.com/paper/2511.09174/) (2025)
- [A Fast Model Counting Algorithm for Two-Variable Logic with Counting and Modulo Counting Quantifiers](https://mlsanity.com/paper/2605.03391/) (2026)
- [Solving Combinatorial Counting Problems with Weighted First-Order Model Counting](https://mlsanity.com/paper/2605.24845/) (2026)

## Abstract (arXiv)

Weighted model counting (WMC) is the task of computing the weighted sum of all satisfying assignments (i.e., models) of a propositional formula. Similarly, weighted model sampling (WMS) aims to randomly generate models with probability proportional to their respective weights. Both WMC and WMS are hard to solve exactly, falling under the #mathsfP-hard complexity class. However, it is known that the counting problem may sometimes be tractable, if the propositional formula can be compactly represented and expressed in first-order logic. In such cases, model counting problems can be solved in time polynomial in the domain size, and are known as domain-liftable. The following question then arises: Is it also the case for weighted model sampling? This paper addresses this question and answers it affirmatively. Specifically, we prove the domain-liftability under sampling for the two-variables fragment of first-order logic with counting quantifiers in this paper, by devising an efficient sampling algorithm for this fragment that runs in time polynomial in the domain size. We then further show that this result continues to hold even in the presence of cardinality constraints. To empirically verify our approach, we conduct experiments over various first-order formulas designed for the uniform generation of combinatorial structures and sampling in statistical-relational models. The results demonstrate that our algorithm outperforms a start-of-the-art WMS sampler by a substantial margin, confirming the theoretical results.