In probabilistic modeling, we often need to update our beliefs as new information arrives. Whether a robot is receiving a stream of sensor data, a user is interacting with a sketch-recognition interface, or an MCMC sampler is exploring a high-dimensional space, the core challenge remains the same: a small piece of evidence changes, and we need to compute the new posterior distribution.
The naive approach is to reset the system and re-run inference from scratch. In standard Belief Propagation (BP) or Junction Tree algorithms, introducing new evidence typically invalidates existing internal states, triggering a global wave of message passing across the entire network (Alvarado et al., 2005).
However, a single new observation rarely alters the entire world state. Its impact is usually highly localized. Incremental message passing exploits this locality. Instead of global recomputation, it updates existing beliefs by propagating only the "deltas" or restricting message passing strictly to the paths affected by the new data.
Localizing Updates via Tree Topologies
To understand why incremental updates are possible, consider the standard Junction Tree algorithm, which clusters variables into a tree of cliques to maintain global consistency (Andersen et al., 1989). When the tree is "calibrated," neighboring cliques agree on their shared variables.
If we instantiate a single new variable, we do not need to re-calibrate the entire tree. As Yuan et al. (2009) demonstrate, the update can be restricted entirely to the unique path connecting the newly modified cluster to the next variable in the search order. Because the rest of the tree remains structurally decoupled from this local change, the computational bottleneck shifts from the global tree size to the local path distance.
[Clique A] -- (Update Path) -- [Clique B] -- [Clique C]
| |
(New Evidence) (Untouched Subtree)
This path-based restriction is incredibly powerful when evaluating complex logical or relational structures. For example, in Markov Logic Networks (MLNs), counting how many ground formulas are satisfied by a given world state is notoriously expensive. Venugopal et al. (2015) showed that by using calibrated junction trees, a change to a single truth value only requires passing messages along the paths directly affected by that variable. This keeps the cost of updating grounding counts nearly independent of the overall domain size.
By storing message histories, systems can dynamically determine exactly which portions of a belief graph require re-calculation, allowing real-time applications to achieve batch-level accuracy with a fraction of the computational overhead (Triebel et al., 2012).
Short-Circuiting Execution and Sampling
The intuition of local updates extends naturally from exact inference to stochastic sampling methods, such as Gibbs sampling and Markov Chain Monte Carlo (MCMC).
Paskin (2003) elegantly bridged these paradigms by framing Gibbs sampling as a sequential walk through a junction tree. Because a single sampling step only modifies one variable at a time, moving between adjacent clusters requires recomputing exactly one conditional message. This reduces the complexity of a sampling step from linear in the number of clusters to a constant factor.
In Probabilistic Programming Languages (PPLs), execution flows can be highly dynamic, making inference notoriously slow. However, because MCMC proposals typically alter only one variable at a time, the underlying dependency structure changes locally. Li et al. (2016) exploit this by using static analysis to isolate the variables controlling these dependencies, allowing the runtime to incrementally update only the affected parts of the execution trace.
Ritchie et al. (2016) accelerated this process further by combining continuation-passing style (CPS) with callsite caching. When a variable is modified:
- The execution trace "jumps" directly to the modified variable's callsite using cached continuations.
- It executes downstream code until the newly computed values match the previously cached values.
- The moment changes stop propagating, the execution short-circuits and terminates early.
This mechanism turns what would be a linear-time global re-execution into a constant-time local update.
Reusing Compiled Structures and Passing Deltas
Another powerful way to achieve incremental inference is through knowledge compilation, where a network's logical constraints are pre-compiled into a tractable, static circuit like a Reduced Ordered Binary Decision Diagram (ROBDD) or a deterministic Decomposable Negation Normal Form (dec-DNNF).
Once the underlying constraint structure is compiled, changing the probability distributions or adding sequential observations does not require rebuilding the graph. Gupta et al. (2019) demonstrated this in the context of weighted model sampling: if the underlying logical constraints remain fixed, you can adapt to entirely new weight distributions simply by traversing the graph and updating the node annotations incrementally.
This decoupling of structural compilation from numerical evaluation allows subsequent queries to be processed in a fraction of the initial compilation time (Cheng et al., 2024.
[Static Compiled Circuit] <-- Fixed logical constraints
||
[Dynamic Node Annotations] <-- Fast, incremental weight updates
On a hardware level, incremental message passing can also be implemented by changing what messages communicate. Instead of overwriting absolute values (such as absolute log-likelihood ratios), systems can pass deltas—the precise change in reliability or belief. Preyss (2012) leveraged this delta-based feedback mechanism in concurrent MIMO wireless decoding, demonstrating that writing only the updates to a shared memory prevents data corruption and ensures that refinements from different processing units accumulate smoothly.
Whether by restricting paths in a tree, short-circuiting program execution, or updating annotations on compiled circuits, incremental inference shifts the computational burden from the total size of the model to the size of the change.
Key Foundational Work
Probabilistic Information Fusion for Multi-Modal Image Segmentation (1987) — contributed 1 concept elements to this direction.
Incremental Causal Reasoning (1987) — contributed 1 concept elements to this direction.
Propagation of belief functions: a distributed approach (1986) — contributed 1 concept elements to this direction.