Optimized Priority Scheduling for Faster Scalable Belief Propagation

Abnash Bassi, Gilead Posluns, Mark C. Jeffrey
Proceedings of the 13th International Conference on Probabilistic Graphical Models, PMLR 343:2-17, 2026.

Abstract

Belief propagation (BP) is a marginalization method using local message passing on probabilistic graphical models, seen in disciplines like Bayesian inference, statistical physics, and wireless communications. With the proliferation of manycore processors with 100s of cores, BP parallelization solves larger marginalization problems in reasonable time. On one hand, the classic synchronous algorithm easily maps to multithreaded execution with abundant parallelism per synchronization barrier. On the other hand, asynchronous algorithms converge on more graphs and reduce total work and sequential time to convergence, but are more difficult to parallelize due to priority-ordered scheduling. Recently proposed relaxed ordered parallel algorithms are plagued by the overheads of a decade-old scheduler. This paper unifies recent innovations in concurrent priority schedulers with relaxed parallel BP, using the Stealing MultiQueue (SMQ) with lazy priority updates. Prior work proposes different relaxed BP algorithms but fails to identify one BP algorithm that outperforms alternatives across inputs. We are the first to empirically show relaxed residual BP (RRBP) consistently outperforming all other baseline BP algorithms: at 384 threads our SMQ-based RRBP outperforms synchronous and other asynchronous BP algorithms by geomean 2.66$\times$ and $>$1.6$\times$, respectively. Our code is available at github.com/mcj-group/rbp.

Cite this Paper

BibTeX
@InProceedings{pmlr-v343-bassi26a, title = {Optimized Priority Scheduling for Faster Scalable Belief Propagation}, author = {Bassi, Abnash and Posluns, Gilead and Jeffrey, Mark C.}, booktitle = {Proceedings of the 13th International Conference on Probabilistic Graphical Models}, pages = {2--17}, 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/bassi26a/bassi26a.pdf}, url = {https://proceedings.mlr.press/v343/bassi26a.html}, abstract = {Belief propagation (BP) is a marginalization method using local message passing on probabilistic graphical models, seen in disciplines like Bayesian inference, statistical physics, and wireless communications. With the proliferation of manycore processors with 100s of cores, BP parallelization solves larger marginalization problems in reasonable time. On one hand, the classic synchronous algorithm easily maps to multithreaded execution with abundant parallelism per synchronization barrier. On the other hand, asynchronous algorithms converge on more graphs and reduce total work and sequential time to convergence, but are more difficult to parallelize due to priority-ordered scheduling. Recently proposed relaxed ordered parallel algorithms are plagued by the overheads of a decade-old scheduler. This paper unifies recent innovations in concurrent priority schedulers with relaxed parallel BP, using the Stealing MultiQueue (SMQ) with lazy priority updates. Prior work proposes different relaxed BP algorithms but fails to identify one BP algorithm that outperforms alternatives across inputs. We are the first to empirically show relaxed residual BP (RRBP) consistently outperforming all other baseline BP algorithms: at 384 threads our SMQ-based RRBP outperforms synchronous and other asynchronous BP algorithms by geomean 2.66$\times$ and $>$1.6$\times$, respectively. Our code is available at github.com/mcj-group/rbp.} }
Endnote
%0 Conference Paper %T Optimized Priority Scheduling for Faster Scalable Belief Propagation %A Abnash Bassi %A Gilead Posluns %A Mark C. Jeffrey %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-bassi26a %I PMLR %P 2--17 %U https://proceedings.mlr.press/v343/bassi26a.html %V 343 %X Belief propagation (BP) is a marginalization method using local message passing on probabilistic graphical models, seen in disciplines like Bayesian inference, statistical physics, and wireless communications. With the proliferation of manycore processors with 100s of cores, BP parallelization solves larger marginalization problems in reasonable time. On one hand, the classic synchronous algorithm easily maps to multithreaded execution with abundant parallelism per synchronization barrier. On the other hand, asynchronous algorithms converge on more graphs and reduce total work and sequential time to convergence, but are more difficult to parallelize due to priority-ordered scheduling. Recently proposed relaxed ordered parallel algorithms are plagued by the overheads of a decade-old scheduler. This paper unifies recent innovations in concurrent priority schedulers with relaxed parallel BP, using the Stealing MultiQueue (SMQ) with lazy priority updates. Prior work proposes different relaxed BP algorithms but fails to identify one BP algorithm that outperforms alternatives across inputs. We are the first to empirically show relaxed residual BP (RRBP) consistently outperforming all other baseline BP algorithms: at 384 threads our SMQ-based RRBP outperforms synchronous and other asynchronous BP algorithms by geomean 2.66$\times$ and $>$1.6$\times$, respectively. Our code is available at github.com/mcj-group/rbp.
APA
Bassi, A., Posluns, G. & Jeffrey, M.C.. (2026). Optimized Priority Scheduling for Faster Scalable Belief Propagation. Proceedings of the 13th International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 343:2-17 Available from https://proceedings.mlr.press/v343/bassi26a.html.

Related Material