Where Staleness Hurts Linear Recurrent Networks

Recurrent sequence models used to be slow to train because each step had to wait for the previous one. Linear recurrent units (LRUs) remove that wait. They make the hidden-state update linear and diagonal, so a whole sequence can be computed with a parallel prefix sum in logarithmic depth. To get rich features anyway, they stack many such layers with nonlinear blocks between them. Deep stacks like these are natural candidates for pipeline parallelism, which splits the layers across GPUs. The fast version of pipelining is asynchronous: every GPU stays busy, but each gradient is computed with weights that are a step or more out of date. The recent methods that make delayed gradients workable, namely error feedback with the Muon optimizer and Hessian-aligned basis rotation, have been tested only on Transformers and mixtures of experts. Meanwhile LRUs have been trained only synchronously.

We think LRUs break the assumption behind those fixes in one specific place: the recurrence eigenvalues $\lambda = \exp(-\nu + i\theta)$, which set how long each channel remembers. When $\nu$ is close to zero, a tiny step in $\nu$ produces a large change in what the layer computes over a long sequence. A stale update that looks small in ordinary Euclidean distance can therefore be large in function space. Our proposal is to measure staleness for these few parameters in function space, as the change in each channel's impulse response, and to correct only them. The open question is whether this fragile set of parameters is where asynchronous training of deep linear recurrent stacks actually fails.

Core Claim

The claim is a falsifiable prediction plus a targeted fix. The prediction is that under asynchronous pipeline training of a deep LRU stack, most of the loss gap to synchronous training comes from delayed updates to the eigenvalue parameters, not from the much larger set of dense projection weights. The prediction also says how the gap should behave: it should grow with sequence length $L$ and with the layer's memory horizon.

Here is where that scaling comes from. One complex mode contributes the kernel $K_k(\lambda) = \lambda^k$ for $k = 0,\dots,L-1$. Its sensitivity to $\lambda$ is

$$\Big\|\frac{\partial K}{\partial \lambda}\Big\|_1 = \sum_{k<L} k|\lambda|^{k-1} \approx \min\!\Big(\tfrac{L^2}{2},\ \tfrac{1}{(1-|\lambda|)^2}\Big).$$

Because $1-|\lambda|\approx\nu$ when $\nu$ is small, this sensitivity grows roughly like the squared memory horizon $1/\nu^2$, capped by $L^2$. A fixed delay $\tau$ therefore does much more damage to long-memory channels.

This also brings in the hierarchical side of the question. Different layers of a deep stack are expected to settle on different timescales. Earlier pipeline stages suffer larger staleness, an observation made in Mitigating Staleness in Asynchronous Pipeline Parallelism via Basis Rotation. So how much a layer is hurt should depend on two things together: its stage in the pipeline and its learned horizons.

The proposed fix keeps everything that already works for dense weights. Optimizer, error feedback and update rules stay unchanged for them. The only change is to the eigenvalue parameters, where the Euclidean parameter gap is replaced by a kernel gap

$$G = \frac{\|K(\lambda_{t+\tau}) - K(\lambda_t)\|_2}{\|K(\lambda_t)\|_2},$$

where $\lambda_t$ is the value used in the forward pass and $\lambda_{t+\tau}$ is the current value. Both norms have closed forms as geometric series, so computing $G$ is cheap. Stale eigenvalue updates are then damped in proportion to $G$.

Research Program

The work builds on four prior results, each playing a different role.

Resurrecting Recurrent Neural Networks for Long Sequences supplies the architecture. It strips the nonlinearity out of the recurrence, diagonalizes the transition in the complex domain, and parameterizes eigenvalues in polar form. Its evaluation is entirely synchronous, which is the gap we target.

Gap-Aware Mitigation of Gradient Staleness supplies the idea that parameter displacement, not elapsed iterations, should set the penalty. It measures displacement in flat Euclidean coordinates; we keep the principle but change the metric for the parameters where Euclidean distance misleads. The same paper reports that over-penalizing mild staleness slows convergence, so we apply damping only to eigenvalue parameters and only above a threshold on $G$.

One-Step Gradient Delay is Not a Barrier for Large-Scale Asynchronous Pipeline Parallel LLM Pretraining is the main constraint. It shows that error feedback, which re-injects the drift caused by delayed updates into later updates, combined with Muon closes the asynchronous gap for Transformers at a delay of one step. If the same recipe closes the gap for LRUs, our fix is unnecessary.

Basis rotation from Mitigating Staleness in Asynchronous Pipeline Parallelism via Basis Rotation realigns the optimizer's coordinates with Kronecker-factored curvature estimates. That factorization fits dense matrix layers but not diagonal complex eigenvalues, so we use it only as a dense-layer component.

The program has three stages.

The first is a diagnosis on a simulated pipeline. On one machine, we assign each stage $s$ of a $K$-stage pipeline a delay $\tau_s$ that follows an asynchronous schedule; this matches the gradients a real pipeline would produce without the hardware noise. We then run a factorial ablation in which only the eigenvalues, only the dense weights, or both receive delayed gradients. We sweep $K \in \{4, 8, 16, 32\}$ and $L$ from 1K to 16K. We log each layer's horizon distribution and per-layer gap over training to test the predicted dependence on horizon.

The second stage tests the kernel-gap correction, both alone and on top of error feedback with Muon.

The third stage is a real asynchronous pipeline run on GPUs, to confirm that the gains survive actual timing and memory limits. The correction adds only a handful of scalars per channel, unlike the extra parameter copies that weight stashing and error feedback keep.

