Lifted Model Construction under Approximate Commutativity

Malte Luttermann; Jan Speller; Tanya Braun; Marcel Gehrke; Ralf Möller

cs.AIAug 25, 2026

Lifted Model Construction under Approximate Commutativity

Authors: Malte Luttermann, Jan Speller, Tanya Braun, Marcel Gehrke, Ralf Möller

Organizations: Institute for Humanities-Centered Artificial Intelligence, University of Hamburg · Data Science Group, University of Münster

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: (a) An fg modelling the interplay between the competences of two employees and the revenue of the company they work for. (b) The function definition of $\phi_{3}$ , where $\varphi_{1},\allowbreak\ldots,\allowbreak\varphi_{6}\in\mathbb{R}_{\geq 0}$ with $\varphi_{i}\neq\varphi_{j}$ for all $i\neq j$ .

Panel of Table 1 — Table 1: (a) An exemplary factor $\phi(ComA,ComB,Rev)$ with $\varepsilon$ -commutative arguments $\{ComA,\allowbreak ComB\}$ provided that $\varphi_{3}$ and $\varphi^{\prime}_{3}$ as well as $\varphi_{4}$ and $\varphi^{\prime}_{4}$ are $\varepsilon$ -equivalent. (b) A compressed representation of $\phi(ComA,ComB,Rev)$ from (a) using a crv to represent the $\varepsilon$ -commutative arguments $\{ComA,\allowbreak ComB\}$ .

Panel of Figure 2 — Figure 2: Downstream lifted inference performance, averaged over all generated instances and queries. (a) Run time of lve on the compressed model returned by acp and its $\varepsilon$ -relaxed variant ( acp $\pm\varepsilon$ ). (b) Distribution of the per-query quotient $p^{\prime}\mathbin{/}p$ between the approximate result $p^{\prime}$ and the exact result $p$ .

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: (a) Run time of lve on the compressed model returned by acp and its $\varepsilon$ -relaxed variant ( acp $\pm\varepsilon$ ), and (b) distribution of the per-query quotient $p^{\prime}\mathbin{/}p$ between the approximate result $p^{\prime}$ and the exact result $p$ for input fg containing $k=1$ $\varepsilon$ -commutative factors with $\varepsilon=0.001$ .

Panel of Figure 4 — Figure 4: (a) Run time of lve on the compressed model returned by acp and its $\varepsilon$ -relaxed variant ( acp $\pm\varepsilon$ ), and (b) distribution of the per-query quotient $p^{\prime}\mathbin{/}p$ between the approximate result $p^{\prime}$ and the exact result $p$ for input fg containing $k=1$ $\varepsilon$ -commutative factors with $\varepsilon=0.01$ .

Panel of Figure 5 — Figure 5: (a) Run time of lve on the compressed model returned by acp and its $\varepsilon$ -relaxed variant ( acp $\pm\varepsilon$ ), and (b) distribution of the per-query quotient $p^{\prime}\mathbin{/}p$ between the approximate result $p^{\prime}$ and the exact result $p$ for input fg containing $k=1$ $\varepsilon$ -commutative factors with $\varepsilon=0.1$ .

Panel of Figure 6 — Figure 6: (a) Run time of lve on the compressed model returned by acp and its $\varepsilon$ -relaxed variant ( acp $\pm\varepsilon$ ), and (b) distribution of the per-query quotient $p^{\prime}\mathbin{/}p$ between the approximate result $p^{\prime}$ and the exact result $p$ for input fg containing $k=3$ $\varepsilon$ -commutative factors with $\varepsilon=0.001$ .

Panel of Figure 7 — Figure 7: (a) Run time of lve on the compressed model returned by acp and its $\varepsilon$ -relaxed variant ( acp $\pm\varepsilon$ ), and (b) distribution of the per-query quotient $p^{\prime}\mathbin{/}p$ between the approximate result $p^{\prime}$ and the exact result $p$ for input fg containing $k=3$ $\varepsilon$ -commutative factors with $\varepsilon=0.01$ .

Panel of Figure 8 — Figure 8: (a) Run time of lve on the compressed model returned by acp and its $\varepsilon$ -relaxed variant ( acp $\pm\varepsilon$ ), and (b) distribution of the per-query quotient $p^{\prime}\mathbin{/}p$ between the approximate result $p^{\prime}$ and the exact result $p$ for input fg containing $k=3$ $\varepsilon$ -commutative factors with $\varepsilon=0.1$ .

Panel of Figure 9 — Figure 9: (a) Run time of lve on the compressed model returned by acp and its $\varepsilon$ -relaxed variant ( acp $\pm\varepsilon$ ), and (b) distribution of the per-query quotient $p^{\prime}\mathbin{/}p$ between the approximate result $p^{\prime}$ and the exact result $p$ for input fg containing $k=7$ $\varepsilon$ -commutative factors with $\varepsilon=0.001$ .

Panel of Figure 10 — Figure 10: (a) Run time of lve on the compressed model returned by acp and its $\varepsilon$ -relaxed variant ( acp $\pm\varepsilon$ ), and (b) distribution of the per-query quotient $p^{\prime}\mathbin{/}p$ between the approximate result $p^{\prime}$ and the exact result $p$ for input fg containing $k=7$ $\varepsilon$ -commutative factors with $\varepsilon=0.01$ .

