12.5.6 — Sequences and the Road to Attention

Here are two support emails Cartwise received on the same morning:

"The parcel arrived, but never the charger that was supposed to be in it."

"The charger arrived, but never the parcel that was supposed to have it."

They contain almost exactly the same words. A bag-of-words model like the naive Bayes and TF-IDF classifiers of 12.3.5, which only counts which words appear, sees them as nearly identical. But the first is a missing-item complaint for the refunds team, and the second is a lost-parcel case for delivery. The meaning lives in the order of the words, and in which word refers back to which: "it" in the first email means the parcel, and in the second it means the charger.

Text, speech, a customer's sequence of clicks, a stream of sensor readings: these are sequences. They have three properties that photos do not. They vary in length: one email has eight words, the next has four hundred. Order matters. And the meaning of one part can depend on a part far away: a pronoun in the last sentence can refer to a noun in the first. This page follows the line of models built for sequences, because the problem each one ran into, and the fix for it, leads directly to the transformer and to every LLM.

1. Recurrent networks: read one word at a time, keep a memory

The natural idea is to read a sequence the way a person does: one word at a time, from left to right, carrying a running summary of everything read so far. A recurrent neural network, or RNN, does exactly that. It keeps a vector called the hidden state, \mathbf{h}, and at each step updates it from the previous state and the new input:

\mathbf{h}_t = \tanh\big(W_h\, \mathbf{h}_{t-1} + W_x\, \mathbf{x}_t + \mathbf{b}\big)

Read it as "the new memory equals the tanh of: the old memory times one weight matrix, plus the new word times another weight matrix, plus a bias". The subscript t counts steps: \mathbf{x}_t is the t-th word (as a vector of numbers; Chapter 12.6.1 explains how words become vectors), and \mathbf{h}_{t-1} is the memory after the previous word. The tanh from 12.5.1 keeps every value between −1 and 1, so the memory cannot grow without limit.

An RNN "unrolled" over four words. There is really only one cell, used again at every step with the same weights; the drawing repeats it to show time passing. The memory h carries information from left to right, and the final memory is a summary of the whole sequence.

Two things in the figure matter. First, the same weights are used at every step. That is weight sharing again, as in the convolutions of 12.5.5, but across time instead of across space: the network learns one rule for "how to update my memory when I see a word", and applies it to emails of any length. Second, each step needs the result of the step before it. You cannot compute \mathbf{h}_3 until \mathbf{h}_2 is finished. Hold on to that; it decides how this story ends.

To classify an email, feed it through word by word and put a classifier on the final memory \mathbf{h}_4. To train, run backpropagation through the unrolled chain, which is called backpropagation through time: an email of 100 words is, for the purposes of the chain rule, a network 100 layers deep.

Why plain RNNs forget

Watch what happens to a single piece of information as it travels through the memory. Take the tiniest possible RNN, with a one-number memory, h_t = \tanh(0.5\, h_{t-1} + x_t), and feed it a 1 followed by nothing but zeros. The memory goes:

Step	1	2	3	4	5	6
h_t	0.762	0.363	0.180	0.090	0.045	0.022

Each step, the memory of that first input is roughly halved. Six words later, it has almost gone. The same thing happens, even more strongly, to the gradient travelling backwards, which is what learning depends on. Each step back multiplies it by the step's local slope, which here is 0.5 \times (1 - h^2), at most 0.5. Twenty steps back, the learning signal has been multiplied by about (0.5 \times 0.75)^{20} \approx 3 \times 10^{-9}. It is the vanishing gradient from 12.5.1 again, now across time. With larger weights, the opposite happens and it explodes. A plain RNN cannot learn that a word twenty steps back matters, which rules out exactly the long-range dependencies that make language hard.

2. LSTM: a memory with gates

The fix that made recurrent networks useful came in 1997, from Sepp Hochreiter and Jürgen Schmidhuber: the LSTM, short for long short-term memory. The name sounds contradictory, and it is meant to: it is a short-term memory, the hidden state, that can last a long time.

