LLM & VLM courseBlog
7Track 1: Foundations · session 7 of 15

Before transformers: RNN, LSTM, seq2seq and the first attention

Transformers were invented to fix specific problems of the models before them. This session builds those models, recurrent networks, LSTMs and sequence-to-sequence translation, and shows exactly where they break: vanishing gradients, a one-vector bottleneck, and steps that cannot run in parallel. Then it shows the idea that fixed the bottleneck: attention.

Time: 3 hours (reading 2 hours, exercises 1 hour)Level: BeginnerBefore this: Sessions 2, 4 and 6

What you will learn

  • How a recurrent neural network (RNN) carries a memory through a sequence
  • Why gradients vanish or explode through time, with the math
  • How the LSTM’s gates and cell state keep gradients alive
  • Sequence-to-sequence models and the one-vector bottleneck
  • Bahdanau attention: scores, softmax weights and a context vector, the direct ancestor of QKᵀ
  • Why self-attention replaced recurrence: parallel training and short paths, and where recurrent ideas still live (SSMs, streaming video)

Why this matters

Before 2017, the best language and translation models were recurrent networks. They read text one token at a time and carried a memory forward. They worked, but they had three problems, and the transformer was designed to remove all three.

  • Forgetting: gradients shrink as they travel back through many steps, so long-range patterns are hard to learn.
  • A bottleneck: a translation model had to squeeze a whole sentence into one fixed vector.
  • No parallelism: step \(t\) needs step \(t-1\), so training cannot use the GPU’s parallel power across the sequence.

Attention was invented in 2014 to fix the bottleneck. In 2017 the transformer kept attention and threw away the recurrence. Understanding this history makes every transformer design choice obvious. And recurrent ideas are back: state space models such as Mamba (session 101) and streaming video models keep a running state much like an RNN.

Recurrent neural networks

An RNN reads a sequence \(\mathbf{x}_1, \dots, \mathbf{x}_T\) and keeps a hidden state \(\mathbf{h}_t\): a vector that summarizes everything read so far. At each step it mixes the old state with the new input:

\[ \mathbf{h}_t = \tanh\!\left( W_{hh}\, \mathbf{h}_{t-1} + W_{xh}\, \mathbf{x}_t + \mathbf{b} \right), \qquad \mathbf{y}_t = W_{hy}\, \mathbf{h}_t \tag{7.1} \]
Read the symbols
\(\mathbf{h}_t\)
the memory after reading token \(t\) (size \(d_h\))
\(W_{hh}\)
how the old memory feeds into the new one
\(W_{xh}\)
how the new input enters the memory
\(\mathbf{y}_t\)
the output at step \(t\), for example the logits for the next token

The same weights are used at every step. That is how an RNN handles sequences of any length with a fixed number of parameters. If you “unroll” it in time, it becomes a very deep network (one layer per token) whose layers all share weights.

As a language model, the RNN predicts \(x_{t+1}\) from \(\mathbf{h}_t\) with softmax and cross-entropy, exactly as before. Unlike an n-gram model, it has no fixed window: in principle \(\mathbf{h}_t\) depends on every earlier token. In practice, the memory fades. The next section shows why.

Training through time: vanishing and exploding gradients

We train an RNN with ordinary backpropagation on the unrolled graph. This is called backpropagation through time (BPTT). The gradient of a loss at step \(T\) with respect to an early state \(\mathbf{h}_k\) is a product of one Jacobian per step:

\[ \frac{\partial \mathbf{h}_T}{\partial \mathbf{h}_k} = \prod_{t=k+1}^{T} \frac{\partial \mathbf{h}_t}{\partial \mathbf{h}_{t-1}} = \prod_{t=k+1}^{T} \operatorname{diag}\!\left(1 - \mathbf{h}_t^2\right) W_{hh} \tag{7.2} \]

The factor \(1 - \mathbf{h}_t^2\) is the derivative of tanh; it is at most 1 and close to 0 when tanh is saturated. Now picture a single number instead of a matrix: the product is like \(\rho^{T-k}\), where \(\rho\) is the typical size of one factor.

Worked example

Over 50 steps: \(0.9^{50} = 0.005\), so the signal from 50 tokens ago is 200 times weaker; \(1.1^{50} = 117\), so it is 117 times stronger. Over 100 steps the effect is even more extreme. A product of many numbers almost never stays near 1.

  • Vanishing gradients (\(\rho \lt 1\)): the model cannot learn that a token far back matters. This is the main reason plain RNNs forget.
  • Exploding gradients (\(\rho \gt 1\)): updates become huge and training diverges. Gradient clipping (Session 4, formula 4.13) fixes this one.

