The complete journey · 2014 → 2024

One idea.
Six generations.

From Bahdanau's alignment network to FlashAttention's IO-aware kernels — how one mechanism for "looking back" became the computational core of every modern language model.

Bahdanau Self-attention Cross-attention Sparse / Local MQA / GQA / MLA FlashAttention
Origins · Bahdanau, Cho & Bengio, 2014

The problem attention was built to solve

Before attention existed, translation models had to compress an entire sentence into one fixed-size vector. Attention's whole reason for existing is that this compression was lossy — and the loss got worse the longer the sentence.

A standard encoder–decoder RNN reads the source sentence token by token, and by the final step the encoder's last hidden state is expected to hold everything — every word, every dependency, every nuance — squeezed into one vector of fixed size. It doesn't matter if the sentence is five words or fifty; the vector stays the same size. The decoder then generates the entire translation from that single vector alone, never looking back at the source again.

encoder — reads "the cat sat on the mat" one fixed vector same size, any length decoder — generates from that vector alone
every source word is compressed through the same narrow gate, no matter how long the sentence gets
What actually broke: translation quality (BLEU score) held up fine on short sentences and degraded sharply as source length grew — the fixed vector simply ran out of room. This single empirical observation, more than any theoretical argument, is what motivated the fix.

Try it — quality vs. sentence length

Drag the slider to see the pattern the original paper observed: a plain encoder–decoder degrades as sentences get longer, while a model that can look back at every source word holds steady.

sentence length 10 words
without attention
90%
with attention
88%
illustrative translation-quality trend, shaped after the pattern reported in Bahdanau et al. (2014), Figure 2

Bahdanau's fix — let the decoder look back

Instead of discarding the encoder's hidden states after producing the final summary, keep all of them — \(h_1, h_2, \dots, h_{T_x}\) — and let the decoder consult all of them at every single output step, deciding fresh each time which ones matter most.

decoder state s(t-1) — "what am I generating next?" decoder state h₁ the h₂ cat h₃ sat h₄ on h₅ mat encoder hidden states — all of them are kept, none are discarded line weight = α(t,j) — recomputed at every decoding step
generating the word aligned with "sat" — the decoder puts most of its weight there, a little on its neighbours
Step 1 — alignment / energy score (a small feed-forward network)
$$e_{tj} = v_a^\top \tanh\!\big(W_a s_{t-1} + U_a h_j\big)$$
Step 2 — softmax normalises the scores into weights that sum to 1
$$\alpha_{tj} = \frac{\exp(e_{tj})}{\sum_{k=1}^{T_x} \exp(e_{tk})}$$
Step 3 — context vector: the weighted sum of every encoder state
$$c_t = \sum_{j=1}^{T_x} \alpha_{tj}\, h_j$$

Because the scoring function concatenates \(s_{t-1}\) and \(h_j\) and pushes them through a learned \(\tanh\) layer rather than a dot product, this is called additive attention. \(c_t\) is recomputed fresh at every single decoding step, so the model attends to a different part of the source sentence for each output word — and because the whole thing is differentiable, it trains end to end with ordinary backpropagation, no separate alignment step required.

Why this mattered beyond the numbers: plotting α(t,j) as a heatmap over source × target positions produces something that looks like a classic statistical-MT alignment matrix — the model learned to "point" at the right source word for each output word, entirely as an emergent, learned behaviour. That interpretability, as much as the quality gain, is why this paper became foundational.
2017 · Vaswani et al., "Attention Is All You Need"

Self-attention — a sequence looking at itself

Self-attention lets every token in a sequence gather information from every other token in that same sequence — including itself. It's the mechanism that let transformers throw the RNN away entirely.

For every token, learn three separate projections of its embedding: a query (what am I looking for), a key (what do I offer, for matching purposes), and a value (what content do I actually contribute once selected). This is the key generalisation over Bahdanau, who reused one encoder state for both matching and content — separating key and value gives the model strictly more room to learn.

A useful mental model borrowed from information retrieval: think of it as a soft database lookup. Every token throws a query into the room ("who has information relevant to me?"), every token also holds up a key as an advertisement of what it contains, and matching a query against a key produces a relevance score. Unlike a real database, nothing is retrieved all-or-nothing — every token's value gets pulled in, just weighted by how relevant its key turned out to be.

Step 0 — project the input into queries, keys and values
$$Q = XW_Q \qquad K = XW_K \qquad V = XW_V$$

