acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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, , where is a query, is the cost of a single NOICE circuit propagation, and 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 M edges, extending the scale of exact structural compilation by up to five orders of magnitude over prior general-purpose methods.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Exact probabilistic inference, Noisy-OR Bayesian networks, Probabilistic circuits, Knowledge compilation, Structural complexity of inference

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_uMu1OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper exploits the unconditional independence of root variables in two-layer noisy-OR Bayesian networks (BN2Os) to derive a factorized circuit representation (NOICE), obtain linear-size compilation, and characterize exact inference complexity through a query-dependent overlap parameter ω(Q). The authors presents extensive empirical evaluation of the approach, demonstrating scale-up for simple query types.

Critical strengths

Overall, the paper is well written and its objectives are clear. The empirical analysis is well laid out. There is an attempted balance between theory and experiment, which is impressive.The highlights:

  1. Clear structural insight The paper identifies a family-set factorization for BN2Os and uses it directly as a compilation mechanism. The derivation is elegant and easy to understand. Unlike much of the probabilistic-circuit literature, the central construction is quite transparent.

  2. Closed-form compilation-size analysis Theorem 2 provides exact formulas for node and edge counts: 7r+8s+3t+3 nodes and 5r+9s+7t+2 edges. This is stronger than merely proving asymptotic complexity and gives a predictable engineering model.

  3. Very large-scale experiments The paper compiles networks with 24M BN edges and 324M circuit edges, which is noteworthy. Even if the practical utility of these giant compilations can be debated, the engineering achievement is impressive.

  4. Runtime characterization is intuitive The overlap index ω(Q) captures something meaningful: (a) roots shared across observed leaves and (b) roots not directly queried and the empirical validation is convincing. The runtime law t(Q)=c(N) 2^ω(Q) matches the data extremely well.

Critical weaknesses

The paper's theoretical treatment lacks real depth, and the theorems derived are straightforward and do not provide any significant advances or insights. It is thus unclear how significant the contributions are. To summarize our concerns:

  1. Novelty is weaker than the paper suggests: This is my biggest concern. The paper repeatedly frames the contribution as discovering a new structural factorization. However, Theorem 1 follows almost immediately from: (a) standard BN factorization, (b) independence of roots, and (c) algebraic cancellation. The proof is only a few lines long. I do not see a fundamentally new probabilistic result here. The novelty is really that a circuit architecture built around this factorization. That is still potentially publishable, but the theoretical narrative currently oversells the discovery. My suggestion is to position the work as a compilation strategy exploiting a known but previously underutilized BN2O factorization rather than as a new structural property of BN2Os.

  2. The overlap law is almost tautological: Theorem 4 states that inference enumerates every assignment of S, the overlap roots. Therefore 2^(∣S∣) propagations are required. Then runtime becomes c(N) 2^(∣S∣). This is mathematically correct. However, from an algorithm-analysis standpoint it is essentially a restatement of the evaluation algorithm. The empirical law works because the algorithm was explicitly designed around enumeration over S. Thus, the theorem is useful but it is not a surprising complexity result. One can view the overlap law as "the runtime follows directly from the code."

  3. Comparison against weak baselines: The paper's strongest claim is the massive scaling advantage over ACE and rank-one compilation. However, ACE fails around roughly 200 edges in their benchmark. That immediately raises questions: Why are the benchmark networks pathological for ACE? Are modern WMC-based methods evaluated? What about specialized noisy-OR methods? What about exact BN2O inference algorithms that exploit causal independence? The paper acknowledges some of these methods but does not compare against them. Consequently the practical significance of the "five orders of magnitude improvement" claim is uncertain.

  4. Compilation size is not inference tractability: A key conceptual issue is hidden in the paper, which demonstrates that compiled representation size is linear in network size. However exact inference complexity remains O(2^r ), and more specifically O(2^ω(Q) ). This means the difficult part has simply moved from circuit construction to query evaluation. The paper is entirely honest about this, but the presentation sometimes risks implying a stronger breakthrough than actually exists. A skeptical reader may ask: Have we solved exact inference, or have we merely obtained a compact representation while retaining exponential query complexity? The latter appears closer to the truth.

  5. Missing discussion of practical query regimes: The paper hinges on ω(Q). Yet there is little characterization of: expected ω(Q) typical ω(Q) in real diagnostic networks distribution of ω(Q) under realistic workloads Without such analysis we cannot determine whether the approach is practically efficient. Consider two possibilities: Typical ω(Q)=5 → method is excellent. Typical ω(Q)=100 → exact inference remains hopeless. The manuscript never quantifies this. This is a substantial omission.

