Why and How LLMs Hallucinate: Connecting the Dots with Subsequence Associations

Yiyou Sun, Yu Gai, Lijie Chen, Abhilasha Ravichander, Yejin Choi, Dawn Song

TL;DR

Large Language Models (LLMs) often hallucinate because they rely on strong, learned associations between specific subsets of input tokens (subsequences) and target outputs, rather than the full context. This paper introduces a unified subsequence association framework and a tracing algorithm (SAT) that successfully identifies the exact "trigger" phrases causing hallucinations by testing their reproducibility across diverse contexts.

What Problem Does This Paper Address?

LLM hallucinations—generating content that is factually incorrect or unfaithful to the context—are notoriously difficult to debug. This difficulty stems from a complex web of entangled causes, such as overconfidence, long-tailed training data, and exposure bias.

Traditional feature attribution methods (like integrated gradients, attention maps, or LIME) only provide token-wise importance scores within a single, fixed context. They fail to establish true causal relationships or explain why a model might generate a hallucination in one prompt but behave perfectly in another. This paper addresses the need for a unified, mathematically grounded framework to trace the root causes of hallucinations across diverse contexts.

Figure 1. Hallucination examples and evidence of subsequence association in Olmo-7B (Groeneveld et al., 2024). (a) An example of a hallucination. The red blocks highlight hallucinated outputs with singers who were not born in New York. (b) Additional examples illustrating subsequence associations (using Ψ as a measure). The probability of each singer’s appearance changes with new sentences with special subsequence. These subsequence associations can be traced back to the training corpus, Dolma (Soldaini et al., 2024).

Methods

The authors propose a Subsequence Association Framework based on the insight that decoder-only transformers inherently function as subsequence embedding models.

  1. Theoretical Formulation: They prove that transformer blocks build up near-orthogonal representations of non-contiguous token sequences layer-by-layer, and the final linear layers map these embeddings directly to output logits.
  2. SAT (Subsequence Association Trace) Algorithm: Instead of measuring prediction gaps in a single context, SAT searches for input subsequences that consistently trigger the same hallucination across a variety of randomized contexts (cross-context reproducibility).
  3. Masking and Refill Strategy: To approximate the real-world input distribution without introducing filler-model bias (like BERT's internal biases), SAT generates diverse test sentences by replacing tokens with syntactically similar but semantically varied alternatives based on embedding space proximity. It then uses a beam-search-based greedy algorithm to isolate the optimal causal subsequence trigger.
Figure 3. Illustration of subsequence embedding procedure via transformer blocks and the encoding of associations within matrix parameters. Orange boxes represent embeddings for individual tokens and subsequences. Blue boxes denote transformer blocks, each comprising Multi-Head Attention (MHA) and Feed-Forward Networks (FFN). The weight matrix is highlighted in yellow boxes. Grey lines depict the flow of token information used to form the subsequence embedding for (sin, ger, New, York, El).

Datasets

The methodology was evaluated using the following resources:

  • HALoGEN: A comprehensive benchmark consisting of 10,923 prompts across nine domains. The authors focused on six programmatically verified domains (e.g., Code Package Imports, Biographies, Scientific Attribution, False Presuppositions) to ensure objective, automated identification of hallucinated subsequences.
  • Dolma-1.7: An open pre-training dataset containing approximately 3 trillion tokens used to train the Olmo-7B model. The authors used this to verify if the causal subsequences identified by SAT match actual statistical anomalies in the training corpus.

Key Insights and Ideas

  • Transformers as Subsequence Embedders: Multi-head attention (MHA) and feed-forward networks (FFN) work together to detect and embed non-contiguous token subsets. This means an LLM doesn't just look at individual words; it builds composite "trigger" features from scattered pieces of the prompt.
  • The Mechanism of Hallucination: Hallucinations occur when a dominant, incorrect subsequence association overrides the faithful context. For example, if a prompt contains "successful singer" and "born in New York," the model might output "Elton John" because the sub-association of "singer" + "El" $\rightarrow$ "Elton John" is overwhelmingly strong in its parameters, completely overshadowing the geographical constraint.
  • The Long-Tail Vulnerability: The authors prove that high-frequency subsequences dominate gradient updates during pre-training. If a fact is rare (long-tailed), the model fails to resolve the probability gap, making it highly susceptible to being hijacked by more common, superficial token associations.

Key Results

  • Superior Tracing Performance: The proposed SAT method vastly outperformed traditional baselines (Attention maps, LIME, Gradient-SHAP, ReAgent) across both small (Olmo-7B) and large (Llama-70B) models.
  • High Reproducibility: SAT achieved an average reproducibility rate ($S_{rep}$) of 46.5% on Llama-70B, which is more than double the performance of the second-best baseline (Attention at 19.8%).
  • Corpus Alignment: The hallucination triggers identified by SAT are strongly correlated ($\rho = 0.72$) with the actual conditional probabilities found in the model's training corpus (Dolma). This provides concrete empirical proof that these hallucinations are direct reflections of pre-training data distributions rather than random decoding noise.

Limitations and Future Work

  • Single-Pathway Simplification: The current analysis simplifies the problem by focusing on a single dominant hallucination pathway at a time, whereas multiple faithful or hallucinatory subsequences might compete simultaneously in practice.
  • Computational Complexity: The beam search algorithm can be computationally expensive when scaling to very long input sequences due to the exponential growth of potential token combinations.
  • Mitigation: While this paper focuses on tracing the causes, future work is needed to leverage these isolated causal subsequences to directly patch or edit model weights, mitigating hallucinations without requiring full retraining.

Summary updated

Abstract

Large language models (LLMs) frequently generate hallucinations-content that deviates from factual accuracy or provided context-posing challenges for diagnosis due to the complex interplay of underlying causes. This paper introduces a subsequence association framework to systematically trace and understand hallucinations. Our key insight is that hallucinations arise when dominant hallucinatory associations outweigh faithful ones. Through theoretical and empirical analyses, we demonstrate that decoder-only transformers effectively function as subsequence embedding models, with linear layers encoding input-output associations. We propose a tracing algorithm that identifies causal subsequences by analyzing hallucination probabilities across randomized input contexts. Experiments show our method outperforms standard attribution techniques in identifying hallucination causes and aligns with evidence from the model's training corpus. This work provides a unified perspective on hallucinations and a robust framework for their tracing and analysis.
BibTeX
@inproceedings{sun2025why,
  author = {Yiyou Sun and Yu Gai and Lijie Chen and Abhilasha Ravichander and Yejin Choi and Dawn Song},
  title = {{Why and How LLMs Hallucinate: Connecting the Dots with Subsequence Associations}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=K2Q4Jp4RbB},
}
Figure