Permutation Equivariance in Self-Attention and What Position Encodings Restore

Shuffle the rows of the input matrix $X \in \mathbb{R}^{n \times d}$ and feed it to a self-attention layer. The output rows come back shuffled in exactly the same way, with every row’s content unchanged. This holds for any permutation, for any weight matrices, at any point in training. It is not a learned property and it is not approximate: it follows from the layer’s definition, and it is the reason a transformer with no positional signal cannot distinguish “dog bites man” from “man bites dog”.

The symmetry follows from two sums

Self-attention computes, for each query row $x_i$, a weighted average of value rows:

$$y_i = \sum_{j=1}^{n} p_{ij} , x_j W^V, \qquad p_{ij} = \frac{\exp!\left(x_i W^Q (x_j W^K)^\top / \sqrt{d_k}\right)}{\sum_{m} \exp!\left(x_i W^Q (x_m W^K)^\top / \sqrt{d_k}\right)}$$

Both the numerator and the denominator are sums over the same index set, and the weights $p_{ij}$ depend only on the pair $(x_i, x_j)$, never on $i$ or $j$ themselves. Apply a permutation $\pi$ to the rows, so row $i$ becomes old row $\pi(i)$. The score between the new row $i$ and the new row $j$ equals the score between old rows $\pi(i)$ and $\pi(j)$, the denominator sums over the same permuted set and is therefore unchanged, and the output at new row $i$ is the old output at row $\pi(i)$. That is the definition of equivariance: $f(\pi X) = \pi f(X)$.

The feed-forward sublayer, layer normalization, and residual connections are all row-wise maps, so they commute with permutation as well. A stack of them is permutation-equivariant end to end. The symmetry group is the full symmetric group $S_n$ on $n$ elements, of order $n!$. For a 512-token sequence that is a group with more elements than there are atoms in the observable universe, and the model’s function is constant along every one of its orbits.

The consequence for language is immediate and fatal without a fix. The multiset of token embeddings carries no ordering, so the layer cannot represent a bigram, a dependency, or a phrase boundary. It can represent set-level properties, such as whether a token appears at all or how many distinct tokens there are, and nothing about their arrangement.

Absolute encodings break the symmetry by adding, not by concatenating

The original construction adds a position-dependent vector to the token embedding before the first block:

$$x_i = E[t_i] + P_i$$

where $P_i \in \mathbb{R}^{d_{\text{model}}}$ depends only on index $i$. The sinusoidal form uses, for coordinate pairs,

$$P_{i,2k} = \sin!\left(i / 10000^{2k/d_{\text{model}}}\right), \qquad P_{i,2k+1} = \cos!\left(i / 10000^{2k/d_{\text{model}}}\right)$$

The wavelengths form a geometric progression from $2\pi$ up to nearly $10{,}000 \cdot 2\pi$, so the encoding of position $i$ is a point on a $d_{\text{model}}/2$-dimensional torus whose coordinates rotate at different rates. Two properties follow and both were cited as reasons for the choice. First, for any fixed offset $k$, $P_{i+k}$ is a fixed linear function of $P_i$, a block-diagonal rotation, which makes relative offsets representable by a linear map that a single attention layer can learn. Second, the encoding of a position is unique up to the period of the slowest coordinate, which is tens of thousands of positions, and the dot product $P_i \cdot P_{i+k}$ depends only on $k$, decaying with distance in a way that gives the model a soft locality bias for free.

The symmetry is now broken, but not in the way a reader might assume. Adding $P_i$ does not make the layer sensitive to order in the abstract; it makes the layer sensitive to which positions the tokens occupy. A sequence whose tokens are the reverse of another has different sums at every index, so the outputs differ. But the invariance is only broken for permutations that move tokens between positions with different encodings, which is every nontrivial permutation. The group is reduced to the trivial one, and the price is that the model must learn from data that position 3 and position 7 are related by an offset of 4, because the encoding provides no direct signal of that relation beyond the linear-map property above.

Learned absolute encodings replace $P_i$ with a lookup table of $n_{\max} \times d_{\text{model}}$ parameters. They are equally symmetry-breaking and slightly more flexible, at the cost of a hard limit: positions beyond $n_{\max}$ have no embedding, so the context length is fixed at training time and extending it requires either interpolating the table or initializing new rows. Interpolation of a learned table is not equivalent to the sinusoidal case, where a longer context can be handled by evaluating the same formula at larger indices.

import numpy as np