Figure 1 runs a real RNN in your browser. The hidden state has only 2 numbers, so you can read every value. The recurrent matrix is a rotation scaled by \(\rho\): \(W_{hh} = \rho \begin{pmatrix} \cos 0.6 & -\sin 0.6 \\ \sin 0.6 & \cos 0.6 \end{pmatrix}\). A rotation does not change the length of a vector, so \(W_{hh}\) changes every length by exactly \(\rho\), and \(\rho\) is its spectral radius. The input matrix is \(W_{xh} = \begin{pmatrix} 0.8 & -0.3 \\ 0.2 & 0.9 \end{pmatrix}\), \(\mathbf{b} = \mathbf{0}\), and each word has a fixed 2-number embedding. First the forward pass runs formula (7.1) one token at a time. Then the backward pass starts from a loss gradient \(\mathbf{g}_T = \partial L / \partial \mathbf{h}_T = (1, 0)\) at the last token. It walks back one step at a time. Each step multiplies by one factor of formula (7.2):

\[ \mathbf{g}_{t-1} = \left(\frac{\partial \mathbf{h}_t}{\partial \mathbf{h}_{t-1}}\right)^{\!\top} \mathbf{g}_t = W_{hh}^\top \left( (1 - \mathbf{h}_t^2) \odot \mathbf{g}_t \right) \]

Here \(\mathbf{g}_t\) is the gradient of the loss with respect to \(\mathbf{h}_t\). The orange bars show its length \(\lVert \mathbf{g}_t \rVert\) on a log scale.

\(h[1]\), first number of the state\(h[2]\), second numbergradient length \(\lVert \mathbf{g}_t \rVert\) (log scale from \(10^{-5}\) to 10; the dotted line is 1)dashed tick: \(\rho^{T-t}\), the one-number picture
  1. \(\mathbf{h}_0 \leftarrow \mathbf{0}\)
  2. for \(t = 1, \dots, T\): // forward
  3. \(\mathbf{a}_t \leftarrow W_{hh}\mathbf{h}_{t-1} + W_{xh}\mathbf{x}_t + \mathbf{b}\)
  4. \(\mathbf{h}_t \leftarrow \tanh(\mathbf{a}_t)\) // (7.1), keep every \(\mathbf{h}_t\)
  5. \(\mathbf{g}_T \leftarrow \partial L/\partial \mathbf{h}_T = (1, 0)\) // backward starts
  6. for \(t = T, \dots, 2\):
  7. \(\mathbf{g}_{t-1} \leftarrow W_{hh}^\top\big((1 - \mathbf{h}_t^2) \odot \mathbf{g}_t\big)\) // one factor of (7.2)
Figure 1. Backpropagation through time, computed live. Forward: each box fills in \(\mathbf{h}_t\) from \(\mathbf{h}_{t-1}\) and the word (blue pulse). Backward: an orange pulse carries the gradient from right to left, and each orange bar shows how long \(\mathbf{g}_t\) still is. The box on the right shows the formula of the current line with the real numbers put in.
How to read Figure 1

Press Play with the defaults (\(\rho = 0.9\), 12 tokens). The forward pass gives \(\mathbf{h}_1 = (0.273, -0.310)\) for “the” and \(\mathbf{h}_2 = (0.731, 0.492)\) for “cat”. Then the gradient walks back. At \(t = 11\) it has length 0.866, and at \(t = 1\) only 0.044. The plain one-number picture predicts \(0.9^{11} = 0.314\) (the dashed ticks). The real gradient is 7 times smaller, because every step also multiplies by the tanh slope \(1 - h^2 \le 1\). Now try three things. (1) \(\rho = 0.5\): the gradient at \(t = 1\) is about \(8 \times 10^{-5}\). The first word gets almost no learning signal. (2) \(\rho = 1.3\) with input scale 0.05: the states stay small, tanh stays in its straight part, and the gradient grows to about 8.9: it explodes. (3) \(\rho = 1.3\) with input scale 1: the states are pushed toward ±1, the tanh slopes shrink, and the gradient falls to about 0.14 instead. So a large \(\rho\) alone does not cause explosion. You cannot pick one \(\rho\) that keeps the gradient near 1 for every input.

Figure 2 shows the same effect over 100 steps, with the matrix and the tanh slope reduced to one number each.

