# Module 5: Sequences Before Transformers

> How RNNs model text, why vanishing gradients and the seq2seq bottleneck limited them, and how Bahdanau attention first appeared in translation.

- Part I: Foundations · core track · Foundational · 3 hours
- By the end you can explain why recurrence hit a wall, and how attention first appeared inside RNN translation models.
- Builds on: [Module 4: How a Model Learns From Data](https://transformers-and-math.drmhse.com/md/04-how-a-model-learns.md)
- Web page (interactive figures, labs and equation explainers): https://transformers-and-math.drmhse.com/modules/05-sequences-before-transformers
- From *Transformers & Math* by Mike Chumba: https://transformers-and-math.drmhse.com

The meaning of a word depends on the words around it, sometimes many words back. Before 2017, sequences were modelled by *recurrent* networks, which read one token at a time and carry a running summary forward. This module explains how they work, the two walls they hit (no parallelism, and gradients that vanish over long distances), and the fix invented inside them: attention. Module 6 shows what happens when attention is all that is left.

## 5.1 Word Vectors and What Similarity Means

After training, the embedding vectors of section 1.5 carry meaning in their directions. Nobody labels which words are related: tokens in similar contexts receive similar updates, so their vectors drift together, and "cat" ends up closer to "dog" than to "carburetor". Word2vec (Mikolov et al., 2013) showed that some relations become directions: "king" minus "man" plus "woman" lands near "queen". Inside large language models these regularities are rougher and differ by layer, but direction encoding meaning is what makes the dot product a sensible score.

> **Interactive figure** `embedding-analogy`, on the web page: https://transformers-and-math.drmhse.com/modules/05-sequences-before-transformers#figure-embedding-analogy
>
> **Try:** The arrow from *man* to *woman* is copied to start at *king*. Before looking, predict where it ends, and what it would mean if it ended far from *queen*.
>
> **What happens:** It ends near *queen*: the change from male to female is roughly the same direction wherever it starts. If it ended far away, the relation would not be a consistent direction in the space, and vector arithmetic would not recover analogies. In real models this holds only roughly, and only for some relations.

> **In words.** Words as arrows in a plane: cat and dog point nearly the same way, cat and carburetor almost opposite. The arrow from man to woman, moved to start at king, ends close to queen.

## 5.2 Recurrent Networks

*Recurrent neural networks* (RNNs), including the Elman RNN and its gated variants LSTM and GRU, read one token at a time and keep a *hidden state* $\mathbf{h}_t$, a fixed-length summary of everything read so far, computed from the previous state and the current token:

$$
\mathbf{h}_t = \tanh(W_{hh} \mathbf{h}_{t-1} + W_{xh} \mathbf{x}_t + \mathbf{b})
$$

$W_{hh}$, $W_{xh}$ and $\mathbf{b}$ are learned. This section writes vectors as columns, as the RNN papers do, so matrices multiply from the left.

The same weights apply at every step, so an RNN reads any length. But the state has a fixed size: everything about the first 500 words must fit in the same few hundred numbers as the first 5.

```mermaid
graph LR
    h0["h_0"] --> T1["RNN step t=1"] --> h1["h_1"] --> T2["RNN step t=2"] --> h2["h_2"] --> T3["RNN step t=3"] --> h3["h_3"]
    x1["x_1"] --> T1
    x2["x_2"] --> T2
    x3["x_3"] --> T3
```

> **In words.** The hidden state passes along a chain, one step per token; the first token reaches the third only through the second. The chain causes both problems below: steps cannot run at the same time, and gradients must travel back along the whole chain.

## 5.3 No Parallelism Across Time

Step $t$ needs $\mathbf{h}_{t-1}$, so an $N$-token sequence takes $N$ matrix multiplications one after another: $\mathcal{O}(N)$ sequential steps. A GPU that could do thousands at once sits mostly idle.

## 5.4 Vanishing and Exploding Gradients

To learn from a mistake at step $T$, training needs how much an earlier state $\mathbf{h}_t$ contributed. By the chain rule (section 2.3), that is a product of one Jacobian per step in between:

$$
\frac{\partial \mathbf{h}_T}{\partial \mathbf{h}_t} = \prod_{k=t+1}^T \frac{\partial \mathbf{h}_k}{\partial \mathbf{h}_{k-1}} = \prod_{k=t+1}^T \operatorname{diag}(1 - \tanh^2(\cdot)) W_{hh}
$$

Each factor is the diagonal Jacobian of $\tanh$ (slopes $1 - \tanh^2$, never more than 1; the $(\cdot)$ is whatever was inside the $\tanh$ at step $k$) times $W_{hh}$.

Let $\sigma_{\max}$ be the most one multiplication by $W_{hh}$ can stretch a vector, the largest $\|W_{hh}\mathbf{v}\| / \|\mathbf{v}\|$ (formally the largest *singular value*, section 20.2). The $\tanh$ factor never stretches, so after $T - t$ steps:

$$
\left\|\frac{\partial \mathbf{h}_T}{\partial \mathbf{h}_t}\right\| \le c \cdot \sigma_{\max}^{T-t} \xrightarrow[T-t \to \infty]{} 0
$$

$T$ here is a step number, not a temperature, and $c$ is a constant independent of distance. If $\sigma_{\max} < 1$ the bound shrinks exponentially: $0.9^{50} \approx 0.005$. This is the *vanishing gradient*; factors above 1 give the *exploding gradient* (section 2.6). LSTMs ease it with a memory path updated by addition rather than repeated multiplication, but still pass information between tokens $N$ apart through $\mathcal{O}(N)$ steps.

> **Browser lab** `rnn-gradient`: an experiment that runs in the reader's browser on the web page: https://transformers-and-math.drmhse.com/modules/05-sequences-before-transformers#lab-rnn-gradient

## 5.5 Seq2seq and the Fixed-Vector Bottleneck

In translation, input and output are sequences of different lengths with words in different orders. Sutskever, Vinyals and Le (2014) used two RNNs, *sequence-to-sequence* (seq2seq):

1. The **encoder** reads the source sentence; its final hidden state summarizes it.
2. The **decoder** starts from that summary and writes the translation one token at a time, feeding each output back in, until an end-of-sentence token.

It worked well on short sentences and badly on long ones, because the *only* link between the halves is one fixed-size vector: 5 words or 50 must fit in the same few hundred numbers. This *fixed-vector bottleneck* made quality fall as sentences grew.

## 5.6 The First Attention

Bahdanau, Cho and Bengio (2014) removed the bottleneck: let the decoder look back at *every* encoder state $\mathbf{h}_1, \dots, \mathbf{h}_M$ and choose which to read at each step. Before writing output word $i$, with its own state $\mathbf{s}_{i-1}$, the decoder:

1. Scores every encoder state with a small learned network, $e_{ij} = \operatorname{score}(\mathbf{s}_{i-1}, \mathbf{h}_j)$.
2. Turns the scores into weights summing to 1 with a softmax: $\alpha_{ij} = \operatorname{softmax}_j(e_{ij})$.
3. Reads their weighted average, the *context vector*:

$$
\mathbf{c}_i = \sum_{j=1}^{M} \alpha_{ij} \mathbf{h}_j
$$

and uses $\mathbf{c}_i$, alongside its own state, to choose the next word.

Nobody tells the model which words correspond; the weights are learned from the translation loss alone. Yet plotted, they line up: writing the French *zone*, the decoder weights the English *area*, and where word order differs, the weights cross over to follow it.

> **Interactive figure** `bahdanau-alignment`, on the web page: https://transformers-and-math.drmhse.com/modules/05-sequences-before-transformers#figure-bahdanau-alignment
>
> **Try:** In a French–English pair, adjectives usually come after the noun in French and before it in English. Before looking, predict what that does to the shape of the alignment pattern.
>
> **What happens:** Most of the weight sits near the diagonal, because most words keep their order, but where an adjective and noun swap, the bright cells form a small cross that steps off the diagonal and back. The model learned the reordering from the loss alone.

> **In words.** A grid with the source sentence across the top and the translation down the side; each cell's shade is the weight on that source word while writing that output word. Most bright cells run along the diagonal, with detours where word order differs.

This first *attention* mechanism solved the bottleneck: the decoder could reach any source word directly. But the RNNs underneath kept both their problems. In 2017, Vaswani et al. asked whether the recurrence was needed at all.

### The Transformer Breakthrough: Maximum Path Length $\mathcal{O}(1)$
It was not. The transformer keeps only attention: between decoder and encoder, as Bahdanau had it, and within each sequence, every token attending to the others (*self-attention*). That removes the chain:
- **Path length.** Any two tokens are one step apart, $\mathcal{O}(1)$, so no long product of factors builds up.
- **Parallelism.** In training, all tokens are processed at once as a few large matrix multiplications. (Generation is still one token at a time.)

## Exercises

**Exercise (check).** Name the two problems of recurrent networks that the transformer removes, and say which design feature causes both.

*Solution:* Steps cannot run in parallel, and gradients vanish or explode over long distances. Both come from the chain: each hidden state is computed from the previous one, so the steps must run in order and the gradient between distant tokens is a product of one factor per step in between.

**Exercise (apply).** A gradient passes back through 40 RNN steps, each scaling it by at most $\sigma_{\max} = 0.85$. What is the largest it can be, as a fraction of its original size?

*Answer:* 0.00150 (within 0.00002)

*Solution:* $0.85^{40} = e^{40 \ln 0.85} = e^{-6.50} \approx 0.0015$. The earliest step receives at most about a seven-hundredth of the signal.

**Exercise (apply).** How many sequential steps does an RNN need to process a 1,000-token sequence, and how many sequential attention steps does one self-attention layer need for the same sequence?

*Solution:* The RNN needs 1,000 steps, one after another, because each depends on the previous one. One self-attention layer needs one step: all 1,000 tokens attend to each other at once, as a few matrix multiplications.

**Exercise (apply).** In Bahdanau attention, the decoder's weights over four source words are $[0.1, 0.6, 0.2, 0.1]$ and the encoder states are the scalars $[1, 3, -1, 2]$. Compute the context value.

*Answer:* 1.9 (within 0.0001)

*Solution:* $0.1 \cdot 1 + 0.6 \cdot 3 + 0.2 \cdot (-1) + 0.1 \cdot 2 = 0.1 + 1.8 - 0.2 + 0.2 = 1.9$. The context leans heavily on the second word, the one with weight $0.6$.

**Exercise (extend).** Explain what information a seq2seq decoder loses on a 200-word sentence, and why attention fixes it without making the encoder's states any larger.

*Solution:* Without attention, the decoder sees only the encoder's final state, a fixed-size vector that must summarize all 200 words; details of early words are overwritten as later words are read. Attention keeps every one of the 200 encoder states and lets the decoder read a different weighted mix of them at each output step. Each state stays the same size; what grows is the number of states the decoder can consult, which grows with the sentence.

### Core Academic References
- **Mikolov et al. (2013)**: *Efficient Estimation of Word Representations in Vector Space* (word2vec). [arXiv:1301.3781](https://arxiv.org/abs/1301.3781)
- **Elman (1990)**: *Finding Structure in Time*. Cognitive Science, 14(2): 179–211.
- **Hochreiter & Schmidhuber (1997)**: *Long Short-Term Memory*. Neural Computation, 9(8): 1735–1780.
- **Bengio, Simard & Frasconi (1994)**: *Learning long-term dependencies with gradient descent is difficult*. IEEE Transactions on Neural Networks, 5(2): 157–166.
- **Sutskever, Vinyals & Le (2014)**: *Sequence to Sequence Learning with Neural Networks*. NeurIPS 2014. [arXiv:1409.3215](https://arxiv.org/abs/1409.3215)
- **Bahdanau, Cho & Bengio (2014)**: *Neural Machine Translation by Jointly Learning to Align and Translate*. ICLR 2015. [arXiv:1409.0473](https://arxiv.org/abs/1409.0473)