Which Recurrent Normalizations Survive a Parallel Scan?

Recurrent networks and state space models carry a memory vector forward one step at a time. Two practical problems follow. The size of that vector tends to drift, collapsing toward zero or blowing up over long sequences. And the step-by-step loop is slow to train. The usual fix for drift is to rescale the state at every step, as layer normalization does. That fix makes training slower, because it has to run inside the loop. The usual fix for speed goes the other way. It rewrites the recurrence as a parallel scan, an algorithm that combines $T$ steps in about $\log T$ rounds, and that rewrite needs the recurrence to be linear. As a result, practitioners currently treat stability and parallel speed as a trade-off.

This note argues that the trade-off is partly an artifact of where the rescaling is placed. It proposes to measure exactly how much of it is real. Write a linear recurrence in homogeneous coordinates, where the input bias becomes an extra constant coordinate of the state. Dividing that whole extended state by a scalar at every step leaves its direction unchanged, so the computation stays exactly scannable. We call this projective normalization. It is mathematically equivalent to running the unnormalized linear recurrence and normalizing only the output. Its value is numerical: the model can carry expanding modes over long horizons in low precision without overflow. Normalizations that rescale the memory but not the fresh input, such as layer normalization inside the loop, are genuinely different dynamics and cannot be scanned exactly. The research question is how much accuracy that non-scannable remainder actually buys.

Core Claim

Consider a linear recurrence $h_t = A_t h_{t-1} + b_t$, where $A_t$ is the (possibly input-dependent, typically diagonal) transition and $b_t$ is the injected input. Augment the state as $z_t = [h_t; w_t]$, where $w_t$ is the extra constant coordinate, and write the step as

$$z_t = \frac{M_t z_{t-1}}{\|M_t z_{t-1}\|}, \qquad M_t = \begin{bmatrix} A_t & b_t \\ 0 & 1 \end{bmatrix}.$$

Because the divisor is a scalar, $z_t$ equals the normalized product $M_t \cdots M_1 z_0 / \|M_t \cdots M_1 z_0\|$. The combine operation on pairs (normalized matrix, accumulated log-norm) is therefore associative, so a parallel scan computes it exactly.

For diagonal $A_t$, each prefix product keeps the form "diagonal plus one column." Each combine then costs the same order as a standard diagonal state space scan. The scan also yields the log-magnitude $\ell_t = \log\|M_t\cdots M_1 z_0\|$ for free. We expose this log-magnitude to the readout alongside the direction $z_t$. This matters because a direction-only readout would behave like $x/\sqrt{1+x^2}$ and saturate, erasing the "diverging at different rates" information that Demystifying the Token Dynamics of Deep Selective State Space Models argues is useful.

We make the following claims about this construction:

  • Exact equivalence. In real arithmetic the model is exactly a linear recurrence followed by a readout of the pair (direction, log-norm).
  • Numerical headroom. In bfloat16 it stays finite for eigenvalues above one and for horizons where a naive scan overflows or underflows.
  • Conjectured boundary. Among scalar divisive normalizations of affine recurrences, only the projective ones are exactly scannable. Every other choice, including in-loop layer normalization, puts fresh input and renormalized memory on different scales. That is precisely the part that changes the dynamics and forces sequential execution.

The easy direction of the conjecture is the equivalence just shown. We will attempt the converse formally and test it empirically either way.

Prior Work and Where It Sits

Several papers motivate the gap. Recurrent Batch Normalization makes batch normalization work inside LSTMs, using per-time-step statistics and small scale initialization. Layer Normalization removes the batch dependence by normalizing across features. Both keep a reduction inside the loop at every step. Recurrent Normalization Propagation quantifies the cost of that reduction: 413 s per epoch against 530 s for layer norm and 545 s for batch norm on Penn Treebank. It avoids the cost with fixed analytic scale constants, which cannot adapt to input-dependent transitions. We instead keep an adaptive, data-dependent scale that costs one scalar per scan combine.

Stabilization of recurrent neural networks through divisive normalization shows that divisive gain control keeps recurrences stable beyond spectral radius one. We ask which divisive schemes also permit parallel training.

Other papers constrain the design. Demystifying the Token Dynamics of Deep Selective State Space Models finds that states either collapse or diverge. Avoiding collapse improves WikiText-103 perplexity from 17.28 to 16.66. The same paper notes that layer normalization distorts these dynamics. This is the regime where running expanding modes without overflow could matter.

Parallel Layer Normalization for Universal Approximation plays two roles. It shows that grouped normalization acts as an S-shaped nonlinearity of the form $x/\sqrt{x^2+1}$, which is exactly what our direction readout computes per group. It also supplies the natural knob for group size, that is, how many state channels share one normalizer.

Two papers supply methods. BPPSA: Scaling Back-propagation by Parallel Scan Algorithm supplies scan-based backpropagation, reporting up to 108x backward and 2.75x end-to-end speedups on vanilla RNNs. Q-Delta: Beyond Key–Value Associative State Evolution supplies the chunkwise-parallel Triton kernel pattern we build on. Q-Delta gets stability from contraction rather than explicit normalization.

The research file claims that in-loop normalization "breaks the associativity" BPPSA needs. We think that claim is imprecise, and we correct it. Any Jacobian chain is associative, so BPPSA's backward scan still applies once forward states exist. What layer normalization actually destroys is the Jacobian sparsity BPPSA relies on, because it couples all units, and it keeps the forward pass sequential. Our construction addresses both, but only for linear recurrences. Gated nonlinear cells are outside its reach.

Research Program

The program has three parts.

