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 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
Encode a binary stack , 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 , and a stack with has , so the top symbol is read by a threshold:
Push and pop are affine maps, and the threshold is one saturated-linear unit, so each operation takes a few neurons:
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 pushes the state must resolve . 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 with their cell state, while GRUs, whose state is an interpolation confined to , do not (Weiss, Goldberg & Yahav, 2018).
Gradients through time: Jacobian bounds
Write the recurrence as with , and let : for tanh and for the logistic sigmoid. The gradient of a loss at time with respect to an earlier state passes through a product of Jacobians:
The spectral norm is submultiplicative, and :
Multiply the factors. If , the gradient of receives exponentially little from distant states and is dominated by short-term terms:
Conversely, if , every factor has norm at most 1 and nothing can grow, so explosion requires . The condition is necessary but not sufficient, because the slopes 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 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 (Arjovsky, Shah & Bengio, 2016), ReLU RNNs initialized at the identity (Le, Jaitly & Hinton, 2015), and gates.
An RNN uses the logistic sigmoid (), and its recurrent matrix has largest singular value . What do Pascanu et al.'s conditions say?
- Gradients must explode, since
- Long-term gradients vanish exponentially, since
- Gradients are exactly preserved
- Nothing: the bounds apply only to tanh
Show the answer
B. Long-term gradients vanish exponentially, since
Each Jacobian factor has norm at most , so : vanishing is guaranteed. Explosion would need .
Gated cells, analyzed
The LSTM cell update has the Jacobian
Along the direct path, error from steps ahead is scaled elementwise by . A unit whose forget gate sits at forgets geometrically with a time constant of about steps: remembers for about 100 steps, for about 1,000. A sigmoid gate starts near , 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 with , spreading the units' time scales up to the longest dependency expected (Tallec & Ollivier, 2018).
A forget gate held at multiplies the cell's error signal by at every step. After how many steps has the signal fallen to ?
Show the answer
100
, so : about 100 steps, the time constant . A vanilla RNN with falls to 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 , which is how it learns .
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 driven by a scalar input , discretized with a step :
As a convolution. Unrolling the linear recurrence from writes the output as the input convolved with a kernel of powers of , computed once and applied with FFTs in for a sequence of length :
As a recurrence. At inference, generate one step at a time with an -dimensional state: constant cost per token, unlike attention, whose cost per token grows with the context.
As a parallel scan. Pairs standing for the affine maps compose associatively, so all states follow from a prefix scan of depth (Blelloch, 1990; Martin & Cundy, 2018), even when and change from step to step:
Long memory comes from . 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 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 , and 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 in 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 : guarantees exponential vanishing, and 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 , 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.
Siegelmann and Sontag's RNN simulates any Turing machine. What does the construction require that real implementations lack?
- Infinitely many neurons
- Unbounded numerical precision in the state, since a stack of depth lives in the digits of one rational number
- Real-valued weights that encode uncomputable numbers
- An activation that is differentiable everywhere
Show the answer
B. Unbounded numerical precision in the state, since a stack of depth lives in the digits of one rational number
The network is fixed and finite, with rational weights, but its states must resolve after 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.
What dilemma did Bengio, Simard & Frasconi (1994) identify?
- RNNs cannot represent functions of long sequences
- Backpropagation through time is too slow to compute
- Storing information robustly requires contracting dynamics, and contracting dynamics make the gradient with respect to distant inputs vanish
- 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, 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.
Why can a time-invariant linear SSM layer be trained without stepping sequentially through the sequence?
- Because it has no hidden state
- Because it uses attention internally
- Because its state is reset at every step
- Because its output is the input convolved with the kernel , 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 , 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- sequence costs with FFTs. When the parameters depend on the input, as in Mamba, the convolution view is lost but the scan remains, with parallel depth.
Why are LSTM forget-gate biases often initialized to 1 or more rather than 0?
- To make the cell state explode early in training
- Because a zero bias makes the gate output , a memory of about two steps, while larger biases keep gradients flowing along the cell path over longer spans
- To make the LSTM equivalent to a GRU
- Because the forget gate is otherwise unused
Show the answer
B. Because a zero bias makes the gate output , 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 it halves every step. A bias of 1 gives , and larger biases give longer memories, with time constant about , 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).