# Self-attention

> Every token of a sequence is projected into a query, a key and a value, and each output is a softmax-weighted average of all the values, with weights from query–key dot products. Any token can reach any other in one step, the layer is permutation-equivariant, and it costs O(n²) in sequence length.

Source: https://www.mlfoundry.in/learn/self-attention  
Section: Deep Learning › Attention and Transformer Architectures  
Level: core · 14 min read · updated 2026-10-12

**Self-attention:** (also **intra-attention**) is attention in which the queries, keys and values all come from **the same sequence**. Given token representations $X\in\mathbb R^{n\times d_{\text{model}}}$, a self-attention layer forms $Q=XW_Q$, $K=XW_K$, $V=XW_V$ and returns $Y=\mathrm{softmax}(QK^\top/\sqrt{d_k})\,V$. Row $i$ of $Y$ is a mixture of the values of all $n$ tokens, weighted by how well the query of token $i$ matches each token's key. It is the core layer of every Transformer.

In the RNN translation models of 2014–2015 (see **Attention mechanism**), attention connected two different sequences: decoder states queried encoder states. A recurrent network still built the representation of each sentence, one token after another. The idea of letting a sequence attend to itself appeared in 2016. Cheng, Dong and Lapata ("Long Short-Term Memory-Networks for Machine Reading", EMNLP 2016) added intra-attention over an LSTM's own past states. Parikh et al. (EMNLP 2016) used intra-sentence attention in a decomposable model for natural language inference, and Lin et al. (ICLR 2017) built sentence embeddings from self-attention over BiLSTM states.

Vaswani et al., "Attention Is All You Need" (NeurIPS 2017), removed the recurrence entirely. Their Transformer builds every representation from stacked self-attention and position-wise feed-forward layers, with **Positional encoding** added to the inputs. On WMT 2014 English→German the big model reached 28.4 BLEU, more than 2 BLEU above the best previous results including ensembles, after 3.5 days of training on 8 P100 GPUs. The argument of the paper was less about accuracy than about structure: self-attention connects every pair of positions with a constant number of operations, and all positions are computed in parallel.

## The layer

$$
Q=XW_Q,\quad K=XW_K,\quad V=XW_V,\qquad A=\mathrm{softmax}\!\Big(\frac{QK^\top}{\sqrt{d_k}}\Big)\in\mathbb R^{n\times n},\qquad Y=AV,\qquad y_i=\sum_{j=1}^{n}A_{ij}\,v_j
$$

- $X\in\mathbb R^{n\times d_{\text{model}}}$: one row per token: embeddings plus position information in the first layer, the previous layer's output later
- $W_Q,W_K\in\mathbb R^{d_{\text{model}}\times d_k}$: learned query and key projections; $q_i^\top k_j$ measures how relevant token $j$ is to token $i$
- $W_V\in\mathbb R^{d_{\text{model}}\times d_v}$: learned value projection: what token $j$ contributes if it is attended to
- $A$: attention matrix; row $i$ is the distribution of token $i$ over all $n$ tokens (including itself), each row sums to 1
- $\sqrt{d_k}$: keeps the scores at unit variance; derived in **Scaled dot-product attention**

The three projections are what make the layer useful. Without them ($Q=K=V=X$) the score $x_i^\top x_j$ is symmetric and usually largest for $j=i$, so each token mostly averages itself with tokens that look like it. With separate $W_Q$ and $W_K$, the relation "$i$ attends to $j$" need not be symmetric: a pronoun's query can look for features that only nouns carry in their keys, while the noun's own query looks for something else. $W_V$ then decides what information is copied along that edge. In practice the layer runs $h$ such heads in parallel with $d_k=d_{\text{model}}/h$ (see **Multi-head attention**).

## Permutation equivariance

Self-attention has no notion of order. Let $P$ be a permutation matrix that reorders the tokens. Then $(PX)W_Q=PQ$, the same for $K$ and $V$, and the score matrix becomes $PQK^\top P^\top$. A row-wise softmax commutes with permuting rows and columns, so:

$$
\mathrm{SA}(PX)=\mathrm{softmax}\!\Big(\frac{PQK^\top P^\top}{\sqrt{d_k}}\Big)PV=P\,\mathrm{softmax}\!\Big(\frac{QK^\top}{\sqrt{d_k}}\Big)P^\top P\,V=P\,\mathrm{SA}(X)
$$

