Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

Recurrent Networks & LSTMs

Memory over time and the vanishing gradient problem.

A recurrent network with rational weights can simulate any Turing machine, yet a plain RNN trained by gradient descent struggles to remember what it saw fifty steps ago. Both facts are theorems about the same recurrence. This lesson proves them, analyzes how gates repair the gradient, and follows recurrence into its 2020s revival as linear state-space models.

What you’ll learn

  • State the Turing completeness of recurrent networks (Siegelmann & Sontag, 1995) and explain why it depends on unbounded precision.
  • Derive Jacobian bounds for RNN gradients, with the sufficient condition for vanishing and the necessary condition for exploding (Pascanu et al., 2013), and state the latching dilemma of Bengio et al. (1994).
  • Analyze gradient flow through LSTM and GRU cells, the memory time scale 1/(1−f)1/(1-f) and the initialization of forget-gate biases.
  • Explain linear state-space models (S4, Mamba): the convolution view, parallel scans, selectivity, and their known limits as of the mid-2020s.

What recurrent networks can compute

DerivationProof idea: a stack in one number
  1. q=∑i=1m2bi+14i∈[0,1),b1=1  ⟺  q≥34q=\sum_{i=1}^m\frac{2b_i+1}{4^i}\in[0,1),\qquad b_1=1\iff q\ge\tfrac34

    Encode a binary stack b1b2…bmb_1b_2\dots b_m, top first, as a rational number in base 4 that uses only the digits 1 and 3. The encoding is injective, the empty stack is 00, and a stack with b1=0b_1=0 has q<12q<\tfrac12, so the top symbol is read by a threshold:

  2. push b: q↦q4+2b+14,pop: q↦4q−(2b1+1),b1=σ(4q−2)\text{push }b:\ q\mapsto\frac q4+\frac{2b+1}4,\qquad\text{pop}:\ q\mapsto4q-(2b_1+1),\qquad b_1=\sigma(4q-2)

    Push and pop are affine maps, and the threshold is one saturated-linear unit, so each operation takes a few neurons:

  3. tape=stackleft⏟left of the head ∣ stackright⏟head and right\text{tape}=\underbrace{\text{stack}_{\text{left}}}_{\text{left of the head}}\ \big|\ \underbrace{\text{stack}_{\text{right}}}_{\text{head and right}}

    Two stacks hold a Turing machine's tape, one for each side of the head, and the finite control is a small network of threshold units. Composing them gives one fixed rational-weight RNN that runs the machine.

The construction needs unbounded precision: after mm pushes the state must resolve 4−m4^{-m}. With fixed precision every RNN is a finite automaton, so the practical question is what finite-precision RNNs trained by gradient descent actually learn, and there architectures differ. LSTMs learn to count, recognizing languages such as anbna^nb^n with their cell state, while GRUs, whose state is an interpolation confined to [−1,1][-1,1], do not (Weiss, Goldberg & Yahav, 2018).

Gradients through time: Jacobian bounds

