Skip to content

Lazy Symbolic Bayesian Inference: A Compiler for Junction Trees

Most exact-inference libraries treat junction-tree calibration as a numerical procedure: build the tree, run two passes of message passing, return the marginals. Change the evidence and the whole pass runs again. PyBayes treats it as a compiler problem instead. The junction tree is built once, then the calibration is reified as a symbolic computation DAG of typed algebraic terms. A parallel heap of torch.Tensor thunks hangs off that DAG, indexed by the same identifiers, evaluated on demand and invalidated selectively when evidence changes. The library is PyBayes (github.com/dlewissandy/pybayes).

The running example is the Asia network (Lauritzen and Spiegelhalter 1988), eight binary variables connected by the familiar diagnostic DAG. PyBayes runs the standard junction-tree pipeline (moralize, triangulate, extract cliques) and delegates it to NetworkX. For Asia this gives six cliques in a tree of treewidth two:

flowchart LR
    C5["C5<br/>Tub, Asia"]
    C4["C4<br/>Tub, LungC, TbOrCa"]
    C3["C3<br/>Bronc, LungC, TbOrCa"]
    C2["C2<br/>Bronc, LungC, Smoker"]
    C1["C1<br/>Bronc, Dysp, TbOrCa"]
    C0["C0<br/>XRay, TbOrCa"]
    C5 ---|Tub| C4
    C4 ---|"LungC, TbOrCa"| C3
    C3 ---|"Bronc, LungC"| C2
    C3 ---|"Bronc, TbOrCa"| C1
    C1 ---|TbOrCa| C0

For the standard pipeline that turns the DAG into this tree (moralization, triangulation, junction-tree extraction), and for the classical Hugin / Shafer–Shenoy message-passing schedules that calibrate it, see the companion post Yet another primer on Bayes nets.

Conventional libraries calibrate this tree numerically. Each message is a concrete table. Each multiplication runs when the schedule reaches it, and each intermediate is written into a clique. When evidence changes, those potentials are stale, and the standard remedy is to reset everything to priors and re-run the full collect/distribute pass. The whole calibration is recomputed from scratch.

Madsen and Jensen's lazy propagation (1999) made one move away from this: keep lazy factor lists at each separator, and defer their multiplication until a query demands a value. That pulls some work out of message passing into query time, but the factors themselves are still numerical and still tied to specific cliques.

PyBayes makes the more aggressive move. The calibration is built as a content-addressed symbolic DAG of typed terms, with no numerical content. A separate heap of torch.Tensor thunks hangs off that DAG, keyed by the same identifiers. The two halves communicate only through the identifiers. Hash-consing of intermediates across queries and Bayes-ball-driven selective invalidation of the evaluation cache both follow from that separation; neither is available if all you do is delay multiplication on numerical factors.

The symbolic DAG

PyBayes runs the same calibration symbolically. Each quantity that message passing would produce becomes a typed algebraic term with no numerical content. The rest of this section is a compiler pipeline: the grammar below is the IR's syntax, the equational laws define a canonical form via term rewriting, and the FormulaStore performs common-subexpression elimination by hash-consing on that canonical form. The numerical evaluator is a separate stage that consumes the IR.

The grammar:

\[ \begin{aligned} t \;\;::=\;\;& \mathbf{1} && \text{unit} \\ \;\;\mid\;\;& \Phi_X && \text{node potential (CPT for } X \text{)} \\ \;\;\mid\;\;& \varepsilon_X && \text{evidence function on } X \\ \;\;\mid\;\;& \textstyle\prod(t_1,\,\ldots,\,t_n) && \text{product} \\ \;\;\mid\;\;& \Sigma_S(t) && \text{marginalize to separator } S \\ \;\;\mid\;\;& \beta_D(t) && \text{reorder (braid) to domain } D \\ \;\;\mid\;\;& \norm(t) && \text{log-normalize} \\ \;\;\mid\;\;& \divop(t_1,\,t_2) && \text{divide} \\ \;\;\mid\;\;& \ref(t) && \text{named indirection} \end{aligned} \]

Terms come with an equational theory, presented here as denotational equations where \(\sem{\cdot}\) maps a term to its log-probability tensor.

Reference.

\[ \sem{\ref(\mathbf{1})} = \sem{\mathbf{1}} \qquad \sem{\ref(\ref(t))} = \sem{\ref(t)} \]

Product.

\[ \begin{aligned} \sem{\textstyle\prod(\,)} &= \sem{\mathbf{1}} &\qquad \sem{\textstyle\prod(t)} &= \sem{t} \\ \sem{\textstyle\prod(\mathbf{1},\,\bar t)} &= \sem{\textstyle\prod(\bar t)} & \sem{\textstyle\prod(\textstyle\prod(\bar s),\,\bar t)} &= \sem{\textstyle\prod(\bar s,\,\bar t)} \end{aligned} \]

