Large probabilistic models are often written as libraries of small reusable pieces. A Bayesian network is a graph of random variables with conditional probability tables, and these pieces are its "network fragments" or object classes. When a query arrives, a system picks the relevant pieces and glues them into a query-specific network. Current systems then throw away the seams. The glued network is flattened into one graph and handed to a standard exact inference engine, which rebuilds a junction tree from scratch for every query. A junction tree is a tree of variable clusters whose cost grows exponentially with the size of its largest cluster. We propose the opposite design. Each fragment is compiled once into its own small inference structure and cached. At query time, the system decides which seams are good cut points and which should be fused. Exact inference then runs as message passing across the kept seams.
The claim is specific and falsifiable. On streams of queries that reuse fragments, keeping good seams and caching per-fragment compilations should lower end-to-end query latency relative to "assemble, flatten, recompile." The answers must stay exactly the same. The gain should come mostly from avoided recompilation and from smaller clusters. If seams are chosen naively, by always cutting at every fragment boundary, the approach should lose on some models, because some authored boundaries are poor cut points. The merge rule is therefore the core ingredient, not an afterthought.
What exists and what is missing
The ingredients exist but have never been joined in the dynamic setting.
Constructing Situation Specific Belief Networks builds a minimal query-specific network from a fragment library. It uses pruning based on d-separation, a graphical test for which variables cannot affect the query. It then flattens the result for an off-the-shelf engine and reports no timing. This paper motivates the proposal: it shows the seams exist and are discarded.
Object-Oriented Bayesian Networks is the closest prior work. It observes that an object's interface separates its internals from the rest of the model, and it compiles a fixed object hierarchy into a multiply sectioned network. That structure, from Exploring Localization in Bayesian Networks for Large Expert Systems, is a tree of subnetworks that share interface variables. It assumes the objects and links are fixed in advance, supports no query-driven assembly, and reports no runtime numbers. We differ on three points. The subnetwork tree is built per query from retrieved fragments. Compiled pieces are cached across queries. Boundaries are merged or kept by a cost rule rather than inherited as given.
The inference machinery is reused from two sources. Inference in Multiply Sectioned Bayesian Networks with Extended Shafer-Shenoy and Lazy Propagation replaces one junction tree per subnet with a linked forest and keeps potentials factored. On its running example this stores 46 parameters where the HUGIN-style approach stores 92, but it assumes a hand-engineered static partition. Optimization of Inter-Subnet Belief Updating in Multiply Sectioned Bayesian Networks schedules messages across subnet links and assumes a fixed tree.
Two results constrain the design. Computational Advantages of Relevance Reasoning in Bayesian Belief Networks shows that relevance pruning on a single monolithic network already yields large speedups, which makes it a serious competitor. The same paper notes that the gains vanish on densely connected graphs. An Empirical Evaluation of Possible Variations of Lazy Propagation shows that extra bookkeeping in factored inference can cost more time than it saves. That warns us that coordination overhead across seams is a real risk.
Core mechanism
Assembly proceeds as in the situation-specific construction work: retrieve fragments, unify their entities, combine influences, and prune irrelevant nodes. It then builds a fragment interaction graph whose nodes are the instantiated fragments and whose edges are their shared interface variables.
A valid tree of subnetworks needs two properties. The shared variables must separate the subnetworks, and the links must form a tree with the running-intersection property, meaning a variable shared by two subnets appears in every subnet on the path between them. Assembled fragments often violate this. A cycle of fragments linked by shared entities is one case. A node whose table is combined from several fragments' influences is another. The algorithm resolves each violation by merging fragments.
Among the valid merge sequences, it greedily chooses merges using a cost estimate:
$$C(\mathcal{P}) = \sum_{S \in \mathcal{P}} \Big( w(S) + [S \notin \text{cache}]\, \kappa(S) \Big) + \sum_{(S,S')} \pi(I_{SS'})$$
Here $\mathcal{P}$ is the current partition into subnets. $w(S)$ is the largest cluster state space of subnet $S$'s compiled forest. $\kappa(S)$ is its compilation cost, paid only on a cache miss. $\pi(I_{SS'})$ is the state space of the shared interface between linked subnets $S$ and $S'$, which bounds the size of the messages between them. The rule fuses fragments whose interface is nearly as large as their internals, and keeps seams that are small relative to what they separate.
Compiled local forests are cached under a key made of the fragment template and the pattern of which interface variables are linked. Reuse therefore depends on how often templates recur, not on whole queries recurring. Correctness reduces to the published exactness guarantee for linked-forest propagation, because the output of the merge step is a valid tree of subnetworks. We will check this empirically against flat inference on every query.
Research Program
The work has three parts. The first is the assembler-compiler just described, implemented on a shared lazy-propagation core so that every method uses identical numerical kernels.
The second is a benchmark suite, which the literature lacks. The modular-representation papers report no timings at all; the military vignettes of Network Engineering for Complex Belief Networks are qualitative. We will build fragment libraries in two ways.
In the first, we cut standard networks along module boundaries: CPCS, ALARM, and Insurance from the bnlearn collection used by Probabilistic Graphical Models Parameter Learning with Transferred Prior and Constraints, plus Barley, Diabetes, and Mildew from Lazy Propagation in Junction Trees. Each network is cut two ways: along boundaries recovered by graph clustering, and along deliberately poor random boundaries. This tests whether the merge rule recovers from bad authoring.
In the second, we write a generator for entity-rich situations in the style of Hypothesis Management in Situation-Specific Network Construction. It varies the number of entities, the density of associations between them, and how often templates repeat. Query streams are sampled so that the overlap between consecutive queries is controlled.
The third part is analysis. We will break latency into its phases (assembly, triangulation, propagation, and message coordination) to see where time goes.
Baselines
The naive reference point is flat compilation of the full, unpruned network with a HUGIN-style junction tree, recompiled whenever the model changes. It tells us how hard each instance is, and on CPCS it is expected to exhaust memory as it did in the relevance-reasoning study.
The strongest existing method on fixed-topology models is relevance-based decomposition plus clustering from Computational Advantages of Relevance Reasoning in Bayesian Belief Networks. That paper reports that it runs "on average over 20 times faster" than whole-network clustering on the 360-node CPCS subset, with nuisance-node removal adding "an average 30% improvement." We will rerun it with our lazy core on the same query streams and the same machine. On the fixed-topology networks, beating it means lower median and 95th-percentile end-to-end latency at equal exactness. On the entity-varying generator, where a monolithic model must pre-wire every possible entity, we expect to dominate it, and we will report how large its pre-wired graph becomes.
The most direct competitor is the situation-specific pipeline of Constructing Situation Specific Belief Networks: same retrieval and pruning, then a flattened network run through lazy propagation, the flat engine the file reports as fastest at higher evidence counts. The file contains no reported runtime for this pipeline (no reported result found on Lacuna for situation-specific network construction timing), so we will implement it faithfully. Both systems get identical fragments, identical pruning, and the same elimination-order heuristic. Beating it means lower amortized latency over a stream of 1,000 queries at matched or lower peak memory.
A memoization baseline caches the entire compiled flattened network keyed by its structure and reuses it on exact repeats.
Two ablations isolate our ingredients. The first keeps every fragment boundary with no merging. The second applies the merge rule but disables cross-query caching.
The Koller–Pfeffer static compilation of a fixed object hierarchy is run where the hierarchy is fixed. The file reports no reported result found on Lacuna for its runtime.
Why not just…?
Why not just flatten the assembled network and use lazy propagation? This is the real threat. If the query-specific networks are small, triangulation is cheap, and lazy propagation already keeps tables factored. In that case our gains collapse to coordination overhead, which the lazy-propagation variation study suggests can be net negative. The phase-level latency breakdown settles it directly. If triangulation plus compilation is under roughly a tenth of flat end-to-end time on the realistic streams, per-fragment caching cannot pay, and we will report that the seams are not worth keeping.
Why not just precompile one big network and prune per query? Relevance pruning on a monolith is strong on fixed topologies, with the twentyfold CPCS result above. It needs every entity and association wired in advance, and the hypothesis-management work argues this becomes combinatorial when the number of entities is unknown. The entity-count sweep in our generator measures where the pre-wired monolith's compile size and pruning time overtake our approach. If they never do within realistic ranges, the idea is limited to open-world models.
Why not just cache the whole compiled network? Whole-network memoization only helps on exact structural repeats. Our cache keys on fragment templates, so it helps whenever parts recur. The query-overlap sweep separates the two. We expect them to tie at high exact-repeat rates and diverge as queries share fragments but differ in composition. If they tie throughout, the finer cache is unnecessary.
Why not just cut at every authored boundary, as in the static object-oriented compilation? Authored interfaces can be as large as the internals, or can form cycles that force expensive merges anyway. The random-boundary cuts test this. The no-merge ablation should lose badly there, while the full method should approach the latency it achieves on the clustering-based cuts.
Decisive checks
Exactness comes first. Posterior marginals must match flat junction-tree inference to within floating-point tolerance on every query; any mismatch means the merge step produced an invalid subnetwork tree.
The central result is a curve of amortized latency against query-stream overlap and against entity count. It should show the full method below the flattened situation-specific pipeline once template reuse is moderate. It should also show the no-merge ablation losing on poorly cut libraries, which would confirm that the cost-based merging is what makes the boundaries usable.
A negative outcome is informative. That would be triangulation being a small share of total time, or relevance pruning on a monolith matching us even with varying entities. Either would establish empirically that inference-time use of fragment boundaries does not pay, a question the modular-representation literature has so far left unmeasured.
References
- Constructing Situation Specific Belief Networks
- Object-Oriented Bayesian Networks
- Exploring Localization in Bayesian Networks for Large Expert Systems
- Inference in Multiply Sectioned Bayesian Networks with Extended Shafer-Shenoy and Lazy Propagation
- Optimization of Inter-Subnet Belief Updating in Multiply Sectioned Bayesian Networks
- Computational Advantages of Relevance Reasoning in Bayesian Belief Networks
- An Empirical Evaluation of Possible Variations of Lazy Propagation
- Network Engineering for Complex Belief Networks
- Probabilistic Graphical Models Parameter Learning with Transferred Prior and Constraints
- Lazy Propagation in Junction Trees
- Hypothesis Management in Situation-Specific Network Construction