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

CREATORQian Li, Xinyu Mao, Shang-Hua Teng
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.01532

Browse the full library · About the Tower of Babel