GitHub

Message Passing

Message passing is the algorithm RxInfer uses to turn a factor graph into concrete posterior distributions. Instead of ever touching the full joint, nodes exchange small local summaries — messages — along edges, and the posterior over each variable emerges from combining them.

The intuition is simple: every message from a factor towards a variable is a local answer to the question "given everything I know about the rest of the graph, what do I think this variable looks like?".

Belief Propagation (BP)

The classical message passing algorithm is belief propagation, also known as the sum-product algorithm. A message from factor $f$ toward variable $x$ integrates $f$ against all other incoming messages:

\[\mu_{f \to x}(x) \;=\; \int f(x, y, z)\, \mu_{y \to f}(y)\, \mu_{z \to f}(z)\, \mathrm{d}y\, \mathrm{d}z\,.\]

The message back from $x$ collects beliefs from all other factors attached to $x$. The marginal posterior is then the normalised product of incoming messages at a variable node:

\[q(x) \;=\; \frac{1}{Z} \prod_{f \in \text{nb}(x)} \mu_{f \to x}(x)\,.\]

On tree-shaped graphs this procedure is exact: a single forward-backward sweep produces the true posterior marginals. On graphs with cycles, iterating the same updates — loopy BP — yields a principled approximation that is often excellent in practice.

Variational Message Passing (VMP)

Once your model has loops, non-conjugate factors, or you deliberately impose simplifying assumptions, exact BP is no longer available. RxInfer's primary algorithm is variational message passing, which turns inference into minimisation of the Bethe Free Energy — the variational objective described in full on the Variational Inference page.

Under a mean-field-style factorisation, the factor-to-variable message becomes

\[\mu_{f \to x}(x) \;=\; \exp\!\left( \int q(y)\, q(z)\, \log f(x, y, z)\, \mathrm{d}y\, \mathrm{d}z \right)\,,\]

where $q(y)$ and $q(z)$ are the current marginal beliefs about the neighbouring variables. Two things make VMP attractive:

  1. BP is a special case: with no extra factorisation constraints, VMP reduces to ordinary belief propagation.
  2. Locality: each update still depends only on immediate neighbours, so the reactive execution model scales naturally.

Which factorisation you get — full mean-field, structured, or none at all — is controlled by constraints specifications.

Automatic rule selection

You never choose a message update rule by hand. RxInfer uses Julia's multiple dispatch to pick the right rule for every edge based on:

  1. Node type — which factor you wrote (Normal, Gamma, a custom deterministic node, ...).
  2. Outgoing edge — which argument of the factor the message is heading towards.
  3. Incoming message types — the distribution families arriving on the other edges.
  4. Factorisation assumption — whether the surrounding constraints require a BP-style or VMP-style rule.

When a conjugate pair is detected, the dispatched rule is a closed-form analytical update. Non-conjugate combinations fall back to numerical or approximate rules. The Understanding Rules manual explains exactly how this machinery works under the hood, and custom rules can be added without touching the core engine.

# Conjugate — dispatches to an exact analytical Beta update
θ ~ Beta(1.0, 1.0)
y ~ Bernoulli(θ)

# Non-conjugate — dispatches to a variational approximation
λ ~ Normal(mean = 0.0, variance = 1.0)
y ~ Poisson(exp(λ))

Reactive scheduling

Traditional inference engines compile an explicit schedule (forward pass, backward pass, sweep order, ...) before inference begins. RxInfer does not. Every node owns a reactive stream of messages, and updates fire whenever their inputs change. The net effect:

  • New observations trigger only the messages that actually depend on them.
  • The graph is its own scheduler — no global plan to build or maintain.
  • Streaming and real-time inference come for free.

The Reactive Programming concept page expands on this execution model.

For deeper understanding