论文

立场:现实世界自回归变压器的图灵完备性很大程度上依赖于上下文管理

Position: The Turing-Completeness of Real-World Autoregressive Transformers Relies Heavily on Context Management

上下文与知识上下文工程

摘要

许多工作提出Transformer是图灵完备的这一夺目论断。然而文献常混淆两种不同的设定:(i) 固定Transformer系统设定,其中一个固定的自回归Transformer与固定的上下文管理方法耦合,逐步处理不同长度的输入;(ii) 扩展家族设定,其中使用一族不同的模型(上下文窗口长度或数值精度递增)来处理不同的输入长度。现有的Transformer图灵完备性证明常在设定(ii)中建立,而现实中的LLM部署与图灵完备性的标准概念更自然地对应设定(i)。本文首先形式化固定系统设定,从而为现实LLM的运行方式提供具体刻画。随后我们论证,在扩展家族设定中证明的结果只提供理论上有意义的资源界限,并不确立图灵完备性,以此澄清对现有结果的一种常见误解。最后,我们证明不同的上下文管理方法可产生截然不同的计算能力,并提出如下立场:上下文管理是关键决定现实自回归Transformer计算能力的核心组件。