Write the recurrence as ht=ϕ(at)\mathbf h_t=\phi(\mathbf a_t) with at=Wht−1+Uxt+b\mathbf a_t=W\mathbf h_{t-1}+U\mathbf x_t+\mathbf b, and let γ=sup⁡∣ϕ′∣\gamma=\sup\abs{\phi'}: γ=1\gamma=1 for tanh and 14\tfrac14 for the logistic sigmoid. The gradient of a loss at time tt with respect to an earlier state passes through a product of Jacobians:

∂ℓt∂hk=∂ℓt∂ht ∂ht∂ht−1⋯∂hk+1∂hk,∂hj∂hj−1=diag⁡(ϕ′(aj)) W\frac{\partial\ell_t}{\partial\mathbf h_k}=\frac{\partial\ell_t}{\partial\mathbf h_t}\,\frac{\partial\mathbf h_t}{\partial\mathbf h_{t-1}}\cdots\frac{\partial\mathbf h_{k+1}}{\partial\mathbf h_k},\qquad\frac{\partial\mathbf h_j}{\partial\mathbf h_{j-1}}=\operatorname{diag}\big(\phi'(\mathbf a_j)\big)\,W
DerivationProof
  1. ∥∂hj∂hj−1∥≤∥diag⁡(ϕ′(aj))∥ ∥W∥≤γλ1\Big\lVert\frac{\partial\mathbf h_j}{\partial\mathbf h_{j-1}}\Big\rVert\le\big\lVert\operatorname{diag}(\phi'(\mathbf a_j))\big\rVert\,\norm W\le\gamma\lambda_1

    The spectral norm is submultiplicative, and ∥diag⁡(ϕ′(aj))∥=max⁡i∣ϕ′(aj,i)∣≤γ\norm{\operatorname{diag}(\phi'(\mathbf a_j))}=\max_i\abs{\phi'(a_{j,i})}\le\gamma:

  2. ∥∂ℓt∂hk∥≤∥∂ℓt∂ht∥ ρ t−k → t−k→∞  0\Big\lVert\frac{\partial\ell_t}{\partial\mathbf h_k}\Big\rVert\le\Big\lVert\frac{\partial\ell_t}{\partial\mathbf h_t}\Big\rVert\,\rho^{\,t-k}\ \xrightarrow{\ t-k\to\infty\ }\ 0

    Multiply the t−kt-k factors. If ρ=γλ1<1\rho=\gamma\lambda_1<1, the gradient of ℓt\ell_t receives exponentially little from distant states and is dominated by short-term terms:

  3. λ1≤1γ⟹∥∂ht∂hk∥≤1for all t>k\lambda_1\le\frac1\gamma\quad\Longrightarrow\quad\Big\lVert\frac{\partial\mathbf h_t}{\partial\mathbf h_k}\Big\rVert\le1\quad\text{for all }t>k

    Conversely, if λ1≤1/γ\lambda_1\le1/\gamma, every factor has norm at most 1 and nothing can grow, so explosion requires λ1>1/γ\lambda_1>1/\gamma. The condition is necessary but not sufficient, because the slopes ϕ′(aj)\phi'(\mathbf a_j) along the trajectory may be small.

Bengio, Simard & Frasconi (1994) showed the problem runs deeper than initialization. To store a bit robustly, a system must keep it in a region of state space where small perturbations die out, an attractor basin, which means ∥∂ht/∂ht−1∥<1\norm{\partial\mathbf h_t/\partial\mathbf h_{t-1}}<1 there. But then the gradient of whatever is stored with respect to inputs far in the past vanishes exponentially: in a plain recurrent network, robust memory and learnable long-range gradients pull in opposite directions. Remedies include gradient clipping for explosions (Pascanu et al., 2013), orthogonal or unitary recurrent matrices that keep λ1=1\lambda_1=1 (Arjovsky, Shah & Bengio, 2016), ReLU RNNs initialized at the identity (Le, Jaitly & Hinton, 2015), and gates.

Check your understanding

An RNN uses the logistic sigmoid (γ=14\gamma=\tfrac14), and its recurrent matrix has largest singular value λ1=3\lambda_1=3. What do Pascanu et al.'s conditions say?

  1. Gradients must explode, since λ1>1\lambda_1>1
  2. Long-term gradients vanish exponentially, since γλ1=34<1\gamma\lambda_1=\tfrac34<1
  3. Gradients are exactly preserved
  4. Nothing: the bounds apply only to tanh
Show the answer

B. Long-term gradients vanish exponentially, since γλ1=34<1\gamma\lambda_1=\tfrac34<1

Each Jacobian factor has norm at most γλ1=0.75\gamma\lambda_1=0.75, so ∥∂ht/∂hk∥≤0.75t−k\norm{\partial\mathbf h_t/\partial\mathbf h_k}\le0.75^{t-k}: vanishing is guaranteed. Explosion would need λ1>1/γ=4\lambda_1>1/\gamma=4.

Gated cells, analyzed

The LSTM cell update ct=ft⊙ct−1+it⊙gt\mathbf c_t=\mathbf f_t\odot\mathbf c_{t-1}+\mathbf i_t\odot\mathbf g_t has the Jacobian

∂ct∂ct−1=diag⁡(ft)+diag⁡(ct−1)∂ft∂ct−1+diag⁡(gt)∂it∂ct−1+diag⁡(it)∂gt∂ct−1⏟through ht−1=ot−1⊙tanh⁡(ct−1)\frac{\partial\mathbf c_t}{\partial\mathbf c_{t-1}}=\operatorname{diag}(\mathbf f_t)+\underbrace{\operatorname{diag}(\mathbf c_{t-1})\frac{\partial\mathbf f_t}{\partial\mathbf c_{t-1}}+\operatorname{diag}(\mathbf g_t)\frac{\partial\mathbf i_t}{\partial\mathbf c_{t-1}}+\operatorname{diag}(\mathbf i_t)\frac{\partial\mathbf g_t}{\partial\mathbf c_{t-1}}}_{\text{through }\mathbf h_{t-1}=\mathbf o_{t-1}\odot\tanh(\mathbf c_{t-1})}
The first term is diagonal and contains no weight matrix. The others pass through ht−1\mathbf h_{t-1} and the gates' weights, like a vanilla RNN's Jacobian, and are often small.

Along the direct path, error from nn steps ahead is scaled elementwise by ∏jfj\prod_j\mathbf f_j. A unit whose forget gate sits at ff forgets geometrically with a time constant of about 1/(1−f)1/(1-f) steps: f=0.99f=0.99 remembers for about 100 steps, f=0.999f=0.999 for about 1,000. A sigmoid gate starts near 12\tfrac12, a memory of a step or two, which is why forget-gate biases are initialized at 1 or more (Gers et al., 2000; Jozefowicz, Zaremba & Sutskever, 2015). Chrono initialization sets bf=log⁡ub_f=\log u with u∼U[1,Tmax⁡−1]u\sim U[1,T_{\max}-1], spreading the units' time scales up to the longest dependency expected (Tallec & Ollivier, 2018).

Predict before you look

A forget gate held at f=0.99f=0.99 multiplies the cell's error signal by ff at every step. After how many steps has the signal fallen to 1/e≈37%1/e\approx37\%?

Show the answer

100

0.99n=enln⁡0.99≈e−0.01005 n0.99^n=e^{n\ln0.99}\approx e^{-0.01005\,n}, so n≈99.5n\approx99.5: about 100 steps, the time constant 1/(1−f)1/(1-f). A vanilla RNN with γλ1=0.9\gamma\lambda_1=0.9 falls to 1/e1/e within about 9.5 steps, even in the best case of its bound.

Large ablation studies found the forget gate and the output activation to be the most critical LSTM components, and no variant consistently better than the standard cell (Greff et al., 2017); GRUs perform comparably on most benchmarks (Chung et al., 2014; Jozefowicz et al., 2015). Gating also changes what is computable at finite precision: unlike a squashing RNN, an LSTM can keep an unbounded counter in ct\mathbf c_t, which is how it learns anbna^nb^n.

State-space models: linear recurrence, revisited

A linear recurrence has no squashing nonlinearity in its state update and can be trained in parallel. Structured state-space models (SSMs) start from a continuous-time system with state s(τ)∈RN\mathbf s(\tau)\in\R^N driven by a scalar input uu, discretized with a step Δ\Delta:

s′(τ)=As(τ)+Bu(τ),  y=C⊤s⟶sk=Aˉsk−1+Bˉuk,  yk=C⊤sk,Aˉ=eΔA\mathbf s'(\tau)=A\mathbf s(\tau)+\mathbf Bu(\tau),\ \ y=\mathbf C^\top\mathbf s\qquad\longrightarrow\qquad\mathbf s_k=\bar A\mathbf s_{k-1}+\bar{\mathbf B}u_k,\ \ y_k=\mathbf C^\top\mathbf s_k,\qquad\bar A=e^{\Delta A}
With a zero-order hold, Bˉ=A−1(eΔA−I)B\bar{\mathbf B}=A^{-1}(e^{\Delta A}-I)\mathbf B; S4 originally used the bilinear transform. A deep SSM runs one such system per channel, with mixing layers in between.
DerivationThree ways to compute the same layer
  1. yk=∑j=0kC⊤Aˉ jBˉ uk−j,Kˉ=(C⊤Bˉ, C⊤AˉBˉ, …, C⊤AˉL−1Bˉ)y_k=\sum_{j=0}^{k}\mathbf C^\top\bar A^{\,j}\bar{\mathbf B}\,u_{k-j},\qquad\bar{\mathbf K}=\big(\mathbf C^\top\bar{\mathbf B},\ \mathbf C^\top\bar A\bar{\mathbf B},\ \dots,\ \mathbf C^\top\bar A^{L-1}\bar{\mathbf B}\big)

    As a convolution. Unrolling the linear recurrence from s0=0\mathbf s_0=\mathbf 0 writes the output as the input convolved with a kernel of powers of Aˉ\bar A, computed once and applied with FFTs in O(Llog⁡L)\order{L\log L} for a sequence of length LL:

  2. per step:  sk=Aˉsk−1+Bˉuk(O(N) for diagonal Aˉ)\text{per step: }\ \mathbf s_k=\bar A\mathbf s_{k-1}+\bar{\mathbf B}u_k\qquad\big(\order{N}\ \text{for diagonal }\bar A\big)

    As a recurrence. At inference, generate one step at a time with an NN-dimensional state: constant cost per token, unlike attention, whose cost per token grows with the context.

  3. (M2,v2)∘(M1,v1)=(M2M1, M2v1+v2)(M_2,\mathbf v_2)\circ(M_1,\mathbf v_1)=\big(M_2M_1,\ M_2\mathbf v_1+\mathbf v_2\big)

    As a parallel scan. Pairs (M,v)(M,\mathbf v) standing for the affine maps s↦Ms+v\mathbf s\mapsto M\mathbf s+\mathbf v compose associatively, so all LL states follow from a prefix scan of depth O(log⁡L)\order{\log L} (Blelloch, 1990; Martin & Cundy, 2018), even when Aˉ\bar A and Bˉ\bar{\mathbf B} change from step to step:

Long memory comes from AA. S4 (Gu, Goel & Ré, 2022) initializes it with HiPPO, a matrix whose state optimally compresses the input history onto Legendre polynomials (Gu et al., 2020), and parameterizes it as normal plus low rank so the kernel can be computed stably. It was the first model to solve the Long Range Arena's Path-X task, with sequences of 16,384 steps. Later work showed that a diagonal AA suffices with the right initialization (S4D; Gu et al., 2022), and that a plain linear recurrence with a stable complex diagonal parameterization matches S4 on these benchmarks (LRU; Orvieto et al., 2023).

Selectivity. A time-invariant SSM applies the same filter to every input, so it cannot decide from content what to remember or ignore. Mamba (Gu & Dao, 2023) makes Δ\Delta, B\mathbf B and C\mathbf C functions of the current input, which breaks the convolution view but keeps the scan; with a hardware-aware scan it trains in time linear in the sequence length and, as of 2024, matched transformers of similar size on language modeling at moderate scales. A selective SSM is again a gated RNN: an input-dependent Δ\Delta in Aˉ=eΔA\bar A=e^{\Delta A} plays the role of a forget gate.

Key takeaways

  • With saturated-linear units and rational weights, a finite RNN simulates any Turing machine by storing stacks in the digits of its state (Siegelmann & Sontag, 1995); with finite precision it is a finite automaton.
  • Gradients through time are products of Jacobians diag⁡(ϕ′)W\operatorname{diag}(\phi')W: ∥W∥<1/γ\norm W<1/\gamma guarantees exponential vanishing, and ∥W∥>1/γ\norm W>1/\gamma is necessary for explosion (Pascanu et al., 2013). In plain RNNs robust memory and long-range gradients conflict (Bengio et al., 1994).
  • LSTM and GRU cells add a diagonal, gated path through time; its memory decays with time constant about 1/(1−f)1/(1-f), which forget-gate biases and chrono initialization control.
  • Linear state-space models compute one layer as a convolution (FFT training), a recurrence (constant-cost inference) or a parallel scan; Mamba's input-dependent parameters restore content-based gating. Such models share transformers' state-tracking limits and copy worse than attention.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Siegelmann and Sontag's RNN simulates any Turing machine. What does the construction require that real implementations lack?

  1. Infinitely many neurons
  2. Unbounded numerical precision in the state, since a stack of depth mm lives in the digits of one rational number
  3. Real-valued weights that encode uncomputable numbers
  4. An activation that is differentiable everywhere
Show the answer

B. Unbounded numerical precision in the state, since a stack of depth mm lives in the digits of one rational number

The network is fixed and finite, with rational weights, but its states must resolve 4−m4^{-m} after mm pushes; with fixed precision every RNN is a finite automaton. Arbitrary real weights would give more than Turing power (P/poly in polynomial time), but the simulation needs only rationals.

Question 2

What dilemma did Bengio, Simard & Frasconi (1994) identify?

  1. RNNs cannot represent functions of long sequences
  2. Backpropagation through time is too slow to compute
  3. Storing information robustly requires contracting dynamics, and contracting dynamics make the gradient with respect to distant inputs vanish
  4. Gradient clipping prevents learning long dependencies
Show the answer

C. Storing information robustly requires contracting dynamics, and contracting dynamics make the gradient with respect to distant inputs vanish

Robust storage means perturbations of the state die out, ∥∂ht/∂ht−1∥<1\norm{\partial\mathbf h_t/\partial\mathbf h_{t-1}}<1 near the stored state, and the gradient with respect to past inputs is a product of such factors, so it vanishes exponentially. Gated cells escape by providing a path with factors near 1 that the gates switch on and off.

Question 3

Why can a time-invariant linear SSM layer be trained without stepping sequentially through the sequence?

  1. Because it has no hidden state
  2. Because it uses attention internally
  3. Because its state is reset at every step
  4. Because its output is the input convolved with the kernel (C⊤AˉjBˉ)j(\mathbf C^\top\bar A^{j}\bar{\mathbf B})_j, computable with FFTs, and more generally because affine maps compose associatively, allowing a parallel scan
Show the answer

D. Because its output is the input convolved with the kernel (C⊤AˉjBˉ)j(\mathbf C^\top\bar A^{j}\bar{\mathbf B})_j, computable with FFTs, and more generally because affine maps compose associatively, allowing a parallel scan

Linearity makes the input–output map a convolution with a fixed kernel, so a length-LL sequence costs O(Llog⁡L)\order{L\log L} with FFTs. When the parameters depend on the input, as in Mamba, the convolution view is lost but the scan remains, with O(log⁡L)\order{\log L} parallel depth.

Question 4

Why are LSTM forget-gate biases often initialized to 1 or more rather than 0?

  1. To make the cell state explode early in training
  2. Because a zero bias makes the gate output 12\tfrac12, a memory of about two steps, while larger biases keep gradients flowing along the cell path over longer spans
  3. To make the LSTM equivalent to a GRU
  4. Because the forget gate is otherwise unused
Show the answer

B. Because a zero bias makes the gate output 12\tfrac12, a memory of about two steps, while larger biases keep gradients flowing along the cell path over longer spans

The error along the cell path is scaled by a product of forget-gate values; at f≈12f\approx\tfrac12 it halves every step. A bias of 1 gives f≈0.73f\approx0.73, and larger biases give longer memories, with time constant about 1/(1−f)1/(1-f), so long-range credit assignment can get started. Chrono initialization spreads the biases to cover a range of time scales.

Further reading

  • H. T. Siegelmann & E. D. Sontag, "On the computational power of neural nets," Journal of Computer and System Sciences 50(1), 132–150 (1995).
  • Y. Bengio, P. Simard & P. Frasconi, "Learning long-term dependencies with gradient descent is difficult," IEEE Transactions on Neural Networks 5(2), 157–166 (1994).
  • R. Pascanu, T. Mikolov & Y. Bengio, "On the difficulty of training recurrent neural networks," ICML (2013).
  • A. Gu, K. Goel & C. Ré, "Efficiently modeling long sequences with structured state spaces," ICLR (2022).
  • I. Goodfellow, Y. Bengio & A. Courville, Deep Learning, ch. 10 (MIT Press, 2016).