Foundations — Computational complexity of attention

Before you can read the parent note Computational complexity of attention, you need to own every symbol it throws at you. We build them one at a time. Nothing is used before it is drawn.

1. What is a "token"? — the letter $n$

A token is one small chunk of text the model reads: usually a word or piece of a word. If you feed the model the sentence "cats love naps", that is 3 tokens.

Look at the figure: each coloured box is one token. Lining them up in a row is literally what "a sequence of length $n$" means. Everything expensive in attention grows as this row gets longer.

2. What is an "embedding"? — the letter $d$

A computer cannot multiply the word "cats". So each token is turned into a list of numbers — like coordinates that place the word somewhere in a space of meaning. Similar words land near each other.

Look at the figure: each token box now has a column of $d$ numbers stacked under it. A vector is just that column — a list of numbers with a fixed length. We write "a vector lives in ${\mathbb{R}}^d$", which is fancy for "it is a list of $d$ real (ordinary) numbers".

3. Stacking vectors into a grid — the matrix $X$

If we take all $n$ token-vectors and stand them side by side, we get a rectangle of numbers: $n$ rows (one per token) and $d$ columns (one per feature).

So the input to attention is one matrix $X$ of shape $n\times d$. Row $i$ of $X$ is the vector for token $i$.

4. What "multiplying two matrices" costs — the heart of complexity

This is the single most important mechanic in the whole topic, so we slow right down.

To multiply a matrix of shape $(a\times b)$ by a matrix of shape $(b\times c)$:

• The inner numbers must match (both are $b$). They "cancel", and the result has shape $(a\times c)$.
• Each cell of the result is made by lining up one row (length $b$) with one column (length $b$), multiplying the pairs, and adding them up — that is $b$ multiplications per cell.
• There are $a\times c$ cells.

Look at the figure: one highlighted result cell is fed by one row (violet) and one column (orange), each of length $b$. Count the arrows — that's $b$ multiplications for one cell. Repeat for all $a\cdot c$ cells and you have the total.

5. The three players — $Q$, $K$, $V$

Each token asks a question, offers a label, and carries content. So each token-vector is turned into three new vectors:

Here $d_k$ is the width of one query/key/value vector — often equal to $d$, or to $d/h$ when we split into heads (Section 8). Full mechanics live in 4.1.1-Self-attention-mechanism.

6. Comparing every pair — the transpose $K^T$ and $S=Q{K}^T$

To score how well token $i$'s query matches token $j$'s key, we multiply the query row by the key row. Doing this for all pairs at once needs the keys turned on their side — that is the transpose.

Now the score matrix: $S=Q{K}^T,(n\times d_k)\times (d_k\times n)=(n\times n).$

Using the cost formula with $a=n,b=d_k,c=n$: $\text{cost}=n\cdot d_k\cdot n=n^2{d}_k.$

Look at the figure: the output $S$ is a full square of side $n$. Cell $(i,j)$ is the score "how much should token $i$ attend to token $j$". A square of side $n$ has $n^2$ cells — this is the birthplace of the quadratic cost the whole topic warns about.

7. Softmax, $\sqrt{d_k}$, and the aggregation $AV$

The scores are first divided by $\sqrt{d_k}$ (square root of the key width). Why? Bigger vectors give bigger dot-product scores just because there are more terms to add; dividing by $\sqrt{d_k}$ shrinks them back so softmax does not become razor-sharp. It answers the question "how do I keep scores at a sane scale regardless of $d_k$?"

Finally each token's output is a weighted blend of all value vectors: $\text{Output}=AV,(n\times n)\times (n\times d_k)=(n\times d_k),\text{cost}=n^2{d}_k.$

8. Reading the growth rate — big-$\mathcal{O}$ and $h$ heads

Look at the figure: the orange linear line ($\propto n$) and the magenta quadratic curve ($\propto n^2$) start close, but the quadratic soon rockets away. That crossover is exactly why long sequences hurt, and why 4.3.2-Sparse-attention-patterns and 4.5.1-Memory-optimization-techniques exist. Position information itself must also scale with $n$ — see 5.2.3-Positional-encoding-scaling.

Prerequisite map

Equipment checklist

Cover the right side and answer out loud. If any stalls, reread that section.