# Learning curves theory for hierarchically compositional data with power-law distributed features

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 43 references that are in the map.
- First posted on arXiv 11 May 2025.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Deep Learning Scaling is Predictable, Empirically](https://mlsanity.com/paper/1712.00409/) (2017)
- [Explaining Neural Scaling Laws](https://mlsanity.com/paper/2102.06701/) (2021)
- [Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks](https://mlsanity.com/paper/2002.02561/) (2020)
- [Feature Learning in Infinite-Width Neural Networks](https://mlsanity.com/paper/2011.14522/) (2020)
- [The Quantization Model of Neural Scaling](https://mlsanity.com/paper/2303.13506/) (2023)
- [A Solvable Model of Neural Scaling Laws](https://mlsanity.com/paper/2210.16859/) (2022)
- [A Dynamical Model of Neural Scaling Laws](https://mlsanity.com/paper/2402.01092/) (2024)
- [A Phase Transition in Diffusion Models Reveals the Hierarchical Nature of Data](https://mlsanity.com/paper/2402.16991/) (2024)
- [Learning Curve Theory](https://mlsanity.com/paper/2102.04074/) (2021)
- [Physics of Language Models: Part 1, Learning Hierarchical Language Structures](https://mlsanity.com/paper/2305.13673/) (2023)
- [Transformers represent belief state geometry in their residual stream](https://mlsanity.com/paper/2405.15943/) (2024)
- [Does syntax need to grow on trees? Sources of hierarchical inductive bias in sequence-to-sequence networks](https://mlsanity.com/paper/2001.03632/) (2020)
- [How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Model](https://mlsanity.com/paper/2307.02129/) (2023)
- [Scaling Laws in Linear Regression: Compute, Parameters, and Data](https://mlsanity.com/paper/2406.08466/) (2024)
- [Do Transformers Parse while Predicting the Masked Word?](https://mlsanity.com/paper/2303.08117/) (2023)
- [Towards a theory of how the structure of language is acquired by deep neural networks](https://mlsanity.com/paper/2406.00048/) (2024)
- [Transformers Can Represent n-gram Language Models](https://mlsanity.com/paper/2404.14994/) (2024)
- [Locality defeats the curse of dimensionality in convolutional teacher-student scenarios](https://mlsanity.com/paper/2106.08619/) (2021)
- [Understanding Transformers via N-gram Statistics](https://mlsanity.com/paper/2407.12034/) (2024)
- [Probing the Latent Hierarchical Structure of Data via Diffusion Models](https://mlsanity.com/paper/2410.13770/) (2024)
- [A Provably Correct Algorithm for Deep Learning that Actually Works](https://mlsanity.com/paper/1803.09522/) (2018)
- [What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languages](https://mlsanity.com/paper/2406.04289/) (2024)
- [How transformers learn structured data: insights from hierarchical filtering](https://mlsanity.com/paper/2408.15138/) (2024)
- [U-Nets as Belief Propagation: Efficient Classification, Denoising, and Diffusion in Generative Hierarchical Models](https://mlsanity.com/paper/2404.18444/) (2024)
- [What Can Be Learnt With Wide Convolutional Neural Networks?](https://mlsanity.com/paper/2208.01003/) (2022)
- [A Statistical Theory of Contrastive Pre-training and Multimodal Generative AI](https://mlsanity.com/paper/2501.04641/) (2025)
- [Can Transformers Learn n-gram Language Models?](https://mlsanity.com/paper/2410.03001/) (2024)

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

- [There Will Be a Scientific Theory of Deep Learning](https://mlsanity.com/paper/2604.21691/) (2026)
- [Bigger Isn't Always Memorizing: Early Stopping Overparameterized Diffusion Models](https://mlsanity.com/paper/2505.16959/) (2025)
- [Why Larger Models Learn More: Effects of Capacity, Interference, and Rare-Task Retention](https://mlsanity.com/paper/2605.29548/) (2026)
- [Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining](https://mlsanity.com/paper/2601.19756/) (2026)
- [Scale Dependent Data Duplication](https://mlsanity.com/paper/2603.06603/) (2026)
- [Towards Worst-Case Guarantees with Scale-Aware Interpretability](https://mlsanity.com/paper/2602.05184/) (2026)
- [Incremental Learning of Sparse Attention Patterns in Transformers](https://mlsanity.com/paper/2602.19143/) (2026)
- [Sampling Data with Chains of Forward-Backward Diffusion Steps](https://mlsanity.com/paper/2605.27006/) (2026)
- [Statistical Properties of Training & Generalization](https://mlsanity.com/paper/2606.20299/) (2026)
- [Diffusion Models Preferentially Memorize Prototypical Examples or: Why Does My Diffusion Model Love Slop?](https://mlsanity.com/paper/2605.30642/) (2026)
- [Spectral Reach: Understanding Neural Scaling as Progress into the Spectral Tail](https://mlsanity.com/paper/2605.31244/) (2026)
- [Smooth Scaling Laws Hide Stepwise Token Learning](https://mlsanity.com/paper/2606.29858/) (2026)
- [Perplexity-Aware Data Scaling Law: Perplexity Landscapes Predict Performance for Continual Pre-training](https://mlsanity.com/paper/2512.21515/) (2025)
- [Sharp feature-learning transitions and Bayes-optimal neural scaling laws in extensive-width networks](https://mlsanity.com/paper/2605.10395/) (2026)
- [Critical Percolation as a Synthetic Data Model for Interpretability](https://mlsanity.com/paper/2606.20347/) (2026)
- [Limits of Reliability and Scaling in Language Models](https://mlsanity.com/paper/2607.14112/) (2026)
- [Neural Dynamics as the Composition of Quantized Units](https://mlsanity.com/paper/2609.32487/) (2026)

## Abstract (arXiv)

Recent theories suggest that Neural Scaling Laws arise whenever the task is linearly decomposed into power-law distributed units. Alternatively, scaling laws also emerge when data exhibit a hierarchically compositional structure, as is thought to occur in language and images. To unify these views, we consider classification and next-token prediction tasks based on probabilistic context-free grammars -- probabilistic models that generate data via a hierarchy of production rules. For classification, we show that having power-law distributed production rules results in a power-law learning curve with an exponent depending on the rules' distribution and a large multiplicative constant that depends on the hierarchical structure. By contrast, for next-token prediction, the distribution of production rules controls the local details of the learning curve, but not the exponent describing the large-scale behaviour.