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

Opening Remark: We thank the reviewer for the constructive and valuable feedback. We are honored that the reviewer recognized the rigorous theoretical connection between transformer structures and subsequence embeddings, as well as the alignment of our approach with training corpus statistics. We are equally pleased that the reviewer found our paper clearly written, well-motivated, and effectively supported by intuitive examples and visualizations. Additionally, we appreciate the acknowledgment of the significance and originality of our subsequence association framework, particularly its unified and broadly applicable approach to interpreting and addressing hallucination in LLMs. We have addressed the reviewer’s comments and concerns below.

Alignment Between SAT's Optimization Target and Evaluation Metric

Thank you for highlighting this important methodological point. We acknowledge your concern about potential circularity, but respectfully clarify our perspective. When a metric captures a valuable property—in our case, the reproducibility of hallucination-triggering patterns—it is common and beneficial to design algorithms that optimize for that property. Our work introduces a novel and underexplored perspective that prioritizes the reproducibility of hallucination phenomena across diverse contexts, which is more convincing than existing attribution metrics that focus solely on local input perturbations.

For clarity, we summarize the key distinctions between traditional methods and our approach in the following table:

Multiple Subsequences Trigger Cases

Great point! Our beam-search-based tracing algorithm indeed maintains a pool of subsequences (size $B$), enabling us to identify multiple non-contiguous subsequences associated with hallucinations. Although our primary evaluation focuses on the strongest individual subsequence to maintain comparability with existing methods—which typically produce single-attribution scores—our method naturally extends to assessing top-K subsequences. We emphasize this potential in our discussion. The lack of established baselines capable of attributing multiple subsequences limits comparative evaluations at this stage, highlighting an important direction for future work.

Ablation Study on Hyperparameter Sensitivity

Absolutely! We provide detailed ablation studies on hyperparameter sensitivity in Appendix C.3, focusing on the beam search width (B), the perturbation corpus size, and also the top-k value ( length ratio α in Figure 4).

Our key finding is that increasing beam size (B) and enlarging the perturbation corpus consistently enhance the accuracy of SAT in identifying causal subsequences, as these adjustments yield more precise approximations. Nevertheless, we observe diminishing returns accompanied by significantly increased computational costs. Therefore, in the main paper, we select B = 20 and a perturbation corpus size of 500, achieving an optimal balance between performance gains and computational efficiency.

Additional Evaluation via Human Annotation and Intervention Studies

Great suggestion! Direct human annotation of the ground truth subsequences causing hallucinations can be challenging, as human judgments may not align with the internal rationales of LLMs. Instead, we adopt an indirect yet effective approach: we evaluate the reproducibility of hallucination phenomena using human-generated natural sentences containing candidate subsequences. Specifically, we sample document chunks from Dolma—the pretraining corpus for Olmo models—as a proxy for human distribution, and use them to calculate the reproducibility metric ($S_{rep}$). The comparative results demonstrating SAT’s superior performance are provided below:

We thank the reviewer for the constructive and valuable feedback.

Suggestion on the Writing Improvement

Following your suggestion, we have made several improvements to enhance readability and structure in the revised version:

a) Clarification of Key Ideas: We have significantly improved the clarity of key concepts in both the Introduction and Method sections by adding intuitive explanations complemented with illustrative examples (Figure 1).

b) Algorithm Placement: Previously, due to space constraints, the full algorithm was moved to Appendix A. Recognizing the importance of immediate clarity, we have now integrated the algorithm back into the main text to provide direct context and enhance readability.

c) Streamlined Experimental Section: We have condensed and clearly structured the experimental evaluation details in Section 4. The updated, succinctly organized subsection is as follows:

\subsection{Experimental Evaluation Setting}

\paragraph{Overview} We aim to provide a systematic evaluation that was conducted on six programmatically verifiable domains from HALoGEN, comparing our Subsequence Association Trace (SAT) method against four attribution baselines on both a small (Olmo-7B-instruct) and a large (Llama-70B-instruct) model. We measure the ability of each method to identify input subsequences that reproducibly trigger a target hallucination subsequence, using a reproducibility rate metric ($S_{\mathrm{rep}}$)...