Panel of Figure 11 — Figure 11: (a) Run time of lve on the compressed model returned by acp and its $\varepsilon$ -relaxed variant ( acp $\pm\varepsilon$ ), and (b) distribution of the per-query quotient $p^{\prime}\mathbin{/}p$ between the approximate result $p^{\prime}$ and the exact result $p$ for input fg containing $k=7$ $\varepsilon$ -commutative factors with $\varepsilon=0.1$ .

Panel of Figure 12 — Figure 12: (a) Speedup for online inference run times (i.e., ratio of the run time of lve on the compressed model returned by acp and the run time of lve on the compressed model returned by the $\varepsilon$ -relaxed variant of acp ). (b) Offline run times of acp and its $\varepsilon$ -relaxed variant ( acp $\pm\varepsilon$ ).

Panel of Figure 13 — Figure 13: Compression ratio $\lvert M^{\prime}\rvert\mathbin{/}\lvert M\rvert$ between the compressed model $M^{\prime}$ and the original model $M$ for input fg containing $k=1$ $\varepsilon$ -commutative factors with (a) $\varepsilon=0.001$ and (b) $\varepsilon=0.1$ .

Panel of Figure 14 — Figure 14: Compression ratio $\lvert M^{\prime}\rvert\mathbin{/}\lvert M\rvert$ between the compressed model $M^{\prime}$ and the original model $M$ for input fg containing $k=3$ $\varepsilon$ -commutative factors with (a) $\varepsilon=0.001$ and (b) $\varepsilon=0.1$ .

Panel of Figure 15 — Figure 15: Compression ratio $\lvert M^{\prime}\rvert\mathbin{/}\lvert M\rvert$ between the compressed model $M^{\prime}$ and the original model $M$ for input fg containing $k=7$ $\varepsilon$ -commutative factors with (a) $\varepsilon=0.001$ and (b) $\varepsilon=0.1$ .

Panel of Figure 16 — Figure 16: Compression ratio $\lvert M^{\prime}\rvert\mathbin{/}\lvert M\rvert$ between the compressed model $M^{\prime}$ and the original model $M$ broken down per instance class, averaged over the number of commutative factors $k$ and the tolerance $\varepsilon$ .

Efficient Inference

Efficient inference reduces the compute, memory, latency, or energy needed to produce accurate predictions, posterior estimates, and decisions.

See all 109 papers

On the Detection of Commutative Factors in Factor Graphs: Necessary and Sufficient Conditions
May 26, 2026Malte Luttermann, Ralf Möller, Marcel GehrkeEfficient Inference
Institute for Humanities-Centered Artificial Intelligence, University of Hamburg, Germany
Lifted Causal Inference
Jun 26, 2026Malte Luttermann, Tanya Braun, Ralf Möller +1Causal Effect Estimation Efficient Inference
Institute for Humanities-Centered Artificial Intelligence, University of Hamburg, Hamburg, Germany. · German Research Center for Artificial Intelligence (DFKI), Lübeck, Germany. · Data Science Group, University of Münster, Münster, Germany.
Lifted Relational Probabilistic Inference via Implicit Learning
Feb 16, 2026Luise Ge, Brendan Juba, Kris Nilsson +1Probabilistic Logic Efficient Inference
Computer Science & Engineering, Washington University in St. Louis, St. Louis, Missouri, USA

May 26, 2026J/K move · Enter open · S save

On the Detection of Commutative Factors in Factor Graphs: Necessary and Sufficient Conditions

Malte Luttermann, Ralf Möller, Marcel Gehrke

Institute for Humanities-Centered Artificial Intelligence, University of Hamburg, Germany

Efficient Inference

Open paper AskPDF arXiv

Exploiting the indistinguishability of objects in a probabilistic graphical model such as a factor graph is key to lifted probabilistic inference algorithms and allows for tractable probabilistic inference problems with respect to domain sizes. A central building block for the exploitation of indistinguishable objects in factor graphs is the identification of commutative factors, i.e., factors whose output values are invariant under permutations of input values assigned to a subset of their arguments. In this paper, we revisit the theoretical foundations underlying the state-of-the-art algorithm to detect commutative factors. Specifically, we show that in its current form, the state-of-the-art algorithm relies on a central theorem that is mistakenly regarded as a sufficient condition to identify commutative factors, while it actually only implies necessary condition. Consequently, the state of the art might, as we show in this paper, deliver incorrect results. To fix the flaws currently present in the state of the art, we prove a slightly modified version of the aforementioned theorem, which serves as a necessary condition to identify commutative factors. Moreover, we present a corrected version of the state-of-the-art algorithm, which keeps its efficiency while ensuring correctness and introduce a complementary algorithm with tighter worst-case bounds.

Abstract

Efficient Inference

Explore similar work

On the Detection of Commutative Factors in Factor Graphs: Necessary and Sufficient Conditions

Lifted Causal Inference

Lifted Relational Probabilistic Inference via Implicit Learning