# Transformers Struggle to Learn to Search

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 51 references that are in the map.
- First posted on arXiv 6 Dec 2024.

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

- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [Are Emergent Abilities of Large Language Models a Mirage?](https://mlsanity.com/paper/2304.15004/) (2023)
- [Scaling Laws for Autoregressive Generative Modeling](https://mlsanity.com/paper/2010.14701/) (2020)
- [Causal Abstractions of Neural Networks](https://mlsanity.com/paper/2106.02997/) (2021)
- [Towards Best Practices of Activation Patching in Language Models: Metrics and Methods](https://mlsanity.com/paper/2309.16042/) (2023)
- [Language Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thought](https://mlsanity.com/paper/2210.01240/) (2022)
- [Selection-Inference: Exploiting Large Language Models for Interpretable Logical Reasoning](https://mlsanity.com/paper/2205.09712/) (2022)
- [Sophia: A Scalable Stochastic Second-order Optimizer for Language Model Pre-training](https://mlsanity.com/paper/2305.14342/) (2023)
- [COGS: A Compositional Generalization Challenge Based on Semantic Interpretation](https://mlsanity.com/paper/2010.05465/) (2020)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)
- [How to use and interpret activation patching](https://mlsanity.com/paper/2404.15255/) (2024)
- [Causal Mediation Analysis for Interpreting Neural NLP: The Case of Gender Bias](https://mlsanity.com/paper/2004.12265/) (2020)
- [LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks](https://mlsanity.com/paper/2402.01817/) (2024)
- [Do Large Language Models Latently Perform Multi-Hop Reasoning?](https://mlsanity.com/paper/2402.16837/) (2024)
- [The pitfalls of next-token prediction](https://mlsanity.com/paper/2403.06963/) (2024)
- [Stream of Search (SoS): Learning to Search in Language](https://mlsanity.com/paper/2404.03683/) (2024)
- [Broken Neural Scaling Laws](https://mlsanity.com/paper/2210.14891/) (2022)
- [Understanding Emergent Abilities of Language Models from the Loss Perspective](https://mlsanity.com/paper/2403.15796/) (2024)
- [On the Paradox of Learning to Reason from Data](https://mlsanity.com/paper/2205.11502/) (2022)
- [A Mechanistic Interpretation of Arithmetic Reasoning in Language Models using Causal Mediation Analysis](https://mlsanity.com/paper/2305.15054/) (2023)
- [NPHardEval: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity Classes](https://mlsanity.com/paper/2312.14890/) (2023)
- [Transformers, parallel computation, and logarithmic depth](https://mlsanity.com/paper/2402.09268/) (2024)
- [Understanding Transformer Reasoning Capabilities via Graph Algorithms](https://mlsanity.com/paper/2405.18512/) (2024)

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

- [BIG-Bench Extra Hard](https://mlsanity.com/paper/2502.19187/) (2025)
- [In-Context Algebra](https://mlsanity.com/paper/2512.16902/) (2025)
- [Transferability for General Reasoning: An Automated Curriculum for Multi-Domain RLVR](https://mlsanity.com/paper/2606.25178/) (2026)
- [The End of Transformers? On Challenging Attention and the Rise of Sub-Quadratic Architectures](https://mlsanity.com/paper/2510.05364/) (2025)
- [Are Language Models Efficient Reasoners? A Perspective from Logic Programming](https://mlsanity.com/paper/2510.25626/) (2025)
- [Discrete Diffusion Models Exploit Asymmetry to Solve Lookahead Planning Tasks](https://mlsanity.com/paper/2602.19980/) (2026)
- [Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More More](https://mlsanity.com/paper/2503.10542/) (2025)
- [The Imitation Game: Turing Machine Imitator is Length Generalizable Reasoner](https://mlsanity.com/paper/2507.13332/) (2025)
- [Uncovering Graph Reasoning in Decoder-only Transformers with Circuit Tracing](https://mlsanity.com/paper/2509.20336/) (2025)
- [The Depth Ceiling: On the Limits of Large Language Models in Discovering Latent Planning](https://mlsanity.com/paper/2604.06427/) (2026)
- [Barriers to Universal Reasoning With Transformers (And How to Overcome Them)](https://mlsanity.com/paper/2604.25800/) (2026)
- [Learning Model Successors](https://mlsanity.com/paper/2502.00197/) (2025)
- [Transformers Can Learn Connectivity in Some Graphs but Not Others](https://mlsanity.com/paper/2509.22343/) (2025)
- [GraphGhost: Tracing Structures Behind Large Language Models](https://mlsanity.com/paper/2510.08613/) (2025)
- [When Do Hallucinations Arise? A Graph Perspective on the Evolution of Path Reuse and Path Compression](https://mlsanity.com/paper/2604.03557/) (2026)
- [Inductive Generalization for Robotic Manipulation](https://mlsanity.com/paper/2606.20999/) (2026)
- [GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs](https://mlsanity.com/paper/2609.12265/) (2026)
- [Transformers Stop Thinking Too Early, and a Tiny LoRA Fixes It](https://mlsanity.com/paper/2609.36585/) (2026)
- [Conditional Transfer from Controlled Pretraining Mixtures to Code](https://mlsanity.com/paper/2610.11548/) (2026)

## Abstract (arXiv)

Search is an ability foundational in many important tasks, and recent studies have shown that large language models (LLMs) struggle to perform search robustly. It is unknown whether this inability is due to a lack of data, insufficient model parameters, or fundamental limitations of the transformer architecture. In this work, we use the foundational graph connectivity problem as a testbed to generate effectively limitless high-coverage data to train small transformers and test whether they can learn to perform search. We find that, when given the right training distribution, the transformer is able to learn to search. We analyze the algorithm that the transformer has learned through a novel mechanistic interpretability technique that enables us to extract the computation graph from the trained model. We find that transformers perform search at every vertex in parallel: For each vertex in the input graph, transformers compute the set of vertices reachable from that vertex. Each layer then progressively expands these sets, allowing the model to search over a number of vertices exponential in nlayers. However, we find that as the input graph size increases, the transformer has greater difficulty in learning the task. This difficulty is not resolved even as the number of parameters is increased, suggesting that increasing model scale will not lead to robust search abilities. We also find that performing search in-context (i.e., chain-of-thought) does not resolve this inability to learn to search on larger graphs.