Why a transformer cannot tell word order

The statement#

Let $X \in \mathbb{R}^{n \times d}$ be the token matrix and $P \in {0,1}^{n \times n}$ a permutation matrix. Single-head self-attention is

$$ \mathrm{Attn}(X) = \mathrm{softmax}!\left( \frac{XW_Q (XW_K)^\top}{\sqrt{d_k}} \right) X W_V $$

Here $W_Q, W_K \in \mathbb{R}^{d \times d_k}$ and $W_V \in \mathbb{R}^{d \times d_v}$ are learned projections, $d_k$ is the head width, and softmax is applied row-wise.

Substituting $PX$:

$$ \frac{(PXW_Q)(PXW_K)^\top}{\sqrt{d_k}} = P \left( \frac{XW_Q(XW_K)^\top}{\sqrt{d_k}} \right) P^\top $$

Row-wise softmax commutes with a symmetric permutation of rows and columns, and $P^\top P = I$, so

$$ \mathrm{Attn}(PX) = P\,\mathrm{Attn}(X) $$

The result extends to multi-head attention (each head is equivariant, and concatenation is per-token), to the position-wise feed-forward block, to layer normalisation, and to residual connections. Every one of those acts row-wise. A stack of $L$ such layers is therefore equivariant, so a transformer encoder with no positional information computes a set function, not a sequence function.

Consequences for expressivity#

Such a model cannot compute any function that distinguishes orderings of the same multiset. That rules out language modelling in any serious sense, since even the bigram distribution requires order.

Yun et al. (2020), Are Transformers universal approximators of sequence-to-sequence functions?, make the boundary precise. Transformers are universal approximators of continuous permutation-equivariant sequence-to-sequence functions on a compact domain; adding positional encodings extends this to arbitrary continuous sequence-to-sequence functions. The positional encoding buys the second class.

The two entry points#

Position can enter in exactly two places. Every scheme in this section is one of them, or a hybrid.

Additive, at the input. Modify $X$ before attention: $X' = X + E$ where $E \in \mathbb{R}^{n \times d}$ depends on position. Sinusoidal and learned absolute embeddings live here. The change propagates through $W_Q$ and $W_K$, so the attention logit becomes

$$ (x_m + e_m)W_Q W_K^\top (x_n + e_n)^\top $$

which expands into four terms: content-content, content-position, position-content and position-position. Only the last carries pure positional signal, and the cross terms mix meaning with place. That interference is a documented weakness of the additive family.

Inside the attention logit. Modify the score directly:

$$ a_{mn} = \frac{q_m^\top k_n}{\sqrt{d_k}} + b(m, n) $$

or apply a position-dependent transformation to $q$ and $k$ before the dot product. T5's relative bias, ALiBi and RoPE all live here. This family keeps the value path clean and expresses position as a relation between two tokens rather than a property of one.

Why the field moved to the second family#

Three reasons, in order of practical weight.

• Length behaviour. A bias or rotation depending on $m - n$ is defined for any $m, n$. An absolute table of size $L$ is defined only up to $L$.
• Translation structure. Language is close to translation-invariant at the sentence level. A relative parameterisation encodes that prior directly instead of spending capacity learning it.
• Cache compatibility. With KV caching, keys are computed once and reused. A scheme applied to keys once, consistently, composes cleanly with cache reuse and with sliding windows.

Causal masking is not a substitute#

Applying a lower-triangular mask $M$ with $M_{mn} = 0$ for $n \le m$ and $-\infty$ otherwise destroys equivariance, because $M$ is not permutation-symmetric. The output at position $m$ depends on the multiset of the first $m+1$ tokens, and those multisets differ in size across positions.

Haviv et al. (2022), Transformer Language Models without Positional Encodings Still Learn Positional Information, show decoder-only models exploit this and recover position internally. Kazemnejad et al. (2023), NeurIPS, extend the analysis and show NoPE can express both absolute and relative schemes. That has its own lesson. The point here is that the mask leaks position as a side effect; it is not a designed encoding.

Papers#

• Vaswani et al., Attention Is All You Need, 2017 — arxiv.org/abs/1706.03762
• Yun et al., Are Transformers universal approximators of sequence-to-sequence functions?, ICLR 2020 — arxiv.org/abs/1912.10077
• Haviv et al., Transformer Language Models without Positional Encodings Still Learn Positional Information, 2022 — arxiv.org/abs/2203.16634
• Kazemnejad et al., The Impact of Positional Encoding on Length Generalization in Transformers, NeurIPS 2023 — arxiv.org/abs/2305.19466

What to learn next#

• Sinusoidal position encoding — the first answer, from the original paper.
• Attention — the mechanism that loses the order in the first place.
• Transformers — where this sits in the full architecture.