Figure 2. The size of the gradient signal from \(k\) steps back, in the one-number picture of formula (7.2): \((\rho \cdot \text{slope})^{k}\). The vertical axis is logarithmic.
How to read Figure 2

The green band is the useful range (between \(10^{-2}\) and \(10^{2}\)). Only when the product is almost exactly 1 does the signal survive for 100 steps. Lower the tanh slope (saturated units): even \(\rho \gt 1\) can vanish. There is no safe setting for long sequences, which is why we need a different design.

LSTM: a memory with gates

The Long Short-Term Memory network (Hochreiter and Schmidhuber, 1997) adds a second memory, the cell state \(\mathbf{c}_t\), which is changed by adding things, not by squashing it through a matrix and tanh at every step. Three gates, each a number between 0 and 1 per dimension, control it:

\[ \begin{aligned} \mathbf{f}_t &= \sigma\!\left(W_f [\mathbf{h}_{t-1}; \mathbf{x}_t] + \mathbf{b}_f\right) &&\text{forget gate} \\ \mathbf{i}_t &= \sigma\!\left(W_i [\mathbf{h}_{t-1}; \mathbf{x}_t] + \mathbf{b}_i\right) &&\text{input gate} \\ \mathbf{o}_t &= \sigma\!\left(W_o [\mathbf{h}_{t-1}; \mathbf{x}_t] + \mathbf{b}_o\right) &&\text{output gate} \\ \tilde{\mathbf{c}}_t &= \tanh\!\left(W_c [\mathbf{h}_{t-1}; \mathbf{x}_t] + \mathbf{b}_c\right) &&\text{candidate} \\ \mathbf{c}_t &= \mathbf{f}_t \odot \mathbf{c}_{t-1} + \mathbf{i}_t \odot \tilde{\mathbf{c}}_t, \qquad \mathbf{h}_t = \mathbf{o}_t \odot \tanh(\mathbf{c}_t) \end{aligned} \tag{7.3} \]

Here \(\odot\) is element-wise multiplication and \([\cdot\,;\cdot]\) is concatenation. Read the cell update in words: keep a fraction \(\mathbf{f}_t\) of the old memory, and add a fraction \(\mathbf{i}_t\) of new information. The output gate decides how much of the memory to show.

Why does this help gradients? Along the cell state, the local derivative is just the forget gate:

\[ \frac{\partial \mathbf{c}_t}{\partial \mathbf{c}_{t-1}} = \operatorname{diag}(\mathbf{f}_t) \quad \Rightarrow \quad \frac{\partial \mathbf{c}_T}{\partial \mathbf{c}_k} \approx \prod_{t=k+1}^{T} \operatorname{diag}(\mathbf{f}_t) \tag{7.4} \]

No weight matrix and no tanh in this path. If the network learns \(f \approx 1\) for an important dimension, the signal passes almost untouched; it can also learn \(f \approx 0\) to forget on purpose. This additive path is the same idea as the residual stream in a transformer (Session 1, formula 1.5). A common trick is to initialize the forget-gate bias to 1 or 2, so memory is kept by default. [Likely]

Figure 3. How much of an item stored at step 0 is still in memory after \(t\) steps: \(f^{t}\) for an LSTM cell with a constant forget gate (blue), compared with a plain RNN whose per-step factor is \(0.9\) (grey).

The GRU (Cho et al., 2014) is a lighter variant with two gates and no separate cell state; it often works about as well as an LSTM. [Likely]

ct−1ct × + forget f input i candidate c̃ × output o × tanh(c)ht all gates read [ht−1; xt] and output values between 0 and 1
Figure 4. One LSTM cell. The thick line on top is the cell state: it is only multiplied by the forget gate and added to, which is why its gradient can survive many steps (formula 7.4).

Figure 5 runs the gates on a small memory task. The LSTM has a hidden size of 1, so every gate is one number. Each input is \(\mathbf{x}_t = (v_t, s_t, r_t)\): a value \(v_t\), a “store” flag \(s_t\) and a “read” flag \(r_t\). The task: store the value when \(s_t = 1\), ignore the noise values in between, and show the stored value when \(r_t = 1\). We set the weights by hand so that you can read them; a trained LSTM finds weights of the same kind:

\[ \begin{aligned} f_t &= \sigma(0.5\,h_{t-1} - 5\,s_t + b_f), & i_t &= \sigma(0.5\,h_{t-1} + 6\,s_t - 3), \\ o_t &= \sigma(6\,r_t - 3), & \tilde{c}_t &= \tanh(3\,v_t) \end{aligned} \]

