Belief Propagation

Imagine you are trying to figure out whether it rained last night. You check the grass (wet), the car (dry, under a cover), and a neighbor's yard (also wet). Each piece of evidence is weak on its own, but together they point somewhere. Now scale that to thousands of interacting variables — a noisy radio channel, a medical diagnosis, a photo you want to sharpen. How do you combine all those weak hints into a single coherent answer?

Belief propagation (BP) is the algorithm that does it. First described by Judea Pearl in 1982 and formalized as the sum-product algorithm in the 1990s, it works on a graph: each node holds a probability distribution over its possible states, and nodes exchange short messages with their neighbors. A message from node A to node B says, in effect, "taking into account everything I know except you, here is what I believe you should believe about yourself."

After a few rounds of message passing, every node multiplies together all the messages it receives and reads off its marginal probability — how likely each of its states is, given all the evidence in the graph. On a tree (a graph with no cycles), this process is provably exact and terminates in a number of steps equal to the diameter of the tree. On a graph with cycles — called a loopy graph — running the same messages anyway gives loopy belief propagation, which has no convergence guarantee but works spectacularly well in practice, powering the best error-correcting codes ever built.

Below is a small chain graph: five nodes, each with two states (0 or 1). The leftmost node is observed (clamped to state 1). Evidence decays as messages travel rightward — but by the end of BP every node has updated its belief about its own state.

Click Step to advance one round of message passing, or Run All to watch convergence. The bar for each node shows P(state = 1 | evidence).

<p class="hint">{{hint}}</p>
<div id="graph-wrap">
  <svg id="graph-svg" viewBox="0 0 460 120" xmlns="http://www.w3.org/2000/svg"></svg>
</div>
<div id="belief-bars"></div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="btn-step">{{btn_step}}</button>
  <button id="btn-run">{{btn_run}}</button>
  <button id="btn-reset" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
#graph-wrap { background: #f0f4f8; border-radius: 10px; padding: 6px 0; margin-bottom: .6rem; }
#graph-svg { display: block; width: 100%; max-width: 460px; height: auto; }
#belief-bars { display: flex; gap: 8px; margin-bottom: .6rem; flex-wrap: wrap; }
.bar-box { flex: 1; min-width: 64px; background: #e8eef3; border-radius: 8px; padding: 6px 8px; }
.bar-label { font-size: .75rem; font-weight: 700; margin-bottom: 3px; color: #1d3557; }
.bar-track { background: #c5cfd8; border-radius: 4px; height: 10px; overflow: hidden; }
.bar-fill { height: 100%; background: #1d6fa0; border-radius: 4px; transition: width .4s; }
.bar-pct { font-size: .73rem; color: #555; margin-top: 2px; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 1.3em; }
.status.done { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice that after just a few steps every node has incorporated the evidence, even those far from the observed node. On this chain (a tree), the result after one left-to-right and one right-to-left sweep is exact. Add a shortcut edge and you have a loop — the messages keep cycling, but they usually still converge close to the right answer.

What is the true cost of inference on a probabilistic graph?

• On trees, BP is exact and efficient. Each message is computed once per edge per direction. Total work is $O(k^{2} \cdot |E|)$ where k is the number of states per variable and |E| is the number of edges — polynomial and fast.
• Exact inference on general graphs is #P-hard. Computing a marginal probability exactly when the graph has cycles is at least as hard as counting the solutions to a SAT formula. There is no known polynomial-time algorithm.
• Loopy BP is a heuristic. Running BP on a cyclic graph (loopy BP) is not guaranteed to converge, and when it does converge, the fixed point may not equal the true marginals. Yet in practice, especially on sparse graphs, it converges quickly and the error is small.
• The turbo-decoding miracle. In 1993, engineers discovered that the turbo codes that had revolutionized satellite communication were implicitly running loopy BP on a cycle graph — and achieving within a hair of the Shannon limit. The same insight later explained LDPC codes. Loopy BP works far better than any theory predicted.
• Belief propagation vs. MCMC. Markov chain Monte Carlo methods give asymptotically exact answers on any graph but converge slowly. BP gives fast approximate answers, and on trees gives exact ones. The two approaches are complementary.

The boundary between tractable and intractable inference runs right through the cycle structure of the graph: trees are easy, general graphs are hard, and loopy BP occupies the fascinating middle ground.

The "pass messages until everyone agrees" pattern solves problems across science and engineering:

• Error-correcting codes: LDPC codes and turbo codes use loopy BP as their decoder. Modern 5G, Wi-Fi 6, and deep-space communication all run BP millions of times per second.
• Computer vision: stereo depth estimation, image segmentation, and denoising are often formulated as Markov random fields solved by BP. Your phone's portrait-mode blur runs something close to this.
• Medical imaging: MRI reconstruction and CT scan denoising use graphical models solved with BP-style inference.
• Probabilistic programming: systems like Infer.NET and Stan compile probabilistic programs into factor graphs and run variants of BP to answer queries.
• Decoding DNA sequences: basecalling in Oxford Nanopore sequencing uses hidden Markov models solved by a variant of BP called the Viterbi / forward-backward algorithm.
• Constraint propagation in AI: belief propagation is a generalization of the arc-consistency algorithm used in constraint solvers — the same idea of propagating local information until global agreement is reached.

Understand BP and you understand the inference engine shared by Bayesian networks, turbo codes, vision systems, and language models.

Belief propagation is built on a simple idea: instead of computing everything at once, let each variable tell its neighbors what it thinks, then update, then repeat. On a tree, this local conversation reaches a globally exact answer. On a graph with loops, it often still works — and that empirical fact unlocked some of the most important coding and vision algorithms ever built.

The deeper lesson is about the structure of inference itself. Easy graphs (trees) and hard graphs (general cycles) sit on opposite sides of a sharp computational divide. BP lives at the boundary — polynomial when it converges, impenetrable when it does not. Understanding that boundary is one of the central open problems connecting probabilistic graphical models to P vs NP and the limits of what algorithms can know.