Breaking the Sequential Curse: Parallel Newton Methods for Dynamical Systems
I can’t access the web in this environment, but I can write the explainer from the abstract and my knowledge of this research area.
The Sequential Tax on Modern ML
Every transformer you train on a GPU is secretly hiding a dirty secret: attention is embarrassingly parallel across sequence positions, which is why transformers scaled so well. But a large class of models — recurrent neural networks, state-space models with nonlinear dynamics, Markov chain Monte Carlo chains — are fundamentally sequential. Each step depends on the last. You can’t hand step 500 to one GPU core while another handles step 501. On hardware with tens of thousands of parallel compute units, this is not a minor inefficiency; it’s a fundamental mismatch.
This paper, Unifying Optimization and Dynamics to Parallelize Sequential Computation, offers a principled framework for breaking that bottleneck — not by approximating the dynamics, but by reframing evaluation as a root-finding problem and solving it exactly with Newton’s method structured as a parallel associative scan.
Why Associative Scans Are the Key
The parallel prefix scan (or associative scan) is one of the core primitives enabling modern sequence models. Given a binary associative operator ⊕ and a sequence [a₁, a₂, ..., aₙ], it computes all prefix reductions [a₁, a₁⊕a₂, a₁⊕a₂⊕a₃, ...] in O(log n) parallel steps instead of O(n) sequential ones. This is the trick that makes linear RNNs like S4 and Mamba trainable at scale — their recurrence happens to be a linear map, making composition associative and enabling the scan.
The hard problem is nonlinear recurrences. If xₜ = f(xₜ₋₁) and f is nonlinear, composing two steps doesn’t reduce to a fixed-size operation. You can’t precompute “what happens over steps 256–512 regardless of starting state” because the answer genuinely depends on the path.
Newton’s Method as a Parallelism Primitive
The key insight is to stop thinking of sequential evaluation as forward simulation and start thinking of it as constraint satisfaction. Given a sequence of states x₁, ..., xₙ, satisfying the recurrence is equivalent to finding the root of a residual function:
F(x) = 0 where Fₜ(x) = xₜ - f(xₜ₋₁)This is a system of nonlinear equations in all the states simultaneously. Newton’s method solves it iteratively: starting from an initial guess for all states in parallel, each Newton step refines every state at once using the Jacobian of F.
The crucial structural property is that the Jacobian of this block-bidiagonal system is itself amenable to parallel inversion via associative scan. The Newton update at each step requires solving a linear system whose structure mirrors the original recurrence — but linear recurrences are parallelizable. So each Newton iteration does O(log n) parallel work, and you need only a handful of Newton steps for convergence, giving total parallel depth of O(k log n) for k iterations.
Unifying Two Fields
What makes the paper’s framing distinctive is the explicit unification of two literatures that have developed separately: numerical optimization (specifically Newton and quasi-Newton methods) and the theory of dynamical systems and parallel algorithms. MCMC methods, for instance, define a Markov chain where each sample depends on the last — textbook sequential computation. But viewed as a fixed-point problem on the joint distribution of the chain, the same Newton machinery applies. The paper effectively shows that the parallel scan trick for linear RNNs was a special case of a much more general principle: any dynamical system evaluation can be parallelized by solving the implied fixed-point equations with Newton’s method.
This has immediate practical relevance for:
- Nonlinear RNNs like LSTMs and GRUs, which couldn’t benefit from the linear scan tricks behind S4/Mamba
- MCMC inference, where long chains are needed for mixing but each step is cheap — the sequential cost dominates
- Physics simulations and ODEs discretized as recurrences, common in scientific ML
What to Watch For
The framework’s applicability depends on a few conditions worth tracking in follow-on work. Newton’s method requires the Jacobian to be well-conditioned and the initial guess to be in a basin of convergence — neither is guaranteed for arbitrary nonlinear dynamics. Papers building on this will likely focus on preconditioning strategies and warm-starting heuristics to make convergence robust.
There’s also the memory cost: materializing all states simultaneously rather than streaming them sequentially requires O(n) memory in the state dimension. For long sequences with large state spaces, this trades sequential time for parallel memory, which may not always be a favorable trade on current hardware.
The deeper implication is architectural. If nonlinear recurrences become trainable at scale with the same wall-clock efficiency as transformers, the design space for sequence models reopens considerably. The community converged on attention partly because recurrent models didn’t parallelize — that constraint may be weaker than assumed.