- $P^\top P=I$: permutation matrices are orthogonal
- $\mathrm{SA}(PX)=P\,\mathrm{SA}(X)$: shuffling the input tokens shuffles the outputs in the same way and changes nothing else: the layer sees a **set**, not a sequence

Two identical tokens at different positions therefore get identical outputs. In "the cat sat on the mat", both copies of "the" produce the same row of $A$, so neither can tell which noun is its own. This is why Transformers add position information: absolute **Positional encoding** added to $X$, relative schemes such as **Rotary positional embeddings (RoPE)** or **ALiBi** inside the scores, or a **Causal attention** mask, which also breaks the symmetry. For genuinely set-structured data (point clouds, object slots, the latent array of a Perceiver) the symmetry is exactly what you want.

## Cost: constant path length, quadratic size

Per-layer cost for sequence length n and width d (Vaswani et al. 2017, Table 1)

| layer type | complexity per layer | sequential operations | maximum path length |
| --- | --- | --- | --- |
| self-attention | $O(n^2\cdot d)$ | $O(1)$ | $O(1)$ |
| recurrent | $O(n\cdot d^2)$ | $O(n)$ | $O(n)$ |
| convolutional (kernel k) | $O(k\cdot n\cdot d^2)$ | $O(1)$ | $O(\log_k n)$ |
| self-attention restricted to r neighbours | $O(r\cdot n\cdot d)$ | $O(1)$ | $O(n/r)$ |

Any two tokens interact through one attention step, so the gradient path between them has constant length. An RNN needs $O(n)$ steps, which is where vanishing gradients and slow sequential training come from. The price is the $n\times n$ matrix. Computing $QK^\top$ and $AV$ takes $4n^2d$ floating-point operations per layer (counting multiply and add), against roughly $24nd^2$ for the projections and the $4d$ feed-forward block. Attention is the cheaper part while $n<6d$; Vaswani et al. note that self-attention is faster than recurrence when $n$ is smaller than $d$, which was the case for sentence-level translation. Memory is the harder limit. Stored naively, the weights take $n^2$ numbers per head and sequence. **FlashAttention** avoids storing them, and **Sparse attention**, **Linear attention**, **Longformer** and **Linformer** change the $n^2$ itself.

> Figure: One attention head over the 10 tokens of 'the animal didn't cross the street because it was tired'. Embeddings are hand-set word features plus noise, and W_Q, W_K encode four relations: pronouns and adjectives look for animate nouns, verbs and determiners look for nouns, auxiliaries look for verbs. With the projections, 'it' puts 0.673 on 'animal' and 0.017 on 'street', 'tired' puts 0.514 on 'animal', and 'cross' puts 0.354 on 'street'. Both copies of 'the' get the same row (0.336 on 'street', 0.170 on 'animal'): without positions, neither can know which noun follows it. Switch to Q = K = V = X: the weights flatten and 8 of 10 rows put their largest weight on the token itself (the two 'the' rows split it between the two copies). Shuffle the tokens: the matrix is permuted, and the outputs are the permuted outputs, max |Y(PX) − P·Y(X)| about 1e−16. Add sinusoidal positions: the two 'the' rows now differ, 'it' → 'animal' rises to 0.831, and a shuffle changes the outputs by up to 0.302. The bottom strip counts the cost of one BERT-base-sized layer (d_model = 768): at n = 512 attention is 10.0% of the FLOPs; at n = 4096 it is 47.1% and each head's fp16 weight matrix takes 33.6 MB; at n = 131,072 it is 96.6%.

## Worked example: three tokens, one head

Take three tokens with $d_{\text{model}}=d_k=2$: $x_1=(1,0)$, $x_2=(0,2)$, $x_3=(1,1)$. Let $W_Q=I$, $W_K=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ (it swaps the two coordinates) and $W_V=\begin{pmatrix}1&2\\0&1\end{pmatrix}$. Then $Q=X$, $k_1=(0,1)$, $k_2=(2,0)$, $k_3=(1,1)$, and $v_1=(1,2)$, $v_2=(0,2)$, $v_3=(1,3)$.

Scores qᵢᵀkⱼ/√2 and weights (rows: queries; checked in PyTorch)

