Direct Message Approximation (DMA): A Consistency-Based Framework for Tractable Approximate Inference on Factor Graphs

Researchers introduced Direct Message Approximation (DMA), a consistency-based framework that approximates factor-to-variable messages directly on factor graphs rather than approximating marginals as expectation propagation (EP) and variational message passing (VMP) do. The authors prove a master theorem bounding marginal KL divergence from message KL divergence for any graph, with corollaries eliminating EP-style inner-loop iteration and negative-precision messages, plus an O(1/r^2) guarantee for the product factor's improper backward message. They derive explicit DMA messages for the product and leaky-ReLU factors and assemble a Bayesian neural network inference algorithm requiring one forward/backward sweep per training example and no gradient learning-rate hyperparameter, with predictive uncertainty widening in data-sparse regions under model mismatch.

arXiv:2609.29466v1 Announce Type: new Abstract: Approximate message passing on factor graphs underlies two dominant families of probabilistic inference algorithms: expectation propagation EP and variational message passing VMP . Both methods approximate the marginal at each factor edge, forcing an iterative round-robin schedule, risking negative-precision messages, and, for VMP, collapsing to point estimates at Dirac-delta factors. We introduce Direct Message Approximation DMA , which approximates factor-to-variable messages directly rather than the marginal. For normalisable factors, we define a consistency condition requiring exactness when all other incoming messages are Dirac deltas to guide message construction. We prove a master theorem proper messages, any graph bounding marginal KL from message KL, with three structural corollaries: Dirac-input consistency, no EP-style inner-loop iteration, and no negative-precision messages. Further, we prove a complementary $O 1/r^2 $ guarantee for the inherently improper backward message of the product factor, whose closed-form treatment has resisted prior work. As a concrete instantiation, we derive explicit DMA messages for the product and leaky-ReLU factors and assemble a Bayesian neural network BNN inference algorithm with one forward/backward sweep per training example and no gradient learning-rate hyperparameter, validating that the structural guarantees translate to predictive uncertainty that widens in data-sparse regions, including under model mismatch.