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

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.

Large language models can produce answers that sound fluent and confident, yet hallucinate with respect to either the given prompt or real-world knowledge. This paper analyzes when such reasoning errors emerge during training and why they occur. We study this problem by viewing reasoning as traversal over a graph: entities or reasoning steps are represented as nodes, while valid relations define paths between them. Under this view, a model should follow the graph structure provided in the prompt or encoded in its learned knowledge. However, we identify two common failure patterns. Early in training, the model may reuse paths from other subgraphs even when they do not match the current prompt. Later in training, it may compress frequently observed multi-step paths into shortcuts, skipping important intermediate steps. These two behaviors help explain why hallucinations can persist even as training loss continues to improve. Our findings provide a clearer framework for diagnosing unfaithful reasoning and may guide future training methods that encourage models to follow valid reasoning paths more reliably.