\(X\) is the matrix of input embeddings (one row per token), and \(W_Q, W_K, W_V\) are learned weight matrices — the only parameters in a single attention head. Everything downstream is deterministic matrix arithmetic on \(Q\), \(K\), \(V\).

Block diagram — the full pipeline, one head

input embeddings X Q = X · W_Q K = X · W_K V = X · W_V QKᵀ similarity scores, all pairs ÷ √d_k + causal mask optional — decoder-only models softmax (row-wise) V bypasses straight here weights · V weighted sum of value vectors output Z
shapes: X is [n, d_model] Q, K, V are [n, d_k] QKᵀ is [n, n] Z is [n, d_v]
every box is either a learned projection or a parameter-free operation — the whole head has exactly three weight matrices
Putting the pipeline back together
$$\text{Attention}(Q,K,V) = \text{softmax}\!\left(\frac{QK^\top}{\sqrt{d_k}} + M\right)V$$

The \(\sqrt{d_k}\) scaling matters more than it looks: without it, dot products grow large as dimensionality increases, pushing softmax into a saturated region with near-zero gradients — the network stops learning from those positions. \(M\) is the optional mask matrix from the dashed box above — all zeros for bidirectional attention, or the causal pattern covered further down.

Where the O(n²) cost actually lives: the QKᵀ box is an [n, n] matrix — one score per pair of tokens. Double the sequence length and that box quadruples in size; every method in the Efficient Attention section further down exists specifically to shrink or avoid materialising this one box.

Block diagram — splitting into multiple heads

In practice you never run just one attention function. \(d_{model}\) is split across \(h\) heads, each with its own \(W_Q, W_K, W_V\) and a smaller dimension \(d_k = d_{model}/h\) — so the total compute stays roughly the same as one big head, but the model gets \(h\) independent "lenses" on the sequence instead of one averaged view.

Multi-head attention
$$\text{head}_i = \text{Attention}(QW_i^Q,\, KW_i^K,\, VW_i^V)$$ $$\text{MultiHead}(Q,K,V) = \text{Concat}(\text{head}_1,\dots,\text{head}_h)\,W^O$$
input X head 1 own Wq, Wk, Wv head 2 own Wq, Wk, Wv head 3 own Wq, Wk, Wv head 4 own Wq, Wk, Wv concat(head₁, head₂, head₃, head₄) · Wᴼ → output one linear layer blends the heads back together
four heads shown for clarity — GPT-3-scale models run 96 of these in parallel, per layer

Each head gets its own learned projections, so different heads can specialise — empirically, some track syntax, some track coreference, some track raw positional distance. Concatenating and projecting the results gives the model several independent "lenses" on the same sequence at once, instead of one averaged view.

Try it — click a token to see what it attends to

The cat sat because it was tired
click "it" — a classic coreference test — and watch it attend back to "cat"

Two flavours of self-attention — and what each can see

FlavourRuleUsed byGood for
Bidirectionalevery token attends to every position, past and futureBERT, encoder stacksunderstanding tasks — classification, embeddings, NER
Causal / maskedtoken i can only attend to positions ≤ iGPT, LLaMA, decoder-only LLMsvalid autoregressive generation — can't peek at the answer
bidirectional
every (query, key) pair is lit — the whole grid
causal / masked
only the lower triangle — position i never sees j > i
The causal mask, added to the scores before softmax
$$M_{ij} = \begin{cases} 0 & j \le i \\ -\infty & j \gt i \end{cases}$$

Adding \(-\infty\) before softmax is what makes this work: \(e^{-\infty} = 0\), so those positions get exactly zero weight — not "very small," genuinely zero. That's what guarantees a decoder-only model can never leak information from a future token during training.

scaled_dot_product_attention.py
def attention(Q, K, V, causal=False): # Q, K, V: [batch, heads, seq_len, d_k] d_k = Q.shape[-1] scores = Q @ K.transpose(-2, -1) / d_k ** 0.5 if causal: # block every position from seeing the future mask = torch.triu(torch.ones_like(scores), diagonal=1) scores = scores.masked_fill(mask.bool(), float("-inf")) weights = torch.softmax(scores, dim=-1) return weights @ V # [batch, heads, seq_len, d_v]
💡
Interview soundbite: self-attention builds context-aware representations of a sequence by letting each token gather information from every other token in the same sequence — same math as Bahdanau's alignment, generalised into learned Q/K/V projections and computed for every position simultaneously instead of just decoder-against-encoder.
2017 · the layer that connects two sequences

Cross-attention — one sequence querying another

