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.
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 ( Δ 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 ( dmodel )
512
Sequence length (block size)
128
Learning rate
5×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 ( dmodel )
512
FFN hidden size
2.8×dmodel
2.8×dmodel
2.8×dmodel
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.
#community_pin_pout
epoch-1
epoch-7
epoch-49
time (ms)
10_0.3_0.01
0.992±0.00
0.998±0.00
0.983±0.00
1197.10
10_0.6_0.01
0.998±0.00
0.999±0.00
0.997±0.00
1805.54
50_0.3_0.01
0.904±0.02
0.979±0.04
0.888±0.14
324.62
50_0.6_0.01
0.967±0.07
0.978±0.02
0.898±0.03
375.81
100_0.1_0.01
0.952±0.01
0.959±0.01
0.851±0.00
199.79
100_0.1_0.02
0.962±0.002
0.970±0.003
0.831±0.011
393.95
Appendix
Table 3: Performance under different graph structures
Figure 9: Path compression in knowledge graph data.
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.
Shanghao Li, Jinda Han, Yibo Wang +5
University of Illinois Chicago · University of Illinois Urbana-Champaign
With the rapid advancement of large language models (LLMs), modern systems not only possess strong foundational capabilities and extensive knowledge, but can also solve complex problems via long, multi-step reasoning. However, as reasoning traces become longer, LLMs may produce a substantial amount of hallucinated content during the reasoning process, which is often difficult to detect. In this work, we conduct a fine-grained analysis of hallucinations arising in LLM reasoning and find that the reasoning traces are particularly prone to Context-Sensitive Factual Hallucinations: cases where the model actually has the relevant knowledge, yet makes factual errors due to contextual interference during reasoning. To address this issue, we propose Step-level Self-Consistency Group Relative Policy Optimization (SSC-GRPO), which assigns step-level rewards to reasoning traces by computing self-consistency scores of individual steps across multiple rollouts. Compared with prior methods, SSC-GRPO achieves state-of-the-art performance on both mathematical reasoning benchmarks and hallucination leaderboards. Our results offer a new perspective for detecting and mitigating hallucinations in the reasoning process of large language models.
In this work, we examine the topology of information flow patterns within attention graphs to effectively distinguish hallucinated from non-hallucinated responses. We analyze the Forman-Ricci curvature to identify structural patterns indicating information bottlenecks in attention graphs. We then introduce a method that captures both semi-local and global information-flow characteristics of attention heads associated with hallucinated responses. We evaluate our approach extensively across several LLMs and established benchmarks. Empirical results demonstrate that our proposed single-pass approach provides consistent improvements over existing attention-based and multi-response baselines across two hallucination-detection benchmarks, while achieving competitive performance across diverse LLM architectures. Further analysis reveals that impaired context sharing among tokens during causal generation is strongly associated with hallucination occurrences in LLMs. In particular, hallucinated responses are consistently characterized by an over-reliance on self-attention, diffused context retrieval from earlier tokens, or information over-squashing, especially in the final transformer layer.
Amir Jalilifard, Anderson Rocha, Eric Wong +1
Institute of Computing, Universidade Estadual de Campinas (UNICAMP), Campinas, SP, Brazil · Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA, USA