implementation

The message store keeps both directions on every edge. Pooling and public overlap rules support categorical and mixture beliefs, with explicit exclusions. Likelihood potentials add log-densities and reweight explicit particles.

Sources: code: messages.jl, gaussian.jl, ../test/overlap.jl

Theory (CT-ML wiki): Bayesian Inversion

Implements: the message store, belief pooling, and both exclusion principles. Theory: Messages are Inversions.

The store keeps both directions per edge

to_variable[e] and to_factor[e], plus nothing for “not yet computed” — which is distinct from “computed and uninformative” (TrivialBelief()). Keeping both directions separately is the alternative to dividing out, which a density representation would do and which is not available for general beliefs.

excluded_marginal recomputes the product over the other edges rather than dividing the full marginal by the skipped message. Division needs densities and is numerically fragile; recomputation costs per message and is always defined.

Both exclusions

  1. Variable side — excluded_marginal: omits . Without it a factor’s own previous claim returns to it as independent evidence and the belief becomes exponentially over-confident.
  2. Factor side — in step!: when computing , the incoming message on that same edge is excluded from the observed channels.

The second was not in the design; the test suite found it. See Mycelium §1.

Implementation difficulties

1. combine is deliberately partial (sample–potential pooling is resolved)

caseresult
TrivialBelief with anythingthe other one
agreeing DiracBeliefsthat Dirac
disagreeing DiracBeliefsthrows
DiracBelief with anythingthe Dirac
CategoricalBelief with CategoricalBeliefelementwise product, renormalised; disjoint supports throw
SampleBelief with a belief that has belief_logdensitythe samples, reweighted (warns if the effective sample size collapses)
potential with potentialLogPotentialBelief whose log-density is the sum
SampleBelief with a potentialimportance reweighting via belief_logdensity, without resampling
Gaussian, categorical (with or without labels), or mixture with a potentialthrows: no exact arbitrary-callable product rule; supply particles or a richer potential type
MixtureBelief with another supported beliefcomponentwise products, weights scaled by each overlap (combine_with_overlap rules: categorical here, Gaussian in Mycelium’s gaussian.jl)
two SampleBeliefsthrows: neither has a density
anything elsethrows informatively

The sample and mixture rules live in the catch-all method, not in new two-argument methods: any (Specific, Abstract) method next to the existing (Abstract, Dirac) and (Abstract, Trivial) ones would create dispatch ambiguities (§1b), whereas the catch-all is only reached when no specific rule applies.

Disagreeing Diracs throw rather than pick one because two hard clamps in contradiction is a wiring error, not a numerical one, and the error message says how to express the intended thing instead (a finite Observed precision — a soft clamp, per Channels and Polarity).

Two SampleBeliefs still cannot be pooled: neither has a density. A sample belief can now be pooled with anything that has one (Gaussian, categorical, mixture) by importance reweighting, and moment_match (in Lenticulum) projects samples onto a Gaussian, after which two particle sets can meet. The two concerns of §1c below are handled as follows: the effective sample size is computed on every reweighting and a collapse warns (below 10 for large sample sets, below 1 % of the samples for medium ones, below 1.5 for tiny ones); and the missing idempotence is the correct behaviour of a product (pooling the same evidence twice counts it twice), so it is documented, not prevented. See Belief Algebra, Categorical Belief, Mixture Belief.

1b. The unit law was unreachable for the one type that can be pooled

The three unit-law methods were originally

combine(::TrivialBelief, b) = b
combine(a, ::TrivialBelief) = a
combine(a::TrivialBelief, ::TrivialBelief) = a

with the untyped second argument covering “anything”. Against the catch-all at the bottom of the file,

combine(a::AbstractBelief, b::AbstractBelief) = throw(ArgumentError(...))

the pair (TrivialBelief, GaussianBelief) matches both (TrivialBelief, Any) and (AbstractBelief, AbstractBelief), and neither is more specific than the other: the first is narrower on the left, the second on the right. Julia reports a MethodError: combine(...) is ambiguous, thrown from inside excluded_marginal on the first sweep — so pooling a message with the accumulator’s TrivialBelief seed failed for GaussianBelief, the only belief type in the project that combine can actually pool.

The fix is to restate the unit law one rung down, at AbstractBelief:

