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. For every message, RxInfer finds the rule by:

  1. Node — which factor you wrote (Normal, Gamma, +, a custom node, ...).
  2. Target — which edge of the factor the message is heading to.
  3. Algorithm — the node's algorithm. Most nodes run under the default; the node of a nonlinear function names its approximation.
  4. Inputs — which messages and marginals arrive on the other edges, and their distribution families. The factorisation your constraints impose decides whether an input is a message, as in BP, or a marginal, as in VMP.

When a conjugate pair meets, the rule is a closed-form update. A Beta prior and a Bernoulli likelihood give an exact Beta posterior:

using RxInfer

@model function coin(y)
    θ ~ Beta(1.0, 1.0)
    for i in eachindex(y)
        y[i] ~ Bernoulli(θ)
    end
end

infer(model = coin(), data = (y = [1.0, 0.0, 1.0, 1.0],)).posteriors[:θ]
Beta{Float64}(α=4.0, β=2.0)

A nonlinear function of a variable, such as sin(x) below, has no closed-form rule. RxInfer represents it with a Delta node, and you choose its approximation with @algorithm:

@model function sensor(y)
    x ~ Normal(mean = 0.0, variance = 1.0)
    z := sin(x)
    y ~ Normal(mean = z, variance = 0.1)
end

result = infer(
    model = sensor(),
    data = (y = 0.5,),
    algorithm = @algorithm(begin
        sin() -> Linearization()
    end),
)
result.posteriors[:x]
NormalWeightedMeanPrecision{Float64}(xi=4.999999999999998, w=10.999999999999996)

When no rule takes the inputs a message needs, as for sin without an approximation, inference stops with an error that names the node and the inputs, and says why each candidate rule does not fit. The Understanding Rules manual explains how rules are found and what decides their inputs. Messages by hand and Variational message passing by hand call the rules of small models one by one, and custom rules can be added without touching the core engine.

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