Differentiable Systematic Resampling for Variational Sequential Monte Carlo

AI summary

Overview

Research area: Machine learning / probabilistic inference — specifically differentiable resampling for variational sequential Monte Carlo (VSMC), also known as particle-filter-based variational inference for state space models.

Technical level: Advanced. The paper assumes familiarity with particle filters, sequential Monte Carlo, the reparameterization trick, the score-function gradient estimator, evidence lower bounds, and optimal transport.

Scope: One-sentence scope: the paper proposes Differentiable Systematic Resampling (DSR), a temperature-controlled relaxation of systematic resampling that enables gradient flow through the resampling step of VSMC while preserving the cumulative-distribution-function (CDF)-ordered, banded structure of the exact discrete scheme.

Publication details: arXiv:2610.12094v1 [stat.ML], 08 Oct 2026, by Fredrik Cumlin and Saikat Chatterjee, Department of Information Science, KTH Royal Institute of Technology, Stockholm, Sweden. License: CC BY 4.0.

What This Paper Is About

Particle filters estimate hidden states in nonlinear dynamical systems by propagating and reweighting a set of particles, and they periodically "resample" — replacing low-weight particles with copies of high-weight ones. Resampling is inherently discrete, so it blocks gradients, which is a problem for variational sequential Monte Carlo, where the whole filtering recursion must be differentiable for gradient-based learning. The paper's goal is a resampling operation that is smooth and differentiable but still behaves like systematic resampling (the standard scheme, favored for its provably lower variance) once training cools down.

Key Contributions

1. DSR itself: a differentiable relaxation that preserves the CDF-ordered, banded structure of systematic resampling while allowing full gradient flow. It softens the CDF-level ancestor assignment using sigmoid functions, leaving the single uniform offset draw untouched.
2. Theoretical guarantees: proofs that DSR converges to exact systematic resampling as the temperature goes to zero, with a pointwise exponential convergence rate for the induced bias under a positive-margin condition.
3. An ordering mechanism: Morton space-filling curve sorting so that neighbours in the CDF are also spatially nearby particles, reducing approximation error to systematic resampling.
4. Empirical results: competitive or superior state estimation and dynamics learning versus existing differentiable resampling baselines, while training more than 2 times faster than entropy-regularized optimal transport (EROT) resampling.

Main Findings

• Exactness in the limit: Proposition 4.1 shows that as the temperature τ → 0⁺, the DSR transport matrix converges to the hard systematic resampling indicator (T_ij → 1(i = a*_j)) and the resampled particle converges to the true ancestor particle, almost surely.
• Exponential bias decay: Proposition 4.2 gives a pointwise bound for τ ≤ τ₀ of the form ||x̃_j − x_{a*_j}||₂ ≤ 2DN exp(−Δ_j/τ), where D is the particle diameter, N the particle count, and Δ_j the margin between the comb point u_j and the nearest CDF boundary. The dominant term is exp(−Δ_j/τ). The bound is pointwise, not uniform: concentrated weights converge fast, while near-uniform weights, where Δ_j scales as O(1/N), bound the worst-case rate.
• Linear Gaussian SSM trade-off: Hard resampling achieved the best training-time posterior (KLD to the Kalman posterior of 17.49 ± 0.07 versus 21.77 ± 0.06 for DSR), yet DSR recovered the true transition matrix most accurately (‖A − Â‖_F of 0.019 ± 0.001 versus 0.035 ± 0.001 for Hard). The paper reads this as evidence that a better training-time posterior does not imply a better gradient signal for parameter learning. DSR also had the best NMSE in that experiment (−11.34 ± 0.01 dB), and EROT the second-best ‖A − Â‖_F (0.022 ± 0.004).
• Lorenz-63 at SMNR = 10 dB: DSR achieved the best NMSE (−29.94 ± 0.28 dB), MSE (0.47 ± 0.24), MSE-5-step (3.38 ± 2.11), log-likelihood (−1.98 ± 0.27) and KLD (3.60 ± 1.04), with low run-to-run variance. Hard was second-best on NMSE (−28.86 ± 0.41 dB) and EROT second-best on MSE-5-step (3.39 ± 2.59).
• Lorenz-63 at the harder SMNR = 0 dB: the gap widened; DSR reached −18.28 ± 0.46 dB NMSE, a 5.7 dB improvement over the second-best method (EROT at −12.57 ± 1.64 dB). DSR's one-step transition-model LL (−3.06 ± 0.24) and KLD (13.41 ± 1.94) were second-best rather than best, which the authors attribute to one-step metrics from true states not capturing error compounding during sequential filtering.
• EROT regularization sensitivity: re-running EROT at ε = 1 stabilized training (MSE-5-step standard deviation dropped to 7.19) and improved its NMSE to −13.47 dB, but DSR still outperformed EROT on every metric.
• Lower, more stable gradients: on Lorenz-63 at SMNR = 10 dB, DSR's mean gradient norm was 4504 with within-epoch standard deviation 2720, versus 17399/17253 for Hard, 17013/8314 for Soft, and 15771/6918 for EROT. DSR's gradient norms were roughly 3 times lower, with within-epoch variance reduced by a similar factor.
• Scaling with particle count: training on Lorenz-63 at SMNR = 10 dB with N ∈ {25, 50, 100, 200}, DSR was the only method that trained stably at every tested N, improving from −29.94 dB at N = 25 to −30.35 dB at N = 200 with run-to-run standard deviation below 0.3 dB. Hard and Soft were competitive at N ≤ 100 but collapsed at N = 200, with NMSE degrading to −20.42 and −21.52 dB and standard deviations above 7 and 12 dB. EROT did not complete at N = 200 because the O(N²) transport matrix combined with 100 Sinkhorn iterations and the autodiff tape over T = 100 time steps exceeded available GPU memory.
• Real handwriting data (CharacterTrajectories): at 10 dB SMNR all differentiable methods were comparable, with DSR marginally best (−15.21 ± 0.15 dB NMSE) ahead of EROT (−14.88 ± 0.17 dB), Soft (−14.69 ± 0.29 dB) and Hard (−14.65 ± 0.20 dB). At 0 dB SMNR, DSR reached −8.59 ± 0.22 dB, a 0.82 dB improvement over EROT (−7.77 ± 1.26 dB), corresponding to a 21% average reduction in MSE.
• Training speed: on Lorenz-63 with an NVIDIA T4 GPU, DSR took 2.55 ± 0.02 hours total (18.39 ± 0.16 s/epoch), adding only 9.6% overhead over Hard (2.49 ± 0.15 h, 17.94 ± 1.11 s/epoch). EROT took 5.96 ± 0.11 h (42.94 ± 0.77 s/epoch), more than 2 times slower, due to its 100 Sinkhorn iterations per resampling step.
• Morton sorting benefit: at N = 200, Morton sorting reduced the L2 distance between DSR and hard systematic resampled particles by 35% compared to random ordering. Filtering and transition model quality benefited modestly at low SNR.
• Known limitation: at finite τ, DSR produces convex combinations of ancestor particles rather than exact copies, which can place mass between modes when the posterior is multimodal — a property EROT shares. Morton sorting partly mitigates this by restricting the soft mixture to spatially nearby particles. On a static bimodal Gaussian (Appendix G), the paper reports that without Morton sorting every resampled particle lands between the modes; the supplied text is truncated at the description of the sorted case.

