斯坦福最新研究:AI幻觉不是玄学,是算力有上限!
《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...