2026-10-01
The convergence of DEER-style parallel solvers is governed by the largest Lyapunov exponent: O((log T)^2) total time when negative, exponentially slow for chaotic systems.
DEER and DeepPCR recast the sequential evaluation of nonlinear state space models as a parallel optimization problem: stack the whole trajectory into one variable, minimize the squared residuals of the recursion, and run Gauss-Newton steps whose linear solves are block-bidiagonal systems computable with a parallel scan in O(log T). A cheap step does not make a cheap algorithm, though. The number of optimization steps, governed by the conditioning of that objective, had no theoretical characterization, so whether the approach paid off was a matter of luck. This paper supplies the precise criterion and turns parallelizability into a property you can analyze before running anything.
The bridge is geometric. The merit function satisfies the Polyak-Lojasiewicz (PL) condition, and its PL constant is determined by the smallest singular value of the residual Jacobian. The central theorem proves that this constant is controlled by the largest Lyapunov exponent (LLE) of the dynamics: when lambda < 0 (predictable, perturbations forgotten) it stays bounded away from zero independent of sequence length; when lambda > 0 (chaotic, perturbations amplified) it decays exponentially in T, carving extremely flat valleys into the loss landscape.
The intuition is plain. In a chaotic system, nudge the initial state slightly and the whole future trajectory changes beyond recognition while the residual barely moves, so the optimizer faces a nearly flat plain. Three companion results follow: Gauss-Newton converges globally at a linear rate on this problem structure (Theorem 4, a guarantee plain Gauss-Newton does not enjoy); the basin of quadratic convergence has radius at least 2mu/L, with L the Lipschitz constant of the dynamics Jacobian; and once inside the basin only O(log log(1/eps)) steps remain. Together, predictable systems admit O((log T)^2) total compute.
| Setting (T=30000) | DEER steps |
| Nine dysts chaotic systems, raw | 697 to 30000 (capped) |
| Matching stable observers | 2 to 14 |
| Lorenz system itself (LLE 1.02) | 30000 (capped) |
| Lorenz observer (LLE -6.28) | 3 |
Sweeping the LLE across a family of mean-field RNNs produces a sharp jump in step count precisely at lambda = 0, matching the theory, and the theoretical conditioning measure tracks measured step counts across lambda and T. On an H100, DEER beats sequential evaluation by an order of magnitude in predictable settings and loses by an order of magnitude in chaotic ones. Langevin dynamics in a two-well potential are locally unstable between wells yet have LLE -0.0145 overall, and DEER steps grow only sublinearly with T: what matters is average predictability, not pointwise stability.
First, it gives an a priori test: compute the LLE and you know whether optimization-based parallelization is worth it, which immediately favors strongly dissipative systems common in robotics and control. Second, it instructs architecture design: bake contraction into nonlinear SSMs if you want them parallelizable. Two concurrent efforts are exactly this, with LrcSSM enforcing a contractive parameterization and Danieli et al. training a 7B-parameter language model with DEER by clipping weight-matrix norms. Third, MCMC chains are contractive in many settings and quasi-Newton parallelization over the chain already delivers order-of-magnitude speedups, which this theory explains. The paper also observes that prior work initialized at zero, squarely in the unstable region, pointing to better initializations.
The theory is worst-case and conservative on the chaotic side; the authors add an average-case analysis to compensate. DEER carries a heavy memory footprint, and quasi-Newton variants trade memory for more steps without a quantitative accounting here. Experiments stay on low-dimensional RNN and ODE benchmarks, with language-model-scale evidence borrowed from other work. Estimating the LLE itself is hard in high-dimensional or nonstationary systems, so the practical computability of the criterion deserves more discussion than it gets.