mlsanityData to 14 Oct 2026

Benchmarking Compositionality with Formal Languages

arXiv 2208.08195 ↗First posted 17 Aug 2022cs.CLcited by 12

Not on the map. Why?

Abstract (arXiv)

Recombining known primitive concepts into larger novel combinations is a quintessentially human cognitive capability. Whether large neural models in NLP can acquire this ability while learning from data is an open question. In this paper, we investigate this problem from the perspective of formal languages. We use deterministic finite-state transducers to make an unbounded number of datasets with controllable properties governing compositionality. By randomly sampling over many transducers, we explore which of their properties contribute to learnability of a compositional relation by a neural network. We find that the models either learn the relations completely or not at all. The key is transition coverage, setting a soft learnability limit at 400 examples per transition.

Key facts. Cited by 12 papers in the map (data through 14 Oct 2026). Builds on 18 of its 45 references that are in the map. First posted on arXiv 17 Aug 2022.

Builds on

18 of 45 references.

References · 18

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,548
  3. 2014Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translationcited by 4,057
  4. 2019Compositionality decomposed: how do neural networks generalise?cited by 265
  5. 2018On the Practical Computational Power of Finite Precision RNNs for Language Recognitioncited by 117
  6. 2020A Benchmark for Systematic Generalization in Grounded Language Understandingcited by 108
  7. 2019Measuring Compositionality in Representation Learningcited by 84
  8. 2020RNNs can generate bounded hierarchical languages with optimal memorycited by 59
  9. 2021The paradox of the compositionality of natural language: a neural machine translation case studycited by 59
  10. 2019LSTM Networks Can Perform Dynamic Countingcited by 45
  11. 2021Examining the Inductive Bias of Neural Language Models with Artificial Languagescited by 40
  12. 2018Jump to better conclusions: SCAN both left and rightcited by 29
6 more
  1. 2022Unobserved Local Structures Make Compositional Generalization Hardcited by 29
  2. 2019Exact Hard Monotonic Attention for Character-Level Transductioncited by 22
  3. 2020On the Practical Ability of Recurrent Neural Networks to Recognize Hierarchical Languagescited by 22
  4. 2015A Roadmap towards Machine Intelligencecited by 15
  5. 2017Subregular Complexity and Deep Learningcited by 5
  6. 2019Multi-Element Long Distance Dependencies: Using SPk Languages to Explore the Characteristics of Long-Distance Dependenciescited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 5; 2024: 3; 2025: 3; 2026: 1.

12 papers.

  1. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 199
  2. 2023Mechanistically analyzing the effects of fine-tuning on procedurally defined taskscited by 115
  3. 2023Compositional Abilities Emerge Multiplicatively: Exploring Diffusion Models on a Synthetic Taskcited by 93
  4. 2024A Percolation Model of Emergence: Analyzing Transformers Trained on a Formal Languagecited by 26
  5. 2024A Survey on Compositional Learning of AI Models: Theoretical and Experimental Practicescited by 15
  6. 2023The Validity of Evaluation Results: Assessing Concurrence Across Compositionality Benchmarkscited by 12
  7. 2025Mechanistic evaluation of Transformers and state space modelscited by 9
  8. 2023Vocabulary for Universal Approximation: A Linguistic Perspective of Mapping Compositionscited by 6
  9. 2024Swing-by Dynamics in Concept Learning and Compositional Generalizationcited by 5
  10. 2025Provable Benefits of In-Tool Learning for Large Language Modelscited by 4
  11. 2025Randomly Sampled Language Reasoning Problems Elucidate Limitations of In-Context Learningcited by 1
  12. 2026Compositionality Emerges in a Narrow Depth-Connectivity Regime: Architecture Constraints and Solution Manifoldscited by 0