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.

本研究证明，在大型语言模型中消除幻觉是不可能的，因为我们定义了一个形式世界，其中幻觉被定义为一个可计算的语言模型与一个可计算的真实函数之间的不一致性。通过使用学习理论的结果，我们表明语言模型无法学习所有的可计算函数，因此它们将始终产生幻觉。此外，我们还描述了真实世界中受幻觉影响的任务，并通过实证验证了我们的论点。最后，我们讨论了现有幻觉减轻方法的可能机制和功效，以及对安全部署大型语言模型的实际影响。

幻觉是不可避免的：大型语言模型的固有限制

Hallucination is Inevitable: An Innate Limitation of Large Language  Models

Given any collection F of computable functions over the reals, we show that
there exists an algorithm that, given any L_F-sentence \varphi containing only
bounded quantifiers, and any positive rational number \delta, decides either
"\varphi is true", or "a \delta-strengthening of \varphi is false". Under mild
assumptions, for a C-computable signature F, the \delta-decision problem for
bounded \Sigma_k-sentences in L_F resides in (\Sigma_k^P)^C. The results stand
in sharp contrast to the well-known undecidability results, and serve as a
theoretical basis for the use of numerical methods in decision procedures for
nonlinear first-order theories over the reals.

通过计算机函数和序列，本研究提出了一种可将有限次量化的公式转化为真或伪命题的算法，同时为实现数值法在实际应用中为非线性全序实数域决策程序提供了理论基础。