| query | s·1 | s·2 | s·3 | A·1 | A·2 | A·3 | yᵢ = Σⱼ Aᵢⱼvⱼ |
| --- | --- | --- | --- | --- | --- | --- | --- |
| x₁ = (1, 0) | 0.0000 | 1.4142 | 0.7071 | 0.1400 | 0.5760 | 0.2840 | (0.4240, 2.2840) |
| x₂ = (0, 2) | 1.4142 | 0.0000 | 1.4142 | 0.4458 | 0.1084 | 0.4458 | (0.8916, 2.4458) |
| x₃ = (1, 1) | 0.7071 | 1.4142 | 1.4142 | 0.1978 | 0.4011 | 0.4011 | (0.5989, 2.4011) |

**Reading the table**

1. Row 1: $q_1^\top k_2=(1,0)\cdot(2,0)=2$, divided by $\sqrt2$ gives $1.4142$. Token 1 attends most to token 2 (0.576), although $x_1$ and $x_2$ are orthogonal: $W_K$ decides what a match means.
2. $A$ is not symmetric: $A_{12}=0.576$ but $A_{21}=0.108$. Each row is a distribution of its own; columns need not sum to 1.
3. Output: $y_1=0.14\,(1,2)+0.576\,(0,2)+0.284\,(1,3)=(0.4240,\,2.2840)$.
4. Without projections ($Q=K=V=X$) the scores are $x_i^\top x_j/\sqrt2$ and token 2 gives 0.7679 to itself, because $\|x_2\|^2=4$ is the largest dot product in its row.
5. Permute the tokens to the order $(3,1,2)$: the outputs come out as $(y_3,y_1,y_2)$ exactly, as the equivariance identity says.

```python
import torch, torch.nn as nn, torch.nn.functional as F

class SelfAttention(nn.Module):
    """Single-head self-attention: Q, K and V are three projections of the same X."""
    def __init__(self, d_model, d_k):
        super().__init__()
        self.q = nn.Linear(d_model, d_k, bias=False)
        self.k = nn.Linear(d_model, d_k, bias=False)
        self.v = nn.Linear(d_model, d_k, bias=False)

    def forward(self, x, return_weights=False):
        # x (N, n, d_model)
        q, k, v = self.q(x), self.k(x), self.v(x)                 # each (N, n, d_k)
        scores = q @ k.transpose(-2, -1) / k.size(-1) ** 0.5      # (N, n, n)
        a = scores.softmax(dim=-1)                                # each row sums to 1
        y = a @ v                                                 # (N, n, d_k)
        return (y, a) if return_weights else y

torch.manual_seed(0)
N, n, d_model, d_k = 2, 10, 32, 16
x = torch.randn(N, n, d_model)
sa = SelfAttention(d_model, d_k)
y, a = sa(x, return_weights=True)
print(y.shape, a.shape)                          # torch.Size([2, 10, 16]) torch.Size([2, 10, 10])
print(torch.allclose(a.sum(-1), torch.ones(N, n)))   # True

# Permutation equivariance: shuffling the tokens shuffles the outputs the same way.
perm = torch.randperm(n)
print(torch.allclose(sa(x[:, perm]), y[:, perm], atol=1e-6))   # True

# Same result from PyTorch's fused kernel.
y2 = F.scaled_dot_product_attention(sa.q(x), sa.k(x), sa.v(x))
print(torch.allclose(y, y2, atol=1e-6))          # True

# Adding a position vector per slot breaks the symmetry.
pos = torch.randn(n, d_model)
print(torch.allclose(sa(x[:, perm] + pos), sa(x + pos)[:, perm], atol=1e-6))   # False

# The n x n weight matrix grows quadratically: fp16 bytes per head, per sequence.
for m in (1024, 8192, 65536):
    print(m, f"{m * m * 2 / 2**20:.0f} MiB")     # 2 MiB, 128 MiB, 8192 MiB
```

Single-head self-attention from scratch, checked against PyTorch's fused kernel and for permutation equivariance

**Self-attention in the original Transformer (Vaswani et al. 2017)**

- **Where:** encoder: one self-attention sub-layer per layer over the source; decoder: masked self-attention over the target prefix, then **Cross-attention** to the encoder
- **Base model:** $N=6$ layers, $d_{\text{model}}=512$, $h=8$ heads, $d_k=d_v=64$, feed-forward $d_{ff}=2048$
- **Big model:** $d_{\text{model}}=1024$, $h=16$, $d_{ff}=4096$
- **Each sub-layer:** $\mathrm{LayerNorm}(x+\mathrm{Sublayer}(x))$ with dropout 0.1 on the sub-layer output (post-LN)
- **WMT'14 En→De:** 27.3 BLEU (base, 12 hours on 8 P100), 28.4 BLEU (big, 3.5 days)
- **WMT'14 En→Fr:** 41.8 BLEU (big)

