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:
Terms come with an equational theory, presented here as denotational equations where \(\sem{\cdot}\) maps a term to its log-probability tensor.
Reference.
Product.
Marginal.
Braid.
Divide.
Normalize.
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
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: callengine.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 callengine.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 callengine.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.