Exact Inference by Variable Elimination and the Cost of Treewidth

A factored joint is a recipe for a distribution, not an answer to a question. The questions that matter are conditional: given evidence $E = e$, what is the marginal over a query set $Q$? Written as sums over the product of factors, the answer involves summing over every non-query, non-evidence variable simultaneously, and a naive evaluation costs a number of additions equal to the number of joint assignments. Variable elimination is the observation that the order of those sums is free and that some orders are dramatically cheaper than others.

Factors, scopes, and two operations

A factor is a function from assignments of a set of variables, its scope, to non-negative reals. Two operations suffice. Multiplying two factors produces a factor over the union of their scopes, with entries formed by matching the shared variables; summing a variable out of a factor produces a factor over the scope minus that variable, with entries summed over its values. The result of multiplying then eliminating one variable has scope equal to the union of the operands’ scopes minus the eliminated variable, which is the fact that makes the whole method work: multiplying two factors costs at most the size of that union, not the size of the full joint.

Computing $p(Q \mid E = e)$ therefore goes as follows. Fix the evidence by restricting every factor whose scope contains an evidence variable to the observed assignment; this can only shrink scopes. Then eliminate each remaining non-query variable in turn, by multiplying every factor that contains it and summing it out. The factors left over are all over subsets of $Q$; multiply them together and normalize. The normalizer accumulated along the way is $p(E = e)$, so the same pass yields the likelihood of the evidence, which is exactly the evidence term that appears in the update discussed in Conjugate Priors and the Arithmetic of Posterior Updating. The method is symmetric with respect to summing and maximizing: replacing the sum by a maximum over the eliminated variable computes the maximum a posteriori assignment over the remaining variables.

The order decides the size of the intermediate tables

Consider a hub variable $H$ with $n$ leaf variables attached to it, and no other edges. Eliminating the leaves first is cheap: each leaf elimination multiplies two factors of scope ${H, L_i}$ and returns a factor over ${H}$, so the running product never exceeds two variables. Eliminating $H$ first is catastrophic: the product of all $n$ leaf factors is a single factor over the $n$ leaves, with $2^n$ entries, and the remaining work is on that table. The graph is identical. Only the order changed, and the cost moved from linear to exponential.

Chains behave the other way. In a chain $X_1 \rightarrow X_2 \rightarrow \dots \rightarrow X_n$ of binary variables, eliminating in index order keeps every intermediate factor confined to two variables, giving a linear number of two-variable operations, whereas an order that interleaves far apart ends of the chain produces wider intermediates. Both examples follow from one rule stated in terms of scopes: eliminating a variable costs the product of the sizes of the factors that must be combined, and the scope of the result is their union minus the variable. Two variables that have never been in a factor together can still end up in one, if the elimination order brings them together.

From elimination order to induced width

The cost of an order can be read off the graph without writing a single number down. Take the directed graph, marry the parents of every node by adding edges between all pairs of parents, and discard directions; the result is the moral graph. Eliminating a node means removing it and adding edges between all of its remaining neighbours, because those neighbours now appear together in an intermediate factor. The number of neighbours at the moment a variable is eliminated, its induced width, is one less than the scope size of the largest factor the elimination of that variable produces; the maximum over the order is the induced width of the order.

For $n$ variables each with domain size $d$, eliminating a variable of induced width $w$ costs $O(d^{w+1})$ time and $O(d^w)$ space, so the whole inference costs $O(n,d^{w+1})$ time for the worst tag along the order. The width of the graph, the treewidth, is the smallest induced width over all orders, and it is the parameter that measures how hard exact inference on that graph is. A chain or tree has treewidth 1, so the cost is linear in $n$ with a factor of $d^2$; the moral graph of a densely connected model can have width $n-1$, where the same formula returns $O(n,d^n)$. With $d = 2$ and $n = 30$, an order of induced width 3 costs about $30 \cdot 2^4 = 480$ elementary operations per factor entry pass, while an order of width 20 crosses the $2^{21}$-sized intermediate that no longer fits in memory.

Why no clever algorithm escapes the exponential

The width is a property of the graph, and the smallest width is what any exact method must pay for. Optimal variable elimination is the same computation as finding a tree decomposition of minimum width, and computing treewidth is NP-hard, as is approximating it within a constant factor. The inference problem inherits that hardness: exact marginal inference in a general Bayesian network is NP-hard, and exact maximum a posteriori assignment is NP-hard as well. The reductions are standard. Inferring a marginal is at least as hard as counting the satisfying assignments of a formula, since a Boolean formula can be encoded as a network whose single query variable is true on exactly the satisfying assignments, and $3$-satisfiability restricts to that counting problem.

This is a statement about the worst case, and the worst case is not a small corner of the problem space. Structures with high treewidth arise naturally whenever one variable is conditioned on many others, which is the same condition under which a tabular conditional distribution becomes unwritable. The practical consequence is a fork: either restrict the model class so that width stays bounded, or accept an approximation whose error is not bounded by the width, as discussed in Belief Propagation on Trees and Why Loopy Message Passing Fails and Variational Inference and the Evidence Lower Bound.

Choosing an order without solving the hard problem

Since optimal width is out of reach, implementations use greedy heuristics on the evolving moral graph. The min-degree heuristic eliminates a variable with the fewest neighbours; the min-fill heuristic eliminates the variable that adds the fewest new edges. Both are computed step by step as edges are added, and both are cheap relative to the inference they schedule. Neither has a useful worst-case guarantee: a greedy choice can commit the order to a width far above the optimum, and examples are constructed in which min-fill performs poorly. The heuristics are nevertheless the standard first move because width differences of a few units change the cost by orders of magnitude.

Two limitations are worth stating explicitly. First, an order that is good for one query variable can be poor for another, since eliminating the query itself is forbidden and its presence widens every factor it touches; a model serving many queries usually pays for a single order wider than any individual query needs. Second, the sum-max interchange that lets one order serve both marginal and maximum a posteriori queries does not extend to mixed queries, where some variables are summed and others maximized and the two operations do not commute. The same factor arithmetic underlies the partition function of undirected models, where every variable is summed out and there is no evidence to restrict anything, which is the subject of Markov Random Fields and the Intractability of the Partition Function.