Research map / Probabilistic and scientific modeling / Dynamical systems
Predictability Enables Parallelization of Nonlinear State Space Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that the conditioning of the DEER/Gauss-Newton merit function for evaluating nonlinear state space models is governed by the largest Lyapunov exponent, so predictable (contractive) systems parallelize well while chaotic ones converge slowly.
Problem
Parallel evaluation of nonlinear state space models by minimizing a residual-based merit function (DEER/DeepPCR) is only fast if the number of optimization steps is small, but what governs the conditioning of this merit function was unclear.
Approach
Links the PL constant of the DEER merit function to the largest Lyapunov exponent of the dynamics: predictable (negative LLE) systems give well-conditioned merit functions with global linear convergence and O((log T)^2) total time, while unpredictable (positive LLE) systems give exponentially flat, ill-conditioned landscapes.
Key results
- Number of DEER steps shows a sharp threshold at largest Lyapunov exponent = 0 across RNN families, with predictable systems converging quickly.
- On nine chaotic flows from dysts, DEER took 29,000+ steps on the systems but only 2-14 steps on their stable observers (T=30,000).
- DEER is reported to be an order of magnitude faster than sequential evaluation in predictable settings and an order of magnitude slower in unpredictable settings (H100).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the stable observer instead of the system | DEER · ABC | DEER steps: 4243 -> 3 | Helped |
| use the stable observer instead of the system | DEER · Chua's Circuit | DEER steps: 697 -> 14 | Helped |
| use the stable observer instead of the system | DEER · Kawczynski-Strizhak | DEER steps: 29396 -> 2 | Helped |
| use the stable observer instead of the system | DEER · Lorenz | DEER steps: 30000 -> 3 | Helped |
| use the stable observer instead of the system | DEER · Nosé--Hoover Thermostat | DEER steps: 29765 -> 3 | Helped |
| use the stable observer instead of the system | DEER · Rössler | DEER steps: 29288 -> 7 | Helped |
| use the stable observer instead of the system | DEER · SprottB | DEER steps: 29486 -> 2 | Helped |
| use the stable observer instead of the system | DEER · Thomas | DEER steps: 12747 -> 7 | Helped |
| use the stable observer instead of the system | DEER · Vallis El Niño | DEER steps: 30000 -> 3 | Helped |
Surprising findings
- DEER can converge quickly on trajectories that pass through locally unstable regions, as long as the overall LLE is negative (two-well Langevin example).
Limitations
- DEER has a significant memory footprint due to the TD x TD structure
- Quasi-Newton alternatives need more optimization steps
- Theory relies on LLE regularity/burn-in assumptions and a constant chi_w independent of T
Experimental setup
Datasets: dysts
Benchmarks: dysts chaotic flows
Metrics: DEER convergence steps largest Lyapunov exponent PL constant bounds wall-clock time
Baselines: sequential evaluation quasi-Newton DEER gradient descent
Builds on: DEER DeepPCR Newton-Kantorovich theorem
Closest papers by meaning
- Towards Scalable and Stable Parallelization of Nonlinear RNNs (NeurIPS 2024 · similarity 0.86)
- Parallel-in-Time Training of Recurrent Neural Networks for Dynamical Systems Reconstruction (NeurIPS 2026 · similarity 0.86)
- UnHiPPO: Uncertainty-aware Initialization for State Space Models (ICML 2025 · similarity 0.85)
- Autocorrelation Matters: Understanding the Role of Initialization Schemes for State Space Models (ICLR 2025 · similarity 0.85)
- The Power of Second Order Methods for Sequence Preconditioning (NeurIPS 2026 · similarity 0.85)
- Tight Time Complexities in Parallel Stochastic Optimization with Arbitrary Computation Dynamics (ICLR 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.