design

A plan for growing Mycelium from a belief-propagation engine into a general inference engine for hybrid (discrete and continuous) factor graphs. It has seven parts:

  • per-node message rules, each with its own free energy;
  • learning through graphs with mean-field nodes;
  • expectation propagation and mixture reduction as rules;
  • cluster nodes with exact inference inside;
  • plates with shared parameters;
  • structure edits on a live graph;
  • schedules that know the rules.

The first step, the message rule, is done (L-ADR-0009 Factor nodes carry a message rule), and so are the free energy of the hybrid (§1, L-SPEC-005 The Hybrid Free Energy), plates (§2, L-SPEC-006 Plates), rule-aware schedules (§3, L-SPEC-007 Hybrid Schedules) and the EP and mixture-reduction rules (§4, L-SPEC-008 Expectation Propagation and Mixture Reduction) and cluster nodes (§5, L-SPEC-009 Cluster Nodes) and structure edits (§6, L-SPEC-010 Structure Edits).

Sources: original to this vault (design). Hybrid belief propagation and mean field: Riegler, Kirkelund, Manchon, Badiu & Fleury, Merging Belief Propagation and the Mean Field Approximation: A Free Energy Approach, IEEE Trans. Inf. Theory 59(1), 2013. Region free energies and generalised belief propagation: Yedidia, Freeman & Weiss, Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms, IEEE Trans. Inf. Theory 51(7), 2005. Expectation propagation: Minka, UAI 2001. Gaussian-mixture reduction: Runnalls, IEEE Trans. Aerosp. Electron. Syst. 2007. Monte Carlo EM: Wei & Tanner, A Monte Carlo Implementation of the EM Algorithm and the Poor Man’s Data Augmentation Algorithms, JASA 85(411), 1990. Stochastic-approximation EM: Delyon, Lavielle & Moulines, Convergence of a Stochastic Approximation Version of the EM Algorithm, Ann. Statist. 27(1), 1999. code: lib/Mycelium.jl/src/graph.jl, passing.jl, free_energy.jl, schedules.jl, exposure.jl

Bibliography: Riegler et al. 2013 · Yedidia et al. 2005 · Minka 2001 · Runnalls 2007 · Wei & Tanner 1990 · Delyon et al. 1999

Theory (CT-ML wiki): Variational Free Energy · Bayesian Inversion

Where Mycelium stands

Mycelium builds a bipartite graph once (GraphBuilder, build), passes messages by a schedule (step!, sweep!, propagate!), scores the result by the Bethe free energy (bethe_free_energy, counting numbers ), and trains parameters by its gradient at fixed factor beliefs (parameter_step, LP-020), with schedule adjoints for coupled edges. Each factor node now carries a message rule.

What the experiments behind Composing Stochastic Factors ran into, in order of cost:

gapwhere it showedconsequence
only belief propagationE6: a sum node fed by switches sees the other switches’ prior momentsbiased learning, 0.5–0.8 nats; fixed for one node by MeanField()
no free energy for hybrid graphsE7 in the graphparameter_step refused; the M-step was written by hand (resolved by §1, 2026-11-02)
one graph per data pointEM through the hybrid graph14 times slower than the vectorised code (28 s against 2 s); plates and tying added by §2 (2026-11-02), the per-message overhead remains
no mixture entropies at variablesthe Bethe sum with a mixture marginal of degree no free energy for most hybrid graphs
mixtures only collapse to momentsE6, E7the only policy is assumed-density filtering
frozen graphsstructure search over switch wiringsstructure moves rebuild models outside Mycelium
blocks built by handE7: a block of switches is a hand-made factor with outcomeseach block is new code

1. A free energy for every rule (first)

Status: implemented for MeanField() (2026-11-02), L-SPEC-005 The Hybrid Free Energy. The counting numbers are those of Riegler et al. (2013), §III, eqs. (16)–(17), checked against the paper: , mean-field nodes with an average energy and no entropy. The hook is mean_field_energy(factor, marginals, ps, st) rather than a rule argument to local_free_energy. Tests: naive mean field in closed form, Monte Carlo for both average energies, a bound against exact enumeration on a sum of switches, the gradient against central differences, and descent under coordinate updates for naive mean field. The E7 block-graph descent and closed-form M-step checks below were not run as written; the gradient is checked against central differences of the converged free energy instead.

What. Each message rule declares the free energy it is the stationary point of, and the graph sums them. For belief propagation that is Bethe. For the hybrid it is the free energy of Riegler et al. (2013), in which:

  • belief-propagation factors contribute their Bethe terms;
  • mean-field factors contribute only an average energy , with no entropy of their own;
  • the variable entropies are counted from the belief-propagation neighbours.

