Core ML

Attention Complexity

Every query scores against every key, so both the compute and the memory attention needs grow with the square of sequence length, not with the length itself.

Doubling the sequence length quadruples the attention score grid, because every one of n queries scores against every one of n keys — cost grows with the square of length, not the length itself

Why Does This Exist?

Self-attention is the mechanism that let every token in a sequence look directly at every other token, in one step, regardless of distance. That directness is exactly what makes it powerful, and exactly what makes it expensive: "every token looks at every other token" is a description of quadratic cost, stated in plain English before any formula gets involved.

This page exists because that cost isn't a minor implementation detail — it's the single constraint that every long-context technique in the transformer band is a response to. Sliding-window attention, sparse attention, linear attention, FlashAttention, state space models: none of them exist in a vacuum. They all exist because the number on this page grows the way it grows, and at some sequence length that growth becomes the thing standing between a model and a task.

Think of It Like This

A conference call where everyone talks to everyone

Ten people on a conference call, and imagine each person needs a private one-on-one exchange with every other person before the call can proceed. That's 45 pairs. Double the group to twenty people and it's not 90 pairs — it's 190. The pairs grow roughly with the square of the headcount, because every new person has to exchange with everyone already there, and everyone already there has to exchange with the new person too.

Self-attention runs exactly that all-pairs exchange, once per layer, for every token in the sequence. A sequence twice as long isn't twice the attention cost — it's four times the cost, for the same reason doubling the call's headcount roughly quadruples the pairs.

How It Actually Works

Where the n² comes from

Recall the attention formula: $\text{softmax}(QK^\top / \sqrt{d_k}) \, V$ . For a sequence of length $n$ with hidden dimension $d$ , computing $QK^\top$ multiplies an $n \times d$ matrix by a $d \times n$ matrix, producing an $n \times n$ score matrix — that's $O(n^2 d)$ multiply-add operations, and it comes directly from the shape of matrix multiplication covered in matrix multiplication: every one of $n$ rows pairs with every one of $n$ columns.

Compute scales as $O(n^2 d)$ — the score matrix computation, plus the subsequent $\text{weights} \times V$ multiply, which is another $O(n^2 d)$ .

Memory scales as $O(n^2)$ — the full $n \times n$ score matrix has to exist somewhere (at least transiently) to run the softmax over it, and that grid, not just the compute to fill it, is the thing that hits a hardware ceiling first in practice. The diagram above makes this concrete: doubling $n$ from the small grid to the large one doesn't double the grid's area, it quadruples it.

Where this actually bites

At $n = 512$ , the score matrix has about 260,000 entries per head — trivial. At $n = 128{,}000$ (a long-context model's advertised window), it has over 16 billion entries per head, and that's before multiplying by the number of heads or layers. This is precisely why "context length" became a marketed number worth optimizing rather than an afterthought: every doubling of context multiplies the attention cost by four, so context length and inference cost are not linearly related, and treating them as if they were badly underestimates what a longer window will cost.

Inference has a second cost: the KV cache

Generating text autoregressively adds a separate memory cost beyond the $O(n^2)$ compute above: at each new token, the model needs the keys and values from every previous token to attend over, so a growing KV cache has to be stored across the whole generation, growing linearly with sequence length per layer and head. This cache is frequently the actual memory bottleneck in production serving — not the attention computation itself, but the running tally of keys and values every generated token has to be checked against.

Show Me the Code

Measuring the score-matrix size directly as sequence length grows, rather than asserting the scaling law.

1import numpy as np2
3
4def attention_score_bytes(n: int, n_heads: int, dtype_bytes: int = 4) -> int:5    """Size in bytes of the raw n x n score matrix, across all heads, one layer."""6    return n * n * n_heads * dtype_bytes7
8
9for n in (512, 1_024, 2_048, 4_096):10    mb = attention_score_bytes(n, n_heads=32) / (1024 ** 2)11    print(f"n={n:>5} -> {mb:>8.1f} MB of scores, one layer")12# -> n=  512 ->      32.0 MB of scores, one layer13# -> n= 1024 ->     128.0 MB of scores, one layer14# -> n= 2048 ->     512.0 MB of scores, one layer15# -> n= 4096 ->    2048.0 MB of scores, one layer

Every doubling of n quadruples the megabyte figure exactly — 32 to 128 is 4×, 128 to 512 is 4×, and so on. That's $O(n^2)$ made visible in a number you can watch grow, per layer, before even counting the model's other layers.

Watch Out For

Budgeting context length linearly

Doubling a model's advertised context window from 32K to 64K tokens does not double the attention cost of a full-context request — it roughly quadruples it. Teams that plan compute or latency budgets by scaling linearly with context length routinely underestimate cost and get surprised at the largest context sizes their product actually supports. Budget attention cost quadratically, and budget the KV cache linearly — the two costs scale differently and both matter.

Assuming quadratic cost is unavoidable

Because $O(n^2)$ falls directly out of the "every token attends to every other token" formula, it's tempting to treat it as an immovable law of attention itself. It isn't — it's a property of exact, dense self-attention specifically. Sliding-window attention, sparse attention patterns, linear-attention approximations, and state space models all exist precisely because this cost is a design choice within "exact dense attention," not a law nature imposes on all sequence models. Treating O(n²) as unavoidable is exactly the assumption every one of those techniques is built to challenge.

The Quick Version

Self-attention scores every query against every key, which is an all-pairs computation by construction.
Compute scales as $O(n^2 d)$ ; memory for the score matrix alone scales as $O(n^2)$ .
Doubling sequence length roughly quadruples attention cost — context length and cost are not linearly related.
Autoregressive inference adds a separate, linearly growing KV-cache cost on top of the quadratic attention cost.
Quadratic cost is a property of exact dense attention specifically, not an unavoidable law — which is exactly what motivates every efficient-attention variant.