When nothing happens, the input gate is \(\sigma(-3) = 0.047\): almost closed. A store flag opens it to \(\sigma(3) = 0.953\) and pushes the forget gate down, so the old memory is replaced. The forget-gate bias \(b_f\) is the slider: it sets how well the memory survives the quiet steps.

cell state \(c_t\) (the conveyor belt, from \(-1\) to \(1\))forget gate \(f\)input gate \(i\)output gate \(o\)
  1. for \(t = 1, \dots, 10\), read \(\mathbf{x}_t = (v_t, s_t, r_t)\):
  2. \(f \leftarrow \sigma(0.5\,h_{t-1} - 5\,s_t + b_f)\) // forget gate
  3. \(i \leftarrow \sigma(0.5\,h_{t-1} + 6\,s_t - 3)\) // input gate
  4. \(o \leftarrow \sigma(6\,r_t - 3)\); \(\;\tilde{c} \leftarrow \tanh(3\,v_t)\)
  5. \(c_t \leftarrow f\, c_{t-1} + i\, \tilde{c}\) // (7.3), additive memory
  6. \(h_t \leftarrow o \tanh(c_t)\) // what the next layer sees
Figure 5. An LSTM cell with hidden size 1, stepped live over 10 inputs. Each step computes the three gates and the candidate, then the new cell state, then the output. The thick line on top is the cell state \(c_t\); the bars are the gate values (0 to 1). The output \(h_t\) is printed under each step.
How to read Figure 5

With \(b_f = 3\), step 1 stores \(\tilde{c} = \tanh(2.4) = 0.984\), and the cell becomes \(c_1 = 0.937\). During the four noise steps the forget gate is about 0.953, and the input gate lets in only about 5% of each noise value. At the read (step 6) the output gate opens to 0.953: the cell still holds \(c_6 = 0.735\), and the output is \(h_6 = 0.596\). The gradient along the belt from step 6 back to step 1 is the product of the forget gates, \(0.953^5 \approx 0.79\) (formula 7.4): no weight matrix, no tanh slope. Step 7 stores a new value, \(-0.6\), and the second read gives \(h_{10} = -0.559\). Now move the slider. With \(b_f = 0\) the forget gate is about 0.5, and the first read gives only 0.022: the memory is gone after 5 steps. With \(b_f = 6\) the first read is good (0.692), but the store at step 7 cannot clear the old memory (\(f_7 = \sigma(1.35) = 0.79\)), so the second read gives \(-0.152\) instead of about \(-0.56\). Remembering and overwriting pull in opposite directions, which is why the gates must depend on the input.

Sequence to sequence, and the bottleneck

For translation, the input and output have different lengths. The sequence-to-sequence model (Sutskever et al., 2014) uses two RNNs. The encoder reads the source sentence and ends in a final state \(\mathbf{c} = \mathbf{h}_{T_x}\). The decoder starts from \(\mathbf{c}\) and generates the target one token at a time:

\[ p(y_1, \dots, y_{T_y} \mid \mathbf{x}) = \prod_{t=1}^{T_y} p\!\left(y_t \mid y_{\lt t},\ \mathbf{c}\right) \tag{7.5} \]

The weakness is plain in the formula: everything the decoder knows about the source is in one fixed-size vector \(\mathbf{c}\), whether the sentence has 5 words or 50. Translation quality of such models dropped for long sentences. [Likely] Figure 7 below shows this on a tiny model: the same network with and without attention, on inputs of growing length.

Attention: look back at every input

Bahdanau, Cho and Bengio (2014) kept all encoder states \(\mathbf{h}_1, \dots, \mathbf{h}_{T_x}\). At each decoder step \(t\), the decoder state \(\mathbf{s}_{t-1}\) scores every encoder state, softmax turns the scores into weights, and the weighted sum becomes a fresh context vector for this step:

\[ e_{tj} = \mathbf{v}^\top \tanh\!\left( W \mathbf{s}_{t-1} + U \mathbf{h}_j \right), \qquad \alpha_{tj} = \frac{e^{e_{tj}}}{\sum_{k} e^{e_{tk}}}, \qquad \mathbf{c}_t = \sum_{j=1}^{T_x} \alpha_{tj}\, \mathbf{h}_j \tag{7.6} \]

