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
| (1) |
| (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
| (3) | |||||
| (4) | |||||
| (5) | |||||
| (6) | |||||
| (7) |
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.
| Length | Ptr-Net | step | step | steps | steps | |||||
|---|---|---|---|---|---|---|---|---|---|---|
| glimpses | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 81% | 90% | 65% | 84% | 84% | 92% | 88% | 94% | 90% | 94% | |
| 8% | 28% | 7% | 30% | 14% | 44% | 17% | 57% | 19% | 50% | |
| 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.
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
| (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
| (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.
| Task | Orders considered | Perplexity |
|---|---|---|
| 1 | 225 | |
| 1 | 280 | |
| Easy | 2 | 225 |
| Hard | 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.