Md. Asif Uddin

Book I · Proposition 7

Attention is permutation-invariant, and positional encoding is the repair.

Given

Permutation equivariance, and the repairIn the upper panel, self-attention alone maps a shuffled input to an identically shuffled output: reordering the tokens carries no information. In the lower panel the same tokens carry positional encodings, so a reordering produces a genuinely different output.attention aloneattention + positionthecatsatsatthecatthecatsatsatthecat+p1+p2+p3+p1+p2+p3the′cat′sat′sat′the′cat′the′cat′sat′cat′sat′the′same output, merely reordered — the model cannot tell the two inputs apartdifferent output — order is now information
Fig. 7 — Permutation equivariance and its repair. Without positional encoding a reordered input yields a merely reordered output; with it, order becomes information.

Demonstration

Let P be a permutation matrix and f a self-attention layer. Then

f(PX) = P f(X)

The layer is permutation-equivariant: permute the input and you get the same outputs in the permuted order. Pool over the sequence and equivariance becomes outright invariance — the set of outputs is unchanged.

The proof is immediate from Proposition 4. Every weight wᵢⱼ depends only on the contents of rows i and j. Relabelling rows relabels the weights identically, so the products and their sums carry through unchanged. There is no term anywhere in the computation that references an absolute index.

This means the cat sat and sat the cat are, to attention alone, the same object. For language that is fatal. For point clouds it is exactly what you want, which is a good reminder that this is a property rather than a bug.

The repair is to make position part of the content. Sinusoidal and learned absolute encodings add a position-dependent vector to each token embedding before the first layer. Rotary encodings instead rotate q and k by an angle proportional to position, so that the dot product qᵢ · kⱼ becomes a function of i − j — relative position falls out of the algebra rather than being bolted on.

Corollary

Any claim that a transformer “understands word order” is a claim about the positional encoding, not about attention. When order-sensitivity fails — long contexts, extrapolation past the training length — the encoding is the first thing to examine, because attention itself never had an opinion about order.