This is the first attention. Compare it with Session 2, formula (2.20): a score per pair, a softmax over the inputs, a weighted sum. The decoder state plays the role of the query, the encoder states are both keys and values. Luong et al. (2015) simplified the score to a dot product, \(e_{tj} = \mathbf{s}_t^\top \mathbf{h}_j\) (or \(\mathbf{s}_t^\top W \mathbf{h}_j\)), which is one step from \(\mathbf{q}^\top \mathbf{k}\). The weights \(\alpha_{tj}\) form an alignment between target and source words, learned with no alignment labels at all.

Click a French word (a row).
Figure 6. An attention alignment for “the keeper saves the shot” → “le gardien arrête le tir”. Each row is one decoder step; the cells are the weights \(\alpha_{tj}\) over the English words and sum to 1. The weights are illustrative, chosen by hand to look like a trained model.

Figure 6 was drawn by hand. Figure 7 is a real model. We trained a tiny seq2seq network on a toy “translation” task: write the input letters in reverse order, so “c a f e b” becomes “b e f a c”. The letters are a to f, and the training sentences had 3 to 7 letters. Encoder and decoder are plain tanh RNNs with 16 hidden numbers (formula 7.1), and the attention is exactly formula (7.6), with an attention size of 16. We trained it offline with Adam, rounded the 1,919 weights to 3 decimals, and put them in this page. Your browser runs the real encoder, the real attention and the real decoder, one step at a time, with greedy decoding (pick the most likely letter at each step). For reversal, the right alignment is the anti-diagonal: the first output letter must look at the last input letter.

The second model has the same encoder and decoder sizes and the same training, but no attention: at every step its context is the last encoder state, \(\mathbf{c}_t = \mathbf{h}_T\). This is the one-vector bottleneck of formula (7.5).

Model
Input
encoder state \(\mathbf{h}_j\) (key and value)attention weight \(\alpha_{tj}\)decoder state and output
  1. encode: \(\mathbf{h}_j \leftarrow \tanh(W_{xh}\mathbf{x}_j + W_{hh}\mathbf{h}_{j-1} + \mathbf{b})\) for all \(j\); \(\;\mathbf{s}_0 \leftarrow \mathbf{h}_T\)
  2. for \(t = 1, 2, \dots\) until the end token:
  3. \(e_{tj} \leftarrow \mathbf{v}^\top \tanh(W\mathbf{s}_{t-1} + U\mathbf{h}_j)\) for every \(j\) // (7.6)
  4. \(\alpha_t \leftarrow \softmax(\mathbf{e}_t)\); \(\;\mathbf{c}_t \leftarrow \sum_j \alpha_{tj}\mathbf{h}_j\) // context
  5. \(\mathbf{c}_t \leftarrow \mathbf{h}_T\) // no attention: always the same vector
  6. \(\mathbf{s}_t \leftarrow \tanh\big(W_s\mathbf{s}_{t-1} + W_y\,\text{emb}(y_{t-1})\) \(+\, W_c\mathbf{c}_t + \mathbf{b}_s\big)\)
  7. \(y_t \leftarrow \argmax\, \softmax(W_o[\mathbf{s}_t; \mathbf{c}_t] + \mathbf{b}_o)\) // greedy
Figure 7. A trained seq2seq model with Bahdanau attention, running live on letter reversal. Each decoder step scores every encoder state, turns the scores into weights with softmax (orange bars and lines), forms the context \(\mathbf{c}_t\), updates the decoder state and writes one letter. The table under the algorithm collects the weights \(\alpha_{tj}\) row by row: the real alignment. Line 5 is used only by the model without attention.
How to read Figure 7

Press Play on “c a f e b”. At step 1 the scores are \(\mathbf{e}_1 = (-1.24, -0.41, 2.84, -1.53, 7.20)\). Softmax turns them into \(\alpha_1 = (0.000, 0.000, 0.013, 0.000, 0.987)\): almost all weight on the last letter “b”, and the model writes “b”. Step 2 puts 0.998 on “e”, and so on. The table fills in the anti-diagonal, and nobody told the model about positions; it learned the alignment from the reversal task alone. Now pick “a f a c d b d” (7 letters) and switch to the model without attention. It writes “d b d c a f” and stops: one letter is lost, because 7 letters do not fit well into one vector of 16 numbers. On 1,000 random inputs of each length (checked in Python with the same rounded weights), the attention model reverses 100% of the sentences with 3 to 7 letters, while the bottleneck model reverses 97.8% at length 6 and 86.9% at length 7. Length 8 is longer than anything seen in training: attention still gets 73.4% right, the bottleneck model 17.5%. At length 9 both fail (under 1%). Attention removes the bottleneck, but it does not teach the decoder to count past its training lengths.

