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.
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