# Discovering Non-monotonic Autoregressive Orderings with Variational Inference

arXiv: https://arxiv.org/abs/2110.15797 · HTML: https://mlsanity.com/paper/2110.15797/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 48 of its 75 references that are in the map.
- First posted on arXiv 27 Oct 2021.

## Builds on (most cited first, 30 of 48)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1312.6114/) (2013)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [CIDEr: Consensus-based Image Description Evaluation](https://mlsanity.com/paper/1411.5726/) (2014)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [Show, Attend and Tell: Neural Image Caption Generation with Visual Attention](https://mlsanity.com/paper/1502.03044/) (2015)
- [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018)
- [Effective Approaches to Attention-based Neural Machine Translation](https://mlsanity.com/paper/1508.04025/) (2015)
- [Deep Visual-Semantic Alignments for Generating Image Descriptions](https://mlsanity.com/paper/1412.2306/) (2014)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Show and Tell: A Neural Image Caption Generator](https://mlsanity.com/paper/1411.4555/) (2014)
- [Conditional Image Generation with PixelCNN Decoders](https://mlsanity.com/paper/1606.05328/) (2016)
- [Sequence-Level Knowledge Distillation](https://mlsanity.com/paper/1606.07947/) (2016)
- [Non-Autoregressive Neural Machine Translation](https://mlsanity.com/paper/1711.02281/) (2017)
- [A Neural Attention Model for Abstractive Sentence Summarization](https://mlsanity.com/paper/1509.00685/) (2015)
- [MADE: Masked Autoencoder for Distribution Estimation](https://mlsanity.com/paper/1502.03509/) (2015)
- [Order Matters: Sequence to sequence for sets](https://mlsanity.com/paper/1511.06391/) (2015)
- [Levenshtein Transformer](https://mlsanity.com/paper/1905.11006/) (2019)
- [Learning Latent Permutations with Gumbel-Sinkhorn Networks](https://mlsanity.com/paper/1802.08665/) (2018)
- [PixelSNAIL: An Improved Autoregressive Generative Model](https://mlsanity.com/paper/1712.09763/) (2017)
- [Insertion Transformer: Flexible Sequence Generation via Insertion Operations](https://mlsanity.com/paper/1902.03249/) (2019)
- [Stochastic Optimization of Sorting Networks via Continuous Relaxations](https://mlsanity.com/paper/1903.08850/) (2019)
- [Recurrent Neural Network Grammars](https://mlsanity.com/paper/1602.07776/) (2016)
- [Neural Machine Translation: A Review and Survey](https://mlsanity.com/paper/1912.02047/) (2019)

## Built on by (most cited first, 15 of 15)

- [Simple and Effective Masked Diffusion Language Models](https://mlsanity.com/paper/2406.07524/) (2024)
- [The pitfalls of next-token prediction](https://mlsanity.com/paper/2403.06963/) (2024)
- [Generative Flow Networks for Discrete Probabilistic Modeling](https://mlsanity.com/paper/2202.01361/) (2022)
- [Path Planning for Masked Diffusion Model Sampling](https://mlsanity.com/paper/2502.03540/) (2025)
- [Training and Inference on Any-Order Autoregressive Models the Right Way](https://mlsanity.com/paper/2205.13554/) (2022)
- [A Survey on Parallel Text Generation: From Parallel Decoding to Diffusion Language Models](https://mlsanity.com/paper/2508.08712/) (2025)
- [Improving Discrete Diffusion Unmasking Policies Beyond Explicit Reference Policies](https://mlsanity.com/paper/2510.05725/) (2025)
- [Planner Aware Path Learning in Diffusion Language Models Training](https://mlsanity.com/paper/2509.23405/) (2025)
- [Discrete Diffusion Language Model for Efficient Text Summarization](https://mlsanity.com/paper/2407.10998/) (2024)
- [Leveraging Recursive Gumbel-Max Trick for Approximate Inference in Combinatorial Spaces](https://mlsanity.com/paper/2110.15072/) (2021)
- [BLens: Contrastive Captioning of Binary Functions using Ensemble Embedding](https://mlsanity.com/paper/2409.07889/) (2024)
- [TUBE: Tangent Upper Bound on Evidence for Discrete Diffusion Language Models](https://mlsanity.com/paper/2605.24292/) (2026)
- [Variational Learning for Insertion-based Generation](https://mlsanity.com/paper/2606.02133/) (2026)
- [Towards Improving the Generation Quality of Autoregressive Slot VAEs](https://mlsanity.com/paper/2206.01370/) (2022)
- [Distilling Specialized Orders for Visual Generation](https://mlsanity.com/paper/2504.17069/) (2025)

## Abstract (arXiv)

The predominant approach for language modeling is to process sequences from left to right, but this eliminates a source of information: the order by which the sequence was generated. One strategy to recover this information is to decode both the content and ordering of tokens. Existing approaches supervise content and ordering by designing problem-specific loss functions and pre-training with an ordering pre-selected. Other recent works use iterative search to discover problem-specific orderings for training, but suffer from high time complexity and cannot be efficiently parallelized. We address these limitations with an unsupervised parallelizable learner that discovers high-quality generation orders purely from training data -- no domain knowledge required. The learner contains an encoder network and decoder language model that perform variational inference with autoregressive orders (represented as permutation matrices) as latent variables. The corresponding ELBO is not differentiable, so we develop a practical algorithm for end-to-end optimization using policy gradients. We implement the encoder as a Transformer with non-causal attention that outputs permutations in one forward pass. Permutations then serve as target generation orders for training an insertion-based Transformer language model. Empirical results in language modeling tasks demonstrate that our method is context-aware and discovers orderings that are competitive with or even better than fixed orders.