Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
2026-06-01 • Machine Learning
Machine LearningComputational Complexity
AI summaryⓘ
The authors challenge the idea that transformers need positional encoding (PE) to handle ordered sequences and perform any computation. They focus on transformers using a limited sliding window of context, showing that this window itself introduces enough order to break symmetry. The authors introduce a theoretical model (HIST) that uses only a small internal state and token counts in the window, proving it can perform any computation. They then demonstrate a transformer without PE can simulate this model, meaning PE is not strictly required for universal computation.
transformerspositional encodingsliding windowTuring completenessautoregressive modelstoken histogramPost machinespermutation invariancechain-of-thoughtuniversal computation
Authors
Qian Li, Xinyu Mao, Shang-Hua Teng
Abstract
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.