# When Do Hallucinations Arise? A Graph Perspective on the Evolution of Path Reuse and Path Compression

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Hallucination detection and mitigation, one of 17 directions in LLM reasoning.
- Builds on 28 of its 33 references that are in the map.
- First posted on arXiv 4 Apr 2026.

## Placed in

- LLM reasoning / [Hallucination detection and mitigation](https://mlsanity.com/lr/hallucination-detection-and-mitigation/)

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

- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [Survey of Hallucination in Natural Language Generation](https://mlsanity.com/paper/2202.03629/) (2022)
- [A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions](https://mlsanity.com/paper/2311.05232/) (2023)
- [A Survey on Evaluation of Large Language Models](https://mlsanity.com/paper/2307.03109/) (2023)
- [Progress measures for grokking via mechanistic interpretability](https://mlsanity.com/paper/2301.05217/) (2023)
- [Siren's Song in the AI Ocean: A Survey on Hallucination in Large Language Models](https://mlsanity.com/paper/2309.01219/) (2023)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [Knowledge Graphs](https://mlsanity.com/paper/2003.02320/) (2020)
- [The Reversal Curse: LLMs trained on "A is B" fail to learn "B is A"](https://mlsanity.com/paper/2309.12288/) (2023)
- [Understanding the Effects of RLHF on LLM Generalisation and Diversity](https://mlsanity.com/paper/2310.06452/) (2023)
- [A Survey on Large Language Model (LLM) Security and Privacy: The Good, the Bad, and the Ugly](https://mlsanity.com/paper/2312.02003/) (2023)
- [LLMs Know More Than They Show: On the Intrinsic Representation of LLM Hallucinations](https://mlsanity.com/paper/2410.02707/) (2024)
- [DocRED: A Large-Scale Document-Level Relation Extraction Dataset](https://mlsanity.com/paper/1906.06127/) (2019)
- [Why Language Models Hallucinate](https://mlsanity.com/paper/2509.04664/) (2025)
- [The pitfalls of next-token prediction](https://mlsanity.com/paper/2403.06963/) (2024)
- [The Troubling Emergence of Hallucination in Large Language Models -- An Extensive Definition, Quantification, and Prescriptive Remediations](https://mlsanity.com/paper/2310.04988/) (2023)
- [Why think step by step? Reasoning emerges from the locality of experience](https://mlsanity.com/paper/2304.03843/) (2023)
- [Understanding Transformer Reasoning Capabilities via Graph Algorithms](https://mlsanity.com/paper/2405.18512/) (2024)
- [The Best Instruction-Tuning Data are Those That Fit](https://mlsanity.com/paper/2502.04194/) (2025)
- [Theoretical limitations of multi-layer Transformer](https://mlsanity.com/paper/2412.02975/) (2024)
- [Transformers Struggle to Learn to Search](https://mlsanity.com/paper/2412.04703/) (2024)
- [ALPINE: Unveiling the Planning Capability of Autoregressive Learning in Language Models](https://mlsanity.com/paper/2405.09220/) (2024)
- [AgentHallu: Benchmarking Automated Hallucination Attribution of LLM-based Agents](https://mlsanity.com/paper/2601.06818/) (2026)
- [PoLLMgraph: Unraveling Hallucinations in Large Language Models via State Transition Dynamics](https://mlsanity.com/paper/2404.04722/) (2024)
- [Towards an Understanding of Stepwise Inference in Transformers: A Synthetic Graph Navigation Model](https://mlsanity.com/paper/2402.07757/) (2024)
- [Spectral Journey: How Transformers Predict the Shortest Path](https://mlsanity.com/paper/2502.08794/) (2025)
- [Benefits and Pitfalls of Reinforcement Learning for Language Model Planning: A Theoretical Perspective](https://mlsanity.com/paper/2509.22613/) (2025)
- [What Does Loss Optimization Actually Teach, If Anything? Knowledge Dynamics in Continual Pre-training of LLMs](https://mlsanity.com/paper/2601.03858/) (2026)

## Abstract (arXiv)

Reasoning hallucinations in large language models (LLMs) often appear as fluent yet unsupported conclusions that violate either the given context or underlying factual knowledge. Although such failures are widely observed, the mechanisms by which decoder-only Transformers produce them remain poorly understood. We model next-token prediction as a graph search process over an underlying graph, where entities correspond to nodes and learned transitions form edges. From this perspective, contextual reasoning is a constrained search over a sampled subgraph (intrinsic reasoning), while context-free queries rely on memorized structures in the underlying graph (extrinsic reasoning). We show that reasoning hallucinations arise from two fundamental mechanisms: Path Reuse, where memorized knowledge overrides contextual constraints during early training, and Path Compression, where frequently traversed multi-step paths collapse into shortcut edges in later training. Together, these mechanisms provide a unified explanation for reasoning hallucinations in LLMs and connected to well-known behaviors observed in downstream applications.