Multiple-Shooting Training for Dense Nonlinear RNNs

Recurrent networks with a nonlinearity inside the update, such as LSTMs and GRUs, track state well. They can count parity, compose permutations, and follow high-dimensional body motion. They are slow to train because step $t$ cannot start until step $t-1$ finishes. The parallel alternatives drop something important. Linear state-space models (recurrences with no nonlinearity, computable by a parallel prefix scan) give up the ability to track state. The best nonlinear parallel solver restricts each hidden unit to update from itself only, so channels no longer mix within the recurrence. We propose to train unmodified, fully dense nonlinear RNNs in parallel with an idea borrowed from numerical ODE solving called multiple shooting. The sequence is cut into chunks. Every chunk runs the exact nonlinear cell from a guessed starting state, all chunks at once. A Newton correction then repairs the guessed boundary states with a linear scan over only $L/B$ chunk boundaries, where $L$ is sequence length and $B$ is chunk length. Because the scan runs over few boundaries rather than every token, it can afford full $d \times d$ Jacobians for hidden size $d$, and those products are dense matrix multiplications that suit GPU hardware.

This is a direct meeting point of two lines of work. Hierarchical temporal partitioning, the nesting of a timeline into coarse and fine intervals, becomes the structure of the solver rather than a fixed architectural stack. The sequential bottleneck is attacked without changing the model being trained. The method also has a useful safety property. After $k$ Newton iterations the first $k$ chunks are exactly correct, so in the worst case it falls back to sequential execution at chunk granularity instead of diverging.

Core Claim

Chunk-level Newton shooting can train dense LSTMs and GRUs to the same solution as sequential unrolling, in a few iterations, with wall-clock speedups at long sequence lengths. Because the cell is left unrestricted, it should recover the state-tracking and high-dimensional accuracy that both linear hierarchical state-space models and diagonal-Jacobian parallel RNNs lose.

The target failure is concrete. HiSS stacks a fast low-level state-space model under a slow high-level one. It improves median MSE by 23% over flat Mamba/S4 on CSP-Bench, yet it loses to a plain sequential LSTM on the 60+-dimensional TotalCapture task. The file reports no number for that gap, so no reported result was found on Lacuna for TotalCapture MSE. Our reading is that this gap is the price of linearity at high dimension, and we test it directly.

Relation to Prior Work

Three parallel-recurrence methods motivate and constrain the design.

ParaRNN is the closest method. It solves the whole-sequence nonlinear system by Newton's method over every token, converging in about 3 iterations and reaching speedups of up to 665× for GRUs. It reports 100% parity accuracy where Mamba-2 struggles. It must use diagonal or block-diagonal Jacobians to keep the per-token scan cheap, and it lacks convergence guarantees for general cells. We differ in the unit of the Newton system. Our unknowns are $L/B$ boundary states rather than $L$ token states, which is what makes dense Jacobians affordable. The within-chunk computation is an exact nonlinear rollout, not a linearization.

BPPSA supplies part of the method. It shows that backpropagation is itself a scan over transposed Jacobians. We use the same observation to compute gradients at the converged solution with one transposed boundary scan.

Transformers are SSMs supplies the hardware argument. Its SSD algorithm tiles sequences into flat chunks so that work within a chunk is matrix multiplication and state passes between chunks, running 2–8× faster than Mamba's scan. Our chunk boundaries play the same hardware role, but the cross-chunk quantity is a Newton correction to a nonlinear state rather than a linear state.

Two slicing approaches are the natural foils. Sliced RNNs run nonlinear cells on independent slices in parallel and reach 136× speedups at length 32,768. They cut state flow at slice boundaries and pass information only upward. HiSS does the same with linear models. Our method with zero Newton iterations and zero initial boundary guesses reduces to this slicing regime. Each added iteration restores the true boundary coupling, so the ablation between them is built into the method.

Two papers constrain the design. The circuit-complexity analysis of SSMs places selective SSMs in $TC^0$, a class of shallow parallel circuits, so they cannot solve $NC^1$-hard problems such as permutation composition. This is why we keep the nonlinear cell exact rather than design a new linear hierarchy. Nonlinear RNNs as a Compute Shortcut shows that a single sLSTM layer near the input recovers about 75% of hybrid gains, and that a 10M hybrid beats a pure baseline given 4× more compute. It still runs that layer sequentially, and our method could parallelize exactly that layer.

Research Program

We need two pieces of notation. Let $F_k(s)$ be the state reached by running the nonlinear cell over chunk $k$'s $B$ inputs from starting state $s$. Let $s_k$ be the guessed state at the end of chunk $k$. The true trajectory satisfies $s_k = F_k(s_{k-1})$. Linearizing around the current guesses gives the Newton correction

$$\delta_k = J_k\,\delta_{k-1} + \big(F_k(s_{k-1}) - s_k\big), \qquad J_k = \partial F_k / \partial s \,\big|_{s_{k-1}},$$

where $\delta_k$ is the correction to $s_k$. This is a linear recurrence over $L/B$ elements with dense $d \times d$ matrices, so an associative scan solves it in $O(\log(L/B))$ matrix-multiply steps.

