🤖 machine learning

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

This paper demonstrates that positional encodings are not strictly necessary for transformers to achieve Turing completeness, as the sliding-window mechanism itself breaks permutation symmetry and provides sufficient positional information to simulate universal computation.

Original authors: Qian Li, Xinyu Mao, Shang-Hua Teng

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Qian Li, Xinyu Mao, Shang-Hua Teng

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to tell a story or solve a math problem. For a long time, computer scientists believed that to do this, the robot needed a special "address book" attached to every word it read. This address book, called Positional Encoding (PE), told the robot exactly where each word was in the sentence (1st, 2nd, 3rd, etc.). Without it, the theory went, the robot would get confused because it couldn't tell the difference between "The cat chased the dog" and "The dog chased the cat."

This paper argues that you don't actually need that address book if the robot is working with a specific type of memory: a sliding window.

Here is the core idea, broken down with some everyday analogies:

1. The Old Belief: The "Static Photo"

Think of a standard Transformer model (the kind behind many AI chatbots) as a photographer taking a picture of a whole crowd. If you just hand the photographer a pile of people's faces without telling them who is standing where, they can't tell the difference between a line of people and a random pile. They need a label on each person's forehead (Positional Encoding) to know the order.

2. The New Discovery: The "Moving Bus"

The authors realized that when AI does complex, step-by-step reasoning (like solving a long math problem), it doesn't look at the whole history at once. Instead, it uses a sliding window.

Imagine the AI is sitting on a bus with a window that only shows the last 10 people who walked by.

The Old View: If you just look at the 10 people currently in the window, you can't tell who walked in first or who walked out last. It's just a group of 10 people.
The New View: The authors noticed that the bus is moving.
- Every second, a new person steps onto the bus (enters the window).
- Every second, the oldest person falls off the back (leaves the window).

Even if the AI can't see the "street addresses" of the people inside the bus, the act of the bus moving creates a pattern. The AI can see: "Oh, a new person just got on, and I know who just fell off because the total group changed."

3. The "Magic Histogram" (The HIST Model)

To prove this, the authors invented a theoretical robot called the HIST model.

This robot is blind to order. It can't say "The red shirt is 3rd."
It only sees a count (a histogram). It knows: "There are 3 red shirts, 2 blue shirts, and 1 green shirt in the window right now."
It also has a tiny memory (a "control state") to remember the last few things that happened.

The magic trick is this: By comparing the count before a new person enters and the count after, the robot can figure out exactly who just left the bus, even without seeing their name tag.

Before: 3 Red, 2 Blue.
New person enters (Blue).
After: 3 Red, 3 Blue.
Wait, the window size is fixed! If a new Blue enters, a Red must have left.
Conclusion: The robot knows a Red shirt just fell off the back, even though it never saw the Red shirt's position.

4. The Big Result: Turing Completeness

In computer science, being "Turing Complete" means a machine can theoretically solve any problem a computer can solve, given enough time and memory.

Previous belief: Transformers needed Positional Encodings to be Turing Complete.
This paper's proof: A Transformer with a sliding window does not need Positional Encodings. The movement of the window itself provides enough "sequential information" to simulate a universal computer.

The authors built a mathematical bridge showing that:

A machine that only counts token types (the HIST model) can simulate a universal computer (specifically, a "Post Machine," which is like a computer with a queue).
A standard Transformer (without Positional Encodings) can perfectly mimic this counting machine.

