# Learning Algebraic Recombination for Compositional Generalization

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 60 references that are in the map.
- First posted on arXiv 14 Jul 2021.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [Compositional Semantic Parsing on Semi-Structured Tables](https://mlsanity.com/paper/1508.00305/) (2015)
- [Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks](https://mlsanity.com/paper/1503.00075/) (2015)
- [Measuring Compositional Generalization: A Comprehensive Method on Realistic Data](https://mlsanity.com/paper/1912.09713/) (2019)
- [COGS: A Compositional Generalization Challenge Based on Semantic Interpretation](https://mlsanity.com/paper/2010.05465/) (2020)
- [The Evolved Transformer](https://mlsanity.com/paper/1901.11117/) (2019)
- [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)
- [Ordered Neurons: Integrating Tree Structures into Recurrent Neural Networks](https://mlsanity.com/paper/1810.09536/) (2018)
- [Compositional generalization through meta sequence-to-sequence learning](https://mlsanity.com/paper/1906.05381/) (2019)
- [Compositional Generalization in Semantic Parsing: Pre-training vs. Specialized Architectures](https://mlsanity.com/paper/2007.08970/) (2020)
- [The Optimal Reward Baseline for Gradient-Based Reinforcement Learning](https://mlsanity.com/paper/1301.2315/) (2013)
- [Compositional Generalization via Neural-Symbolic Stack Machines](https://mlsanity.com/paper/2008.06662/) (2020)
- [Span-based Semantic Parsing for Compositional Generalization](https://mlsanity.com/paper/2009.06040/) (2020)
- [Compound Probabilistic Context-Free Grammars for Grammar Induction](https://mlsanity.com/paper/1906.10225/) (2019)
- [Sequence-Level Mixed Sample Data Augmentation](https://mlsanity.com/paper/2011.09039/) (2020)
- [Learning to Recombine and Resample Data for Compositional Generalization](https://mlsanity.com/paper/2010.03706/) (2020)
- [Compositional generalization in a deep seq2seq model by separating syntax and semantics](https://mlsanity.com/paper/1904.09708/) (2019)
- [Compositional Generalization by Learning Analytical Expressions](https://mlsanity.com/paper/2006.10627/) (2020)
- [Learning to Compose Task-Specific Tree Structures](https://mlsanity.com/paper/1707.02786/) (2017)
- [Compositional Generalization for Primitive Substitutions](https://mlsanity.com/paper/1910.02612/) (2019)
- [Cooperative Learning of Disjoint Syntax and Semantics](https://mlsanity.com/paper/1902.09393/) (2019)
- [Hierarchical Poset Decoding for Compositional Generalization in Language](https://mlsanity.com/paper/2010.07792/) (2020)
- [Revisiting Iterative Back-Translation from the Perspective of Compositional Generalization](https://mlsanity.com/paper/2012.04276/) (2020)
- [*-CFQ: Analyzing the Scalability of Machine Learning on a Compositional Task](https://mlsanity.com/paper/2012.08266/) (2020)
- [Iterative Utterance Segmentation for Neural Semantic Parsing](https://mlsanity.com/paper/2012.07019/) (2020)

## Built on by (most cited first, 30 of 31)

- [Compositional Semantic Parsing with Large Language Models](https://mlsanity.com/paper/2209.15003/) (2022)
- [How Do In-Context Examples Affect Compositional Generalization?](https://mlsanity.com/paper/2305.04835/) (2023)
- [Improving Compositional Generalization with Latent Structure and Data Augmentation](https://mlsanity.com/paper/2112.07610/) (2021)
- [Uncontrolled Lexical Exposure Leads to Overestimation of Compositional Generalization in Pretrained Models](https://mlsanity.com/paper/2212.10769/) (2022)
- [Structural generalization is hard for sequence-to-sequence models](https://mlsanity.com/paper/2210.13050/) (2022)
- [SLOG: A Structural Generalization Benchmark for Semantic Parsing](https://mlsanity.com/paper/2310.15040/) (2023)
- [A Survey on Compositional Learning of AI Models: Theoretical and Experimental Practices](https://mlsanity.com/paper/2406.08787/) (2024)
- [When Can Transformers Ground and Compose: Insights from Compositional Generalization Benchmarks](https://mlsanity.com/paper/2210.12786/) (2022)
- [Compositionality as Lexical Symmetry](https://mlsanity.com/paper/2201.12926/) (2022)
- [Mutual Exclusivity Training and Primitive Augmentation to Induce Compositionality](https://mlsanity.com/paper/2211.15578/) (2022)
- [LAGr: Labeling Aligned Graphs for Improving Systematic Generalization in Semantic Parsing](https://mlsanity.com/paper/2110.07572/) (2021)
- [MAGNIFICo: Evaluating the In-Context Learning Ability of Large Language Models to Generalize to Novel Interpretations](https://mlsanity.com/paper/2310.11634/) (2023)
- [Can LLM find the green circle? Investigation and Human-guided tool manipulation for compositional generalization](https://mlsanity.com/paper/2312.07763/) (2023)
- [Learning to Generalize Compositionally by Transferring Across Semantic Parsing Tasks](https://mlsanity.com/paper/2111.05013/) (2021)
- [Compositional Generalisation with Structured Reordering and Fertility Layers](https://mlsanity.com/paper/2210.03183/) (2022)
- [Does Deep Learning Learn to Abstract? A Systematic Probing Framework](https://mlsanity.com/paper/2302.11978/) (2023)
- [Beam Tree Recursive Cells](https://mlsanity.com/paper/2305.19999/) (2023)
- [On Evaluating Multilingual Compositional Generalization with Translated Datasets](https://mlsanity.com/paper/2306.11420/) (2023)
- [Compositional Generalization without Trees using Multiset Tagging and Latent Permutations](https://mlsanity.com/paper/2305.16954/) (2023)
- [What makes Models Compositional? A Theoretical View: With Supplement](https://mlsanity.com/paper/2405.02350/) (2024)
- [Efficient Beam Tree Recursion](https://mlsanity.com/paper/2307.10779/) (2023)
- [Compositional Program Generation for Few-Shot Systematic Generalization](https://mlsanity.com/paper/2309.16467/) (2023)
- [Structural generalization in COGS: Supertagging is (almost) all you need](https://mlsanity.com/paper/2310.14124/) (2023)
- [Strengthening Structural Inductive Biases by Pre-training to Perform Syntactic Transformations](https://mlsanity.com/paper/2407.04543/) (2024)
- [Translate First Reorder Later: Leveraging Monotonicity in Semantic Parsing](https://mlsanity.com/paper/2210.04878/) (2022)
- [Learning to Compose Representations of Different Encoder Layers towards Improving Compositional Generalization](https://mlsanity.com/paper/2305.12169/) (2023)
- [Compositional Generalization Requires Compositional Parsers](https://mlsanity.com/paper/2202.11937/) (2022)
- [Laziness Is a Virtue When It Comes to Compositionality in Neural Semantic Parsing](https://mlsanity.com/paper/2305.04346/) (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)

## Abstract (arXiv)

Neural sequence models exhibit limited compositional generalization ability in semantic parsing tasks. Compositional generalization requires algebraic recombination, i.e., dynamically recombining structured expressions in a recursive manner. However, most previous studies mainly concentrate on recombining lexical units, which is an important but not sufficient part of algebraic recombination. In this paper, we propose LeAR, an end-to-end neural model to learn algebraic recombination for compositional generalization. The key insight is to model the semantic parsing task as a homomorphism between a latent syntactic algebra and a semantic algebra, thus encouraging algebraic recombination. Specifically, we learn two modules jointly: a Composer for producing latent syntax, and an Interpreter for assigning semantic operations. Experiments on two realistic and comprehensive compositional generalization benchmarks demonstrate the effectiveness of our model. The source code is publicly available at https://github.com/microsoft/ContextualSP.