Introduction

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.

Watch Messages Settle

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">A chain of 5 nodes. Node 0 is <b>observed</b> (clamped to state 1).
    Each edge has a compatibility: neighboring nodes prefer to <b>agree</b> (coupling = 0.8).
    Click <b>Step</b> to advance one round of message passing, or <b>Run All</b> to converge.</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">Round 0 โ€” click Step to start.</div>
<div class="btns">
  <button id="btn-step">Step</button>
  <button id="btn-run">Run All</button>
  <button id="btn-reset" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// โ”€โ”€ Belief Propagation on a chain of N nodes โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
// Each node has 2 states: {0, 1}.
// Node 0 is observed: phi[0] = [0, 1] (clamped to state 1).
// All other nodes have uniform prior: phi[i] = [0.5, 0.5].
// Edge compatibility: psi(a,b) = agree ? COUPLE : (1-COUPLE)
//   where COUPLE = 0.8  (strong tendency for neighbors to match).
// Messages: mu[i->j][state_j] = sum_{state_i} phi[i][state_i] * psi(state_i,state_j)
//                                * product of incoming messages to i from k!=j
// Beliefs: bel[i][s] proportional to phi[i][s] * product of all incoming msgs to i
// On a chain (tree), two sweeps (left->right then right->left) give the exact answer.

const N = 5;
const COUPLE = 0.8;  // compatibility when states match

// Node evidence (likelihood)
const phi = Array.from({length: N}, (_, i) => i === 0 ? [0.0, 1.0] : [0.5, 0.5]);

// Messages: msg[i][j] = message from node i to node j, length-2 array
// Edges: i -- i+1 for i in 0..N-2
function makeMessages() {
  const m = {};
  for (let i = 0; i < N-1; i++) {
    m[`${i}->${i+1}`] = [0.5, 0.5];
    m[`${i+1}->${i}`] = [0.5, 0.5];
  }
  return m;
}

// psi(a, b): compatibility factor
function psi(a, b) { return a === b ? COUPLE : (1 - COUPLE); }

// Normalize a length-2 array
function norm(v) { const s = v[0]+v[1]; return s < 1e-12 ? [0.5,0.5] : [v[0]/s, v[1]/s]; }

// Compute belief for node i given current messages
function belief(i, msgs) {
  let b = [phi[i][0], phi[i][1]];
  if (i > 0) {
    const mu = msgs[`${i-1}->${i}`];
    b = [b[0]*mu[0], b[1]*mu[1]];
  }
  if (i < N-1) {
    const mu = msgs[`${i+1}->${i}`];
    b = [b[0]*mu[0], b[1]*mu[1]];
  }
  return norm(b);
}

// One full sweep: left->right then right->left
function sweep(msgs) {
  const next = makeMessages();
  // Left to right
  for (let i = 0; i < N-1; i++) {
    // msg from i -> i+1: exclude incoming from i+1
    let incoming_i = [1, 1];
    if (i > 0) { const mu = msgs[`${i-1}->${i}`]; incoming_i = [mu[0], mu[1]]; }
    const newMsg = [0, 0];
    for (let sj = 0; sj < 2; sj++) {
      for (let si = 0; si < 2; si++) {
        newMsg[sj] += phi[i][si] * incoming_i[si] * psi(si, sj);
      }
    }
    next[`${i}->${i+1}`] = norm(newMsg);
  }
  // Right to left (use newly computed left->right messages)
  for (let i = N-1; i > 0; i--) {
    // msg from i -> i-1: exclude incoming from i-1
    let incoming_i = [1, 1];
    if (i < N-1) { const mu = next[`${i+1}->${i}`]; incoming_i = [mu[0], mu[1]]; }
    const newMsg = [0, 0];
    for (let sj = 0; sj < 2; sj++) {
      for (let si = 0; si < 2; si++) {
        newMsg[sj] += phi[i][si] * incoming_i[si] * psi(si, sj);
      }
    }
    next[`${i}->${i-1}`] = norm(newMsg);
  }
  return next;
}

let msgs = makeMessages();
let round = 0;
const MAX_ROUNDS = 6;

// โ”€โ”€ Rendering โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
const CX = [40, 135, 230, 325, 420];
const CY = 60;
const R = 28;

