# Lifted Variable Elimination: Decoupling the Operators from the Constraint Language

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Feb 2014.

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

- [Colour Passing Revisited: Lifted Model Construction with Commutative Factors](https://mlsanity.com/paper/2309.11236/) (2023)
- [Efficient Detection of Exchangeable Factors in Factor Graphs](https://mlsanity.com/paper/2403.10167/) (2024)
- [Lifted Causal Inference in Relational Domains](https://mlsanity.com/paper/2403.10184/) (2024)
- [Lifted Algorithms for Symmetric Weighted First-Order Model Sampling](https://mlsanity.com/paper/2308.08828/) (2023)
- [Efficient Detection of Commutative Factors in Factor Graphs](https://mlsanity.com/paper/2407.16280/) (2024)
- [Estimating Causal Effects in Partially Directed Parametric Causal Factor Graphs](https://mlsanity.com/paper/2411.07006/) (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)
- [Lifting Factor Graphs with Some Unknown Factors](https://mlsanity.com/paper/2406.01275/) (2024)
- [Lifted Model Construction without Normalisation: A Vectorised Approach to Exploit Symmetries in Factor Graphs](https://mlsanity.com/paper/2411.11730/) (2024)
- [Lifted Forward Planning in Relational Factored Markov Decision Processes with Concurrent Actions](https://mlsanity.com/paper/2505.22147/) (2025)
- [On the Detection of Commutative Factors in Factor Graphs: Necessary and Sufficient Conditions](https://mlsanity.com/paper/2605.26908/) (2026)
- [On the Completeness and Complexity of the Lifted Dynamic Junction Tree Algorithm](https://mlsanity.com/paper/2110.09197/) (2021)
- [First-Order Context-Specific Likelihood Weighting in Hybrid Probabilistic Logic Programs](https://mlsanity.com/paper/2201.11165/) (2022)
- [Towards Privacy-Preserving Relational Data Synthesis via Probabilistic Relational Models](https://mlsanity.com/paper/2409.04194/) (2024)
- [Lifting Factor Graphs with Some Unknown Factors for New Individuals](https://mlsanity.com/paper/2504.04089/) (2025)
- [A First Step Towards Even More Sparse Encodings of Probability Distributions](https://mlsanity.com/paper/2603.29691/) (2026)
- [Lifted Causal Inference](https://mlsanity.com/paper/2606.28024/) (2026)
- [The Curious Case of Exploding DecPOMDPs: Containing the Fire through Policy Counting](https://mlsanity.com/paper/2608.17749/) (2026)

## Abstract (arXiv)

Lifted probabilistic inference algorithms exploit regularities in the structure of graphical models to perform inference more efficiently. More specifically, they identify groups of interchangeable variables and perform inference once per group, as opposed to once per variable. The groups are defined by means of constraints, so the flexibility of the grouping is determined by the expressivity of the constraint language. Existing approaches for exact lifted inference use specific languages for (in)equality constraints, which often have limited expressivity. In this article, we decouple lifted inference from the constraint language. We define operators for lifted inference in terms of relational algebra operators, so that they operate on the semantic level (the constraints extension) rather than on the syntactic level, making them language-independent. As a result, lifted inference can be performed using more powerful constraint languages, which provide more opportunities for lifting. We empirically demonstrate that this can improve inference efficiency by orders of magnitude, allowing exact inference where until now only approximate inference was feasible.