Computational complexity of attention: Worked examples

Before anything, let us make sure every symbol is earned.

The scenario matrix

Every question this topic can ask lands in one of these cells. The worked examples below are labelled with the cell they cover, and together they hit all of them.

Cell	Regime / input	What decides the answer	Worked example
C1	Short sequence, $n ≪ d$	Projections $4 n d^{2}$ dominate	Ex 1
C2	Long sequence, $n ≫ d$	Attention $n^{2} d$ dominates	Ex 2
C3	Crossover, find $n^{*}$	Set the two terms equal	Ex 3
C4	Scaling law ("double $n$ ")	Ratio of new/old, quadratic behaviour	Ex 4
C5	Head count varies	Show $h$ cancels asymptotically	Ex 5
C6	Degenerate inputs $n = 0, 1$ ; $d_{k} = 0$	Limiting / boundary behaviour	Ex 6
C7	Real-world memory word problem	Bytes = floats × 4, sum over heads·layers	Ex 7
C8	Exam twist (spot the wrong factor)	The " $\times h$ " trap on projections	Ex 8

Ex 1 — Cell C1: short sequence, projections rule

Forecast: $n = 32$ is tiny compared to $d = 512$ . Guess before reading: attention or projections? Write down your guess.

Attention FLOPs $= h n^{2} d_{k} = 8 \times 3 2^{2} \times 64$ . Why this step? This is the score-computation-plus-aggregation term; it grows with $n^{2}$ , but $n^{2} = 1024$ is small here. $= 8 \times 1024 \times 64 = 524, 288 \approx 0.52$ M.
Projection FLOPs $= 4 n d^{2} = 4 \times 32 \times 51 2^{2}$ . Why this step? Q, K, V, and $W_{O}$ each cost $n d^{2}$ ; they scale only linearly in $n$ , so a short sequence keeps them from shrinking. $= 4 \times 32 \times 262, 144 = 33, 554, 432 \approx 33.6$ M.
Ratio attention / projection $= 0.52/33.6 \approx 0.0156$ . Why this step? The ratio is the single number that tells you who wins; $< 1$ means projections dominate.

Verify: Projections are $\approx 64 \times$ larger. Sanity: $n ≪ d$ , so the $n^{2} d$ term ( $\propto n^{2}$ ) is squashed while $4 n d^{2}$ ( $\propto d^{2}$ ) stays huge. Matches the parent's claim that short sequences are projection-bound. ✔

Ex 2 — Cell C2: long sequence, attention rules

Forecast: We just quadrupled-and-more the length. Guess the winner.

Attention FLOPs $= 8 \times 1638 4^{2} \times 64$ . Why this step? $1638 4^{2} \approx 2.68 \times 1 0^{8}$ — the quadratic term has finally exploded. $= 8 \times 268, 435, 456 \times 64 = 137, 438, 953, 472 \approx 137$ B.
Projection FLOPs $= 4 \times 16384 \times 51 2^{2} = 4 \times 16384 \times 262144 = 17, 179, 869, 184 \approx 17.2$ B. Why this step? Projections grew only $512 \times$ from Ex 1 (linear in $n$ ), while attention grew $\sim 262, 000 \times$ (quadratic).
Ratio $= 137/17.2 \approx 8.0$ . Why this step? We compute the ratio because a single number tells us who dominates: $> 1$ now means attention is the bigger cost, the exact reverse of Ex 1 where the ratio was $< 1$ . Watching this one number flip from $0.0156$ to $8.0$ is the whole story of the quadratic takeover.

Verify: Attention is $8 \times$ bigger. Cross-check with Ex 1: going from $n = 32$ to $16384$ is $512 \times$ longer. Attention $\propto n^{2}$ so grows $51 2^{2} = 262, 144 \times$ ; projections $\propto n$ grow $512 \times$ . Ratio should shift by $262144/512 = 512 \times$ : indeed $0.0156 \times 512 = 8.0$ . ✔ (This is the promised quadratic takeover.)

Ex 3 — Cell C3: find the crossover length $n^{*}$

Forecast: From Ex 1 ( $n = 32$ : projections win) and Ex 2 ( $n = 16384$ : attention wins), the crossover is somewhere between. Guess an order of magnitude.

Set the terms equal: $h n^{2} d_{k} = 4 n d^{2}$ . Why this step? "Equal cost" is exactly the definition of the crossover; solving it locates $n^{*}$ .
Cancel one $n$ (valid since $n \neq = 0$ ): $h n d_{k} = 4 d^{2} \Rightarrow n^{*} = \frac{4 d ^{2}}{h d _{k}}$ . Why this step? Since $h d_{k} = d$ , this simplifies beautifully to $n^{*} = \frac{4 d ^{2}}{d} = 4 d$ .
Plug numbers: $n^{*} = 4 \times 512 = 2048$ . Why this step? Astonishingly clean: crossover is at $n = 4 d$ , independent of how you slice heads.

