# Hallucination is Inevitable: An Innate Limitation of Large Language Models

arXiv: https://arxiv.org/abs/2401.11817 · HTML: https://mlsanity.com/paper/2401.11817/

## Key facts

- Cited by 332 papers in the map (data through 14 Oct 2026).
- Builds on 47 of its 72 references that are in the map.
- First posted on arXiv 22 Jan 2024.

## Builds on (most cited first, 30 of 47)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [TruthfulQA: Measuring How Models Mimic Human Falsehoods](https://mlsanity.com/paper/2109.07958/) (2021)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [The Pile: An 800GB Dataset of Diverse Text for Language Modeling](https://mlsanity.com/paper/2101.00027/) (2020)
- [Survey of Hallucination in Natural Language Generation](https://mlsanity.com/paper/2202.03629/) (2022)
- [A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions](https://mlsanity.com/paper/2311.05232/) (2023)
- [When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non-Parametric Memories](https://mlsanity.com/paper/2212.10511/) (2022)
- [Scheduled Sampling for Sequence Prediction with Recurrent Neural Networks](https://mlsanity.com/paper/1506.03099/) (2015)
- [Deduplicating Training Data Makes Language Models Better](https://mlsanity.com/paper/2107.06499/) (2021)
- [Siren's Song in the AI Ocean: A Survey on Hallucination in Large Language Models](https://mlsanity.com/paper/2309.01219/) (2023)
- [Retrieval Augmentation Reduces Hallucination in Conversation](https://mlsanity.com/paper/2104.07567/) (2021)
- [Sequence Level Training with Recurrent Neural Networks](https://mlsanity.com/paper/1511.06732/) (2015)
- [Large Language Models Struggle to Learn Long-Tail Knowledge](https://mlsanity.com/paper/2211.08411/) (2022)
- [NeMo Guardrails: A Toolkit for Controllable and Safe LLM Applications with Programmable Rails](https://mlsanity.com/paper/2310.10501/) (2023)
- [Check Your Facts and Try Again: Improving Large Language Models with External Knowledge and Automated Feedback](https://mlsanity.com/paper/2302.12813/) (2023)
- [HaluEval: A Large-Scale Hallucination Evaluation Benchmark for Large Language Models](https://mlsanity.com/paper/2305.11747/) (2023)
- [Trusting Your Evidence: Hallucinate Less with Context-aware Decoding](https://mlsanity.com/paper/2305.14739/) (2023)
- [Chain-of-Verification Reduces Hallucination in Large Language Models](https://mlsanity.com/paper/2309.11495/) (2023)
- [FreshLLMs: Refreshing Large Language Models with Search Engine Augmentation](https://mlsanity.com/paper/2310.03214/) (2023)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Data and its (dis)contents: A survey of dataset development and use in machine learning research](https://mlsanity.com/paper/2012.05345/) (2020)
- [Automatically Correcting Large Language Models: Surveying the landscape of diverse self-correction strategies](https://mlsanity.com/paper/2308.03188/) (2023)
- [Survey on Factuality in Large Language Models: Knowledge, Retrieval and Domain-Specificity](https://mlsanity.com/paper/2310.07521/) (2023)
- [Factuality Enhanced Language Models for Open-Ended Text Generation](https://mlsanity.com/paper/2206.04624/) (2022)
- [Large Language Models with Controllable Working Memory](https://mlsanity.com/paper/2211.05110/) (2022)
- [Breaking the Softmax Bottleneck: A High-Rank RNN Language Model](https://mlsanity.com/paper/1711.03953/) (2017)

## Built on by (most cited first, 30 of 332)

- [Scaling Synthetic Data Creation with 1,000,000,000 Personas](https://mlsanity.com/paper/2406.20094/) (2024)
- [AbstentionBench: Reasoning LLMs Fail on Unanswerable Questions](https://mlsanity.com/paper/2506.09038/) (2025)
- [Advances and Challenges in Foundation Agents: From Brain-Inspired Intelligence to Evolutionary, Collaborative, and Safe Systems](https://mlsanity.com/paper/2504.01990/) (2025)
- [Emergent social conventions and collective bias in LLM populations](https://mlsanity.com/paper/2410.08948/) (2024)
- [A Survey on Uncertainty Quantification of Large Language Models: Taxonomy, Open Research Challenges, and Future Directions](https://mlsanity.com/paper/2412.05563/) (2024)
- [InstructRAG: Instructing Retrieval-Augmented Generation via Self-Synthesized Rationales](https://mlsanity.com/paper/2406.13629/) (2024)
- [HaloScope: Harnessing Unlabeled LLM Generations for Hallucination Detection](https://mlsanity.com/paper/2409.17504/) (2024)
- [Fast Adversarial Attacks on Language Models In One GPU Minute](https://mlsanity.com/paper/2402.15570/) (2024)
- [MLLM can see? Dynamic Correction Decoding for Hallucination Mitigation](https://mlsanity.com/paper/2410.11779/) (2024)
- [Speculative RAG: Enhancing Retrieval Augmented Generation through Drafting](https://mlsanity.com/paper/2407.08223/) (2024)
- [AgentRxiv: Towards Collaborative Autonomous Research](https://mlsanity.com/paper/2503.18102/) (2025)
- [SafeBench: A Safety Evaluation Framework for Multimodal Large Language Models](https://mlsanity.com/paper/2410.18927/) (2024)
- [Building Guardrails for Large Language Models](https://mlsanity.com/paper/2402.01822/) (2024)
- [Large language models for automated scholarly paper review: A survey](https://mlsanity.com/paper/2501.10326/) (2025)
- [Missing Premise exacerbates Overthinking: Are Reasoning Models losing Critical Thinking Skill?](https://mlsanity.com/paper/2504.06514/) (2025)
- [A Survey of LLM-Driven AI Agent Communication: Protocols, Security Risks, and Defense Countermeasures](https://mlsanity.com/paper/2506.19676/) (2025)
- [Determinants of LLM-assisted Decision-Making](https://mlsanity.com/paper/2402.17385/) (2024)
- [A Closer Look at Machine Unlearning for Large Language Models](https://mlsanity.com/paper/2410.08109/) (2024)
- [Visual Agents as Fast and Slow Thinkers](https://mlsanity.com/paper/2408.08862/) (2024)
- [RACER: Rich Language-Guided Failure Recovery Policies for Imitation Learning](https://mlsanity.com/paper/2409.14674/) (2024)
- [Large Language Models Hallucination: A Comprehensive Survey](https://mlsanity.com/paper/2510.06265/) (2025)
- [Usable XAI: 10 Strategies Towards Exploiting Explainability in the LLM Era](https://mlsanity.com/paper/2403.08946/) (2024)
- [Language Generation in the Limit](https://mlsanity.com/paper/2404.06757/) (2024)
- [Benchmarking Language Model Creativity: A Case Study on Code Generation](https://mlsanity.com/paper/2407.09007/) (2024)
- [FiDeLiS: Faithful Reasoning in Large Language Model for Knowledge Graph Question Answering](https://mlsanity.com/paper/2405.13873/) (2024)
- [Unveiling the Safety of GPT-4o: An Empirical Study using Jailbreak Attacks](https://mlsanity.com/paper/2406.06302/) (2024)
- [Visual Large Language Models for Generalized and Specialized Applications](https://mlsanity.com/paper/2501.02765/) (2025)
- [RAG-DDR: Optimizing Retrieval-Augmented Generation Using Differentiable Data Rewards](https://mlsanity.com/paper/2410.13509/) (2024)
- [Position: Multimodal Large Language Models Can Significantly Advance Scientific Reasoning](https://mlsanity.com/paper/2502.02871/) (2025)
- [LLaMP: Large Language Model Made Powerful for High-fidelity Materials Knowledge Retrieval and Distillation](https://mlsanity.com/paper/2401.17244/) (2024)

## Abstract (arXiv)

Hallucination has been widely recognized to be a significant drawback for large language models (LLMs). There have been many works that attempt to reduce the extent of hallucination. These efforts have mostly been empirical so far, which cannot answer the fundamental question whether it can be completely eliminated. In this paper, we formalize the problem and show that it is impossible to eliminate hallucination in LLMs. Specifically, we define a formal world where hallucination is defined as inconsistencies between a computable LLM and a computable ground truth function. By employing results from learning theory, we show that LLMs cannot learn all the computable functions and will therefore inevitably hallucinate if used as general problem solvers. Since the formal world is a part of the real world which is much more complicated, hallucinations are also inevitable for real world LLMs. Furthermore, for real world LLMs constrained by provable time complexity, we describe the hallucination-prone tasks and empirically validate our claims. Finally, using the formal world framework, we discuss the possible mechanisms and efficacies of existing hallucination mitigators as well as the practical implications on the safe deployment of LLMs.