# Lifted Inference with Linear Order Axiom

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 26 references that are in the map.
- First posted on arXiv 2 Nov 2022.

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

- [Probabilistic Generating Circuits](https://mlsanity.com/paper/2102.09768/) (2021)
- [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)
- [Weighted Model Counting in FO2 with Cardinality Constraints and Counting Quantifiers: A Closed Form Formula](https://mlsanity.com/paper/2110.05992/) (2021)
- [Two-variable Logic with Counting and a Linear Order](https://mlsanity.com/paper/1604.06038/) (2016)

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

- [Lifted Algorithms for Symmetric Weighted First-Order Model Sampling](https://mlsanity.com/paper/2308.08828/) (2023)
- [Lifted Inference beyond First-Order Logic](https://mlsanity.com/paper/2308.11738/) (2023)
- [Bridging Weighted First Order Model Counting and Graph Polynomials](https://mlsanity.com/paper/2407.11877/) (2024)
- [On Exact Sampling in the Two-Variable Fragment of First-Order Logic](https://mlsanity.com/paper/2302.02730/) (2023)
- [Faster Lifting for Ordered Domains with Predecessor Relations](https://mlsanity.com/paper/2507.19182/) (2025)
- [Weighted First Order Model Counting with Directed Acyclic Graph Axioms](https://mlsanity.com/paper/2302.09830/) (2023)
- [Towards Practical First-Order Model Counting](https://mlsanity.com/paper/2502.12278/) (2025)
- [Polynomial-Time Relational Probabilistic Inference in Open Universes](https://mlsanity.com/paper/2505.04115/) (2025)
- [Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relations](https://mlsanity.com/paper/2508.11515/) (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)
- [CombEval: A Framework for Evaluating Combinatorial Counting in Large Language Models](https://mlsanity.com/paper/2606.19788/) (2026)

## Abstract (arXiv)

We consider the task of weighted first-order model counting (WFOMC) used for probabilistic inference in the area of statistical relational learning. Given a formula φ, domain size n and a pair of weight functions, what is the weighted sum of all models of φ over a domain of size n? It was shown that computing WFOMC of any logical sentence with at most two logical variables can be done in time polynomial in n. However, it was also shown that the task is texttt#P1-complete once we add the third variable, which inspired the search for extensions of the two-variable fragment that would still permit a running time polynomial in n. One of such extension is the two-variable fragment with counting quantifiers. In this paper, we prove that adding a linear order axiom (which forces one of the predicates in φ to introduce a linear ordering of the domain elements in each model of φ) on top of the counting quantifiers still permits a computation time polynomial in the domain size. We present a new dynamic programming-based algorithm which can compute WFOMC with linear order in time polynomial in n, thus proving our primary claim.