The MLP language model of §3.2 reads a fixed window of $n-1$ tokens with separate weights for each slot. Language does not respect windows. In "the keys that I left on the table by the door last night are gone", the verb agrees with keys, twelve words back, with a singular noun (night) right next to it. A 5-gram model cannot see it, and widening the window means more weights, separate for every position.

Here is a different design. Read the sentence one token at a time, like a person does, and keep a running summary in a vector. At each step, combine the summary so far with the new token to get the next summary, using the same function every time. The summary is a memory of unbounded history, and the parameters do not grow with sentence length. This is a recurrent neural network, the idea Elman (1990) made popular as the simple recurrent network, and the architecture that ruled language modeling from Mikolov et al. (2010) until the Transformer.

§0.8 sketched the recurrence, the product of Jacobians, and the gate in a few paragraphs. This section does it properly. It builds an RNN language model, derives backpropagation through time and checks it numerically, and then does the analysis every interviewer expects, namely why gradients through a recurrence vanish or explode, what the eigenvalues and singular values of the recurrent matrix have to do with it, and how the LSTM and GRU gates fix it. The linear algebra it leans on (eigendecomposition, spectral radius, singular values, and operator norms) is in §0.10.

A recurrent network reads one token at a time

At step $t$ the network looks up the embedding $\mathbf x_t = \mathbf E_{w_t} \in \R^{d}$ of the current token, and updates its hidden state $\mathbf h_t \in \R^{d_h}$,

with $\mathbf W_{hh} \in \R^{d_h \times d_h}$, $\mathbf W_{xh} \in \R^{d_h \times d}$, and $\mathbf b_h \in \R^{d_h}$. To predict the next token it reads the state out through a softmax,

In plain words, the new memory is a squashed mix of the old memory and the new word, and the prediction is read off the memory. The loss is the same next-token cross-entropy as before, summed or averaged over all positions, so a sequence of $T+1$ tokens gives $T$ predictions and one loss.

Unrolled in time, the network is a very deep feed-forward network with one layer per token, and every layer shares the same weights.

 target:      w2          w3          w4
               ↑           ↑           ↑
            softmax     softmax     softmax
               ↑           ↑           ↑
  h0  ──W_hh──▶ h1 ──W_hh──▶ h2 ──W_hh──▶ h3
                ↑           ↑           ↑
              W_xh        W_xh        W_xh
                ↑           ↑           ↑
 input:        w1          w2          w3

A scalar example shows what "memory" means. Take $h_t = \tanh(0.5\, h_{t-1} + x_t)$ and feed in $x = (1, 0, 0, 0)$. Then $h_1 = \tanh(1) = 0.762$, $h_2 = \tanh(0.381) = 0.363$, $h_3 = \tanh(0.182) = 0.180$, and $h_4 = 0.090$. The single input echoes forward, halving at every step because the recurrent weight is 0.5. With a recurrent weight above 1 the echo would grow until the tanh caps it. Keep this picture in mind, because the whole vanishing-gradient story is this echo, run backward.

As in §3.2, the code stores each matrix transposed (Wxh has shape (d, dh)), so that row vectors and minibatches multiply on the left. The equations and the code compute the same thing.

import numpy as np

def rnn_forward(P, ids, h0):
    raise NotImplementedError

Backpropagation through time

To train the RNN we need the gradient of the loss with respect to the shared weights. Unroll the network over the sequence, and it is an ordinary computation graph, so ordinary backpropagation applies. Because the same $\mathbf W_{hh}$ appears at every step, its gradient is the sum of its gradients at every step. This is backpropagation through time (BPTT), named and explained by Werbos (1990).

The only new ingredient is that the hidden state $\mathbf h_t$ influences the loss through two routes, through its own prediction at step $t$ and through the next state $\mathbf h_{t+1}$. So the error arriving at $\mathbf h_t$ is a sum. Let $\mathcal L = \sum_t \ell_t$, write $\mathbf p_t$ for the predicted distribution at step $t$ and $y_t$ for its target (the token $w_{t+1}$), write $\bar{\mathbf h}_t = \partial\mathcal L/\partial\mathbf h_t$ for the error arriving at the state (the adjoint notation of §0.3), and let $\boldsymbol\delta_t$ be the error at the pre-activation inside the tanh. Run the recursion backward from $t = T$ with $\boldsymbol\delta_{T+1} = \mathbf 0$,

