{"course":{"slug":"machine-learning-foundations","title":"Machine Learning, Foundations","url":"https://addaly.com/learn/machine-learning-foundations","level":"intermediate","track":"start"},"lesson":{"slug":"from-sequences-to-attention","title":"Sequences: from recurrence to attention","url":"https://addaly.com/learn/machine-learning-foundations/from-sequences-to-attention","position":81,"of":92,"minutes":9,"answer":"Attention lets every position read every other in one step by computing a similarity-weighted average, which removes the multiplication chain that limited recurrent networks and parallelises training.","keyIdea":"Attention lets every position read every other in one step by computing a similarity-weighted average, which removes the multiplication chain that limited recurrent networks and parallelises training, at a cost that grows with the square of the sequence length."},"body":{"format":"markdown","text":"## The problem with a sequence\n\nA sentence, a time series, a sequence of user actions. Two properties break the tools so far: the length varies, and order matters.\n\n## Recurrent networks, and their ceiling\n\nProcess one element at a time, carrying a hidden state forward:\n\n```text\nh_t = f(W_h * h_{t-1} + W_x * x_t)\n```\n\nThe state is a running summary of everything seen so far. Elegant, handles any length, and it dominated sequence modelling for two decades.\n\nIt has two problems that turned out to be fatal.\n\n**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.\n\n**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.\n\n## Attention\n\nInstead of forcing everything through one running state, let every position look directly at every other position and decide what is relevant.\n\nFor 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.\n\n```text\nattention(Q, K, V) = softmax(Q K' / sqrt(d)) V\n```\n\nRead 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.\n\nThe `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.\n\n## What this changed\n\n**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.\n\n**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.\n\n**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.\n\n## The cost\n\nEvery 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.\n\nIt 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.\n\n## Multi-head attention\n\nRun 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.\n\n## Where this leaves you\n\nA 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.\n\nThat 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."},"check":{"question":"A team replaces an LSTM with a transformer on 800-element sequences and finds memory use rises sharply. What property explains it?","options":[{"text":"Transformers have more parameters per layer than LSTMs, so the model itself is larger.","correct":false,"tempting":"Parameter counts do differ, but the model's own size does not scale with sequence length, and the reported problem appeared when sequences got long."},{"text":"Layer normalisation stores statistics per position, which grows with sequence length.","correct":false,"tempting":"Layer norm's statistics are a few numbers per position and are trivial next to the attention matrix."},{"text":"Attention computes a score for every pair of positions, so an 800-element sequence produces a 640,000-entry matrix per head per layer, and memory grows with the square of the length.","correct":true},{"text":"Transformers cannot process sequences incrementally, so the whole dataset must be held in memory at once.","correct":false,"tempting":"Batching works normally; it is the per-sequence attention matrix rather than the dataset that drives the memory cost."}]},"prev":{"slug":"convolutions","title":"Convolution: the same detector, everywhere in the image","url":"https://addaly.com/learn/machine-learning-foundations/convolutions"},"next":{"slug":"transfer-learning","title":"Standing on somebody else's compute","url":"https://addaly.com/learn/machine-learning-foundations/transfer-learning"},"authorship":"Founder and series editor: Dr Mustafa Mun. Written by AI models to a written standard. Exam keys checked blind by a second model: 3,665 of 3,666 agreed. Academic review invited.","review":{"status":"Draft, open for academic review"},"cite":"Addaly (2026) 'Sequences: from recurrence to attention', in Machine Learning, Foundations. Edited by M. Mun. Addaly. Available at: https://addaly.com/learn/machine-learning-foundations/from-sequences-to-attention (Accessed: 13 October 2026).","licence":{"name":"CC BY-NC-SA 4.0","url":"https://creativecommons.org/licenses/by-nc-sa/4.0/"},"reader":{"schema":1,"title":"Sequences: from recurrence to attention","courseTitle":"Machine Learning, Foundations","module":{"index":8,"slug":"neural-networks","title":"Neural networks, built from what you already know"},"answer":null,"keyIdea":"Attention lets every position read every other in one step by computing a similarity-weighted average, which removes the multiplication chain that limited recurrent networks and parallelises training, at a cost that grows with the square of the sequence length.","hero":{"kind":"plate","image":null,"alt":null,"caption":null},"blocks":[{"t":"h2","id":"the-problem-with-a-sequence","runs":[{"text":"The problem with a sequence"}]},{"t":"p","runs":[{"text":"A sentence, a time series, a sequence of user actions. Two properties break the tools so far: the length varies, and order matters."}]},{"t":"h2","id":"recurrent-networks-and-their-ceiling","runs":[{"text":"Recurrent networks, and their ceiling"}]},{"t":"p","runs":[{"text":"Process one element at a time, carrying a hidden state forward:"}]},{"t":"code","lang":"text","label":"Text","text":"h_t = f(W_h * h_{t-1} + W_x * x_t)"},{"t":"p","runs":[{"text":"The state is a running summary of everything seen so far. Elegant, handles any length, and it dominated sequence modelling for two decades."}]},{"t":"p","runs":[{"text":"It has two problems that turned out to be fatal."}]},{"t":"p","runs":[{"text":"Long-range dependencies.","b":true},{"text":" “The cat, which had spent the entire afternoon asleep on the warm bricks by the kitchen door, "},{"text":"was","b":true},{"text":" hungry.” The verb agrees with “cat”, 18 words back. To carry that information the network multiplies its hidden state by "},{"text":"W_h","code":true},{"text":" eighteen times, and repeated multiplication shrinks or explodes exactly as in backpropagation. "},{"text":"LSTMs","b":true},{"text":" and "},{"text":"GRUs","b":true},{"text":" 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."}]},{"t":"p","runs":[{"text":"No parallelism.","b":true},{"text":" "},{"text":"h_t","code":true},{"text":" needs "},{"text":"h_{t-1}","code":true},{"text":", 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."}]},{"t":"h2","id":"attention","runs":[{"text":"Attention"}]},{"t":"p","runs":[{"text":"Instead of forcing everything through one running state, let every position look directly at every other position and decide what is relevant."}]},{"t":"p","runs":[{"text":"For each position, produce three vectors from its representation: a "},{"text":"query","b":true},{"text":" (what am I looking for), a "},{"text":"key","b":true},{"text":" (what do I offer), and a "},{"text":"value","b":true},{"text":" (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."}]},{"t":"code","lang":"text","label":"Text","text":"attention(Q, K, V) = softmax(Q K' / sqrt(d)) V"},{"t":"p","runs":[{"text":"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."}]},{"t":"p","runs":[{"text":"The "},{"text":"sqrt(d)","code":true},{"text":" matters and is easy to skip past. Dot products of "},{"text":"d","code":true},{"text":"-dimensional vectors grow with "},{"text":"d","code":true},{"text":", 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."}]},{"t":"h2","id":"what-this-changed","runs":[{"text":"What this changed"}]},{"t":"p","runs":[{"text":"Any position reaches any other in one step.","b":true},{"text":" No multiplication chain, so the 18-word dependency is as easy as an adjacent one. Long-range structure stops being the hard case."}]},{"t":"p","runs":[{"text":"Everything is parallel.","b":true},{"text":" 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."}]},{"t":"p","runs":[{"text":"Order must be reinserted.","b":true},{"text":" 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."}]},{"t":"h2","id":"the-cost","runs":[{"text":"The cost"}]},{"t":"p","runs":[{"text":"Every position attends to every other, so computation grows with the "},{"text":"square","b":true},{"text":" 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."}]},{"t":"p","runs":[{"text":"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."}]},{"t":"h2","id":"multi-head-attention","runs":[{"text":"Multi-head attention"}]},{"t":"p","runs":[{"text":"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."}]},{"t":"h2","id":"where-this-leaves-you","runs":[{"text":"Where this leaves you"}]},{"t":"p","runs":[{"text":"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."}]},{"t":"p","runs":[{"text":"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."}]}],"check":{"question":[{"text":"A team replaces an LSTM with a transformer on 800-element sequences and finds memory use rises sharply. What property explains it?"}],"options":[{"text":[{"text":"Transformers have more parameters per layer than LSTMs, so the model itself is larger."}],"correct":false,"tempting":[{"text":"Parameter counts do differ, but the model’s own size does not scale with sequence length, and the reported problem appeared when sequences got long."}]},{"text":[{"text":"Layer normalisation stores statistics per position, which grows with sequence length."}],"correct":false,"tempting":[{"text":"Layer norm’s statistics are a few numbers per position and are trivial next to the attention matrix."}]},{"text":[{"text":"Attention computes a score for every pair of positions, so an 800-element sequence produces a 640,000-entry matrix per head per layer, and memory grows with the square of the length."}],"correct":true,"tempting":null},{"text":[{"text":"Transformers cannot process sequences incrementally, so the whole dataset must be held in memory at once."}],"correct":false,"tempting":[{"text":"Batching works normally; it is the per-sequence attention matrix rather than the dataset that drives the memory cost."}]}],"order":[3,1,2,0],"why":null},"prev":{"slug":"convolutions","title":"Convolution: the same detector, everywhere in the image","minutes":9},"next":{"slug":"transfer-learning","title":"Standing on somebody else’s compute","minutes":9}}}