The exact counting numbers are to be taken from the paper’s statement before implementing; this sketch is not a substitute for it.

Before it: LP-020 (resolved 2026-11-01). The graph gradient held messages, not beliefs, fixed, and was not the gradient of the Bethe free energy. It now holds the beliefs fixed (factor_belief, belief_free_energy). A free energy for the hybrid needs the same for its mean-field nodes, whose beliefs are products of marginals.

Why first. It turns the refusal of L-ADR-0009 Factor nodes carry a message rule into an answer, and with it parameter_step trains hybrid graphs: EM becomes coordinate descent on one objective, inside Mycelium.

How.

  • local_free_energy gets a rule argument. The mean-field term needs only the factor’s expected energy under a product of marginals, which every residual factor can provide from means and covariances.
  • variable_corrections counts belief-propagation degrees.
  • _check_energy_edges then refuses only rules without a free energy.

Test (expected properties, each with an oracle):

  • with every node on belief propagation it is Bethe, unchanged;
  • with every node on mean field it is the naive mean-field free energy, checked by Monte Carlo;
  • on the block graph of E7, sequential updates never increase it;
  • at a fixed point its parameter gradient equals the closed-form M-step.

2. Plates: one graph, many data points, shared parameters

Status: implemented (2026-11-02), L-SPEC-006 Plates, lib/Mycelium.jl/src/plates.md. Tying is general (factor!(...; params)), the plate builder unrolls the template with tied factors, and plate_schedule runs each template task for all replicas at once through factor_messages. Checked against the loop of graphs (marginals, free energy, gradients with three backends) and closed forms, including a shared latent variable and a plate of hybrid graphs. The speed target was not met: for factor analysis the grouped plate is about 6.3 times faster than a loop of prebuilt graphs and 170–240 times slower than the hand-written E-step, after the fixes of a review (graph types that grew with the graph, per-replica work in batched groups; plates.md). The comparison with E7’s vectorised code was not rerun (E7 lives on experiment-qm). A plate is unrolled rather than batched; “factors inside see batched inputs” holds only through factor_messages. A batched message representation, the remaining step to the speed target, was decided in L-ADR-0010 Plates get batched message blocks and implemented on 2026-11-03 (blocks.md): plate edges hold one block per template edge, and the factor-analysis E-step is about 9 times the hand-written one at (0.09 ms against 0.0102 ms, bench/plates.jl), with the free energy and its gradient batched per template factor.

What. A graph template replicated over observations with tied parameters, run as one batched graph: beliefs with a batch dimension, messages computed for all replicas at once, and gradients summed over replicas.

Why. Learning through a graph is the point of the library. Today it means graphs and a loop, and the docs list “no parameter sharing between factor nodes” as a gap. L-SPEC-003 Exposed Parameters and Energy Channels already ties parameters by exposing them as channels on a shared variable. A plate is the batched, structured form of the same thing.

How.

  • Plate(name, n) in the builder, with variables and factors declared inside or outside it.
  • Factors inside see batched inputs. A factor without a batched method falls back to a loop over replicas, so every existing factor works and the fast ones opt in.
  • Parameters outside the plate are shared, and their gradient is the sum over replicas (as for exposed parameters).

Test. A batched graph equals the loop of graphs to rounding, in marginals, free energy and gradients. Speed is measured against the vectorised E-step of E7, with the target of being within a small factor of hand-written code.

3. Schedules that know the rules

Status: implemented (2026-11-03), L-SPEC-007 Hybrid Schedules. hybrid_schedule(g) as described, propagate!(...; criterion = :marginals) comparing marginals by their moments (the default for hybrid schedules), and plate_schedule(g) for hybrid templates. It reproduces the hand-ordered hybrid of lib/Lenticulum.jl/test/switching_constraint.jl to at a tolerance of (the hand schedule needed on messages), and the free energy does not increase along it with components of width . Tutorial 11 uses it.

What. hybrid_schedule(g): belief-propagation subtrees swept inward and outward around each mean-field node, and mean-field nodes updated in turn. It replaces the hand-written task lists of the current tests. Convergence would be measured on beliefs (marginals), not only on messages, because mixtures of very narrow components have a rounding floor in belief_distance.

Test. It reproduces the hand-ordered hybrid of lib/Lenticulum.jl/test/switching_constraint.jl, and the free energy of §1 decreases along it.

4. Expectation propagation and mixture reduction as rules

