# Compression versus Accuracy: A Hierarchy of Lifted Models

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 27 references that are in the map.
- First posted on arXiv 28 May 2025.

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

- [Tractability through Exchangeability: A New Perspective on Efficient Probabilistic Inference](https://mlsanity.com/paper/1401.1247/) (2014)
- [Lifted Variable Elimination: Decoupling the Operators from the Constraint Language](https://mlsanity.com/paper/1402.0565/) (2014)
- [Colour Passing Revisited: Lifted Model Construction with Commutative Factors](https://mlsanity.com/paper/2309.11236/) (2023)
- [Approximate Lifted Model Construction](https://mlsanity.com/paper/2504.20784/) (2025)

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

- [On the Detection of Commutative Factors in Factor Graphs: Necessary and Sufficient Conditions](https://mlsanity.com/paper/2605.26908/) (2026)
- [Inducing Comparability of Factorised Probability Distributions](https://mlsanity.com/paper/2607.20502/) (2026)
- [Lifted Model Construction under Approximate Commutativity](https://mlsanity.com/paper/2608.24713/) (2026)

## Abstract (arXiv)

Probabilistic graphical models that encode indistinguishable objects and relations among them use first-order logic constructs to compress a propositional factorised model for more efficient (lifted) inference. To obtain a lifted representation, the state-of-the-art algorithm Advanced Colour Passing (ACP) groups factors that represent matching distributions. In an approximate version using varepsilon as a hyperparameter, factors are grouped that differ by a factor of at most (1± varepsilon). However, finding a suitable varepsilon is not obvious and may need a lot of exploration, possibly requiring many ACP runs with different varepsilon values. Additionally, varying varepsilon can yield wildly different models, leading to decreased interpretability. Therefore, this paper presents a hierarchical approach to lifted model construction that is hyperparameter-free. It efficiently computes a hierarchy of varepsilon values that ensures a hierarchy of models, meaning that once factors are grouped together given some varepsilon, these factors will be grouped together for larger varepsilon as well. The hierarchy of varepsilon values also leads to a hierarchy of error bounds. This allows for explicitly weighing compression versus accuracy when choosing specific varepsilon values to run ACP with and enables interpretability between the different models.