Belief propagation is a family of algorithms that estimate probabilities on a graph by having neighbouring nodes repeatedly send each other small summaries called messages. When the graph has cycles ("loopy" graphs), the algorithm can oscillate, stall, or waste most of its effort re-sending messages that barely changed. The standard fix, residual belief propagation, keeps a global ranked list of which message changed most and updates that one first. That ranked list is a centralized bottleneck: on parallel or neuromorphic hardware, every processor fights over it. This proposal borrows a tool from control engineering instead. Each edge sends a new message only when its accumulated, unsent change crosses a threshold. The threshold is itself a small dynamical variable that tightens as the local system settles. The whole algorithm is then analyzed as a hybrid system, meaning a system that evolves smoothly between events and jumps discretely at them.
The practical payoff is a single tunable knob that trades communication volume (how many messages the fabric must carry) against time-to-accurate-beliefs, with no shared queue at all. The theoretical payoff is a proof technique for asynchronous message passing on graphs with cycles, at least in the Gaussian case. That technique yields a guaranteed minimum time between an edge's transmissions, which rules out the pathological rapid-fire triggering that has kept event-driven schemes brittle. Because "send only on significant change" is exactly what a spike does, the same scheme gives a spiking implementation of Gaussian belief propagation. Its latency is set by how surprising the evidence is, rather than by long rate-coding windows.
Core Claim
Residual belief propagation (Elidan, McGraw, Koller) already uses the residual $r_{i\to j}=\|m^{\text{new}}_{i\to j}-m^{\text{curr}}_{i\to j}\|$, the gap between the message an edge would send now and the one it last sent. It uses this gap only to rank edges globally. The event-triggered control framework of Postoyan et al. uses the same kind of quantity, the error between the last transmitted state and the current state, to decide locally whether to transmit. It certifies that decision with a hybrid Lyapunov function, an energy-like quantity shown to decrease both during smooth evolution and across jumps.
The claim is that importing the second idea into the first gives a decentralized message-passing scheme with three properties:
- At matched accuracy, it sends substantially fewer messages than residual scheduling.
- It runs faster in wall-clock time than the relaxed multiqueue version of residual scheduling, because it has no queue to contend over.
- For Gaussian models where ordinary Gaussian belief propagation is contractive, it admits a provable convergence rate and a positive minimum inter-event time.
The key new ingredient is the dynamic threshold. A fixed "send if residual exceeds ε" rule is the obvious simpler design, and the proposal is built so that experiments can show whether the dynamic version is actually needed.
Formulation
Each directed edge $i\to j$ carries two quantities: its current internal message $m_{ij}$, and the last value actually transmitted, $\hat m_{ij}$. Receivers compute only with transmitted values. Between events, internal messages relax continuously toward the ordinary belief-propagation update:
$$\dot m_{ij}(t) = F_{ij}(\hat m(t)) - m_{ij}(t).$$
Here $F_{ij}$ is the standard sum-product (or Gaussian) update for edge $i\to j$, evaluated on the transmitted messages $\hat m$. Fixed points of this flow are exactly belief-propagation fixed points.
Discretizing the flow with an Euler step of size 1 recovers plain belief propagation, and smaller steps recover damped belief propagation. Damping is therefore a special case of the scheme, not a separate method.
A transmission event (a jump, $\hat m_{ij}\leftarrow m_{ij}$) fires when the unsent error $e_{ij}=m_{ij}-\hat m_{ij}$ violates
$$\|e_{ij}\|^2 \le \sigma\, \|F_{ij}(\hat m)-\hat m_{ij}\|^2 + \theta\,\eta_{ij}, \qquad \dot\eta_{ij} = -\beta\,\eta_{ij} + \sigma\, \|F_{ij}(\hat m)-\hat m_{ij}\|^2 - \|e_{ij}\|^2.$$
The symbols are:
- $\sigma\in(0,1)$ sets how much unsent error is tolerated relative to the local drive toward the fixed point.
- $\eta_{ij}\ge 0$ is an auxiliary "credit" variable. It accumulates when the edge has been quiet and well-behaved and drains otherwise.
- $\beta>0$ is its decay rate.
- $\theta\ge 0$ scales how much credit may be spent.
This is the dynamic triggering rule of Postoyan et al., transplanted edge-wise. The ratio $\sigma$ plays the role that the control weight $V$ plays in the drift-plus-penalty schedulers of Huang et al.: larger tolerance means fewer transmissions and a looser approximation along the way.
We expect, but must verify, an analogous tradeoff. In that tradeoff, message count falls and convergence time rises as $\sigma\to 1$, and the attainable residual at a fixed message budget scales with the tolerance. This expectation follows from the flow condition, which gives exponential decay at a rate proportional to $1-\sigma$.
Research Program
Gaussian theory. The first component is theory in the Gaussian case. In Gaussian belief propagation, messages are means and precisions and $F$ is affine in the means once precisions converge. We will construct a hybrid Lyapunov function $R(m,e,\eta)$ satisfying the four conditions of Postoyan et al.:
- positive definiteness;
- decrease during flow;
- non-increase across jumps;
- a minimum dwell time between events on each edge.
We will do this under the assumption that synchronous Gaussian belief propagation is a contraction. We deliberately do not claim to settle the open problem, noted by both Elidan et al. and Aksenov et al., of convergence guarantees for asynchronous schemes on general loopy graphs. Our result would extend contraction-based guarantees to decentralized, queue-free event-triggered schedules and add a Zeno-freedom bound, meaning a guarantee against infinitely many events in finite time. That remains a real contribution even in the restricted setting.
Discrete models. For discrete models such as Ising and Potts grids and error-correcting codes, the analysis will be empirical. In the regime where the Bethe free energy (the approximate objective that belief propagation implicitly minimizes) has many poor local minima, Elidan et al. show that no scheduling rule can guarantee a good answer. We will report failures there rather than hide them.
Parallel CPU implementation. Each thread owns a partition of edges and checks triggers locally. Transmissions are written to neighbours' buffers with no priority structure. This implementation is what we compare against the relaxed multiqueue of Aksenov et al..
Spiking implementation. The third component is a spiking implementation of Gaussian belief propagation in which each transmission event is a spike that carries a quantized update. This design follows the observation of Brette et al. that integrate-and-fire neurons are themselves hybrid systems with a flow and a threshold-reset jump. The contrast is with the existing spiking Gaussian belief propagation of Fang et al., which encodes each Gaussian as population firing rates on a fixed grid. That encoding requires long integration windows and fixed bounds on the mean and variance. Our version sends only changes, so quiet evidence costs almost nothing and latency tracks surprise. This is the belief-propagation counterpart of the adaptive early-exit idea of Li et al., but its stopping condition is local and certified rather than a globally tuned softmax threshold.
Baselines
Naive reference: fixed-iteration synchronous belief propagation. This baseline runs synchronous belief propagation, with and without damping, for a fixed number of iterations chosen to match our method's message budget. It is the "do nothing clever" point. Synchronous parallel methods are known to fail entirely on the 1000×1000 Potts grid (Aksenov et al.), so on that grid it mainly calibrates how hard each instance is. Damping is swept over the same grid of values we give our tolerance parameters.
Residual belief propagation. This is Elidan et al., run with a strict priority queue on one core. It is the strongest competitor on message efficiency, because it spends every update on the largest residual. The file's reported figure is that it converged in about 66% of the Ising cases where tree-reweighted propagation failed, and in 7 of 8 protein-interaction networks where other methods failed. To beat it, we must reach the same marginal error with fewer transmitted messages, while matching its convergence rate across instances.
Relaxed multiqueue residual belief propagation. This is Aksenov et al., the strongest competitor on wall-clock time. It reports a 14x speedup over the sequential version on a 72-core Xeon on 1000×1000 Ising grids. We will rerun it on the same machine class, thread counts, graphs, and stopping tolerance. To beat it, we need lower wall-clock time to a fixed marginal error at 72 threads, with no loss in fraction of instances converged.
Static-threshold ablation. This is our own method with $\theta=0$, i.e. a fixed trigger "send if $\|e\|^2 > \sigma\,\|F-\hat m\|^2$" and no credit variable, plus a pure absolute-threshold variant. It isolates the dynamic threshold. Both get the same tuning budget as the full method: an equal number of hyperparameter configurations on held-out instances.
Spiking baseline. This is the rate-coded network of Fang et al.. On the car-tracking benchmark it reports a final posterior mean of 24.804 against the exact Kalman value of 24.419. On Bayesian regression it reports weights of about (1.72, 0.88) against exact values of about (1.74, 0.87). To beat it, we need posterior error at or below theirs with fewer spikes and fewer simulated time steps.
Tree-sampling reference. On the 5G cell-identity instance PCI_INSTANCE_1, we include the spanning-tree method of From Fields to Random Trees. It reports final energy of about 84k, in fewer than 10 iterations, against about 372M for stalled loopy and tree-reweighted belief propagation. This is a hard reference that we do not expect to beat on energy. It shows where message passing of any schedule is the wrong tool.
Why not just…?
Why not just use residual belief propagation with a relaxed multiqueue? The multiqueue already removes most contention, and on graphs with uniform difficulty it may be nearly as good as our method. Our argument is that residual scheduling always updates something next, even when every residual is tiny, and still needs a shared structure touched on every update. An event-triggered rule can go fully silent on settled regions and needs no shared structure. Whether this matters in practice is exactly what the 72-thread wall-clock comparison and the message-count comparison decide. If the multiqueue matches us on both, the practical claim fails and only the theory remains.
Why not just use a fixed residual threshold? This is the most serious threat, because it is the obvious design and is nearly free to implement. A fixed threshold either freezes beliefs at an inaccurate state, if it is set too high, or re-sends near-identical messages, if it is set too low. The credit variable is meant to avoid both. The only direct evidence in the file is from control, not inference: the dynamic scheme of Postoyan et al. needed 13.31 executions against 18.47 for a prior static-style event-triggered design and 54.34 for periodic control. That result may not transfer. The ablation, with equal tuning budgets and full message-versus-error curves, settles it. If the static rule matches the dynamic one, we will say so and simplify.
Why not just damp synchronous belief propagation and stop early? Damping is a special case of our flow (Euler step below 1), so it is included automatically. Truncation without adaptivity is known to fail on hard loopy instances like the Potts grid (Aksenov et al.), and the same failure appears for spiking networks (Sun et al.). The comparison at matched message budgets shows whether adaptivity buys anything beyond damping.
Why not just remove the loops with spanning trees? On static energy minimization the tree method wins decisively on the cell-identity instance. However, its effective-resistance reweighting costs $O(MN^3)$ (From Fields to Random Trees), and it is an offline procedure. Our target is streaming and decentralized inference, where evidence changes over time and nodes cannot afford a global recomputation. We therefore treat the tree method as a boundary marker rather than something to argue away.
Proposed Experiments
Discrete benchmarks. These are the 1000×1000 Ising grids with coupling strength swept from easy to near-critical, the 1000×1000 Potts grid, and the (3,6) error-correcting code of size $3\times10^5$ used by Aksenov et al.. Each method is scored on:
- total transmitted messages and wall-clock time to reach a fixed maximum marginal error, measured against a long-run residual-scheduling reference (and against exact marginals on small grids);
- the fraction of instances converged;
- for the code, bit error rate at a fixed message budget.
Gaussian benchmarks. These are random sparse Gaussian models built so that synchronous Gaussian belief propagation is contractive, plus near-boundary cases where it is not. On these we test the theory directly. We check whether measured decay rates respect the predicted bound. We also check whether the minimum observed inter-event time on each edge stays above the derived dwell-time bound, and how both behave as models leave the contractive regime.
Spiking experiments. These reuse the car-tracking and Bayesian regression benchmarks of Fang et al.. We add a loopy extension, a 2D grid-structured Gaussian model, which that work did not attempt. We report posterior error against spike count and simulated time steps.
Decisive checks. Three outcomes decide the claims:
- The full method must trace a message-versus-error curve strictly below the static-threshold ablation on at least the hard Ising and Potts instances. Otherwise the dynamic threshold is not justified.
- It must beat the relaxed multiqueue on 72-thread wall-clock time. Otherwise the practical claim fails.
- On Gaussian models, no edge may ever violate the derived dwell-time bound. A single violation falsifies the proof, not just the tuning.
We will also report where every schedule, ours included, fails on near-critical couplings. That failure regime is predicted by the non-convex landscape analysis in Elidan et al., and it marks the honest limit of what any scheduling rule can do.
References
- Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing
- A unifying Lyapunov-based framework for the event-triggered control of nonlinear systems
- Utility optimal scheduling in processing networks
- Scalable Belief Propagation via Relaxed Scheduling
- Simulation of networks of spiking neurons: A review of tools and strategies
- A Spiking Neural Network Implementation of Gaussian Belief Propagation
- Unleashing the Potential of Spiking Neural Networks with Dynamic Confidence
- From Fields to Random Trees
- Many Eyes, One Mind: Temporal Multi-Perspective and Progressive Distillation for Spiking Neural Networks