Structurally identical to self-attention — same formula, same softmax — with one change that matters enormously: where Q, K, and V come from.

Query (Q)Key & Value (K, V)
Self-attentionthis sequencethe same sequence
Cross-attentionthe target / decoder sequencea different sequence — usually the encoder's output

This is exactly what Bahdanau attention was doing conceptually — reformulated with learned Q/K/V projections and computed in the standard transformer attention form instead of an additive scoring MLP. In the original encoder–decoder transformer, every decoder layer runs masked self-attention over its own tokens first, then cross-attends into the encoder's final output — that second step is the only place source and target sequences actually connect.

decoder input (previous tokens) masked self-attention cross-attention Q from decoder · K,V from encoder encoder output K, V live here feed-forward network decoder output
one decoder layer — self-attention looks inward, cross-attention is the only step that looks at the source
Same formula — different source for K, V
$$\text{CrossAttn}(Q_{\text{dec}}, K_{\text{enc}}, V_{\text{enc}}) = \text{softmax}\!\left(\frac{Q_{\text{dec}} K_{\text{enc}}^\top}{\sqrt{d_k}}\right)V_{\text{enc}}$$

Where cross-attention shows up

Machine translation
Target ← Source
the original use case — every decoder layer cross-attends into the encoder's representation of the source sentence.
Vision-language models
Text ← Image patches
Flamingo, BLIP-2 — text tokens cross-attend into visual features from a separate frozen or lightly-tuned vision encoder.
Perceiver / Perceiver IO
Latents ← Raw input
cross-attention compresses an arbitrarily large input down into a small fixed set of latent vectors — inverts the usual bottleneck problem into a deliberate design choice.
Diffusion models
Image ← Text prompt
Stable Diffusion's U-Net cross-attends into CLIP text embeddings to condition image generation on a prompt.
2019 onward · attacking the O(n²) cost

Efficient attention — sparse, local & linear

Full self-attention computes an n×n score matrix — every token against every token. Double the sequence length and you quadruple the compute and memory. This is the single biggest obstacle to long-context models, and it spawned an entire research subfield.

Try it — which pairs actually get computed?

Each cell is a (query, key) pair. Full attention lights up the whole grid. Everything below is a strategy for lighting up far fewer cells while still capturing what matters.

key position →query position ↓
every query attends to every key — n² pairs, no matter how long the sequence is
Cost per layer, sequence length n, window size w, dimension d
$$O(n^2 d)\ \text{full} \quad\rightarrow\quad O(n\,w\,d)\ \text{local/sparse} \quad\rightarrow\quad O(n\,d^2)\ \text{linear / kernelised}$$

The methods

Child et al., 2019
Sparse Transformer
fixed strided/local pattern instead of full attention — roughly O(n√n). First proof that you don't need every pair.
Beltagy et al., 2020
Longformer
sliding local window plus a handful of global tokens (e.g. [CLS]) that attend to and are attended by everything.
Zaheer et al., 2020
BigBird
local + global + random attention. Proves theoretically the sparse pattern preserves full attention's expressiveness.
Kitaev et al., 2020
Reformer
locality-sensitive hashing buckets similar queries and keys together — only attends within a bucket, approximating full attention.
Choromanski et al., 2020
Performer (linear)
approximates the softmax kernel with random features (FAVOR+) — genuinely O(n), at some cost in exactness.
Mistral 7B, 2023
Sliding window attention
each token only attends within a fixed window per layer — but the effective reach grows with depth, like a CNN's receptive field.
💡
The common thread: every method above trades some completeness of the attention pattern for compute savings. That's the key distinction from the next section — none of these give you the exact same output as full attention, they approximate it.
2019 – 2024 · shrinking the KV cache

Multi-Query, Grouped-Query & Latent Attention

A different bottleneck than compute: during autoregressive generation you cache every previous token's K and V so you don't recompute them each step. That cache — not the model weights — becomes the dominant memory cost for long generations.

KV cache size per layer — n = tokens cached, h = query heads, g = KV groups, dₕ = head dimension
$$\text{MHA: } 2nh\,d_h \quad\ \text{GQA: } 2ng\,d_h \ (g \lt h) \quad\ \text{MQA: } 2n\,d_h \ (g{=}1) \quad\ \text{MLA: } \approx n\,d_c \ (d_c \ll h\,d_h)$$

Block diagram — why the cache grows every single step

Autoregressive generation produces one token at a time, and every new token needs its own K and V computed and appended to what's already stored — recomputing K/V for every earlier token, every step, would be wasteful, so instead the cache just accumulates.

