Hallucination

34 beliefs (34 IN, 0 OUT)

The topic of hallucination in AI covers the phenomenon of language models producing outputs that are factually incorrect or fabricated, and the theoretical, mechanistic, and practical dimensions of that failure. Historically, the term was not born in NLP or chatbot research; Eric Mjolsness introduced "hallucination" in his 1986 PhD thesis in the context of computer vision, specifically face hallucination (ai-hallucination-term-coined-1986-mjolsness-computer-vision). The practical stakes are substantial: by mid-2026, over 1,300 documented AI hallucination incidents appeared in U.S. legal filings, with hundreds more in Canadian and Israeli courts (us-legal-filing-ai-hallucinations-over-1300-by-2026), and the Stanford Alpaca model—once the flagship of the open fine-tuning ecosystem—was taken offline partly over hallucination concerns (alpaca-first-llama-community-finetune-march-2023). At the mechanistic level, Anthropic's 2025 research on Claude identified internal "answer-gating" circuits that normally suppress output when information is insufficient, with hallucination emerging when that inhibition fails (anthropic-2025-answer-gating-circuit-hallucination).

Two major theoretical frameworks dominate the formal treatment of hallucination, and they operate at different levels of abstraction. The Kalai-Vempala (2023) result, published as arXiv:2311.14648v3 with Kalai at OpenAI (work done at Microsoft Research) and Vempala at Georgia Tech (kalai-venue-and-affiliations), establishes a statistical lower bound: any semantically calibrated language model must hallucinate at a rate bounded below by the monofact rate (the fraction of factoids appearing exactly once in training data) minus miscalibration and vanishing terms (kalai-vempala-calibrated-lm-must-hallucinate-monofacts-bound, kalai-2023-corollary1-lower-bound-formula). Crucially, this bound is architecture-independent, following from calibration and combinatorial counting alone rather than from transformer specifics (kalai-hallucination-architecture-independent, kalai-2023-lower-bound-is-architecture-independent), and it holds even under ideal assumptions of perfectly factual training data, single-fact documents, and no adversarial prompting (kalai-2023-hallucination-inevitable-under-perfect-conditions, kalai-ideal-data-assumption). The monofact rate is the tight bound, as shown by an explicit construction achieving that rate while maintaining calibration (kalai-2023-tightness-construction-algorithm, kalai-2023-dmf-is-tight-hallucination-lower-bound). The framework also draws a sharp distinction between arbitrary singleton facts, which are subject to the bound, and systematic or frequently recurring facts (arithmetic, rule-governed logic, popular citations), for which no such lower bound applies (kalai-two-hallucination-regimes, kalai-2023-monofact-rate-distinguishes-hallucination-types, hallucination-bound-applies-only-to-arbitrary-facts-not-systematic). A related foundational point is that the calibration requirement is genuinely distinct from KL divergence or raw accuracy: a model can be well-calibrated yet hallucinate, or hallucinate while having small KL divergence (kalai-2023-calibration-distinct-from-kl-divergence), and the semantic-level calibration metric itself is computationally intractable to evaluate on large models (kalai-2023-semantic-calibration-computationally-intractable). Separately, the document log-likelihood decomposition shows that hallucination is not merely a statistical artifact of autoregressive next-token training (document-log-likelihood-equals-sum-of-next-token-log-likelihoods).

