Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing

• URL: http://arxiv.org/abs/2602.00906v4
• Date: Thu, 05 Feb 2026 07:24:05 GMT
• Title: Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing
• Authors: Anxin Guo, Jingwei Li,
• Abstract summary: Large language models often hallucinate with high confidence on "random facts"<n>We formalize memorization of such facts as a membership testing problem.<n>We show that hallucinations persist as a natural consequence of lossy compression.
• Score: 3.4782736103257323
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large language models often hallucinate with high confidence on "random facts" that lack inferable patterns. We formalize the memorization of such facts as a membership testing problem, unifying the discrete error metrics of Bloom filters with the continuous log-loss of LLMs. By analyzing this problem in the regime where facts are sparse in the universe of plausible claims, we establish a rate-distortion theorem: the optimal memory efficiency is characterized by the minimum KL divergence between score distributions on facts and non-facts. This theoretical framework provides a distinctive explanation for hallucination: even with optimal training, perfect data, and a simplified "closed world" setting, the information-theoretically optimal strategy under limited capacity is not to abstain or forget, but to assign high confidence to some non-facts, resulting in hallucination. We validate this theory empirically on synthetic data, showing that hallucinations persist as a natural consequence of lossy compression.

Related papers

• HalluGuard: Demystifying Data-Driven and Reasoning-Driven Hallucinations in LLMs [20.59139155257836]
  We introduce a unified theoretical framework that decomposes hallucination risk into data-driven and reasoning-driven components.<n>We introduce HalluGuard, an NTK-based score that leverages the induced geometry and captured representations of the NTK to jointly identify data-driven and reasoning-driven hallucinations.
  arXiv  Detail & Related papers  (2026-01-26T18:23:09Z)
• Are Hallucinations Bad Estimations? [19.11290014868759]
  We show that even loss-minimizing optimal estimators still hallucinate.<n>This reframes hallucination as structural misalignment between loss minimization and human-acceptable outputs.
  arXiv  Detail & Related papers  (2025-09-25T19:39:09Z)
• Theoretical Foundations and Mitigation of Hallucination in Large Language Models [0.0]
  Hallucination in Large Language Models (LLMs) refers to the generation of content that is not faithful to the input or the real-world facts.<n>This paper provides a rigorous treatment of hallucination in LLMs, including formal definitions and theoretical analyses.
  arXiv  Detail & Related papers  (2025-07-20T15:22:34Z)
• MIRAGE: Assessing Hallucination in Multimodal Reasoning Chains of MLLM [58.2298313720146]
  Multimodal hallucinations are multi-sourced and arise from diverse causes.<n>Existing benchmarks fail to adequately distinguish between perception-induced hallucinations and reasoning-induced hallucinations.
  arXiv  Detail & Related papers  (2025-05-30T05:54:36Z)
• HalluLens: LLM Hallucination Benchmark [49.170128733508335]
  Large language models (LLMs) often generate responses that deviate from user input or training data, a phenomenon known as "hallucination"<n>This paper introduces a comprehensive hallucination benchmark, incorporating both new extrinsic and existing intrinsic evaluation tasks.
  arXiv  Detail & Related papers  (2025-04-24T13:40:27Z)
• 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)
• The Law of Knowledge Overshadowing: Towards Understanding, Predicting, and Preventing LLM Hallucination [85.18584652829799]
  We introduce a novel framework to quantify factual hallucinations by modeling knowledge overshadowing.<n>We propose a new decoding strategy CoDa, to mitigate hallucinations, which notably enhance model factuality on Overshadow (27.9%), MemoTrap (13.1%) and NQ-Swap (18.3%)
  arXiv  Detail & Related papers  (2025-02-22T08:36:06Z)
• Trust Me, I'm Wrong: LLMs Hallucinate with Certainty Despite Knowing the Answer [51.7407540261676]
  We investigate a distinct type of hallucination, where a model can consistently answer a question correctly, but a seemingly trivial perturbation causes it to produce a hallucinated response with high certainty.<n>This phenomenon is particularly concerning in high-stakes domains such as medicine or law, where model certainty is often used as a proxy for reliability.<n>We show that CHOKE examples are consistent across prompts, occur in different models and datasets, and are fundamentally distinct from other hallucinations.
  arXiv  Detail & Related papers  (2025-02-18T15:46:31Z)
• Hallucinations are inevitable but can be made statistically negligible. The "innate" inevitability of hallucinations cannot explain practical LLM issues [23.12905996928255]
  Hallucinations, a phenomenon where a language model (LM) generates nonfactual content, pose a significant challenge to the practical deployment of LMs.<n>Recent studies established a computability-theoretic result showing that any LM will inevitably generate hallucinations on an infinite set of inputs.<n>This paper claims that those "innate" inevitability results from computability theory and diagonal argument, in principle, cannot explain practical issues of LMs.
  arXiv  Detail & Related papers  (2025-02-15T07:28:40Z)
• LLMs Will Always Hallucinate, and We Need to Live With This [1.3810901729134184]
  This work argues that hallucinations in language models are not just occasional errors but an inevitable feature of these systems. It is, therefore, impossible to eliminate them through architectural improvements, dataset enhancements, or fact-checking mechanisms.
  arXiv  Detail & Related papers  (2024-09-09T16:01:58Z)
• Alleviating Hallucinations of Large Language Models through Induced Hallucinations [67.35512483340837]
  Large language models (LLMs) have been observed to generate responses that include inaccurate or fabricated information. We propose a simple textitInduce-then-Contrast Decoding (ICD) strategy to alleviate hallucinations.
  arXiv  Detail & Related papers  (2023-12-25T12:32:49Z)

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.