# Lifted Model Construction under Approximate Commutativity

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

## Key facts

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

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

- [Tractability through Exchangeability: A New Perspective on Efficient Probabilistic Inference](https://mlsanity.com/paper/1401.1247/) (2014)
- [Colour Passing Revisited: Lifted Model Construction with Commutative Factors](https://mlsanity.com/paper/2309.11236/) (2023)
- [Efficient Detection of Commutative Factors in Factor Graphs](https://mlsanity.com/paper/2407.16280/) (2024)
- [Approximate Lifted Model Construction](https://mlsanity.com/paper/2504.20784/) (2025)
- [Compression versus Accuracy: A Hierarchy of Lifted Models](https://mlsanity.com/paper/2505.22288/) (2025)
- [On the Detection of Commutative Factors in Factor Graphs: Necessary and Sufficient Conditions](https://mlsanity.com/paper/2605.26908/) (2026)

## Abstract (arXiv)

Lifted inference algorithms enable scalable probabilistic inference even for large object domains by leveraging the indistinguishability of objects in a probability distribution. An essential prerequisite for constructing a lifted representation is to identify commutative factors, i.e., functions whose output values are invariant under permutations of a subset of their input values, in a potential-based factorisation. In practice, however, parameters learned from data inevitably deviate even if associated objects are indistinguishable, causing their corresponding factors to be only approximately commutative instead of being exactly commutative. We address this problem by introducing the concept of ε-commutativity, a relaxation of commutativity where output values are only approximately invariant under permutations of input values. Specifically, we show how ε-commutativity can be exploited for lifted model construction, downstream probabilistic inference, and prove strict bounds on the induced approximation error, thereby ensuring the practical applicability of lifted model construction while maintaining highly accurate query results. These theoretical guarantees are confirmed empirically, demonstrating comparable query accuracy at lower runtime.