The Xu et al. (2024) framework approaches the problem from computability and complexity theory rather than probability calibration. They formally define hallucination as a computable inconsistency between the model output and a ground-truth function on the same input, requiring both to be computable (hallucination-formal-definition-computable-inconsistency), and frame the impossibility as a universal-existential statement: for every training stage, some input is answered incorrectly (xu-2024-hallucination-formal-quantifier-structure). The proof proceeds via Cantor's diagonalization, constructing a ground-truth function by flipping diagonal entries of the model's output table, rather than through probabilistic or complexity lower-bound methods (xu-2024-proof-by-cantor-diagonalization). This yields unconditional impossibility—no computably enumerable set of LLMs is hallucination-free across all computable worlds—logically distinct from PAC unlearnability, which requires bounded-error and polynomial-time assumptions (xu-2024-unconditional-vs-pac-distinction). The framework identifies specific hallucination-prone problem classes with complexity-theoretic guarantees, including combinatorial listing, Subset Sum/SAT under P≠NP, Presburger arithmetic, and first-order logic entailment (xu-2024-hallucination-prone-problem-classes), and maps causes to three stages of the pipeline: data, training, and inference (xu-2024-three-stage-cause-mapping). A positive result states that for any computably enumerable set of well-structured task classes, a sufficiently trained LLM can be hallucination-free on that set (xu-2024-theorem-e3-positive-result), while the set of functions on which a computable LLM can be fully reliable is itself bounded by a computably enumerable set, leaving fundamentally unreachable targets such as the halting problem (xu-2024-theorem-e2-ce-set-bound).

In terms of mitigations, the knowledge base treats several approaches as partial rather than complete. RAG, introduced by Lewis et al. in 2020 (rag-lewis-2020), operates at the prompting layer to augment context with retrieved information (rag-addresses-knowledge-currency-at-prompting-layer), but it does not eliminate hallucination because the model can still misinterpret retrieved material or fabricate around it (rag-does-not-eliminate-hallucination). RLHF alignment reduces hallucination in practice but at the cost of increased Expected Calibration Error, as shown by GPT-4's ECE rising from 0.007 to 0.074 post-training (gpt4-ece-rises-0007-to-0074-post-rlhf). Per Xu et al., the only methods that genuinely bypass the impossibility theorem are those injecting information beyond the training samples—programmable guardrails, external knowledge bases, retrieval augmentation, symbolic reasoning, and human oversight—because they render the formal theorem inapplicable (xu-2024-only-external-aids-bypass-inevitability). Prompt injection and adversarial ML are noted as related but distinct security concerns alongside hallucination (prompt-injection-adversarial-ml-security-concerns). All beliefs in this group are marked IN; none have been retracted, indicating the knowledge base currently holds a consistent and unrevised picture of the hallucination landscape. The foundational premises in this cluster are the formal definitions and idealized assumptions (computability requirements, calibration definitions, ideal-data assumptions), from which the derived results—the statistical lower bounds, diagonalization proofs, and problem-class impossibility guarantees—logically follow.