Methodology in Plain English

Systematic resampling works by building the cumulative distribution function of the particle weights, drawing one random offset, and then laying a uniformly spaced "comb" of points across the probability interval. Each comb point falls between two consecutive CDF values, which identifies one ancestor particle — a hard yes/no threshold decision. The paper relaxes only this threshold step and leaves the random offset untouched.

The trick is to rewrite each hard threshold as the difference of two step functions, and then replace each step function with a sigmoid at temperature τ. The resulting soft assignment weights sum to one after normalization, so each resampled particle becomes a convex combination of ancestor particles and gradients can flow through the weights. Because the softened assignments are banded and ordered like the original CDF, the method retains the structure of systematic resampling rather than replacing it with something diffuse. A single pass of sigmoid evaluations replaces the iterative Sinkhorn solver that optimal-transport-based methods need.

To make the soft mixtures more sensible, particles are sorted along a Morton space-filling curve before building the CDF, so that CDF neighbours are also spatial neighbours. The method is evaluated against three baselines — Hard (standard systematic resampling, which effectively uses only the reparameterization gradient term), Soft (a relaxation of multinomial resampling with α = 0.5), and EROT (entropy-regularized optimal transport with ε = 0.5 and 100 Sinkhorn iterations) — on a 4-dimensional linear Gaussian model, the Lorenz-63 chaotic attractor with a nonlinear 8×8-pixel camera observation model, and the CharacterTrajectories handwriting dataset. Default settings are 25 particles for training, Adam optimization with gradient clipping at norm 5.0, and results averaged over 10 independent runs. Code is available at https://github.com/fcumlin/differentiable-systematic-resampling.git.

Why This Matters

Impact on research. VSMC is a principled way to learn both the transition model and the proposal distribution of a state space model from observations, but its gradient estimator is either biased (when the score-function term is dropped) or high-variance. DSR attacks this bottleneck directly: it keeps the favorable variance properties of systematic resampling, the de facto standard at inference time, and makes the resampling operation trainable without an iterative solver. The paper's finding that a better training-time posterior does not imply a better learned transition model is a useful caution for how the field judges inference quality, and the exponential bias bound gives a concrete handle on how much approximation error the relaxation introduces.

Real-world applications.

• Robotics and navigation, where nonlinear state estimation underpins tracking and control.
• Econometrics and finance, where latent state models are fit to noisy time series.
• Computer vision and tracking, e.g., the camera-style observation model used here.
• Epidemiology, where latent infection-state dynamics must be inferred from partial observations.
• Handwriting and human motion analysis, as demonstrated on the CharacterTrajectories dataset.

Industry relevance. The wall-clock story is the industrial one: DSR adds only 9.6% overhead over non-differentiable systematic resampling, while EROT is more than 2 times slower, and DSR is the only method tested that trains stably all the way up to 200 particles (EROT exhausted GPU memory at N = 200). Systems that need to scale particle counts or run many training jobs benefit from that combination of stability and speed.

Future Directions

• Reducing the O(N²) cost. The paper's Remark 3.1 notes that forming the transport matrix could in principle be truncated to O(NK) by keeping only a band of soft assignments per column, at the cost of a bias that decreases with K. The authors retained the full form because the wall-clock benefit on GPU was

Authors’ abstract

Particle filters are a standard tool for nonlinear state estimation, but their resampling step is discrete, preventing gradient-based learning in variational sequential Monte Carlo. We introduce Differentiable Systematic Resampling (DSR), a temperature-controlled relaxation of systematic resampling, that preserves the CDF-ordered, banded structure of systematic resampling while enabling full gradient flow. DSR converges to exact systematic resampling as the temperature vanishes, and we prove a pointwise exponential convergence rate for the induced bias. Compared to optimal-transport-based differentiable resampling, DSR avoids iterative solvers and has substantially lower computational overhead. Experiments on stochastic dynamical systems and real-world handwriting data show that DSR achieves comparable or superior filtering and dynamics learning performance.