Consider self attention, where:
$$ \text{Attention}(Q,K,V) = \text{softmax}(\frac{QK^T}{\sqrt{d_k}})V $$
We want to show permutation invariance, meaning that shuffling the tokens/rows in an ordered input $X$ does not affect the attention scores between two tokens, regardless of their old and new positions.
Semantically, “man eats chicken” and “chicken eats man” generates the same attention score for the query “eats” to “man” even though the semantic meaning changes due to reordering.
Each row in the input matrix corresponds to a token. The columns correspond to the features associated to a token. When we shuffle tokens around, a permutation matrix applied to the rows (the left hand side of the matrix) is sufficient. There is no need to shuffle the columns (apply P^t to rhs) as column-order should be preserved.
$$ X’ = PX \\ Q’, V’, K’ = PQ, PV, PK $$
Recall: $$ \text{Attention}(Q,K,V) = \text{softmax}(\frac{QK^T}{\sqrt{d_k}})V $$
We first consider the attention score without softmax and without sqrt scaling; $A = QK^T$
If we shuffle the rows,
$$
A’ = Q’V’^T \\
A’ = (PQ)(PK)^T \\
A’ = PQK^TP^T \\
A’ = PAP^T
$$
Notice that this resolves to $PAP^T$, which means that $A’$ is a permutation of $A$. This is due to permutation conjugation.
This is not obvious to me initially because I have never learnt permutation conjugation before. But essentially permutating a 2D matrix requires the permutation matrix (and its transpose) to be applied. To help with visualization I copied an example (generated via AI because im too lazy to handtype latex) that can be traced and manually worked out.
{begin ai}
Let
$$ A = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} $$
where $A_{ij}$ is the attention score between token $i$ and token $j$.
Suppose we permute the tokens as
$$ [1,2,3] \rightarrow [3,2,1]. $$
The corresponding permutation matrix is
$$ P = \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}, \qquad P^T = \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}. $$
(human note: P = P^T due to symmetry, a special case that may not always hold. But this doesn’t matter for this example.)
We can see what $PAP^T$ does explicitly:
$$ PA = \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix} \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} =\begin{bmatrix} a_{31} & a_{32} & a_{33} \\ a_{21} & a_{22} & a_{23} \\ a_{11} & a_{12} & a_{13} \end{bmatrix} $$
The left multiplication by $P$ permutes the rows, because rows represent query tokens.
Then,
$$ PAP^T = \begin{bmatrix} a_{31} & a_{32} & a_{33} \\ a_{21} & a_{22} & a_{23} \\ a_{11} & a_{12} & a_{13} \end{bmatrix} \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix} =\begin{bmatrix} a_{33} & a_{32} & a_{31} \\ a_{23} & a_{22} & a_{21} \\ a_{13} & a_{12} & a_{11} \end{bmatrix}. $$
The right multiplication by $P^T$ permutes the columns, because columns represent key tokens.
Thus,
$$ \boxed{ A’ = PAP^T = \begin{bmatrix} a_{33} & a_{32} & a_{31} \\ a_{23} & a_{22} & a_{21} \\ a_{13} & a_{12} & a_{11} \end{bmatrix} } $$
For example, the original relationship
$$ A_{13} $$
is the relationship between token $1$ and token $3$.
After the permutation,
$$ 1 \rightarrow 3, \qquad 3 \rightarrow 1, $$
so the same relationship appears at
$$ A’_{31}. $$
Therefore,
$$ \boxed{A_{13}=A’_{31}}. $$
More generally, if token $i$ moves to position $i’$ and token $j$ moves to position $j’$, then
$$ \boxed{A_{ij}=A’_{i’j’}}. $$
The attention scores themselves have not changed. Only their positions in the matrix have changed.
{end ai}
Since we shown that shuffling tokens about does not fundamentally change the attention relationship between tokens, we show that when “man eats chicken”, it also means that “chicken eats man” (insofar as attention between tokens matter). This is why the Transformer architecture requires positional encoding to maintain semantics driven by order across tokens.