We typically think of Transformers as sequence processors because of their massive success in natural language processing. However, mathematically, the core mechanism of a Transformer—self-attention—is entirely order-agnostic.
If you pass a collection of vectors into a standard self-attention layer, the output for any given vector depends solely on its content and its pairwise relationships with the other vectors, not on its position in the input matrix. The only reason Transformers can process language sequentially is that we explicitly inject positional encodings. When we intentionally omit or modify these encodings, we unlock an architecture natively optimized for sets, tables, graphs, and distributions.
The Hidden Symmetry of Self-Attention
To understand why this works, consider the self-attention operation. Given an input matrix $X$, the layer computes Queries ($Q$), Keys ($K$), and Values ($V$) via linear transformations, and then computes:
$$\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V$$
If you shuffle the rows of $X$, the rows of $Q$, $K$, and $V$ are permuted in the exact same way. Because the matrix multiplication $QK^T$ computes all pairwise dot products, the resulting attention weight matrix simply shuffles its rows and columns symmetrically. The final multiplication with $V$ ensures that the output matrix is permuted identically to the input.
This property is known as permutation equivariance. As Kim et al. demonstrated, standard Transformers can be viewed as a direct generalization of classical set-processing models like DeepSets. Instead of using static pooling operations (like sum or max) to aggregate set elements, the Transformer uses dynamic, data-dependent self-attention to let elements route information to one another.
Eliminating Spurious Order in Tabular Data
Tabular data is a prime example of a structure that lacks a natural sequence. The columns (features) and rows (records) of a database table can be shuffled arbitrarily without changing the underlying meaning of the data. Yet, traditional deep learning models often force tabular data into fixed-order vectors or sequential strings.
Wang et al. and Ye et al. argue that forcing tabular data into sequential architectures causes models to learn "spurious dependencies"—artificial patterns based entirely on the physical arrangement of columns. By removing positional encodings, the Transformer treats features as an unordered set, aligning the network's internal physics with the structural reality of tables (van Breugel et al.).
Standard Transformer (Sequential Bias):
[Feature A] -> Position 1 \
[Feature B] -> Position 2 -> Model learns arbitrary order dependencies
[Feature C] -> Position 3 /
Permutation-Invariant Transformer (Set-Based):
{ Feature B, Feature C, Feature A } -> Self-Attention -> Order-independent representations
Alternatively, instead of removing encodings entirely, Dash et al. introduced a uniform position-encoding strategy where all data cells share an identical starting position relative to their headers, neutralizing sequential bias. For non-textual metadata, Yunqing Xia omits positional embeddings entirely to prevent the model from inventing relationships between independent attributes like age, income, or gender.
Scaling to Higher-Order Symmetries
Permutation invariance means the final output is unchanged by reordering the input (e.g., classifying a graph regardless of node ordering). Permutation equivariance means that if you shuffle the inputs, the intermediate representations shuffle in the exact same way.
Xu et al. proved that this mathematical equivariance holds true not just for the forward pass, but also across the backward propagation pass for both token sequences and internal feature dimensions. This allows for gradient descent and model optimization to be performed directly on shuffled or encrypted data without losing convergence accuracy.
This property is vital for combinatorial optimization, where Tian et al. showed that the permutation equivariance of attention layers allows models trained on short sequences to generalize seamlessly to much longer ones. Similarly, in wireless communications, Pratik et al. utilized self-attention to ensure that a model's output is equivariant to the arbitrary indexing of transmitters, preventing the network from memorizing specific channel orderings.
In-Context Bayesian Inference and Meta-Learning
Beyond tables and graphs, an entire dataset can be framed as an unordered set of data points. This insight enables Transformers to perform meta-learning and complex statistical inference in a single forward pass.
Müller et al. introduced Prior-Data Fitted Networks (PFNs), which remove positional encodings to feed pairs of inputs and labels as an unordered collection. Because the architecture is strictly permutation invariant with respect to the samples, it treats the data as an exchangeable set, allowing the network to approximate complex Bayesian posteriors instantly.
Input Dataset: {(x1, y1), (x2, y2), (x3, y3)}
│
▼ (No Positional Encodings)
┌──────────────────────┐
│ Transformer Encoder │ ◄── Permutation Invariant
└──────────────────────┘
│
▼
Exact Bayesian Posterior Prediction
Expanding on this paradigm, Jannik Kossen demonstrates that applying self-attention directly between different datapoints allows deep models to reason across an entire dataset as an unordered set of related examples. This set-based formulation ensures query independence and sequence-agnostic predictions, a property also leveraged by Maraval et al. for end-to-end meta-Bayesian optimization.
Why It Works: The Logic of Global Counting
Why is the permutation-invariant Transformer so effective at processing sets compared to traditional pooling methods? The answer lies in the expressivity of the attention mechanism.
Chiang et al. mathematically characterized the expressivity of Transformer encoders, showing that their fundamental mechanism is the ability to perform global counting and simultaneous comparison of input features. While a simple average or max-pooling layer collapses a set into a static summary vector, self-attention allows every element in the set to dynamically query every other element.
Whether aggregating arbitrary medical codes within a single clinical visit (Cui et al.), analyzing unordered gene expressions (Yang et al.), or processing sparse market observations (Yongxin Yang), stripping the positional constraints allows the Transformer to compute rich, context-aware representations of relational structures without imposing an artificial order.