Parallelizing Sequential Sampling for High Dimensional Inference

251 concepts208 papers1 proposal

The fundamental challenge in Bayesian inference and generative modeling is that our most reliable tools—Markov Chain Monte Carlo (MCMC) and Sequential Monte Carlo (SMC)—are inherently serial. In a standard MCMC chain, the state at time $t+1$ is a stochastic function of the state at time $t$. This creates a "sequential bottleneck": while modern hardware like GPUs can perform millions of operations in parallel, a sampling chain must wait for each step to finish before beginning the next.

As David M. Zoltowski et al. observe in Parallelizing MCMC Across the Sequence Length, this linear time complexity relative to chain length prevents us from fully leveraging distributed computing. Recent research has focused on breaking this dependency by reframing sampling not as a serial walk, but as a parallelizable optimization or a fixed-point problem.

From Serial Walks to Parallel Picard Iterations

One of the most promising ways to bypass the sequential bottleneck is to treat the entire sampling trajectory as a single object to be optimized. In Langevin dynamics, we typically update a position $x$ by following the gradient of a log-density plus some noise. Instead of computing these steps one by one, Nima Anari and Thuy-Duong Vuong propose using Picard iterations in Fast parallel sampling under isoperimetry.

The intuition is similar to solving a differential equation: if you have an initial guess for the entire path of the sampler, you can refine all points along that path simultaneously. Huanjian Zhou and Masashi Sugiyama further refined this in Parallel simulation for sampling under isoperimetry and score-based diffusion models, showing that a "diagonal-style" parallel iteration can reduce the number of sequential rounds from linear to logarithmic relative to the dimension $d$. By updating the whole sequence in parallel, the wall-clock time scales with $\log d$ rather than $d$, effectively turning a "slow" sequential process into a high-speed parallel one.

Breaking the Resampling Barrier

In Sequential Monte Carlo (SMC) or particle filtering, the bottleneck is not just the temporal dependency, but the resampling step. To prevent "particle degeneracy"—where a few particles carry all the mathematical weight while others become useless—the algorithm must periodically stop and redistribute particles based on their weights.

As Christian A. Naesseth et al. explain in Elements of Sequential Monte Carlo, this resampling requires global communication. Every particle must know the weights of every other particle to determine its survival. This creates a synchronization barrier that halts parallel execution.

To solve this, researchers have looked toward hybrid models. Alexander G. D. G. Matthews et al. introduced CRAFT in Continual Repeated Annealed Flow Transport Monte Carlo, which uses Normalizing Flows to "transport" particles between distributions. By learning a deterministic transformation that moves particles toward high-probability regions, the authors reduce the frequency of global resampling, allowing for smoother parallelization across distributed nodes.

Exploiting Local Independence and Subspaces

When the target distribution has a specific structure, such as a graph or a grid, we can use local independence to update multiple variables at once. The authors of Parallel Gibbs Sampling: From Colored Fields to Thin Junction Trees demonstrate this through "Chromatic sampling." By coloring a graph such that no two adjacent nodes have the same color, all nodes of the same color can be updated in parallel because they are conditionally independent given their neighbors.

For problems where the parameter space is too vast for simple coloring, subspace acceleration offers a path forward. Johnathan M. Bardsley et al. show in Scalable optimization-based sampling on function space that by identifying a low-dimensional subspace where the data is most informative, one can perform complex updates in parallel while maintaining stability in infinite-dimensional spaces.

Sampling as Root-Finding

Perhaps the most radical departure from sequentiality is treating the MCMC chain as a fixed-point solution to a nonlinear recursion. David M. Zoltowski et al. argue that if we view the entire sequence of states as a vector, the MCMC transition rule defines a system of equations. By applying a parallelized Newton’s method to solve these equations, they achieve sublinear time complexity in chain length. This approach shifts the burden from the CPU's serial clock speed to the GPU's parallel throughput, allowing for speedups of over an order of magnitude.

By moving away from the "one step at a time" mindset, these methods—ranging from Picard iterations to parallelized root-finding—are transforming sampling from a serial bottleneck into a scalable engine for high-dimensional science.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 216 papers
  2. Version 1 · 2026-10-04 · 302 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_sequential_sampling_bottleneck_262efca6,
  title = {sequential sampling bottleneck},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-sampling-bottleneck/rdr_262efca6f1d14d96af7d5fda5b046012},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_sequential_sampling_bottleneck_262efca6_v2,
  title = {sequential sampling bottleneck},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-sampling-bottleneck/rdr_262efca6f1d14d96af7d5fda5b046012/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake