mlsanityData to 7 Oct 2026

Task Generalization With AutoRegressive Compositional Structure: Can Learning From D Tasks Generalize to DT Tasks?

arXiv 2502.08991 ↗First posted 13 Feb 2025cs.LG stat.MLcited by 11

Not on the map. Why?

Abstract (arXiv)

Large language models (LLMs) exhibit remarkable task generalization, solving tasks they were never explicitly trained on with only a few demonstrations. This raises a fundamental question: When can learning from a small set of tasks generalize to a large task family? In this paper, we investigate task generalization through the lens of autoregressive compositional structure, where each task is a composition of T operations, and each operation is among a finite family of D subtasks. This yields a total class of size DT. We first show that generalization to all DT tasks is theoretically achievable by training on only widetildeO(D) tasks. Empirically, we demonstrate that Transformers achieve such exponential task generalization on sparse parity functions via In-context Learning (ICL) and chain-of-thought (CoT) reasoning. We further show generalization in arithmetic and translation, beyond parity functions.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 28 of its 36 references that are in the map. First posted on arXiv 13 Feb 2025.

Builds on

28 of 36 references.

References · 28

  1. 2020Language Models are Few-Shot Learnerscited by 32,199
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  3. 2022Emergent Abilities of Large Language Modelscited by 2,483
  4. 2019Invariant Risk Minimizationcited by 1,832
  5. 2016Understanding intermediate layers using linear classifier probescited by 1,279
  6. 2021Domain Generalization: A Surveycited by 760
  7. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 700
  8. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 496
  9. 2023Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selectioncited by 291
  10. 2023Transformers as Algorithms: Generalization and Stability in In-context Learningcited by 220
  11. 2020Understanding and Mitigating the Tradeoff Between Robustness and Accuracycited by 148
  12. 2021Towards a Theoretical Framework of Out-of-Distribution Generalizationcited by 94
16 more
  1. 2023Testing the General Deductive Reasoning Capacity of Large Language Models Using OOD Examplescited by 84
  2. 2018Marginal Singularity, and the Benefits of Labels in Covariate-Shiftcited by 65
  3. 2023Compositional Generalization from First Principlescited by 62
  4. 2023Understanding In-Context Learning in Transformers and LLMs by Learning to Learn Discrete Functionscited by 62
  5. 2020Distributionally Robust Losses for Latent Covariate Mixturescited by 57
  6. 2022Optimally tackling covariate shift in RKHS-based nonparametric regressioncited by 53
  7. 2023How Do In-Context Examples Affect Compositional Generalization?cited by 51
  8. 2021Near-Optimal Linear Regression under Distribution Shiftcited by 40
  9. 2024Do Large Language Models Have Compositional Ability? An Investigation into Limitations and Scalabilitycited by 39
  10. 2024How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpadcited by 35
  11. 2024Out-of-distribution generalization via composition: a lens through induction heads in Transformerscited by 28
  12. 2024From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiencycited by 28
  13. 2024Instruct-SkillMix: A Powerful Pipeline for LLM Instruction Tuningcited by 27
  14. 2016Hypothesis Transfer Learning via Transformation Functionscited by 26
  15. 2024When does compositional structure yield compositional generalization? A kernel theorycited by 19
  16. 2024Can Models Learn Skill Composition from Examples?cited by 17

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 5; 2026: 6.

11 papers.

  1. 2025Extrapolation by Association: Length Generalization Transfer in Transformerscited by 13
  2. 2025Ineq-Comp: Benchmarking Human-Intuitive Compositional Reasoning in Automated Theorem Proving on Inequalitiescited by 8
  3. 2026Efficient and Minimax Optimal In-context Nonparametric Regression with Transformerscited by 7
  4. 2026Contextual Agentic Memory is a Memo, Not True Memorycited by 5
  5. 2025Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Trainingcited by 4
  6. 2026Shattered Compositionality: Counterintuitive Learning Dynamics of Transformers for Arithmeticcited by 2
  7. 2025Small Models, Smarter Learning: The Power of Joint Task Trainingcited by 1
  8. 2026When Is Compositional Reasoning Learnable from Verifiable Rewards?cited by 1
  9. 2025Can Language Models Compose Skills In-Context?cited by 0
  10. 2026Generalization in LLM Problem Solving: The Case of the Shortest Pathcited by 0
  11. 2026Learning to Extrapolate to New Tasks: A Relational Approach to Task Extrapolationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Compositional Generalization in Autoregressive Models via Logit Composition
  2. 2025Characterizing Pattern Matching and Its Limits on Compositional Task Structures
  3. 2024On Provable Length and Compositional Generalization
  4. 2023Skills-in-Context Prompting: Unlocking Compositionality in Large Language Models
  5. 2026Learning to Reason with Curriculum II: Compositional Generalization
  6. 2025Compositional Generalization from Learned Skills via CoT Training: A Theoretical and Structural Analysis for Reasoning
  7. 2026Loop, Think, & Generalize: Implicit Reasoning in Recurrent-Depth Transformers
  8. 2025Beyond Single-Task: Robust Multi-Task Length Generalization for LLMs