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

📄 arXiv: 2606.01532v1 📥 PDF

作者: Qian Li, Xinyu Mao, Shang-Hua Teng

分类: cs.LG, cs.CC

发布日期: 2026-06-01

💡 一句话要点

证明无位置编码的滑动窗口Transformer在长文本推理中仍具备图灵完备性

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: Transformer 位置编码 滑动窗口 图灵完备性 长文本推理

📋 核心要点

  1. 传统Transformer依赖位置编码处理序列数据，但长文本推理中滑动窗口机制可能已蕴含位置信息。
  2. 论文提出HIST模型，仅依赖固定大小内部状态和窗口内token计数直方图，证明其图灵完备性。
  3. 构建无位置编码的滑动窗口Transformer，并证明其可以模拟HIST模型，表明窗口滑动本身已包含足够的位置信息。

📝 摘要（中文）

本文重新审视了位置编码（PE）在Transformer处理有序序列中的必要性。传统观点认为，缺少PE时，next-token映射在其上下文token中表现出置换不变性。这一直是先前通用性结果的基础，这些结果依赖于位置信息来证明具有思维链的Transformer可以执行任意计算，即它们是图灵完备的。本文在与长文本推理最相关的场景下，即通过有限滑动上下文窗口进行生成，重新审视了这一观点。研究发现窗口机制本身（轻微地）打破了置换对称性。为了提炼和精确捕捉这种额外表达能力的程度，本文引入了一个抽象的自回归模型HIST，其中每次更新仅取决于固定大小的内部状态和当前窗口内的token计数直方图。通过证明窗口的演化可以揭示刚刚离开窗口的token，从而模拟图灵完备的Post机器，证明了HIST模型是图灵完备的。然后，本文构建了一个基于固定大小token字母表的无PE滑动窗口Transformer，并表明它可以模拟HIST模型。结果表明，位置编码不是Transformer执行通用计算所必需的：窗口滑动本身已经打破了置换对称性，并捕获了足够的位置信息。

🔬 方法详解

问题定义：Transformer模型通常需要位置编码（PE）来处理序列数据，因为没有PE，模型似乎对输入序列中token的顺序不敏感。现有的通用性证明也依赖于PE。然而，在长文本推理中，通常使用滑动窗口来限制上下文长度，这引发了一个问题：在这种情况下，PE是否仍然是必需的？现有方法忽略了滑动窗口本身可能引入的位置信息。

核心思路：论文的核心思路是证明即使没有显式的位置编码，滑动窗口机制本身也足以打破置换对称性，并使Transformer能够执行通用计算。通过构建一个抽象模型HIST，并证明其图灵完备性，然后证明一个没有PE的滑动窗口Transformer可以模拟HIST模型，从而论证了这一观点。关键在于窗口滑动过程揭示了离开窗口的token，从而提供了足够的位置信息。

技术框架：论文的技术框架包括以下几个关键部分：1) 引入抽象自回归模型HIST，该模型仅依赖于固定大小的内部状态和当前窗口内的token计数直方图。2) 证明HIST模型是图灵完备的，通过展示窗口的演化可以揭示刚刚离开窗口的token，从而模拟图灵完备的Post机器。3) 构建一个基于固定大小token字母表的无PE滑动窗口Transformer。4) 证明该Transformer可以模拟HIST模型。

关键创新：最重要的技术创新点在于证明了滑动窗口机制本身可以提供足够的位置信息，使得Transformer在没有显式位置编码的情况下仍然可以实现图灵完备性。这挑战了Transformer必须依赖位置编码才能处理序列数据的传统观点。与现有方法的本质区别在于，现有方法依赖于显式的位置编码，而本文证明了隐式的位置信息（由窗口滑动提供）就足够了。

关键设计：HIST模型的设计是关键。它抽象了滑动窗口Transformer的核心操作，只保留了固定大小的内部状态和token计数直方图。Transformer的构建也至关重要，需要确保它能够有效地模拟HIST模型的操作。论文中token字母表的大小被限制为常数，这简化了证明过程。具体的参数设置和网络结构细节在论文中应该有更详细的描述（未知）。

📊 实验亮点

论文证明了无位置编码的滑动窗口Transformer仍然可以实现图灵完备性，这挑战了Transformer必须依赖位置编码的传统观点。通过构建HIST模型并证明其图灵完备性，以及展示Transformer可以模拟HIST模型，有力地支持了这一结论。具体的性能数据和提升幅度未知，但该理论结果本身具有重要的意义。

🎯 应用场景

该研究成果对长文本处理领域具有重要意义，可以简化Transformer模型的结构，降低计算成本，并可能促进更高效的长文本建模方法的发展。潜在的应用领域包括自然语言生成、机器翻译、文本摘要和对话系统等。未来的影响可能体现在更轻量级、更高效的Transformer模型设计上。

📄 摘要（原文）

Positional encoding (PE) is widely viewed as necessary for transformers to process ordered sequences: without them, the next-token map appears permutation-invariant in its context tokens. This intuition underlies all prior universality results, which rely on positional information to prove that transformers with chain-of-thought can perform arbitrary computation, i.e., they are Turing complete. We revisit this belief in the regime most relevant to long-form reasoning, where generation proceeds through a finite sliding context window. Our opening perception is that the window mechanism itself (mildly) breaks the permutation symmetry. To distill and precisely capture the degree of this added expressiveness, we introduce an abstract autoregressive model, the HIST model, in which each update depends only on constant-size internal state and the token-count histogram within the current window. We prove that this HIST model is Turing complete by showing that the evolution of the window can reveal the token that has just left the window, which suffices to simulate Turing-complete Post machines. We then construct a sliding-window transformer over a constant-size token alphabet, without PE, and show that it can simulate the HIST model. Our result demonstrates that positional encodings are not indispensable for transformers to perform universal computation: The window sliding itself already breaks permutation symmetry and captures sufficient positional information.