Order Matters: Sequence to Sequence for Sets

Order Matters: Sequence to Sequence for Sets asks a deceptively simple question: sequence models require you to feed elements in some order — so what happens when the data is really a set, with no natural order at all? The answer: the order you pick genuinely changes what the model learns, and there are architectures that fix this.

This page builds on Seq2Seq and Pointer Networks. Read those first if the terms “encoder-decoder” or “pointer” are new.

Why Students Should Care

• Lots of real data is set-shaped — point clouds, tags, detected objects — and pretending sets are sequences quietly hurts your model.
• The paper’s fix, attention-based order-invariant processing, is an early blueprint for what Transformers later made standard.
• It teaches a subtle general lesson: choices that look like formatting details (how you order your data) are actually part of your model design.

The Problem, in Plain English

An LSTM reads its input one element at a time, so something has to come first. But if your input is the set of points A, B, and C, feeding “A, B, C” versus “C, A, B” should not change the answer — the set is the same. In practice, it does change the answer, because the model’s hidden state depends on the order it read things.

Standard seq2seq models assume ordered sequences. But many tasks involve sets:

• Input sets: Point clouds, object collections
• Output sets: Predicted tags, detected objects
• Both: Sorting (input set → output sequence)

Naively treating sets as sequences introduces spurious ordering dependencies — the model wastes capacity learning to cope with orderings that never should have mattered.

Input Order Sensitivity

Experiment: sort numbers using seq2seq. The same set, presented in different orders, can succeed or fail:

Input Order	Output
[3, 1, 4, 2]	[1, 2, 3, 4] ✓
[1, 2, 3, 4]	[1, 2, 3, 4] ✓
[4, 3, 2, 1]	[1, 2, 3, ?] ✗

Different input orderings can lead to different (wrong) outputs — even though logically the task is identical.

Interactive Demo

Explore how input order affects set processing:

Order Matters

Set InputSequence Output

Input: Unordered set (order shouldn't matter)

5

1

3

4

6

1

9

2

Shuffle Input Order

Same set, different order → model should give same output

Read-Process-Write

Read: Embed all inputs. Process: Attention over set. Write: Generate sequence.

Permutation Invariance

Use attention to aggregate—order of input doesn't affect representation.

Applications

• Sorting: Input set → sorted sequence

• Convex hull: Points → ordered hull vertices

• Sentence ordering: Shuffled sentences → coherent paragraph

Solution: Read-Process-Write

The paper proposes a three-phase architecture. The trick: replace “read the elements in order” with “look at all elements through attention”, which is order-invariant by construction.

1. Read

Embed all input elements independently (no order involved yet):

$$\{e_1, e_2, ..., e_n\} = \text{Embed}(x_1, x_2, ..., x_n)$$

2. Process

An LSTM repeatedly attends over the whole set instead of consuming elements one by one:

$$q_t = \text{LSTM}(q_{t-1})$$ $$\alpha_i = \text{softmax}(e_i \cdot q_t)$$ $$r_t = \sum_i \alpha_i e_i$$

The weighted sum $r_t$ is the same no matter how you shuffle the elements — that is where the order-invariance comes from. Multiple processing steps refine the representation.

3. Write

Generate the output sequence with a pointer network, selecting input elements one at a time:

$$p(y_i | y_{<i}, M) = \text{Attention}(s_i, M)$$

Output Order Learning

Some tasks have output sets too — the correct answer is a collection, but the model must emit it in some order. Which order should the training data use? The paper’s answer: let the model search for the ordering that is easiest to learn:

$$\mathcal{L} = \min_{\pi \in S_n} \sum_i -\log p(y_{\pi(i)} | y_{\pi(<i)})$$

In words: among all permutations of the target output, train against the one the model currently finds most probable.

Key Results

Sorting

Model	Accuracy
Seq2seq	72%
Seq2seq + Attention	87%
Read-Process-Write	94%

Convex Hull

Sorting input points by angle dramatically improved performance — demonstrating that “natural” orderings help learning even when the task is order-free in principle.

Implications

1. Order is a hyperparameter: Choice of ordering affects learning
2. Attention enables invariance: Attention over sets removes order dependence
3. Output order matters: Some orderings are easier to learn than others

Connection to Transformers

The Read-Process-Write architecture anticipated:

• Set attention (now standard in Transformers)
• Iterative refinement (multiple attention layers)
• Permutation invariance (via attention aggregation)

A Transformer encoder without positional encodings is essentially a permutation-invariant set processor — the same core insight, scaled up.

Common Confusion

• “Order matters” — for what? The title means input/output element ordering affects seq2seq training. It is not about word order in language.
• Set vs. sequence: a sequence has meaningful positions (“first”, “second”); a set does not. The bug this paper diagnoses is feeding sets into models that assume positions mean something.
• Order Matters vs. Pointer Networks: Pointer Networks (same lead author) give models an input-sized output vocabulary; this paper studies ordering effects and uses a pointer network as its Write phase.
• Invariance from attention vs. from sorting: the paper offers two remedies — an architecture that ignores order (attention), and picking a good canonical order (e.g., sort by angle). Both work; they are different strategies.

Where To Go Next

• Read Pointer Networks for the output mechanism used in the Write phase.
• Read Seq2Seq for the baseline architecture whose assumptions this paper questions.
• Read Transformer and Attention Is All You Need to see set attention become the dominant paradigm.
• Read Bahdanau Attention for the original attention mechanism.

Key Paper

• Order Matters: Sequence to Sequence for Sets — Vinyals, Bengio, Kudlur (2015)
  https://arxiv.org/abs/1511.06391