LLM + RoboticsUnit 3 · The Transformer era · Day 16

Order Matters: Sequence to Sequence for Sets

Seq2seq models care about the order you feed them, even when the data has no natural order. This paper measures that, then shows how to read a set without caring about order.

AuthorsOriol Vinyals, Samy Bengio, Manjunath Kudlur
Year / venue2015 arXiv · ICLR 2016
Core ideaOrder-invariant set encoding; learn the output order
Study time3–4 h

Original: arXiv:1511.06391 · Code, notebook and exercises: 30u30 Day 16

Start here (no maths needed)

Some things are just a group with no real order, like the toys on a table, and a computer should give the same answer however that group is listed.

Think of it like this

Your shopping list "milk, eggs, bread" is the same list as "bread, milk, eggs". But if a friend reads it one item at a time, the order can still change what they remember best. This paper shows that computers that read one item at a time have the same problem. It then builds a reader that looks at the whole group at once, so the order stops mattering. It also shows that when the computer has to give its answer one item at a time, some orders are easier to learn, just like packing a bag is easier if the heavy things go in first.

How it works

  1. Read: turn each item into a note, using the same method for every item.
  2. Process: a "thinker" looks over all the notes at once, several times, using attention. Because it mixes everything together, shuffling the items doesn't change its result.
  3. Write: it answers by pointing at items one at a time, for example from smallest to largest.
  4. When the answer itself is a group, the computer is allowed to learn which order of answers is easiest, instead of being forced into one.

Why robots care

A robot's camera might list the objects on a table as "cup, apple, toy" one time and "toy, cup, apple" the next. The robot should make the same choice either way. And when clearing the table, it has to pick an order: taking the top box off a stack first is much easier than pulling out the bottom one.

Try it

Words to know

Set
A group of things where order doesn't matter.
Sequence
A list where order does matter, like the words in a sentence.
Order-invariant
Gives the same answer no matter how the input is shuffled.
Read, Process, Write
The three parts of this paper's model: take in, think, answer.
Pointer
Answering by picking one of the input items.

Going deeper: everything below is the full version, with some maths. On a first read, skim the headings and the "Why it matters for robotics" box, and come back for the rest later.

1. Summary

TL;DR

An LSTM encoder reads its input one element at a time, so the order of the input shapes what it learns. That is fine for sentences and wrong for sets, like "the numbers to sort" or "the objects on the table". The paper makes three points. First, ordering choices change results even when, in theory, they shouldn't. Second, a Read–Process–Write model with content-based attention can encode a set so that shuffling it changes nothing. Third, when the output is a set, you can let the model search for the order that is easiest to produce during training.

2. The core idea

Given memories m_1 … m_n (one per set element, from the Read block), the Process block runs for t = 1 … T:

q_t   = LSTM(q*_{t−1})               # query, from the previous step
e_i,t = f(m_i, q_t)                  # score each memory, e.g. dot product
a_i,t = exp(e_i,t) / Σ_j exp(e_j,t)   # attention weights
r_t   = Σ_i a_i,t · m_i               # readout
q*_t  = [q_t ; r_t]                   # next LSTM state input

For outputs that are sets, the paper trains with the best ordering instead of a fixed one:

θ* = argmax_θ  Σ_i  max_π  log p( Y_π(X_i) | X_i ; θ )

Searching all n! orderings is impossible, and picking the max greedily from the start locks in a random early choice. The fix: pretrain with uniformly random orderings, then sample orderings in proportion to their probability under the model.

3. Deep dive

Evidence that order matters

In principle the chain rule works in any order. In practice the optimiser and the LSTM's inductive bias prefer some orders. That's the paper's main warning.

The sorting experiment

Task: sort N random numbers between 0 and 1, outputting indices. The baseline reads the numbers into an LSTM, then points. Read–Process–Write replaces that LSTM with the attention-based Process block. For N = 10 the baseline sorted 8% of test sets correctly (28% with "glimpses", an extra attention read before each pointer step). With 5 processing steps and glimpses, Read–Process–Write reached 57%. With zero processing steps it was mostly worse than the baseline: the set embedding needs some computation. All models struggled at N = 15 (10% at best).

Interactive: a sequential encoder vs an attention readout

Six numbers in [0, 1], drawn in their current order. A toy RNN (h ← tanh(0.9h + 2x − 1)) reads them left to right. A toy Process block attends over embeddings m_i = (cos πx, sin πx) for T steps, with a fixed update standing in for the LSTM. Shuffle: the RNN state changes, the readout does not. Bar height is x; the green bar fill shows the last step's attention weight.

RNN final state
–
Readout r (x, y)
–
Shuffles so far
0

Where this went

Read–Process–Write is a small attention model over a set with no positional information. The Transformer encoder (Day 13) without positional encodings has the same property: self-attention is permutation-equivariant, and a pooled output is invariant. Later set models (Deep Sets, Set Transformer) and object-centric models build on that. Removing positional encoding is a deliberate choice in long-context models too: see NoPE in Module 05, where order comes from elsewhere. Relation Networks (Day 19) treat objects as a set in a different way: by summing over all pairs.

4. Why it matters for robotics

5. How to study it

  1. Read sections 2–4 of the paper for the model, then section 5 on output ordering. Table 1 (sorting) is the key result.
  2. In the 30u30 Day 16 folder, read implementation.py and identify the Read, Process and Write parts. Then run train.py.
  3. Write a test: shuffle the input set and confirm the Process output is identical to floating-point precision.
  4. Do exercises 1–5, and use visualization.py or the notebook to plot attention over the set.
  5. Note: write-ups of this paper sometimes mix in Pointer Network results (convex hull, TSP). Those belong to Day 18. Keep the original's tables as your reference.

6. Self-check

Why is the Process block's output unchanged when the input set is shuffled?

The only path from memories to the LSTM is the readout r_t, a weighted sum whose weights depend only on each memory's content. Reordering the terms of a sum doesn't change it.

Why did Read–Process–Write with zero processing steps mostly do worse than the LSTM baseline?

With no processing steps the writer gets no real summary of the set before it starts pointing. The set embedding needs at least one round of attention to be useful.

If the chain rule works for any order, why does output order matter?

Because learning is not exact. Some factorisations are much easier for an LSTM to fit and for SGD to find. The paper shows big gaps, like 89.5% vs 81.5% F1 for two parse-tree orders.

Why not just take the max over orderings from the first step of training?

The untrained model's favourite ordering is arbitrary, and training on it reinforces it. Pretraining on uniformly random orders, then sampling orders by model probability, avoids locking in a bad choice.

What property does a Transformer encoder share with the Process block?

Without positional encodings, self-attention treats its input as a set: permuting the inputs permutes the outputs the same way, and any pooled summary is unchanged.

7. Further reading