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.
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.
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 length10 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.
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)
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
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
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.
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
Thecatsatbecauseitwastired
click "it" — a classic coreference test — and watch it attend back to "cat"
Two flavours of self-attention — and what each can see
Flavour
Rule
Used by
Good for
Bidirectional
every token attends to every position, past and future
BERT, encoder stacks
understanding tasks — classification, embeddings, NER
Causal / masked
token i can only attend to positions ≤ i
GPT, LLaMA, decoder-only LLMs
valid 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
defattention(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.5if 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-attention
this sequence
the same sequence
Cross-attention
the target / decoder sequence
a 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.
one decoder layer — self-attention looks inward, cross-attention is the only step that looks at the 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
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
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.
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
Variant
KV heads stored
Cache size (h=64, g=8 example)
Quality vs MHA
Ships in
MHA
h (one per query head)
100%
baseline
original Transformer, GPT-3
GQA
g (shared across groups)
~12.5%
close to MHA
LLaMA 2 & 3, Mistral, Qwen2
MQA
1 (shared by all heads)
~1.6%
noticeably lower
PaLM, Falcon, StarCoder
MLA
0 — a compressed shared latent instead
smaller still, model-dependent
reported on par with, or above, MHA
DeepSeek-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.
the cache only ever holds cₜ — one small vector per token, shared by every head
MLA — compress once, reconstruct per head at attention time
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
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
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 attention
Sparse / linear (previous section)
FlashAttention
Output
exact
approximate
exact — identical to standard
Memory
O(n²)
O(n) to O(n log n)
O(n)
What changed
—
the attention pattern itself
only 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.
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.