Marginal.

\[ \begin{aligned} \sem{\Sigma_S(\mathbf{1})} &= \sem{\mathbf{1}} &\qquad \sem{\Sigma_\varnothing(t)} &= \sem{\mathbf{1}} \\ \sem{\Sigma_S(t)} &= \sem{t} && \text{when } \vars(t) \subseteq S \\ \sem{\Sigma_S(\Sigma_T(t))} &= \sem{\Sigma_{S \cup T}(t)} \\ \sem{\Sigma_S(\beta_D(t))} &= \sem{\beta_{D'}(\Sigma_{S \cap \dom(t)}(t))} \end{aligned} \]

Braid.

\[ \sem{\beta_D(t)} = \sem{t}\;\;\text{when } D = \dom(t) \qquad \sem{\beta_D(\ref(t))} = \sem{\beta_D(t)} \]

Divide.

\[ \sem{\divop(t,\,\mathbf{1})} = \sem{t} \qquad \sem{\divop(t,\,t)} = \sem{\mathrm{const}(0)} \]

Normalize.

\[ \begin{aligned} \sem{\norm(\norm(t))} &= \sem{\norm(t)} &\qquad \sem{\norm(\ref(t))} &= \sem{\norm(t)} \\ \sem{\norm(\mathrm{const}(c))} &= \sem{\mathrm{const}(0)} & \sem{\norm(\beta_D(t))} &= \sem{\beta_D(\norm(t))} \end{aligned} \]

The implementation has seventeen rewrite rules, each oriented left-to-right from one direction of one of these equations. They run at insertion time as a fixed-point pass and canonicalise every incoming term before the FormulaStore assigns it an identifier.

The canonical form of a term is the steady state of the rewrite system: the term has reached canonical form when no rule applies. Two terms are defined as equivalent (and hash-consed to the same identifier) when they reduce to the same steady state. The rule set is the equivalence relation. Adding a rule grows the equivalence classes and produces more sharing in the store; removing one shrinks them and produces more distinct intermediates. The seventeen rules PyBayes ships canonicalise the structural rearrangements that natural junction-tree calibration produces: associativity and unit elimination on products, cumulative-domain laws on nested marginals, normalisation idempotence, and the law that lets a marginal commute past a domain reorder. They are not exhaustive. A stronger rule set would shrink the term store further, at the cost of a more expensive canonicalisation pass at insertion time. That is the standard compiler trade-off between IR-construction cost and IR-induced sharing.

PyBayes uses a Shafer–Shenoy schedule, so messages live on edges as lazy factor lists. Under no evidence the formula store for Asia contains 80 terms: 8 NodePotential leaves, 8 EvidenceFunction leaves, 18 Product, 21 Marginal, 24 Normalize, and one Unit. The clique posterior for \(C_4 = \{\text{LungC}, \text{TbOrCa}, \text{Tub}\}\) is

\[ \psi \;=\; \norm\!\Bigl(\,\textstyle\prod\bigl(\, \Phi_\text{Tub},\;\Phi_\text{LungC},\;\Phi_\text{TbOrCa},\; m_{C_5 \to C_4},\; \varepsilon_\text{Tub},\;\varepsilon_\text{LungC},\;\varepsilon_\text{TbOrCa}\, \bigr)\Bigr) \]

where \(m_{C_5 \to C_4}\) is the incoming message from \(C_5\) over the separator {Tub}. None of those symbols stands for an array; they are identifiers into the term store.

The store is content-addressed. Each canonical term has a deterministic name derived from its structure. The store indexes by name and returns the existing identifier if a structurally-equal term already exists. Two expressions that reduce to the same canonical form share one identifier, so every common subexpression in the calibration gets stored once. That covers separator marginals shared across both directions of message passing, intermediates produced by the rewrite rules, and clique potentials reused across queries. The technique is hash-consing.

The win shows up in concrete numbers. Under no evidence the FormulaStore for Asia holds 80 terms with 137 operand references. The fourteen roots that infer_all() cares about (six clique posteriors plus eight per-variable query Normalizes) would name 478 terms if their subtrees were expanded independently as trees. Hash-consing collapses those into 74 unique terms used by at least one query, a 6.5× reduction taken entirely at term-construction time. The most heavily reused term is ε(TbOrCa), referenced 14 times because TbOrCa appears in four cliques. ε(Bronchitis) and ε(LungCancer) are each referenced 9 times; the calibrated message N(C3) is referenced 4 times.

Selective eviction

The compiler/runtime split is two parallel arrays keyed by the same FormulaId. The FormulaStore holds the symbolic terms: content-addressed, append-only, immutable. The LogitsStore is a heap of thunks. Slot \(i\) either holds the evaluated torch.Tensor for term \(i\), or None (an unforced thunk). The runtime forces a thunk when a query demands its value, and resets it to None when its dependencies have changed.

When evidence changes on Asia (say the patient reports an abnormal x-ray), the formula DAG does not move. The tensor backing the EvidenceFunction thunk for AbnormalXRay is replaced; every other thunk is untouched. The runtime question is which non-leaf thunks are now stale.

The Bayes-ball algorithm (Shachter 1998) answers it. Originally designed for query-time independence checking, it works equally well as a thunk-invalidation policy. When evidence on a set \(E\) changes, the eviction manager runs Bayes-ball from \(E\) and unforces every thunk whose underlying term has a domain intersecting the d-connected set. The next query re-forces only what it needs; warm thunks elsewhere in the heap are returned by lookup.

Setting AbnormalXRay = T opens a path through TbOrCa to its ancestors, and through Bronchitis to Smoker. Cached marginals on those nodes are invalidated. Evidence on VisitToAsia leaves the smoking subtree alone, since Asia and Smoker are marginally independent and remain so without evidence on a common descendant.

Two distinct policies ship. Maximal evicts every cached thunk on every evidence change, the overcautious baseline. Minimal (also exposed as BayesBall and exact) runs the selective Bayes-ball invalidation described above: only thunks d-connected to the changed evidence are evicted. "Minimal" here means minimal eviction, not minimal work; it does the bookkeeping of a Bayes-ball walk on every evidence change to compute the smallest correct invalidation set. Both policies are switched at run time through PYBAYES_EVICTION_MANAGER and share the same symbolic DAG; eviction is a runtime concern, and the compiled IR knows nothing about it. The wall-clock effect is in the next section.

Evaluation

PyBayes is not the fastest exact-inference library. It is slower than pgmpy and pomegranate on raw queries, mostly because the symbolic layer adds Python dispatch overhead that those libraries have spent years removing. Comparing wall-clock against them mostly measures optimisation-years, not architecture.

The comparison that does measure architecture is selective eviction versus full recompute, both running through the same PyBayes machinery. They share the same engine construction, FormulaStore, LogitsStore, and numerical backend. The single difference is the eviction policy: Bayes-ball selectively invalidates only thunks d-connected to the changed evidence, while Maximal invalidates every thunk on every change. The numbers below isolate the contribution.

Methods

Hardware: Apple M1 Ultra (Mac Studio), Python 3.12.1, PyTorch 2.9.0.

Networks: three from the PyBayes test corpus, plus six ancestrally-closed subgraphs of the largest one to fill in the scaling curve on a single topology family. Each row links to the network's DAG:

Source Node count
Pearl burglary network (data/alarm.json) 5
Asia (data/asia.json) 8
Subgraphs of data/huge_network.json 10, 15, 20, 25, 30, 35
Full huge_network.json (synthetic, max-7 parents) 39

Subgraphs are computed by Kahn's topological sort and taking the first N nodes; this preserves parent-child structure, so each subgraph is a well-formed Bayesian network from the same topology family as the full huge network.

Four labels per (manager, network), each averaged over 500 timed iterations after one warmup call:

  • engine_init: construct an engine from the network. Builds the junction tree (delegated to NetworkX), constructs the symbolic FormulaStore, allocates the LogitsStore, and installs the eviction manager. A one-time cost, amortised over all subsequent queries.
  • infer_all: call engine.infer_all() repeatedly without changing evidence. After the first call the cache is fully warm; this measures the steady-state cost of returning cached posteriors.
  • infer_with_evidence: assert random single-variable evidence, then call engine.infer(query) for one variable. Tests selective eviction together with lazy single-variable evaluation, both contributions compounded.
  • infer_all_with_evidence: assert random single-variable evidence, then call engine.infer_all() for every variable. Tests selective eviction directly, without the laziness benefit.

Results

All times in milliseconds (mx = Maximal, mn = Minimal):

Nodes engine_init (mn) infer_all warm (mn) infer_all_with_ev (mx) infer_all_with_ev (mn) speedup
5 1.6 0.16 0.56 0.56 1.01×
8 3.6 0.24 1.22 1.10 1.11×
10 1.7 0.31 0.55 0.44 1.25×
15 2.3 0.45 0.75 0.58 1.30×
20 3.2 0.60 1.01 0.74 1.37×
25 4.4 0.77 1.43 0.90 1.58×
30 12.6 0.93 2.79 1.57 1.78×
35 24.8 1.04 90.5 4.09 22.1×
39 29.9 1.24 122.4 5.17 23.6×

Selective eviction beats full recompute monotonically as the network grows. The sharp jump between subset sizes 30 and 35 is a real topological event in the junction tree, not a smooth size effect. The huge network has three nodes (node1, node24, node36) that all share the same five-parent set (node25, node13, node16, node17, node37). They enter the topological prefix in a three-position window at sizes 32, 33, 34. Once they do, the maximum separator size in the junction tree jumps from 1 to 5, the total separator weight nearly doubles, and the maximum clique degree triples.

The substructure responsible:

Collider Parents
node1 node25, node13, node16, node17, node37
node24 node25, node13, node16, node17, node37
node36 node25, node13, node16, node17, node37

Three identical rows. Each collider has the same five-parent set. Moralisation adds a complete graph on those five parents (every pair shares a child) and adds it three times over from the three colliders. After triangulation and clique extraction, the resulting cliques are large and overlap heavily on subsets of the five-parent set. That overlap is the direct cause of the separator-weight jump in the table above.

Adding a single high-arity collider does not move the needle. Adding three colliders that share an identical parent set enlarges every separator they participate in, which expands the d-connected set any single evidence update can reach. Maximal eviction has to recompute that whole expanded set; selective eviction does not. The performance jump tracks the topology jump, with one position of lag because PyBayes' message-passing schedule reaches the new structure on the next query rather than at insertion time.

The lesson generalises beyond this particular network: selective eviction's payoff is controlled by junction-tree separator density, not by raw node count. A 100-node tree-shaped network with treewidth 1 will see a small benefit; a 30-node network with a few high-arity shared-parent colliders will see a large one.

The compounded effect of selective eviction together with lazy single-variable evaluation is larger. Worst case (full recompute under blanket invalidation) versus best case (single-variable query under selective invalidation):

Nodes mx infer_all_with_ev mn infer_with_ev combined
5 0.56 ms 0.30 ms 1.9×
8 1.22 ms 0.47 ms 2.6×
10 0.55 ms 0.12 ms 4.7×
15 0.75 ms 0.12 ms 6.5×
20 1.01 ms 0.11 ms 9.1×
25 1.43 ms 0.12 ms 12.2×
30 2.79 ms 0.26 ms 10.8×
35 90.5 ms 0.94 ms 96×
39 122.4 ms 1.12 ms 109×

For the workload PyBayes was built for (long-running interactive systems that absorb streaming evidence and answer focused queries), the architecture turns a 122 ms per-cycle update on a 39-node network into a 1.12 ms cycle. The crossover where the contribution starts to pay sits around 6 to 8 nodes; beyond that, both selective eviction and lazy evaluation grow more valuable as the network grows.

Building the symbolic DAG (engine_init) costs between 1.6 ms at 5 nodes and roughly 30 ms at 39 nodes. That cost is one-time and is recovered after a single full-recompute cycle on any network where selective eviction wins. On the huge network, the 30 ms construction cost is less than a quarter of one maximal-eviction update; every subsequent query amortises it further across the session.

Reproducibility

The benchmark script is in the PyBayes repo at scripts/bench_eviction.py. To reproduce:

git clone https://github.com/dlewissandy/pybayes
cd pybayes
uv sync
for cmd in "--network alarm" "--network asia" \
           "--network huge --subset 10" "--network huge --subset 15" \
           "--network huge --subset 20" "--network huge --subset 25" \
           "--network huge --subset 30" "--network huge --subset 35" \
           "--network huge"; do
  uv run python scripts/bench_eviction.py $cmd --repeat 500
done

The script reports six labels per (network, manager). The four cited above (engine_init, infer_all, infer_with_evidence, and infer_all_with_evidence) are the relevant ones for this evaluation. All numbers above came from a single run on the hardware listed in the Methods section. Absolute timings will vary by machine; the shape of the scaling curve should not.

References

Lauritzen, S. L. and Spiegelhalter, D. J. (1988). Local computations with probabilities on graphical structures and their application to expert systems. Journal of the Royal Statistical Society, Series B, 50(2): 157–224.

Madsen, A. L. and Jensen, F. V. (1999). Lazy propagation: a junction tree inference algorithm based on lazy evaluation. Artificial Intelligence, 113(1–2): 203–245.

Shachter, R. D. (1998). Bayes-ball: the rational pastime (for determining irrelevance and requisite information in belief networks and influence diagrams). Proceedings of UAI '98, pp. 480–487.

Shafer, G. R. and Shenoy, P. P. (1990). Probability propagation. Annals of Mathematics and Artificial Intelligence, 2: 327–351.

Comments & reactions