An LSTM adds a second memory, called the cell state, which runs along the sequence with only simple, mostly additive changes at each step. Three small learned "gates" control it. Each gate is a layer with a sigmoid, so it outputs numbers between 0 and 1, which act like valves:

• The forget gate decides how much of the old cell state to keep: 1 keeps everything, 0 erases it.
• The input gate decides how much of the new information from this word to write in.
• The output gate decides how much of the cell state to reveal as this step's hidden state.

The key is that the cell state is updated by adding new information to a kept fraction of the old, c_t = f_t \odot c_{t-1} + i_t \odot \tilde{c}_t, rather than by squashing everything through a tanh at every step. When the forget gate stays near 1, information and gradient pass along the cell state almost unchanged for hundreds of steps. It is the same idea as the residual connection of 12.5.4, a clean path for the signal, invented eighteen years earlier for time instead of depth. The GRU, or gated recurrent unit, proposed by Kyunghyun Cho and colleagues in 2014, is a simpler two-gate version that performs about as well.

LSTMs powered most of the language technology of the 2010s: speech recognition on phones, early neural machine translation, autocomplete on keyboards.

3. Encoder and decoder, and the bottleneck

Translation added a new requirement: the input and the output are both sequences, of different lengths. "Where is my parcel?" is four words in English and may be a different number in Hindi. In 2014, Ilya Sutskever, Oriol Vinyals and Quoc Le at Google showed a design called sequence to sequence that handled this. One LSTM, the encoder, reads the whole input sentence and produces its final memory. A second LSTM, the decoder, starts from that memory and generates the output one word at a time, each new word fed back in as the next step's input, until it produces an "end of sentence" marker.

It worked surprisingly well, and it had an obvious weakness. The entire meaning of the input sentence has to squeeze through one fixed-size vector, the encoder's final memory, before the decoder can use any of it. For a five-word sentence that is fine. For a fifty-word sentence, it is like summarising a paragraph into one number list of fixed length and then asking someone to translate the paragraph from your summary alone. Translation quality fell off sharply as sentences got longer.

4. Attention: let the decoder look back

The fix, published in 2014 by Dzmitry Bahdanau, Kyunghyun Cho and Yoshua Bengio, is the most important idea in this Part after backpropagation, and it is simple to state: instead of forcing everything through the final memory, keep the encoder's memory at every word, and let the decoder look back at all of them, choosing which ones to focus on at each step. That choosing is called attention.

How does the decoder decide where to look? It compares what it currently needs with each encoder word, using the dot product of 12.2.1 as a similarity score, and turns the scores into weights with softmax from 12.2.6. A tiny worked example, with two-number vectors so the arithmetic is visible:

• The decoder's current state, "what am I looking for": \mathbf{q} = (1, 0).
• Encoder states for three input words: "parcel" (1, 0), "never" (0, 1), "arrived" (0.7, 0.7).

Attention, step by step. The decoder compares its query with every encoder word (①), softmax turns the similarity scores into weights that add to 1 (②), and the decoder receives a weighted average of the words' vectors (③), mostly "parcel", partly "arrived", a little "never".

1. Score each word with a dot product: \mathbf{q} \cdot \text{parcel} = 1, \mathbf{q} \cdot \text{never} = 0, \mathbf{q} \cdot \text{arrived} = 0.7.
2. Turn scores into weights with softmax: e^{1} \approx 2.718, e^{0} = 1, e^{0.7} \approx 2.014, adding to 5.732, so the weights are 0.474, 0.174 and 0.351. They add to 1.
3. Take the weighted average of the word vectors: 0.474 \times (1, 0) + 0.174 \times (0, 1) + 0.351 \times (0.7, 0.7) \approx (0.720, 0.420). This context vector is what the decoder uses at this step.

The decoder is no longer limited to one summary. At every output word it builds a fresh mixture of the input words it currently needs: when producing the word for "parcel" it looks mostly at "parcel", and when producing the verb it looks at "arrived". Translation quality stopped collapsing on long sentences, and when people plotted the weights, they could see the model lining up words between the two languages, often correctly handling word-order differences between them, without ever being told which word matched which.

