Selective Indicator Elimination in Arithmetic Circuits for Bipartite Noisy-OR Bayesian Networks

Cory Butz, Alejandro Santoscoy-Rivero, Jiřı́ Vomlel, Anders Madsen
Proceedings of the 13th International Conference on Probabilistic Graphical Models, PMLR 343:140-152, 2026.

Abstract

Bipartite noisy-OR Bayesian networks (BN2Os) have been compiled into arithmetic circuits (ACs) for exact inference, where evaluation traditionally consists of assigning indicator values at the circuit leaves and propagating values upward to the root. We introduce selective indicator elimination (SIE), a transformation for compiled BN2O ACs that removes indicator-controlled single-variable subcircuits and replaces them with cached values. The resulting method has two phases: an offline transformation phase that prunes such subcircuits and precomputes their replacement values, and an online evaluation phase that parses a query, assigns the appropriate cached values, and propagates over the transformed AC. Unlike prior AC compression methods that simplify static numeric computation by compressing arithmetic subcircuits consisting of multiplication and addition nodes, our approach is the first to eliminate indicator leaves together with their associated indicator-controlled computation while preserving support for general exact inference queries. We formally prove that SIE preserves exact inference correctness. Statistically significant improvements in both circuit size and exact inference runtime are empirically observed for $58%$ of the tested synthetic BN2Os.

Cite this Paper

BibTeX
@InProceedings{pmlr-v343-butz26b, title = {Selective Indicator Elimination in Arithmetic Circuits for Bipartite {Noisy-OR} {Bayesian} Networks}, author = {Butz, Cory and Santoscoy-Rivero, Alejandro and Vomlel, Ji{\v{r}}{\'\i} and Madsen, Anders}, booktitle = {Proceedings of the 13th International Conference on Probabilistic Graphical Models}, pages = {140--152}, year = {2026}, editor = {Camps-Valls, Gustau and Leonelli, Manuele and Varando, Gherardo}, volume = {343}, series = {Proceedings of Machine Learning Research}, month = {09--11 Sep}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v343/main/assets/butz26b/butz26b.pdf}, url = {https://proceedings.mlr.press/v343/butz26b.html}, abstract = {Bipartite noisy-OR Bayesian networks (BN2Os) have been compiled into arithmetic circuits (ACs) for exact inference, where evaluation traditionally consists of assigning indicator values at the circuit leaves and propagating values upward to the root. We introduce selective indicator elimination (SIE), a transformation for compiled BN2O ACs that removes indicator-controlled single-variable subcircuits and replaces them with cached values. The resulting method has two phases: an offline transformation phase that prunes such subcircuits and precomputes their replacement values, and an online evaluation phase that parses a query, assigns the appropriate cached values, and propagates over the transformed AC. Unlike prior AC compression methods that simplify static numeric computation by compressing arithmetic subcircuits consisting of multiplication and addition nodes, our approach is the first to eliminate indicator leaves together with their associated indicator-controlled computation while preserving support for general exact inference queries. We formally prove that SIE preserves exact inference correctness. Statistically significant improvements in both circuit size and exact inference runtime are empirically observed for $58%$ of the tested synthetic BN2Os.} }
Endnote
%0 Conference Paper %T Selective Indicator Elimination in Arithmetic Circuits for Bipartite Noisy-OR Bayesian Networks %A Cory Butz %A Alejandro Santoscoy-Rivero %A Jiřı́ Vomlel %A Anders Madsen %B Proceedings of the 13th International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2026 %E Gustau Camps-Valls %E Manuele Leonelli %E Gherardo Varando %F pmlr-v343-butz26b %I PMLR %P 140--152 %U https://proceedings.mlr.press/v343/butz26b.html %V 343 %X Bipartite noisy-OR Bayesian networks (BN2Os) have been compiled into arithmetic circuits (ACs) for exact inference, where evaluation traditionally consists of assigning indicator values at the circuit leaves and propagating values upward to the root. We introduce selective indicator elimination (SIE), a transformation for compiled BN2O ACs that removes indicator-controlled single-variable subcircuits and replaces them with cached values. The resulting method has two phases: an offline transformation phase that prunes such subcircuits and precomputes their replacement values, and an online evaluation phase that parses a query, assigns the appropriate cached values, and propagates over the transformed AC. Unlike prior AC compression methods that simplify static numeric computation by compressing arithmetic subcircuits consisting of multiplication and addition nodes, our approach is the first to eliminate indicator leaves together with their associated indicator-controlled computation while preserving support for general exact inference queries. We formally prove that SIE preserves exact inference correctness. Statistically significant improvements in both circuit size and exact inference runtime are empirically observed for $58%$ of the tested synthetic BN2Os.
APA
Butz, C., Santoscoy-Rivero, A., Vomlel, J. & Madsen, A.. (2026). Selective Indicator Elimination in Arithmetic Circuits for Bipartite Noisy-OR Bayesian Networks. Proceedings of the 13th International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 343:140-152 Available from https://proceedings.mlr.press/v343/butz26b.html.

Related Material