t₁ K,V cached t₂ K,V cached t₃ K,V cached t₄ K,V cached t₅ computing now t₆ not generated yet attention(query₅, all cached K, V) only t₅'s Q is new — t₁…t₄'s K,V are reused, not recomputed cache size ∝ tokens generated so far
by the time you're 4,000 tokens into a conversation, that's 4,000 K/V pairs sitting in memory per layer, per head group
🔢
Worked example — LLaMA-2 70B (64 query heads, 8 KV groups, head dim 128, 80 layers, bf16):
MHA cache would need 2 × 64 × 128 × 2 bytes = 32KB per token per layer → 2.5MB per token across all 80 layers.
The GQA it actually ships with needs 2 × 8 × 128 × 2 bytes = 4KB per token per layer → 320KB per token — an 8× reduction, exactly matching g/h = 8/64. At a 32K-token context, that's the difference between roughly 82GB and 10GB of cache.

Head-sharing patterns, side by side

baseline
MHA
every query head owns its own K/V head — best quality, largest cache (100%).
Ainslie et al., 2023
GQA
groups of query heads share one K/V head — used in LLaMA 2/3, Mistral. Tunable middle ground.
Shazeer, 2019
MQA
all query heads share one K/V head — smallest cache, fastest decode, some quality cost.
DeepSeek-V2, 2024
MLA
K/V compressed into a shared low-rank latent, reconstructed per-head at attention time — even smaller cache, minimal quality loss.

All four, compared directly

VariantKV heads storedCache size (h=64, g=8 example)Quality vs MHAShips in
MHAh (one per query head)100%baselineoriginal Transformer, GPT-3
GQAg (shared across groups)~12.5%close to MHALLaMA 2 & 3, Mistral, Qwen2
MQA1 (shared by all heads)~1.6%noticeably lowerPaLM, Falcon, StarCoder
MLA0 — a compressed shared latent insteadsmaller still, model-dependentreported on par with, or above, MHADeepSeek-V2, DeepSeek-V3

Block diagram — how MLA actually compresses the cache

GQA and MQA save memory by literally storing fewer K/V vectors. MLA takes a different approach entirely: it never stores per-head K/V at all. Instead, each token is compressed down into one small shared latent vector — that's the only thing written to the cache — and the full per-head K and V are reconstructed from it on the fly, fresh, every time attention is computed.

hidden state hₜ down-projection W^DKV compresses to a much lower rank latent cₜ dc ≪ h·dh ← only this is written to the KV cache up-projection W^UK one per head, computed on demand up-projection W^UV one per head, computed on demand reconstructed Kᵢ, Vᵢ per head used for this attention call, then discarded — never cached
the cache only ever holds cₜ — one small vector per token, shared by every head
MLA — compress once, reconstruct per head at attention time
$$c_t = W^{DKV} h_t \qquad K_i = W_i^{UK} c_t \qquad V_i = W_i^{UV} c_t$$

Only \(c_t\) — the compressed latent — ever touches the KV cache. The per-head \(K_i, V_i\) are recomputed from it inside every attention call and thrown away immediately after, so the cache footprint depends on the latent dimension \(d_c\) rather than on \(h \times d_h\) at all. DeepSeek-V2's reported result — a far smaller cache with quality matching or beating full MHA — is what makes this the most aggressive entry in the family, at the cost of noticeably more implementation complexity than GQA.

Try it — how much cache does grouping actually save?

GQA groups (of 8 heads) 2 groups
MHA
100%
GQA (yours)
25%
MQA
12.5%
MLA (illustrative)
6%
cache size relative to full MHA at the same sequence length — dragging the slider changes only the GQA bar
What LLaMA 2/3 and Mistral actually ship: GQA, not MQA — because sharing K/V across small groups (e.g. 8 groups for 32 query heads) recovers nearly all of MHA's quality while still cutting the cache dramatically, whereas full MQA sharing loses noticeably more.
2022 · Dao et al. — an algorithm, not a new pattern

FlashAttention — exact, just faster

This is the one everyone confuses with the sparse/linear methods above. It isn't an approximation at all — it computes the exact same standard softmax attention, bit-for-bit equivalent output. The entire win is where the arithmetic happens.

A GPU has two very different kinds of memory: HBM (high-bandwidth memory — tens of gigabytes, but slow to access) and SRAM (on-chip cache — tiny, maybe 20MB, but extremely fast). Standard attention computes the full n×n score matrix and writes it out to HBM, then reads it back for softmax, then reads it again for the final matmul with V — several slow round trips to the big, slow memory for something that's only ever used briefly. FlashAttention never materialises that full matrix in HBM at all.

