Hallucination is Inevitable: An Innate Limitation of Large Language Models Ziwei Xu, Sanjay Jain, Mohan Kankanhalli Abstract: Hallucination is a significant drawback for large language models (LLMs). While many efforts have been made to reduce hallucination, they are mostly empirical and cannot answer whether it can be completely eliminated. This paper formalizes the problem and shows that hallucination is inevitable for LLMs. Specifically, hallucination is defined as inconsistencies between a computable LLM and a computable ground truth function. Using learning theory, it is shown that LLMs cannot learn all computable functions and will always hallucinate. Since the formal world is part of the real world, hallucinations are also inevitable for real-world LLMs. The paper also discusses possible mechanisms and efficacies of existing hallucination mitigators and their practical implications on the safe deployment of LLMs. Introduction: The emergence of large language models (LLMs) has marked a significant milestone in artificial intelligence, particularly in natural language processing. However, one of the critical challenges they face is the problem of "hallucination," where the models generate plausible but factually incorrect or nonsensical information. This issue has brought increasing concerns about safety and ethics as LLMs are being applied widely, resulting in a growing body of literature trying to classify, understand, and mitigate it. Prior works have identified multiple possible sources of hallucination in LLMs from the data collection to the training and inference aspects. For example, in the survey paper [29], the authors attribute hallucination in natural language generation to heuristic data collection, innate divergence, imperfect representation learning, erroneous decoding, exposure bias, and parametric knowledge bias. A plethora of methods have been proposed to mitigate hallucination. For example, factual-centred metrics [19, 20, 40, 57] and benchmarks [34, 35, 65] have been proposed to measure and reduce hallucination on specific datasets. Retrieval-based methods reinforce LLM by knowledge graphs or databases to help correct factual errors in models' outputs [57, 76]. Prompting the models to reason [69] and verify [13] their answers has also been shown to reduce hallucination. Up to now, research on LLM hallucination remains largely empirical. Useful as they are, empirical studies cannot answer the fundamental question: can hallucination be completely eliminated? The answer to this question is fundamental as it indicates a possible upper limit of LLMs' abilities. However, since it is impossible to empirically enumerate and test every possible input, formal discussion on this question is impossible without a clear definition and formal analysis of hallucination. In the real world, formally defining hallucination, a factual or logical error of LLM, turns out to be extremely difficult. This is because a formal definition of semanticsHallucination is Inevitable: An Innate Limitation of Large Language Models Ziwei Xu, Sanjay Jain, Mohan Kankanhalli Abstract: Hallucination is a significant drawback for large language models (LLMs). While many efforts have been made to reduce hallucination, they are mostly empirical and cannot answer whether it can be completely eliminated. This paper formalizes the problem and shows that hallucination is inevitable for LLMs. Specifically, hallucination is defined as inconsistencies between a computable LLM and a computable ground truth function. Using learning theory, it is shown that LLMs cannot learn all computable functions and will always hallucinate. Since the formal world is part of the real world, hallucinations are also inevitable for real-world LLMs. The paper also discusses possible mechanisms and efficacies of existing hallucination mitigators and their practical implications on the safe deployment of LLMs. Introduction: The emergence of large language models (LLMs) has marked a significant milestone in artificial intelligence, particularly in natural language processing. However, one of the critical challenges they face is the problem of "hallucination," where the models generate plausible but factually incorrect or nonsensical information. This issue has brought increasing concerns about safety and ethics as LLMs are being applied widely, resulting in a growing body of literature trying to classify, understand, and mitigate it. Prior works have identified multiple possible sources of hallucination in LLMs from the data collection to the training and inference aspects. For example, in the survey paper [29], the authors attribute hallucination in natural language generation to heuristic data collection, innate divergence, imperfect representation learning, erroneous decoding, exposure bias, and parametric knowledge bias. A plethora of methods have been proposed to mitigate hallucination. For example, factual-centred metrics [19, 20, 40, 57] and benchmarks [34, 35, 65] have been proposed to measure and reduce hallucination on specific datasets. Retrieval-based methods reinforce LLM by knowledge graphs or databases to help correct factual errors in models' outputs [57, 76]. Prompting the models to reason [69] and verify [13] their answers has also been shown to reduce hallucination. Up to now, research on LLM hallucination remains largely empirical. Useful as they are, empirical studies cannot answer the fundamental question: can hallucination be completely eliminated? The answer to this question is fundamental as it indicates a possible upper limit of LLMs' abilities. However, since it is impossible to empirically enumerate and test every possible input, formal discussion on this question is impossible without a clear definition and formal analysis of hallucination. In the real world, formally defining hallucination, a factual or logical error of LLM, turns out to be extremely difficult. This is because a formal definition of semantics