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

Belief Propagation (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 Gaussian Belief Propagation (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 Central Limit Theorem 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.

In robotics and AI, robots and sensors must constantly process messy data to understand their environment. A popular tool for this is "Gaussian Belief Propagation"—an efficient method where different parts of a network of robots or sensors share local clues to reach a collective conclusion. Engineers rely on it because it is fast and runs on low-power hardware, but it assumes the underlying data follows a perfect bell curve (Gaussian distribution) and in reality the data is normally much messier. Our research explains why Gaussian Belief Propagation succeeds anyway. Using a fundamental rule of statistics called the Central Limit Theorem, we prove that as information repeatedly passes through a sparse network, the network's beliefs of its environment naturally smooth out into a bell curve. This means robots can safely rely on fast, energy-efficient approximations without making major errors.