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

• URL: http://arxiv.org/abs/2604.03557v1
• Date: Sat, 04 Apr 2026 02:51:46 GMT
• Title: When Do Hallucinations Arise? A Graph Perspective on the Evolution of Path Reuse and Path Compression
• Abstract summary: Reasoning hallucinations in large language models (LLMs) often appear as fluent yet unsupported conclusions that violate either the given context or underlying factual knowledge.<n>We show that reasoning hallucinations arise from two fundamental mechanisms: textbfPath Reuse, where memorized knowledge overrides contextual constraints during early training, and textbfPath Compression, where frequently traversed multi-step paths collapse into shortcut edges in later training.
• Score: 41.881697211314396
• License: http://creativecommons.org/licenses/by/4.0/
• 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: \textbf{Path Reuse}, where memorized knowledge overrides contextual constraints during early training, and \textbf{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.

Related papers

• HIVE: Understanding Post-Hallucination Reasoning in Vision Language Models [70.67112531913669]
  Hallucinations in vision language models are commonly treated as semantic errors.<n>Prior work mainly focuses on detecting or suppressing hallucinations at generation time.<n>We study Post Hallucination Reasoning (PHR), the stage in which hallucinated semantics enter the model's inference context.
  arXiv  Detail & Related papers  (2026-07-08T15:02:11Z)
• Why LLMs Hallucinate on Structured Knowledge: A Mechanistic Analysis of Reasoning over Linearized Representations [36.45654492179688]
  We find that hallucinations arise from systematic internal dynamics rather than random noise.<n>First, attention disproportionately concentrates toward shortcut-like structural cues rather than distributing across the full context.<n>Second, feed-forward representations fail to ground the provided knowledge, causing the model to revert to parametric memory.
  arXiv  Detail & Related papers  (2026-05-25T22:08:59Z)
• Seeing Through the Chain: Mitigate Hallucination in Multimodal Reasoning Models via CoT Compression and Contrastive Preference Optimization [78.94590726578014]
  multimodal reasoning models (MLRMs) remain prone to hallucinations, and effective solutions are still underexplored.<n>We propose C3PO, a training-based mitigation framework comprising textbfCompression and textbfPreference textbfOptimization.
  arXiv  Detail & Related papers  (2026-02-03T11:00:55Z)
• Distributional Semantics Tracing: A Framework for Explaining Hallucinations in Large Language Models [4.946483489399819]
  Large Language Models (LLMs) are prone to hallucination, the generation of factually incorrect statements.<n>This work investigates the intrinsic, architectural origins of this failure mode through three primary contributions.
  arXiv  Detail & Related papers  (2025-10-07T16:40:31Z)
• How Large Language Models are Designed to Hallucinate [0.42970700836450487]
  We argue that hallucination is a structural outcome of the transformer architecture.<n>Our contribution is threefold: (1) a comparative account showing why existing explanations are insufficient; (2) a predictive taxonomy of hallucination linked to existential structures with proposed benchmarks; and (3) design directions toward "truth-constrained" architectures capable of withholding or deferring when disclosure is absent.
  arXiv  Detail & Related papers  (2025-09-19T16:46:27Z)
• How do Transformers Learn Implicit Reasoning? [67.02072851088637]
  We study how implicit multi-hop reasoning emerges by training transformers from scratch in a controlled symbolic environment.<n>We find that training with atomic triples is not necessary but accelerates learning, and that second-hop generalization relies on query-level exposure to specific compositional structures.
  arXiv  Detail & Related papers  (2025-05-29T17:02:49Z)
• Auditing Meta-Cognitive Hallucinations in Reasoning Large Language Models [12.747507415841168]
  We study the causality of hallucinations under constrained knowledge domains by auditing the Chain-of-Thought trajectory.<n>Our analysis reveals that in long-CoT settings, RLLMs can iteratively reinforce biases and errors through flawed reflective reasoning.<n>Surprisingly, even direct interventions at the origin of hallucinations often fail to reverse their effects, as reasoning chains exhibit 'chain disloyalty'
  arXiv  Detail & Related papers  (2025-05-19T14:11:09Z)
• Why and How LLMs Hallucinate: Connecting the Dots with Subsequence Associations [82.42811602081692]
  This paper introduces a subsequence association framework to systematically trace and understand hallucinations.<n>Key insight is hallucinations that arise when dominant hallucinatory associations outweigh faithful ones.<n>We propose a tracing algorithm that identifies causal subsequences by analyzing hallucination probabilities across randomized input contexts.
  arXiv  Detail & Related papers  (2025-04-17T06:34:45Z)
• In-Context Sharpness as Alerts: An Inner Representation Perspective for Hallucination Mitigation [36.31646727970656]
  Large language models (LLMs) frequently hallucinate and produce factual errors. correct generations tend to have sharper context activations in the hidden states of the in-context tokens, compared to the incorrect ones. We propose an entropy-based metric to quantify the sharpness'' among the in-context hidden states and incorporate it into the decoding process.
  arXiv  Detail & Related papers  (2024-03-03T15:53:41Z)
• Exposing Attention Glitches with Flip-Flop Language Modeling [55.0688535574859]
  This work identifies and analyzes the phenomenon of attention glitches in large language models. We introduce flip-flop language modeling (FFLM), a family of synthetic benchmarks designed to probe the extrapolative behavior of neural language models. We find that Transformer FFLMs suffer from a long tail of sporadic reasoning errors, some of which we can eliminate using various regularization techniques.
  arXiv  Detail & Related papers  (2023-06-01T17:44:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.