Domain
natural language processing, machine learning, artificial intelligence
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 of the computable functions and will therefore always hallucinate.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.
This paper discusses the concept of hallucinations in large language models (LLMs), a recognized limitation that has yet to be thoroughly tested for its fundamental nature. The authors formalize hallucination as discrepancies between LLM outputs and a computable ground truth function, arguing that, due to results from learning theory, hallucination is an inevitable aspect of LLMs. They outline a formal theoretical framework where LLMs fail to learn all computable functions. Empirical studies validate the theoretical findings, indicating that state-of-the-art LLMs are indeed prone to hallucinations on certain tasks. The authors propose several implications for improving hallucination mitigators and highlight the challenges involved in deploying LLMs safely, emphasizing that hallucinations cannot be fully eliminated. Finally, the paper calls for continuous exploration of LLMs' capabilities and limitations. The main contributions include formal definitions of hallucination, empirical validations of their theoretical claims, and discussions on practical implications.
This paper employs the following methods:
- Learning Theory
- Diagonalization Argument
- Chain-of-Thought Prompting
- Retrieval-Augmented Methods
The following datasets were used in this research:
- Hallucination is inevitable for LLMs regardless of model architecture or training methods.
- State-of-the-art LLMs confirmed to be hallucination-prone in empirical studies.
The authors identified the following limitations:
- Formal definitions of hallucination were difficult to establish in a real-world context.
- Some empirical studies indicated that LLMs performed poorly on certain tasks despite high parameter counts.
- Number of GPUs: 4
- GPU Type: NVIDIA A100
hallucination
large language models
formal analysis
learning theory
computability
robustness