Last updated Aug 2026 · Methods
The variable elimination algorithm for exact marginal inference in graphical models, and why the order in which variables are eliminated controls its cost.
Once we have a Bayesian network (see the previous note on representation), the natural next question is how to use it: given a factorized joint $p(x_1, \dotsc, x_n)$, compute a marginal such as $p(x_i)$, or a conditional such as $p(x_i \mid x_j = \text{observed})$. The naive approach sums the full joint over every variable except the one we care about,
\[p(x_i) = \sum_{x_1} \cdots \sum_{x_{i-1}} \sum_{x_{i+1}} \cdots \sum_{x_n} p(x_1, \dotsc, x_n),\]which touches every entry of the joint distribution and costs $O(d^n)$ for $d$-valued variables. That is exactly the blowup the factorized representation was meant to avoid, so summing out the full joint directly defeats the purpose.
The factorized form is a product of small local factors, and sums distribute over products whenever a factor does not depend on the variable being summed. That single fact, applied repeatedly, is the entire algorithm. Rather than summing the whole joint at once, we sum out one variable at a time, multiplying together only the factors that actually involve it, and pushing every other factor outside the sum.
Concretely, variable elimination maintains a working set of factors (CPDs and, later, intermediate results). To eliminate a variable $x_k$:
After eliminating every variable except the query variable, what remains is (up to normalization) the marginal we wanted.
Worked example. Reuse the chain from the representation note: infection $I \rightarrow$ temperature $T \rightarrow$ alert $A$, with $p(i, t, a) = p(i)\, p(t \mid i)\, p(a \mid t)$. Suppose we want $p(a)$, marginalizing out $I$ and $T$. Eliminating $I$ first:
\[\tau_1(t) = \sum_{i} p(i)\, p(t \mid i),\]which only touches the two factors that mention $I$, leaving $p(a \mid t)$ untouched. Eliminating $T$ next,
\[p(a) = \sum_{t} \tau_1(t)\, p(a \mid t).\]Each step is a small sum over one variable’s values, not a sum over all three variables jointly. On a chain like this, the intermediate factor $\tau_1$ never has more than two variables in it, which is the whole reason the computation stays cheap.
The cost of variable elimination is governed by the size of the largest intermediate factor produced along the way, not by the number of variables in the original network. Each time we multiply factors together, the result can depend on the union of their variables, so a bad elimination order can produce a large intermediate factor even in a sparse network. The size of the largest factor produced, expressed as one less than its number of variables, is called the induced width of that ordering, and the running time of variable elimination scales exponentially in the induced width, not in $n$.
This has two consequences worth remembering. First, on graphs that are already chain-shaped or tree-shaped, eliminating leaves inward keeps every intermediate factor small, so inference stays linear in the number of variables. Second, on densely connected graphs, no ordering may keep the induced width small, and finding the best possible ordering is itself an NP-hard problem in general, so in practice we rely on heuristics such as always eliminating the variable that currently has the fewest neighbors.
Variable elimination is exact, which is both its strength and its limit: on graphs with large treewidth it becomes intractable regardless of ordering, which is what motivates the approximate inference methods, sampling and variational inference, that this collection of notes will get to next.