# Faster Lifting for Ordered Domains with Predecessor Relations

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 25 references that are in the map.
- First posted on arXiv 25 Jul 2025.

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

- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (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)
- [Lifted Inference with Linear Order Axiom](https://mlsanity.com/paper/2211.01164/) (2022)
- [Bridging Weighted First Order Model Counting and Graph Polynomials](https://mlsanity.com/paper/2407.11877/) (2024)
- [Complexity of Weighted First-Order Model Counting in the Two-Variable Fragment with Counting Quantifiers: A Bound to Beat](https://mlsanity.com/paper/2404.12905/) (2024)
- [Stable Dinner Party Seating Arrangements](https://mlsanity.com/paper/2305.09549/) (2023)
- [Weighted First Order Model Counting with Directed Acyclic Graph Axioms](https://mlsanity.com/paper/2302.09830/) (2023)

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

- [A Fast Model Counting Algorithm for Two-Variable Logic with Counting and Modulo Counting Quantifiers](https://mlsanity.com/paper/2605.03391/) (2026)
- [CombEval: A Framework for Evaluating Combinatorial Counting in Large Language Models](https://mlsanity.com/paper/2606.19788/) (2026)

## Abstract (arXiv)

We investigate lifted inference on ordered domains with predecessor relations, where the elements of the domain respect a total (cyclic) order, and every element has a distinct (clockwise) predecessor. Previous work has explored this problem through weighted first-order model counting (WFOMC), which computes the weighted sum of models for a given first-order logic sentence over a finite domain. In WFOMC, the order constraint is typically encoded by the linear order axiom introducing a binary predicate in the sentence to impose a linear ordering on the domain elements. The immediate and second predecessor relations are then encoded by the linear order predicate. Although WFOMC with the linear order axiom is theoretically tractable, existing algorithms struggle with practical applications, particularly when the predecessor relations are involved. In this paper, we treat predecessor relations as a native part of the axiom and devise a novel algorithm that inherently supports these relations. The proposed algorithm not only provides an exponential speedup for the immediate and second predecessor relations, which are known to be tractable, but also handles the general k-th predecessor relations. The extensive experiments on lifted inference tasks and combinatorics math problems demonstrate the efficiency of our algorithm, achieving speedups of a full order of magnitude.