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

Xinnan Dai, Kai Yang, Cheng Luo, Shenglai Zeng, Kai Guo, Jiliang Tang
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:22617-22632, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-dai26k, title = {When Do Hallucinations Arise? {A} Graph Perspective on the Evolution of Path Reuse and Path Compression}, author = {Dai, Xinnan and Yang, Kai and Luo, Cheng and Zeng, Shenglai and Guo, Kai and Tang, Jiliang}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {22617--22632}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/dai26k/dai26k.pdf}, url = {https://proceedings.mlr.press/v306/dai26k.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T When Do Hallucinations Arise? A Graph Perspective on the Evolution of Path Reuse and Path Compression %A Xinnan Dai %A Kai Yang %A Cheng Luo %A Shenglai Zeng %A Kai Guo %A Jiliang Tang %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-dai26k %I PMLR %P 22617--22632 %U https://proceedings.mlr.press/v306/dai26k.html %V 306 %X 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.
APA
Dai, X., Yang, K., Luo, C., Zeng, S., Guo, K. & Tang, J.. (2026). When Do Hallucinations Arise? A Graph Perspective on the Evolution of Path Reuse and Path Compression. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:22617-22632 Available from https://proceedings.mlr.press/v306/dai26k.html.

Related Material