Variable Elimination¶
An exact factor-based inference algorithm that removes nonquery variables one at a time by combining their incident factors and summing or optimizing them out, with complexity controlled by elimination order.
Core Idea¶
Variable elimination is an exact algorithmic pattern for inference in a factored function such as a Bayesian network, Markov random field, constraint network, or dynamic-programming model. To remove a nonquery variable \(X\), gather every current factor whose scope contains \(X\), multiply or otherwise combine them, then eliminate \(X\) with the problem's marginalization operator—usually summation for probabilities or maximization for MAP-style objectives. The resulting factor on the remaining neighboring variables replaces the gathered factors.
For probabilistic inference, distributivity lets elimination avoid constructing the full joint table. The numerical answer is independent of a valid summation order, but intermediate factor sizes are not.
Scope of Application¶
The algorithm is used for marginals, evidence likelihoods, conditional probabilities, most probable explanations, constraint reasoning, expected utility, and related factored computations. In Bayesian networks it incorporates evidence by restricting factors, then eliminates hidden variables. In Markov networks it operates on potentials. In influence diagrams or MAP tasks, operator order can be constrained because sum and max do not generally commute.
Variable elimination also provides the conceptual basis of junction-tree compilation and bucket elimination. It is effective when treewidth is modest or when a good order keeps intermediate scopes small. Dense interactions or poor orderings can make exact computation infeasible.
Clarity¶
The abstraction clarifies why local conditional tables do not automatically make inference cheap. Multiplying only the factors relevant to the current variable keeps irrelevant structure separate, but elimination can connect all remaining neighbors, creating fill-in. A sparse input graph can therefore generate a large intermediate factor.
Manages Complexity¶
The full joint distribution over \(n\) binary variables has \(2^n\) entries. Factorization stores local tables and elimination uses distributivity to combine only locally relevant pieces. Complexity is governed by the largest intermediate scope: for domain size \(d\) and induced width \(w\), a typical bound is exponential in \(w+1\), not necessarily \(n\).
Abstract Reasoning¶
Suppose a joint factorization is \(F(X,Y,Z)=\phi_1(X,Y)\phi_2(Y,Z)\phi_3(Z)\), and the query is a function of \(X\). Eliminating \(Z\) creates
then eliminating \(Y\) creates \(h(X)=\sum_Y\phi_1(X,Y)g(Y)\). This equals \(\sum_{Y,Z}F(X,Y,Z)\) by associativity and distributivity, without materializing the full three-variable table.
Knowledge Transfer¶
Literal transfer occurs across Bayesian networks, Markov random fields, constraint networks, and bucket-elimination formulations where combination distributes over elimination. The reusable workflow is: factor, choose order, gather bucket, combine, eliminate, and insert replacement. Graph-width analysis transfers with it.
The broader pattern belongs to Algorithm, Decomposition, and Dynamic Programming. But Gaussian elimination or organizational removal does not inherit probabilistic factor semantics. Transfer is literal only when local factors and a distributive operator pair remain.
Relationships to Other Abstractions¶
Current abstraction Variable Elimination Domain-specific
Parents (1) — more general patterns this builds on
-
Variable Elimination is a kind of Algorithm Prime
Variable Elimination specializes
prime:algorithm: inputs, ordered effective steps, exact output, termination, and resource bounds are explicit.
Hierarchy paths (2) — routes to 2 parentless roots
- Variable Elimination → Algorithm → Function (Mapping)
Neighborhood in Abstraction Space¶
Variable Elimination sits in a sparse region of the domain-specific corpus (81st percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (1565 abstractions)
Nearest neighbors
- Condensed Detachment — 0.83
- Boosting — 0.83
- Polynomial Chaos Expansion — 0.82
- Probability Bounds Analysis — 0.81
- Tensor Sketch — 0.81
Computed from structural-signature embeddings · 2026-09-08