Aligning Divergent Paths in Probabilistic Programs

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 111 papers20 conceptsfrozen 2026-10-04

In a standard deterministic program, the path from input to output is a straight line. In a probabilistic program, that path is a tree. When we run such a program, we are essentially sampling one branch of that tree.

The difficulty arises when we need to compare two different executions. This happens in two major contexts: inference, where we run thousands of parallel simulations (particles) to estimate a distribution, and verification, where we compare a program's behavior on two slightly different inputs to prove properties like differential privacy.

The core problem is that random choices lead to divergent control flows. One execution might take the left branch of an if statement, while another takes the right. One might loop five times, while another loops fifty. This "asynchronicity" makes it nearly impossible to synchronize particles for resampling or to prove that two runs stay "close" to one another.

The Synchronization Barrier

In Sequential Monte Carlo (SMC) inference, we maintain a "swarm" of particles. Periodically, we need to perform resampling: killing off particles with low probability and multiplying those with high probability. For this to work, all particles must be at a comparable point in their execution.

However, as Daniel Lundén, David Broman, and their colleagues point out in Automatic Alignment of Sequential Monte Carlo Inference in Higher-Order Probabilistic Programs, stochastic branching causes particles to reach conditioning points (where weights are updated) at different times. If one particle is deep in a recursive call while another is just starting, resampling them together is like comparing apples to oranges.

To solve this, Lundén and Broman developed automatic alignment. Using static analysis, their system identifies "stable" points in the code that all executions will eventually pass through in the same relative order. By forcing the inference engine to only resynchronize at these aligned points, they ensure that the parallel simulations remain meaningful and accurate, even in complex, higher-order programs.

Coupling: Verification Without Lockstep

A similar problem plagues formal verification. To prove that an algorithm is differentially private, we must show that changing one person's data doesn't significantly change the output distribution. Traditionally, this required "lockstep" execution: assuming both versions of the program follow the exact same path.

But real algorithms diverge. Justin Hsu and Aws Albarghouthi addressed this in Constraint-Based Synthesis of Coupling Proofs. They utilize a technique called coupling, which creates a mathematical correlation between the random choices of two different runs.

Their key insight for handling divergent control flow is to "lift" the random samples. By moving the random choices to the very beginning of the program, the remaining logic becomes deterministic. This decoupling allows them to establish a relationship between the two executions' randomness once at the start, making it irrelevant if the programs later branch into different loop iterations or conditional blocks. In Synthesizing Coupling Proofs of Differential Privacy, they formalize this into Horn Modulo Couplings (HMC), allowing for the first fully automated proofs of complex algorithms like "Sparse Vector."

Shadow Execution and State-Dependent Alignment

Sometimes, the alignment between two runs isn't fixed at the start; it depends on the state of the program as it evolves. Yuxin Wang, Daniel Kifer, and their team introduced shadow execution in Proving differential privacy with shadow execution to handle these cases.

In this framework, a "shadow" program runs alongside the main program. The shadow run uses the same source of random noise but operates on an adjacent dataset. Crucially, the shadow execution is allowed to diverge from the main path. By tracking how the noise is used in both paths, the system can dynamically maintain a "randomness alignment." This allows verifiers to handle algorithms where the privacy proof depends on future queries or branching that only becomes clear during runtime.

The Challenge of Randomized Termination

The most extreme form of divergence occurs when one execution terminates while the other continues indefinitely or for a much longer duration. This is common in algorithms like Stochastic Gradient Descent or systems with randomized waiting times.

In Proving Expected Sensitivity of Probabilistic Programs with Randomized Execution Time, Peixin Wang, Hongfei Fu, and their colleagues tackle this using Ranking Supermartingales (RSMs). Traditionally used to prove that a program will eventually stop, RSMs are repurposed here to bound the "distance" between two non-synchronous executions. By treating the difference between the two program states as a martingale, they can prove that even if the programs diverge in time, their final outputs will remain close in expectation.

Summary

Whether the goal is more efficient inference or automated privacy proofs, the technical frontier is the same: managing divergence. By using static analysis to find alignment points, lifting randomness to decouple it from control flow, or using shadow executions to track state-dependent noise, researchers are turning the "chaos" of stochastic branching into structured, verifiable, and performant systems.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_aligning_divergent_paths_in_probabilisti_633f4c8c,
  title = {Aligning Divergent Paths in Probabilistic Programs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/aligning-divergent-paths-in-probabilistic-programs/rdr_633f4c8cf13d4d7e9e9e61dd61d3bb75},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_aligning_divergent_paths_in_probabilisti_633f4c8c_v1,
  title = {Aligning Divergent Paths in Probabilistic Programs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/aligning-divergent-paths-in-probabilistic-programs/rdr_633f4c8cf13d4d7e9e9e61dd61d3bb75/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}