Sequences: from recurrence to attention

The problem with a sequence

A sentence, a time series, a sequence of user actions. Two properties break the tools so far: the length varies, and order matters.

Recurrent networks, and their ceiling

Process one element at a time, carrying a hidden state forward:

h_t = f(W_h * h_{t-1} + W_x * x_t)

The state is a running summary of everything seen so far. Elegant, handles any length, and it dominated sequence modelling for two decades.

It has two problems that turned out to be fatal.

Long-range dependencies. “The cat, which had spent the entire afternoon asleep on the warm bricks by the kitchen door, was hungry.” The verb agrees with “cat”, 18 words back. To carry that information the network multiplies its hidden state by W_h eighteen times, and repeated multiplication shrinks or explodes exactly as in backpropagation. LSTMs and GRUs address this with gates that let information pass through unchanged when the gate is open (the same idea as a residual connection) and they extend the usable range considerably without removing the limit.

No parallelism. h_t needs h_{t-1}, so a sequence of 500 elements requires 500 sequential steps. This cannot be parallelised, and on hardware built for parallel arithmetic it is the difference between training in days and training in weeks.

Attention

Instead of forcing everything through one running state, let every position look directly at every other position and decide what is relevant.

For each position, produce three vectors from its representation: a query (what am I looking for), a key (what do I offer), and a value (what I will contribute). Compare each query against every key by dot product, softmax the results into weights, and take the weighted sum of the values.

attention(Q, K, V) = softmax(Q K' / sqrt(d)) V

Read it as a soft dictionary lookup. Rather than retrieving one entry by exact match, you retrieve a weighted blend of all of them, weighted by similarity.

The sqrt(d) matters and is easy to skip past. Dot products of d-dimensional vectors grow with d, and large values push softmax into a region where it is nearly one-hot and its gradients nearly vanish. Dividing by the square root of the dimension keeps the scale stable.

What this changed

Any position reaches any other in one step. No multiplication chain, so the 18-word dependency is as easy as an adjacent one. Long-range structure stops being the hard case.

Everything is parallel. Every position’s attention is computed simultaneously, as a couple of large matrix multiplications, which is exactly what GPUs are built for. This is the practical reason transformers won: the same idea, trainable on far more data in the same wall-clock time.

Order must be reinserted. Attention treats the input as a set: permute the inputs and the outputs permute with them, unchanged. So position information is added explicitly, as a positional encoding, which is a slightly awkward patch on an otherwise clean idea and is still an area of active design.

The cost

Every position attends to every other, so computation grows with the square of the sequence length. Double the context and you quadruple the cost. This is the central engineering constraint of the whole architecture, and the reason context windows were 512 tokens in 2018 and expanded only as sparse patterns, linear approximations and memory-efficient exact implementations such as FlashAttention arrived.

It is worth being clear that this is a genuine limit rather than a temporary one. The workarounds are approximations or better memory management, not a change to the quadratic relationship itself.

Multi-head attention

Run several attention operations in parallel with different learned projections, then concatenate. One head may track syntactic agreement, another coreference, another position. Analyses of what individual heads do have found interpretable roles in some cases and nothing clean in many others, so treat “head 4 does syntax” as an occasional finding rather than a design principle.

Where this leaves you

A transformer block is: multi-head attention, a residual connection, layer normalisation, a small feed-forward network, another residual, another normalisation. Every component in that list appeared earlier in this module. Stack the block 12 or 96 times and you have the architecture behind essentially every modern language model.

That is the point of ending here. The parts are not exotic. They are the linear layer from module 2, the non-linearity from earlier in this module, the residual connection and normalisation from the initialisation lesson, and one new operation: a weighted average whose weights are computed from similarities. Understanding that composition is a reasonable place for a foundations course to stop.