TL;DR
Probabilistic inference in multi-agent, relational, or dynamic domains often suffers from combinatorial state-space explosion, yet different research communities have independently devised techniques to compress symmetric states. This systematic review surveys 116 papers across lifted inference, multi-target tracking, robotics, and biochemical simulation, organizing them into eight distinct categories based on six functional properties. The authors provide a practical decision guide for choosing abstraction techniques and highlight major open gaps—chiefly the inability of existing sequential filtering methods to preserve symmetries over time.
What Problem Does This Paper Address?
Standard probabilistic inference algorithms (such as Variable Elimination or Belief Propagation) operate at a propositional level. When applied to domains with many interacting entities—such as tracking untracked people in an office, modeling molecular interactions in biochemistry, or analyzing social networks—the state space grows exponentially with the number of domain objects.
However, many of these problems possess deep symmetries: molecules of the same type are interchangeable, and unobserved individuals often share identical marginal probabilities. Over the past two decades, disparate communities (e.g., statistical relational AI, multi-object tracking, control theory, and systems biology) tackled this via state-space abstractions—reasoning over compact, "lifted" representations of symmetric states rather than individual ground states. Because these communities developed solutions in silos using completely different terminology, researchers lacked a unified conceptual framework to compare methods and identify unexplored problem domains.
Methods
The authors performed a systematic literature review following PRISMA guidelines, identifying papers across four major academic databases (ScienceDirect, IEEE Xplore, ACM Digital Library, and Scopus).
To compare algorithms across disciplines, the review classifies approaches using six core properties:
- Group Variables: Exploiting exchangeability across identical random variables (e.g., lifted inference).
- Parameterization: Representing distributions compactly via parametric forms (e.g., Kalman filter Gaussians, Fourier series over permutations).
- Splitting: De-abstracting/grounding representations when entities must be treated distinctly.
- Merging: Aggregating grounded variables back into abstract representations (lifting).
- Identification: Ability to handle evidence or queries tied to specific individuals.
- Online: Operating sequentially for dynamic, streaming processes (Bayesian filtering) with bounded per-step complexity.
Using these traits, the authors clustered the literature into eight algorithmic families: Top-down Lifted Inference (LI), Bottom-up LI, Continuous Inference, Probabilistic Multiset Rewriting, Logical Particle Filters, Relational Particle Filters, Relational Kalman Filters, and Data Association.
Datasets
Not discussed in the paper (as this is a qualitative systematic literature review analyzing published methodology rather than an empirical benchmark paper).
Key Insights and Ideas
- Two orthogonal types of abstraction: Algorithms compress state spaces either by grouping interchangeable variables (exploiting exchangeability across objects) or by parameterizing distributions (describing infinite or combinatorial spaces via closed-form functions, Fourier coefficients, or algebraic decision diagrams).
- The symmetry-breaking dilemma: Observing evidence about a single individual shatters symmetry. Top-down lifted inference handles this by splitting abstract formulas. However, in dynamic sequential filtering (e.g., particle filtering), repeated splitting quickly leads to total propositionalization unless an explicit merging operation recombines variables whose distinctions have washed out over time.
- A unified practitioner flowchart: The review translates the six properties into a diagnostic decision tree (Figure 13 in the paper), guiding engineers from problem characteristics (e.g., static vs. dynamic, continuous vs. discrete, presence of individual-level evidence) to the appropriate class of algorithms.
Key Results
- Search and Corpus: From an initial pool of 4,503 records, rigorous inclusion/exclusion filtering yielded 116 primary papers (73 from search queries, 43 identified via citation chaining).
- Terminological fragmentation: The initial query achieved an empirical precision of only 1.6% and recall of 62.9%, quantitatively demonstrating that disparate disciplines use non-overlapping terminology to describe state-space abstraction.
- Ecosystem breakdown: Research is heavily skewed toward static models:
- Top-down lifted inference: 50 papers
- Bottom-up lifted inference: 31 papers
- Data association: 16 papers
- Stochastic multiset rewriting: 7 papers
- Continuous inference: 5 papers
- Dynamic relational/logical filtering (LPF, RPF, RKF): 7 papers combined
Limitations and Future Work
- Excluded problem domains: The survey explicitly excluded deterministic state-space abstraction methods (e.g., partial order reduction in model checking), first-order Markov Decision Processes (MDPs) solved via dynamic programming, and relational parameter/structure learning algorithms that do not contribute a novel inference abstraction.
- Unaddressed algorithmic frontiers:
- Hybrid relational inference: Almost no algorithms simultaneously exploit relational exchangeability (grouping variables) and general continuous distributions (beyond restricted Gaussian relational models).
- Lifted Bayesian filtering: True lifted inference capabilities (such as counting formulas) have not yet been generalized to online, sequential Bayesian filtering with arbitrary distributions.
- Re-introducing symmetry: More work is needed on approximate "re-lifting" or merging mechanisms to heal symmetries broken by sensor evidence over long time horizons.
Summary updated