What. Two more rules:

  • ExpectationPropagation() projects the tilted belief (cavity times factor) onto the target’s family and divides the cavity out. Gaussian division is subtraction in canonical form, so it is defined even for improper sites.
  • Reduce(maxcomponents) lets a node send mixtures reduced to a budget (Runnalls’ merge, reduce_mixture exists) instead of collapsing them to moments, which is the only policy today.

Why.

  • E6 measured Gaussian EP on the additive wiring as a per-point loop: better pair moments at (0.16–0.40 nats), unstable at . As a rule it can be tried on any graph, with damping.
  • Mixture reduction is the standard middle ground between exact mixtures, which grow, and assumed-density filtering, which collapses.

Test.

  • EP on Minka’s clutter problem against the exact posterior in small cases.
  • Reduce on a switching linear chain against exact enumeration, as the budget grows.

Status (2026-11-03): implemented (L-SPEC-008 Expectation Propagation and Mixture Reduction, passing.md, switching.md §9). The rules are ExpectationPropagationRule() (Lenticulum already exports ExpectationPropagation, the likelihood factor’s inversion method) and MixtureReduction(M); a factor opts in to the second with mixture_message, the exact message with mixture inputs expanded, implemented for the linear and switching constraint factors. Both tests above pass: on the clutter problem the rule reaches the fixed point of a hand-written Minka loop to , and belief propagation (exact there, components) gives the posterior to compare with; on a switching chain of five steps the error falls from 0.16 at a budget of one component to at 16, the exact posterior. An EP node’s free energy is counted like belief propagation’s and is stationary at a fixed point (checked numerically); a reduction node has no free energy and is refused. The same day plates of switching factors were batched to the outcome and in their free energy (switching.md §10): a Gaussian-mixture E-step over 1000 points takes 0.10 ms, 2.3 times the closed form, against 9.7 ms edge by edge. Later that day the mixture messages were batched too (mixture blocks, L-SPEC-006 §8), and with them EP on plates: one EP sweep of a latent mixture over 1000 points takes 0.85 ms instead of 44 ms edge by edge.

5. Cluster nodes: exact inference inside, messages outside

What. A node that groups several factors and variables and runs exact inference inside (enumeration of its discrete states, Gaussian elimination of its continuous ones). Outside it looks like one factor, with messages and a closed-form local free energy. This is the region of generalised belief propagation (Yedidia, Freeman & Weiss 2005), restricted to regions small enough to solve exactly.

Why. E7’s remedy, exact blocks of overlapping switches, is a cluster, but today each block is a hand-built SwitchingConstraintFactor with outcomes. A cluster node would make “group these switches” a graph operation. Grouping by overlap (largest of the offsets in the noise metric) becomes a transformation of the graph. A cluster over also gives the closed-form entropy that a mixture variable lacks, which is the cleanest answer to the mixture-entropy gap.

Test. A cluster of binary switches equals the hand-built block factor in messages and free energy. With every factor in one cluster, the graph is exact.

Status (2026-11-03): implemented (L-SPEC-009 Cluster Nodes, cluster.md) for conditionally linear-Gaussian factors: each states itself as a residual with noise and weights (cluster_form; the constraint factors, Gaussian and categorical priors), and the node enumerates the discrete states and eliminates the continuous ones. Both tests pass: three switches in a cluster send the block factor’s messages (to ) and have its local free energy term by term; a switching chain in one cluster has the free energy and the enumerated marginals to . The mixture-entropy gap closes as predicted: with the sum node and the switches in one cluster the additive wiring has a free energy (), where on plain belief propagation it has none. Grouping by overlap is still the caller’s choice.

6. Structure edits on a live graph

What. Adding and removing variables, factors and edges on a built graph, keeping and warm-starting the messages that remain valid (Dynamic Graphs has the analysis). The free energy of §1 scores the edits.

Why. Greedy structure search over switch wirings worked on the branch (four moves scored by BIC, generating structures recovered), but it rebuilt models outside Mycelium, with exact scores.

Test. The moves of structure_switches.jl, done as edits, reproduce its search paths and scores where exact inference is available.

Status (2026-11-03): implemented (L-SPEC-010 Structure Edits, edits.md). A graph is opened as a builder, edited by name and rebuilt; transfer carries the shared edges’ messages. The test in part: the add and remove moves of the additive wiring (), as edits of one graph holding 200 points as tied cluster nodes (exact scores), find the 8-mode grid’s three switches by the branch’s path (lib/Lenticulum.jl/examples/structure_edits.md), in 166 s (with the clusters as a plate, 2026-11-04; 734 s before) against the branch’s 3.6–13 s with closed-form EM. The split and merge moves () followed the same day (lib/Lenticulum.jl/examples/structure_clusters.md): the switch over sums as a graph needs a discrete factor tying each switch’s outcome to the cluster label (TableFactor), and the cluster nodes drop the assignments it rules out. On the branch’s tree the four moves end at , BIC 1 355.84, worse than the generating at 1 299.15; a compound split-and-remove with a data-driven split reaches at 1 299.17 (2026-11-04). Same day: grouping switches by overlap (§5, overlap_groups, switch_overlaps) cuts the error of switch posteriors from 0.092 to 0.031 on eight overlapping switches, but only with E7’s partial sum per block, itself a structure edit (now partial_sums).

