🤖 machine learning

Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete

本文证明了位置编码对于 Transformer 实现图灵完备性并非严格必要，因为滑动窗口机制本身打破了置换对称性，并提供了足以模拟通用计算的位置信息。

原作者： Qian Li, Xinyu Mao, Shang-Hua Teng

发布于 2026-06-02

📖 1 分钟阅读☕ 轻松阅读

原作者： Qian Li, Xinyu Mao, Shang-Hua Teng

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在试图教一个机器人讲故事或解决数学问题。长期以来，计算机科学家们一直认为，要实现这一点，机器人需要为它读到的每个单词都附带一个特殊的“地址簿”。这个被称为**位置编码（Positional Encoding, PE）**的地址簿，会告诉机器人每个单词在句子中的确切位置（第1个、第2个、第3个，等等）。如果没有它，理论上机器人会感到困惑，因为它无法区分“猫追狗”和“狗追猫”。

这篇论文指出，如果机器人使用的是一种特定类型的记忆机制：滑动窗口（sliding window），那么你其实并不需要那个地址簿。

以下是核心思想的拆解，通过一些日常类比来解释：

1. 旧有的信念：“静态照片”

把标准的 Transformer 模型（许多 AI 聊天机器人背后的模型）想象成一个正在拍摄人群照片的摄影师。如果你只是把一堆人的脸交给摄影师，而不告诉他们谁站在哪里，他们就无法分辨出一排站立的人和一堆乱作一团的人之间的区别。他们需要在每个人的额头上贴一个标签（位置编码），才能知道顺序。

2. 新的发现：“移动的巴士”

作者们意识到，当 AI 进行复杂的、循序渐进的推理（比如解决一个长长的数学题）时，它并不会一次性观察整个历史。相反，它使用的是一个滑动窗口。

想象 AI 正坐在一辆巴士上，车窗每次只能看到刚刚经过的 10 个人。

旧观点： 如果你只看窗口内当前的 10 个人，你无法判断谁先进入窗口，也不知道谁最后离开。他们只是一组 10 个人。
新观点： 作者注意到，这辆巴士是在移动的。
- 每秒钟，都会有一个新人踏上巴士（进入窗口）。
- 每秒钟，都会有一个最旧的人从后面掉下去（离开窗口）。

即使 AI 看不到窗口内的人拥有“街道地址”，巴士移动的行为本身也创造了一种模式。AI 可以观察到：“哦，刚才有个新人上车了，而且我知道谁刚从后面掉下去了，因为总人数发生了变化。”

3. “神奇直方图”（HIST 模型）

为了证明这一点，作者发明了一个理论上的机器人，叫做 HIST 模型。

这个机器人对顺序是“盲”的。它无法说“红衣服的人在第 3 位”。
它只能看到一个计数（直方图）。它知道：“现在窗口里有 3 个穿红衣服的人，2 个穿蓝衣服的人和 1 个穿绿衣服的人。”
它还拥有一个微小的记忆（一个“控制状态”）来记住过去发生的最后几件事。

神奇的诀窍在于：通过比较新成员进入前的计数和进入后的计数，机器人可以推断出究竟是谁离开了巴士，即使它没看到那个人的名字牌。

之前： 3 红，2 蓝。
新人进入（蓝色）。
之后： 3 红，3 蓝。
等等，窗口大小是固定的！ 如果进来一个蓝色，说明必然有一个红色离开了。
结论： 机器人知道刚才有一个穿红衣服的人从后面掉下去了，尽管它从未见过那件红衣服在什么位置。

4. 重大结果：图灵完备性

在计算机科学中，“图灵完备”（Turing Complete）意味着一台机器在拥有足够的时间和内存的情况下，理论上可以解决任何计算机能解决的问题。

此前的观点： Transformer 需要位置编码才能达到图灵完备。
本论文的证明： 一个带有滑动窗口的 Transformer 不需要位置编码也能实现图灵完备。窗口本身的移动过程提供了足够的“序列信息”，足以模拟一台通用计算机。

作者建立了一个数学桥梁，证明了：

一个只能计数 Token 类型（即 HIST 模型）的机器，可以模拟一台通用计算机（具体来说是类似于带有队列的 Post Machine）。
一个标准的（不带位置编码的）Transformer 可以完美地模仿这种计数机器。

5. 这意味着什么（以及它并不意味着什么）

好消息：
事实证明，处理数据时的“流动过程”本身就足以产生秩序。你不需要手动给每个单词贴上数字标签，就能获得通用计算能力。这种“滑动”动作本身打破了对称性。

注意事项（论文并未表达的内容）：

这不是关于速度： 这是一个关于“可能性”的证明，而不是关于“效率”的证明。仅仅因为一个机器人可以在没有地址簿的情况下解决问题，并不意味着它在现实生活中会做得很快或很容易。
它并不读取精确位置： 机器人仍然无法说“第 5 个词是‘苹果’”。它只能推断出“有人离开了这个群体”。这是一种聪明的演绎技巧，而不是直接的映射。
它需要一点数学魔法： 该证明依赖于机器人能够进行非常精确的计数（奇偶校验），以知道究竟是谁离开了窗口。在现实世界中，这可能需要极高的数学精度，这是作者承认的一个技术细节。

总结

把位置编码想象成每个单词的 GPS 坐标。这篇论文说：“如果你正走在街上，看着人们进进出出一家商店，你其实不需要 GPS。人们进出的流动过程本身就会讲述故事，即使你不知道他们的确切街道地址。”