combine(::TrivialBelief, b::AbstractBelief) = b
combine(a::AbstractBelief, ::TrivialBelief) = a

which is strictly more specific than the catch-all, so the unit always wins. The untyped methods stay, for payloads that are not AbstractBeliefs at all.

This failed loudly only by luck

The catch-all throws. Had it returned something — a TrivialBelief, say, or a “best effort” pooling — the ambiguity would have been resolved silently in whichever order the methods happened to be defined, and marginal would have quietly dropped every message pooled against the seed. A catch-all that throws is what turned a specificity bug into a stack trace.

The general lesson for this file: every rule in the table above is stated at two different levels of the type hierarchy (Any for foreign payloads, AbstractBelief for beliefs), and a rule stated at only one of them is a latent ambiguity waiting for the first downstream belief type. Adding a belief type is not what exposes it — adding a belief type that gets pooled is.

Caught by The Linear Gaussian Chain and by the two-factor model in Lenticulum’s test suite, not by this package’s own tests at the time: those tests used DiracBelief and TrivialBelief only, and every one of those pairs had an explicit method. The current suite also checks structured beliefs, particle weighting, and callable potentials. A package whose central operation is “combine two beliefs” cannot test that operation with one belief type.

1c. A density RATIO is enough, and a classifier estimates one

The oldest sample-pooling blocker is resolved when one operand supplies a potential. AdversarialFactors.RatioFactor emits LogPotentialBelief(x -> log r(x)); the existing belief_logdensity reweighting path applies it to a particle cavity. Two such messages add their log-potentials. No density of the particle cloud is required, and no density estimator is invented for two clouds.

Mycelium reports severe ESS collapse. Reapplying the same evidence multiplies it twice; products are not idempotent, and this does not violate associativity or commutativity. test/runtests.jl checks both orders and parenthesisations for two ratio potentials on one particle variable, including matrix and vector-of-vectors particles. AdversarialFactors’ test/conformance.jl checks the same algebra through a graph with two RatioFactors.

An arbitrary callable does not specify an exact Gaussian or mixture posterior. This implementation also refuses categorical products, including labeled ones, rather than assuming how labels map to evaluation points. Richer likelihood subtypes can supply those rules later.

1d. Stated as a typing problem

Partiality is the shape of the difficulty, not an incidental feature of it. The set of pairs combine accepts is a relation on types, checked dynamically by method lookup and an error branch — and the ambiguity bug recorded in §1b is what happens when symmetric multiple dispatch is asked to resolve a partial binary operation on a type lattice.

A discipline that indexed beliefs by what they support would turn combine(SampleBelief, SampleBelief) from a runtime throw into a compile-time refusal, and would make the conditions on a new belief type explicit rather than discovered by the first crash. See The Type Discipline of a Factor Graph §3.1.

1e. There is a Julia package that already does this

IncrementalInference.jl (with Caesar.jl and KernelDensityEstimate.jl) performs nonparametric belief propagation: beliefs as kernel density estimates, with the product of belief functions estimated by multiscale Gibbs sampling, over a Bayes/junction tree.

That is this gap, closed, in production robotics — by a third route, neither the density-ratio one of §1c nor the NCE one of §1d. Anything built here should be measured against it first. See Related Julia Projects §6.

2. combine is not associative-by-construction, and the fold assumes it is

marginal folds combine left to right over the incident edges. Product-of-densities is associative and commutative, so this is fine in principle; but the implemented DiracBelief dominance rule is only associative because Dirac-vs-Dirac throws on disagreement. Add a belief type whose combination is order-sensitive (a moment-matched Gaussian projection, say) and marginal silently becomes order-dependent.

The LP-016 tests check particle/potential associativity and commutativity against explicit normalised weights; these are algebraic checks on the finite support, not guarantees about importance-sampling accuracy.

3. belief_distance returns Inf, not 0, for unknown pairs

Deliberate. An unverifiable residual makes propagate! run to maxsweeps and report that convergence could not be checked. Returning 0 would be more convenient and would produce silent false “converged” reports. A wasted sweep is much cheaper than a wrong answer.

LogPotentialBelief returns distance zero only when the two wrapped callables are identical (===), and Inf otherwise. Other potential subtypes retain the conservative fallback. This does not attempt to recognise functions equal up to a constant, and assumes captured mutable data is not changed while a message is in use.