Theoretical Concerns: I have several concerns on this front, where we also provide a means for addressing these concerns. These include:

  1. Relationship to treewidth is underdeveloped: The paper emphasizes that inference depends on overlap rather than network size. But overlap is essentially another representation of the source of induced dependence. It would strengthen the work greatly if the authors established: formal relations between ω(Q) and treewidth, lower bounds, upper bounds, equivalence in certain BN2O subclasses. Currently the relationship is mostly qualitative.

  2. No lower-bound theory: The paper gives: (a) exact size characterization, and (b) exact runtime formula. However, there is no impossibility result. A stronger theoretical contribution would show: Any factorization preserving exactness must incur exponential dependence on overlap. Without such results, the necessity of the overlap law remains unclear.

  3. "Polytree-like factorization" claim may be overstated: The paper repeatedly states that BN2Os admit a factorization "identical in form to polytrees." Formally this is true. Conceptually, however, the hard dependencies have not disappeared. They reappear in the overlap enumeration stage. Thus readers may interpret the statement more strongly than intended. I would recommend toning down this claim.

Experimental Concerns: I have the following issues with the empirical analysis.

  1. Runtime results largely validate the implementation: The runtime law validation is very clean. However much of Section 4 verifies consequences already implied by the algorithm. These include(a) fixing ω(Q) gives near-constant runtime, and (b) increasing ω(Q) produces exponential growth. These results are expected from the algorithmic structure. The experiments are therefore more sanity checks than discoveries.

  2. Lack of real-world datasets: The evaluation relies on synthetic fan-in-4 networks and synthetic QMR-like generators. I would very much like to see: actual QMR-DT subsets, medical diagnosis datasets, learned noisy-OR networks. Without such experiments it is difficult to assess practical impact.

  3. No analysis of query distributions: The central quantity ω(Q) is measured after query construction. What is missing is: (a) expected overlap under random evidence, (b) expected overlap in diagnosis tasks, and (c) scaling of overlap with network size. This is arguably more important than the current runtime plots.

Presentation Comments

The paper is generally well written and the authors are to be commended for this. However, the authors should consider the following issues:

Introduction: The narrative sometimes implies exact inference in huge BN2Os becomes tractable. The more precise claim is: compilation becomes linear-size; exact query cost is governed by overlap. That distinction should be emphasized earlier.

Section 3: The derivation of Theorem 1 is straightforward enough that it almost belongs as a proposition rather than the centerpiece theorem.

Section 4: The experimental section is longer than necessary. Several figures essentially demonstrate the same phenomenon: runtime independent of evidence count once overlap fixed, exponential growth in overlap. These could be compressed.

Questions for authors
  1. Expected-overlap theory: Can you develop E[ω(Q)] for random BN2Os and random evidence models? This would move the work beyond algorithm description.

  2. Lower bounds: Can you show that exponential dependence on overlap is unavoidable under exact inference? That would transform the overlap law from an algorithm property into a structural theorem.

  3. Real diagnostic workloads: Can you demonstrate that realistic diagnosis queries produce modest overlap? Otherwise scalability claims remain largely about compilation rather than inference.

  4. Experiments: Can you run experments on real examples rather than synthetic ones?

Reviewer_giirOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The authors propose a factorization of the BN2O joint distribution and a circuit framework with an algorithm that yields circuits of size linear in the number of roots, leaves and edges in the BN2O. Additionally, the paper provides an algorithm for inference with the new framework. The paper proves the correctness of the factorization, the inference algorithm, and a theoretical scaling of circuit size and inference runtime. Furthermore, the authors suggest a scaling law that governs the runtime of their method as well as additional analysis of compilation complexity, claiming compilation of networks with millions of edges. Finally, the paper provides an extensive empirical evaluation of the theoretical circuit size and scaling laws.

Critical strengths

S1: The paper is overall well written and cohesive

S2: The proofs are correct by my assessment

S3: Scaling evaluation is extensive.

Critical weaknesses

W1: limited novelty in the suggested factorization and circuit evaluation algorithm.

W2: incorrect framing by overloading the term "compile" with its traditional meaning from prior methods.

W3: missing accuracy checks or output comparisons with other baselines

W4: technical details in supplementary code, which contradict some of the paper's descriptions.

Questions for authors

Q1: The paper has limited novelty in the theory it presents. The factorization in Theorem 1 is trivial, stemming from the chain rule of conditional probability and root independence. Circuit construction in Algorithm 1 is a direct application of the factorization from Theorem 1 with the added design choice of using family marginals. Circuit evaluation in Algorithm 2 is cutset conditioning where the set of shared roots is used as the cutset. The runtime law is true by construction and states that query inference time is the time of a single circuit pass times the number of passes required. Then, the paper's circuit construction lacks the advantages of existing compilation methods, such as ACE. In the latter, constructing the circuit takes a lot of runtime but results in a decomposable circuit, which makes query inference possible in a single pass. In this work, circuit construction is much faster but the resulting circuit is not decomposable. As a result, the complexity of circuit compilation is offloaded to inference time, resulting in queries requiring multiple passes, exponential in the root overlap. The paper compiles only in the sense of building a circuit, without the usual runtime benefits of compilation.

Q2: Alternative methods such as Quickscore handle negative and positive findings in the query differently and typically only positive findings affect runtime. That is not the case with NOICE and more importantly, its runtime grows with network size regardless of the number of observed variables in the query. Unobserved leaves and roots with no observed leaves are usually pruned as they don't contribute to the result. The dependence on network size is evident in the linear factor c(N) in Eq. 4, which means that even trivial queries (with implied low \omega(Q)) can have disproportionately long runtimes in large networks in contrast to methods that perform pruning.

