Computational complexity of attention: Question bank

Before you start, here is the vocabulary reminder that makes every answer readable.

Definition The symbols you need

$n$ = sequence length (how many tokens are in the input).
$d$ = model dimension (the length of each token's embedding vector).
$b$ = batch size (how many independent sequences we process at once). Every cost below scales linearly with $b$ , so the true time is $O (b n^{2} d + b n d^{2})$ and memory is $O (b n^{2} + b n d)$ . We often drop $b$ to compare shapes, but in practice it multiplies your whole GPU bill.
$h$ = number of attention heads; each head works in dimension $d_{k} = d / h$ .
$Q, K, V$ = the query, key, value matrices. Each is the input reshaped by a learned weight matrix: $Q$ asks "what am I looking for?", $K$ advertises "what do I offer?", $V$ carries "the actual content to pass along". All three are $n \times d_{k}$ per head.
$W_{O}$ = the output projection weight matrix ( $d \times d$ ); after the heads are concatenated back into a $d$ -vector, $W_{O}$ mixes them and maps back to model dimension.
$softmax$ = the operation that turns a row of raw scores into positive weights that sum to 1, so each token's attention is a proper weighted average. It is applied per row of the $n \times n$ score matrix.
$O (\cdot)$ = "grows no faster than", ignoring constant factors — it tells you the shape of the growth, not the exact FLOP count. A "FLOP" is one floating-point multiply-or-add. When we say $n^{2} d$ we mean roughly that many multiply-adds (per sequence in the batch).

Read the two figures first — every answer below points back at them.

Figure 1 is the growth-curve picture. The horizontal axis is the sequence length $n$ ; the vertical axis is the number of operations (in millions) for a fixed $d = 512$ . The black line is the projection cost $n d^{2}$ (a straight line — linear in $n$ ). The red line is the attention cost $n^{2} d$ (a parabola — quadratic in $n$ ). Follow the red parabola upward and notice it stays below the black line for small $n$ , then crosses it at the dashed vertical mark where $n = d$ , and shoots above it afterwards. That single crossing point is the whole story of "which term dominates": left of it, projections rule; right of it, attention rules.

Figure — Computational complexity of attention

Figure 2 is the score-matrix picture. Each little square is one entry $S_{ij}$ = the score between query token $i$ (row) and key token $j$ (column). A filled square is a score we actually compute and store. On the left ("full attention") the entire $n \times n$ grid is filled black — every token pair exists, which is why the cost is quadratic. On the right ("causal attention") only the red lower triangle is filled — token $i$ may only look at itself and earlier tokens, so roughly half the grid ( $n^{2} /2$ ) is computed. Compare the two grids side by side: masking removes a constant fraction, but the grid is still $n \times n$ in shape, so the asymptotic $n^{2}$ cost is unchanged.

True or false — justify

Multi-head attention is asymptotically

h

times more expensive than single-head attention.

False. The

h

heads split the dimension (

d_{k} = d / h

), so

h

heads each costing

n^{2} d_{k}

sum to

h \cdot n^{2} (d / h) = n^{2} d

— identical to one full-dimension head (the red parabola in Figure 1 does not move when you change

h

The linear projection cost gets multiplied by the number of heads

h

False. Q, K, V and

W_{O}

each act once on the full

d

-dimensional space; splitting into heads is just a reshape, so the projection term stays

O (n d^{2})

(the black line in Figure 1), never

O (h n d^{2})

Doubling the sequence length doubles the total compute.

False in general. The dominant

n^{2} d

term quadruples when you double

n

(walk twice as far right on the red parabola in Figure 1); only the

n d^{2}

projection term doubles. For long sequences the quadratic term wins, so cost roughly quadruples.

For very short sequences (

n ≪ d

), the linear-projection term dominates, not attention.

True. When

n

is small you are left of the crossover in Figure 1, where the black

n d^{2}

line sits above the red

n^{2} d

curve, so most work is in the Q/K/V/output projections, not the score matrix.

Doubling the batch size

b

leaves the total cost unchanged.

False. Every sequence in the batch runs the full pipeline independently, so both time and memory scale linearly with

b

: the true cost is

O (b n^{2} d + b n d^{2})

. Batching improves hardware utilization, not the per-sequence cost.

The

O (n^{2})

memory cost disappears at inference time.

Only under specific conditions. With batch size 1 and streaming/flash-style kernels that never materialize the full matrix, peak working memory can fall toward

O (n d)

; but any framework that caches the whole score matrix, or a batch of size

b

, still holds

O (b n^{2})

, and training always must store it for backprop.

Self-attention connects any two tokens in a single step, unlike an RNN.

True. Attention has a depth-1 path between every pair of tokens — that is why the full

n \times n

grid in Figure 2 exists — whereas an RNN needs up to

n

sequential steps to relay information across the sequence.

Sparse attention reduces the asymptotic time below

O (n^{2} d)

True. Patterns like

O (n n d)

fill only a structured subset of the Figure 2 grid, trading global exactness for sub-quadratic cost — see 4.3.2-Sparse-attention-patterns.

A learned relative-position bias table is "free" because it is just an addition to the scores.

False. A relative/pairwise positional bias adds one bias term to every one of the

n \times n

scores, an extra

O (n^{2})

compute and, for learned bias tables, extra memory of the same shape — it rides on top of the same quadratic bottleneck rather than removing it. See 5.2.3-Positional-encoding-scaling.

Linear attention removes the quadratic term entirely and is exact.

Half-true — sub-quadratic, but not exact. Full attention computes

(Q K^{T}) V

: forming

Q K^{T}

first costs

n^{2}

. Linear attention replaces softmax with a kernel feature map so the products can be reassociated as

Q (K^{T} V)

; now

K^{T} V

is a small

d_{k} \times d_{k}

matrix built in

O (n d^{2})

, dodging the

n \times n

step. But softmax is non-linear and cannot be factored this way, so the kernel is an approximation of it — same shape of output, different function.

Spot the error

"Attention FLOPs are

h \cdot n^{2} \cdot d

, because we do

n^{2} d

work per head across

h

heads."

Error: double counting $d$ . Each head does

n^{2} d_{k}

work, and

d_{k} = d / h

. The

h

heads together give

n^{2} d

, not

h n^{2} d

. The head factor cancels the split dimension.

"The output projection

W_{O}

is free, so total projection cost is

3 n d^{2}

Error: $W_{O}$ is not free. Q, K, V and the output projection each cost

n d^{2}

, giving

\approx 4 n d^{2}

. Forgetting

W_{O}

undercounts the linear term by a quarter.

"Memory is

O (n^{2} d)

because we store the score matrix and it depends on

d

Error: the stored matrix is $n \times n$ , not $n \times n \times d$ . Scores are a single number per token pair (one square per cell in Figure 2), so memory is

O (n^{2})

per sequence — total

O (b n^{2})

with a batch — plus

O (b n d)

for the Q/K/V/output activations.

"Since

d_{k} \approx d

, we can just write total time as

O (n^{2} d)

and drop

n d^{2}

Error: dropping $n d^{2}$ is wrong when $n < d$ . Left of the crossover in Figure 1 the

n d^{2}

term dominates, so both terms must be kept:

O (n^{2} d + n d^{2})

"An RNN uses less memory (

O (d)

) and less time, so it is strictly better for long sequences."

Error: better on memory, not on usable long-range connection. RNNs need

n

sequential steps and suffer vanishing gradients over long distances — attention's cost buys instant global reach, which the RNN cannot match.

"The softmax step is the quadratic bottleneck."

Error: softmax is $O (n^{2})$ but cheap per element. The quadratic shape comes from building the

n \times n

score matrix

Q K^{T}

(the

O (n^{2} d)

step); softmax merely normalizes those already-computed scores.

"Adding a relative-position bias makes attention asymptotically slower."

Error: it is the same order. The bias adds

O (n^{2})

additions on top of the

O (n^{2} d)

score computation, so it inflates the constant factor and memory but does not change the

O (n^{2} d)

growth shape.

Why questions

Why is the score matrix

S = Q K^{T}

inherently quadratic in

n

Because every token's query must be compared against every token's key to decide who to attend to, producing all

n \times n

pairwise scores (the full grid in Figure 2) — there is no way to get a full attention weight without the pair existing.

Why does using more heads not change asymptotic complexity?

More heads reshape the same

d

-dimensional space into

h

blocks of size

d / h

; the total arithmetic is conserved because the per-head savings (

d_{k} < d

) exactly offset the head count. See 4.1.7-Multi-head-attention.

Why can Q, K, V be split across heads but

W_{O}

is still applied once over the full

d

Because Q/K/V are inputs to

h

independent attention computations, so they are literally sliced into

h

blocks of width

d / h

that each head consumes separately.

W_{O}

acts after the heads are concatenated back into one

d

-vector — there is only one full-width vector left to mix, so there is nothing to slice and it costs

n d^{2}

exactly once.

Why does attention overtake linear projections only at large

n

Projections grow like

n d^{2}

(linear in

n

, the black line in Figure 1) while attention grows like

n^{2} d

(quadratic, the red curve); the ratio is

\frac{n ^{2} d}{n d ^{2}} = n / d

, so attention wins once

n > d

— exactly the crossover marked in the figure.

Why does the batch factor

b

multiply cost but never appear in

O (n^{2} d)

shorthand?

Each of the

b

sequences runs the identical pipeline, so

b

is a clean linear multiplier on both compute and memory (

O (b n^{2} d + b n d^{2})

); we drop it when comparing the shape of two architectures because it multiplies them equally, but you must restore it when sizing a real GPU.

Why does reassociating

(Q K^{T}) V

into

Q (K^{T} V)

make linear attention cheap?

Matrix multiplication is associative, so the result is unchanged, but

K^{T} V

collapses the

n

axis first into a tiny

d_{k} \times d_{k}

summary — you never build the

n \times n

grid of Figure 2, turning

n^{2} d

into

n d^{2}

. This only works once softmax is dropped, because softmax sits between

Q K^{T}

and

V

and blocks the reordering.

Why can streaming (row-by-row) attention cut peak memory from

O (n^{2})

O (n d)

at inference?

Process the score matrix of Figure 2 one query row at a time: for query

i

compute its

n

scores against all keys, softmax that single row, immediately multiply by

V

to get that token's output, then discard the row before starting row

i + 1

. You only ever hold one length-

n

row plus the length-

d

running output, so working memory is

O (n + d) = O (n d)

overall, never the full

n \times n

grid — this is the core idea behind flash/streaming attention.

Why is gradient checkpointing important for long-context training?

The

n \times n

activation matrices across all layers dominate memory; checkpointing recomputes them in the backward pass instead of storing them, trading extra compute for much lower peak memory. See 4.5.1-Memory-optimization-techniques.

Why does the

d_{k}

scaling inside softmax not affect the complexity?

It is a single scalar division applied per score — an

O (n^{2})

operation with tiny constant — so it changes numerical stability, not the asymptotic cost.

Why can't we naively feed an entire novel into a standard transformer?

A novel is tens of thousands of tokens; the Figure 2 grid becomes enormous (e.g.

50 k^{2} = 2.5

billion entries per head per layer), exploding

n^{2}

memory and compute past hardware limits — hence efficient-attention research exists.

Edge cases

What happens to the cost ratio

n / d

when

n = d

exactly?

Attention and projection terms are asymptotically balanced (

n^{2} d = n d^{2}

when

n = d

) — this is precisely the crossover mark in Figure 1; neither dominates, and constant factors (the

4

4 n d^{2}

) decide which is larger in practice.

What is the complexity when

n = 1

(a single token)?

Attention degenerates: the score grid of Figure 2 is a single

1 \times 1

square, softmax is trivial (weight

= 1

), and cost collapses to the projections

O (d^{2})

— the quadratic term vanishes.

How does causal (masked) attention change the count?

In autoregressive models each token attends only to itself and earlier tokens — the red lower triangle in Figure 2, about

n^{2} /2

scores. The constant halves but the asymptotic cost stays

O (n^{2} d)

; masking saves a factor of 2, not an order.

What if all keys are identical, so every score is equal?

The softmax outputs a uniform distribution and the output becomes the plain average of value vectors; complexity is unchanged — cost depends on shapes, not on the values inside the matrices.

How does adding a relative-position bias change the picture?

It adds an

O (n^{2})

bias term (and, for a learned table,

O (n^{2})

extra memory) on top of the score matrix — the same quadratic shape, a larger constant. See 5.2.3-Positional-encoding-scaling.

In the limit

n \to \infty

with

d

fixed, which term governs everything?

The

n^{2} d

attention term (the red parabola in Figure 1), since it grows without bound faster than the linear

n d^{2}

term; asymptotically the projection cost becomes a rounding error.

What happens to memory if you compute attention but never store scores for backprop (inference only)?

You can process row-by-row and discard each row's scores after use (see the streaming Why-question), so peak working memory can drop toward

O (n d)

per sequence.

h = d

(one dimension per head,

d_{k} = 1

), does the model get cheaper?

No — attention is still

h n^{2} d_{k} = d \cdot n^{2} \cdot 1 = n^{2} d

, unchanged; you have simply fragmented the representation as far as it can go without altering asymptotic cost.

Recall One-line summary to lock in

The true total is $O (b n^{2} d + b n d^{2})$ : the first term is the unavoidable all-pairs score grid, the second is the four full-width projections — $b$ multiplies everything, and neither term ever carries a factor of $h$ .