State-Space Abstractions for Probabilistic Inference: A Systematic Review

Stefan Lüdtke, Max Schröder, Frank Krüger, Sebastian Bader, Thomas Kirste

Introduction

Probabilistic inference is a cornerstone of modern artificial intelligence, enabling reasoning under uncertainty in diverse fields such as social network analysis, human behavior recognition, and biochemical modeling. However, as the scale of these systems grows, standard inference algorithms face a significant hurdle: the state-space explosion problem. This paper provides a systematic review of "state-space abstraction" techniques—methods designed to exploit symmetries and redundancies to make inference computationally tractable. By analyzing 116 core papers, the authors bridge fragmented research communities and offer a unified taxonomy for these "lifted" inference methods.

The State-Space Explosion Problem

Standard probabilistic inference algorithms typically operate at a "propositional" level. In this paradigm, every individual entity—whether it is a person in a social network or a molecule in a cell—is treated as a unique random variable. As the number of entities increases, the complexity of the model grows exponentially.

A factor graph representation of a relational model involving smoking, cancer, and mortality for individuals Alice and Bob.

Consider a model of a flu outbreak or the classic "Friends and Smokers" example shown in the figure above. In a propositional model, the probability of Alice having cancer is treated separately from the probability of Bob having cancer, even if their underlying risk factors and relationships are identical. This redundancy is the root of the state-space explosion. State-space abstraction aims to "lift" these symmetries, allowing algorithms to reason over groups of equivalent entities rather than individuals.

A Unified Taxonomy of Abstractions

The authors' primary contribution is a rigorous taxonomy based on six functional properties of inference algorithms. This framework allows researchers to categorize and compare methods from disparate fields like AI, control theory, and computer vision.

  1. Group Variables: The ability to treat equivalent random variables as a single block.
  2. Parameterization: Representing distributions using functional forms (e.g., Gaussians) instead of exhaustive tables.
  3. Splitting: The capacity to break an abstraction when an individual entity becomes "special" due to specific observations (e.g., observing Alice specifically).
  4. Merging: Re-abstracting a model by identifying new symmetries that emerge during inference.
  5. Identification: Handling evidence related to specific individuals within a group.
  6. Online Inference: Capability for real-time, sequential reasoning, such as Bayesian filtering.

Based on these properties, the authors identify eight distinct algorithmic families, ranging from top-down lifted inference to relational particle filters and data association methods.

Key Insights and Research Gaps

The systematic review reveals several critical insights into the state of the field:

  • The "Lifting" Unity: Despite different terminologies, "Lifted Inference" in AI and "Data Association" in computer vision are fundamentally performing the same task: inference over compact representations of symmetric states.
  • Top-Down vs. Bottom-Up: Algorithms are divided between those that start with high-level relational descriptions (top-down) and those that automatically discover symmetries in "flat" propositional models (bottom-up).
  • The Symmetry-Breaking Curse: A single observation about one individual can "break" the symmetry of an entire group, potentially forcing the algorithm to revert to slow, propositional reasoning. This is a major bottleneck for scaling.
  • Hybrid Model Gaps: There is a notable lack of algorithms that can simultaneously handle variable grouping (exchangeability) and complex continuous distributions, except in highly restricted cases.

Conclusion and Future Directions

The field of lifted inference has seen a massive spike in interest since 2008, moving from theoretical logic to practical probabilistic programming. However, significant challenges remain. Current "online" lifted filters often suffer from "complete propositionalization" over time because they lack robust mechanisms to re-discover symmetries as systems evolve.

Furthermore, the authors suggest that "approximate lifting"—treating entities that are "almost" identical as the same—is a promising frontier. Developing algorithms that can handle these approximate symmetries while maintaining accuracy will be essential for applying probabilistic inference to truly massive, real-world systems. This systematic review serves as a roadmap for engineers and researchers to navigate these complex techniques and identify the most suitable abstraction for their specific problem.

Summary updated

Abstract

Tasks such as social network analysis, human behavior recognition, or modeling biochemical reactions, can be solved elegantly by using the probabilistic inference framework. However, standard probabilistic inference algorithms work at a propositional level, and thus cannot capture the symmetries and redundancies that are present in these tasks. Algorithms that exploit those symmetries have been devised in different research fields, for example by the lifted inference-, multiple object tracking-, and modeling and simulation-communities. The common idea, that we call state space abstraction, is to perform inference over compact representations of sets of symmetric states. Although they are concerned with a similar topic, the relationship between these approaches has not been investigated systematically. This survey provides the following contributions. We perform a systematic literature review to outline the state of the art in probabilistic inference methods exploiting symmetries. From an initial set of more than 4,000 papers, we identify 116 relevant papers. Furthermore, we provide new high-level categories that classify the approaches, based on common properties of the approaches. The research areas underlying each of the categories are introduced concisely. Researchers from different fields that are confronted with a state space explosion problem in a probabilistic system can use this classification to identify possible solutions. Finally, based on this conceptualization, we identify potentials for future research, as some relevant application domains are not addressed by current approaches.
BibTeX
@article{ludtke2018state,
  author = {Stefan Lüdtke and Max Schröder and Frank Krüger and Sebastian Bader and Thomas Kirste},
  title = {{State-Space Abstractions for Probabilistic Inference: A Systematic Review}},
  journal = {J. Artif. Intell. Res.},
  year = {2018},
  url = {https://openreview.net/forum?id=ARgZ1RWpCC},
}
Figure