# Tractability through Exchangeability: A New Perspective on Efficient Probabilistic Inference

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jan 2014.

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

- [How to Turn Your Knowledge Graph Embeddings into Generative Models](https://mlsanity.com/paper/2305.15944/) (2023)
- [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)
- [Efficient Detection of Commutative Factors in Factor Graphs](https://mlsanity.com/paper/2407.16280/) (2024)
- [Sum-Product-Set Networks: Deep Tractable Models for Tree-Structured Graphs](https://mlsanity.com/paper/2408.07394/) (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)
- [Exchangeability-Aware Sum-Product Networks](https://mlsanity.com/paper/2110.05165/) (2021)
- [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)
- [Lifting DecPOMDPs for Nanoscale Systems -- A Work in Progress](https://mlsanity.com/paper/2110.09152/) (2021)
- [Bayesian Theory of Consciousness as Exchangeable Emotion-Cognition Inference](https://mlsanity.com/paper/2407.09488/) (2024)
- [Combining Local Symmetry Exploitation and Reinforcement Learning for Optimised Probabilistic Inference -- A Work In Progress](https://mlsanity.com/paper/2503.08786/) (2025)
- [Lifting Factor Graphs with Some Unknown Factors for New Individuals](https://mlsanity.com/paper/2504.04089/) (2025)
- [Why Isn't Relational Learning Taking Over the World?](https://mlsanity.com/paper/2507.13558/) (2025)
- [A homotopy-type-theoretic generalization of neurosymbolic inference](https://mlsanity.com/paper/2606.17851/) (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)
- [Lifted Model Construction under Approximate Commutativity](https://mlsanity.com/paper/2608.24713/) (2026)

## Abstract (arXiv)

Exchangeability is a central notion in statistics and probability theory. The assumption that an infinite sequence of data points is exchangeable is at the core of Bayesian statistics. However, finite exchangeability as a statistical property that renders probabilistic inference tractable is less well-understood. We develop a theory of finite exchangeability and its relation to tractable probabilistic inference. The theory is complementary to that of independence and conditional independence. We show that tractable inference in probabilistic models with high treewidth and millions of variables can be understood using the notion of finite (partial) exchangeability. We also show that existing lifted inference algorithms implicitly utilize a combination of conditional independence and partial exchangeability.