Notice that nothing in these three steps involves the step-by-step recurrence. Comparing a query with every position, taking a softmax, and averaging can all be done for every position at the same moment.

5. Why recurrence lost

By 2016, the best language systems were LSTM encoders and decoders with attention between them. They still had the flaw marked in section 1: each step must wait for the one before it. A GPU, as 12.2.2 explained, is fast because it does thousands of independent calculations at the same moment. An RNN reading a 500-word document has 500 calculations that must happen one after another. However large the GPU, most of it sits idle, waiting.

That mattered more and more, because the field was discovering that the single most reliable way to improve language models was to train them on more text. An architecture that could not use the hardware fully could not be trained on enough text to compete.

In 2017, a team at Google asked the obvious question in a paper whose title answered it: "Attention Is All You Need." If attention can connect any two positions directly, why keep the recurrence at all? Their transformer removed it entirely. Every word attends to every other word directly, in one step, and all the positions are processed at the same moment, so a GPU can be fully used. Information no longer has to pass through a long chain of memory updates to travel from the first word to the last: any word can look at any other in a single step, so long-range dependencies became easy. Order, which recurrence gave for free, is put back in by adding position information to each word, as Chapter 12.7.4 explains.

The transformer trained faster, scaled to far more data, and was better. Within a few years it had replaced recurrent networks almost everywhere in language, and then spread to vision (the vision transformer of 12.5.5), speech and more. The attention you just computed by hand, scaled up with learned projections and many parallel copies, is the core of every LLM, and Chapter 12.7.3 works through it in full.

import torch
import torch.nn as nn

emails = torch.randn(8, 40, 64)          # (1) 8 emails, 40 words each, 64 numbers per word

lstm = nn.LSTM(input_size=64, hidden_size=128, batch_first=True)
out, (h, c) = lstm(emails)               # (2) reads the 40 words in order
print(out.shape, h.shape)                # → torch.Size([8, 40, 128]) torch.Size([1, 8, 128])

attn = nn.MultiheadAttention(embed_dim=64, num_heads=4, batch_first=True)
mixed, weights = attn(emails, emails, emails)   # (3) every word looks at every word, all at once
print(mixed.shape, weights.shape)        # → torch.Size([8, 40, 64]) torch.Size([8, 40, 40])

Line (1) makes a batch of eight stand-in emails, each 40 words long with 64 numbers per word: a tensor of shape (8, 40, 64), as in 12.2.2. Line (2) runs an LSTM over them; internally it must process word 1, then word 2, and so on to word 40. out holds the memory after every word, and h the final memory for each email. Line (3) runs a transformer-style attention layer on the same batch. The weights output has shape (8, 40, 40): for each email, a 40 by 40 table saying how much each word attended to each other word, all computed at once with matrix multiplications rather than a 40-step loop. That 40 by 40 table is what the next chapter is about.

Recall

• Sequences vary in length, depend on order, and have long-range links, so bag-of-words cannot tell "parcel arrived but never the charger" from its reverse.
• A recurrent neural network updates a hidden state word by word with shared weights. Its memory and its gradient shrink by a factor each step, so it cannot learn dependencies more than a few words back.
• The LSTM adds a cell state updated mostly by addition, controlled by forget, input and output gates, giving a clean long-distance path, like a residual connection across time. The GRU is a simpler version.
• An encoder and decoder handle sequence-to-sequence tasks like translation, but squeezing the whole input into one vector is a bottleneck.
• Attention lets the decoder score every input position (dot product), softmax the scores into weights, and take a weighted average. Recurrence still forced step-by-step work that wasted GPUs; the transformer (2017) dropped recurrence and kept attention, processing all positions at once.

Self-test: In the tiny RNN, why does the first input fade by about half each step? In the attention example, how would the weights change if the query were (0, 1)? Give the single reason the transformer could be trained on far more text than an LSTM in the same time.

Next: 12.5.7 Training at Scale — the transformer's whole advantage is that it can use enormous hardware; the last deep learning page covers what that hardware is, how big models are made to fit and train across many machines, and how to keep track of every experiment along the way.