The figure below plots both costs against $n$ for this exact model. Follow the teal curve (projections, $4 n d^{2}$ ) — it rises as a gentle straight line because it is linear in $n$ . The burnt-orange curve (attention, $h n^{2} d_{k}$ ) starts far lower on the left but bends upward as a parabola. The plum dot marks where they cross at $n^{*} = 2048$ ; the shaded teal region to its left is the "projections win" zone (Cell C1), and the shaded orange region to its right is the "attention wins" zone (Cell C2). The picture makes concrete why Ex 1 and Ex 2 came out the way they did: they live on opposite sides of that dot.

Figure — Computational complexity of attention

Verify: At $n = 2048$ : attention $= 8 \times 204 8^{2} \times 64 = 2, 147, 483, 648$ ; projection $= 4 \times 2048 \times 51 2^{2} = 2, 147, 483, 648$ . Identical. ✔ And $2048$ sits between $32$ and $16384$ as predicted. This $n^{*} = 4 d$ rule is why 512-dim models feel the quadratic wall around 2K tokens — see 4.3.2-Sparse-attention-patterns.

Ex 4 — Cell C4: the "double the length" scaling law

Forecast: Everyone's first guess is "2×." Is it?

Attention factor: attention $\propto n^{2}$ , so doubling $n$ gives $2^{2} = 4 \times$ . Why this step? Squaring the length is the whole reason the parent note warns about quadratic blow-up.
Compute both totals. At $n = 4096$ : attention $= 8 \times 409 6^{2} \times 64 = 8, 589, 934, 592$ ; projection $= 4 \times 4096 \times 51 2^{2} = 4, 294, 967, 296$ . Total $= 12, 884, 901, 888$ . At $n = 8192$ : attention $= 8 \times 819 2^{2} \times 64 = 34, 359, 738, 368$ ; projection $= 4 \times 8192 \times 51 2^{2} = 8, 589, 934, 592$ . Total $= 42, 949, 672, 960$ . Why this step? The total mixes a $4 \times$ piece with a $2 \times$ piece, so the real factor lands between 2 and 4.
Total factor $= 42, 949, 672, 960/12, 884, 901, 888 \approx 3.33$ . Why this step? We divide new-total by old-total because "growth factor" is by definition the ratio of the two bills; this single number is what you multiply your GPU budget by. It also confirms the intuition from step 2 that the real answer sits strictly between the pure-attention $4 \times$ and the pure-projection $2 \times$ .

Verify: Between 2 and 4, closer to 4 because attention already dominates. ✔ Attention alone: $34, 359, 738, 368/8, 589, 934, 592 = 4.0$ exactly. ✔ Memorable takeaway: near-quadratic regime, doubling length ≈ 3.3× the bill.

Ex 5 — Cell C5: does more heads cost more?

Forecast: "12 heads = 12× work" — true or trap? Commit to an answer.

Attention, $h = 1$ : $h n^{2} d_{k} = 1 \times 102 4^{2} \times 768 = 805, 306, 368$ . Why this step? One head sees the full $d = 768$ dimension.
Attention, $h = 12$ : $12 \times 102 4^{2} \times 64 = 805, 306, 368$ . Why this step? $h d_{k} = 12 \times 64 = 768 = d$ , so the product $h d_{k}$ is unchanged — the heads share the $d$ budget, not multiply it.
Projections (both): $4 n d^{2} = 4 \times 1024 \times 76 8^{2} = 2, 415, 919, 104$ , identical in both cases because Q, K, V, $W_{O}$ act on the full $d$ once. Why this step? This is the exact point the parent's "misconception" callout hammers.

Verify: Attention identical ( $805, 306, 368 = 805, 306, 368$ ) and projections identical. Head count did not multiply either term. ✔ Splitting heads only reshapes the same arithmetic — the core lesson of 4.1.7-Multi-head-attention.

Ex 6 — Cell C6: degenerate & limiting inputs

Forecast: Do the formulas quietly do the sensible thing, or blow up?

