Research map / Time series / Causal and generative time series
Parallelizing non-linear sequential models over the sequence length
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.
Proposes DEER, a Newton-style fixed-point framework that rewrites non-linear sequential models (RNNs, NeuralODEs) as parallelizable linear recurrences solved with parallel prefix scan, giving large GPU speedups over sequential evaluation.
Problem
Non-linear sequential models such as RNNs and Neural ODEs must be evaluated serially over sequence length, making training on long sequences slow.
Approach
Restate the non-linear recurrence/ODE as a fixed-point iteration equivalent to Newton's method (quadratic convergence); each iteration solves a linear recurrence in parallel with an associative prefix scan, with Jacobians giving the linear operator, and no special architecture structure is required.
Key results
- On a V100, DEER evaluates a GRU with 1M sequence length, batch 16, n=1 in 15 ms versus 8.7 s sequentially (over 500x speedup); forward+gradient speedups exceed 1000x in that setting.
- Training an HNN on a two-body system with 10k time points is about 11x faster than RK45-based training with no significant difference in validation loss.
- GRU on EigenWorms (17,984 steps) reaches 88.0% accuracy and trains up to 22x faster than sequential; multi-head GRU reaches 90.25% on sequential CIFAR-10.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace sequential GRU evaluation with DEER | GRU · 1M sequence length, batch size 16, n = 1, V100 GPU | speedup: over 500 | Helped |
| Use DEER for forward and gradient calculations instead of sequential evaluation | GRU · 1M sequence length, batch size 16, n = 1 | speedup: more than 1000 times faster | Helped |
| Use DEER instead of RK45 for training | HNN NeuralODE · Two-body physical system, validation loss | validation loss | No clear effect |
| Use DEER instead of RK45 for training | HNN NeuralODE · Two-body physical system training | training speed: 11 times faster | Helped |
| Use DEER instead of the sequential method for training | GRU · EigenWorms validation accuracy | accuracy | No clear effect |
| Use DEER instead of the sequential method for training | GRU · EigenWorms training | training speed: up to 22 times faster | Helped |
| Use DEER instead of the sequential method for training | Multi-head GRU · Sequential CIFAR-10 training | training speed: about 3 times faster | Helped |
Surprising findings
- Speedup falls sharply as state dimension grows (only about 25% at 64 dimensions) because the explicit Jacobian and matrix products scale as O(n^3).
- Forward and gradient calculations are faster than forward alone, since the backward pass needs only one inverse linear operator evaluation.
Limitations
- Newton iteration may fail to converge if the initial guess is far from the solution; global convergence is left to future work.
- Memory and compute scale as O(n^2) and O(n^3) in state dimension, so benefits shrink for large hidden sizes.
- Only one hyperparameter (tolerance), but the method is implemented in JAX because PyTorch lacks easy custom associative scan.
Experimental setup
Datasets: EigenWorms (UEA) sequential CIFAR-10 two-body gravitational system (synthetic)
Benchmarks: EigenWorms sequential CIFAR-10 two-body HNN training
Metrics: speedup classification accuracy validation loss output difference
Baselines: sequential GRU evaluation RK45 ODE solver ODE-RNN NCDE NRDE UnICORNN LEM S4 LSSL Liquid-S4 LRU
Builds on: Newton's method parallel prefix scan DEQ multiple shooting method Hamiltonian Neural Networks
Closest papers by meaning
- Parallelizing Linear Recurrent Neural Nets Over Sequence Length (ICLR 2018 · similarity 0.89)
- Convolutional Sequence to Sequence Learning (ICML 2017 · similarity 0.89)
- FlashRNN: Unlocking Parallel Training of Nonlinear RNNs for Large Language Models (ICLR 2026 · similarity 0.89)
- Parallel-in-Time Training of Recurrent Neural Networks for Dynamical Systems Reconstruction (NeurIPS 2026 · similarity 0.88)
- Harnessing Manycore Processors with Distributed Memory for Accelerated Training of Sparse and Recurrent Models (AAAI 2024 · similarity 0.86)
- Sequence Accumulation and Beyond: Infinite Context Length on Single GPU and Large Clusters (AAAI 2025 · similarity 0.86)
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.