# Language models can learn implicit multi-hop reasoning, but only if they have lots of training data

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 23 of its 48 references that are in the map.
- First posted on arXiv 23 May 2025.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

## Builds on (most cited first, 23 of 23)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [HuggingFace's Transformers: State-of-the-art Natural Language Processing](https://mlsanity.com/paper/1910.03771/) (2019)
- [Decoupled Weight Decay Regularization](https://mlsanity.com/paper/1711.05101/) (2017)
- [OpenAI o1 System Card](https://mlsanity.com/paper/2412.16720/) (2024)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Progress measures for grokking via mechanistic interpretability](https://mlsanity.com/paper/2301.05217/) (2023)
- [Training Large Language Models to Reason in a Continuous Latent Space](https://mlsanity.com/paper/2412.06769/) (2024)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [Do NOT Think That Much for 2+3=? On the Overthinking of o1-Like LLMs](https://mlsanity.com/paper/2412.21187/) (2024)
- [Language Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thought](https://mlsanity.com/paper/2210.01240/) (2022)
- [From Explicit CoT to Implicit CoT: Learning to Internalize CoT Step by Step](https://mlsanity.com/paper/2405.14838/) (2024)
- [Explaining grokking through circuit efficiency](https://mlsanity.com/paper/2309.02390/) (2023)
- [Theoretical limitations of multi-layer Transformer](https://mlsanity.com/paper/2412.02975/) (2024)
- [Do Large Language Models Perform Latent Multi-Hop Reasoning without Exploiting Shortcuts?](https://mlsanity.com/paper/2411.16679/) (2024)
- [Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits](https://mlsanity.com/paper/2308.03212/) (2023)
- [Critical Data Size of Language Models from a Grokking Perspective](https://mlsanity.com/paper/2401.10463/) (2024)
- [Strassen Attention, Split VC Dimension and Compositionality in Transformers](https://mlsanity.com/paper/2501.19215/) (2025)

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

- [Scaling Latent Reasoning via Looped Language Models](https://mlsanity.com/paper/2510.25741/) (2025)
- [Loop the Loopies!](https://mlsanity.com/paper/2607.16051/) (2026)
- [Benefits and Limitations of Communication in Multi-Agent Reasoning](https://mlsanity.com/paper/2510.13903/) (2025)
- [Rote Learning Considered Useful: Generalizing over Memorized Data in LLMs](https://mlsanity.com/paper/2507.21914/) (2025)
- [Layer-Order Inversion: Rethinking Latent Multi-Hop Reasoning in Large Language Models](https://mlsanity.com/paper/2601.03542/) (2026)
- [Opening the Black Box: A Survey on the Mechanisms of Multi-Step Reasoning in Large Language Models](https://mlsanity.com/paper/2601.14270/) (2026)
- [The Power of Power Law: Asymmetry Enables Compositional Reasoning](https://mlsanity.com/paper/2604.22951/) (2026)
- [Multi-Hop Knowledge Composition is Bound by Pretraining Exposure](https://mlsanity.com/paper/2606.09338/) (2026)
- [Disentangling Curriculum Learning in NLP: Towards a Unifying Taxonomy](https://mlsanity.com/paper/2607.18984/) (2026)
- [How Many Thoughts Can a Vector Hold? The Capacity of Reasoning by Superposition](https://mlsanity.com/paper/2609.13747/) (2026)
- [AgentVidBench: A Multi-Hop Video Question Answering Benchmark for Evaluating MLLM Agents](https://mlsanity.com/paper/2609.21386/) (2026)

## Abstract (arXiv)

Implicit reasoning is the ability of a language model to solve multi-hop reasoning tasks in a single forward pass, without chain of thought. We investigate this capability using GPT2-style language models trained from scratch on controlled k-hop reasoning datasets (k = 2, 3, 4). We show that while such models can indeed learn implicit k-hop reasoning, the required training data grows exponentially in k, and the required number of transformer layers grows linearly in k. We offer a theoretical explanation for why this depth growth is necessary. We further find that the data requirement can be mitigated, but not eliminated, through curriculum learning.