4. Damping is often a no-op

damp returns the new message unchanged when can_damp is false. This includes potentials: normalisation is unknown, so a convex mixture has no chosen interpretation. Schedules can inspect can_damp, but currently do not report unsupported damping automatically. Earlier notes overstated that reporting. Numeric Diracs, categorical beliefs on the same support, samples on identical particles, Gaussians, and mixtures with matching components have their existing damping rules.

5. Vector{Any} for the store

Messages are heterogeneous (different belief types per edge), so the store is Vector{Any} and every access is a dynamic dispatch. Correct and simple; the alternative — a per-edge type-parameterised store — would make MessageStore depend on the whole graph’s belief types, which are not known until the first sweep. Probably the right trade at this scale, but it means message passing will not be fast, and pretending otherwise would be misleading.

Measured, on the same access pattern with and without concrete types: Vector{Any} is 130× slower and turns an allocation-free loop into 19 MB. And a second, separate finding sits next to it — a sweep is quadratic in the number of factors, because ps is a NamedTuple looked up with a runtime Symbol, which is linear in its field count. Both are in Parallelism and Compilation §2, with the benchmark in bench/scaling.jl.

Related: Messages are Inversions, passing, Loopy Message Passing, Parallelism and Compilation, The Linear Gaussian Chain

Public overlap rule

combine_with_overlap(c,d) returns the pooled belief and log ∫p_c p_d. Categorical pairs use a log-sum-exp; disjoint support returns (c,-Inf) as a placeholder, and mixture pooling drops that zero-mass pair. Gaussian pairs are implemented in Mycelium’s gaussian.jl, require proper c, and allow improper d up to an additive constant depending on d alone. There is no extra log_overlap wrapper: callers needing only the mass use last. test/overlap.jl checks categorical sums, Gaussian convolution, and improper Gaussian overlap differences against closed forms. Homotopy branch weighting uses this public rule, as does mixture pooling’s availability check.

LP-011 implementation (2026-10-27)

Read-only message operations accept an internal abstract store, allowing immutable replay tuples alongside the ordinary mutable MessageStore. Marginal and excluded-marginal reads enforce detach even on externally populated stores. A Gaussian belief covariance ChainRules rule uses the inverse-matrix derivative, avoiding differentiation through a mutating Cholesky inverse.

Evidence: lib/MyceliumLearning.jl/test/gradient_couplings.jl and test/gradient_couplings.jl. API, mixed Jacobians, costs and unsupported combinations are specified in gradient_couplings and L-SPEC-002 Stop Gradient.

LP-018 finite particle weights (2026-10-29)

The particle-distance normaliser divides weights by their maximum before summing. Finite weights whose raw sum overflows now give the same convergence residual as ordinary weights in the same proportions. The existing all-zero fallback is unchanged; importance reweighting already normalises max-shifted log weights. Evidence: test/lp018.jl, “LP-018.9 particle distance normalises finite overflowing weights”, checks equal weights and the independent total variation 1/6 between (2/3,1/3) and (1/2,1/2), with vector and tuple weights. Both original vector assertions failed in Mycelium-final.log before this fix. Scaling uses non-mutating division so immutable weight containers remain supported.

Block rows in the store (2026-11-03)

MessageStore’s fields to_variable and to_factor are EdgeMessages rather than Vector{Any}. They index the same way; a graph with plates gives each template edge a block row that can hold one BeliefBlock for all replicas, read edge by edge as views (blocks.md). has_to_variable and has_to_factor ask the storage (_isset) instead of building the view.

Two improper mixture components (2026-11-03)

combine_with_overlap for a Gaussian pair now also takes two improper operands: their product is exact in canonical form (gaussian.md, “Products of improper components”). An improper c with a proper d still throws; _mixture_product puts the proper operand first, as before. The LP-019 test that combine(site, mix) no longer throws keeps passing.

A point against a categorical belief (2026-11-04, LP-023)

combine(DiracBelief(k), b::CategoricalBelief) returned the point whatever b said. A point of probability zero under b is a contradiction (zero mass), so it now throws, as two different points do. Test: Mycelium test/runtests.jl.