# On backward smoothing algorithms

arXiv: https://arxiv.org/abs/2207.00976 · HTML: https://mlsanity.com/paper/2207.00976/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jul 2022.

## Built on by (most cited first, 7 of 7)

- [Sequential Monte Carlo for Policy Optimization in Continuous POMDPs](https://mlsanity.com/paper/2505.16732/) (2025)
- [Recursive Nested Filtering for Efficient Amortized Bayesian Experimental Design](https://mlsanity.com/paper/2409.05354/) (2024)
- [A State-Space Perspective on Modelling and Inference for Online Skill Rating](https://mlsanity.com/paper/2308.02414/) (2023)
- [Risk-Sensitive Stochastic Optimal Control as Rao-Blackwellized Markovian Score Climbing](https://mlsanity.com/paper/2312.14000/) (2023)
- [Recursive Learning of Asymptotic Variational Objectives](https://mlsanity.com/paper/2411.02217/) (2024)
- [Auxiliary MCMC and particle Gibbs samplers for parallelisable inference in latent dynamical systems](https://mlsanity.com/paper/2303.00301/) (2023)
- [Nonlinear Bayesian Estimator for Parameter Learning: A Fixed-Point Characterization](https://mlsanity.com/paper/2606.10111/) (2026)

## Abstract (arXiv)

In the context of state-space models, skeleton-based smoothing algorithms rely on a backward sampling step which by default has a mathcal O(N2) complexity (where N is the number of particles). Existing improvements in the literature are unsatisfactory: a popular rejection sampling -- based approach, as we shall show, might lead to badly behaved execution time; another rejection sampler with stopping lacks complexity analysis; yet another MCMC-inspired algorithm comes with no stability guarantee. We provide several results that close these gaps. In particular, we prove a novel non-asymptotic stability theorem, thus enabling smoothing with truly linear complexity and adequate theoretical justification. We propose a general framework which unites most skeleton-based smoothing algorithms in the literature and allows to simultaneously prove their convergence and stability, both in online and offline contexts. Furthermore, we derive, as a special case of that framework, a new coupling-based smoothing algorithm applicable to models with intractable transition densities. We elaborate practical recommendations and confirm those with numerical experiments.