# Bucket Elimination: A Unifying Framework for Several Probabilistic Inference

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

## Key facts

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

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

- [VolcanoML: Speeding up End-to-End AutoML via Scalable Search Space Decomposition](https://mlsanity.com/paper/2107.08861/) (2021)
- [Causal Inference Using Tractable Circuits](https://mlsanity.com/paper/2202.02891/) (2022)
- [Partition Function Estimation: A Quantitative Study](https://mlsanity.com/paper/2105.11132/) (2021)
- [On the Complexity of Counterfactual Reasoning](https://mlsanity.com/paper/2211.13447/) (2022)
- [Mixtures of All Trees](https://mlsanity.com/paper/2302.14202/) (2023)
- [Identifying Causal Effects Under Functional Dependencies](https://mlsanity.com/paper/2403.04919/) (2024)
- [Pretrained Cost Model for Distributed Constraint Optimization Problems](https://mlsanity.com/paper/2112.04187/) (2021)
- [Deep Attentive Belief Propagation: Integrating Reasoning and Learning for Solving Constraint Optimization Problems](https://mlsanity.com/paper/2209.12000/) (2022)
- [Faster Exact MPE and Constrained Optimization with Deterministic Finite State Automata](https://mlsanity.com/paper/2108.03899/) (2021)
- [Unifying AI Algorithms with Probabilistic Programming using Implicitly Defined Representations](https://mlsanity.com/paper/2110.02325/) (2021)
- [Physics-Informed Deep Monte Carlo Quantile Regression method for Interval Multilevel Bayesian Network-based Satellite Heat Reliability Analysis](https://mlsanity.com/paper/2202.06860/) (2022)
- [Efficient End-to-End AutoML via Scalable Search Space Decomposition](https://mlsanity.com/paper/2206.09423/) (2022)
- [GDBA Revisited: Unleashing the Power of Guided Local Search for Distributed Constraint Optimization](https://mlsanity.com/paper/2508.06899/) (2025)

## Abstract (arXiv)

Probabilistic inference algorithms for finding the most probable explanation, the maximum aposteriori hypothesis, and the maximum expected utility and for updating belief are reformulated as an elimination--type algorithm called bucket elimination. This emphasizes the principle common to many of the algorithms appearing in that literature and clarifies their relationship to nonserial dynamic programming algorithms. We also present a general way of combining conditioning and elimination within this framework. Bounds on complexity are given for all the algorithms as a function of the problem's structure.