Then the weight gradients collect one outer product per step,

with $\partial\mathcal L/\partial\mathbf b_h = \sum_t \boldsymbol\delta_t$, $\partial\mathcal L/\partial\mathbf b_y = \sum_t (\mathbf p_t - \mathbf e_{y_t})$, and $\mathbf W_{xh}^\top\boldsymbol\delta_t$ scatter-added into the embedding row of $w_t$.

In plain words, walk backward through time carrying an error vector. At each step add the error from that step's own prediction, push the total back through the tanh, record outer products for the weights, and hand the error to the previous step through $\mathbf W_{hh}^\top$.

BPTT has a memory cost. The backward pass needs every $\mathbf h_t$, so a sequence of length $T$ stores $T$ hidden states per layer and per example. For a long stream of text, like a whole book, that is impossible. Truncated BPTT splits the stream into chunks of $K$ steps. The hidden state is carried forward from chunk to chunk, so the forward pass still sees the whole history, but gradients are stopped at chunk boundaries (in PyTorch, h = h.detach()). The cost is that the gradient cannot teach the model any dependency longer than $K$ steps, even though information can still flow forward further than that.

import numpy as np

def rnn_bptt(P, ids, h0):
    raise NotImplementedError

Why gradients vanish or explode

This part of the story trips most people up, so let's go slowly. Look at how the error travels in the BPTT recursion. Ignoring the new error injected at each step, it is multiplied at every step by the transpose of

So the influence of the state $k$ steps back on the current state is a product of $k$ Jacobians,

In plain words, a signal from $k$ steps ago reaches the present only after being multiplied by $\mathbf W_{hh}$ and squashed by the tanh derivative $k$ times. A product of many matrices tends to shrink to nothing or blow up, and only a knife-edge in between keeps it stable.

Run the scalar echo from the start of the section backward to see it by hand. With $h_t = \tanh(0.5\,h_{t-1} + x_t)$ the one-by-one Jacobian is $J_t = 0.5\,(1 - h_t^2)$. The states were $h_2 = 0.363$, $h_3 = 0.180$, $h_4 = 0.090$, so $J_2 = 0.5 \times 0.868 = 0.434$, $J_3 = 0.484$, and $J_4 = 0.496$. The sensitivity of $h_4$ to $h_1$ is their product, $0.434 \times 0.484 \times 0.496 = 0.104$, a little below the $0.5^3 = 0.125$ that the recurrent weight alone would give, because each tanh derivative shaves off a bit more. Going one step further back, to the input $x_1$, multiplies by $1 - h_1^2 = 0.42$ and leaves $0.044$. Three steps cost a factor of twenty. Thirty steps would cost about $10^{-9}$.

The linear case is all about eigenvalues

Drop the nonlinearity for a moment, so $\mathbf J_t = \mathbf W_{hh}$ and the product is $\mathbf W_{hh}^k$. Suppose $\mathbf W_{hh}$ is diagonalizable (the eigendecomposition of §0.10), $\mathbf W_{hh} = \mathbf Q \boldsymbol\Lambda \mathbf Q^{-1}$, with eigenvalues $\lambda_1, \dots, \lambda_{d_h}$ on the diagonal of $\boldsymbol\Lambda$. Then

Express any gradient vector in the eigenvector basis. Its component along eigenvector $i$ is multiplied by $\lambda_i^k$ after $k$ steps. Let the spectral radius be $\rho(\mathbf W_{hh}) = \max_i |\lambda_i|$. If $\rho < 1$, every component decays geometrically and the gradient from far in the past vanishes. If $\rho > 1$, the components along eigenvectors with $|\lambda_i| > 1$ grow geometrically and the gradient explodes. Pascanu, Mikolov, and Bengio (2013) state exactly this for the linear case. $\rho < 1$ is sufficient for the long-term components to vanish, and $\rho > 1$ is necessary for them to explode.

