Literature
Display
← All papers

Order Matters: Sequence to Sequence for Sets

Oriol Vinyals · Samy Bengio · Manjunath Kudlur

· ICLR 2016 ↗

Contents

At a glance

Sequence models can represent the same distribution in many orders, but finite models and their optimization do not treat those orders equally. This paper proposes a permutation-invariant encoder for input sets and a training procedure that searches over output orders. Sorting, language, parsing, and synthetic graphical-model experiments illustrate both the benefits and remaining difficulty.

1 Introduction

A set of objects has no intrinsic sequence, and a tree can be serialized in several ways. Choosing an arbitrary order changes what the model must learn. The paper separates two questions: how to encode a set without depending on its presentation, and how to choose a useful order for generating a structured output.

2 Related Work

The approach builds on sequence-to-sequence learning, external memories, and differentiable attention. It retains autoregressive factorization to model output dependencies, rather than imposing conditional independence or requiring a supplied input tree.

3 Neural Networks for Sequences and Sets

The probability chain rule is valid for any ordering, but a trainable RNN may find some factorizations easier. A sequence can also be represented as an unordered set of token–position pairs, preserving its original information. This distinction lets the experiments change computational order without necessarily changing the modeled object.

Equations 1–2
P⁡(Y|X)=∏t=1TP⁡(yt|y1,y2,…,yt−1,X)P(Y|X)=\prod_{t=1}^{T}P(y_{t}|y_{1},y_{2},\ldots,y_{t-1},X)
hs=fe​n​c​(hs−1,xs)h_{s}=f_{enc}(h_{s-1},x_{s}) (1)
g1\displaystyle g_{1} =\displaystyle= hs\displaystyle h_{s}
gt\displaystyle g_{t} =\displaystyle= fd​e​c​(gt−1,yt−1)\displaystyle f_{dec}(g_{t-1},y_{t-1})
P⁡(yt|y1,y2,…,yt−1,X)=softmax​(affine​(gt)).P(y_{t}|y_{1},y_{2},\ldots,y_{t-1},X)=\mbox{softmax}(\mbox{affine}(g_{t}))\;. (2)

4 Input Sets

A set encoder should be unchanged when input elements are permuted. Pooling embeddings satisfies that condition but compresses everything into a fixed-size vector. The proposed model instead stores one memory vector per element and repeatedly attends to this growing memory.

4.1 Input Order Matters

Prior translation and parsing results improved when input sentences were reversed, while angle-sorting points made hull learning easier. These changes suggest that optimization and useful inductive biases matter even when representational capacity is nominally sufficient; they do not imply one universal best ordering.

4.2 Attention Mechanisms

An input-free LSTM updates a query, scores all memory vectors, and reads their weighted sum. Permuting the memory leaves this read unchanged because scores and values move together. Repeating the read provides several processing steps before decoding.

Equations 3–7
qt\displaystyle q_{t} =\displaystyle= L​S​T​M​(qt−1∗)\displaystyle LSTM(q^{*}_{t-1}) (3)
ei,t\displaystyle e_{i,t} =\displaystyle= f⁡(mi,qt)\displaystyle f(m_{i},q_{t}) (4)
ai,t\displaystyle a_{i,t} =\displaystyle= exp⁡(ei,t)∑jexp⁡(ej,t)\displaystyle\frac{\exp(e_{i,t})}{\sum_{j}\exp(e_{j,t})} (5)
rt\displaystyle r_{t} =\displaystyle= ∑iai,t​mi\displaystyle\sum_{i}a_{i,t}m_{i} (6)
qt∗\displaystyle q^{*}_{t} =\displaystyle= [qt​rt]\displaystyle[q_{t}\ r_{t}] (7)
Original figure
Figure 1:The Read-Process-and-Write model.

4.3 Read, Process, Write

Read independently embeds every element; Process repeatedly attends over these embeddings; Write uses a pointer decoder to output input positions. An additional attention read before each pointer prediction is called a glimpse. Shared element embeddings and symmetric attention make the initial set representation permutation-invariant.

4.4 Sorting Experiment

On sorting random numbers, processing steps and decoder glimpses improve complete-sequence accuracy. For ten elements, five processing steps with one glimpse reach 57%, versus 28% for the pointer baseline with a glimpse. Fifteen elements remain difficult: the best table entry is only 10%. More computation helps, but the model does not learn a consistently exact sorting procedure.