IN ai-hallucination-term-coined-1986-mjolsness-computer-vision
The term 'hallucination' in AI was introduced in Eric Mjolsness's 1986 PhD thesis in the context of computer vision (face hallucination), not in NLP or chatbot contexts.
IN alpaca-first-llama-community-finetune-march-2023
Alpaca (Stanford, March 2023) was the first widely-known community fine-tune of LLaMA-7B (instruction-tuned), pioneering the open fine-tuning ecosystem, and was later taken offline over cost and hallucination concerns.
IN anthropic-2025-answer-gating-circuit-hallucination
Anthropic's 2025 research on Claude identified internal 'answer-gating' circuits that normally suppress output when information is insufficient; hallucination occurs when this inhibition fails.
IN document-log-likelihood-equals-sum-of-next-token-log-likelihoods
Document log-likelihood equals the sum of next-token log-likelihoods, meaning any probability distribution over documents can be represented as a conditional next-token distribution, so hallucination is not a statistical artifact of autoregressive training.
IN gpt4-ece-rises-0007-to-0074-post-rlhf
GPT-4's Expected Calibration Error rises from 0.007 (pre-trained) to 0.074 (post-RL/PPO) on multiple-choice tasks, indicating that RLHF alignment reduces hallucination at the cost of increased calibration error.
IN hallucination-bound-applies-only-to-arbitrary-facts-not-systematic
The Kalai-Vempala hallucination lower bound applies to arbitrary facts (5W factoids like one-off events) but explicitly excludes systematic facts (arithmetic, rule-governed logic) and frequently recurring references (book titles, citations) for which no such lower bound applies.
IN hallucination-formal-definition-computable-inconsistency
In Xu et al. (2024), hallucination is formally defined as an inconsistency between a computable LLM's output and a computable ground-truth function's output on the same input string, requiring both the model and the truth function to be computable for the argument to hold
IN hallucination-lower-bound-is-architecture-independent
The Kalai-Vempala (2023) hallucination lower bound is architecture-independent: it follows purely from probability calibration and combinatorial counting of factoids, and does not depend on using transformers, attention, or any specific model class.
IN kalai-2023-calibration-distinct-from-kl-divergence
A model can achieve near-zero miscalibration (e.g., by outputting a random factoid) while having large KL divergence, and conversely can have small KL divergence while hallucinating — the hallucination guarantee specifically requires calibration, not just good log-likelihood or accuracy.
IN kalai-2023-corollary1-lower-bound-formula
Under s-sparse regular Dworld, the hallucination rate satisfies g(H) ≥ dMF − Mis_b(g,p) − 3e^{−s}/δ − √(6ln(6/δ)/n) with probability ≥ 1−δ, where s-sparse means |F| ≤ e^{−s}|H|.
IN kalai-2023-dmf-is-tight-hallucination-lower-bound
The monofact rate (dMF), the fraction of factoids appearing exactly once in training data, is the tight (optimal) lower bound on the hallucination rate of any calibrated language model — no algorithm can guarantee a hallucination rate significantly below dMF while maintaining calibration.
IN kalai-2023-hallucination-inevitable-under-perfect-conditions
Kalai & Vempala (2023) prove that a calibrated LM must hallucinate even when training data is perfectly factual, documents contain at most one fact, and no prompt encourages fabrication — the hallucination is a statistical consequence of calibration, not a data-quality or prompting problem.
IN kalai-2023-monofact-rate-distinguishes-hallucination-types
Facts with high monofact rate (appearing only once in training, e.g., specific 5W entity attributes) are subject to the statistical hallucination lower bound, while facts with low monofact rate (e.g., popular book/article titles) have their hallucination attributed to model capacity and reference volume rather than the calibration-inevitability mechanism.
IN kalai-2023-semantic-calibration-computationally-intractable
The paper's calibration metric Mis_b(g,p) = ‖p_{V_b(g)} − g‖_TV is defined at the semantic/fact level rather than per-token probability, making it computationally intractable to evaluate on large models — a stated limitation distinct from standard token-level calibration used in classification.
IN kalai-2023-tightness-construction-algorithm
The tightness construction defines the output distribution as g(y) = dMF/|U| for unobserved factoids and (1−dMF)/|O| for observed factoids, achieving Mis∞(g,p) ≤ 3√(ln(4/δ)/n) while hallucinating at rate g(H) ≤ dMF, proving the bound cannot be improved in general.
IN kalai-hallucination-architecture-independent
The statistical lower bound on hallucination is architecture-independent, holding for transformers, RNNs, or any other architecture, as it follows from the calibration constraint alone
IN kalai-hallucination-good-turing-bound
For statistically calibrated LMs with bounded maximum fact probability, hallucination probability on singleton facts approximates the fraction of facts occurring exactly once in training data (Good-Turing estimate)
IN kalai-ideal-data-assumption
The hallucination lower bound for singleton facts holds even assuming ideal training data containing no errors whatsoever, ruling out data-quality explanations
IN kalai-two-hallucination-regimes
Singleton/arbitrary facts have an unavoidable hallucination lower bound for calibrated models, while repeated/systematic facts (e.g., publication references, arithmetic rules) have no statistical lower bound forcing hallucination
IN kalai-vempala-calibrated-lm-must-hallucinate-monofacts-bound
Kalai and Vempala (2023, OpenAI/Georgia Tech) prove that any language model satisfying semantic-level calibration must hallucinate at a rate ≥ dMF − Miscalibration − 300·|Facts|/|Possible hallucinations| − 7/√n, even with i.i.d. training data, no factual errors, and no architectural constraints.
IN kalai-venue-and-affiliations
Kalai (OpenAI, work done at Microsoft Research) and Vempala (Georgia Tech, NSF/Simons funded) published the result as arXiv:2311.14648v3 [cs.CL], March 2024
IN prompt-injection-adversarial-ml-security-concerns
Prompt injection and adversarial machine learning are recognized security concerns for LLMs, alongside hallucination as a failure mode.
IN rag-addresses-knowledge-currency-at-prompting-layer
RAG provides a prompting-layer solution to hallucination and knowledge freshness without architectural changes, operating entirely at the context level to augment model outputs with dynamically retrieved information.
IN rag-does-not-eliminate-hallucination
RAG does not eliminate hallucinations; the LLM can still misinterpret retrieved context or hallucinate around accurate source material.
IN rag-lewis-2020
Retrieval-Augmented Generation (RAG) was introduced by Lewis et al. in 2020, combining retrieval with generation to reduce hallucination
IN us-legal-filing-ai-hallucinations-over-1300-by-2026
Over 1,300 documented AI hallucination incidents occurred in U.S. legal filings by mid-2026, with 167+ in Canadian courts and 55+ in Israeli courts.
IN xu-2024-hallucination-formal-quantifier-structure
Xu et al. (2024) formally define hallucination as a ∀i ∃s statement: for every training stage i, there exists some input s such that h[i](s) ≠ f(s), meaning no matter how long training continues, some input is always answered incorrectly.
IN xu-2024-hallucination-prone-problem-classes
Xu et al. (2024) identify specific hallucination-prone problem classes: combinatorial listing (Ω(2ⁿ) time, guaranteed for O(nᵏ)-time LLMs), Subset Sum/SAT (guaranteed under P≠NP for polynomial-time LLMs), Presburger arithmetic (Ω(2^(2^(cn))) time, guaranteed for O(2ⁿ)-time LLMs), and first-order logic entailment (undecidable, guaranteed for all computable LLMs).
IN xu-2024-only-external-aids-bypass-inevitability
According to Xu et al. (2024), only methods that inject information beyond training samples—programmable guardrails, external knowledge bases, retrieval augmentation, symbolic reasoning, and human oversight—can bypass the hallucination inevitability theorem, because they make Theorem 3 inapplicable.
IN xu-2024-proof-by-cantor-diagonalization
Xu et al. (2024) prove hallucination inevitability via Cantor's diagonalization argument—constructing a ground-truth function f by flipping diagonal entries of the LLM output table (f(s_k) = Δ(ĥ_k(s_k)))—rather than via probabilistic or complexity lower-bound methods.
IN xu-2024-theorem-e2-ce-set-bound
The set of ground-truth functions on which a computable LLM can be hallucination-free is a subset of a computably enumerable set of total computable functions, meaning functions outside this set (e.g., the halting problem) are fundamentally unreachable by any LLM.
IN xu-2024-theorem-e3-positive-result
For any computably enumerable set of total computable functions, there exists an LLM that can be hallucination-free on all functions in that set given sufficient training samples, establishing that LLMs can be reliable on specific well-structured task classes.
IN xu-2024-three-stage-cause-mapping
Xu et al. 2024's three-stage causal model maps specific hallucination causes to stages: data (long-tail knowledge gaps, bias, misinformation), training (exposure bias, diluted attention, architectural deficiencies), and inference (softmax bottleneck, sampling randomness, insufficient context attention).
IN xu-2024-unconditional-vs-pac-distinction
Xu et al. 2024's hallucination impossibility result is unconditional—no computably enumerable set of LLMs is hallucination-free across all computable worlds—making it logically distinct from PAC unlearnability, which requires assumptions of bounded error rates and polynomial-time constraints.