《Hallucination Stations On Some Basic Limitations of Transformer-Based Language Models》

大语言模型（LLM）存在“幻觉”现象，即生成虚假或无意义的信息。作者从计算复杂性的新颖角度来探讨这一局限性 。随着LLM越来越多地被用于构建能自主执行任务的“智能体”（Agentic AI），理解其能力边界变得至关重要。作者提出，无论是执行计算任务还是验证任务的准确性，只要任务的复杂度超过一个特定阈值，LLM就必然会失败。

LLM的计算复杂性及其影响

任何计算任务的解决都无法快于其固有的计算复杂度。作者指出，LLM生成单个词元（token）的核心操作，其计算复杂度为 $O(N^{2}.d)$，其中 $N$ 是输入序列的长度，$d$ 是模型的维度。这意味着LLM处理任何任务所能执行的计算步骤有一个明确的上限。因此，如果一个任务本身所需的计算步骤从根本上就多于这个上限（例如，复杂度为 $O(n^{3})$ 或指数级的任务），那么LLM在理论上就不可能正确完成这个任务。这个论证为我们提供了一个关键的评判标准：通过比较任务的内在复杂度与LLM的计算能力上限，我们可以预判LLM在处理该任务时是否会“碰壁”，从而产生幻觉。

示例1：词元组合

这个例子非常直观地展示了上述理论。作者提出了一个任务：“给定一个包含n个词元的集合，列出所有长度为k的字符串”。要完成这个任务，需要进行的计算量是 $O(n^{k})$，这是一个指数级的增长。当n和k的值增大时，这个数值会轻易地超过LLM的计算能力上限 $O(N^{2}.d)$ 。LLM也许能根据提示生成一些看起来合理的序列，但它并不是在真正地执行指数级的枚举计算，而只是在根据概率预测下一个最可能的词元。这启发我们，即使LLM的回答在表面上看起来正确，它也可能没有遵循任务要求的计算逻辑，尤其是在面对需要穷举所有可能性的组合问题时，其结果很可能是不可靠的。

示例2：矩阵乘法

矩阵乘法是另一个经典的计算问题，其标准算法的计算复杂度是 $O(n^{3})$（或更精确地说是 $O(m \cdot n \cdot p)$）。作者指出，当矩阵的维度超过LLM的词汇量规模时，LLM将无法正确执行乘法计算。这个例子进一步巩固了核心论点，并将其扩展到更多在现实世界中常见的、具有高阶多项式复杂度的计算任务，如寻找最短路径的Floyd-Warshall算法、某些数据库操作以及计算流体力学等。这给我们的启发是，在将LLM应用于需要精确数值计算，特别是涉及大规模矩阵或网络问题的科学和工程领域时，必须极其谨慎，因为这些任务的复杂度往往超出了LLM的能力范围。

示例3：智能体AI

本节将前面的讨论扩展到当前热门的智能体AI领域。智能体AI是指利用LLM自主决策和执行任务的系统，应用场景包括金融交易、预订服务乃至工业控制。作者论证说，如果一个任务本身的计算复杂度就超过了 $O(N^{2}.d)$，那么无论是直接让LLM执行，还是将其包装成一个智能体来执行，结果都是一样的：任务无法被正确完成。更有启发性的是，作者进一步探讨了用一个智能体（$A_{2}$）去验证另一个智能体（$A_{1}$）的任务结果是否可行。结论是不可行的，因为在许多情况下，验证一个解的正确性（尤其是最优解）需要同等甚至更高的计算复杂度 。例如，验证一个旅行商问题（TSP）的解是否为最短路径，需要对比所有可能的路径，这是一个阶乘级别的计算量（$\frac{(n-1)!}{2}$），远远超过LLM的能力。这警示我们，试图构建一个“监督者”LLM来检查“工作者”LLM的复杂计算结果，这条路在理论上是走不通的，我们不能依赖LLM来自我纠错或相互验证。

定理1及其证明

给定一个长度为N的提示，其中包含一个计算复杂度为 $O(n^{3})$ 或更高的任务（其中$n

简单来说，这个定理断言，如果你要求LLM做一个从根本上讲就很“难”的计算题（这里的“难”是用计算复杂度来量化的），超出了它自身处理能力的天花板，那么它必然会“答错”，也就是产生所谓的“幻觉” 。

该定理的证明引用了计算理论中的一个基石性成果——哈特曼尼斯-斯特恩斯（Hartmanis and Stearns）的时间层次定理（time-hierarchy theorem）。

证明的逻辑步骤如下：

1. LLM的能力上限：首先，证明明确了LLM处理能力的一个硬性限制。生成单个词元（token）是LLM的核心操作，其计算复杂度为 $O(N^{2}.d)$，其中N是输入序列的长度，d是模型的维度 。这意味着，对于一个长度为N的输入，LLM能够投入的计算资源有一个明确的上限。
2. 任务的复杂度要求：定理所设定的任务，其解决所需的计算复杂度至少是 $O(n^{3})$ ，这是一个比 $O(N^{2}.d)$ 更高阶的复杂度。
3. 引用时间层次定理：时间层次定理是一个根本性的计算原理，它指出，如果一个函数 $t_{2}(n)$ 的增长速度渐进地快于另一个函数 $t_{1}(n)$（例如 $t_{2}(n)=n^{2}$ 和 $t_{1}(n)=n$），那么必然存在一些能在 $O(t_{2}(n))$ 时间内解决，却无法在 $O(t_{1}(n))$ 时间内解决的决策问题 。换句话说，给予更多的计算时间，就能解决更复杂的问题；反之，一个需要高复杂度才能解决的问题，无法被一个低复杂度的算法完成。
4. 结论：将这个定理应用到LLM上，LLM的计算能力对应着较低的时间复杂度 $t_{1}(n)$ （即 $O(N^{2}.d)$），而任务的要求对应着更高的复杂度 $t_{2}(n)$ （即 $O(n^{3})$ 或更高） 99。因此，根据时间层次定理，任何需要超过 $O(N^{2}.d)$ 时间才能解决的任务，都无法被LLM正确地执行。由于LLM无法正确执行任务，其输出的结果必然是错误的或与正确答案无关的，这种情况被定义为“幻觉”。

它绕开了对LLM内部工作机制的复杂分析，直接从计算理论的根本限制出发，得出了一个普适性的结论。它表明LLM的幻觉问题，在面对高复杂度任务时，并非是训练数据不足或模型结构不佳导致的技术缺陷，而是一个源于其计算能力上限的、无法避免的理论限制。

讨论

当任务的内在复杂度高于LLM的核心操作复杂度时，LLM的回答要么必然错误，要么即使碰巧正确，其过程也是错误的（作者将这两种情况都归为“幻觉”）。作者强调，在应用LLM解决任何要求精确或涉及复杂计算的现实问题时，都必须格外小心。同时，带有“思考”或“推理”步骤的模型（reasoning models）能否克服这一限制？作者的初步判断是否定的，因为这些模型的底层计算单元复杂度没变，并且额外生成的“思考”文本所能提供的计算量远不足以弥补巨大的复杂度差距 。