Standard attention
Materialise, then compute
HBM — large, slow n×n score matrix fully materialised in HBM ↺ read + write, several passes
memory grows as O(n²); most of the runtime is spent waiting on HBM bandwidth, not on the actual math.
FlashAttention
Tile in SRAM, write once
HBM — large, slow SRAM tile Q,K,V blocks + softmax output written once
memory is O(n) — the full matrix is never formed; blocks are tiled through fast SRAM and softmax is computed incrementally.

The trick that makes tiling possible is online softmax: softmax normally needs the full row of scores before it can normalise, but there's a numerically stable running-update formula that lets you process the row in small chunks, updating a running max and running sum as you go, and rescaling the accumulated output so far each time a new chunk arrives. That's what lets attention be computed block-by-block without ever holding the whole row in memory at once.

Standard attentionSparse / linear (previous section)FlashAttention
Outputexactapproximateexact — identical to standard
MemoryO(n²)O(n) to O(n log n)O(n)
What changedthe attention pattern itselfonly the implementation
load_model.py — one flag, free speedup
model = AutoModelForCausalLM.from_pretrained( "meta-llama/Llama-3-8b", torch_dtype = torch.bfloat16, attn_implementation = "flash_attention_2", # same outputs, less HBM traffic )
The interview trap: don't lump FlashAttention in with Longformer/Performer/sparse attention. Those change what gets computed and trade quality for speed. FlashAttention changes where the arithmetic happens and gives you the exact same numbers, faster and with less memory — which is exactly why it got adopted almost universally with zero controversy, unlike the approximate methods.
Ten years, one thread

The full timeline

Every later idea is a response to a cost the previous idea introduced — a straight line from "the decoder can't see the source" to "don't waste GPU memory bandwidth."

2014

Bahdanau attention

additive alignment network — decoder consults every encoder state instead of one fixed vector. Solves the compression bottleneck.

2015

Luong attention

multiplicative / dot-product scoring — simpler and faster than Bahdanau's feed-forward network. Direct ancestor of scaled dot-product attention.

2017

"Attention Is All You Need"

self-attention + cross-attention + multi-head attention. RNNs removed entirely — attention becomes the whole architecture.

2018 – 19

Relative position attention · Sparse Transformer · MQA

Transformer-XL's relative positions; first sparse attention patterns; Shazeer's Multi-Query Attention for faster decoding.

2020

Longformer · BigBird · Reformer · Performer

the efficient-attention wave — local windows, global tokens, LSH bucketing, linear kernel approximations.

2021

RoPE · ALiBi

position folded directly into the attention score instead of a separate embedding — better length extrapolation.

2022

FlashAttention

IO-aware exact attention — tiles Q/K/V through fast SRAM, never materialises the full n×n matrix in slow HBM.

2023

Grouped-Query Attention · FlashAttention-2

GQA becomes the production default (LLaMA 2/3, Mistral); FlashAttention-2 pushes GPU utilisation further.

2024

Multi-head Latent Attention

DeepSeek-V2 compresses K/V into a shared low-rank latent — an even smaller KV cache with reported quality on par with full MHA.

Decision guide

Which attention does your model actually need?

Answer these in order — by the second question you know your architecture.

What kind of sequence relationship are you modelling?
Understanding one sequence (classification, embeddings, NER) → bidirectional self-attention, no causal mask
Generating text token by token → causal / masked self-attention
One sequence needs to consult a different one (translation, image→text) → cross-attention
Is sequence length the bottleneck?
Yes, need 100k+ tokens of context → local/sliding-window or linear attention, layered with FlashAttention regardless
No, typical context lengths are fine → full attention is fine, just make it FlashAttention — there's no downside
Is inference cost / KV cache the bottleneck?
Serving an existing open-weight checkpoint → the head-sharing scheme is already baked in; you can't change MHA→GQA after the fact
Training a new model, serving many concurrent users → design in GQA (safe, proven default) or MLA (more aggressive, more engineering effort)
🎯
The one-paragraph version: attention started as a fix for one fixed-length vector holding an entire sentence hostage. Transformers generalised the fix into the whole architecture. Everything since has attacked one of three costs — the O(n²) compute of full attention, the KV-cache memory of autoregressive decoding, or the missing sense of position in a permutation-invariant mechanism — without ever touching the two-line idea underneath: score every relevant pair, then take a weighted sum.