The numbers are brutal. With $\rho = 0.9$, a gradient 50 steps back is scaled by $0.9^{50} \approx 0.005$, and 100 steps back by $0.9^{100} \approx 2.7 \times 10^{-5}$. With $\rho = 1.1$, 50 steps back it is scaled by $1.1^{50} \approx 117$, and 100 steps back by about $1.4 \times 10^4$. Only $\rho$ very close to 1 gives anything usable, and training does not stay there by itself.

The tanh only makes vanishing worse

Now put the nonlinearity back. The tanh derivative $1 - \tanh^2(u)$ lies in $(0, 1]$, equal to 1 only at $u = 0$ and tiny when the unit saturates. Write $\gamma$ for an upper bound on the derivative of the nonlinearity ($\gamma = 1$ for tanh and $\gamma = 1/4$ for the logistic sigmoid) and $\sigma_{\max}$ for the largest singular value of $\mathbf W_{hh}$. The operator norm $\Vert\mathbf A\Vert$ (the largest factor by which $\mathbf A$ can stretch a vector, which equals its largest singular value, see §0.10) is submultiplicative, $\Vert\mathbf A\mathbf B\Vert \le \Vert\mathbf A\Vert\,\Vert\mathbf B\Vert$, and a diagonal matrix stretches by at most its largest entry in absolute value, here at most $\gamma$. So

In plain words, each step can stretch the gradient by at most $\gamma\sigma_{\max}$, so after $k$ steps by at most that number to the power $k$. It follows that $\sigma_{\max} < 1/\gamma$ is sufficient for the gradient to vanish exponentially, and $\sigma_{\max} > 1/\gamma$ is necessary (but not sufficient) for it to explode. This is the theorem of Pascanu et al. (2013). It explains the observation of Bengio, Simard, and Frasconi (1994) and of Hochreiter's 1991 thesis that gradient descent struggles to learn long-term dependencies in recurrent networks.

Try three settings. With an orthogonal $\mathbf W$, inputs off (input scale 0), and $\rho = 0.9$ or $1.1$, the linear curve lies exactly on $\rho^k$, the straight line on a log scale. Switch to a Gaussian $\mathbf W$ with the same $\rho$ and the curve bulges above the line before falling, because $\sigma_{\max}$ is larger. Then raise the input scale. The tanh units saturate, the mean tanh derivative drops, and the tanh curve falls far below the linear one even when $\rho > 1$. In a saturating tanh network, vanishing is the common case and explosion needs large weights.

The linear column matches $\rho^{50}$ exactly, because an orthogonal matrix scaled by $\rho$ has every singular value equal to $\rho$. The tanh column is far smaller in all three rows, because driven by inputs the units spend much of their time away from zero, where the derivative is less than one.

What does vanishing do to learning? The total gradient for $\mathbf W_{hh}$ is a sum over pairs of steps, a loss at step $t$ reaching back to a state at step $t - k$. The terms with small $k$ are of ordinary size, and the terms with large $k$ are exponentially small. So the gradient is dominated by short-range dependencies, and the model learns local structure (spelling, short phrases) long before it learns anything that spans a clause, if it ever does. Exploding gradients do the opposite damage. A single huge step throws the parameters far away, and the loss spikes or becomes NaN.

Gradient clipping tames explosions

Explosions have a cheap fix that you already know from §0.6, clipping by global norm. If the norm of the whole gradient, taken over all parameters together, exceeds a threshold $c$, rescale it to have norm $c$, $\mathbf g \leftarrow \mathbf g \cdot \min(1, c/\Vert\mathbf g\Vert)$. The direction is kept and only the length of the step is capped. What is worth adding here is why recurrent networks need it so badly, because the reason is a picture.

Pascanu et al. (2013), who proposed norm clipping for RNNs, explained explosions as cliffs. A recurrent map can have several stable states (attractors), and a small change in the weights can move the trajectory from one basin to another. Near that boundary the final state, and so the loss, changes abruptly, so the loss surface has a nearly vertical wall with flat plateaus on either side. On the wall the gradient is huge. It is also only valid over a tiny distance, because it describes the wall's slope, not the plateau beyond it. A full gradient step there extrapolates the slope far past where it holds and throws the parameters somewhere arbitrary.

