Imagine training a neural network to look at an image of a pizza and list its ingredients: {cheese, tomato, crust, pepperoni}. Mathematically, this output is a set—the order of the ingredients does not change the nature of the pizza.
Yet, if you use a standard autoregressive Transformer or Recurrent Neural Network (RNN), you are forced to flatten this unordered set into a linear sequence during training (e.g., "cheese, tomato, crust, pepperoni"). This mismatch between the unordered nature of the data and the sequential constraints of our most powerful architectures introduces a systemic flaw known as sequential ordering bias (or false order bias).
The Core Mismatch: Sets vs. Sequences
Many fundamental machine learning problems are inherently set-prediction tasks disguised as sequence generation. Examples span across multiple domains:
- Multi-Label Classification: Assigning an unordered collection of tags to videos, images, or text (Order-Free RNN With Visual Attention for Multi-Label Classification).
- Information Extraction: Extracting a set of facts, entities, or relations from a document (A sequence-to-sequence approach for document-level relation extraction).
- Structured Data Generation: Generating combinatorial structures like graphs (Pard: Permutation-Invariant Autoregressive Diffusion for Graph Generation) or tabular features (TabStruct: Measuring Structural Fidelity of Tabular Data).
To train sequential models on these tasks, researchers typically apply arbitrary serialization heuristics, sorting target items alphabetically, by frequency, or by their order of appearance in the source text. However, forcing an artificial linear sequence onto non-sequential data introduces severe training pathologies.
Why Forced Linearization Fails
When we force a sequential structure on an unordered set, the model suffers from three distinct types of degradation:
1. The False Order Penalty
In a standard sequence-to-sequence model, the loss function evaluates predictions step-by-step at exact token positions. As Zinong Yang et al. observe in UniCOQE: Unified Comparative Opinion Quintuple Extraction As A Set, if a model correctly identifies all target elements but outputs them in a different permutation than the ground truth, the cross-entropy loss penalizes it heavily. The model is punished for content accuracy simply because it failed to guess the arbitrary sequence order chosen by the annotator.
2. Spurious Dependencies
Autoregressive models predict the next token conditioned on previously generated tokens. When forced to learn an artificial sequence, the model begins tracking spurious correlations. As Sean Welleck demonstrates in Order and Learning in Sequential Neural Structured Prediction, this constraint forces the model to learn arbitrary dependencies that do not reflect the underlying structural relationships of the objects. For instance, the model might learn that "pepperoni" must follow "cheese," creating an artificial directional bias that harms its internal representation of the data.
3. Exposure Bias and Conservatism
Because the model is penalized for exploring alternative permutations, it becomes highly conservative. Che-Ping Tsai et al. show in Order-Free Learning Alleviating Exposure Bias in Multi-Label Classification that fixed-order supervision causes models to primarily memorize and replicate exact label combinations present in the training data. This prevents the model from generalizing to novel, unseen combinations of labels at inference time.
Restoring Permutation Invariance
To eliminate sequential ordering bias, recent research focuses on making either the loss function or the model architecture permutation-invariant—ensuring that the model evaluates a set based on its holistic contents rather than its sequence.
Sequential Loss (Cross-Entropy):
Model Output: [B, A, C] <-- Heavily penalized at Step 1
Ground Truth: [A, B, C]
Permutation-Invariant Loss (Bipartite Matching):
Model Output: [B, A, C] \ /
X <-- Zero penalty (Perfect match found)
Ground Truth: [A, B, C] / \
Bipartite Matching Losses
The most direct way to bypass the sequence constraint is to decouple the loss from the output order using bipartite matching algorithms (like the Hungarian algorithm).
In Set Generation Networks for End-to-End Knowledge Base Population, Dianbo Sui et al. utilize a non-autoregressive transformer decoder paired with a bipartite matching loss. Instead of calculating loss token-by-token, the network generates all elements simultaneously, and the loss function finds the optimal one-to-one assignment between the predicted set and the ground-truth set. Similarly, Jie Cao et al. introduce OTSeq2Set: An Optimal Transport Enhanced Sequence-to-Set Model for Extreme Multi-label Text Classification, which leverages Optimal Transport to align predictions in a semantic embedding space, completely bypassing alphabetical or frequency-based sorting penalties.
Dynamic Label Alignment
If an autoregressive architecture must be used, the training paradigm can be adapted to let the model determine its own optimal generation path.
Abel Gonzalez-Garcia et al. propose this in Orderless Recurrent Models for Multi-label Classification via Predicted Label Alignment (PLA). Instead of forcing the model to match a static target sequence, PLA dynamically reorders the ground-truth labels during training to match the model's highest-confidence predictions. This approach eliminates the false order penalty and significantly reduces duplicate token generation. In a similar vein, Kechen Qin et al. develop a framework in Adapting RNN Sequence Prediction Model to Multi-label Set Prediction that defines set probability as the sum over all possible label permutations, freeing the recurrent network to discover the most natural generation order dynamically.
Parallel and Branching Decoders
Rather than flattening a set into a single concatenated string, alternative decoding topologies can handle set generation natively.
Standard Decoder: [Start] -> Item A -> Item B -> Item C -> [End]
Branching Decoder: /-> Item A -> [End]
[Start] ------> Item B -> [End]
\-> Item C -> [End]
To solve the problem of concatenating multiple text sequences, Zixian Huang et al. introduce a novel architecture in A Branching Decoder for Set Generation. Their model, One2Branch, dynamically branches the hidden states of a decoder to generate multiple target sequences in parallel. By eliminating order dependence entirely, this architectural shift prevents conflicting training signals and accelerates inference speeds. For entity extraction, Buzhou Tang et al. demonstrate in SetGNER: General Named Entity Recognition as Entity Set Generation that detecting entity components concurrently eliminates the spurious correlations learned by traditional sequence-to-sequence translation frameworks.
Why It Works: The Intuition
Shifting from sequence prediction to true set prediction works because it aligns the model's optimization objective with the mathematical reality of the data.
When a model is freed from memorizing an arbitrary output sequence, its capacity is no longer wasted on learning meaningless permutations. Instead, the self-attention mechanisms and hidden representations can focus entirely on capturing global dependencies and semantic content. By removing artificial sequence constraints, models achieve better generalization on rare item combinations, exhibit robustness to variable set sizes, and frequently benefit from massive inference speedups via parallel generation.