(a) $n = 0$ : attention $= h \cdot 0^{2} \cdot d_{k} = 0$ ; projections $= 4 \cdot 0 \cdot d^{2} = 0$ ; memory $= h \cdot 0^{2} = 0$ . Why this step? No tokens ⇒ no work ⇒ zero. The formula degrades gracefully; no division-by-zero anywhere (softmax normalizes over the row, and there are no rows).
(b) $n = 1$ : attention $= 8 \times 1^{2} \times 64 = 512$ ; projections $= 4 \times 1 \times 51 2^{2} = 1, 048, 576$ ; score matrix is $1 \times 1$ . Why this step? A single token attends only to itself — one score, softmax of one number $= 1$ . Projections still cost a full $n d^{2}$ per matrix because you still transform that one vector. Projections dominate absolutely here ( $n = 1 ≪ d$ ), matching Cell C1's logic taken to the limit.
(c) $d_{k} = 0$ : attention $= h n^{2} \cdot 0 = 0$ and $d = h d_{k} = 0$ ⇒ projections $= 4 n \cdot 0^{2} = 0$ . Why this step? A zero-width head carries no information and costs nothing — the degenerate "no model" case. Useful as an algebraic sanity anchor, not a real config.

Verify: All three give finite, non-negative, sensible values; the only "special" one, $n = 1$ , yields projections $1, 048, 576 ≫$ attention $512$ . ✔ No formula divides by $n$ or $d_{k}$ , so no singularities.

Ex 7 — Cell C7: real-world GPU memory word problem

Forecast: The parent quoted "~2.3 GB." Guess whether you'll reproduce it.

Floats in one head's score matrix $= n^{2} = 204 8^{2} = 4, 194, 304$ . Why this step? Every query–key pair produces one score; that's an $n \times n$ grid — the memory analogue of the $n^{2}$ compute term. (This is exactly what 4.5.1-Memory-optimization-techniques tries to shrink.)
Total floats $= n^{2} \times h \times L = 4, 194, 304 \times 12 \times 12 = 603, 979, 776$ . Why this step? Each of the 12 heads in each of the $L = 12$ layers keeps its own score grid during the forward pass.
Bytes (FP32) $= 603, 979, 776 \times 4 = 2, 415, 919, 104$ bytes $= 2, 415, 919, 104/102 4^{3} \approx 2.25$ GB. Why this step? Convert floats → bytes (×4), then bytes → GiB (÷ $102 4^{3}$ ). Units: floats × (bytes/float) = bytes. ✔
FP16: halve the bytes/float → $\approx 1.13$ GB. Why this step? Precision only changes the bytes-per-float constant, not the $n^{2} h L$ count.

Verify: $2.25$ GB matches the parent's "~2.3 GB." ✔ FP16 gives exactly half: $2.25/2 = 1.13$ . ✔ This memory (not the parameters!) is why long-context training needs checkpointing — the second [!mistake] in the parent.

Ex 8 — Cell C8: the exam trap

Forecast: Does the head count $h$ belong in the projection term? (You solved this idea in Ex 5.)

Spot the error: the extra factor $h$ is wrong. Projections Q, K, V, $W_{O}$ operate once over the full $d$ -dimensional space; heads are a reshape of that same output, not $h$ separate full-width projections. Why this step? This is the exact " $\times h$ trap" the parent's misconception callout warns about.
Wrong value (what the claim gives): $12 \times 4 \times 1024 \times 76 8^{2} = 28, 991, 029, 248 \approx 29.0$ B. Why this step? We compute the wrong number explicitly so we can measure exactly how far off the trap lands — it arises from wrongly multiplying the correct $4 n d^{2}$ projection cost by the head count $h = 12$ . Naming the actual figure (29.0B) turns a vague "that's too big" into a precise "that's $12 \times$ too big," which is what a grader must justify.
Correct value: $4 n d^{2} = 4 \times 1024 \times 76 8^{2} = 2, 415, 919, 104 \approx 2.42$ B. Why this step? Drop the spurious $h$ ; the true projection cost is $12 \times$ smaller.

Verify: The claim over-counts by exactly $h = 12$ : $28, 991, 029, 248/2, 415, 919, 104 = 12.0$ . ✔ Correct answer $\approx 2.42$ B (agrees with Ex 5). The tempting-but-wrong version is $\approx 29.0$ B.

Pulling the cases together

Recall Self-test (reveal after answering)

The crossover length in terms of $d$ ::: $n^{*} = 4 d$ (independent of head count). Doubling $n$ in the attention-dominated regime multiplies attention FLOPs by ::: $4$ (since attention $\propto n^{2}$ , and $2^{2} = 4$ ). Does using 12 heads instead of 1 multiply the projection cost by 12? ::: No — projections act once over the full $d$ ; heads only reshape it. Memory for score matrices scales as ::: $h n^{2}$ floats per layer (quadratic in $n$ ). FP32 → FP16 changes the memory bill by a factor of ::: $\frac{1}{2}$ (bytes-per-float only).