When we feed data into modern deep learning architectures like Transformers or LSTMs, we implicitly assume that the order of the input matters. In natural language, changing the order of words completely alters the meaning of a sentence. In computer vision, shuffling the pixels of an image destroys its spatial coherence. Consequently, our most powerful models are fundamentally optimized to be sensitive to sequence and position.
However, a vast amount of the world's data does not care about order. Consider a relational table: if you swap the first two rows or shuffle the columns, the underlying information remains exactly the same. The same is true for chemical reactions (the order in which you list the reactants doesn't change the mixture), multi-agent systems (a group of players on a court), or ad-hoc microphone arrays. These data structures are fundamentally sets, meaning they are inherently permutation-invariant.
When we force these unordered structures into sequence-based models—a process known as linearization—we introduce a severe structural mismatch. This article explores why sequence models suffer from permutation sensitivity, how they exploit arbitrary ordering as a brittle shortcut, and the architectural and training mechanisms researchers are using to enforce true permutation invariance.
The Structural Mismatch of Linearization
To process structured data like tables with a Large Language Model (LLM), the standard practice is to flatten the two-dimensional grid into a one-dimensional string of text (e.g., using comma-separated values or HTML tags). As Fang et al. note in their survey on tabular LLMs, this design choice forces sequence-based models to treat tabular inputs as ordered sequences rather than order-invariant sets.
This mismatch introduces significant representation biases. As Tsai et al. point out, because tables have no inherent column order, a naive sequential processing approach causes the model to incorrectly learn patterns based on arbitrary feature positioning. For instance, if a model is trained on data where the "Age" column always precedes the "Income" column, its internal attention weights become bound to that specific spatial arrangement. If the columns are flipped, the model's performance can collapse entirely, even though the semantic content is identical.
This issue extends far beyond tabular data. In chemical machine learning, molecules are frequently serialized into text strings called SMILES. Jiang demonstrates that sequence-based chemical models frequently suffer from a lack of permutation invariance, where simply altering the order in which reactants are listed in the text string changes the model's prediction of reaction yield or practicality. Similarly, Guo shows that sequence-based representations of data columns introduce strict input length limitations and arbitrary row-ordering sensitivities that prevent models from capturing the true global information of a dataset.
Why Sequence Models Fail the Shuffle Test
To understand why this happens, we have to look at how Transformers and sequence models handle position.
Transformers use positional encodings to inject the order of tokens into the self-attention mechanism. If you pass a table through a standard Transformer, the token in the first cell gets a positional embedding of $P_1$, the second gets $P_2$, and so on. As Dash et al. explain, this means that standard positional embeddings assign entirely different values to identical cells based purely on their row or column index. When the table is shuffled, the mathematical representations of the cells change completely, preventing the model from recognizing the structural equivalence.
Because sequence models are highly expressive, they quickly learn to rely on these arbitrary positional cues as "shortcuts" rather than learning deep semantic relationships. In a systematic study of Table Question Answering (QA) robustness, Zhao et al. created ROBUT, a benchmark of adversarial perturbations. They discovered that state-of-the-art models rely heavily on brittle shortcuts like specific row orders or exact header matches. When these elements are shuffled, model performance degrades significantly.
Standard Linearization (Order-Sensitive):
[Row 1, Col 1] (Pos 1) -> [Row 1, Col 2] (Pos 2) -> [Row 2, Col 1] (Pos 3)
*Result: Shuffling rows changes the positional embeddings and breaks the model.*
Permutation-Invariant Strategy:
[Row 1, Col 1] (Coord: R1, C1) <--> Unordered Set Relations <--> [Row 2, Col 1] (Coord: R2, C1)
*Result: Shuffling preserves coordinate identities and set relations.*
This reliance on non-semantic, positional cues is a systemic vulnerability. Mudrakarta et al. used attribution techniques to show that neural architectures regularly develop dependencies on the arbitrary layout of input data. When faced with logically equivalent but structurally rearranged inputs, they fail because their internal attention distributions are anchored to fixed sequence positions rather than invariant concepts. This behavior is also visible in text processing; Grenander et al. showed that extractive summarization models suffer severe performance drops when document sentences are shuffled, proving they over-rely on the expected information hierarchy (lead bias) rather than content saliency.
Architectural Remedies: Graph and Hypergraph Modalities
If the root cause of permutation sensitivity is the one-dimensional nature of text serialization, the most direct solution is to change the input modality itself. Instead of flattening structured data into a string, researchers are designing architectures that treat tables and sets as graphs or hypergraphs.
In a graph, nodes represent entities (like cells or features) and edges represent relationships. Crucially, graph topology is completely independent of how the nodes are indexed or ordered in memory. Chen et al. introduced this concept to tabular data with HyTrel, a framework that views tables as hypergraphs. Cells are treated as nodes, while entire rows and columns are treated as hyperedges. By encoding tables through this geometric structure, the model explicitly enforces the rule that reordering rows or columns cannot change the underlying representation.
Taking this a step further, Li et al. proposed TAMO, a framework that treats tables as a distinct modality altogether—akin to images or audio. Rather than forcing an LLM to read a table as text, TAMO uses a structural hypergraph encoder to preserve the table's geometric semantics. This ensures that the model's reasoning remains perfectly consistent regardless of physical layout changes, yielding massive performance boosts on complex reasoning tasks.
This shift to graph-based inductive biases is a recurring theme across domains:
- Biological Communities: Ruaud leverages Graph Neural Networks (GNNs) to model microbial communities. Because the sequence of species in a dataset is arbitrary, the permutation invariance of GNNs allows the model to generalize to larger, unseen communities where sequence-based models fail.
- Chemical Reactions: Shi et al. developed ReaDISH, which models chemical reactions by isolating changing molecular fragments and mapping their interactions as an unordered set, eliminating the reactant-order sensitivity that plagues text-based SMILES models.
Mathematical Invariance via Symmetric Pooling and Encodings
When changing the entire architecture to a graph is impractical, researchers instead modify the mathematical operations inside sequence models to guarantee invariance. This is typically achieved through two methods: coordinate-based positional encodings or commutative aggregation layers.
Instead of standard sequential positional encodings ($1, 2, 3...$), Dash et al. introduced the PI (Permutation Invariant) Strategy for Transformers. The PI strategy decouples the encoding from the sequence index. Instead, it assigns multi-dimensional coordinates that identify an element's structural role (e.g., its specific row and column intersection) without imposing a directional order. Because the attention mechanism treats these coordinates as attributes rather than sequence steps, the model becomes indifferent to cell ordering.
Alternatively, models can use mathematical operations that are inherently commutative—meaning the outcome is identical regardless of input order (such as $A + B = B + A$). Yoon et al. utilized this in DeepCCI for predicting chemical-chemical interactions. To ensure that predicting the interaction between Chemical A and Chemical B yields the exact same result as Chemical B and Chemical A, they pass both inputs through a shared network and merge their representations using a sum-based pooling layer. Because addition is commutative, the model is mathematically guaranteed to be symmetric.
A similar principle applies to physical sensors. Yemini et al. designed a speech dereverberation network that works with an arbitrary number of microphones in any spatial arrangement. By utilizing Deep Symmetric Sets layers, the network processes the microphone inputs as an unordered set rather than a rigid vector, allowing users to add, remove, or rearrange microphones without degrading the model's performance.
Training and Augmentation for Order Agnosticism
When working with frozen, off-the-shelf language models, architectural modifications are not an option. In these scenarios, researchers turn to specialized training objectives and data augmentation frameworks to force models to unlearn their positional biases.
The simplest approach is permutation augmentation. As Ampomah et al. demonstrate in table-to-text generation tasks, sequence-to-sequence models are highly prone to hallucinating or misattributing facts if column orders change. By explicitly shuffling the input data layouts during training, the model is prevented from memorizing specific sequence shortcuts, forcing it to learn the invariant relationships between data points instead.
Training with Permutation Augmentation:
Step 1: Train on [Name | Age | Job] -> Learn semantic links
Step 2: Train on [Job | Name | Age] -> Penalize positional shortcuts
Step 3: Train on [Age | Job | Name] -> Enforce layout robustness
Beyond simple shuffling, researchers also inject order-agnostic reasoning directly into the pre-training phase. Zhao et al. introduced ReasTAP, a method that injects table reasoning skills into language models using synthetic examples. By pre-training models on millions of auto-generated questions that require operations like sorting, counting, and comparing across randomized layouts, they break the model's reliance on physical row/column shortcuts. This pre-training forces the model to develop a robust, logical understanding of how headers bind to cell values, independent of their sequence position.
Ultimately, building permutation invariance into our models is a prerequisite for true generalization. Whether achieved through graph-based modalities, commutative mathematical layers, or adversarial training, forcing models to ignore the arbitrary order of presentation allows them to capture the stable, invariant structure of the real world.