使用Transformer作为通用计算机还可以执行上下文学习算法。如何使用？集思广益的研究人员想用它来设计可编程计算机！这篇论文的作者分别来自普林斯顿大学和威斯康星大学，题目是《Looped Transformers as Programmable Computers》，旨在探索如何使用Transformer实现通用计算机。具体来说，作者提出了一个框架，通过使用特定权重对它们进行编程并将它们置于循环中，将变压器网络用作通用计算机。在此框架中，输入序列充当穿孔卡，由指令和用于数据读/写的存储器组成。作者证明了恒定数量的编码器层可以模拟基本的计算块。使用这些构建块，他们模拟了一个小型指令集计算机。这使他们能够将迭代算法映射到可以由循环的13层转换器执行的程序。他们展示了这个转换器如何模拟一个基本的计算器、一个基本的线性代数库和一个使用反向传播的上下文学习算法，由它的输入引导。这项工作突出了注意力机制的多功能性，并证明即使是浅层转换器也可以执行完善的通用程序。论文概述Transformer(TF)已成为各种机器学习任务的热门选择，并在自然语言处理和计算机视觉等领域的许多问题上取得了最先进的成果。Transformer成功的一个关键原因是它能够通过注意力机制捕获高阶关系和远程依赖关系。这允许TF对上下文信息进行建模，并使其在机器翻译和语言建模等任务中更加有效，而Transformers在这些任务中始终优于其他方法。GPT-3（175B参数）和PaLM（540B参数）等千亿参数的语言模型在许多自然语言处理任务上都取得了最先进的性能。有趣的是，这些大型语言模型(LLM)中的一些还可以执行上下文学习(ICL)，根据简短提示和一些示例即时调整和执行特定任务。LLM的ICL能力无需训练，并允许这些大型模型在不更新权重的情况下有效地执行新任务。令人惊讶的是，有了ICL，LLM可以执行算法任务和推理，[Nye等人。[2021]，魏等。[2022c]，Lewkowycz等人。[2022]，魏等。[2022b]，周等。[2022]]已经证明了其可行性。[周等人的工作。[2022]]等。演示了在给定多位加法算法和一些加法示例的提示时，LLM可以成功地为未知用例执行加法。这些结果表明，LLM可以根据算法原理在推理时对给定输入执行预先指示的命令，就好像将自然语言解释为代码一样。有证据表明，Transformers可以模拟具有足够深度的图灵机或注意力层之间的递归链接[Pérezetal.[2021]，佩雷斯等人。[2019]，魏等人。[2022a]]。这证明了Transformer网络完全遵循输入指定的算法指令的潜力。然而，这些结构相对笼统，无法深入理解如何创建能够执行特定算法任务的Transformer。然而，更专业的设计允许TF执行更高级的程序。例如，[Weiss等人。[2021]]设计一个计算模型和一种编程语言，将简单的选择和聚合命令映射到索引输入标记。这种语言可用于创建各种有趣的算法，例如令牌计数、排序、创建直方图和识别Dyck-k语言。然后可以将用受限访问序列处理语言(RASP)编写的程序映射到一个Transformer网络中，该网络的大小通常与程序的大小成比例。另一项研究展示了一种选择Transformer模型权重的方法，该模型用作动态学习线性回归模型的优化算法，在给定训练数据作为输入的情况下在推理时执行隐式训练。这些方法通常需要与学习算法的迭代次数成比例的层数，并且仅限于一个损失函数和模型集合。能够对Transformer模型进行编程以模拟图灵机的抽象计算、针对RASP等语言的专门命令以及针对ICL的特定算法，突出了Transformer网络作为多用途可编程计算机的潜力。作者的研究旨在探索这一充满希望的前景，揭示注意力机制如何模拟受指令集架构启发的通用计算机。作为可编程计算机的Transformers在本文中，作者展示了Transformer网络可以通过使用特定权重对它们进行硬编码并将它们置于循环中来模拟复杂的算法和程序。作者通过逆向工程Attention来模拟基本的计算块，例如对输入序列、非线性函数、函数调用、程序计数器和条件分支的编辑操作。作者的论文演示了使用单个循环或递归将Transformer的输出序列连接回其输入的重要性，从而避免了对深度模型的需要。论文地址：https://arxiv.org/pdf/2301.13196.pdf作者通过设计一个Transformer来实现这一点，它可以执行用单个指令的通用版本编写的程序，称为SUBLEQ(A,B,C)，即，如果小于或等于零，则减去并分支。SUBLEQ是一种单指令语言，定义了单指令集计算机（one-instructionsetcomputer，简称OISC）。SUBLEQ由3个内存地址操作数组成。执行时，将内存地址B的值减去内存地址A的值，将结果存入B。如果B的结果小于等于0，则跳转到地址C，否则继续执行下一条指令。但是这个指令可以定义一个通用计算机。作者构造了一个显式的Transformer，实现了一个类似SUBLEQ的程序，作者称之为FLEQ的更灵活的单指令，形式为其中f_m可以从一组函数（矩阵乘法/非线性函数/多项式）中选择等），并且它被硬编码到网络中。可以执行FLEQ程序的循环Transformer的深度不取决于程序的深度或代码行数，而是取决于执行单个FLEQ指令所需的深度，它是恒定的。这是通过在输入序列上重复运行Transformer来实现的，类似于CPU的运行方式。使用此框架，作者展示了在推理时模拟各种函数的能力，包括基本计算器、基本线性代数库（矩阵转置、乘法、求逆、幂迭代）以及在实现反向传播的隐式全连接网络ICL中.输入序列或提示充当打孔卡，包含Transformer需要执行的指令，同时为存储和处理程序中使用的变量提供空间。用于执行这些过程的Transformer网络的深度都小于或等于13，并且提供了所有这些模型的权重矩阵。下面的定理总结了作者的主要发现：定理1：存在一个少于13层的循环Transformer，可以模拟通用计算机（文章第5节）、基本计算器（文章第7节）、数值线性代数方法，如近似矩阵求逆和幂迭代（文章第8节），以及基于神经网络的ICL算法，如SGD（文章第9节）。图1：递归Transformer架构示意图，其中输入序列存储命令、从中读取/写入数据的内存以及存储中间结果的暂存器。输入由网络处理，输出用作新输入，允许网络迭代更新隐式状态并执行复杂的计算。作者的研究突出了注意力机制的灵活性和单循环的重要性，这使得设计能够模拟复杂迭代算法和执行通用程序的模型成为可能。它进一步展示了Transformer模型高效执行复杂数学和算法任务的能力。可以想象，现代Transformer，例如GPT-3，在执行各种任务时使用类似的内部子程序。在某种程度上，这些特定于模型的技巧或算法功能可以在给出上下文示例和插图时得到启发，类似于函数调用。然而，这种假设应该谨慎对待，因为作者设计结构的方式与现实世界语言模型的训练方式没有任何相似之处。作者希望他们的研究能够鼓励进一步研究注意力机制的潜力，以及语言模型执行算法指令的能力。作者提出的设计可以帮助确定执行特定算法任务所需的最小Transformer网络规模。此外，作者希望他们的发现将有助于激发方法的开发，通过利用更小的、逆向工程的Transformer网络来完成特定的算法任务，从而增强训练语言模型的能力。构建用于通用计算的Transformer模块要使用Transformer网络构建通用计算框架，需要专门的计算块。这些块被组装起来以创建所需的最终功能。下面重点介绍Transformer层可以执行的各种操作。这些操作将为创建更复杂的例程和算法提供基础。这些操作被设计成可以相互操作，利用Attention的能力来执行各种任务，例如生成近似置换矩阵和通过sigmoid函数逼近一般函数。图2：用作实现小型指令集计算机构建块的三个Transformer块的示意图。这些块处理输入序列中的编辑操作（例如从一个块移动或复制到另一个块），跟踪程序计数器，并在满足指定条件时执行程序计数器跳转。位置编码、程序计数器和数据指针转换器通常需要执行迭代算法或执行一系列命令。为实现这一点，作者使用了一个循环执行命令的程序计数器。计数器包含存储下一个命令位置的代码。此外，命令可能具有指向命令需要读取和写入的数据位置的数据指针。程序计数器和数据指针都使用与上一段中讨论的相同的位置编码。作者的位置编码方案也可用于指向特定的数据位置以进行读取或写入，这将在下一节中讨论。这是通过使用与程序计数器和数据指针的位置编码相同的二进制向量来实现的。此外，这种指向特定数据位置的技术使Transformer能够在执行算法或为实现它而构建的命令序列期间有效地读取/写入数据。读/写：将数据、指令复制到暂存器或从暂存器复制数据、指令图3：读操作示意图。箭头显示从分配给暂存器命令的输入部分复制的命令块。指令是一组指针。位置代码和计数器用于跟踪在何处复制的内容。下面的引理指出，程序计数器指向的命令或当前命令中指定位置的数据可以复制到暂存器以供进一步计算。程序计数器的位置通常就在暂存器内容的正下方，但可以任意更改。在整个计算过程中将其保持在特定位置有助于保持结构井井有条。下一个引理解释了存储在暂存器中的向量v可以复制到存储器中的指定位置，如暂存器本身指定的那样。这允许数据从暂存器传输到内存中的特定位置以供进一步使用或存储。图4：写操作示意图。箭头表示数据块正在从暂存器复制到分配给内存的输入部分中的指定位置。位置编码用于跟踪目标位置并确保数据写入正确的内存位置。条件分支在这部分中，作者实现了一个条件分支指令，该指令评估条件并在条件为真时将程序计数器设置到指定位置，或者在条件为假时将程序计数器递增1。该命令具有以下形式：如果mem[a]≤0，则转到i，其中mem[a]是输入序列的内存部分中某个位置的值。该命令分为两部分：判断不等式和修改程序计数器。模拟通用单指令集计算机SUBLEQTransformerMavaddat和Parhami早在1988年就证明存在一条指令，通过该指令可以将任何计算机程序转换为由该指令的实例化组成的程序。该指令的一个变体是SUBLEQ，它可以访问不同的寄存器或内存位置。SUBLEQ的工作方式很简单。它访问内存中的两个寄存器，获取它们内容的差异并将其存储回其中一个寄存器，然后如果结果是否定的，它跳转到不同的预定义代码行，或者继续执行当前行的下一条指令.为执行SUBLEQ程序而构建的计算机称为单指令集计算机，并且是通用计算机，即，如果它可以访问无限内存，则它是图灵完备的。下面描述了一个循环Transformer的构造，它可以执行用特定指令集编写的程序。Transformer跟踪代码行、内存位置和程序计数器，使用输入的内存部分作为内存寄存器，使用命令部分作为代码行/指令。暂存器用于记录每条指令、读、写、条件分支操作等涉及的加法和指针。图5：实现OISC指令块的图形表示。前两个块将数据/命令传输到暂存器，第二个和第三个执行减法并存储结果，最后一个执行完成指令的ifgoto命令。FLEQ:AMoreFlexibleAttention-BasedComputer在本节中，作者介绍了FLEQ，它是SUBLEQ的推广，它定义了一种更灵活的RISC计算机。这个隐式附加指令集基于更高级版本的SUBLEQ，允许在同一个Transformer网络中实现多个功能。作者使用术语FLEQ来指代它定义的指令、语言和基于注意力的计算机。FLEQ的设计允许通过生成比简单减法更通用的函数来实现矩阵乘法、平方根计算、激活函数等复杂算法。基于注意力的计算机执行周期。在循环Transformer的每次迭代中，根据程序计数器从输入中的指令集中提取一条指令。然后指令被复制到暂存器。根据要实现的功能，该功能的结果使用不同的功能块位置记录在本地。一旦计算出结果，它就会被复制回指令提供的指定内存位置。执行周期类似于上一节中单指令集计算机(OISC)的执行周期，主要区别在于对于每条指令，可以从以矩阵等任意数组形式输入的预选函数列表中进行选择、向量和标量。输入序列的格式。如图6所示，循环Transformer的输入X可以执行由一系列FLEQ指令组成的程序（X由暂存器、内存、指令三部分组成）。基于Transformer的功能块的格式。每个功能块位于输入X的左下部分，如图6所示。图6：执行FLEQ命令的输入X的结构有关更多技术细节和示例，请参阅原始论文。
