Self-Attention Complexity

What You’ll Learn

You’ll learn why self-attention costs $O(n^2 d)$ time and $O(n^2)$ space by following the matrix shapes. You’ll also see which operation creates the bottleneck and why quadratic cost is the central engineering constraint for long-context transformers.

Three Operations, One Bottleneck

Self-attention boils down to three matrix operations. The complexity question is really: what shapes are these matrices, and how expensive is each multiplication?

Step through the visualization below. Watch the matrix shapes at each step, especially the $n \times n$ result in step 1.

Self-Attention: Three Operations

Step 1: Q × Kᵀ

Time: O(n²d) Space: O(n²)

Each of the n×n entries requires a d-length dot product. 4×4 = 16 entries, each costing 3 multiplications. The n×n matrix is the quadratic bottleneck.

What to look for: Steps 1 and 3 both produce $O(n^2 d)$ work (the two large matrix multiplications). Step 2 (softmax) is $O(n^2)$ , which is $d$ times cheaper. The $n \times n$ attention matrix is the bottleneck in both time and space.

(Forgot how Q, K, V work? Review Self-Attention)

Counting Operations

Why $O(n^2 d)$ ? Think about what happens when you multiply Q ( $n \times d$ ) by $K^\top$ ( $d \times n$ ).

The result is an $n \times n$ matrix. Each entry is a dot product of two $d$ -dimensional vectors: $d$ multiplications, $d - 1$ additions. So each entry costs $O(d)$ work, and there are $n \times n$ entries:

$n \times n \times d = n^2 d$

Softmax operates on each of the $n$ rows independently: exponentiate $n$ values, sum, divide. That’s $O(n)$ per row, $n$ rows: $O(n^2)$ . Compared to $n^2 d$ , this is negligible (since $d$ is typically 64 to 128).

The final multiplication (weights $\times$ $V$ ) is an $n \times n$ matrix times an $n \times d$ matrix, costing $n \times d \times n = n^2 d$ again.

With $Q, K \in \mathbb{R}^{n \times d}$ and $V \in \mathbb{R}^{n \times d}$ :

Step 1: $QK^\top \in \mathbb{R}^{n \times n}$

$\text{Time: } O(n \cdot n \cdot d) = O(n^2 d)$

Step 2: $\text{softmax}(QK^\top)$ (row-wise, in-place)

$\text{Time: } O(n \cdot n) = O(n^2)$

Step 3: $\text{softmax}(QK^\top) \cdot V \in \mathbb{R}^{n \times d}$

$\text{Time: } O(n \cdot d \cdot n) = O(n^2 d)$

Total: $O(n^2 d) + O(n^2) + O(n^2 d) = O(n^2 d)$

For space: the attention score matrix $QK^\top$ is $n \times n$ , so $O(n^2)$ . The inputs $Q, K, V$ are each $n \times d$ , totaling $O(nd)$ . Total space: $O(n^2 + nd)$ .

Quick Check

Which operation in self-attention is the cheapest?

Your turn

Choose an answer to check your understanding.

Attempts: 0

Feeling the Quadratic Growth

Numbers make this concrete. Click through different sequence lengths below and watch how the operation counts grow. Toggle between time and space to see what dominates.

How Cost Scales with Sequence Length

Sequence length (n):

d = 128

QK^T n²d

33.6M

softmax n²

262.1K

× V n²d

33.6M

Total: 67.4M operations

Softmax (262.1K) is 128x smaller than the matrix multiplications. It's negligible.

What to look for: Double the sequence length, and the cost roughly quadruples. At 4K tokens, $QK^\top$ alone requires over 2 billion operations. The softmax bar is barely visible next to the matrix multiplications. Toggle to “Space” and notice how the $n \times n$ score matrix dominates once $n > d$ .

Why This Is a Problem

A 1,000-token input produces a 1,000 $\times$ 1,000 attention matrix: 1 million entries. A 10,000-token input produces 100 million entries. A 100,000-token input produces 10 billion entries.

This quadratic scaling is why:

GPT-2 had a 1,024-token context window
Processing a full book (500K tokens) would require a 250-billion-entry attention matrix per layer
Researchers developed Flash Attention (reduces memory from $O(n^2)$ to $O(n)$ by never materializing the full matrix)
Architectures like Mamba use state-space models for $O(n)$ time and space
Linear attention replaces softmax with kernels to avoid the $n \times n$ matrix entirely

Fill in the Blanks

Self-attention has time complexity O( ) and space complexity O( ). The bottleneck is the attention matrix.

Fill in every blank, then check your answer.

Quick Summary

Step	Time	Space	Intuition
$QK^\top$	$O(n^2d)$	$O(n^2)$	Every query scores against every key
softmax	$O(n^2)$	$O(n^2)$	Normalize each row (cheap)
$\times V$	$O(n^2d)$	$O(nd)$	Blend values by attention weights
Total	$O(n^2d)$	$O(n^2 + nd)$	Quadratic in sequence length

Multi-Head Attention Complexity

With $h$ attention heads, each head uses dimension $d_k = d/h$ . The cost per head is $O(n^2 \cdot d/h)$ , and with $h$ heads the total stays $O(n^2 d)$ . Multi-head attention doesn’t change the asymptotic complexity. It just reorganizes how the $d$ dimensions are used.

Including the Linear Projections

The full self-attention layer also includes the $W_Q$ , $W_K$ , $W_V$ , and $W_O$ projection matrices, each $d \times d$ . Projecting all $n$ tokens through one of these costs $O(nd^2)$ . With four projections:

$\text{Projection cost} = O(nd^2)$

So the complete self-attention layer is $O(n^2 d + nd^2)$ . For short sequences ( $n < d$ ), the projection cost dominates. For long sequences ( $n > d$ ), the attention matrix dominates.

Feed-Forward Network Complexity

For comparison, the FFN layer (with hidden size $4d$ ) costs $O(nd^2)$ in time but only $O(nd)$ in space (the largest intermediate is the $n \times 4d$ hidden activation). The FFN is sequence-length-linear, so it’s never the bottleneck for long sequences.

Learning Checklist

I can break self-attention into three operations and state the cost of each
I know which operation is cheapest (softmax) and why
I can explain why doubling sequence length roughly quadruples the cost
I understand that the $n \times n$ matrix is both the time and space bottleneck
I’m aware of approaches that avoid this quadratic cost (Flash Attention, linear attention, SSMs)

Now that you see why the $n \times n$ matrix is the bottleneck, learn how Linear Attention avoids it entirely by reordering the computation, or how the KV Cache eliminates redundant work during generation.