The smallest example is one unit with a self-weight of 2, which with no bias has two attractors near $\pm 0.96$. Start it at $h_0 = -0.9$, run it for 20 steps with a bias $b$, and ask for $h_{20} = 0.8$. For small $b$ the state stays in the negative basin, for large $b$ it escapes to the positive one, and in between is the cliff.

Off the cliff the gradient is around a hundredth. On it, it is tens of thousands of times larger, and one unclipped step moves $b$ by about 30 when the whole interesting region is one unit wide. Clipping turns that step into an ordinary one in the same direction. In a real network with millions of weights the same thing happens along a few directions at a time, which is why training curves of RNNs (and of large Transformers) show sudden loss spikes, and why the norm before clipping is the number to log.

Two practical notes. The threshold is a hyperparameter, set relative to the typical gradient norm. Pascanu et al. suggested a value around the average norm over many updates, Sutskever, Vinyals, and Le (2014) clipped their translation model at 5, and large Transformer runs today clip at 1.0 (§8.8). And the norm must be global, over all parameters together, because clipping each tensor separately changes the direction of the update.

Clipping does nothing for vanishing gradients. You cannot rescale a gradient that carries no information about the distant past. Initialization helps a little. An orthogonal $\mathbf W_{hh}$ starts with every singular value at exactly 1 (Saxe, McClelland, and Ganguli 2014), and Le, Jaitly, and Hinton (2015) trained ReLU RNNs from an identity $\mathbf W_{hh}$ on tasks with long gaps. But training moves the weights off these points and the tanh still saturates, so initialization only delays the problem. A lasting fix needs a change of architecture.

The LSTM gives the gradient an additive path

The long short-term memory of Hochreiter and Schmidhuber (1997) attacks the product of Jacobians at its root. Instead of rewriting its memory at every step through a matrix and a squashing function, an LSTM keeps a separate cell state $\mathbf c_t$ that is updated mostly by addition, and it uses learned gates (vectors of numbers between 0 and 1) to decide what to write, what to keep, and what to show.

At each step the LSTM computes four vectors from the current input and the previous hidden state, each with its own weights,

and then updates the cell and the hidden state,

Here each $\mathbf W_\ast \in \R^{d_h \times d}$, each $\mathbf U_\ast \in \R^{d_h \times d_h}$, and $\sigma$ is the logistic sigmoid. In plain words, the cell is a notepad. The forget gate decides how much of the old note to keep, the input gate decides how much of the new candidate to add, and the output gate decides how much of the note to reveal as the hidden state that the rest of the network sees.

Now look at the gradient along the cell. Holding the gates fixed, $\partial\mathbf c_t / \partial\mathbf c_{t-1} = \operatorname{diag}(\mathbf f_t)$, so

There is no weight matrix in this product and no tanh derivative. The gradient along the cell is scaled only by the forget gates, which the network itself controls. When it needs to remember something, it can hold $\mathbf f_t \approx 1$ and the gradient passes through many steps nearly undiminished. When it needs to forget, it closes the gate. In the original 1997 LSTM there was no forget gate at all, so the cell path was exactly the identity, which Hochreiter and Schmidhuber called the constant error carousel. The forget gate was added by Gers, Schmidhuber, and Cummins (2000) so that the network could also reset its memory.

The widget below is a single LSTM cell with its weights set by hand to count bracket depth. Its input gate opens on brackets, the candidate is $+1$ for "(" and $-1$ for ")", the forget gate is a constant set by its bias, and the output gate opens only on "?".

Play with three things. Load the "long gap" preset, three open brackets followed by forty distractors. With the default forget bias of 7 ($f \approx 0.999$) the cell still holds a count of about 2.7 at the "?" (each bracket writes $i \cdot g \approx 0.95$, and 41 steps of $f = 0.999$ cost a few percent), and the product of forget gates (the gradient along the cell path) stays above 0.95. Lower the forget bias to 0, so every $f_t = 0.5$, and the count has leaked away after a few steps and the gradient product is around $10^{-13}$. Finally compare the cell with the plain tanh RNN row. The RNN state is squashed to $(-1, 1)$ at every step, so it cannot represent depth 4 differently from depth 2.

