2026-10-01
Recasting nonlinear recurrences as quadratically convergent fixed-point iterations with parallel scans speeds GRU evaluation up to 500x and training 10-22x with unchanged outputs.
RNNs and Neural ODEs are inherently serial along the time axis: step t needs step t-1, so the massive parallel throughput of GPUs sits idle. Transformers displacing RNNs in language modeling owed much to parallel training, and linear recurrences such as S4 and LRU were parallelized over sequence length via prefix scan, but nonlinear recurrent units (LSTM, GRU) still had to run one step at a time. On long-sequence tasks this serial rollout became the training bottleneck and locked classical architectures out of modern experimentation.
DEER (non-linear Differential Equation as fixed point itERation) rewrites the recurrence as a fixed-point iteration in which every operation is parallelizable.
The same framework covers discrete recurrences like GRU and ODEs, with no special structure required from the model. The only added hyperparameter is the convergence tolerance (1e-4 suffices in float32).
On a V100 with a GRU (sequence length 1M, hidden size 1, batch 16): sequential evaluation took 8.7 s, DEER took 15 ms, a speedup above 500x; forward plus gradients exceeded 1000x; batch size 2 exceeded 2600x. Outputs agree with sequential evaluation to float32 precision.
| Task | Result |
| Two-body Hamiltonian NN (10k points) | 11x faster than RK45; 55k steps in 1d6h vs 2 weeks |
| EigenWorms (17,984 steps) GRU | 22x faster training (>1 day to 1 hour), 88.0% accuracy |
| EigenWorms LEM replication | 92.3%, on par with original; 18s vs 116s per epoch |
| Sequential CIFAR-10, multi-head GRU | 90.25%, best among nonlinear recurrent units |
Speedups shrink as hidden size grows: only about 25% at n=64, since explicit Jacobians and matrix products cost O(n^3). A multi-head scheme (256 channels split into 32 heads of 8 channels with exponentially increasing strides) works around that wall at the price of shorter effective sequences and a reduced speedup of roughly 3x.
It breaks the assumption that nonlinear recurrences cannot be parallelized over time, with zero intrusion into the architecture. Training 10-22x faster on long sequences converts directly into experiment throughput: the 88% GRU result on EigenWorms came out of rapid hyperparameter exploration, restoring classical recurrent units to competitiveness on benchmarks they had been priced out of. Neural ODE settings such as physical system identification benefit equally.
Newton's caveats carry over: iterates started far from the solution may diverge, and globally convergent variants are left to future work. O(n^2) memory and O(n^3) compute cap the hidden size, which the authors concede limits scalability. The implementation leans on associative scan, which had no convenient PyTorch equivalent at the time, so all experiments live in the JAX ecosystem. Reviewers flagged thin task coverage, and the CIFAR-10 study was added during rebuttal. All headline speedups come from small hidden sizes; implications for large models are not discussed.