6b. Sampling, and what an average must keep

Status: implemented (2026-11-01) in lib/Mycelium.jl/src/sampling.jl (sampling): pins, the Gibbs sampler, the buffer with window and decay filters and a horizon, and the Monte Carlo EM gradient (one inference per sample, then the fixed-belief gradient of LP-020). Building it exposed LP-020 The fixed-message parameter gradient is not the free-energy gradient.

What. Passing points instead of beliefs: a Gibbs sampler over chosen variables. The switches are sampled; the continuous variables between them are integrated out exactly by belief propagation with the sampled ones pinned (Rao-Blackwellisation). Beliefs then never grow, each update is local, and learning is Monte Carlo EM (Wei & Tanner 1990): the parameter gradient is the average, over posterior samples, of the pinned graph’s free-energy gradient. With all sampled variables pinned and the rest a tree, that free energy is .

Requirement: averaging a structured energy. A vector energy averaged the wrong way loses exactly the structure it was made to keep. Every sampling or point-passing rule, and every report built on samples, must satisfy the following.

  1. Scalarise each sample, then average, one graded component at a time. Never average a raw residual vector across samples or outcomes before its scalarisation: residuals of different samples cancel (two outcomes with right-hand sides average to a zero residual although neither constraint holds). This is L-ADR-0003’s two levels, applied to samples.
  2. Report the mean and the full covariance of each factor’s residual vector. For a squared-norm scalarisation they are exact sufficient statistics, , so the trace term, the Jensen gap, stays visible and checkable. When a sample carries a Gaussian part (Rao-Blackwellisation), the covariance is combined by the law of total covariance: the average of the within-sample covariances plus the covariance of the sample means.
  3. A diagonal covariance is a declared reduction, valid only for a diagonal weighting. With a full noise matrix the off-diagonal covariances enter the trace.
  4. Nonlinear scalarisations need the samples themselves. Mean and covariance are not sufficient for robust or point-dependent scalarisations (L-ADR-0007), so the samples are kept.

Interface: samples are kept, filtered, and forgotten.

  • A sample buffer keeps each sample’s points, its graded local energies, the residual moments of every factor that has them, and the parameter step at which it was drawn.
  • A filter turns the buffer into weights. A window keeps the last samples with equal weight. An exponential filter weighs a sample draws old by ; with a decreasing step size this is stochastic-approximation EM (Delyon, Lavielle & Moulines 1999).
  • Forgetting: after horizon parameter steps a sample is dropped, since samples drawn under old parameters bias the gradient.
  • Averages, residual moments and gradients are always computed from the buffer under the filter’s weights. The gradient re-runs belief propagation at the current parameters with each stored sample pinned.

Test.

  • The Gibbs conditional is exact (frequencies against enumeration).
  • With the buffer holding every configuration at its exact posterior weight, the gradient equals the gradient of the exact , and the residual moments equal the enumerated ones.
  • The filters’ weights and the forgetting are checked deterministically.

7. Factors that follow from this (Lenticulum)

These belong to Lenticulum, not to Mycelium, but the plan depends on them:

  • the general switching factor (per-outcome , ; Switching Constraint Factors §8);
  • the directed switching kernel for chains;
  • mean-field rules for the remaining residual factors, GaussianFactor and NonlinearFactor (linearised).

Order

  1. The free energy of every rule (§1). It unblocks learning through hybrid graphs.
  2. Plates (§2). They make that learning affordable.
  3. Rule-aware schedules (§3). They are small, and §1’s tests need them.
  4. EP and reduction rules (§4), then cluster nodes (§5). They widen what the graph can approximate.
  5. Structure edits (§6). They need §1’s score.

Sampling (§6b) is independent of the others and is implemented first, by Daniel’s choice (2026-11-01): it needs no new free energy, because the pinned graph’s Bethe free energy is exact.

Each part gets an LP or an L-SPEC when it starts, with its tests written against the oracles named above.

Related: L-ADR-0009 Factor nodes carry a message rule, Composing Stochastic Factors, Switching Constraint Factors, Bethe Free Energy, Loopy Message Passing, Dynamic Graphs, Schedules