# Spectral Journey: How Transformers Predict the Shortest Path

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2025.

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

- [Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thought](https://mlsanity.com/paper/2505.12514/) (2025)
- [GaLore 2: Large-Scale LLM Pre-Training by Gradient Low-Rank Projection](https://mlsanity.com/paper/2504.20437/) (2025)
- [Is the Reversal Curse a Binding Problem? Uncovering Limitations of Transformers from a Basic Generalization Failure](https://mlsanity.com/paper/2504.01928/) (2025)
- [Benefits and Pitfalls of Reinforcement Learning for Language Model Planning: A Theoretical Perspective](https://mlsanity.com/paper/2509.22613/) (2025)
- [From Sequence to Structure: Uncovering Substructure Reasoning in Transformers](https://mlsanity.com/paper/2507.10435/) (2025)
- [Provable Benefits of RLVR over SFT for Reasoning Models: Learning to Backtrack Efficiently](https://mlsanity.com/paper/2606.22938/) (2026)
- [When Do Hallucinations Arise? A Graph Perspective on the Evolution of Path Reuse and Path Compression](https://mlsanity.com/paper/2604.03557/) (2026)
- [Generalization in LLM Problem Solving: The Case of the Shortest Path](https://mlsanity.com/paper/2604.15306/) (2026)

## Abstract (arXiv)

Decoder-only transformers lead to a step-change in capability of large language models. However, opinions are mixed as to whether they are really planning or reasoning. A path to making progress in this direction is to study the model's behavior in a setting with carefully controlled data. Then interpret the learned representations and reverse-engineer the computation performed internally. We study decoder-only transformer language models trained from scratch to predict shortest paths on simple, connected and undirected graphs. In this setting, the representations and the dynamics learned by the model are interpretable. We present three major results: (1) Two-layer decoder-only language models can learn to predict shortest paths on simple, connected graphs containing up to 10 nodes. (2) Models learn a graph embedding that is correlated with the spectral decomposition of the line graph. (3) Following the insights, we discover a novel approximate path-finding algorithm Spectral Line Navigator (SLN) that finds shortest path by greedily selecting nodes in the space of spectral embedding of the line graph.