De-Sequentialized Monte Carlo: a parallel-in-time particle smoother

Adrien Corenflos, Nicolas Chopin, Simo Särkkä

Abstract

State-space models (SSMs) are fundamental to time-series analysis, yet their inference via Sequential Monte Carlo (SMC) methods is traditionally constrained by a linear time complexity $O(T)$. This sequential bottleneck prevents full utilization of modern parallel hardware like GPUs. We present de-Sequentialized Monte Carlo (dSMC), a novel particle smoothing algorithm that breaks this dependency. By employing a divide-and-conquer tree structure, dSMC achieves $O(\log T)$ time complexity, enabling significant speedups and mitigating the "genealogy degeneracy" common in sequential filters.

Introduction

Sequential Monte Carlo (SMC) methods, such as particle filtering and smoothing, are the standard for hidden state estimation in noisy systems. However, the "sequential" nature of these algorithms is a major limitation: observations must be processed one by one, scaling linearly with the time horizon $T$. While increasing the number of particles ($N$) can be parallelized, parallelizing across the time dimension has remained a challenge. Furthermore, standard smoothers often suffer from degeneracy, where the estimated path for early time steps becomes increasingly inaccurate as more data is processed.

Methods: Divide-and-Conquer Smoothing

The core innovation of dSMC is the reimagining of smoothing as a recursive stitching problem rather than a serial process.

Tree-Based Architecture

Instead of a linear pass, dSMC constructs a binary tree over the time interval $[0, T]$. The algorithm computes partial smoothing distributions for small temporal blocks and recursively merges them. This structure allows nodes at the same depth to be processed independently and simultaneously on parallel hardware.

Extracted figure from page 7 of De-Sequentialized Monte Carlo: a parallel-in-time particle smoother

Parallel-in-Time (PIT) Execution

By reducing the "span complexity"—the longest chain of dependent operations—from $O(T)$ to $O(\log T)$, dSMC can leverage the massive thread counts of modern GPUs. To maintain efficiency and reduce variance, the authors introduce:

  • Conditional dSMC (c-dSMC): An adaptation for Particle Gibbs sampling to estimate unknown model parameters.
  • PIT Gaussian Proposals: Parallelized Kalman-style approximations that guide particles toward high-probability regions.
  • Lazy Resampling: A rejection-resampling technique that avoids the $O(N^2)$ memory cost of weight matrices, keeping memory usage linear with respect to the number of particles.

Results and Performance

The algorithm was evaluated on several statistical benchmarks, including Poisson-AR(1) models, the Theta-Logistic model for population dynamics, and constrained random walks.

  • Execution Speed: In the Theta-logistic model experiment ($T=120$), obtaining $10^5$ samples from a Gibbs chain took only 480 seconds with c-dSMC, compared to 4,083 seconds for standard bootstrap cSMC—a nearly 10x speedup.
  • Scalability: Testing on an Nvidia RTX 3090 confirmed that dSMC scales logarithmically for small to medium $T$. While it eventually reverts to linear scaling once GPU thread capacity is saturated, it remains consistently faster than sequential baselines like Forward Filtering Backward Sampling (FFBS).
  • Homogeneous Error Profile: Unlike standard SMC, where ancestors at $t=0$ are resampled $T$ times (leading to total diversity loss), dSMC resamples each time step at most $\lceil \log_2 T \rceil$ times. This results in a more uniform error profile across the entire trajectory.

Discussion

The transition from $O(T)$ to $O(\log T)$ scaling represents a significant shift in how we approach time-series inference. While dSMC relies on independent proposals for different time blocks—which can increase variance in highly "sticky" systems—the massive speedup allows researchers to use significantly more particles to compensate.

Future work may explore pathwise proposals to further reduce variance and ensemble techniques to refine parallel resampling. By breaking the sequential bottleneck, dSMC opens the door for real-time, high-fidelity inference on massive datasets that were previously computationally prohibitive.

Summary updated

Abstract

Particle smoothers are SMC (Sequential Monte Carlo) algorithms designed to approximate the joint distribution of the states given observations from a state-space model. We propose dSMC (de-Sequentialized Monte Carlo), a new particle smoother that is able to process $T$ observations in $\mathcal{O}(\log_2 T)$ time on parallel architectures. This compares favorably with standard particle smoothers, the complexity of which is linear in $T$. We derive $\mathcal{L}_p$ convergence results for dSMC, with an explicit upper bound, polynomial in $T$. We then discuss how to reduce the variance of the smoothing estimates computed by dSMC by (i) designing good proposal distributions for sampling the particles at the initialization of the algorithm, as well as by (ii) using lazy resampling to increase the number of particles used in dSMC. Finally, we design a particle Gibbs sampler based on dSMC, which is able to perform parameter inference in a state-space model at a $\mathcal{O}(\log_2 T)$ cost on parallel hardware.
BibTeX
@article{corenflos2022de,
  author = {Adrien Corenflos and Nicolas Chopin and Simo Särkkä},
  title = {{De-Sequentialized Monte Carlo: a parallel-in-time particle smoother}},
  journal = {J. Mach. Learn. Res.},
  year = {2022},
  url = {https://openreview.net/forum?id=53DL5TWe8O},
}
Figure