Autoregressive Large Language Models are Computationally Universal

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

论文探讨了如何利用transformer-based语言模型的自回归解码实现通用计算，验证了这一假设是否成立。

通过对自回归解码的改进，将发射的token附加到序列末尾，使得模型能够处理任意长的输入，从而实现通用计算。

论文证明了一个Lag系统可以模拟图灵机，并且展示了一个大型语言模型可以模拟这个Lag系统。作者还提供了实验细节和开源代码。

最近的相关研究包括使用transformer-based语言模型进行自然语言生成和理解的工作。