From attention to the transformer

Once the decoder can look at all encoder states, why keep the RNNs at all? The transformer (Vaswani et al., 2017) lets every position attend to every other position in the same sequence (self-attention), with no recurrence. The comparison from the paper explains the switch:

Layer typeCost per layerSequential stepsLongest path between two tokens
Self-attention\(O(n^2 d)\)\(O(1)\)\(O(1)\)
Recurrent\(O(n d^2)\)\(O(n)\)\(O(n)\)
Convolution (kernel \(k\))\(O(k n d^2)\)\(O(1)\)\(O(\log_k n)\)

\(O(1)\) sequential steps means the whole sequence trains in parallel on a GPU. A path length of \(O(1)\) means a gradient between any two tokens passes through a constant number of layers, so nothing vanishes over distance. The price is the \(O(n^2)\) cost in sequence length, which is what all of Track 5’s efficient attention work tries to reduce.

Where recurrence still wins

At inference, an RNN keeps a fixed-size state, so each new token costs the same and memory does not grow. A transformer keeps a KV cache that grows with every token (session 80). For very long or endless streams (live audio, live video), that difference matters. State space models and linear-attention models try to get transformer-quality training with RNN-style constant-memory inference.

Where this is used

ApplicationRecurrent ideaToday
Streaming event detection on live videoA GRU or LSTM over per-frame features keeps a running state with constant cost per frameStill a strong, cheap choice for low-latency heads on top of a frozen image encoder
Action recognition (2015-era)CNN features per frame, then an LSTM over time (LRCN-style)Mostly replaced by video transformers (session 202)
Machine translationSeq2seq with attentionReplaced by transformers; the encoder–decoder shape lives on (session 24)
Speech recognition and keyboards on deviceRNN transducers with small stateStill used where memory and latency are tight [Likely]
Long-sequence LLMsSelective state space models (Mamba), RWKV, hybridsAn active alternative to attention (session 100)

Pseudo-code

Algorithm 1: one LSTM step (formula 7.3)
  1. input: \(\mathbf{x}_t\), \(\mathbf{h}_{t-1}\), \(\mathbf{c}_{t-1}\), weights \(W \in \R^{4d_h \times (d_h + d_x)}\), bias \(\mathbf{b}\)
  2. \(\mathbf{a} \leftarrow W[\mathbf{h}_{t-1}; \mathbf{x}_t] + \mathbf{b}\) // one matmul for all four parts
  3. split \(\mathbf{a}\) into \(\mathbf{a}_f, \mathbf{a}_i, \mathbf{a}_o, \mathbf{a}_c\) (each size \(d_h\))
  4. \(\mathbf{f}, \mathbf{i}, \mathbf{o} \leftarrow \sigma(\mathbf{a}_f), \sigma(\mathbf{a}_i), \sigma(\mathbf{a}_o)\); \(\;\tilde{\mathbf{c}} \leftarrow \tanh(\mathbf{a}_c)\)
  5. \(\mathbf{c}_t \leftarrow \mathbf{f} \odot \mathbf{c}_{t-1} + \mathbf{i} \odot \tilde{\mathbf{c}}\) // additive memory
  6. return \(\mathbf{h}_t = \mathbf{o} \odot \tanh(\mathbf{c}_t)\), \(\mathbf{c}_t\)
Algorithm 2: one decoder step with attention (formula 7.6)
  1. input: decoder state \(\mathbf{s}\), encoder states \(H \in \R^{T_x \times d}\), previous output token \(y\)
  2. for \(j = 1\) to \(T_x\) do \(e_j \leftarrow \mathbf{v}^\top \tanh(W\mathbf{s} + U\mathbf{h}_j)\) // or \(\mathbf{s}^\top \mathbf{h}_j\) (Luong)
  3. \(\alpha \leftarrow \softmax(\mathbf{e})\); \(\;\mathbf{c} \leftarrow \alpha^\top H\) // context vector
  4. \(\mathbf{s} \leftarrow \text{RNNcell}([\text{embed}(y); \mathbf{c}],\ \mathbf{s})\)
  5. return logits \(= W_{\text{out}}[\mathbf{s}; \mathbf{c}]\), new state \(\mathbf{s}\), weights \(\alpha\)