function renderSVG() {
  const svg = document.getElementById('graph-svg');
  svg.innerHTML = '';
  // Edges
  for (let i = 0; i < N-1; i++) {
    const line = document.createElementNS('http://www.w3.org/2000/svg','line');
    line.setAttribute('x1', CX[i]); line.setAttribute('y1', CY);
    line.setAttribute('x2', CX[i+1]); line.setAttribute('y2', CY);
    line.setAttribute('stroke', '#9fb8cc'); line.setAttribute('stroke-width', '2.5');
    svg.appendChild(line);

    // Arrow labels for messages
    const fwd = msgs[`${i}->${i+1}`];
    const bwd = msgs[`${i+1}->${i}`];
    const mx = (CX[i]+CX[i+1])/2;
    function mkTxt(txt, x, y, col) {
      const t = document.createElementNS('http://www.w3.org/2000/svg','text');
      t.setAttribute('x', x); t.setAttribute('y', y);
      t.setAttribute('font-size', '10'); t.setAttribute('fill', col);
      t.setAttribute('text-anchor', 'middle'); t.setAttribute('font-family', 'ui-monospace,monospace');
      t.textContent = txt; svg.appendChild(t);
    }
    mkTxt(`โ†’ ${fwd[1].toFixed(2)}`, mx, CY-10, '#1d6fa0');
    mkTxt(`โ† ${bwd[1].toFixed(2)}`, mx, CY+22, '#7b3fa0');
  }
  // Nodes
  for (let i = 0; i < N; i++) {
    const bel = belief(i, msgs);
    const fill = i === 0 ? '#e63946' : `rgb(${Math.round(29+(140*(1-bel[1])))},${Math.round(111+(30*bel[1]))},${Math.round(160*(1-bel[1]+0.3))})`;
    const circle = document.createElementNS('http://www.w3.org/2000/svg','circle');
    circle.setAttribute('cx', CX[i]); circle.setAttribute('cy', CY);
    circle.setAttribute('r', R); circle.setAttribute('fill', fill);
    circle.setAttribute('stroke', '#fff'); circle.setAttribute('stroke-width', '2');
    svg.appendChild(circle);
    const txt = document.createElementNS('http://www.w3.org/2000/svg','text');
    txt.setAttribute('x', CX[i]); txt.setAttribute('y', CY+5);
    txt.setAttribute('font-size', '12'); txt.setAttribute('fill', '#fff');
    txt.setAttribute('text-anchor', 'middle'); txt.setAttribute('font-weight', 'bold');
    txt.setAttribute('font-family', 'ui-monospace,monospace');
    txt.textContent = i === 0 ? 'obs' : bel[1].toFixed(2);
    svg.appendChild(txt);
    // Node label below
    const lbl = document.createElementNS('http://www.w3.org/2000/svg','text');
    lbl.setAttribute('x', CX[i]); lbl.setAttribute('y', CY+R+14);
    lbl.setAttribute('font-size', '11'); lbl.setAttribute('fill', '#555');
    lbl.setAttribute('text-anchor', 'middle');
    lbl.textContent = `X${i}`;
    svg.appendChild(lbl);
  }
}

function renderBars() {
  const wrap = document.getElementById('belief-bars');
  wrap.innerHTML = '';
  for (let i = 0; i < N; i++) {
    const bel = belief(i, msgs);
    const pct = Math.round(bel[1]*100);
    const box = document.createElement('div'); box.className = 'bar-box';
    box.innerHTML = `<div class="bar-label">X${i}${i===0?' (obs)':''}</div>
      <div class="bar-track"><div class="bar-fill" style="width:${pct}%"></div></div>
      <div class="bar-pct">P(1) = ${(bel[1]).toFixed(3)}</div>`;
    wrap.appendChild(box);
  }
}

function setStatus(t, cls='') {
  const s = document.getElementById('status');
  s.textContent = t; s.className = 'status ' + cls;
}

function render() { renderSVG(); renderBars(); }

function step() {
  if (round >= MAX_ROUNDS) { setStatus(fmt('Converged after %round% rounds.', { round: round }), 'done'); return; }
  msgs = sweep(msgs);
  round++;
  render();
  const b1 = belief(1, msgs)[1];
  setStatus(fmt('Round %round%: X1 P(1) = %b1%%v%', { round: round, b1: b1.toFixed(3), v: round >= MAX_ROUNDS ? ' โ€” converged.' : '' }), round >= MAX_ROUNDS ? 'done' : '');
}

function runAll() {
  if (round >= MAX_ROUNDS) return;
  const id = setInterval(() => {
    step();
    if (round >= MAX_ROUNDS) clearInterval(id);
  }, 350);
}

function reset() {
  msgs = makeMessages(); round = 0;
  render();
  setStatus('Round 0 โ€” click Step to start.');
}

document.getElementById('btn-step').addEventListener('click', step);
document.getElementById('btn-run').addEventListener('click', runAll);
document.getElementById('btn-reset').addEventListener('click', reset);

render();
// Log exact marginals for verification
// After convergence (2 sweeps), expected P(X_i=1) should decay from 1.0 at X0.
// For the chain with COUPLE=0.8: P(Xi=1) = 0.8^i * norm factor approximately.
console.log('Initial beliefs (uniform except X0):',
  Array.from({length:N},(_,i)=>belief(i,msgs)[1].toFixed(4)));
Result
Console

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.

The Real Complexity

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(k2โ‹…โˆฃEโˆฃ)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/belief-propagation/Content licensed under CC BY-NC 4.0.