One iteration has three stages. First, all chunks roll out in parallel for $B$ steps, carrying the $d \times d$ tangent matrix that yields $J_k$. Second, a boundary scan computes the corrections. Third, the guesses are updated. Parallel depth per iteration is about $B + \log(L/B)$, and choosing $B$ near $\sqrt{L}$ balances the two terms. Carrying the full tangent costs $O(Bd^3)$ per chunk, all in matrix multiplications. For large $d$ we will test a matrix-free variant that uses a few Jacobian-vector products per boundary with a Krylov solve (an iterative method that needs only matrix-vector products). This is the main engineering risk.

The hierarchy enters in two ways. First, the scheme recurses: boundary states of chunks can themselves be grouped into super-chunks and shot, which gives a $k$-level temporal tree. Second, initial guesses come from coarse to fine. A cheap linear surrogate, for instance a linearized cell or an LRU-style model as in Resurrecting RNNs, predicts boundary states first. Newton then refines them.

The analysis will prove the finite-termination property. It will also measure how iteration count depends on the cell's contractivity, on $B$, and on training progress, since warm-starting from the previous minibatch's solution may help. Finally, it will characterize when dense Jacobians are ill-conditioned, for example saturated gates in long chunks, and whether damping is needed.

Baselines

The naive reference is the same dense LSTM or GRU unrolled sequentially with a fused cuDNN kernel. It defines both the target accuracy, since our method must match it to numerical tolerance, and the speed floor. It also covers the "do nothing" option: at short sequence lengths it may simply win on wall-clock, and we will report the crossover length honestly.

The strongest competitor on speed with nonlinearity is ParaRNN with its diagonal ParaGRU and ParaLSTM cells. It reports 7B-scale SlimPajama perplexities of 9.19 and 9.16, against 8.62 for Mamba-2, along with 665× and 447× speedups. It is the right comparison because it is the only existing method that trains nonlinear RNNs in parallel. We run it at matched parameter count, data, GPU type, and hyperparameter search budget. We beat it if the dense cells trained our way reach lower error on TotalCapture and on permutation composition at comparable wall-clock. If diagonal cells tie dense ones everywhere, our method's reason to exist shrinks to the guarantee property.

The strongest hierarchical competitor is HiSS, which reports a 23% median MSE improvement over Mamba/S4 on CSP-Bench and about 75% lower MSE than a causal Transformer on Marker Writing. We run it with its per-dataset chunk sizes and the same tuning budget. Beating it means matching it on low-dimensional CSP-Bench tasks and clearly beating it on TotalCapture.

Mamba-2 and LRU serve as linear parallel references. LRU reports 94.2% on Path-X in Resurrecting RNNs.

Two ablations isolate the key ingredients. Zero-iteration shooting, which is SRNN-like slicing with cut boundaries, isolates boundary coupling. Diagonal-Jacobian shooting isolates the value of dense mixing.

Why not just…?

Why not just use ParaRNN with diagonal cells? This is the real threat. Diagonal recurrences may be expressive enough once stacked with dense layers between them, and ParaRNN already reports 100% parity. Parity, however, needs only a sign flip per unit. Permutation composition on five elements and 60-dimensional body tracking need within-step cross-channel mixing. The decisive test is dense versus diagonal cells under our solver and under ParaRNN, at matched parameters and wall-clock, on those two tasks. If diagonal cells match dense ones, we will say so.

Why not just run a sequential LSTM, which already beats HiSS on TotalCapture? For sensor windows of a few thousand steps, cuDNN may be fast enough, and we will report exactly where it stops being so. The claim is not that sequential training fails at those lengths. The claim is that it becomes the bottleneck at 16K–64K steps and in pretraining, and that our method returns the identical model faster there. Matching loss curves to numerical tolerance is the check.

Why not just add one sequential sLSTM layer to a Mamba-2 backbone? The compute-shortcut result says this recovers most hybrid gains cheaply. The two ideas are compatible, and we test them together. We parallelize that sLSTM layer with our solver and measure throughput. We also compare the hybrid to an all-dense-RNN model on permutation composition and GIFT-Eval.

Why not just slice like SRNN or HiSS and skip Newton? This is our zero-iteration ablation. If boundary coupling does not matter on a task, the curve of accuracy against iteration count will be flat and we will report that. On state-tracking tasks, where the state must cross chunk boundaries exactly, we expect a sharp gain after the first few iterations.

Proposed Experiments

We will run synthetic state tracking first: parity and permutation composition at lengths 1K–64K. We measure accuracy, Newton iterations to reach $10^{-6}$ relative residual, and wall-clock versus cuDNN and ParaRNN.

Second, we will run CSP-Bench (Marker Writing, RoNIN, VECtor, TotalCapture) with MSE against HiSS, Mamba, LSTM, and ParaLSTM. TotalCapture is the decisive dataset.

Third, we will run LRA ListOps and Path-X, reusing evaluation scripts such as mala-lab/SEMPO, to check long-range memory against the reported 94.2% LRU Path-X result. We will also run GIFT-Eval zero-shot forecasting with CRPS and rank, against the sLSTM-hybrid setup.

The decisive checks are three. Converged solutions must match sequential training in loss and final metrics. Iteration counts must stay small, around 3–8, rather than approaching $L/B$ during real training. Dense cells must beat diagonal ones on TotalCapture and permutation composition at matched compute. If iteration counts grow toward $L/B$, the method reduces to sequential training with overhead, and we will report that as a negative result.