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

**Authors:** Ziwei Xu, Sanjay Jain, Mohan Kankanhalli  
**arXiv:** [2401.11817](https://arxiv.org/abs/2401.11817)  
**Date:** 2024-01-22  
**Summary page:** https://www.summarizepaper.com/en/paper/2401.11817v1/

## Key points

- Hallucination in large language models (LLMs) is a significant issue involving the generation of inconsistent or incorrect information.
- Previous research has focused on reducing hallucination empirically, but the authors take a formal approach to demonstrate its impossibility.
- The authors establish a framework defining hallucination as discrepancies between computable LLMs and ground truth functions.
- Learning theory insights suggest that LLMs are limited in learning all computable functions, leading to inevitable instances of hallucination.
- The limitation extends to real-world applications due to environmental complexity.
- Tasks prone to inducing hallucinations in real-world LLMs have provable time complexity constraints, confirmed through empirical validation.
- Existing strategies for mitigating hallucination within this formal framework are discussed, shedding light on potential mechanisms and their effectiveness.

## Summary

In their paper titled "Hallucination is Inevitable: An Innate Limitation of Large Language Models," authors Ziwei Xu, Sanjay Jain, and Mohan Kankanhalli address the significant issue of hallucination in large language models (LLMs). Hallucination refers to the generation of inconsistent or incorrect information by LLMs and has been a major concern in natural language processing. Previous research has focused on empirically reducing hallucination, but the authors take a formal approach to demonstrate its impossibility. They establish a framework where hallucination is defined as discrepancies between computable LLMs and ground truth functions. Drawing on insights from learning theory, they argue that LLMs are limited in their ability to learn all computable functions, leading to inevitable instances of hallucination. This limitation extends to real-world applications due to the complexity of their environments. The authors also identify tasks prone to inducing hallucinations in real-world LLMs with provable time complexity constraints and confirm their presence through empirical validation. By discussing existing strategies for mitigating hallucination within this formal framework, the authors shed light on potential mechanisms and their effectiveness in addressing this inherent limitation. Overall, this paper contributes valuable insights into understanding and managing hallucination in LLMs and highlights the challenges associated with ensuring safe deployment of these powerful language models in practical settings.