\paragraph{Datasets} We adopt six HALoGEN domains, each providing programmatic verification of atomic hallucinated facts to avoid subjective judgment: ...

\paragraph{Models} a) Olmo-7B-instruct (decoder-only, 7B parameters), pre-trained on Dolma-1.7 (400M documents); b) Llama-70B-instruct (70B parameters);

\paragraph{Metric}: Reproducibility Rate ($S_{\mathrm{rep}}$) ... (with detailed response in the last response section.)

\paragraph{Baselines}: 
We compare against four widely used attribution techniques, adapted to subsequences by summing token saliency over all target tokens in $\tilde o_h$: ...

We are open and responsive to any additional feedback you may have. We hope these revisions enhance the manuscript’s clarity and readability.

Broader Impact to Benefit Future Research for the Community

The primary goal of our paper is to establish a unified framework that helps practitioners and researchers understand why and how hallucinations arise in large language models (LLMs). By doing so, we enable a "debugging" strategy that identifies which problematic subsequences trigger these hallucinations and where they might have originated in the training data. Below, we highlight several practical implications:

1. Actionable Diagnosis and Debugging
   Traditionally, when an LLM like GPT-4 returns an incorrect answer (e.g., summarizing the wrong paper), users or developers can only make broad guesses such as “the model must be confused” or “the prompt might have been poorly phrased.” Our framework offers a more systematic explanation, showing that the subsequence [ar, https, ://, ar, xiv, /pdf, 141, 0, ., 6] (Fig. 5) triggers the hallucinated paper consistently across various contexts. Users can then reproduce and isolate the error across multiple prompts that include this problematic subsequence. Tracing the source of these associations back to specific training documents enables developers to either refine their training data or adjust certain associations through targeted fine-tuning.

2. Advancing Hallucination Detection Methods
   Current hallucination detection techniques often rely on (a) uncertainty scores—flagging low-confidence outputs as potentially hallucinatory—or (b) consistency checks (e.g., sampling multiple times and marking inconsistent outputs as hallucinations). However, as discussed in Section 2.2, if the “hallucinatory subsequence” strongly outweighs the faithful subsequence, the model may remain confident in its incorrect output, evading both uncertainty- and consistency-based checks. Our framework highlights why such approaches can miss high-confidence, repetitive hallucinations, thereby opening pathways for more sophisticated detection methods that look directly at the internal associations rather than just the model’s surface-level outputs.

3. Guidance for Prompt Engineering
   In everyday prompting, users often combine popular and less common elements. For instance, a well-known paper title followed by a rarely cited link may cause the model to generate a hallucination that aligns more with the popular element while ignoring the lower-frequency or less-canonical portion of the prompt. Recognizing this dynamic enables more careful prompt design: if a crucial but low-frequency piece of information is included, one must be vigilant that it might be overshadowed by a popular conflicting subsequence.

4. Informed Training Corpus Design
   Our findings suggest that if an important piece of knowledge appears only in narrowly defined contexts, the model may inadvertently form stronger associations with other, more common elements—leading to hallucinations. Thus, to ensure faithful performance on specific knowledge, developers can:

   • Increase diversity of contexts: Introduce the key concept in multiple, varied settings.
   • Use data augmentation: Shuffle or re-contextualize data to break unfaithful subsequence associations.

   For example, if we regularly see “Elvis Crespo” appear in contexts also mentioning “Víctor Manuelle,” this might lead to an unintended conflation of the two. Spreading mentions of “Elvis Crespo” across different contexts mitigates this risk.

5. Motivation for Future Research
   Finally, our framework lays the groundwork for developing:

   • Robust hallucination detection methods that effectively handle high-confidence or reproducible hallucinations (rather than relying on surface-level uncertainty).
   • Embedding visualization techniques that identify recurring patterns in hallucinatory subsequence associations.
   • Targeted training-data augmentation to disrupt undesirable subsequence associations.

In summary, our proposed subsequence association framework represents a practical step toward systematically diagnosing and mitigating hallucinations. By pinpointing the exact triggers and tracing them back to specific training patterns, this approach helps developers refine data, improve prompts, and design more robust LLMs.

Selection of Domains from HALoGEN

Great question! Our primary goal is to reliably compare the reproducibility of specific hallucination phenomena, which necessitates clearly defined and deterministic hallucination targets. Therefore, we selected domains within HALoGEN that predominantly employ objective, programmatic verification methods, as opposed to relying on an LLM-based judge.

In contrast, other HALoGEN domains such as "Text Summarization," "Text Simplification," and "Historical Events" utilize an LLM verifier, making hallucination identification less deterministic and potentially subjective. For instance, in domains like "code package import," the hallucination targets are explicitly clear (e.g., referencing a non-existent code package), facilitating robust and objective measurement.

Elaboration of Metric $S_{rep}$

Certainly! The reproducibility rate $S_{rep}$ quantifies the reliability with which an identified input subsequence triggers a hallucinated output subsequence across diverse input contexts.

Intuition

Instead of just measuring whether a model produces a hallucinated span in a single context, $S_{\mathrm{rep}}$ checks if this span is consistently reproduced whenever the identified trigger subsequence is present—even after changing the rest of the prompt in diverse ways. This gives a robust measure of causal influence, not just correlation.

Step-by-Step Computation

1. Identify the Trigger: For a specific hallucinated output subsequence $\tilde o_h$, attribution methods select an input subsequence $\tilde s$ that is suspected to trigger it.

2. Contextual Perturbation: Create multiple perturbed versions of the original input, each containing $\tilde s$ but with the rest of the input replaced (masked) in various ways to simulate different possible contexts.

   • The positions not in $\tilde s$ are replaced with padding tokens.
   • These padding tokens are filled using four diverse strategies (details in paper):
     • BERT-filling
     • Random tokens
     • GPT-4o-mini completion with mask
     • GPT-4o-mini sentence with only subsequence
   • For each strategy, sample 25 perturbed inputs, leading to a diverse set of contexts ($4 \times 25 = 100$ perturbed prompts per ($\tilde s$, $\tilde o_h$) pair).

3. LLM Generation: For each perturbed input, generate the model’s output.

4. Check for Reproduction: For each output, check whether the hallucinated subsequence $\tilde o_h$ appears anywhere in the generated text.

5. Calculate Conditional Probability: For each replacement strategy, compute the proportion of perturbed inputs in which the hallucination is reproduced (i.e., the conditional probability that $\tilde o_h$ appears, given that $\tilde s$ is present in the input).

6. Aggregate Across Strategies: Average this proportion across all four replacement strategies to obtain $S_{\mathrm{rep}}$:

   $$S_{\mathrm{rep}} = \mathbb{E}_{P \in \{\text{bert, rand, gpt-m, gpt-t}\}} \left[ P(o \sqsupseteq \tilde o_h \mid s \sqsupseteq \tilde s) \right]$$

   Where $o$ is the generated output and $s$ is the perturbed input containing $\tilde s$.

Overall, $S_{rep}$ quantifies how much a hallucinated output can be reliably and reproducibly triggered by a specific input subsequence, even as the rest of the context changes, making it a powerful metric for evaluating causal attribution in LLM hallucinations.

Dear Reviewer,

As the discussion phase will close soon, I wanted to check if there are any remaining concerns or clarifications we can address. We’re happy to provide any additional details if helpful. Thank you again for your time and feedback!

Opening Remark: We thank the reviewer for the constructive and valuable feedback. We are honored that you found our framing of hallucinations as arising from associations between input subsequences and outputs both intuitive and insightful. We are equally pleased that the proposed theory aligns naturally with transformer mechanics—specifically, how each output token integrates influences from earlier input subsequences. Additionally, we appreciate your recognition of the thorough evaluation of our SAT method, as well as the strong correlation between our identified subsequence associations and patterns in the Dolma training data, which supports the validity of our approach. We have addressed the reviewer’s comments and concerns below.

Independence Assumption in Proposition 2.3

We agree with the reviewer that, in practice, the independence assumption stated in Proposition 2.3 holds only under specific conditions. As noted at the beginning of Section 2.2, our intention is to provide an intuitive perspective of hallucination phenomena rather than a rigorous proof. Theoretical results typically require certain simplifying assumptions to deliver clear insights. Under these conditions, Proposition 2.3 effectively conveys that hallucination subsequences appearing in the model's output are influenced by the cumulative effects of key subsequence associations between input and output. This intuitive interpretation typically remains valid even when the independence assumption is relaxed.

Evaluation on Top-100 Frequent Hallucination Patterns

Great question! The selection of the top-100 most frequent hallucination patterns serves a specific methodological purpose (targeting reproducible hallucinations) rather than introducing bias. Since all tracing methods in Table 2 are evaluated on identical test cases, the comparison remains fair and unbiased.

Our approach targets reproducible hallucinations—a critical distinction in hallucination research. We observe that hallucinations generally fall into two categories:

1. Reproducible hallucinations: Consistent erroneous outputs that reliably appear across multiple samples with the same prompt context.

2. Stochastic hallucinations: Random errors resulting from low-probability token sampling during decoding, occurring perhaps once in 1,000 generations.

Our framework is designed to analyze reproducible hallucinations, where the underlying causal mechanisms can be systematically studied. For stochastic hallucinations, the base reproduction rate approaches zero even with complete prompts, making it nearly impossible for any tracing method—including ours—to identify subsequences that meaningfully increase hallucination probability above baseline.

By focusing on frequent, reproducible patterns, we ensure that our evaluation measures genuine causal attribution rather than random noise. This approach enables meaningful comparison of tracing effectiveness across methods and provides actionable insights for understanding systematic hallucination behaviors in LLMs. The high-frequency nature of these patterns reflects their systematic occurrence in model behavior, making them the most relevant targets for causal analysis and potential mitigation strategies.

The Spurious Association versus Legitimate Association

Another great question! The distinction between spurious and legitimate associations indeed depends significantly on context. Consider the prompt, "The successful singer was born in New York. He never watched the Lion King. He is _____." Here, responding with "Elton John" constitutes a spurious association, as Elton John is neither an American singer nor plausibly described by the given context. This response thus reflects reliance on partial or misleading associations.

Conversely, the prompt "The successful singer who composed songs for the movie Lion King is _____." correctly establishes a legitimate association with "Elton John." Hence, the legitimacy of an association is contextually determined rather than intrinsic. Our framework specifically addresses scenarios where contextually incomplete or misleading associations lead to hallucinations, distinguishing these from valid, contextually appropriate associations.

Opening Remark: We thank the reviewer for their constructive and valuable feedback. We are honored that the reviewer finds our claims regarding hallucinations being explained by dominant subsequence associations in model representations to be reasonable and well-supported. We are equally pleased that our interpretation of transformer blocks as embedding models for these subsequences, along with the tracing method for identifying and mitigating hallucinated outputs, has been recognized positively. Additionally, we appreciate the reviewer acknowledging our empirical validation across both small and larger models against various attribution method baselines. We have addressed the reviewer’s comments and concerns below.

Comparative Analysis with Attribution Methods Focused on Local Context

Thank you for raising this insightful point! Indeed, our paper addresses a novel and relatively unexplored perspective, emphasizing the "reproducibility" of hallucination phenomena rather than traditional local-context attribution methods. We summarize the distinctions clearly below:

To our knowledge, suitable baselines explicitly designed to capture reproducibility beyond local context attribution are currently unavailable. This highlights a valuable new perspective our method introduces to the community.

Suggested comparison on AT2 method

Thank you for recommending this additional baseline! Indeed, the AT2 method introduced in [1] leverages a linear surrogate modeling approach (inspired by LIME) combined with attention weights, offering an enhanced attribution method compared to traditional attention-based approaches. We conducted an additional comparison to illustrate the relative performance:

The AT2 method indeed exhibits stronger performance compared to conventional attention and LIME-based methods, effectively identifying locally relevant subsequences. However, since AT2 remains inherently focused on local-context attribution, it does not capture the broader reproducibility of hallucination-triggering subsequences across varied contexts. Our SAT framework, specifically designed for reproducibility-based analysis, demonstrates a notable advantage, underscoring the unique value of our approach.