Autoregressive Large Language Models are Computationally Universal

📄 arXiv: 2410.03170v1 📥 PDF

作者: Dale Schuurmans, Hanjun Dai, Francesco Zanini

分类: cs.CL

发布日期: 2024-10-04

备注: 32 pages

💡 一句话要点

证明自回归大语言模型在计算上具有通用性，无需外部干预。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大语言模型 自回归解码 通用计算 图灵完备 Lag系统 提示工程 Gemini-1.5-Pro-001

📋 核心要点

  1. 现有语言模型在处理超长输入时面临上下文窗口的限制，影响其复杂计算能力。
  2. 论文提出一种广义自回归解码方法，通过将输出token附加到输入序列末尾，扩展上下文窗口。
  3. 实验证明，通过特定提示，Gemini-1.5-Pro-001模型可以模拟通用Lag系统，实现通用计算。

📝 摘要（中文）

本文证明了基于Transformer的语言模型的自回归解码可以实现通用计算，而无需外部干预或修改模型的权重。为了证明这一结果，需要理解语言模型如何使用有限的上下文处理任意长度的输入。为此，我们考虑了一种广义的自回归解码，其中，给定一个长输入，发射的token被附加到序列的末尾，随着上下文窗口的推进。我们首先证明，由此产生的系统对应于一种经典的计算模型，即Lag系统，该系统长期以来被认为是计算通用的。通过利用一个新的证明，我们表明一个通用的图灵机可以被一个具有2027条产生式规则的Lag系统模拟。然后，我们研究了现有的一个大型语言模型是否可以模拟这种通用Lag系统的行为。我们给出了肯定的答案，通过展示可以为gemini-1.5-pro-001开发一个单一的系统提示，该提示驱动模型在确定性（贪婪）解码下，正确地应用2027条产生式规则中的每一条。我们得出结论，根据邱奇-图灵论题，具有扩展自回归（贪婪）解码的提示gemini-1.5-pro-001是一种通用计算机。

🔬 方法详解

问题定义：论文旨在证明大型语言模型（LLM）在计算上具有通用性，即能够执行任何可计算的任务。现有方法的痛点在于，标准LLM的上下文窗口大小有限，限制了其处理复杂、长序列计算的能力。

核心思路：论文的核心思路是，通过扩展自回归解码过程，使LLM能够处理任意长度的输入。具体而言，不是简单地截断超出上下文窗口的输入，而是将模型生成的token附加到输入序列的末尾，从而动态地扩展上下文。这种方式允许模型逐步构建和维护计算状态。

技术框架：论文的技术框架主要包括以下几个步骤：1) 形式化定义了一种广义的自回归解码过程，称为Lag系统。2) 证明了Lag系统在计算上是通用的，即可以模拟任何图灵机。3) 设计了一个特定的系统提示，用于引导Gemini-1.5-Pro-001模型模拟一个通用的Lag系统。4) 通过实验验证了在确定性（贪婪）解码下，模型能够正确应用Lag系统的产生式规则。

关键创新：论文最重要的技术创新点在于，它将LLM的自回归解码过程与经典的计算模型（Lag系统）联系起来，并证明了通过简单的提示工程，LLM可以模拟该计算模型，从而实现通用计算。这种方法无需修改模型权重，仅通过提示即可解锁LLM的潜在计算能力。

关键设计：论文的关键设计包括：1) Lag系统的形式化定义，确保其与图灵机等价。2) 系统提示的设计，需要精确地引导LLM模拟Lag系统的产生式规则。3) 使用确定性（贪婪）解码，确保模型行为的可预测性和可重复性。论文选择Gemini-1.5-Pro-001作为实验对象，因为它具有较大的上下文窗口和较强的推理能力。

📊 实验亮点

论文通过实验证明，经过适当提示的Gemini-1.5-Pro-001模型可以正确应用2027条产生式规则，成功模拟通用Lag系统。这一结果表明，大型语言模型在计算上具有通用性，能够执行任何可计算的任务，而无需额外的训练或微调。

🎯 应用场景

该研究成果对通用人工智能的发展具有重要意义，它表明大型语言模型不仅可以用于自然语言处理，还可以作为通用计算平台。潜在应用包括：复杂算法的LLM实现、新型计算架构的设计、以及利用LLM进行科学计算等。未来可能影响AI芯片设计和软件开发模式。

📄 摘要（原文）

We show that autoregressive decoding of a transformer-based language model can realize universal computation, without external intervention or modification of the model's weights. Establishing this result requires understanding how a language model can process arbitrarily long inputs using a bounded context. For this purpose, we consider a generalization of autoregressive decoding where, given a long input, emitted tokens are appended to the end of the sequence as the context window advances. We first show that the resulting system corresponds to a classical model of computation, a Lag system, that has long been known to be computationally universal. By leveraging a new proof, we show that a universal Turing machine can be simulated by a Lag system with 2027 production rules. We then investigate whether an existing large language model can simulate the behaviour of such a universal Lag system. We give an affirmative answer by showing that a single system-prompt can be developed for gemini-1.5-pro-001 that drives the model, under deterministic (greedy) decoding, to correctly apply each of the 2027 production rules. We conclude that, by the Church-Turing thesis, prompted gemini-1.5-pro-001 with extended autoregressive (greedy) decoding is a general purpose computer.