Attention is permutation equivariant

ProofIntermediate⏱ 30 minDeep Learningattentionpermutationpositional encoding

Theory: The Mathematics of Transformers →

Problem

Prove that $\operatorname{Attention}$ applied to permuted inputs returns the permuted output, and deduce that a transformer without positional information computes a function of the input multiset. Verify that the MLP and normalisation sublayers do not break the symmetry.

Write a complete argument. Every inequality you use should be one you could state precisely.

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
When does attention dominate the MLP?	Deep Learning	Numerical	Beginner	30 min
Implement multi-head attention from scratch run	Deep Learning	Coding	Intermediate	3 hours
The softmax Jacobian as a variance, and saturation	Deep Learning	Proof	Intermediate	30 min
Why attention divides by the square root of d_k	Deep Learning	Proof	Intermediate	30 min
Multi-head attention is a sum of low-rank maps	Deep Learning	Proof	Advanced	30 min