> **Without positions it is a bag of tokens:** A Transformer encoder with no **Positional encoding** gives the same output for "dog bites man" and "man bites dog", up to the order of the rows. If a model ignores word order, check that positions are actually added, that they are not overwritten by a later reshape, and that rotary or relative schemes are applied to $Q$ and $K$ and not to $V$.

> **The n × n matrix, not the parameters, sets the memory:** A self-attention layer has $3d_{\text{model}}d_k$ parameters per head regardless of $n$, but the activations kept for backprop include the $n\times n$ weights of every head and layer. At $n=8192$ that is 128 MiB per head per sequence in fp16, times heads, layers and batch. Long-context training runs out of memory here first; fused kernels such as **FlashAttention** never materialise $A$.

> **A data-dependent, fully connected layer:** A dense layer mixes features with fixed weights; self-attention mixes **tokens** with weights computed from the tokens themselves. Every output can depend on every input, as in a fully connected layer over positions, but the mixing matrix $A$ is recomputed for each input and works for any $n$. Convolution is the special case of fixed weights over a local window. Cordonnier, Loukas and Jaggi (ICLR 2020) showed that multi-head self-attention with relative positions can express any convolution, which is part of why **Vision Transformers (ViT)** work at all.

> **Self-attention versus cross-attention:** The mechanism is identical; only the source of $K$ and $V$ differs. Self-attention takes $Q$, $K$ and $V$ from one sequence, so $A$ is square. **Cross-attention** takes queries from one sequence and keys and values from another, so $A$ is $n_q\times m$. A decoder-only language model uses only (causal) self-attention.

**Strengths**

- Constant path length between any two tokens: long-range dependencies are one step away
- All positions computed in parallel with a few large matrix products, unlike an RNN
- Input-dependent mixing weights; works for any sequence length with the same parameters
- Permutation equivariance is a clean inductive bias for sets

**Limitations**

- $O(n^2d)$ time and $O(n^2)$ memory per head for the attention weights
- No built-in notion of order: needs positional information
- No locality prior, so it typically needs more data than CNNs or RNNs on small datasets
- Attention weights invite over-interpretation as explanations

**Question:** You feed a Transformer encoder layer (no positional encoding) the tokens [A, B, C] and then [C, A, B]. How are the two outputs related?

- A. They are unrelated, because attention weights depend on order
- B. The second output is the first with its rows reordered to (C, A, B)
- C. They are identical row by row
- D. Only the first token's output changes

**Answer:** B. The second output is the first with its rows reordered to (C, A, B) — Self-attention, the position-wise feed-forward layer, residuals and layer norm are all permutation-equivariant: $f(PX)=Pf(X)$. Each token gets the same output as before, now in its new row. Position information has to be injected explicitly to break this.

**Question:** A model has d_model = 1024. Using the 4n²d versus 24nd² count, from about which sequence length does attention (QKᵀ and AV) cost more FLOPs than the projections and feed-forward block of a layer?

- A. n ≈ 1024
- B. n ≈ 4096
- C. n ≈ 6144
- D. n ≈ 24,576

**Answer:** C. n ≈ 6144 — $4n^2d=24nd^2$ gives $n=6d=6144$. Below that the dense parts dominate the compute, which is why short-context models spend most FLOPs in projections and the MLP. Memory for the $n\times n$ weights can become the bottleneck earlier.

**Key points**

- $Q=XW_Q,\ K=XW_K,\ V=XW_V$ from the same $X$; $Y=\mathrm{softmax}(QK^\top/\sqrt{d_k})\,V$ with $A\in\mathbb R^{n\times n}$, rows summing to 1.
- Permutation-equivariant: $\mathrm{SA}(PX)=P\,\mathrm{SA}(X)$, so positions must be added (positional encodings, RoPE, ALiBi, causal masks).
- Cost per layer $O(n^2d)$ time and $O(n^2)$ memory per head, but $O(1)$ sequential steps and $O(1)$ path length between any two tokens.
- Separate $W_Q$ and $W_K$ make attention asymmetric; without them a token mostly attends to itself.
- Vaswani et al. (NeurIPS 2017) built the Transformer from self-attention alone: 28.4 BLEU on WMT'14 En→De.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