5. What This Means (and What It Doesn't)

The Good News:
It turns out that the "motion" of processing data step-by-step is powerful enough to create order. You don't need to manually tag every word with a number to get universal computation. The "sliding" action breaks the symmetry on its own.

The Caveats (What the paper doesn't say):

It's not about speed: This is a proof of possibility, not efficiency. Just because a robot can solve a problem without the address book doesn't mean it will do it quickly or easily in real life.
It doesn't read exact positions: The robot still can't say "The 5th word is 'apple'." It can only deduce "Someone left the group." It's a clever trick of deduction, not a direct map.
It needs a tiny bit of math magic: The proof relies on the robot being able to count very precisely (parity checks) to know exactly who left the window. In the real world, this might require very high-precision math, which is a technical detail the authors acknowledge.

Summary

Think of the Positional Encoding as a GPS coordinate for every word. This paper says: "You don't need a GPS if you are walking down a street and watching people enter and leave a shop. The flow of people in and out tells you the story, even if you don't know their exact street addresses."

The sliding window itself is the "GPS" for the AI, making the external address book unnecessary for the machine to be capable of universal computation.

Technical Summary: Rethinking the Role of Positional Encoding in Sliding-Window Transformers

1. Problem Statement

Positional encoding (PE) has long been considered a necessary component for Transformer architectures to process ordered sequences. The prevailing intuition is that without explicit positional information, the self-attention mechanism is permutation-invariant, rendering the model unable to distinguish between different orderings of the same context tokens. This assumption underpins prior theoretical results establishing the Turing completeness of Transformers with Chain-of-Thought (CoT) reasoning, which rely heavily on PE to simulate sequential computation.

However, these universality results often assume the model attends to the entire history. In practical long-form reasoning scenarios, models operate with a finite sliding context window. As the window slides forward, tokens enter and exit, introducing a temporal asymmetry. The central question addressed by this paper is: Are positional encodings truly necessary for universal computation in sliding-window Transformers? The authors investigate whether the sliding-window mechanism itself provides sufficient sequential structure to achieve Turing completeness without explicit PE.

2. Methodology and Framework

The HIST Model

To isolate the computational power derived from the sliding window, the authors introduce an abstract autoregressive model called the HIST model.

Definition: A HIST machine generates the next token based solely on a finite control state and the token-count histogram of the current window (the vector of token frequencies indexed by the alphabet).
Constraint: The model has no access to the specific positions of individual tokens within the window; its transition function is permutation-invariant with respect to the window's content.
Parity-HIST Variant: A restricted version where the transition function depends only on the parity of the histogram (i.e., whether the count of each token type is even or odd).

Theoretical Strategy

The proof of Turing completeness proceeds in two main stages:

Simulating Post Machines: The authors prove that a Parity-HIST machine can simulate a Post Machine (a queue-based automaton known to be Turing complete).
- Key Insight: Although the Parity-HIST machine only observes the parity of the window, the FIFO (First-In-First-Out) nature of the sliding window allows it to infer the token that just left the window. By comparing the parity histogram before and after a window update (and utilizing the finite control state to store the newly entered token), the machine can deduce the identity of the "dropped" front token. This effectively simulates a queue's dequeue operation without explicit positional addressing.
Simulating Parity-HIST with Transformers: The authors construct a sliding-window Transformer without PE that can simulate the Parity-HIST model.
- Mechanism: The Transformer uses a constant-size token alphabet and an adaptive update bit. To recover the raw token counts (and thus their parity) from the attention mechanism, the construction introduces a special marker symbol (#).
- Attention Dynamics: By using uniform attention (achieved via zeroed Query and Key matrices), the attention weights become $1/m$ (where $m$ is the window size). The presence of a single marker allows the model to infer the window size $m$ and convert normalized attention masses back into raw integer counts.
- Parity Extraction: With sufficient arithmetic precision (logarithmic in the window size), the MLP layer computes the parity of the token counts, effectively replicating the Parity-HIST transition function.

3. Key Contributions and Results

Theorem 1 (High Level): The Parity-HIST model is Turing complete. The authors demonstrate that the temporal evolution of a sliding window, combined with a permutation-invariant summary (histogram parity) and finite state, is sufficient to simulate Post machines.
Theorem 2 (High Level): Every Parity-HIST machine can be simulated by a sliding-window Transformer without positional encodings.
Corollary: Sliding-window Transformers without PE are Turing complete.
Construction Details:
- The construction uses a constant-size vocabulary and a constant number of learnable parameters.
- It employs an adaptive window update mechanism where tokens carry a control bit to either slide the window (standard) or expand it (retaining the oldest token), avoiding the need to pre-specify a worst-case window size.
- The simulation requires logarithmic precision ( $O(\log S)$ ) for arithmetic operations to compute parities, where $S$ is the maximum window length.

4. Significance and Claims

The paper claims to fundamentally separate the concepts of positional encoding and sequential structure in the context of universal computation.

PE is Not Indispensable: The results demonstrate that explicit positional encodings are not a prerequisite for Transformers to perform universal computation. The "FIFO-like motion" of the sliding window itself breaks permutation symmetry and provides the necessary sequential signal.
Refining Universality: The work clarifies that while universal computation requires some source of sequential structure, this structure need not be provided by an external positional address system. It can emerge naturally from the temporal dynamics of the generation process.
Distinction from Prior Work: Unlike previous universality proofs that use PE to store circuit structures or identify specific tokens, this construction routes the simulation through a permutation-invariant window-summary model.
Limitations and Scope:
- The construction is an expressiveness result, not a claim about learnability or practical efficiency. It does not imply that standard Transformers will naturally learn these algorithms.
- The model does not recover exact token positions within the window; it only infers the identity of tokens entering and leaving.
- The construction relies on a specific parity primitive requiring logarithmic precision, which is isolated as a numerical requirement rather than a fundamental architectural limitation of the reduction.

In summary, the paper establishes that the sliding-window mechanism alone, even in the absence of positional encodings, endows Transformers with the capacity for universal computation by leveraging the temporal asymmetry of token entry and exit.