Table 1:The sorting experiment: out-of-sample sorting accuracy for various problem sizes and processing steps, with or without glimpses. All the reported accuracies are shown after reaching 10000 training iterations, at which point all models had converged but none overfitted. Higher is better.
LengthNN Ptr-Net P=0P=0 step P=1P=1 step P=5P=5 steps P=10P=10 steps
glimpses 0 1 0 1 0 1 0 1 0 1
N=5N=5 81% 90% 65% 84% 84% 92% 88% 94% 90% 94%
N=10N=10 8% 28% 7% 30% 14% 44% 17% 57% 19% 50%
N=15N=15 0% 4% 1% 2% 0% 5% 2% 4% 0% 10%

5 Output Sets

An autoregressive output model must choose a generation order even when the desired object is unordered. The following experiments test the practical consequences of that choice.

5.1 Output Order Matters

The experiments vary output order while preserving the underlying prediction task. They test whether representational equivalence also produces equal learning behavior.

5.1.1 Language Modeling

Penn Treebank language models achieve validation perplexity 86 in either natural or reversed word order. Reversing words within each three-word block raises perplexity to 96 and also worsens training fit. Disrupting useful local structure therefore makes the same distribution harder for this model to learn.

5.1.2 Parsing

A parsing decoder using depth-first tree serialization achieves 89.5% F1, compared with 81.5% for breadth-first serialization. Invalid trees make the latter number potentially optimistic. Figure 2 preserves both encodings so the changed prediction dependencies are visible.

Original figure
Figure 2:Depth first and breadth first linearizations of a parse tree which shows our different setups for output ordering in the parsing task.

5.1.3 Combinatorial Problems

Equivalent tours, triangle sets, or ranked elements can have factorially many serializations. Randomizing these representations forces a model to spread probability over equivalent answers and slows learning. Canonical output conventions improved the authors’ earlier combinatorial experiments, illustrating the statistical cost of unnecessary symmetry.

5.1.4 Graphical Models

Synthetic star-shaped graphical models reveal the shared parent variable first or last. Large datasets or nearly deterministic distributions reduce the ordering difference; with limited data and uncertainty, generating the parent first is easier. The experiment isolates a setting where the dependency structure suggests a useful factorization.

Equation 8
P⁡(y1,y2,…,yT)=∏t=1TP⁡(yt|y1,y2,…,yt−1)P(y_{1},y_{2},\ldots,y_{T})=\prod_{t=1}^{T}P(y_{t}|y_{1},y_{2},\ldots,y_{t-1}) (8)

5.2 Finding Optimal Orderings while Training

Training maximizes likelihood over both model parameters and an output permutation. A greedy maximum can lock onto an early arbitrary order, so the authors first train with a uniform ordering prior, then sample orders in proportion to their current likelihood. Ancestral sampling avoids enumerating all permutations, but this remains an approximate non-convex search.

Equation 9
θ⋆=arg⁡max⁡∑iθ⁡maxπ⁡(Xi)⁡log⁡p⁡(Yπ⁡(Xi)|Xi;θ)\theta^{\star}=\arg\max_{\theta}\sum_{i}\max_{\pi(X_{i})}\log p(Y_{\pi(X_{i})}|X_{i};\theta) (9)

5.2.1 5-gram Modeling

For isolated five-word windows, natural ordering yields perplexity 225 while a chosen awkward ordering yields 280. Searching among either two orders or all 120 permutations recovers 225, typically settling on natural, reverse, or nearby orders. This demonstrates recovery of useful orderings on a small problem; it does not establish scalable optimal ordering for arbitrary structured outputs.

Table 2: Experiments in which the model finds the optimal ordering of a set for the 5-gram language modeling task. Perplexities are reported on the validation set (lower is better).
Task Orders considered Perplexity
(1,2,3,4,5)(1,2,3,4,5) 1 225
(5,1,3,4,2)(5,1,3,4,2) 1 280
Easy 2 225
Hard 5!5! 225

6 Conclusion

The work treats ordering as a modeling choice with measurable consequences. Attention supplies a principled set encoder, while sampled order search can reduce output-order dependence. Stronger guarantees and performance on larger sets remain outside the demonstrated results.

Acknowledgments

The authors acknowledge discussions with the Google Brain team and feedback from reviewers.

Concept demonstration

Open image ↗