Recurrent neural networks (RNN)

The Elman recurrence#

Elman (1990), Finding structure in time, defines the standard form:

h_t = φ( W_hh · h_{t−1}  +  W_xh · x_t  +  b_h )
y_t = W_hy · h_t + b_y

x_t ∈ R^d is the input at step t, h_t ∈ R^m the hidden state, φ an elementwise non-linearity (tanh classically), and W_hh ∈ R^{m×m}, W_xh ∈ R^{m×d}, W_hy ∈ R^{k×m} the shared parameters. The Jordan variant feeds back y_{t−1} instead of h_{t−1}.

Parameter count is m² + md + m per layer and is independent of sequence length T. This weight sharing across time is the direct analogue of a CNN's weight sharing across space, and it is what makes variable-length input tractable.

Backpropagation through time, and why it fails#

Unrolling for T steps gives a feedforward network of depth T with tied weights. Werbos (1990) formalised BPTT. The gradient of the loss at step T with respect to an early state factorises:

∂L_T / ∂h_t  =  ∂L_T / ∂h_T  ·  Π_{k=t+1..T}  ∂h_k / ∂h_{k−1}

∂h_k / ∂h_{k−1}  =  diag( φ'(a_k) ) · W_hh

a_k is the pre-activation at step k. The product of T − t Jacobians is the whole problem. Bounding its norm:

‖ ∂h_k / ∂h_{k−1} ‖  ≤  γ · ‖W_hh‖ ,      γ = sup |φ'|

γ = 1 for tanh and 0.25 for the logistic sigmoid. Bengio, Simard and Frasconi (1994) showed that if the largest singular value of W_hh satisfies σ_max < 1/γ, the product contracts geometrically and long-range gradients vanish. If the spectral radius exceeds 1/γ the product can diverge, and gradients explode.

The trap is that these are the same condition seen from two sides. Pascanu, Mikolov and Bengio (2013) state it directly: a vanilla RNN cannot both store information stably over long spans and receive usable long-range gradient, because stable storage requires contraction and gradient flow requires none.

Practical consequences, all standard:

• Gradient clipping by global norm handles the explosion half. It does nothing for vanishing.
• Truncated BPTT backpropagates only k steps, trading long-range credit assignment for bounded memory. Memory during BPTT is O(T · m) for stored activations, which is the real constraint on T.
• Orthogonal or identity initialisation of W_hh places the spectrum on the unit circle at the start. Le, Jaitly and Hinton (2015) showed an identity-initialised ReLU RNN competing with LSTMs on long-dependency tasks.

Gated cells#

LSTM (Hochreiter and Schmidhuber, 1997) introduces an additive cell state c_t:

c_t = f_t ⊙ c_{t−1}  +  i_t ⊙ g_t
h_t = o_t ⊙ tanh(c_t)

f_t, i_t, o_t ∈ (0,1)^m are the forget, input and output gates, g_t the candidate update, and ⊙ elementwise product. The gradient path through c_t is multiplication by f_t rather than by W_hh with a saturating derivative. With f_t ≈ 1 the path is close to the identity, so gradients survive far longer. Gers, Schmidhuber and Cummins (2000) added the forget gate; initialising its bias to 1.0 is a standard and genuinely useful trick.

GRU (Cho et al., 2014) merges the cell and hidden state and drops one gate, giving roughly 25% fewer parameters. Greff et al. (2017), LSTM: A Search Space Odyssey, ran a large ablation and found no variant reliably beating the standard LSTM, with the forget gate and output activation the components that matter most.

Why transformers displaced them#

The decisive property is not accuracy, it is parallelism.

                     sequential steps   time per layer      inference state
RNN / LSTM           O(T)               O(T · m²)           O(m)
Transformer          O(1)               O(T² · d + T · d²)  O(T · d) KV cache

An RNN's step t cannot begin before step t−1 finishes, so training time scales with T regardless of available hardware. A transformer computes all positions at once, and Vaswani et al. (2017) explicitly cite the number of sequential operations as the design driver. Path length between any two positions is O(1) under attention and O(T) under recurrence, which also removes the vanishing-gradient argument entirely.

The RNN wins on inference state: constant memory per step against a KV cache growing linearly in context length. That is why streaming and on-device workloads never fully abandoned recurrence.

The linear-recurrence revival#

Modern work recovers parallel training by dropping the non-linearity from the recurrence, leaving h_t = A h_{t−1} + B x_t, which is an associative scan and computable in O(log T) depth.

• S4 (Gu, Goel and Ré, 2021) parameterises A with HiPPO structure for principled long-range memory; strong results on Long Range Arena.
• Mamba (Gu and Dao, 2023) makes the state-space parameters input-dependent and supplies a hardware-aware selective scan, reaching transformer-quality language modelling with linear scaling in T.
• RWKV (Peng et al., 2023) formulates a transformer-like model with an RNN inference mode, giving constant-memory decoding.

Whether these match transformers on tasks requiring precise recall of arbitrary earlier tokens remains contested; the compression into a fixed-size state is exactly the constraint attention avoids. Hybrid stacks that interleave recurrent layers with a small number of attention layers currently look like the pragmatic answer.

Papers#

• Elman, Finding Structure in Time, Cognitive Science, 1990.
• Werbos, Backpropagation Through Time: What It Does and How to Do It, Proc. IEEE, 1990.
• Bengio, Simard and Frasconi, Learning Long-Term Dependencies with Gradient Descent is Difficult, IEEE Trans. Neural Networks, 1994.
• Hochreiter and Schmidhuber, Long Short-Term Memory, Neural Computation, 1997.
• Cho et al., Learning Phrase Representations using RNN Encoder-Decoder, 2014 — arxiv.org/abs/1406.1078
• Sutskever, Vinyals and Le, Sequence to Sequence Learning with Neural Networks, 2014 — arxiv.org/abs/1409.3215
• Pascanu, Mikolov and Bengio, On the Difficulty of Training Recurrent Neural Networks, 2013 — arxiv.org/abs/1211.5063
• Greff et al., LSTM: A Search Space Odyssey, 2017 — arxiv.org/abs/1503.04069
• Gu, Goel and Ré, Efficiently Modeling Long Sequences with Structured State Spaces (S4), 2021 — arxiv.org/abs/2111.00396
• Gu and Dao, Mamba: Linear-Time Sequence Modeling with Selective State Spaces, 2023 — arxiv.org/abs/2312.00752

What to learn next#

• LSTM — the gated cell that made long-range memory workable.
• Transformers — the architecture that removed the running memory entirely.
• Attention — letting every position look directly at every other position.