Belief Propagation Converges to Gaussian Distributions in Sparsely-Connected Factor Graphs

Tom Yates, Yuzhou Cheng, Ignacio Alzugaray, Danyal Akarca, Pedro A.M. Mediano, Andrew J. Davison · 2026

Read Belief Propagation Converges to Gaussian Distributions in Sparsely-Connected Factor Graphs by Tom Yates, Yuzhou Cheng, Ignacio Alzugaray, Danyal Akarca, Pedro A.M. Mediano, Andrew J. Davison (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-21935.txt.

Introduction

Tom Yates and co-authors study belief propagation, a workhorse algorithm for drawing conclusions in probabilistic graphical models. The method passes messages between variables until they agree on a joint picture. Exact belief propagation quickly becomes infeasible as models grow, blowing past compute and memory budgets.

Cheaper variants exist, and the most popular one assumes every distribution is locally Gaussian, bell-shaped near each point. The team's 2026 preprint shows that belief propagation itself tends to converge toward Gaussian distributions in sparsely connected factor graphs. That result helps explain why the Gaussian shortcut works as well as it does. And it tells practitioners when the cheap version can stand in for the exact computation.

Catalog record

CREATORTom Yates, Yuzhou Cheng, Ignacio Alzugaray, Danyal Akarca, Pedro A.M. Mediano, Andrew J. Davison
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-21935

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Belief Propagation Converges to Gaussian Distributions in Sparsely-Connected Factor Graphs Tom Yates, Yuzhou Cheng, Ignacio Alzugaray, Danyal Akarca, Pedro A.M. Mediano, Andrew J. Davison Abstract BP ( BP ) is a powerful algorithm for distributed inference in probabilistic graphical models, however it quickly becomes infeasible for practical compute and memory budgets. Many efficient, non-parametric forms of BP have been developed, but the most popular is GBP ( GBP ), a variant that assumes all distributions are locally Gaussian. GBP is widely used due to its efficiency and empirically strong performance in applications like computer vision or sensor networks – even when modelling non-Gaussian problems. In this paper, we seek to provide a theoretical guarantee for when Gaussian approximations are valid in highly non-Gaussian, sparsely-connected factor graphs performing BP (common in spatial AI). We leverage the CLT ( CLT ) to prove mathematically that variables’ beliefs under BP converge to a Gaussian distribution in complex, loopy factor graphs obeying our 4 key assumptions. We then confirm experimentally that variable beliefs become increasingly Gaussian after just a few BP iterations in a stereo depth estimation task. † † affiliationnotice: \dagger Co-supervised this work. Figure 1: Along a chain of variables connected with random factors, beliefs become progressively Gaussian. Variable x_{1} has the only unary factor f_{1} and inherits its distribution, but the variable beliefs of x_{2},x_{3} and x_{4} are increasingly Gaussian, demonstrating the CLT ’s influence. 1 INTRODUCTION Recent years have seen a surge in distributed and parallel computing architectures for spatial AI, from multi-core processors and GPUs to large-scale sensor networks and multirobot systems ( 13 ; 23 ) . As problems become more distributed, there is an increasing need for efficient algorithms that leverage local processing to solve global problems without centralized coordination, enabling scalability and resilience in complex environments. BP is one such algorithm for distributed inference, consisting of local message passing where nodes interact only with their neighbours. First formalised as an algorithm for singly connected graphs by ( 19 ) , many more efficient variants of the algorithm have since emerged, such as Expectation Propagation ( 17 ) or Particle Belief Propagation ( 10 ) . GBP ( 26 ) , a variant that assumes all distributions are Gaussian, dramatically improves tractability by efficiently representing beliefs with only their mean and variance. BP ’s existing theory guarantees convergence to the correct posterior mean under strong assumptions, such as Gaussian graphs ( 26 ) or diagonally dominant covariances ( 15 ) . While the validity of assuming all distributions are Gaussian in densely-connected graphs has been studied extensively ( 8 ; 4 ; 16 ) , the same cannot be said of the sparsely-connected graphs common to spatial AI. Despite this, practitioners routinely apply it for highly non-Gaussian robust estimation problems ( 18 ; 9 ) . These examples achieve strong empirical results with little theoretical justification. Our work intends to partially bridge this gap, offering guarantees common to spatial AI in which the Gaussian approximation is valid in highly non-Gaussian problems. We offer a derivation showing that BP ’s variable beliefs converge to Gaussian distributions for non-Gaussian problems with highly uncertain data terms and complex graph topologies. Mathematical proofs and experimental results on a stereo depth estimation task demonstrate that the region of Gaussian convergence is empirically large, and so the Gaussian approximation can be applied to many probabilistic inference problems involving non-Gaussian elements. More specifically, our key contributions are: • Unified Mechanism : We reveal a mechanism by which Gaussian distributions naturally emerge in BP across sparsely-connected graph topologies. • Theoretical Derivation : We provide the first derivation of BP ’s variable beliefs tending to Gaussian distributions in sparsely-connected graphs following Assumptions 1.1 – 1.1 , detailed below. • Empirical Validation : We validate these findings on synthetic and real stereo depth estimation tasks, demonstrating that the Gaussian assumption is valid for large regions of the graph even in non-Gaussian settings. 1.1 Scope & Assumptions Our findings apply to sparsely-connected graphs with a fixed topology implementing synchronous BP . Such graphs are deterministic, so ergodic properties can be dismissed. For our proofs to hold, the graphs must obey: Assumption 1.1 ( Finite moments ). Functions for all factors in the graph have finite moments of all orders. Assumption 1.2 ( Lindeberg Condition ). The sequence of factor potentials along any path satisfies the Lindeberg condition, such that the variance contribution of any single factor asymptotically vanishes relative to the total path’s variance. Assumption 1.3 ( Low-degree factors ). The graph contains only unary and binary factors. Assumption 1.4 ( Shift invariance ). Binary factors f(x_{i},x_{j}) only depend on their corresponding variables via their difference, f(x_{i},x_{j})=g(x_{i}-x_{j}) . Assumptions’ Generality. Assumptions 1.1 & 1.1 hold for almost all physical systems, where sensor limits ensure finite moments and redundancy prevents any single factor from dominating the total uncertainty. Intuitively, assumption 1.1 simply excludes physical scenarios such as a broken sensor with variance orders of magnitude larger than its neighbours, which would drown out the smoothing effect of convolution and prevent Gaussian convergence. While assumptions 1.1 & 1.1 appear restrictive, they cover the vast majority of spatial AI problems. Regarding assumption 1.1 , ( 20 ) showed that linear high-degree factors (ternary or more) can be exactly decomposed to unary/binary factors. Assumption 1.1 is stated for Euclidean vector spaces ( x_{j}-x_{i} ), but generalizes to Lie groups (e.g. SO(3) , SE(3) ) via left-invariant potentials which map to vector addition in the Lie Algebra (tangent space) ( 24 ) . Consequently, our results extend to the relative pose factors common in SLAM (see Appendix A ). Many spatial AI problems can be formulated as graphs satisfying these assumptions, including image pixel estimation, robot odometry localisation, and networks of range-only sensors. 2 KEY INTUITIONS Our work provides a theoretical validation of GBP ’s Gaussian assumption in uncertain regions of sparsely-connected, non-Gaussian graphs that follow assumptions 1.1 – 1.1 . This encourages the use of GBP over more expensive non-parametric methods like Particle-based BP ( 10 ) in such regions. Figure 1 highlights a toy example of variable beliefs converging to a Gaussian distribution for a set of variables x_{1}\;...\;x_{4} linked in a chain-shaped factor graph. This is a simple but common set-up in engineering, that could for example represent tracking the position over time of a mobile robot with noisy odometry sensors. Under a set of reasonable assumptions (detailed in Section 1.1 ), we prove that BP messages converge to a Gaussian distribution in long chains. This is because message passing at factors is equivalent to convolution, and by the CLT repeated convolution will drive distributions to a Gaussian in the asymptotic limit as path length from the closest data source (prior factor) tends to infinity. Given tree and loopy graphs under our assumptions can be unwrapped as convolutional chains interspersed by multiplication, we extend this idea to trees and loopy graphs by showing that multiplication doesn’t reduce Gaussianity in a “near-Gaussian” basin of attraction, and so near-Gaussian BP messages converge to a Gaussian distribution. Empirically, Section 5 then validates this convergence mechanism across a range of topologies, exploring the convergence rate, influence of node degree and prior factor uncertainty. This

Read the complete text