Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
Qian Li, Xinyu Mao, Shang-Hua Teng · 2026
Read Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete by Qian Li, Xinyu Mao, Shang-Hua Teng (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-01532.txt.
Description
Li, Mao, and Teng show transformers can compute fully without position codes. Positional encoding is widely seen as a must for transformers. Without it, the next-token map looks blind to order. All prior universality proofs lean on positional data. They revisit this in the sliding-window regime of long-form reasoning. Generation there runs through a finite moving window. The window itself breaks permutation symmetry, they note. Their HIST model distills that added power precisely.
In HIST, each update uses a small state plus a token histogram. The histogram counts tokens inside the current window. They prove HIST is Turing complete via Post machines. A sliding-window transformer with no position codes can simulate HIST. Window sliding thus captures enough positional signal on its own.
Catalog record
| CREATOR | Qian Li, Xinyu Mao, Shang-Hua Teng |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.01532