滑动窗口本身就是 AI 的“GPS”，使得外部地址簿对于机器实现通用计算变得不再必要。

技术摘要：重新思考滑动窗口 Transformer 中位置编码的角色

1. 问题陈述

长期以来，位置编码（Positional Encoding, PE）一直被认为是 Transformer 架构处理有序序列所必需的组件。主流直觉认为，如果没有显式的位置信息，自注意力机制将具有置换不变性（permutation-invariant），从而导致模型无法区分相同上下文标记（tokens）的不同排列顺序。这一假设支撑了先前关于利用思维链（Chain-of-Thought, CoT）推理实现 Transformer 图灵完备性的理论结果，这些结果高度依赖于 PE 来模拟序列计算。

然而，这些通用性结果通常假设模型能够关注整个历史记录。在实际的长文本推理场景中，模型运行在有限的滑动上下文窗口中。随着窗口向前滑动，标记进入并退出，从而引入了时间上的不对称性。本文旨在解决的核心问题是：在滑动窗口 Transformer 中，位置编码对于实现通用计算是否真的是必需的？ 作者研究了滑动窗口机制本身是否提供了足够的序列结构，以在没有显式 PE 的情况下实现图灵完备性。

2. 方法论与框架

HIST 模型

为了隔离由滑动窗口带来的计算能力，作者引入了一个抽象的自回归模型，称为 HIST 模型。

定义： HIST 机器仅根据当前窗口的有限控制状态和标记计数直方图（即按字母表索引的标记频率向量）来生成下一个标记。
约束： 该模型无法访问窗口内单个标记的具体位置；其转移函数对于窗口内容具有置换不变性。
Parity-HIST 变体： 一种受限版本，其转移函数仅取决于直方图的奇偶性（即每个标记类型的计数是偶数还是奇数）。

理论策略

证明图灵完备性的过程分为两个主要阶段：

模拟 Post 机器： 作者证明了 Parity-HIST 机器可以模拟 Post 机器（一种已知的基于队列的图灵完备自动机）。
- 核心洞察： 尽管 Parity-HIST 机器只能观察到窗口的奇偶性，但滑动窗口的 FIFO（先进先出）特性允许它推断刚刚离开窗口的标记。通过比较窗口更新前后及更新过程中的奇偶直方图（并利用有限控制状态来存储新进入的标记），该机器可以推断出“掉落”的前端标记的身份。这有效地在没有显式位置寻址的情况下模拟了队列的 dequeue 操作。
用 Transformer 模拟 Parity-HIST： 作者构建了一个不带 PE 的滑动窗口 Transformer，它可以模拟 Parity-HIST 模型。
- 机制： 该 Transformer 使用常数大小的标记字母表和一个自适应更新位。为了从注意力机制中恢复原始标记计数（从而获得其奇偶性），该构造引入了一个特殊的标记符号 (#)。
- 注意力动力学： 通过使用均匀注意力（通过将 Query 和 Key 矩阵置零实现），注意力权重变为 $1/m$ （其中 $m$ 是窗口大小）。单个标记的存在允许模型推断窗口大小 $m$ ，并将归一化的注意力质量转换回原始整数计数。
- 奇偶性提取： 利用足够的算术精度（对窗口大小呈对数关系），MLP 层计算标记计数的奇偶性，从而有效地复制了 Parity-HIST 的转移函数。

3. 主要贡献与结果

定理 1（高层级）： Parity-HIST 模型是图灵完备的。作者证明了滑动窗口的时间演化，结合置换不变的汇总（直方图奇偶性）和有限状态，足以模拟 Post 机器。
定理 2（高层级）： 每个 Parity-HIST 机器都可以由不带位置编码的滑动窗口 Transformer 模拟。
推论： 不带 PE 的滑动窗口 Transformer 是图灵完备的。
构造细节：
- 该构造使用常数大小的词表和常数数量的可学习参数。
- 它采用了一种自适应窗口更新机制，其中标记携带一个控制位，用于决定是滑动窗口（标准模式）还是扩展窗口（保留最旧的标记），从而避免了预先指定最坏情况下的窗口大小。
- 该模拟需要对数精度（ $O(\log S)$ ）进行算术运算以计算奇偶性，其中 $S$ 是最大窗口长度。

4. 重要性与主张

本文声称从根本上分离了在通用计算语境下的位置编码与序列结构的概念。

PE 并非不可或缺： 研究结果表明，显式的位置编码并不是 Transformer 执行通用计算的前提条件。滑动窗口的“类 FIFO 运动”本身打破了置换对称性，并提供了必要的序列信号。
完善通用性定义： 本研究澄清了，虽然通用计算需要某种来源的序列结构，但这种结构并不一定需要由外部位置寻址系统提供。它可以从生成过程的时间动力学中自然产生。
与前人工作的区别： 不同于以往利用 PE 存储电路结构或识别特定标记的通用性证明，本构造通过一个置换不变的窗口汇总模型来进行模拟。
局限性与范围：
- 该构造是一个表达能力结果，而非关于可学习性或实际效率的断言。它并不意味着标准的 Transformer 会自然地学习这些算法。
- 该模型无法恢复窗口内标记的精确位置；它只能推断进入和离开窗口的标记身份。
- 该构造依赖于一个需要对数精度的特定奇偶性原语，这被视为一种数值要求，而非还原过程中的基本架构限制。

总之，本文确立了仅靠滑动窗口机制，即使在缺乏位置编码的情况下，也能通过利用标记进入和退出的时间不对称性，赋予 Transformer 进行通用计算的能力。