# Learning Compositional Functions with Transformers from Easy-to-Hard Data

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2025.

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

- [Scaling Latent Reasoning via Looped Language Models](https://mlsanity.com/paper/2510.25741/) (2025)
- [Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization](https://mlsanity.com/paper/2511.07378/) (2025)
- [Sharp Capacity Scaling of Spectral Optimizers in Learning Associative Memory](https://mlsanity.com/paper/2603.26554/) (2026)
- [Sequential Group Composition: A Window into the Mechanics of Deep Learning](https://mlsanity.com/paper/2602.03655/) (2026)
- [h1: Bootstrapping LLMs to Reason over Longer Horizons via Reinforcement Learning](https://mlsanity.com/paper/2510.07312/) (2025)
- [Benefits and Limitations of Communication in Multi-Agent Reasoning](https://mlsanity.com/paper/2510.13903/) (2025)
- [Beyond Statistical Learning: Exact Learning Is Essential for General Intelligence](https://mlsanity.com/paper/2506.23908/) (2025)
- [From Shortcut to Induction Head: How Data Diversity Shapes Algorithm Selection in Transformers](https://mlsanity.com/paper/2512.18634/) (2025)
- [Outcome-Based RL Provably Leads Transformers to Reason, but Only With the Right Data](https://mlsanity.com/paper/2601.15158/) (2026)
- [Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining](https://mlsanity.com/paper/2601.19756/) (2026)
- [Shift is Good: Mismatched Data Mixing Improves Test Performance](https://mlsanity.com/paper/2510.25108/) (2025)
- [T-SHRED: Symbolic Regression for Regularization and Model Discovery with Transformer Shallow Recurrent Decoders](https://mlsanity.com/paper/2506.15881/) (2025)
- [On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach](https://mlsanity.com/paper/2510.04115/) (2025)
- [Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Training](https://mlsanity.com/paper/2511.07372/) (2025)
- [Length Generalization Bounds for Transformers](https://mlsanity.com/paper/2603.02238/) (2026)
- [Provably Learning from Modern Language Models via Low Logit Rank](https://mlsanity.com/paper/2512.09892/) (2025)
- [Shattered Compositionality: Counterintuitive Learning Dynamics of Transformers for Arithmetic](https://mlsanity.com/paper/2601.22510/) (2026)
- [Positive Distribution Shift as a Framework for Understanding Tractable Learning](https://mlsanity.com/paper/2602.08907/) (2026)
- [Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently](https://mlsanity.com/paper/2511.17852/) (2025)
- [Deep Networks Learn Deep Hierarchical Models](https://mlsanity.com/paper/2601.00455/) (2026)
- [Breaking the Reversal Curse in Autoregressive Language Models via Identity Bridge](https://mlsanity.com/paper/2602.02470/) (2026)
- [When does Chain-of-Thought Help: A Markovian Perspective](https://mlsanity.com/paper/2603.00306/) (2026)
- [Transformers Provably Learn to Internalize Chain-of-Thought](https://mlsanity.com/paper/2605.28600/) (2026)
- [Invariant Learning Dynamics of Transformers in Inductive Reasoning Tasks](https://mlsanity.com/paper/2607.11875/) (2026)
- [Understanding the Staged Dynamics of Transformers in Learning Latent Structure](https://mlsanity.com/paper/2511.19328/) (2025)
- [MathMixup: Boosting LLM Mathematical Reasoning with Difficulty-Controllable Data Synthesis and Curriculum Learning](https://mlsanity.com/paper/2601.17006/) (2026)
- [Boule or Baguette? A Study on Task Topology, Length Generalization, and the Benefit of Reasoning Traces](https://mlsanity.com/paper/2602.14404/) (2026)
- [Transformers Efficiently Perform In-Context Logistic Regression via Normalized Gradient Descent](https://mlsanity.com/paper/2605.06609/) (2026)
- [Fine-Tuning Dynamics of In-Context Factual Recall in Transformers](https://mlsanity.com/paper/2605.27774/) (2026)
- [SciDocBench: A Workflow-Centered Benchmark and Data Pipeline for Scientific Document Understanding](https://mlsanity.com/paper/2609.05141/) (2026)

## Abstract (arXiv)

Transformer-based language models have demonstrated impressive capabilities across a range of complex reasoning tasks. Prior theoretical work exploring the expressive power of transformers has shown that they can efficiently perform multi-step reasoning tasks involving parallelizable computations. However, the learnability of such constructions, particularly the conditions on the data distribution that enable efficient learning via gradient-based optimization, remains an open question. Towards answering this question, in this work we study the learnability of the k-fold composition task, which requires computing an interleaved composition of k input permutations and k hidden permutations, and can be expressed by a transformer with O(log k) layers. On the negative front, we prove a Statistical Query (SQ) lower bound showing that any SQ learner that makes only polynomially-many queries to an SQ oracle for the k-fold composition task distribution must have sample size exponential in k, thus establishing a statistical-computational gap. On the other hand, we show that this function class can be efficiently learned, with runtime and sample complexity polynomial in k, by gradient descent on an O(log k)-depth transformer via two different curriculum learning strategies: one in which data consists of k'-fold composition functions with k' ≤ k presented in increasing difficulty, and another in which all such data is presented simultaneously. Our work sheds light on the necessity and sufficiency of having both easy and hard examples in the data distribution for transformers to learn complex compositional tasks.