A Structural Runtime Law for Scalable Exact Inference in Two-Layer Noisy-OR Bayesian Networks

Exact inference in two-layer noisy-OR Bayesian networks (BN2Os) is challenging due to the multiply connected structure. We identify a structural factorization of BN2O joint distributions induced by the unconditional independence of root variables. To exploit this factorization, we introduce noisy-OR circuit engineering (NOICE), a circuit framework that compiles BN2Os into a quotient of family-set marginal distributions represented by explicit arithmetic subcircuits. This factorization yields a structural runtime law for exact inference, $t(Q)=c(N)2^{\omega (Q)}$, where $Q$ is a query, $c(N)$ is the cost of a single NOICE circuit propagation, and $\omega (Q)$ is the number of non-queried roots shared by two or more observed leaves. We prove that NOICE compilation produces circuits whose size grows linearly in the numbers of roots, leaves, and edges, with closed-form expressions determining the compiled size a priori. Experiments on BN2Os spanning five orders of magnitude validate the predicted runtime law for inference and demonstrate compilation of BN2Os with up to $24$M edges, extending the scale of exact structural compilation by up to five orders of magnitude over prior general-purpose methods.