毫无疑问，现在可说是自回归大型语言模型（LLM）的时代，我们看到技术迭代，我们也看到应用频出，但即便如此，也依然有人表示不看好。
唱衰自回归范式的最著名人物应当是 Yann LeCun 无疑了。他甚至还曾给出过一个相当大胆的判断：「从现在起 5 年内，没有哪个头脑正常的人会使用自回归模型。」详见AI在线报道《GPT-4 的研究路径没有前途？Yann LeCun 给自回归判了死刑》。
Yann LeCun 在演讲中表示自回归 LLM 会走向末路（doomed）
但现在，DeepMind 和阿尔伯塔大学的一篇论文却给出了截然相反的见解，其研究结果表明：无需外部干预或修改模型权重，基于 Transformer 的语言模型的自回归式解码就可以实现通用计算。
论文标题：Autoregressive Large Language Models are Computationally Universal
论文地址：https://arxiv.org/pdf/2410.03170
具体来说，这篇论文研究的核心问题是：当使用无界限的思维链时，大型语言模型是否可以支持通用计算？
近期很多研究都已经证明，可以通过外部记忆来增强 LLM，从而通过提示来实现对通用图灵机的模拟。但是，如果使用会将计算责任转移到语言模型之外的外部控制机制（尤其是正则表达式解析工具），则可能削弱这一结果。那无辅助的 LLM 是否能成为通用图灵机呢？这一问题仍待解答。
DeepMind 的这项研究给出了肯定答案：无辅助 LLM 确实可以模拟通用图灵机。不知道 Yann LeCun 会如何评价这一结果？
为了做到这一点，需要从一个更普适的视角来看待自回归解码，并且其要能处理任意长度的输入字符串。
该团队研究了自回归解码的一种自然泛化，其中在处理每个连续的上下文之后，输出的 token 都会被添加到序列末端 —— 只要输入能放入上下文窗口中，则该过程就会简化成标准的自回归解码。
不过，该团队得到这一结果的过程比较复杂，涉及到一步步地演算推进：
首先，针对自回归解码，他们给出了一个更通用的视角，其可适用于长输入字符串的情况。
他们提出了一种扩展，可让语言模型实现 Lag 系统的一种受限形式。而 Lag 系统则是一种最早的通用计算模型的一个变体。
他们又接着证明 Lag 系统不仅能将内存组织为循环队列，还可以提供对内存访问的双向控制。
在介绍了图灵机的有限内存模拟的相关背景之后，他们又证明任何图灵机都可由上下文长度为 2 的受限 Lag 系统模拟。他们指出，尽管 Lag 系统的通用性早为人知，但他们给出的证明更加直接，并能为后续证明提供支持。
之后，他们将此归约技术应用于一种特定的通用图灵机 U_{15,2}，得到了一个通用 Lag 系统，该系统由一组 2027 条产生式规则（production rule）定义，这些规则基于 262 个符号构成的字母表。
最后，他们开发了一条系统提示词，可让 gemini-1.5-pro-001 这个特定的 LLM 正确地在贪婪解码下应用那 2027 条规则中的每一条。基于此，该团队得出结论认为：扩展了自回归（贪婪）解码的 gemini-1.5-pro-001 可以精确模拟 U_{15,2} 对任何输入的执行情况，因此它是一台通用计算机。
下面我们将简要介绍一下其证明过程，并将重点关注最后一步，更多详情请参阅原论文。
自回归解码与 Lag 系统
语言模型表示的是在给定的输入字符串 s_1…s_n 上，下一个符号 s_{n+1} 的条件分布 p。任何此类模型都可以通过概率链式法则扩展为输出序列上的条件分布。
从 (1) 式也能看出，这个过程是自回归式的，也因此叫做自回归解码。算法 1 总结了上下文长度为 N 的语言模型的确定式自回归解码。
该团队给出的第一个关键观察是：大型语言模型的自回归解码可以通过 Lag 系统复现出来。Lag 系统最早由 1963 年的论文《Tag systems and Lag systems》提出，这是通用计算的一种最早的形式模型 Tag 系统的一个简单变体。
Lag 系统由一组有限的规则 x_1…x_N → y 组成，其中 N 是上下文的长度，x_1…x_N 表示要匹配的符号序列，y 表示相应的输出。
对于确定性 Lag 系统，每个模式 x_1…x_N 都是唯一的，因此 Lag 系统定义了一个部分函数 L，其可将模式 x_1…x_N 映射成相应的输出 y。Lag 系统的计算是通过对内存字符串进行操作来定义的 —— 在每次迭代中，都会有一条规则与内存字符串的前缀匹配，然后结果被附加到字符串后面，之后再删除第一个符号；参见算法 2。
图灵机
形式上看，图灵机 T 由一个元组 T = (Q, Γ, b, q_0, H, f) 组成，其中 Q 是一组有限的状态，Γ 是一组有限的磁带符号，b ∈ Γ 是唯一的「空白」符号，q_0 ∈ Q 是唯一的起始状态，H ⊆ Q×Γ 是一组表示终止的配对的 (状态，符号)，f : Q×Γ → Γ × Q × {−1, +1} 是一组有限的转换规则，用于指定该图灵机在每个计算周期中的操作。
该图灵机可以访问单向无界的存储磁带，因此可以通过自然数 i ∈ N (i > 0) 来索引存储位置，这样 i = 1 处有一个最左边的存储位置，但没有最右边的存储位置
图灵机的执行定义如下。
磁带用一个由有限数量的非空白符号表示的输入进行初始化，其它所有位置均为空白，T 从状态 q_0 开始，磁带头从指定位置 i_0 开始（默认 i_0 = 1）。
在每个计算周期开始时，T 处于某个状态 q ∈ Q，磁带头位于某个位置 i > 0，当前正在从磁带读取符号 γ ∈ Γ。组合 (q, γ) 确定更新 f (q, γ) → (γ′ , q′ , D)，指定符号 γ′ 写入当前内存位置 i，机器状态 q 更新为 q′ ，磁带头移动到 i + D（即根据 D 的符号向左或向右一步）。假设机器永远不会移出磁带的左端。计算循环重复进行，直到机器遇到配置 (q, γ) ∈ H。不停机计算是可能的。
为便于后续证明，了解可以如何仅使用有限内存来模拟图灵机的计算会很有用。算法 3 描述了一种标准模拟策略，其中使用新的分隔符 # 来标记访问内存的末尾，从而可在必要时分配额外的空间。这使得可以模拟潜在的无限内存，而无需分配无限存储空间。
用 Lag 系统模拟图灵机
该团队证明，任意图灵机都可通过一个受限 (2, 2)-Lag 系统模拟。这是他们得到的首个主要结果。该证明还意味着任何线性有界自动机都可以用一个受限 (2, 2)-Lag 系统模拟。
之前研究者已经证明 Lag 系统具有计算通用性，但原始的证明依赖于一种少有人知形式的寄存器机（register machine ）的简化。这里并不方便利用这个证明。于是，该团队开发了一种将图灵机直接简化为 Lag 系统的方法，从而能在后续论证中利用小型通用图灵机。
给定一个图灵机 T = (Q, Γ, b, q_0, H, f)，可以这样构建其对应的 Lag 系统：Lag 系统将使用字母表
其中 # 是分隔符符号，Q 是来自 T 的有限状态集（使得空白符号不属于 Q），Σ_left 和 Σ_right 是位置控制字母表。
也就是说，Lag 系统中的每个符号都是一个三元组，由内存符号、状态符号和位置控制符号组成。
该团队为该 Lag 系统设计了一些规则，使得其内存字符串会跟踪图灵机模拟算法 3 中局部变量的状态。
具体而言，在每次迭代 k ∈ N 开始时，算法 3 维护一组局部变量：m、n、q 和 i，其中 m 是一个表示当前磁带内容的数组、n 是 m 的当前长度、q 是 T 的控制器的当前状态，i 是磁带头的当前位置。
为了镜像这些局部变量的值，Lag 系统将维护一个内存字符串 s，使得序列 m_1…m_{n−1}# 对应于 m，s 的长度为 n，q 对应于相同的控制器状态，图灵机磁带头的位置 i 由三元组第二个位置中唯一的非空白状态符号 q 的位置表示。
具体来说，对于给定的图灵机 T，通过算法 4 确定的规则集定义相应的滞后系统 L。
这项研究结果表明：基于算法 4 得到的 Lag 系统 L，算法 2 可模拟给定图灵机 T 在任意输入 γ_1…γ_{n−1} 上执行算法 3。
一个通用的 Lag 系统
由于论文的主要目标是证明当前的语言模型在扩展的自回归解码下是计算上通用的，最直接的证明方法就是看看这个模型是否能够模拟一个已知的、计算上通用的系统。
从本质上来讲，任何关于计算机通用性的讨论，都要回到大名鼎鼎的「邱奇 – 图灵」论题。邱奇和图灵都有过这样的猜想：所有计算机制都可以由图灵机来表达。图灵提出了通用图灵机的概念，它能够模拟任何计算过程。
鉴于语言模型的自回归解码与 Lag 系统在更新时具有类似的机制，因此，很自然地想要通过一个通用的 Lag 系统来证明其通用性。定理 7 为构建这样一个通用 Lag 系统提供了明确的路径。
使用语言模型模拟通用 Lag 系统
最后，要证明现有的 LLM 可以模拟通用 Lag 系统 L (U_{15,2}) 在任意输入字符串上的执行情况。该团队的做法是开发一个特定的提示词，以让扩展过的自回归（贪婪）编码模仿 L (U_{15,2}) 的行为。
他们开发了一个提示策略，其中包含两个组件：系统提示词和滑动窗口提示词。其中系统提示词提供了完整的规则集，而滑动窗口提示词会在输入序列中附加下一个符号对（4 个 token）。
每次迭代过程中，下一个符号对都会附加到系统提示词中并作为输入提供给语言模型；然后，语言模型的输出（2 或 4 个 token）会附加到序列的末尾，如图 3 所示。
为了确保系统是确定性的，他们将温度值设置为 0，并固定了定义语言模型行为的所有随机种子。
为了允许语言模型为每个上下文窗口输出可变数量的 token ，他们采用了扩展自回归解码，其中除了 262 个 token 对的基本字母表之外，还使用了一个隐式的隐含终止 token h。
最后，为了验证扩展自回归（贪婪）解码是否确实能够复制 L (U_{15,2}) 的行为，他们挑选了一个特定的 LLM：gemini-1.5-pro-001。几番实验之后，他们开发了一个系统提示词，可让模型正确执行那 2027 条规则中的每一条。他们将这个系统提示词称为 S_gemini。之后他们得出了最终结论。
从这个定理出发，根据「邱奇 – 图灵」定理，可以得出结论：在扩展自回归（贪婪）解码条件下，gemini-1.5-pro-001 是一台通用计算机。重要的是，实现这一结果不需要引入任何扩展自回归解码之外的计算机制。
参考链接：
Yann LeCun 演讲《From Machine Learning to Autonomous Intelligence》，https://www.youtube.com/watch?v=mViTAXCg1xQ