# Compositional Generalization without Trees using Multiset Tagging and Latent Permutations

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 57 references that are in the map.
- First posted on arXiv 26 May 2023.

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

- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension](https://mlsanity.com/paper/1910.13461/) (2019)
- [Compositionality decomposed: how do neural networks generalise?](https://mlsanity.com/paper/1908.08351/) (2019)
- [COGS: A Compositional Generalization Challenge Based on Semantic Interpretation](https://mlsanity.com/paper/2010.05465/) (2020)
- [Learning Latent Permutations with Gumbel-Sinkhorn Networks](https://mlsanity.com/paper/1802.08665/) (2018)
- [Good-Enough Compositional Data Augmentation](https://mlsanity.com/paper/1904.09545/) (2019)
- [Improving Text-to-SQL Evaluation Methodology](https://mlsanity.com/paper/1806.09029/) (2018)
- [The Devil is in the Detail: Simple Tricks Improve Systematic Generalization of Transformers](https://mlsanity.com/paper/2108.12284/) (2021)
- [Compositional Semantic Parsing with Large Language Models](https://mlsanity.com/paper/2209.15003/) (2022)
- [Span-based Semantic Parsing for Compositional Generalization](https://mlsanity.com/paper/2009.06040/) (2020)
- [Meta-Learning to Compositionally Generalize](https://mlsanity.com/paper/2106.04252/) (2021)
- [The Neural Data Router: Adaptive Control Flow in Transformers Improves Systematic Generalization](https://mlsanity.com/paper/2110.07732/) (2021)
- [Simple and Accurate Dependency Parsing Using Bidirectional LSTM Feature Representations](https://mlsanity.com/paper/1603.04351/) (2016)
- [Improving Compositional Generalization with Latent Structure and Data Augmentation](https://mlsanity.com/paper/2112.07610/) (2021)
- [AMR Parsing as Graph Prediction with Latent Alignment](https://mlsanity.com/paper/1805.05286/) (2018)
- [Compositional Generalization via Semantic Tagging](https://mlsanity.com/paper/2010.11818/) (2020)
- [Learning Algebraic Recombination for Compositional Generalization](https://mlsanity.com/paper/2107.06516/) (2021)
- [Sequence-to-Sequence Learning with Latent Neural Grammars](https://mlsanity.com/paper/2109.01135/) (2021)
- [Disentangled Sequence to Sequence Learning for Compositional Generalization](https://mlsanity.com/paper/2110.04655/) (2021)
- [Lexicon Learning for Few-Shot Neural Sequence Modeling](https://mlsanity.com/paper/2106.03993/) (2021)
- [Structural generalization is hard for sequence-to-sequence models](https://mlsanity.com/paper/2210.13050/) (2022)
- [ReCOGS: How Incidental Details of a Logical Form Overshadow an Evaluation of Semantic Interpretation](https://mlsanity.com/paper/2303.13716/) (2023)
- [AMR Dependency Parsing with a Typed Semantic Algebra](https://mlsanity.com/paper/1805.11465/) (2018)
- [Structured Reordering for Modeling Latent Alignments in Sequence Transduction](https://mlsanity.com/paper/2106.03257/) (2021)
- [Sinkhorn Algorithm for Lifted Assignment Problems](https://mlsanity.com/paper/1707.07285/) (2017)
- [LAGr: Labeling Aligned Graphs for Improving Systematic Generalization in Semantic Parsing](https://mlsanity.com/paper/2110.07572/) (2021)
- [Compositional Generalization for Natural Language Interfaces to Web APIs](https://mlsanity.com/paper/2112.05209/) (2021)
- [Compositional Generalisation with Structured Reordering and Fertility Layers](https://mlsanity.com/paper/2210.03183/) (2022)
- [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)

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

- [Leveraging Code to Improve In-context Learning for Semantic Parsing](https://mlsanity.com/paper/2311.09519/) (2023)
- [SIP: Injecting a Structural Inductive Bias into a Seq2Seq Model by Simulation](https://mlsanity.com/paper/2310.00796/) (2023)
- [Compositional Generalization Across Distributional Shifts with Sparse Tree Operations](https://mlsanity.com/paper/2412.14076/) (2024)
- [Strengthening Structural Inductive Biases by Pre-training to Perform Syntactic Transformations](https://mlsanity.com/paper/2407.04543/) (2024)
- [Compositional Generalisation for Explainable Hate Speech Detection](https://mlsanity.com/paper/2506.03916/) (2025)

## Abstract (arXiv)

Seq2seq models have been shown to struggle with compositional generalization in semantic parsing, i.e. generalizing to unseen compositions of phenomena that the model handles correctly in isolation. We phrase semantic parsing as a two-step process: we first tag each input token with a multiset of output tokens. Then we arrange the tokens into an output sequence using a new way of parameterizing and predicting permutations. We formulate predicting a permutation as solving a regularized linear program and we backpropagate through the solver. In contrast to prior work, our approach does not place a priori restrictions on possible permutations, making it very expressive. Our model outperforms pretrained seq2seq models and prior work on realistic semantic parsing tasks that require generalization to longer examples. We also outperform non-tree-based models on structural generalization on the COGS benchmark. For the first time, we show that a model without an inductive bias provided by trees achieves high accuracy on generalization to deeper recursion.