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

cs.AIApr 4, 2026

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

Authors: Xinnan Dai, Kai Yang, Cheng Luo, Shenglai Zeng, Kai Guo, Jiliang Tang

Organizations: Michigan State University · University of Michigan · Independent Researcher

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.

Figures & tables

Figure 1: Reasoning Hallucinations from Underlying Graph Structures. (a) Building up the underlying graph for the implicit knowledge structure (b) In intrinsic reasoning, the model reuses common paths and hallucinates a direct relation (John → Scott) instead of the correct reasoning provided in context (John → Kim → Scott). (c) In extrinsic reasoning, long reasoning chains (David → John → Kim → Scott) are compressed into shorter paths (David → Kim → Scott), causing hallucinated relations via path compression.

Figure 2: Training evolution in conditional reasoning. (a) Accuracy trajectories under a 20% training set. The persistent gap between global and local accuracy indicates the emergence of hallucinations. (b) Accuracy trajectories under a 0.1% training set. Hallucinations persist and cannot be resolved by simply increasing the number of training steps. The zoomed-out view further shows that, at later stages of training, the Exist Acc gradually deteriorates and Global Acc is not stable.

Figure 3: Path Compression. (a) Accuracy degradation during training across graph settings. (b) Errors are biased toward k-hop neighbors. (c) Path-compression hallucinations via implicit k-hop edge creation. (d) Accumulation of high–out-degree nodes in erroneous predictions.

Figure 4: Error Understanding. (a) Prediction errors decrease as the out-degree of the start nodes increases. (b) Path compression reveals a tendency to bypass bridge nodes, directly jumping across communities.

Figure 5: Uncompressed ratio under different model settings. (a) Increasing the number of layers does not prevent the decline of the uncompressed ratio. (b) The uncompressed ratio consistently declines across different next-token prediction frameworks.

Panel of Figure 6 — Figure 6: Example of change a reasoning path from underlying graph to a story.

Figure 7: Training on language sequence. The highest uncompressed ratio is in the early stage.

Figure 8: Accuracy improvement ( $\Delta$ ACC) during finetuning with SFT and PPO. The original Acc are 0.8527, 0.753, 0.6787 at epoch [1][3][6]. (a) SFT finetuning shows unstable recovery behavior, especially at later pretraining stages. (b) PPO finetuning consistently achieves higher and more stable accuracy gains across different hop distances.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Hyperparameter	Value
Hidden size ( $d_{\text{model}}$ )	512
Sequence length (block size)	128
Learning rate	$5\times 10^{-4}$
Optimizer	AdamW
Weight decay	0.1
Learning rate scheduler	Cosine

Appendix

Table 1: Training hyperparameters used in all experiments unless otherwise specified.

Parameter	LLaMA	Mixtral	Qwen2
Hidden size ( $d_{\text{model}}$ )	512
FFN hidden size	$2.8\times d_{\text{model}}$	$2.8\times d_{\text{model}}$	$2.8\times d_{\text{model}}$
Number of layers	6
Attention heads	16
Key-value heads (GQA)	8
Head dimension	64

Appendix

Table 2: Backbone model configurations for different Transformer architectures.

$\#\mathrm{community}\_p_{in}\_p_{out}$	epoch-1	epoch-7	epoch-49	time (ms)
$10\_0.3\_0.01$	$0.992\pm 0.00$	$0.998\pm 0.00$	$0.983\pm 0.00$	1197.10
$10\_0.6\_0.01$	$0.998\pm 0.00$	$0.999\pm 0.00$	$0.997\pm 0.00$	1805.54
$50\_0.3\_0.01$	$0.904\pm 0.02$	$0.979\pm 0.04$	$0.888\pm 0.14$	324.62
$50\_0.6\_0.01$	$0.967\pm 0.07$	$0.978\pm 0.02$	$0.898\pm 0.03$	375.81
$100\_0.1\_0.01$	$0.952\pm 0.01$	$0.959\pm 0.01$	$0.851\pm 0.00$	199.79
$100\_0.1\_0.02$	$0.962\pm 0.002$	$0.970\pm 0.003$	$0.831\pm 0.011$	393.95

Appendix

Table 3: Performance under different graph structures

Figure 9: Path compression in knowledge graph data.

Dataset	#Node	#Edge	#Community	Internal degree	External degree
GSM8K (Math)	1406	5084	71	0.383	0.002
APPS (Code)	12454	112184	136	0.389	0.001
DocRED (KG)	20221	38180	770	0.431	$1\times 10^{-5}$

Appendix

Table 4: Real world data analysis

Figure 10: Underlying graphs with 0.01 $\rm p_{out}$

Figure 11: Underlying graphs with 0.02 $\rm p_{out}$

Figure 12: Underlying graphs with 0.03 $\rm p_{out}$

Hallucination in Language Models

Hallucination in language models studies how systems produce unsupported or false claims and how to detect, explain, and reduce them.

See all 247 papers

Why LLMs Hallucinate on Structured Knowledge: A Mechanistic Analysis of Reasoning over Linearized Representations
May 25, 2026Shanghao Li, Jinda Han, Yibo Wang +5LLM Grounding LLM Interpretability
University of Illinois Chicago · University of Illinois Urbana-Champaign
Reasoning Error from Known Fact: Step-Level Self-Consistency Group Relative Policy Optimization for LLMs
Jul 21, 2026Xiaomeng Hu, Jiaqi Hu, Hao Chen +4RL for Language Model Reasoning Hallucination in Language Models
Zhejiang University
Detecting Hallucination in LLMs: Tracing the Topological Signatures of Impaired Context Sharing
Sep 17, 2026Amir Jalilifard, Anderson Rocha, Eric Wong +1LLM Hallucination Detection Hallucination in Language Models
Institute of Computing, Universidade Estadual de Campinas (UNICAMP), Campinas, SP, Brazil · Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA, USA

May 25, 2026J/K move · Enter open · S save

Why LLMs Hallucinate on Structured Knowledge: A Mechanistic Analysis of Reasoning over Linearized Representations

Shanghao Li, Jinda Han, Yibo Wang, Yuanjie Zhu+4

University of Illinois Chicago · University of Illinois Urbana-Champaign

LLM Grounding LLM Interpretability Hallucination in Language Models LLM Hallucination Detection

Open paper AskPDF arXiv

In many reasoning tasks, large language models (LLMs) rely on structured external knowledge, such as graphs and tables, which is typically linearized into sequential token representations. However, even when sufficient knowledge is available, LLMs can still produce hallucinated outputs, and the underlying mechanisms behind such failures remain poorly understood. We investigate these mechanisms and find that hallucinations arise from systematic internal dynamics rather than random noise. First, attention disproportionately concentrates toward shortcut-like structural cues rather than distributing across the full context. Second, feed-forward representations fail to ground the provided knowledge, causing the model to revert to parametric memory. Moreover, our results indicate that hallucination is consistently associated with failures in semantic grounding within feed-forward layers, while attention allocation exhibits greater task-dependent variability. Finally, we show that these mechanistic patterns generalize beyond single-hop graphs to multi-hop and tabular settings, enabling effective hallucination detection across structured knowledge formats.

Abstract

Hallucination in Language Models

Explore similar work

Why LLMs Hallucinate on Structured Knowledge: A Mechanistic Analysis of Reasoning over Linearized Representations

Reasoning Error from Known Fact: Step-Level Self-Consistency Group Relative Policy Optimization for LLMs

Detecting Hallucination in LLMs: Tracing the Topological Signatures of Impaired Context Sharing