We deliberately do not claim that asynchrony increases expressive power. The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity proves that selective state-space models and parallel scans sit in the shallow circuit class $\mathsf{TC}^0$. Changing the training schedule does not change the function class, so ListOps appears here as a hard optimization stress test, not as evidence about expressivity.

Baselines

The reference point that costs nothing in quality is synchronous pipeline training with a 1F1B schedule and AdamW. It has no staleness, so it sets the target loss and accuracy, and it pays for that with idle GPU time. In a real asynchronous run we will report wall-clock time against it, at matched model size, data, token count and pipeline depth. The naive point is plain asynchronous AdamW with no correction. We expect it to degrade badly, as it does for Transformers, where basis rotation needed 81.7% fewer iterations than the best asynchronous baseline on a 3B model (Mitigating Staleness in Asynchronous Pipeline Parallelism via Basis Rotation).

The strongest existing competitor is asynchronous training with Muon plus update-level error feedback (One-Step Gradient Delay is Not a Barrier for Large-Scale Asynchronous Pipeline Parallel LLM Pretraining). It reports a final validation loss of 1.906 on a 10B mixture-of-experts model trained on 200B tokens of FineWeb-Edu, identical to its synchronous baseline. That is the most direct evidence that asynchrony can be made free. However, the result is for Transformers at a delay of one step, and no result is reported on Lacuna for this method on linear recurrent or state-space models.

We will run this competitor with the same models, data and token budget as our method. Each method gets the same hyperparameter sweep, eight learning-rate and momentum configurations, tuned on the validation split. Our method counts as beating it if, at delays of two or more steps or at $L \geq 4$K, it closes at least half of the remaining gap to synchronous training without extra memory, across three seeds.

On Long Range Arena (LRA) the synchronous reference is the LRU's 94.2% on Path-X (Resurrecting Recurrent Neural Networks for Long Sequences). No per-task ListOps number for the LRU is reported on Lacuna, so we will reproduce one.

Two further baselines test the method rather than the field. Euclidean Gap-Aware damping applied to the same eigenvalue parameters (Gap-Aware Mitigation of Gradient Staleness) isolates the kernel metric. If it matches our method, the contribution reduces to "damp eigenvalues," and the metric adds nothing. A per-group learning-rate reduction on the eigenvalues, with the factor tuned by the same sweep, isolates whether any staleness-dependent correction is needed at all.

Why not just…?

Why not just use error feedback with Muon, which already solved this for Transformers? This is the real threat, and the first experiment is built to settle it. If error feedback with Muon matches synchronous training on LRU stacks across the full range of $K$ and $L$, we report that as a positive transfer result and drop the correction. Our reason to expect a residual gap is that error feedback corrects drift additively, in the same coordinates in which drift is measured. Where sensitivity grows like $1/\nu^2$, the leftover drift may still matter. The published evidence covers only fixed one-step delays, so this is untested.

Why not just lower the learning rate on the eigenvalue parameters? It is cheap and may capture much of the benefit. But a fixed factor cannot follow horizons that change during training and differ across layers and stages. It also slows learning of short-memory channels that are not at risk. The per-group learning-rate baseline, tuned to the same budget, measures exactly how much of the gain survives without the kernel gap.

Why not just stay synchronous? Asynchronous execution was 1.1x to 1.9x faster than 1F1B and DualPipe at pipeline depth 16 (One-Step Gradient Delay is Not a Barrier for Large-Scale Asynchronous Pipeline Parallel LLM Pretraining). Decoupled execution gave a 3.32x speedup for ResNet-101 on four GPUs (Accumulated Decoupled Learning with Gradient Staleness Mitigation for Convolutional Neural Networks). We will report wall-clock time to target loss, so if synchronous training wins on time, that will show up.

Why not just accumulate gradients per module, as in decoupled learning? Module-wise accumulation in Accumulated Decoupled Learning with Gradient Staleness Mitigation for Convolutional Neural Networks cuts staleness by up to 75% when accumulating over four steps. It does so by enlarging the effective batch, which affects every parameter equally. We include it at the accumulation step that gives matched staleness to check whether a uniform fix is enough.

Proposed Experiments

The models are LRU stacks of 12 to 48 layers. They will be trained on three groups of tasks:

  • Long Range Arena tasks, specifically ListOps, sequential CIFAR-10 and Path-X (Long Range Arena: A Benchmark for Efficient Transformers), reporting accuracy;
  • WikiText-103 language modeling, reporting perplexity;
  • a FineWeb-Edu subset (FineWeb), reporting validation loss and steps and wall-clock time to target loss.

The decisive check is the factorial ablation from the first stage. The idea is supported only if three things hold. First, delaying the eigenvalue parameters alone reproduces most of the asynchronous gap. Second, that gap grows with $L$ and with depth, and is largest on Path-X at 16K. Third, the per-layer kernel gap $G$ predicts which layers' delayed updates hurt the loss, better than Euclidean displacement or the delay $\tau$ do.

If delaying the dense weights accounts for the gap instead, the hypothesis is wrong and the existing Transformer fixes should transfer as they are. We will report that outcome as the result.

A secondary check repeats the 32-stage scaling test from Mitigating Staleness in Asynchronous Pipeline Parallelism via Basis Rotation on LRU stacks. There, standard asynchronous pipelining slowed convergence 5.81x on Transformers and basis rotation cut this to 1.27x. We will see whether the eigenvalue parameters account for a comparable slowdown in recurrent models.