The first part is theoretical. We will try to prove the characterization above. We will also derive how the gradient behaves through the normalized readout, which is well defined because the log-scale is tracked explicitly rather than recovered by division.

The second part is a kernel. We will write a chunkwise Triton implementation of the projective scan for diagonal-plus-column prefix products. Each chunk stores a normalized product and a scalar log-norm, and the backward pass is the reverse scan of the same operator. We will measure its throughput against an ordinary diagonal scan. The target is near-parity, since the only extra work is one norm per combine.

The third part is a controlled comparison. The same recurrent layer is trained under five treatments: no normalization, projective scan, sequential in-loop layer norm, recurrent batch norm, and a norm penalty. The comparison runs across tasks chosen to separate numerical headroom from genuine dynamical benefit.

Baselines

Naive reference. The do-nothing reference is the same diagonal linear recurrence scanned in the ordinary way, in bfloat16. Transition eigenvalues are constrained below one in magnitude and a layer norm is applied only to the output. This is the common design in modern state space layers. It is the most important competitor because, in exact arithmetic, it spans nearly the same function class as our method. Beating it means one of two things. Either it matches accuracy while tolerating eigenvalues above one and longer horizons without non-finite values, or it improves accuracy where the eigenvalue constraint bites.

Strongest accuracy baseline. This is sequential in-loop normalization. We run a layer-normalized recurrence following Layer Normalization and the per-step batch normalization of Recurrent Batch Normalization. The latter reports 95.4% on permuted MNIST and 1.32 bits per character on Penn Treebank. Both are run with the same state size, data, and hyperparameter search budget as our model, using a fused sequential kernel so the speed comparison is not strawmanned. "Beating" this baseline has two meanings. On speed, we must be faster at equal accuracy. On accuracy, a gap within noise supports the claim that the non-projective remainder is unnecessary. A persistent gap is itself a finding: it would locate where input-gain control truly matters.

Static-scaling baseline. Recurrent Normalization Propagation represents static analytic scaling. It reports 413 s per epoch on Penn Treebank. No reported result found on Lacuna for its perplexity as a number in this file.

Penalty baseline. Regularizing RNNs by Stabilizing Activations David Krueger adds a norm-change penalty. It reports that stabilized networks run to 10,000 steps on the adding task after training on 50, and that Penn Treebank bits per character improve from 1.47 to 1.39. This penalty is scan-compatible, so we run it on the ordinary scan with the same tuning budget.

Ablations. Three ablations isolate the key ingredients. The first removes the log-norm readout, leaving the direction only. The second forbids eigenvalues above one inside the projective scan. The third varies group size, from single channels to the full state.

Why not just…?

Why not just normalize the output of an ordinary linear scan? This is the real threat, because our model is mathematically that design plus a log-magnitude readout. The difference exists only where the ordinary scan's finite precision fails, or where contractive constraints hurt. The Vo et al. perplexity gap between eigenvalue regimes suggests such regimes exist, but it does not show they need overflow protection. The naive-reference comparison under bfloat16 at long horizons, with eigenvalue constraints both on and off, settles this directly. If output normalization matches us everywhere, we will report that projective normalization adds nothing beyond numerics, and that the in-loop remainder is the only open question.

Why not just add Krueger's norm penalty? The penalty is cheap and changes nothing in the forward graph. It discourages norm drift but cannot prevent overflow of a mode that the task drives to grow. It also adds a tuning coefficient that its authors note slows training when set large. We run it alone and combined with the projective scan. If the penalty alone reaches the same length-extrapolation curve on the adding task, the kernel is unnecessary.

Why not just fuse layer norm into a fast sequential kernel? A fused loop removes launch overhead but keeps $T$ dependent steps. The Norm Prop timings show the per-step reduction alone costs roughly a quarter of epoch time on Penn Treebank at short lengths, and the depth gap grows with $T$. We measure wall-clock time against sequence length for both kernels. The crossover length tells practitioners when the scan pays off.

Why not just run the scan in fp32 or log space? Pure log-space scans handle positive diagonal decay but not sign changes or the additive input term. fp32 postpones overflow rather than removing it. Our (direction, log-norm) representation is effectively the correct log-space scan for affine recurrences. We include an fp32 ordinary scan to show how much of the benefit it recovers.

Proposed Experiments

Adding task. Train at length 50 and test at lengths up to 10,000, matching Krueger's protocol. We report accuracy against test length and the rate of non-finite values against eigenvalue bound and precision.

Permuted MNIST. The goal is to match 95.4% at 784 steps, recording time per epoch.

Penn Treebank characters. We report bits per character and seconds per epoch. The reference points are 1.32 bits per character, and 413 s versus 530 s per epoch.

WikiText-103. We use a small selective state space model with the projective scan replacing the standard one, and ask whether it reproduces or exceeds the 16.66 perplexity regime while allowing expanding modes.

S-NIAH-3. The 4K needle retrieval task tests whether log-magnitude readout preserves retrievable memory. The reference is Q-Delta's 48.0 against GatedDeltaNet's 21.4, and we run it at matched small scale rather than claiming parity.

Decisive checks. There are two. First, on the task where the projective scan is most stable, it must reach within noise of the naive reference's accuracy at equal eigenvalue constraints, confirming the equivalence and exposing any kernel error. Second, sequential in-loop layer norm either does or does not beat the projective scan once the tuning budget is matched. Beating it everywhere would mean that fresh-input-versus-memory gain control is the ingredient that matters. The next step would then be to find a cheap, approximately scannable form of that gain control rather than more normalization engineering.