# The Power of Power Law: Asymmetry Enables Compositional Reasoning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 55 of its 66 references that are in the map.
- First posted on arXiv 24 Apr 2026.

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

- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022)
- [Measuring and Narrowing the Compositionality Gap in Language Models](https://mlsanity.com/paper/2210.03350/) (2022)
- [Deep Learning Scaling is Predictable, Empirically](https://mlsanity.com/paper/1712.00409/) (2017)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Scaling Laws for Autoregressive Generative Modeling](https://mlsanity.com/paper/2010.14701/) (2020)
- [Beyond neural scaling laws: beating power law scaling via data pruning](https://mlsanity.com/paper/2206.14486/) (2022)
- [MQuAKE: Assessing Knowledge Editing in Language Models via Multi-Hop Questions](https://mlsanity.com/paper/2305.14795/) (2023)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [From Explicit CoT to Implicit CoT: Learning to Internalize CoT Step by Step](https://mlsanity.com/paper/2405.14838/) (2024)
- [Task Arithmetic in the Tangent Space: Improved Editing of Pre-Trained Models](https://mlsanity.com/paper/2305.12827/) (2023)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit](https://mlsanity.com/paper/2207.08799/) (2022)
- [Scaling Latent Reasoning via Looped Language Models](https://mlsanity.com/paper/2510.25741/) (2025)
- [Do Large Language Models Latently Perform Multi-Hop Reasoning?](https://mlsanity.com/paper/2402.16837/) (2024)
- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [Physics of Language Models: Part 3.2, Knowledge Manipulation](https://mlsanity.com/paper/2309.14402/) (2023)
- [Rethinking Class-Balanced Methods for Long-Tailed Visual Recognition from a Domain Adaptation Perspective](https://mlsanity.com/paper/2003.10780/) (2020)
- [The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks](https://mlsanity.com/paper/2202.08658/) (2022)
- [The Quantization Model of Neural Scaling](https://mlsanity.com/paper/2303.13506/) (2023)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [Skill-it! A Data-Driven Skills Framework for Understanding and Training Language Models](https://mlsanity.com/paper/2307.14430/) (2023)
- [A Theory for Emergence of Complex Skills in Language Models](https://mlsanity.com/paper/2307.15936/) (2023)
- [Physics of Language Models: Part 2.1, Grade-School Math and the Hidden Reasoning Process](https://mlsanity.com/paper/2407.20311/) (2024)
- [Metacognitive Capabilities of LLMs: An Exploration in Mathematical Problem Solving](https://mlsanity.com/paper/2405.12205/) (2024)
- [Grokked Transformers are Implicit Reasoners: A Mechanistic Journey to the Edge of Generalization](https://mlsanity.com/paper/2405.15071/) (2024)
- [Learning Parities with Neural Networks](https://mlsanity.com/paper/2002.07400/) (2020)
- [Hopping Too Late: Exploring the Limitations of Large Language Models on Multi-Hop Queries](https://mlsanity.com/paper/2406.12775/) (2024)
- [Skill-Mix: a Flexible and Expandable Family of Evaluations for AI models](https://mlsanity.com/paper/2310.17567/) (2023)

## Abstract (arXiv)

Natural language data follows a power-law distribution, with most knowledge and skills appearing at very low frequency. While a common intuition suggests that reweighting or curating data towards a uniform distribution may help models better learn these long-tail skills, we find a counterintuitive result: across a wide range of compositional reasoning tasks, such as state tracking and multi-step arithmetic, training under power-law distributions consistently outperforms training under uniform distributions. To understand this advantage, we introduce a minimalist skill-composition task and show that learning under a power-law distribution provably requires significantly less training data. Our theoretical analysis reveals that power law sampling induces a beneficial asymmetry that improves the pathological loss landscape, which enables models to first acquire high-frequency skill compositions with low data complexity, which in turn serves as a stepping stone to efficiently learn rare long-tailed skills. Our results offer an alternative perspective on what constitutes an effective data distribution for training models.