Hallucination is inevitable论文阅读笔记
Published:
相关定义
定义1:词表和字符串：词表是\(N\)个token的有限集合\(\mathcal{A}=\{a_0,a_1,...,a_{N-1}\}\)，字符串\(w_0 w_1...w_{n-1}\)是由词表中的token拼接组合成的序列。（这里的定义隐含了字符串和词表长度相同的意思）
定义2:大语言模型：设\(\mathcal{S}\)是词表\(\mathcal{A}\)中所有有限长字符串的可计算集合，\((s_0,s_1,...)\)是\(\mathcal{S}\)中所有元素的一对一枚举。一个大的语言模型\(h\)是一个函数，它使用函数的预测token\(h(s)\)在有限时间内补全输入字符串\(s\in\mathcal{S}\)。函数\(h\)是利用一组输入-补全对的训练样本程序化实现的。
定义3:\(P\)-proved LLMs：设P为一个以某些函数为输入并判断其是否具有指定特性的可计算函数，\(P\)-proved LLM是可以由P在指定步数内证明具有特定特性的LLM
如果将LLM视作所有可计算函数的子集，将\(P\)-proved LLM视作LLM的子集，将现实存在的LLM视作\(P\)-proved LLM的子集，则可以讲LLM描述成一个包括关系。LLMs可以根据其输出沿一个光谱上的可取性进行分类。在光谱的一侧是无意义的token预测器，它产生输入字符串的无意义的补全结果（完全幻觉）。在另一端是一个理想的无幻觉的函数，将任何形式良好的输入字符串完成为一个合理的、事实的字符串。中间就是现在的各种LLM，可以在一些输入上产生合理且符合事实的结果，但在另一些输入上会产生幻觉。
\(f\)的形式化世界：真值函数\(f\)的形式化世界是一个集合\(\mathcal{G}_f=\{(s,f(s)\vert s\in\mathcal{S})\}\)，其中\(f(s)\)是输入字符串的唯一正确补全结果。
我们只假设这样的可计算f在我们的形式世界中对于所有的任务总是存在(尽管其具体实现方式可能不得而知)。否则，我们可以立即说LLM在形式世界的某些任务上会产生幻觉，因为LLM是可计算的，而基本真值函数f是不可计算的。
训练样本：训练样本是一个集合\(\mathcal{T}=\{(s_0,f(s_0)),(s_1,f(s_1)),...(s_i,f(s_i))\vert s_i\in\mathcal{S}\}\)。样本的标签是这个样本在形式化世界中唯一正确的补全结果。
幻觉：如果\(s\in\mathcal{S}\)且\(f(s)\neq h(s)\)，则称LLM \(h\)针对真值函数\(f\)出现幻觉。
就是把幻觉定义为输出和真实结果不一致的现象，幻觉就可以分为三种，完全幻觉（一个都不一样），部分幻觉（有一部分不一样）和没有幻觉（所有样本都一致）。LLM的训练就是要让输出和真实结果尽可能贴合。
幻觉是不可避免的
论文整体来看是用了枚举+构造特例的方法证明LLM一定会在某些输入上产生幻觉，因此幻觉不可能完全消失。
可计算枚举的LLM会出现幻觉
首先使用对角论证来证明\(P\)-proved LLM的幻觉的不可避免性。因为无法直接枚举所有的可计算函数，从而无法直接使用对角论证，但可以使用\(P\)作为枚举函数来枚举所有的\(P\)-proved完全可计算函数。因此可以枚举出所有满足限制的LLM的输出，如果某些输出不在这些输出里面，则说明对于对应的输入样本一定会产生幻觉。
对于LLM的集合\(\{h_0,h_1,...h_i\vert h_i\in P-proved\}\)，每个LLM可以被训练样本逐渐更新为新的版本\(\{h_i^{[1]}, h_i^{[2]},...,h_i^{[j]}\}\)，使用康托尔配对函数将\(\{i,j\}\)编码为一个整数\(k\)，可以得到所有LLM的所有训练版本的新的序列\(\{\hat{h}_0, \hat{h}_1,..., \hat{h}_k\vert k=(i+j)(i+j+1)/2+j\}\)。然后对所有版本的LLM输入所有的训练样本\(s\in\mathcal{S}\)，就可以得到所有版本-所有输出的枚举表，这就是LLM集合可以学习的所有函数，如果有一个真值函数不在这个枚举表里，说明这个函数无法被这些LLM学习。
因此构造
\[f(s_i)=\Delta(\hat{h}_i(s_i)), \forall i\in\mathbb{N}\]其中\(\Delta\)是一个输出与输入字符串不一致的可计算函数。由此可以发现对于所有的LLM都无法得到\(f(s)=\hat{h}(s)\)，所以这些LLM针对这个\(f\)一定会产生幻觉。最终得到定理如下。
定理1：对于LLM集合\(\{h_0,h_1,...h_i\vert h_i\in P-proved\}\)，存在一个可计算真值函数\(f\)，使得集合内的所有LLM都会出现幻觉。
以上定理说明如果\(f\)未在枚举表中列出，则表中的任何LLM都无法学习到\(f\)，因此表中的所有LLM都会对\(f\)产生幻觉。
LLMs会在无法计算的问题上出现幻觉
到目前为止，所有的LLM不仅在有限时间内生成输出，更在多项式时间\(O(\Pi(m))\)内生成输出，其中\(m\)是问题的长度。这说明如果它们要拟合的真值函数\(f\)无法在多项式时间内完成，那么\(P\)-proved \(O(\Pi(m))\) LLM就一定会出现幻觉。
必然结果1：如果LLM是\(P\)-proved可以在最多\(O(\Pi(m))\)步骤内生成输出，那么针对以下的真值函数\(f\)一定会出现幻觉：
- 组合列表：使用有两个字符的词表列出所有长度为\(m\)的字符串，复杂度为\(O(2^m)\)
- Presburger算术：给出一个公理系统中的一条语句，如果能证明则\(f\)返回yes，否则返回no，复杂度为\(O(2^{2^{\Pi(m)}})\)
假设\(P\neq NP\)，\(O(\Pi(m))\) LLM会在NP完全问题上出现幻觉，比如
- 子集和：给定\(m\)个整数的集合和一个数字\(q\)，如果有一个子集的和为\(q\)则\(f\)返回yes，否则返回no
- 布尔可满足性问题（SAT）：给定一个有\(m\)个布尔变量的公式，如果有一个赋值方式让公式为真则\(f\)返回true，否则返回false
就是超出LLM可计算复杂度的问题LLM都会出现幻觉
LLM在面对无限多的问题时会出现幻觉
考虑不加\(P\)限制的所有可计算枚举LLM构成的集合\(\{h_0,h_1,...h_i\}\)，构建真值函数\(f\)为
\[f(s_i)=\Delta(\hat{h}_j(s_i)\vert j\leq i),\forall i\in\mathbb{N}\]其中\(\Delta(\hat{h}_j(s_i)\vert j\leq i)\)返回一个与字符串集合\(\{\hat{h}_j(s_i)\vert j\leq i\}\)中的字符串都不同的字符串。这样\(\forall j\leq i, f(s_i)\neq\hat{h}_j(s_i)\)成立。一般而言，在\(\mathcal{S}\)的一对一枚举\((s_0,s_1,...)\)中，LLM(\(h_k\))会对\(s_{k-1}\)之后的所有输入字符串产生幻觉。由此得到以下定理。
定理2：对于所有的可计算枚举LLM构成的集合，存在一个可计算的真值函数\(f\)，使得集合内的所有LLM在无限多的输入上都会产生幻觉。
任意可计算的LLM都会产生幻觉
在这一步，本文将LLMs视为一般的全可计算函数，基本真值函数f仍将假设为任意的全可计算函数。任意独立的LLM构成一个单独的集合，由此是可计算枚举的，根据定理2可以知道一定存在一个真值函数让这个集合内唯一的一个LLM在无限多的输入时出现幻觉，因此可以得到如下定理。
定理3：对于所有的可计算LLM，存在一个真值函数，使得LLM的每个版本在无限多的输入上都会出现幻觉。
以及这个必然结果
必然结果2：所有可计算的LLM都无法完全消除自身的幻觉。
相关讨论
现有和可能的幻觉缓解方法
现在的缓解方法基本分两类：(a)提高LLM的容量，(b)通过使用训练样本或归纳偏差，为LLM提供更多关于真实世界的信息。
更大的模型和更多的训练数据：如果训练时间足够，如果LLMs可以学习任务，那么增加的训练数据将导致泛化误差的减小。增加模型参数量会增加模型的复杂度，让模型可以学习更加复杂的真值函数。但如果基础真值函数\(f\)完全不能被LLM捕获，那么增加参数和数据是徒劳的。比如在多项式时间LLM中增加更多的多头注意力层只会导致更大的多项式时间LLM，并且只会减少和可能消除对于多项式时间背景的真值函数的幻觉。无论增加多少层或提供多少额外的训练数据，它都不会消除指数时间真值函数的幻觉。
使用Chain-of-Thoughts/Verification/Reflections对LLM进行提示：这类方法本质上是试图以一种程序化的方式引入\(f\)产生答案的归纳偏差。prompting可以有效地减轻幻觉，引导LLM更倾向于人类喜欢的解决方案，这些方案可能是复杂度较低的方案，并且在LLMs的能力范围内。但这种方法只可能应用于特定任务上，不太可能将所有的真值函数都使用prompt完全描述。不太可能通过简单地修改prompt然后希望LLM可以自动避免幻觉来为所有任务消除幻觉。
LLM ensemble：使用多个LLM通过投票或共识来解决一个问题，它注入了归纳偏见，即由世界的不同假设交叉验证的prompt补全的字符串更可能是世界的真实元素。与单独的LLM相比，Ensemble可能更有能力和更少的幻觉。但在定义2下，Ensemble本质上是一个单一的LLM，这意味着它被定理3所限制，并且不能消除幻觉。
Guardrails and Fences：guardrails是将LLMs的输出与人类的价值观、道德和法律要求保持一致的原则。Fences是使用LLMs永远不应该完全自动化的关键任务列表。两者均作为安全约束，以防止LLMs (和其他AI模型)产生不良结果。它对于形式世界和一些真实世界的问题来说是一个潜在的有用的幻觉缓解方法。然而，其在现实世界中的可扩展性仍然是一个开放的问题。
知识加强的LLM：该方法利用外部知识源(例如,知识图谱和数据库)和符号推理方法(例如,逻辑学)来辅助LLMs进行训练和推理。在这种方法下，LLMs通过训练数据以外的方式获得关于真值函数f的额外信息，因此不受定理3的约束。这可能是正式世界中幻觉的有效缓和剂。然而，它在现实世界任务中是否具有可扩展性是一个公开的问题。
待研究问题
待研究问题可以分为：
- 什么真实世界的问题可以被LLMs证明无幻觉地解决？这个问题可以进一步分为以下几个问题：
- LLM的理论计算能力是什么
- 真实世界的问题总是可计算的吗？如果是的话，真实世界问题的复杂性是什么?
- 如果LLMs在理论上能够解决真实世界问题，那么如何训练LLMs以达到其理论能力，从而在有限的领域内消除幻觉?
- 推论1强调了计算复杂性和幻觉之间的关系。哪些任务本质上比其他任务更难？如何在不同计算复杂度的任务上设计评估LLMs的基准？
- 对于在LLMs能力范围内可证明的问题，是否更倾向于使用LLMs或使用针对问题编码的程序?我们应该训练一个能做所有事情的LLM，还是一个能为特定问题使用适当工具的LLM?
- 如何利用外部知识源和推理工具对任何真实世界的问题进行幻觉检测和修正?此外，LLMs是否总能找到合适的外部工具来解决现实世界的问题?
- 如何针对真实世界的问题来量化幻觉的风险?量化幻觉风险是确定LLMs安全部署问题的重要步骤，即使存在不可避免的幻觉。