The O(n^2) cost of self-attention originates from computing the QK^T score matrix over every pair of tokens, and this quadratic scaling is precisely why memory-efficient kernels and alternative attention architectures exist as separate mitigation work.

True. True: forming $QK^T$ produces an $n\times n$ matrix — one score per token pair — which is the mechanical source of the $O(n^2)$ time and memory cost. Because this cost becomes a practical bottleneck at long sequence lengths, it motivates separate techniques (kernel-level and architectural) that reduce or avoid materializing that full matrix — without those techniques being part of the complexity derivation itself.

Attention mechanism computational complexity Interview Q&A

Deriving Attention’s n² Cost

1
Form Q, K, VEach of the n tokens is projected into a query, key, and value vector, giving matrices $Q, K, V \in \mathbb{R}^{n \times d}$ .
2
Compute $QK^T$ Multiplying $Q$ by $K^T$ produces an $n \times n$ matrix of scores — one entry per token pair. This single matmul already has $n^2$ entries.
3
Softmax each rowSoftmax normalizes every row of that $n \times n$ matrix into attention weights, touching all $n^2$ entries again.
4
Weight and sum VThe $n \times n$ weights multiply $V$ to mix values per token. The $n^2$ term fixed in step 2 propagates through every later stage.

Setup

Suppose a sequence has n = 4 tokens. How many pairwise attention scores must be computed, and what happens if n doubles to 8?

1
Count pairs for n=4: each of 4 tokens scores against all 4 tokens, giving $4 \times 4 = 16$ scores.
WhyThe $QK^T$ matrix has one entry per ordered token pair, so the total score count is $n^2$ .
2
Count pairs for n=8: $8 \times 8 = 64$ scores.
WhyDoubling n doubles both matrix dimensions, so the entry count scales by $2 \times 2 = 4$ .
3
Compare growth: $64 / 16 = 4$ , not 2.
WhyBecause cost is $O(n^2)$ , doubling sequence length quadruples pairwise computation, not merely doubling it.

Takeaway

Whenever n doubles, the number of pairwise scores — and thus attention’s compute — grows by a factor of 4, not 2, because the cost scales quadratically in n.

Setup

A model processes n = 100,000 tokens (roughly a full book) with vanilla self-attention.

Expected

You might expect memory to scale linearly with n, since each token’s representation is a fixed-size vector.

What breaks

But softmax and the later weighted sum require the full

n \times n

score matrix to be materialized, so memory scales as

O(n^2)

. At n=100,000 that matrix has 10 billion entries — far beyond typical GPU memory.

Lesson

Time and memory both blow up quadratically because the same

n \times n

matrix that costs

O(n^2)

time to compute must also be held fully in memory, not just streamed through.

Because vanilla self-attention costs $O(n^2)$ in both time and memory, doubling sequence length quadruples the resource demand — growth far faster than the input itself. Past some sequence length, this quadratic wall becomes the binding constraint on model scale. That is exactly why separate lines of work exist: memory-efficient kernels that avoid fully materializing the score matrix, and architectural variants that change the underlying $n^2$ pattern. Those are answers to this bottleneck, not part of deriving it.

Attention mechanism computational complexity

Deriving Attention’s n² Cost

Sources

A focused session on your AI Research Scientist interview

More Attention Mechanisms & Kernels questions