Not every collection has a meaningful first item, second item and third item. A set of detected objects, a collection of database rows, a bag of measurements or a point cloud can represent the same underlying information no matter how its elements are listed.
Set and permutation representation is the problem of building models that respect this fact. If order is meaningless, the model should not change its answer merely because an input serializer happened to place item B before item A.
This article continues the eduKateSingapore Representation and Tokenisation series by asking a necessary counter-question: when should a model refuse to invent sequence?
The Set Representation Route
UNORDERED ELEMENTS → ELEMENT REPRESENTATIONS → ORDER-INVARIANT OR EQUIVARIANT PROCESSING → POOLING / ATTENTION / RELATIONAL INTERACTION → SET REPRESENTATION → PREDICTION PERMUTE INPUT ORDER → SAME SET → SAME SET-LEVEL ANSWER
1. A Set Has Membership Without Sequence
The mathematical set {A, B, C} is the same set as {C, A, B}.
Any model predicting a property of the set should normally preserve that invariance.
2. Serialization Can Introduce Fake Order
Software often stores a set as an array because arrays are convenient.
The array order can then leak into the model even though the represented world has no such order.
3. Fake Order Creates Spurious Correlation
If training data always sorts products by ID, the model can learn position-specific shortcuts unrelated to product meaning.
Changing the sort order at deployment can then change predictions unexpectedly.
4. Permutation Invariance Means the Output Does Not Change
For a set-level prediction, reordering the inputs should leave the result unchanged.
This property is called permutation invariance.
5. Permutation Equivariance Is Different
If the model outputs one representation per input element, reordering the input should reorder the corresponding outputs in the same way.
The individual outputs move with their elements; the model does not invent new identities.
6. Deep Sets Formalised a General Set Architecture
Deep Sets established a widely used form for permutation-invariant functions: transform each element, aggregate the transformed elements with an order-invariant operation such as summation, then transform the aggregate.
The architectural lesson is elegant: if order should not matter, use an aggregation that mathematically cannot depend on order.
7. Sum, Mean and Max Are Invariant Pooling Operators
Adding, averaging or taking an elementwise maximum across a set gives the same result regardless of input order.
Each operator preserves different information.
8. Sum Preserves Cardinality Information Better Than Mean
Two identical elements sum to twice one element while their mean is unchanged.
If set size matters, aggregation choice matters.
9. Mean Normalises Set Size
A mean representation emphasises average element features rather than count.
This can improve comparability across differently sized sets and erase useful multiplicity.
10. Max Preserves Salient Extremes
Max pooling can capture whether any element strongly expresses a feature.
It can discard how many elements expressed that feature or how close the alternatives were.
11. Pooling Alone Can Lose Relationships
A set of points can contain shape. A set of people can contain pairwise relationships. Compressing each element independently and immediately summing can lose rich interactions.
Set models often need relational processing before final pooling.
12. Set Transformer Adds Attention Among Set Elements
Set Transformer uses attention to model interactions among elements while preserving the permutation properties required for set-structured inputs.
This allows the representation of pairwise and higher-order relationships without imposing meaningful sequence order.
13. Attention Does Not Require Semantic Order
Self-attention can compare every element with every other element even when no positional encoding is added.
Without artificial positions, the interaction can remain permutation-equivariant.
14. Positional Encoding Can Break Set Invariance
If arbitrary array positions receive learned position vectors, the model can distinguish the first serialized element from the second even when the world cannot.
Do not add coordinates where no coordinates exist.
15. This Is the Counterpart to Positional Representation
Ordered sequences need position. True sets need invariance to arbitrary ordering.
See Positional Representation.
16. Point Clouds Are Canonical Set Inputs
A 3D point cloud can be stored in any row order while representing the same sampled geometry.
PointNet-style models therefore require permutation-invariant handling of the point set.
17. Geometry Adds Relations Without Global Sequence
Points have coordinates and neighbourhoods even though they lack a natural list order.
Set invariance can coexist with spatial structure.
18. Object Detections Are Sets Too
A vision system may detect five objects in an image. The detection order is usually an implementation detail.
Downstream reasoning should use object identity, class, location and relation rather than detection-list position.
19. Database Query Results Can Be Sets
A SQL query without an ORDER BY clause does not promise semantic row ordering.
A model should not infer significance from whichever order the database happened to return.
20. Bags and Multisets Preserve Repetition
A mathematical set collapses duplicates. Many machine-learning inputs are better described as multisets where repeated elements matter.
Three identical transactions are not the same evidence as one transaction repeated in storage by accident.
21. Multiplicity Is a Representation Choice
If duplicate occurrences are meaningful, the model must preserve counts.
If duplicates are data errors, they should be deduplicated before modelling.
22. Sets Can Contain Typed Elements
A scene can contain people, vehicles and signs. A medical case can contain symptoms, medications and test results.
Type embeddings can preserve element category without imposing sequence.
23. Sets Can Contain Entities With Stable IDs
Canonical identifiers preserve which object is which across permutations.
Identity is independent of list position.
24. Pairwise Relations Can Turn a Set Into a Graph
If the relationships among elements are important and explicit, graph representation may be more natural than pure set pooling.
A set says what elements exist. A graph says how they connect.
25. Set and Graph Representations Can Coexist
A graph’s node collection is still order-independent even though edges add relational structure.
Permutation-aware graph models preserve both properties.
26. Sets Can Be Variable-Sized
One scene can contain three objects and another thirty. One patient’s record can contain two medications and another twenty.
Set architectures should handle varying cardinality naturally.
27. Padding Variable Sets Needs Masks
Batching can pad smaller sets to the size of the largest.
Padding elements must be excluded from aggregation and attention so they do not become fake set members.
28. Sorting Can Be Useful When the Sort Key Is Semantically Real
A set of transactions can be sorted by timestamp if the task becomes temporal reasoning.
At that point the representation has changed from an unordered collection into an ordered sequence under a meaningful key.
29. Order Should Be Introduced Deliberately
Sorting by time, distance, priority or score can reveal useful structure.
The crucial rule is to name what the ordering means rather than inherit arbitrary serialization order.
30. Canonical Sorting Is Not the Same as Natural Order
Alphabetically sorting a set can make files reproducible while remaining semantically arbitrary.
Canonical order can help engineering without becoming a feature the model should exploit.
31. Random Permutation Is a Useful Test
If a set model’s prediction changes materially when input order is shuffled, either the architecture is not invariant or some order-dependent feature leaked in.
Permutation testing is therefore a direct representation audit.
32. Training With Shuffled Orders Can Reduce Shortcut Learning
If a sequence model must consume set data, randomising order during training can discourage reliance on one serialization pattern.
This is a workaround, not the same guarantee as an invariant architecture.
33. Learned Sorting Can Introduce Task-Specific Order
A model can learn to rank elements by relevance before deeper processing.
That order is not intrinsic to the input set; it is an adaptive representation chosen for the task.
34. Adaptive Selection Changes Cardinality
A large set can be reduced to the most informative elements or pooled summaries.
This connects set modelling to Adaptive Tokenisation.
35. Selection Must Preserve Rare Important Elements
One unusual measurement can determine a safety diagnosis even when ninety-nine ordinary measurements dominate the set.
Pooling and pruning should not confuse frequency with importance.
36. Set-Level Explanations Need Element Attribution
If a model predicts fraud, disease risk or scene category from a set, users may need to know which elements contributed most.
Order invariance does not remove the need for provenance.
37. Hierarchical Sets Are Common
A document collection is a set of documents, each document can contain an ordered sequence. A scene is a set of objects, each object contains spatially arranged features.
Real systems often combine ordered and unordered representations at different levels.
38. The Set and Permutation Audit
- Does the input have a genuine semantic order?
- If not, can serialization order change arbitrarily?
- Should the output be permutation-invariant or permutation-equivariant?
- What aggregation operation is used?
- Does multiplicity matter?
- Are pairwise interactions important?
- Would a graph representation be more faithful?
- Are element types and identities preserved?
- How are variable set sizes batched?
- Are padding elements masked?
- Does any positional encoding introduce fake order?
- Does shuffling elements change the prediction?
- If order is introduced, what semantic key defines it?
- Can set-level outputs return to the elements supporting them?
39. What Students Should Remember
- Sets contain elements without meaningful sequence.
- Permutation invariance means set-level output is unchanged by reordering.
- Permutation equivariance means element-level outputs move with their elements.
- Deep Sets uses invariant aggregation; Set Transformer models richer element interactions.
- Adding arbitrary position can inject false structure.
- Point clouds, object detections and many query results are naturally set-like.
- Order should be introduced only when the ordering key has real meaning.
40. The Deep Principle
Sequence is powerful because order carries meaning. It is dangerous when order is only an accident of storage.
A faithful representation does not ask every collection to stand in line. When the world supplies membership without order, the model should preserve membership without inventing a story about who came first.