Q3: The evaluation in Section 4 focuses entirely on experimentally confirming the theoretical scaling of the circuit sizes and inference times, but what about the correctness and precision of the query results? how do they compare to ACE and rank-one?

Q4: The supplied code implements circuit creation differently from what is described in the paper. The connect_children function adds a division node after each leaf circuit instead of one denominator node as described in Algorithm 1. Additionally, there are many garbage collection (GC) calls throughout the compiler module, which incur a non-constant runtime penalty. Engineering considerations for GC are understandable, however experiments that measure compile runtime are impacted by GC. I kindly ask the authors to verify that their code faithfully follows the implementation presented in the paper and make necessary changes where there are any gaps. Further, I ask to measure the impact of GC on runtime and account for that in the reported results.

Q5: Inference and compile times comparisons to ACE and rank-one are shown in appendices B and C. On the fixed fan-in dataset, Table 3 shows that ACE and rank-one have up to two orders of magnitude faster inference times than NOICE, as the overlap index increases. Table 4 shows a narrower gap when combining compilation and inference time, however compilation is done once offline and therefore the inference only gaps are the substantial ones. On the second dataset, Table 14 presents combined compilation and inference time and separate inference-only runtime is not reported for this dataset. Regardless, Table 14 shows much the same pattern as before, with NOICE having better total runtime in slightly more cases. But, as \omega(Q) increases all methods reach the same order of magnitude runtimes, ACE and rank-one have lower times on the smallest network.

Q6: One true benefit of NOICE is its application to large networks, where ACE and rank-one fail to compile due to memory limits, however the paper is not framed around this idea and does not explore it further. Another caveat is that this advantage comes at the cost of increasing inference time, which calls for a comparison against methods that do not compile at all. I agree with the finding that the inference time of NOICE is entirely dependent on \omega(Q) (on fixed network size), however that does not directly measure query difficulty itself. Are there cases where \omega(Q) is large but inference cost of non-compiling methods, or direct inference, is cheap? Under which conditions will NOICE have faster inference times over such methods, despite high \omega (Q)?

Q7: As I see it, where the baselines compile, NOICE is faster only for low-overlap queries but that advantage shrinks rapidly as overlap increases. When the baseline does not compile, I would first test NOICE inference times against non-compiling methods and given that assess its overall contribution.

Reviewer_hwtoOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper investigates how the structural properties of the computational graph of Two-Layer Noisy-OR Bayesian Networks (BN2Os) can be leveraged for exact inference, which is challenging in general due to their dense structure. The authors approach the problem via the lens of arithmetic circuits and formulate a circuit model following a quotient factorization of the BN2O. The authors prove that their model size, unlike existing approaches, is linear w.r.t. the BN2O model size, which enables construction of 5-orders of magnitude larger BN2O models. The authors also derive a BN2O runtime scaling law, which is exponential w.r.t. unobserved root nodes that are shared by two or more leaf nodes. The theory and method is empirically tested against a competing method (ACE), with results showing empirical evidence supporting the claims.

Critical strengths

The paper presents a clever method for leveraging structural properties of BN2Os. The work is an interesting combination of arithmetic circuits, caching and BN2O factorization that leads to a more computationally efficient model construction, enabling a several orders of magnitude increase in feasible model sizes for exact inference and improved understanding of the limits to runtime. Theoretical findings are also backed by convincing empirical results: Authors provide details for a robust experimentation procedure of the method, and provide empirical findings that support the theoretical result proposed (the BN2O Overlap Law for runtime calculation). Authors have also taken steps to enable full reproducibility of the results presented with a codebase that is well-organized and accessible.

Critical weaknesses

The extent of the novelty of the contributions is left unclear. I found it difficult to distinguish what is already known in the BN2O and BN literature regarding the computational complexity of these methods, and what are the novel findings the paper adds on top of this. This could be mitigated by adding a contributions list to the introduction that lays this out. The paper is also missing a limitations and discussion section that could be used to further explain what the contributions mean in practice for BN2Os. Finally, being a paper discussing arithmetic circuits that represent joint distributions and using structural constraints for tractability, I would have expected more extensive discussion of how the work relates to the probabilistic circuits literature studying these same issues.

Questions for authors
  1. What are some of the impacts in application of the method within the BN and BN2O communities that the authors expect to see, given the substantial increase in BN2O size where exact inference is feasible?
  2. How restrictive is the exponential growth defined in the BN2O Overlap Law in practice? Do BN2O models generally have a fully connected structure, or sparser connections? How restrictive to the expressivity of the model is enforcing the latter to keep runtime feasible?
  3. Could the authors expand on the novelty of the BN2O Overlap Law further. How does the BN2O Overlap Law for runtime calculation relate and compare to existing literature studying the computational complexity of BNs and BN2Os? Is this identification of shared unobserved parents governing the runtime in BN2Os, or BNs in general, a previously unknown result?
  4. Why do the authors opt not to use probabilistic circuits more extensively? These seem to be a close fit to the problem.
  5. What does introducing the quotient node add? Is the circuit computing the division ever actually realized, or are strictly sub-circuits evaluated independently?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.