Research map / Architectures and efficiency / Attention and transformers
Permutation Equivariance of Transformers and Its Applications
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Defines a broader permutation equivariance (inter- and intra-token, forward and backward) for Transformers, proves it for common architectures, and applies it to privacy-enhanced split learning and model authorization via column-permutation "encryption".
Problem
Prior work shows Transformers are robust to token shuffling only in the forward pass, and treats permutation invariance narrowly; the paper asks whether permutation equivariance holds more broadly across row/column permutations in both forward and backward propagation, and whether it can be used for
Approach
Extends permutation equivariance to intra-token (column) permutations as well as inter-token (row) ones, and proves that weight-permuted (P_C^{-1} W P_C) Transformers train equivariantly, so the permutation acts as a key for privacy-preserving offloading and model authorization.
Key results
- Row and column permutation leave ViT-Base (97.65%) and ViT-Adapter (48.75 mIoU) test results unchanged, and column-permuted models with normal inputs drop to random-guess accuracy (about 10% on CIFAR-10).
- On CelebA split learning, row permutation with Gaussian noise lowers SSIM from 0.457 to 0.167 at equal utility (88.8% accuracy).
- Fine-tuning an encrypted ViT without the key reaches 78.03% test accuracy versus 97.94% with the key, and overhead is about 2.1 GFLOPs more (100.4B to 102.1B FLOPs/B) with negligible memory change.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add row permutation to Gaussian Noise features | Split learning on CelebA · CelebA | SSIM: 0.457 -> 0.167 | Helped |
| Add row permutation to Gaussian Noise features | Split learning on CelebA · CelebA | accuracy: 88.8 -> 88.8 | No clear effect |
| Add row permutation to loss-pass filter features | Split learning on CelebA · CelebA | SSIM: 0.450 -> 0.110 | Helped |
| Add row permutation to loss-pass filter features | Split learning on CelebA · CelebA | accuracy: 90.1 -> 90.2 | No clear effect |
| Add row permutation to Batch Shuffle features | Split learning on CelebA · CelebA | accuracy: 90.8 -> 91.1 | Helped |
| Add row permutation to Batch Shuffle features | Split learning on CelebA · CelebA | SSIM: 0.148 -> 0.143 | Helped |
| Use row permutation during inference | ViT-Base and ViT-Adapter · Cifar10 and ADE20k | accuracy: 97.65 -> 97.65 | No clear effect |
| Use column permutation with correspondingly permuted weights | ViT-Base and ViT-Adapter · Cifar10 and ADE20k | accuracy: 97.65 -> 97.65 | No clear effect |
| Train with row permutation and inverse permutation | ViT-Base · Cifar10 | accuracy: 97.75 -> 97.73 | No clear effect |
| Train with row permutation and inverse permutation | Bert (Small) · SNLI | accuracy: 76.4 -> 76.5 | No clear effect |
| Train with column permutation and correspondingly permuted weights | Bert · IMDB | accuracy: 94.00 -> 93.72 | No clear effect |
| Train with column permutation and correspondingly permuted weights | GPT2 · IMDB | accuracy: 94.03 -> 93.66 | No clear effect |
Surprising findings
- Set Transformer's permutation invariance is described as a pseudo-invariance because its PMA head does not preserve gradient alignment in the backward pass.
- Unauthorized fine-tuning of an encrypted model lands between normal fine-tuning and training from scratch rather than matching either extreme.
Limitations
- Convolutional operators (sliding windows) are excluded from the equivariance proofs.
- Column permutation offers only partial security compared with homomorphic encryption, and unauthorized fine-tuning still gets non-trivial performance.
- Bert experiments required a small 2-layer model because the padding mask in the Hugging Face implementation breaks the property.
Experimental setup
Datasets: CIFAR-10 ADE20k IMDB SNLI WebText WikiText2 CelebA
Benchmarks: CIFAR-10 ADE20k IMDB SNLI WikiText2 CelebA
Metrics: test accuracy mIoU aAcc mAcc perplexity SSIM PSNR F-SIM training loss curves FLOPs
Baselines: GN (Gaussian noise) split learning LP (low-pass filter) split learning BS (batch shuffle) Set Transformer PMA
Builds on: Set Transformer Deep Sets Split learning with shuffled embeddings (Yao et al.) ViT-Adapter
Closest papers by meaning
- Beyond the Permutation Symmetry of Transformers: The Role of Rotation for Model Fusion (ICML 2025 · similarity 0.88)
- Towards Understanding Inductive Bias in Transformers: A View From Infinity (ICML 2024 · similarity 0.86)
- REVISITING MULTI-PERMUTATION EQUIVARIANCE THROUGH THE LENS OF IRREDUCIBLE REPRESENTATIONS (ICLR 2025 · similarity 0.86)
- Permutation Equivariant Neural Networks for Symmetric Tensors (ICML 2025 · similarity 0.86)
- A Characterization Theorem for Equivariant Networks with Point-wise Activations (ICLR 2024 · similarity 0.85)
- Translation Equivariant Transformer Neural Processes (ICML 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.