# Predictability Enables Parallelization of Nonlinear State Space Models

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 50 of its 103 references that are in the map.
- First posted on arXiv 22 Aug 2025.

## Builds on (most cited first, 30 of 50)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality](https://mlsanity.com/paper/2405.21060/) (2024)
- [Simplified State Space Layers for Sequence Modeling](https://mlsanity.com/paper/2208.04933/) (2022)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Shampoo: Preconditioned Stochastic Tensor Optimization](https://mlsanity.com/paper/1802.09568/) (2018)
- [Scaling up Test-Time Compute with Latent Reasoning: A Recurrent Depth Approach](https://mlsanity.com/paper/2502.05171/) (2025)
- [Resurrecting Recurrent Neural Networks for Long Sequences](https://mlsanity.com/paper/2303.06349/) (2023)
- [Parallelizing Linear Transformers with the Delta Rule over Sequence Length](https://mlsanity.com/paper/2406.06484/) (2024)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024)
- [Hierarchical Reasoning Model](https://mlsanity.com/paper/2506.21734/) (2025)
- [It's Raw! Audio Generation with State-Space Models](https://mlsanity.com/paper/2202.09729/) (2022)
- [Parallelizing Linear Recurrent Neural Nets Over Sequence Length](https://mlsanity.com/paper/1709.04057/) (2017)
- [Parallel Sampling of Diffusion Models](https://mlsanity.com/paper/2305.16317/) (2023)
- [Learning Stable Deep Dynamics Models](https://mlsanity.com/paper/2001.06116/) (2020)
- [Lipschitz Recurrent Neural Networks](https://mlsanity.com/paper/2006.12070/) (2020)
- [Chaos as an interpretable benchmark for forecasting and data-driven modelling](https://mlsanity.com/paper/2110.05266/) (2021)
- [Stable Recurrent Models](https://mlsanity.com/paper/1805.10369/) (2018)
- [Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving](https://mlsanity.com/paper/2002.03629/) (2020)
- [Learning Certified Control using Contraction Metric](https://mlsanity.com/paper/2011.12569/) (2020)
- [Recurrent Equilibrium Networks: Flexible Dynamic Models with Guaranteed Stability and Robustness](https://mlsanity.com/paper/2104.05942/) (2021)
- [Contraction Theory for Nonlinear Stability Analysis and Learning-based Control: A Tutorial Overview](https://mlsanity.com/paper/2110.00675/) (2021)
- [Parallelizing non-linear sequential models over the sequence length](https://mlsanity.com/paper/2309.12252/) (2023)
- [Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexity](https://mlsanity.com/paper/2405.15986/) (2024)
- [Towards Scalable and Stable Parallelization of Nonlinear RNNs](https://mlsanity.com/paper/2407.19115/) (2024)

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

- [ParaRNN: Unlocking Parallel Training of Nonlinear RNNs for Large Language Models](https://mlsanity.com/paper/2510.21450/) (2025)
- [Why Are Linear RNNs More Parallelizable?](https://mlsanity.com/paper/2603.03612/) (2026)
- [Pretraining Recurrent Networks without Recurrence](https://mlsanity.com/paper/2606.06479/) (2026)
- [A Unifying Framework for Parallelizing Sequential Models with Linear Dynamical Systems](https://mlsanity.com/paper/2509.21716/) (2025)
- [Integrative neurocybernetic modeling in the era of large-scale neuroscience](https://mlsanity.com/paper/2604.23903/) (2026)
- [Parallel-in-Time Training of Recurrent Neural Networks for Dynamical Systems Reconstruction](https://mlsanity.com/paper/2605.12683/) (2026)
- [Riccati State Space Models: Non-iterative Parallelization for Nonlinear Sequence Modeling](https://mlsanity.com/paper/2609.35441/) (2026)

## Abstract (arXiv)

The rise of parallel computing hardware has made it increasingly important to understand which nonlinear state space models can be efficiently parallelized. Recent advances like DEER (arXiv:2309.12252) and DeepPCR (arXiv:2309.16318) recast sequential evaluation as a parallelizable optimization problem, sometimes yielding dramatic speedups. However, the factors governing the difficulty of these optimization problems remained unclear, limiting broader adoption. In this work, we establish a precise relationship between a system's dynamics and the conditioning of its corresponding optimization problem, as measured by its Polyak-Lojasiewicz (PL) constant. We show that the predictability of a system, defined as the degree to which small perturbations in state influence future behavior and quantified by the largest Lyapunov exponent (LLE), impacts the number of optimization steps required for evaluation. For predictable systems, the state trajectory can be computed in at worst O((log T)2) time, where T is the sequence length: a major improvement over the conventional sequential approach. In contrast, chaotic or unpredictable systems exhibit poor conditioning, with the consequence that parallel evaluation converges too slowly to be useful. Importantly, our theoretical analysis shows that predictable systems always yield well-conditioned optimization problems, whereas unpredictable systems lead to severe conditioning degradation. We validate our claims through extensive experiments, providing practical guidance on when nonlinear dynamical systems can be efficiently parallelized. We highlight predictability as a key design principle for parallelizable models.