Position Problem › Attention Is Permutation Equivariant

To understand why self-attention ignores position, we need to examine its mathematical structure with care. The conclusion that self-attention is position-blind is not intuitive at first, because the computation does produce one output vector per position. It looks like position is being tracked. But appearances are deceiving. Let's build up the key insight step by step, starting with precise definitions and culminating in a demonstration that reveals where position information is missing.

Two related properties appear throughout machine learning, and distinguishing them clarifies exactly what kind of symmetry self-attention has.

A function is permutation invariant if reordering its inputs leaves the output completely unchanged. Computing the mean of a set of numbers is permutation invariant: the mean of $\{3, 7, 2, 5\}$ is the same as the mean of $\{5, 2, 7, 3\}$. Set membership and operations such as summation or taking a maximum have the same property. Permutation invariant functions discard order entirely.

A function is permutation equivariant if reordering the inputs causes the outputs to be reordered in exactly the same way. If you feed a permuted input, you get back the same outputs you would have gotten from the original input, just rearranged by the same permutation. Formally, a function $f$ is permutation equivariant if for any permutation $\pi$:

$$f(\pi(\mathbf{X})) = \pi(f(\mathbf{X}))$$

where:

• $\mathbf{X}$: the input sequence (a matrix where each row is a token's embedding)
• $\pi$: any permutation of the row indices
• $f(\mathbf{X})$: the output sequence produced by the function $f$
• $\pi(f(\mathbf{X}))$: that same output, with its rows rearranged by $\pi$

Self-attention falls squarely into the equivariant category, not the invariant category.

Why does equivariance matter more than invariance here? Invariance would be even more extreme: the output itself would not change when we reorder inputs. Self-attention at least tracks which output corresponds to which input, which is why we describe it as equivariant rather than invariant. But equivariance is still problematic for language, because it means the model cannot tell from the outputs alone whether the input was "dog bites man" or "man bites dog." The relative ordering between positions carries no information. Two sequences that are permutations of each other produce outputs that are the same permutation of each other.

The key insight is this: permutation equivariance means that reordering the input has exactly the same effect as reordering the output. The attention mechanism does not encode any relationship between input positions that survives reordering. It is as if the attention computation is computed in a "coordinate-free" space where positions have no identity.

To see why permutation equivariance emerges, we need to trace through the self-attention computation and identify every place where position could enter, but does not.

Self-attention produces an output vector for each position by aggregating information from all positions. For position $i$, we compute a weighted sum where each position $j$ contributes its value vector, scaled by how relevant it is to position $i$. This is the fundamental operation of attention:

$$\mathbf{y}_i = \sum_{j=1}^{n} \alpha_{ij} \mathbf{v}_j$$

where:

• $\mathbf{y}_i \in \mathbb{R}^{d_v}$: the output representation for position $i$
• $\alpha_{ij}$: the attention weight from position $i$ to position $j$ (determines how much $j$ contributes to $i$'s output)
• $\mathbf{v}_j \in \mathbb{R}^{d_v}$: the value vector at position $j$ (the information that position $j$ contributes)
• $n$: the sequence length
• $\sum_{j=1}^{n}$: summation over all positions in the sequence

Notice that the formula is a weighted sum: a linear combination of value vectors. The weight $\alpha_{ij}$ controls how much of position $j$'s value flows into position $i$'s output. If $\alpha_{ij}$ is large, position $j$ has a strong influence on position $i$'s representation. If $\alpha_{ij}$ is near zero, position $j$ contributes almost nothing.

This formula shows that the output at position $i$ depends on all value vectors $\mathbf{v}_j$ and all attention weights $\alpha_{ij}$. But notice: the values come from the token content, and the weights come from content comparisons. Where does position enter?

The attention weights themselves come from applying softmax to scaled dot products between query and key vectors. The softmax function converts raw similarity scores into a probability distribution. This keeps all weights are positive and sum to 1:

$$\alpha_{ij} = \frac{\exp\!\left(\mathbf{q}_i \cdot \mathbf{k}_j / \sqrt{d_k}\right)}{\sum_{l=1}^{n} \exp\!\left(\mathbf{q}_i \cdot \mathbf{k}_l / \sqrt{d_k}\right)}$$

where:

• $\alpha_{ij}$: the attention weight from position $i$ to position $j$ (how much position $i$ attends to position $j$)
• $\mathbf{q}_i \in \mathbb{R}^{d_k}$: the query vector for position $i$
• $\mathbf{k}_j \in \mathbb{R}^{d_k}$: the key vector for position $j$
• $d_k$: the dimension of query and key vectors (used for scaling)
• $\exp(\cdot)$: the exponential function. This keeps all values are positive
• $\sum_{l=1}^{n}$: summation over all $n$ positions, serving as the normalizing constant

The queries and keys are computed by multiplying the input embedding by learned weight matrices. For position $i$ with input embedding $\mathbf{x}_i$:

$$\mathbf{q}_i = \mathbf{x}_i \mathbf{W}_Q, \quad \mathbf{k}_i = \mathbf{x}_i \mathbf{W}_K, \quad \mathbf{v}_i = \mathbf{x}_i \mathbf{W}_V$$

where $\mathbf{W}_Q$, $\mathbf{W}_K$, and $\mathbf{W}_V$ are the learned projection matrices shared across all positions. The same matrices are applied to every token, regardless of where it appears in the sequence.

Here is the critical observation: examine both equations carefully and notice what is absent. The indices $i$ and $j$ appear only as subscripts identifying which vectors to retrieve. They never appear as values in the computation itself. The attention weight $\alpha_{ij}$ depends entirely on:

1. The query vector $\mathbf{q}_i$, which is derived from the content at position $i$ (the token embedding $\mathbf{x}_i$)
2. The key vector $\mathbf{k}_j$, which is derived from the content at position $j$ (the token embedding $\mathbf{x}_j$)
3. The normalization over all keys, which also depends only on content

Position indices serve as labels that tell us which output corresponds to which input. They are bookkeeping, not input features. The number $i$ or $j$ itself never enters any arithmetic operation. If we swap the tokens at positions 2 and 5, the query and key vectors simply swap, and the computation produces swapped outputs. The absolute values 2 and 5 played no role.

Think of it as the difference between a library catalog (where shelf number matters for retrieval) and a set of books on a table (where the arrangement of books has no permanent identity). Self-attention is the table: books can be rearranged and the pairwise relationships remain identical, just reordered.

This contrasts sharply with recurrent networks. In an RNN or LSTM, position is implicitly encoded through sequential processing. The hidden state at step 5 depends on the hidden state at step 4, which depends on step 3, and so on. The temporal chain of computation bakes position into the representation as an inductive bias: earlier tokens shape later representations in ways that later tokens cannot shape earlier ones. Self-attention discards this sequential chain entirely, processing all positions in parallel and achieving massive efficiency gains, but at the cost of positional awareness.

The mathematical argument is clear, but seeing the effect in code makes it concrete. Let's implement self-attention and verify that permuting the input produces identically permuted output.

The outputs match exactly, up to floating-point precision. This confirms permutation equivariance: permuting the input permutes the output in the same way. Self-attention does not "know" that we reordered the tokens. It computes the same pairwise relationships in a different order and produces the same outputs in a different order. No information about the original positions has been preserved beyond the assignment of outputs to input slots.

This experiment confirms what the mathematics predicted. Self-attention treats the input as an unordered set of tokens, using only their content to determine relationships. Each token's output depends on three things, none of which involve position:

1. Its own content (through its query vector, which asks "what am I looking for?")
2. The content of all other tokens (through their key vectors, which answer "what do I offer?")
3. The pairwise content relationships (through dot products that measure semantic compatibility)

This is a deliberate architectural choice, not an oversight. The original Transformer designers wanted to avoid the sequential bottleneck of RNNs, where position is encoded implicitly by the order of computation. Parallelizing across all positions means forgoing positional inductive bias. The model is given maximum flexibility to learn relationships from content alone, but that flexibility comes with the responsibility of explicitly injecting position information from outside the attention mechanism.

Notice that this is quite different from convolutional neural networks (CNNs), which have a different kind of positional inductive bias. A CNN's filters are applied at specific spatial locations, and nearby positions share features through local connectivity. Position is implicitly encoded through the spatial structure of the convolution. Self-attention has no analogous spatial structure. It is maximally flexible with respect to distance.