def sinusoidal(n, d_model, base=10000.0):
    inv = 1.0 / (base ** (np.arange(0, d_model, 2) / d_model))  # per-pair frequency
    pos = np.arange(n)[:, None] * inv[None, :]
    pe = np.zeros((n, d_model))
    pe[:, 0::2] = np.sin(pos)
    pe[:, 1::2] = np.cos(pos)
    return pe

pe = sinusoidal(64, 16)
inv = 1.0 / (10000.0 ** (np.arange(0, 16, 2) / 16))
k = 5
# rotating the pair (sin, cos) by angle k*inv[j] maps P[i] onto P[i+k]
for j in range(3):
    a = -k * inv[j]          # negative angle maps P[i] to P[i+k]
    rot = np.array([[np.cos(a), -np.sin(a)], [np.sin(a), np.cos(a)]])
    lhs = pe[10, 2*j:2*j+2] @ rot.T
    print(j, np.allclose(lhs, pe[10 + k, 2*j:2*j+2]))

Relative encodings move the position signal into the score

A different answer is to leave the token embeddings permutation-invariant and add position information to the attention score itself:

$$e_{ij} = \frac{x_i W^Q \left(x_j W^K + a_{ij}^K\right)^\top}{\sqrt{d_k}}$$

where $a_{ij}^K$ is a learned vector indexed by the relative offset $j - i$ (clipped to a range, or shared across a set of buckets). The value side gets an analogous term. Now the score depends on the pair’s relative position, and the layer is equivariant to translation of the whole sequence: shift every index by a constant and all offsets $j - i$ are unchanged, so the outputs shift with it. This is a stronger and more useful symmetry than anything absolute encodings provide, because the model no longer has to relearn the same relation at every absolute position.

The cost is parameter count and score-computation work. With $h$ heads, per-head relative key and value tables of size $(2k_{\max}+1) \times d_k$ add parameters proportional to head count and offset range, and the score computation gains a gather over the offset table. For a maximum offset of 512 and 16 heads at $d_k = 64$, the tables hold roughly $16 \times 1025 \times 64 \approx 10^6$ entries on the key side, comparable to a small projection matrix. Implementations usually clip offsets beyond the table range to the boundary entry, which means far-apart tokens are treated identically, a locality assumption that is deliberate but is a real limitation for tasks requiring long-range exact distance.

What the choice constrains downstream

The three families differ in which transformations leave the layer’s behaviour unchanged, and that difference is what determines whether a trained model can be extended to longer inputs.

Family	Symmetry remaining	Extrapolation beyond trained length
None	full $S_n$	meaningless; order is unrepresentable
Absolute sinusoidal	trivial	possible by evaluating the formula at larger indices; quality depends on the model having learned the offset structure
Absolute learned	trivial	requires interpolation or new parameters
Relative (learned offsets)	translation of the whole sequence	requires the offset table to cover the new range
Rotary	translation, exactly	frequency-dependent; high-frequency coordinates alias past their period

Rotary encodings, covered in rotary position embeddings and relative offsets, take the relative idea further by applying a position-dependent rotation to the query and key vectors so that the score depends only on the difference of their angles. Because the rotation is exact rather than learned, the translation symmetry is exact, but the periodicity of the rotation means that offsets beyond a coordinate’s wavelength become indistinguishable from smaller ones. That aliasing, not the parameter count, is the real constraint on context extension.

Two further points are worth keeping in view. Position information interacts with masking: a causal mask already breaks permutation symmetry in a directional way, since it makes the layer’s output at position $i$ depend only on positions $\le i$. A causal model with no positional encoding is therefore not permutation-invariant; it is invariant only to permutations that preserve the prefix structure, and the set of such permutations is small. The mask is doing part of the ordering work, which is why causal language models tolerate weaker positional signals than bidirectional encoders. The mechanics of that interaction are in causal masking and mask placement.

The second point concerns vision and other non-sequential inputs. A patch-based image transformer has a genuine two-dimensional grid, and a one-dimensional absolute encoding over the flattened patch order introduces an arbitrary choice of traversal. The original vision transformer used learned one-dimensional embeddings and still worked, which suggests the model can recover two-dimensional structure from data given enough examples, but variants that encode row and column separately, or that use relative offsets in both axes, remove the arbitrary factor and generalize differently across resolutions. The symmetry argument is the same in every modality: the encoding choice fixes which transformations the model must learn to undo, and everything else is data.