A set has no order — so stop secretly giving it one.
By 2015, recurrent networks had made everything look like a sequence. That was convenient, but it hid a problem: many things have no natural order at all — a set of numbers to sort, a bag of variables, an unordered collection. The moment you line such data up to feed it into a sequence model, you have chosen an order, and that choice was never neutral.
This paper's quiet heresy: order is a hidden hyperparameter nobody was tuning, and it measurably changes what a model learns. The fix is to treat a set as a set — read all its elements, then process them with an attention step whose answer does not change if you shuffle the inputs. That permutation-invariant block is the whole idea.
Feed a set in a different order and you get a different model. So build a block that cannot tell the difference.
The order trap
What goes wrong when a set is forced to be a sequence.
Step 1 · The black box
A box that sorts a set — and the input has no order to begin with.
Here is our running task, the paper's own artificial benchmark. A handful of numbers between 0 and 1 go in; the same numbers come out in sorted order. We will use this exact set of five for all ten steps:
The catch is in the very first arrow. To feed five numbers into a normal recurrent sequence-to-sequence (seq2seq) model — a network that reads one input list and writes one output list — you must lay them out in some line. But a set has no first element. Whatever line you pick, you have invented an order the data never had.
The paper asks the uncomfortable question hiding in that arrow: does the invented order matter? Steps 2 puts real numbers on the answer; the rest of the page builds a box that refuses to care.
From the abstract: “We show that the order in which we organize input and/or output data matters significantly when learning an underlying model.”
Step 2 · The evidence
Reorder the data, and the score moves — on real tasks, not just toys.
Step 1 left a suspicion: the order you invent might not be free. Here the paper cashes that suspicion into three measurements — and in all three, only the ordering changed.
“The data is unordered” does not let you off the hook. The authors take the same data, feed it in different orders, and watch the score move. Perplexity here means “how surprised the model is” (lower is better); F1 is a parsing accuracy score (higher is better).
| Task | Ordering changed | Score | Δ |
|---|---|---|---|
| Parsing a sentence into its tree | depth-first traversal | 89.5% F1 | — |
| Parsing the same trees | breadth-first traversal | 81.5% F1 | −8.0 |
| Language modeling (Penn Treebank) | natural word order | 86 perplexity | — |
| Same words, scrambled | 3-word reversal | 96 perplexity | +10 |
Read those four rows slowly. The only thing that differs within each pair is the order the model saw — same trees, same sentences. Yet writing a parse tree breadth-first instead of depth-first costs 8 points of F1, and a meaning-preserving word scramble costs 10 points of perplexity. Order is not bookkeeping; it is a knob on model quality.
Even when the order should be irrelevant — a 3-word reversal keeps every word and almost every local relation — it still hurts optimization. Order changes not just what is possible to represent, but what is easy to learn.
Numbers from the paper: depth-first vs. breadth-first parse linearizations score 89.5% vs. 81.5% F1; PTB language-model perplexity goes from 86 (natural) to 96 (3-word reversal).
Step 3 · The floor plan
If order is the disease, a permutation-blind block is the cure: Read · Process · Write.
Step 2 proved order leaks in through the input arrow. The fix is to redesign that arrow so it cannot tell one ordering from another. The paper's architecture has exactly three blocks.
Don't pretend the set is a sequence. Instead: Read every element into a memory, Process that memory with an attention step that is blind to order, and Write the output by pointing back at elements. Here is the whole machine on one slide:
m₁ … m₅
Embed each number with the same small network into a memory slot. No order is imposed — they are just five slots.
q*_T
An LSTM with no inputs reads all slots by attention, T times, boiling them into one vector that ignores order.
② ⑤ ④ …
A pointer network reads q*_T and points at input slots one at a time — the sorted output indices.
Read · Process · Write
Open each block — and meet the attention step that erases order.
Step 4 · Read
Read turns each element into a memory slot — independently, so no order sneaks in.
Step 3 named the three blocks. We open the first, Read, and notice the one design choice that already protects against order.
The Read block is the simplest thing imaginable: take each number xᵢ and pass it through the same small neural network — a multilayer perceptron (MLP), a tiny stack of fully-connected layers — to get a memory vector mᵢ. The same network for every element. After Read, the set lives as five unordered slots m₁…m₅.
Why does this matter? Because each slot is computed independently. Slot m₃ depends only on the number 0.88 — never on what sat to its left or right. So far, nothing in the model has even noticed there is an order to notice.
Step 5 · Process — the heart of the paper
Process reads the whole memory by a weighted average — and a weighted average doesn't care about order.
Step 4 gave us five slots. Now the Process block has to boil them into one summary vector — without ever lining them up. This is the single most important idea on the page, so we will compute it by hand first.
The Process block is an LSTM that takes no input. At each step it forms a query qₜ, compares that query to every memory slot to get a score, turns the scores into weights with softmax (exponentiate, then normalize so the weights sum to 1), and reads back a weighted average of the slots. Let's do one read with toy scores.
Score every slot against the query
The query qₜ compares itself to each slot mᵢ (a dot product). Say it likes the slots holding larger numbers; here are five raw scores eᵢ:
Softmax the scores into weights
Exponentiate each score and divide by the total, so the five weights add to 1. The biggest score (m₃) wins the most weight:
Read = the weighted average of the slots
The read vector rₜ is each slot times its weight, summed. It is dominated by m₃ — and crucially, this sum is the same no matter what order the slots were in.
Drag the five scores — watch softmax exponentially favor the highest, and watch the weights still sum to exactly 1
Weights sum to 1.00. The read vector is a blend of all five slots, dominated by the highest-scoring one.
JavaScript off: the bars show the worked example above — a₃ ≈ 0.59 carries the read.
What to notice: softmax turns a small score gap into a big weight gap — but every weight stays positive and the five always sum to 1. That is what makes the read a genuine, order-free average.
The formula you just did by hand — eqs. (3)–(7)
One Process step t, exactly as in the paper. Each line is one row of your worksheet:
f is a dot product. Note: permuting the mᵢ leaves rₜ unchanged.
Step 6 · Permutation invariance
Shuffle the set, and the read vector doesn't move. That's the whole point.
Step 5's read was a weighted sum: rₜ = Σᵢ aᵢ mᵢ. Addition does not care about order — 0.17·m₁ + 0.46·m₃ is the same number whichever you write first. Let's feel that directly.
A weight aᵢ rides along with its own slot mᵢ. Reorder the slots and you reorder the terms of the sum, but a sum is a sum: the total is identical. So the read vector — and therefore the Process block's final summary q*_T — is permutation invariant: blind to input order.
Hit Shuffle — the slots jump around, but the read vector below stays frozen
Read vector rₜ = Σ aᵢ mᵢ (its bars never change)
Order shown: 0.72, 0.15, 0.88, 0.43, 0.31. The read vector is identical — and so is the sorted output.
JavaScript off: imagine the chips in any order. Because the read is a sum, the vector underneath never budges.
What to notice: the chips rearrange; the orange bars do not. A vanilla seq2seq encoder — an LSTM reading left to right — would give a different vector for each order. The Process block, by construction, cannot.
“Permuting mᵢ and mi′ has no effect on the read vector rₜ.” This single sentence is why the architecture treats X as a true set — it is invariant to the order of the elements.
Step 7 · Processing steps T
One glance isn't enough — let the block re-read the set T times before deciding.
Step 6 showed one order-free read. But sorting needs more than a single glance — you might want to find the smallest, then the next. So the Process block repeats its read T times, each time using the previous state to ask a sharper question.
Each pass updates the query, attends again, and refines the running state q*. After T passes, the final state q*_T is the set's summary — still permutation invariant, but now computed with several rounds of “thinking.” How much does T matter? The sorting numbers are blunt:
| Processing steps | Sort 5 (acc.) | Sort 10 (acc.) | Sort 15 (acc.) |
|---|---|---|---|
| Vanilla seq2seq (Ptr-Net) | 90% | 28% | 4% |
| P = 0 steps (no processing) | 84% | 30% | 2% |
| P = 1 step | 92% | 44% | 5% |
| P = 10 steps | 94% | 50% | 10% |
Look at the hardest column, sorting 15 numbers. With zero processing the model gets 2% right; ten processing passes lift it to 10% — a 5× jump from the very same architecture, just allowed to re-read its memory more. “As soon as at least one processing step is allowed, the model gets better, increasing with the number of steps.”
Accuracies are out-of-sample, after 10,000 iterations, with glimpses on (Table 1 of the paper). Higher is better.
Step 8 · Write
Write points back at the set, one element per step — a pointer, not a fixed vocabulary.
Step 7 produced the summary q*_T. Now the Write block has to emit the answer — but the answer is indices into the input set, not words from a dictionary. So it uses a pointer.
A pointer network is a decoder LSTM that, at each step, runs an attention over the input slots and points at the winner — outputting that slot's index instead of a vocabulary word. The paper adds one extra attention read before each point, a glimpse, which re-checks the set first. Watch it emit the sorted order of our five numbers:
Step the pointer — each click glimpses the set, then points at the next-smallest number
Output so far (sorted)
Ready. The pointer will emit input positions in sorted order: 0.15 → 0.31 → 0.43 → 0.72 → 0.88.
JavaScript off: the pointer emits 0.15, 0.31, 0.43, 0.72, 0.88 — the input numbers in sorted order.
What to notice: the output is always one of the inputs — the model never invents a number, it only points. That is what makes it a clean answer to combinatorial set problems like sorting.
Adding glimpses (an attention read before each point) “more than doubles accuracy” in the hardest cases — for both the vanilla pointer net and Read-Process-Write. Looking before you point is worth a lot.
Results & legacy
What the numbers say, and what the idea grew into.
Step 9 · When the output is a set too
If the output has no order either, don't pick one — search over orderings while training.
So far the input was a set and the output a sequence. Step 9 closes the loop: what if the output is also a set, with no canonical order (a bag of triangles, a set of factors)? Committing to one output order is the same mistake again.
The paper's answer is to make the loss — the training objective — search over output orderings instead of fixing one. For each example, take the ordering π that the model currently finds easiest, and train on that. Over time the model and its preferred order settle together.
For each example, pick the best ordering π of the output, then maximize its likelihood. Naively this is O(n!); the paper samples orderings to make it O(1).
Does forcing one order really hurt? On a 5-gram language task where the output is the five words, fixing the natural order (1,2,3,4,5) gives 225 perplexity; fixing an arbitrary order (5,1,3,4,2) gives 280 — clearly worse. But let the model search over all 5! = 120 orderings, and it rediscovers the good orders on its own, landing back at 225.
| Output ordering | Orders considered | Perplexity |
|---|---|---|
| Fixed natural (1,2,3,4,5) | 1 | 225 |
| Fixed arbitrary (5,1,3,4,2) | 1 | 280 |
| Easy search | 2 | 225 |
| Hard search (all orders) | 5! = 120 | 225 |
From the paper (Table 2, validation perplexity, lower is better): searching even over all 120 orderings recovers the natural-order result of 225.
Step 10 · The report card
Across toys and real tasks, the same lesson holds: order is a knob, and a set deserves a set-shaped model.
We have read all three blocks and seen order leak in twice — once at the input, once at the output. Here is the whole scoreboard on one card.
Sorting accuracy — vanilla seq2seq vs. Read-Process-Write (10 numbers)
Ptr-Net, no processing
P = 5 steps + glimpses
The experiments are illustrative, not large-scale — this is conceptual groundwork. But the message is sharp and it generalizes: whenever your data is a set, the order you impose is a decision, and you are better off with a model that does not have to make it.
Can you explain it now?
Why does feeding a set in different orders change anything?
A vanilla seq2seq encoder reads left to right, so its summary depends on the order. The order is an arbitrary choice you smuggled in, and it changes both what's representable and what's easy to learn — measurably, even on real parsing and language tasks.
What makes the Process block permutation invariant?
Its read is a weighted average rₜ = Σᵢ aᵢ mᵢ. Each weight aᵢ travels with its own slot mᵢ, and a sum doesn't depend on the order of its terms. Shuffle the inputs and the read vector — and the final summary q*_T — are unchanged.
What do the T processing steps buy you?
Several rounds of attention over the same memory, refining the summary before decoding. On sorting 15 numbers, going from 0 to 10 processing steps lifts accuracy from 2% to 10% — same architecture, more re-reading.
How does the Write block output an answer?
A pointer network: at each step it attends over the input slots and points at one, emitting that slot's index rather than a dictionary word. A “glimpse” attention before each point more than doubles accuracy in the hardest cases.
What if the output is a set with no order?
Don't fix an order — make the loss search over output orderings and train on the one the model finds easiest. Over all 5! = 120 orderings of a 5-gram task it recovers the natural-order perplexity of 225, beating a fixed arbitrary order's 280.
In one sentence, what did this paper change?
It promoted “ordering” from invisible bookkeeping to a first-class modeling decision, and gave the first principled recipe — Read-Process-Write — for inputting and outputting sets as sets.
“We show that the order in which we organize input and/or output data matters significantly when learning an underlying model, despite the fact that many architectures … are agnostic to this order.” — Vinyals, Bengio & Kudlur, 2015
The line that taught models to respect sets.
This paper was the conceptual seed, not the finished tool. Its question — “how do you put a set into a model?” — became a small field, and its authors carried the attention-and-pointer machinery straight into the architectures that followed.
Deep Sets
Formalized permutation-invariant functions as “pool the elements, then map” — the same sum-over-elements trick, proved to be the general form.
Set Transformer
Replaced the Process LSTM with stacked self-attention over the set, scaling the read-a-set idea up to a full attention-based set encoder.
Pointer Networks → attention
The pointer and glimpse mechanisms here fed directly into the broader attention work the same authors pushed toward modern seq2seq.
The next time you reach for a sort, a deduplication, or a model that eats an unordered collection, you are standing on the idea this page just taught: a set is not a sequence, so don't make it pretend to be one.