In practice the four gates' weights are stacked into single matrices so that one matrix multiply computes all of them. PyTorch's nn.LSTM stores weight_ih with shape (4 dh, d), weight_hh with shape (4 dh, dh), and two bias vectors, with the gates in the order input, forget, candidate, output. An LSTM layer therefore has $4(d_h d + d_h^2 + d_h)$ parameters (PyTorch's two biases make it $4(d_h d + d_h^2 + 2d_h)$), four times a plain RNN layer.

import numpy as np

def lstm_cell(x, h, c, W, U, b):
    raise NotImplementedError

Interviewers often follow "write the LSTM forward pass" with "now backpropagate through one cell". It is the same outer-product bookkeeping as BPTT, with one trap. The upstream gradient reaches the new cell $\mathbf c_t$ by two routes, directly from the next step's cell and through $\mathbf h_t = \mathbf o_t \odot \tanh(\mathbf c_t)$.

import numpy as np

def lstm_cell_backward(x, h, c, W, U, b, dh_new, dc_new):
    raise NotImplementedError

The GRU merges the gates

Cho et al. (2014) proposed a simpler gated unit in the same paper that introduced the RNN encoder-decoder (§3.5). They called it a new type of hidden unit, and Chung et al. (2014) named it the gated recurrent unit, or GRU. It has no separate cell and only two gates. With $\mathbf z_t$ the update gate and $\mathbf r_t$ the reset gate,

In plain words, the update gate interpolates between keeping the old state and replacing it with a candidate, and the reset gate decides how much of the old state the candidate may look at. When $\mathbf z_t \approx 1$ the state is copied forward and $\partial\mathbf h_t/\partial\mathbf h_{t-1}$ contains the term $\operatorname{diag}(\mathbf z_t)$, an additive shortcut just like the LSTM cell. The GRU has three blocks of weights instead of four, so about 25% fewer parameters than an LSTM of the same width. Empirically the two are close. Jozefowicz et al. (2015) found the GRU slightly ahead of an LSTM with the default forget bias and roughly tied once the bias was set to 1, and Greff et al. (2017), in an extensive study of LSTM variants, found the forget gate and the output activation to be the most critical components.

import numpy as np

def gru_cell(x, h, W, U, b):
    raise NotImplementedError

Gates in action, measured

The cleanest way to see what gating buys is to measure the gradient directly. Below, a loss depends only on the last hidden state of a randomly initialized network, and we measure how large its gradient is with respect to the very first input as the sequence gets longer. This is the signal that would teach the network a dependency spanning the whole sequence.

The plain RNN's gradient falls by many orders of magnitude between 5 and 50 steps, the vanishing gradient in its rawest form. An LSTM with a zero forget bias does barely better, since $f \approx 0.5$ is a leaky memory. A bias of 1 ($f \approx 0.73$) decays much more slowly but still vanishes by 100 steps, which is fine as a starting point because training can raise the bias where memory pays. With the forget bias at 3 ($f \approx 0.95$) the gradient stays of order one over 100 steps. That last row is more than the cell path alone explains, since $0.95^{100} \approx 0.006$. The rest arrives along the other paths of the derivation above (through $\mathbf h$ and the gates), which at a random initialization can amplify as well as shrink, so read the table as a measurement rather than a formula. The architecture did not solve the problem by itself. It gave the network a knob, the forget gate, that can solve it.

Training an RNN language model the real way

Here is the complete training loop for a character-level LSTM language model with truncated BPTT, the recipe behind Karpathy's famous char-rnn experiments (Karpathy 2015) and Graves's (2013) handwriting and text generation. The stream is cut into chunks of $K = 64$ characters. The hidden state is carried across chunks but detached, and the gradient's global norm is clipped.

Within 200 steps the loss falls from about $\log V \approx 3.1$ to below 0.2, and the samples are mostly well-formed sentences of the toy language with the occasional misspelling. Run the same loop for longer on Shakespeare, Wikipedia, or the Linux source code, as Karpathy did, and the samples become convincing pastiches with balanced brackets and plausible indentation. Karpathy, Johnson, and Fei-Fei (2015) then looked inside such models and found individual cells with readable jobs, one tracking whether the text is inside a quotation, one the position along a line, one the nesting depth of code. The bracket-counting cell of the widget above is the hand-built version of what these networks learn on their own.

Three details in this loop are easy to get wrong in an interview. The state must be detached at every chunk boundary, or the graph grows forever and memory explodes. The streams must be laid out so that chunk $k+1$ of row $b$ continues chunk $k$ of row $b$, otherwise carrying the state is meaningless. And clipping happens after backward and before step.

Stacking layers and regularizing them

Real recurrent language models have more than one layer. A stacked RNN feeds each layer's hidden states to the next layer as its inputs at the same time step. Writing $\mathbf h_t^{(l)}$ for the state of layer $l$ at step $t$, with $\mathbf h_t^{(0)} = \mathbf x_t$,

and the softmax reads the top layer $\mathbf h_t^{(L)}$ (the same stacking works with LSTM or GRU cells). In plain words, depth in this direction adds computation at every step without making the path through time any longer. Two to four layers was typical. Sutskever et al. used four in their translation model (§3.5), and ELMo uses two (§3.4). In PyTorch this is the num_layers argument.

Large LSTM language models overfit quickly, and the obvious regularizer goes wrong. Dropout with a fresh mask at every step on the recurrent connection $\mathbf h_{t-1} \to \mathbf h_t$ corrupts the memory over and over, so information cannot survive many steps. Zaremba, Sutskever, and Vinyals (2014) showed that dropout works well if it is applied only to the non-recurrent connections (on the embeddings, between layers, and before the softmax). PyTorch's nn.LSTM(..., num_layers=2, dropout=0.3) does the between-layer part, and you add the other two yourself. Gal and Ghahramani (2016) then showed that the recurrent connections can be dropped too, as long as the same mask is reused at every step of a sequence (variational dropout). AWD-LSTM combined that with DropConnect on the recurrent matrix itself, a mask on the entries of $\mathbf W_{hh}$ drawn once per batch, and with tying the softmax weights to the embedding table (§3.2). Those choices, not a new cell, produced its record perplexities.

Gating solved the vanishing gradient well enough that LSTMs dominated language modeling, speech recognition, and translation for most of the 2010s. Two problems remained, and they will drive the rest of this chapter. First, the whole history still has to fit into one fixed-size vector. Second, step $t$ cannot be computed until step $t-1$ is done, so training cannot be parallelized across the sequence, which is why the Transformer of Chapter 5 won once hardware made parallelism the main currency. The recurrence itself has made a comeback in linear-time sequence models, where the same eigenvalue analysis returns as the stability condition of state-space models that keep a recurrent state but train in parallel.

Read more

• Elman (1990). Finding Structure in Time. The simple recurrent network and what its hidden states learn about language.
• Mikolov et al. (2010). Recurrent Neural Network Based Language Model. The paper that made RNN language models practical.
• Pascanu, Mikolov, and Bengio (2013). On the Difficulty of Training Recurrent Neural Networks. The eigenvalue and singular value analysis, and gradient norm clipping. Read Section 2.
• Hochreiter and Schmidhuber (1997). Long Short-Term Memory, and Gers, Schmidhuber, and Cummins (2000), Learning to Forget. The constant error carousel, then the forget gate.
• Zaremba, Sutskever, and Vinyals (2014). Recurrent Neural Network Regularization. Dropout on the non-recurrent connections only, the recipe for large LSTM language models.
• Jozefowicz, Zaremba, and Sutskever (2015). An Empirical Exploration of Recurrent Network Architectures. Ten thousand architectures, and the forget-bias result. Jozefowicz et al. (2016), Exploring the Limits of Language Modeling, is the LSTM at its largest.
• Karpathy (2015). The Unreasonable Effectiveness of Recurrent Neural Networks. Character-level LSTMs writing Shakespeare, LaTeX, and C. Karpathy, Johnson, and Fei-Fei (2015), Visualizing and Understanding Recurrent Networks, finds the interpretable cells.
• Olah (2015). Understanding LSTM Networks. The gates drawn one at a time, the clearest picture of the cell. Chapter 14 of Jurafsky and Martin (in the reading list of §3.4) is the textbook version.

Watch next

▶

▶

▶

▶