import torch, torch.nn as nn
torch.manual_seed(0)
B, T, d_in, d_h = 2, 7, 16, 32
lstm = nn.LSTM(d_in, d_h, batch_first=True)          # formula (7.3), all steps in one call
x = torch.randn(B, T, d_in)
H, (h_T, c_T) = lstm(x)                              # H: (B, T, d_h) every state; h_T, c_T: (1, B, d_h)
with torch.no_grad():                                 # forget-gate bias = 1 (PyTorch order: i, f, g, o)
    lstm.bias_ih_l0[d_h:2 * d_h].fill_(1.0)

class AdditiveAttention(nn.Module):                   # Bahdanau, formula (7.6)
    def __init__(self, d_s, d_h, d_a=64):
        super().__init__()
        self.W, self.U, self.v = nn.Linear(d_s, d_a, bias=False), nn.Linear(d_h, d_a, bias=False), nn.Linear(d_a, 1, bias=False)
    def forward(self, s, H):                          # s: (B, d_s), H: (B, T, d_h)
        e = self.v(torch.tanh(self.W(s)[:, None, :] + self.U(H))).squeeze(-1)   # (B, T) scores
        a = torch.softmax(e, dim=-1)                  # weights over source positions
        return (a[:, :, None] * H).sum(1), a           # context (B, d_h), weights (B, T)

ctx, a = AdditiveAttention(d_h, d_h)(h_T[0], H)
print(ctx.shape, a.sum(-1))                           # torch.Size([2, 32]) and ones

Common mistakes

  • Using the last output of a padded batch. With padding, the “last” step is padding for short sequences. Use pack_padded_sequence or gather the true last index.
  • No gradient clipping for RNNs. Exploding gradients are common; clip the global norm.
  • Forgetting gate order. PyTorch stores LSTM gates as input, forget, cell, output. Initializing the “forget bias” at the wrong slice changes a different gate.
  • Masking attention over padding. Set scores of padded source positions to \(-\infty\) before softmax, or the model attends to padding.
  • Calling attention weights an explanation. Alignments are suggestive, not proof of what the model used.

Interview questions

Why do gradients vanish or explode in RNNs?core
BPTT multiplies one Jacobian \(\operatorname{diag}(1-\mathbf{h}_t^2)W_{hh}\) per step (formula 7.2). The product of many such factors shrinks to zero if their typical size is below 1 and blows up if it is above 1; tanh saturation pushes toward vanishing. Clipping fixes explosion; gating (LSTM/GRU), careful initialization and shorter paths fix vanishing.
How does the LSTM help with vanishing gradients?core
The cell state is updated additively, \(\mathbf{c}_t = \mathbf{f}_t\odot\mathbf{c}_{t-1} + \mathbf{i}_t\odot\tilde{\mathbf{c}}_t\), so the gradient along it is multiplied only by the forget gate (formula 7.4), with no weight matrix and no tanh. With \(f\approx1\) the signal survives many steps. It is the same principle as residual connections.
What is the bottleneck in seq2seq, and how does attention remove it?basic
Without attention the decoder sees the source only through one fixed vector, the final encoder state, regardless of sentence length. Attention keeps every encoder state and computes a new weighted context vector at each decoder step, so the decoder can focus on the relevant source words.
Write Bahdanau attention and relate it to transformer attention.core
\(e_{tj} = \mathbf{v}^\top\tanh(W\mathbf{s}_{t-1} + U\mathbf{h}_j)\), \(\alpha = \softmax(e)\), \(\mathbf{c}_t = \sum_j \alpha_{tj}\mathbf{h}_j\). The decoder state is the query; encoder states are keys and values. Luong’s dot-product score and then the transformer’s scaled dot product \(\mathbf{q}^\top\mathbf{k}/\sqrt{d}\) with separate projections for Q, K and V are direct descendants; additive attention costs more because of the extra tanh layer.
Compare self-attention and recurrence in complexity.core
Self-attention: \(O(n^2 d)\) per layer, \(O(1)\) sequential operations, \(O(1)\) maximum path length. Recurrent: \(O(nd^2)\), \(O(n)\) sequential, \(O(n)\) path. Attention is faster to train on GPUs and learns long-range links more easily, but costs quadratic time and a growing KV cache in sequence length.
When would you still use a recurrent model today?advanced
For streaming with strict memory and latency limits (constant state per step), very long or unbounded streams, or tiny on-device models. For example, a GRU head over frame embeddings from a frozen encoder for live event detection, or state space models for long sequences. For most offline language tasks, transformers or hybrids win.
What does an LSTM’s forget-gate bias initialization of 1 do?basic
\(\sigma(1)\approx0.73\) at the start, so the cell keeps most of its memory by default instead of forgetting half of it each step. This makes gradients flow better early in training. [Likely]
Why is BPTT memory-hungry, and what is truncated BPTT?advanced
Backprop needs the hidden state at every step, so memory grows with sequence length, like activations in any deep network. Truncated BPTT backpropagates through only the last \(K\) steps while carrying the state forward, trading long-range credit assignment for bounded memory.

