# Structured Reordering for Modeling Latent Alignments in Sequence Transduction

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 63 references that are in the map.
- First posted on arXiv 6 Jun 2021.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [SuperGLUE: A Stickier Benchmark for General-Purpose Language Understanding Systems](https://mlsanity.com/paper/1905.00537/) (2019)
- [Show, Attend and Tell: Neural Image Caption Generation with Visual Attention](https://mlsanity.com/paper/1502.03044/) (2015)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Effective Approaches to Attention-based Neural Machine Translation](https://mlsanity.com/paper/1508.04025/) (2015)
- [Generating Sentences from a Continuous Space](https://mlsanity.com/paper/1511.06349/) (2015)
- [Neural Module Networks](https://mlsanity.com/paper/1511.02799/) (2015)
- [Measuring Compositional Generalization: A Comprehensive Method on Realistic Data](https://mlsanity.com/paper/1912.09713/) (2019)
- [Learning Latent Permutations with Gumbel-Sinkhorn Networks](https://mlsanity.com/paper/1802.08665/) (2018)
- [Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?](https://mlsanity.com/paper/2010.12725/) (2020)
- [Improving Text-to-SQL Evaluation Methodology](https://mlsanity.com/paper/1806.09029/) (2018)
- [Lagging Inference Networks and Posterior Collapse in Variational Autoencoders](https://mlsanity.com/paper/1901.05534/) (2019)
- [Differentiable Ranks and Sorting using Optimal Transport](https://mlsanity.com/paper/1905.11885/) (2019)
- [Stochastic Optimization of Sorting Networks via Continuous Relaxations](https://mlsanity.com/paper/1903.08850/) (2019)
- [Structured Attention Networks](https://mlsanity.com/paper/1702.00887/) (2017)
- [Span-based Semantic Parsing for Compositional Generalization](https://mlsanity.com/paper/2009.06040/) (2020)
- [SparseMAP: Differentiable Sparse Structured Inference](https://mlsanity.com/paper/1802.04223/) (2018)
- [Compositional generalization in a deep seq2seq model by separating syntax and semantics](https://mlsanity.com/paper/1904.09708/) (2019)
- [Rearranging the Familiar: Testing Compositional Generalization in Recurrent Networks](https://mlsanity.com/paper/1807.07545/) (2018)
- [Learning Conditioned Graph Structures for Interpretable Visual Question Answering](https://mlsanity.com/paper/1806.07243/) (2018)
- [Probing Linguistic Systematicity](https://mlsanity.com/paper/2005.04315/) (2020)
- [AMR Parsing as Graph Prediction with Latent Alignment](https://mlsanity.com/paper/1805.05286/) (2018)
- [Latent Alignment and Variational Attention](https://mlsanity.com/paper/1807.03756/) (2018)
- [Learning to Compose Words into Sentences with Reinforcement Learning](https://mlsanity.com/paper/1611.09100/) (2016)
- [Cooperative Learning of Disjoint Syntax and Semantics](https://mlsanity.com/paper/1902.09393/) (2019)
- [Sequence Modeling via Segmentations](https://mlsanity.com/paper/1702.07463/) (2017)
- [Online Segment to Segment Neural Transduction](https://mlsanity.com/paper/1609.08194/) (2016)
- [Latent Template Induction with Gumbel-CRFs](https://mlsanity.com/paper/2011.14244/) (2020)

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

- [Evaluating the Impact of Model Scale for Compositional Generalization in Semantic Parsing](https://mlsanity.com/paper/2205.12253/) (2022)
- [Improving Compositional Generalization with Latent Structure and Data Augmentation](https://mlsanity.com/paper/2112.07610/) (2021)
- [Sequence-to-Sequence Learning with Latent Neural Grammars](https://mlsanity.com/paper/2109.01135/) (2021)
- [Improving Generalization in Language Model-Based Text-to-SQL Semantic Parsing: Two Simple Semantic Boundary-Based Techniques](https://mlsanity.com/paper/2305.17378/) (2023)
- [Measuring and Improving Compositional Generalization in Text-to-SQL via Component Alignment](https://mlsanity.com/paper/2205.02054/) (2022)
- [LAGr: Labeling Aligned Graphs for Improving Systematic Generalization in Semantic Parsing](https://mlsanity.com/paper/2110.07572/) (2021)
- [Hierarchical Phrase-based Sequence-to-Sequence Learning](https://mlsanity.com/paper/2211.07906/) (2022)
- [Compositional Generalisation with Structured Reordering and Fertility Layers](https://mlsanity.com/paper/2210.03183/) (2022)
- [Compositional Generalization without Trees using Multiset Tagging and Latent Permutations](https://mlsanity.com/paper/2305.16954/) (2023)
- [Translate First Reorder Later: Leveraging Monotonicity in Semantic Parsing](https://mlsanity.com/paper/2210.04878/) (2022)
- [On graph-based reentrancy-free semantic parsing](https://mlsanity.com/paper/2302.07679/) (2023)
- [Layer-wise Representation Fusion for Compositional Generalization](https://mlsanity.com/paper/2307.10799/) (2023)
- [Measuring Alignment Bias in Neural Seq2Seq Semantic Parsers](https://mlsanity.com/paper/2205.08288/) (2022)
- [Improving Grammar-based Sequence-to-Sequence Modeling with Decomposition and Constraints](https://mlsanity.com/paper/2306.02671/) (2023)
- [A Note on Bias to Complete](https://mlsanity.com/paper/2402.11710/) (2024)
- [LAGr: Label Aligned Graphs for Better Systematic Generalization in Semantic Parsing](https://mlsanity.com/paper/2205.09607/) (2022)
- [A Short Survey of Systematic Generalization](https://mlsanity.com/paper/2211.11956/) (2022)

## Abstract (arXiv)

Despite success in many domains, neural models struggle in settings where train and test examples are drawn from different distributions. In particular, in contrast to humans, conventional sequence-to-sequence (seq2seq) models fail to generalize systematically, i.e., interpret sentences representing novel combinations of concepts (e.g., text segments) seen in training. Traditional grammar formalisms excel in such settings by implicitly encoding alignments between input and output segments, but are hard to scale and maintain. Instead of engineering a grammar, we directly model segment-to-segment alignments as discrete structured latent variables within a neural seq2seq model. To efficiently explore the large space of alignments, we introduce a reorder-first align-later framework whose central component is a neural reordering module producing it separable permutations. We present an efficient dynamic programming algorithm performing exact marginal inference of separable permutations, and, thus, enabling end-to-end differentiable training of our model. The resulting seq2seq model exhibits better systematic generalization than standard models on synthetic problems and NLP tasks (i.e., semantic parsing and machine translation).