Introduction
Large Language Models (LLMs) are notorious for producing fluent yet entirely unsupported conclusions—a phenomenon widely known as hallucination. Historically, research has categorized these errors based on what they are (e.g., fact-conflicting versus input-conflicting). However, the mechanisms by which decoder-only Transformers actually produce them have remained poorly understood.
This paper shifts the focus from what to why, reinterpreting LLM reasoning as a search process over an underlying "knowledge graph." By modeling next-token prediction as a transition between nodes (entities) via learned edges (transitions), the authors provide a unified framework that explains why models ignore context or skip logical steps.
Intrinsic vs. Extrinsic Reasoning
To understand hallucinations, the authors distinguish between two types of reasoning:
- Intrinsic Reasoning: Contextual reasoning that acts as a constrained search over a provided subgraph (i.e., following the rules and facts provided in a prompt).
- Extrinsic Reasoning: Context-free queries that rely on memorized, global structures in the underlying graph (i.e., relying on pre-trained memory).
Hallucinations occur when there is a disconnect or conflict between these two modes. The researchers propose a "Mixture of Transition Matrices" hypothesis, suggesting that Transformers do not merely learn single-step transitions; they learn a weighted average of multi-hop connections. This mathematical reality drives the model's urge to take logical "shortcuts."
Two Fundamental Mechanisms of Hallucination
Through controlled training dynamics, the study identifies two distinct, training-driven mechanisms that cause reasoning failures:
1. Path Reuse (Global Before Local)
During early training, models learn the "big picture" global structure of the graph before they learn to obey the specific, local constraints of a prompt. This leads to Path Reuse, where memorized knowledge overrides contextual constraints. The model essentially ignores the provided context and outputs a path it has memorized from its broader training data.
2. Path Compression (The Overfitting Shortcut)
As models continue to train, they begin to "compress" multi-step reasoning. If a model frequently traverses the path $A \to B \to C$, it eventually collapses this sequence into a direct shortcut edge: $A \to C$. While this appears efficient, it is a structural hallucination because it bypasses necessary intermediate logic (the "bridge nodes").
Interestingly, Path Compression also provides a structural explanation for the Reversal Curse (why models know "A is B" but not "B is A"). Because compression is directional and collapses specific sequences, the inverse path remains weakly represented and is often skipped.
Experimental Setup and Datasets
To isolate these variables, the researchers moved beyond black-box observation by utilizing synthetic graph environments:
- Synthetic Graphs: Erdős–Rényi (ER) graphs for uniform connectivity and Stochastic Block Models (SBM) to simulate "communities" of knowledge.
- Natural Language Stories: Using Gemini-2.5-lite, synthetic graph paths were translated into 80-word interpersonal stories to test if hallucination patterns persist when the graph is hidden within prose.
- Real-World Benchmarks: The team analyzed community structures in DocRED (knowledge graphs), GSM8K (math reasoning), and APPS (code), confirming that real-world data mirrors the "cluster-and-bridge" structure of their synthetic models.
- Models: Llama-2, Qwen-2, and Mixtral architectures were trained from scratch to observe these dynamics.
Key Findings
- The Accuracy Gap: In early training, models exhibit high "Exist Accuracy" (predicting an edge that exists somewhere in the global graph) but low "Local Accuracy" (following the specific prompt).
- Compression Peaks in Communities: Path compression is most severe in graphs with many distinct communities. In SBM graphs with 100 communities, accuracy dropped significantly from 0.95 to 0.80 as the model aggressively skipped bridge nodes.
- Architecture Invariance: The decline in the "Uncompressed Ratio" was observed across all tested architectures (Llama-2, Qwen-2, Mixtral), proving this is a fundamental byproduct of the next-token prediction objective, not a specific model quirk.
- PPO Outperforms SFT: Reinforcement Learning from Human Feedback—specifically Proximal Policy Optimization (PPO)—is significantly better at fixing path compression than Supervised Fine-Tuning (SFT). PPO achieved an accuracy improvement of ~0.3, whereas SFT often led to model collapse when applied to heavily compressed checkpoints.
Limitations and Future Directions
While this graph perspective offers a powerful diagnostic tool, the authors note that it primarily applies to decoder-only Transformers; dynamics may differ in encoder-decoder architectures. Additionally, "nodes" in real-world reasoning (like abstract concepts) are inherently fuzzier than discrete nodes in synthetic graphs.
Looking ahead, this research opens the door to structurally grounded training objectives. Instead of relying solely on next-token prediction, future loss functions could explicitly penalize the skipping of intermediate logical steps, paving the way for "graph-aware" LLMs that remain faithful to their provided context.
Summary updated