Exercises

  1. An RNN has per-step factor 0.95. After how many steps is the gradient signal below 1% of its original size?
  2. An LSTM keeps \(f = 0.99\). What fraction of an item stored at step 0 is left after 100 steps? With \(f = 0.9\)?
  3. Count the parameters of one LSTM layer with input size 16 and hidden size 32 (PyTorch has two bias vectors).
  4. In Figure 6, which English word does “arrête” attend to most? Why is “le” (row 4) split between two words?
  5. Write a dot-product (Luong) version of AdditiveAttention. What constraint does it put on the sizes of \(\mathbf{s}\) and \(\mathbf{h}\)?
  6. In Figure 5, set \(b_f = 1\). The forget gate in the quiet steps is now about 0.73. Before you press Play, estimate the cell state at the first read (step 6) and the output \(h_6\). Then check.
  7. In Figure 1, why does the gradient at \(t = 1\) stay small when you raise \(\rho\) to 1.5 with input scale 1, but grow when the input scale is 0.05?
Answerscheck
1. \(0.95^k = 0.01\) gives \(k = \ln 0.01/\ln 0.95 \approx 90\) steps. 2. \(0.99^{100} = 0.366\); \(0.9^{100} \approx 0.00003\). 3. \(4 \times (32 \times 16 + 32 \times 32 + 32 + 32) = 4 \times 1600 = 6{,}400\). 4. “saves”: they are the same verb. Two words share the article “the”, and position plus context decide which one. 5. Use \(e_j = \mathbf{s}^\top\mathbf{h}_j\); this needs the same size for \(\mathbf{s}\) and \(\mathbf{h}\), or a matrix \(W\) in between (\(\mathbf{s}^\top W\mathbf{h}_j\)). 6. Four quiet steps and the read step each multiply the memory by about 0.73, and \(0.73^5 \approx 0.21\), so \(c_6 \approx 0.937 \times 0.21 \approx 0.19\) (the figure gives 0.195; the small noise inputs change it a little). Then \(h_6 = 0.953 \cdot \tanh(0.195) = 0.183\). 7. Each backward step multiplies by \(W_{hh}^\top\) (length times \(\rho\)) and by the tanh slopes \(1 - h_t^2\). With large inputs the states are near ±1, the slopes are small, and they win over \(\rho = 1.5\) (the figure gives 0.24 at \(t = 1\)). With tiny inputs the states stay near 0, the slopes stay near 1, and \(\rho \gt 1\) makes the gradient grow (3.2 at \(t = 1\)).

Key takeaways

  • An RNN (7.1) carries a fixed-size memory with shared weights; BPTT multiplies Jacobians (7.2), so gradients vanish or explode over long distances.
  • The LSTM (7.3) keeps memory on an additive path whose gradient is just the forget gate (7.4): the same idea as residual connections.
  • Seq2seq (7.5) squeezes the source into one vector; attention (7.6) replaces it with a fresh weighted context per output step, learned alignments included.
  • Self-attention gives \(O(1)\) sequential steps and \(O(1)\) paths at \(O(n^2)\) cost; recurrence keeps \(O(1)\) inference memory, which is why SSMs and streaming models bring it back.

References for this session

  1. Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, chapter 14: RNNs and LSTMs
  2. Xiao & Zhu, NLP: Neural Networks and Large Language Models, chapter 4: Recurrent and Convolutional Sequence Models
  3. Xiao & Zhu, NLP: Neural Networks and Large Language Models, chapter 5: Sequence-to-Sequence Models
  4. Sutskever et al. (2014). Sequence to Sequence Learning with Neural Networks
  5. Bahdanau et al. (2014). Neural Machine Translation by Jointly Learning to Align and Translate
  6. Hochreiter & Schmidhuber (1997). Long Short-Term Memory
  7. Cho et al. (2014). Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation
  8. Luong et al. (2015). Effective Approaches to Attention-based Neural Machine Translation