# Complexity Control Facilitates Reasoning-Based Compositional Generalization in Transformers

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 56 of its 82 references that are in the map.
- First posted on arXiv 15 Jan 2025.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models](https://mlsanity.com/paper/2206.04615/) (2022)
- [Measuring and Narrowing the Compositionality Gap in Language Models](https://mlsanity.com/paper/2210.03350/) (2022)
- [A Closer Look at Memorization in Deep Networks](https://mlsanity.com/paper/1706.05394/) (2017)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [Compositional Visual Generation with Composable Diffusion Models](https://mlsanity.com/paper/2206.01714/) (2022)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Training-Free Structured Diffusion Guidance for Compositional Text-to-Image Synthesis](https://mlsanity.com/paper/2212.05032/) (2022)
- [Frequency Principle: Fourier Analysis Sheds Light on Deep Neural Networks](https://mlsanity.com/paper/1901.06523/) (2019)
- [Selection-Inference: Exploiting Large Language Models for Interpretable Logical Reasoning](https://mlsanity.com/paper/2205.09712/) (2022)
- [Compositionality decomposed: how do neural networks generalise?](https://mlsanity.com/paper/1908.08351/) (2019)
- [COGS: A Compositional Generalization Challenge Based on Semantic Interpretation](https://mlsanity.com/paper/2010.05465/) (2020)
- [Label Words are Anchors: An Information Flow Perspective for Understanding In-Context Learning](https://mlsanity.com/paper/2305.14160/) (2023)
- [Reduce, Reuse, Recycle: Compositional Generation with Energy-Based Diffusion Models and MCMC](https://mlsanity.com/paper/2302.11552/) (2023)
- [DeepNet: Scaling Transformers to 1,000 Layers](https://mlsanity.com/paper/2203.00555/) (2022)
- [Training behavior of deep neural network in frequency domain](https://mlsanity.com/paper/1807.01251/) (2018)
- [Omnigrok: Grokking Beyond Algorithmic Data](https://mlsanity.com/paper/2210.01117/) (2022)
- [Faithful Reasoning Using Large Language Models](https://mlsanity.com/paper/2208.14271/) (2022)
- [Benchmarking Spatial Relationships in Text-to-Image Generation](https://mlsanity.com/paper/2212.10015/) (2022)
- [A very preliminary analysis of DALL-E 2](https://mlsanity.com/paper/2204.13807/) (2022)
- [Grokked Transformers are Implicit Reasoners: A Mechanistic Journey to the Edge of Generalization](https://mlsanity.com/paper/2405.15071/) (2024)
- [The Neural Data Router: Adaptive Control Flow in Transformers Improves Systematic Generalization](https://mlsanity.com/paper/2110.07732/) (2021)
- [Improving Deep Transformer with Depth-Scaled Initialization and Merged Attention](https://mlsanity.com/paper/1908.11365/) (2019)

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

- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [An overview of condensation phenomenon in deep learning](https://mlsanity.com/paper/2504.09484/) (2025)
- [An Analysis for Reasoning Bias of Language Models with Small Initialization](https://mlsanity.com/paper/2502.04375/) (2025)
- [Adaptive Preconditioners Trigger Loss Spikes in Adam](https://mlsanity.com/paper/2506.04805/) (2025)
- [Do Latent-CoT Models Think Step-by-Step? A Mechanistic Study on Sequential Reasoning Tasks](https://mlsanity.com/paper/2602.00449/) (2026)
- [From Condensation to Rank Collapse: A Two-Stage Analysis of Transformer Training Dynamics](https://mlsanity.com/paper/2510.06954/) (2025)
- [An explainable transformer circuit for compositional generalization](https://mlsanity.com/paper/2502.15801/) (2025)
- [Unveiling the Mechanisms of Multi-Hop Reasoning in Transformers via Identity Bridge](https://mlsanity.com/paper/2509.24653/) (2025)
- [Weight Decay Improves Language Model Plasticity](https://mlsanity.com/paper/2602.11137/) (2026)
- [Achilles' Heel of Mamba: Essential difficulties of the Mamba architecture demonstrated by synthetic data](https://mlsanity.com/paper/2509.17514/) (2025)
- [Scalable Complexity Control Facilitates Reasoning Ability of LLMs](https://mlsanity.com/paper/2505.23013/) (2025)
- [Frequency-Aware Ensemble Learning for BraTS 2025 Pediatric Brain Tumor Segmentation](https://mlsanity.com/paper/2509.19353/) (2025)
- [Opening the Black Box: A Survey on the Mechanisms of Multi-Step Reasoning in Large Language Models](https://mlsanity.com/paper/2601.14270/) (2026)
- [Focus and Dilution: The Multi-stage Learning Process of Attention](https://mlsanity.com/paper/2605.01199/) (2026)
- [Critical Windows of Complexity Control: When Transformers Decide to Reason or Memorize](https://mlsanity.com/paper/2605.04396/) (2026)
- [Towards Compositional Generalization in LLMs for Smart Contract Security: A Case Study on Reentrancy Vulnerabilities](https://mlsanity.com/paper/2601.06914/) (2026)
- [The Stability of Singular Distribution: A Spectral Perspective on the Two-Phase Dynamics of Language Model Pre-training](https://mlsanity.com/paper/2605.26489/) (2026)
- [Small Initialization Matters for Large Language Models](https://mlsanity.com/paper/2606.17945/) (2026)
- [Gauging, Measuring, and Controlling Critic Complexity in Actor-Critic Reinforcement Learning](https://mlsanity.com/paper/2607.00452/) (2026)
- [Complexity-Guided Component-wise Initialization for Language Model Pretraining](https://mlsanity.com/paper/2607.09204/) (2026)

## Abstract (arXiv)

Transformers have demonstrated impressive capabilities across various tasks, yet their performance on compositional problems remains a subject of debate. In this study, we investigate the internal mechanisms underlying Transformers' behavior in compositional tasks. We find that complexity control strategies significantly influence whether the model learns primitive-level rules that generalize out-of-distribution (reasoning-based solutions) or relies solely on memorized mappings (memory-based solutions). By applying masking strategies to the model's information circuits and employing multiple complexity metrics, we reveal distinct internal working mechanisms associated with different solution types. Further analysis reveals that reasoning-based solutions exhibit a lower complexity bias, which aligns with the well-studied neuron condensation phenomenon. This lower complexity bias is hypothesized to be the key factor enabling these solutions to learn reasoning rules. We validate these conclusions across multiple real-world datasets, including image generation and natural language processing tasks, confirming the broad applicability of our findings.