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

• URL: http://arxiv.org/abs/2606.01532v2
• Date: Tue, 02 Jun 2026 03:44:54 GMT
• Title: Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
• Abstract summary: Positional encoding (PE) is widely viewed as necessary for transformers to process ordered sequences.<n>This intuition underlies all prior results, which rely on positional information to prove that transformers with chain-of-thought can perform arbitrary universality.<n>We revisit this belief in the regime most relevant to long-form reasoning, where generation proceeds through a finite sliding context window.
• Score: 13.001718919406164
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• A Compositional Theory of Causally Masked Transformers [50.88598486616582]
  We develop a formalization that derives expressivity directly from the model's implemented dynamics.<n>Each attention head updates its own state independently within a layer.<n>A modified form of soft attention supports irreversible, checklist-like state.
  arXiv  Detail & Related papers  (2026-07-29T14:47:19Z)
• Clebsch-Gordan Transformer: Fast and Global Equivariant Attention [19.720202550140325]
  We propose Clebsch-Gordan Transformer, achieving efficient global attention by a novel Clebsch-Gordon Convolution on $SO(3)$ irreducible representations.<n>Our method enables equivariant modeling of features at all orders while achieving $O(N log N)$ input token complexity.<n>We benchmark our method on a diverse set of benchmarks including n-body simulation, QM9, ModelNet point cloud classification and a robotic grasping dataset.
  arXiv  Detail & Related papers  (2025-09-28T22:09:36Z)
• Constant Bit-size Transformers Are Turing Complete [6.70318953627082]
  We prove that any Turing machine running on inputs of arbitrary length can be simulated by a constant bit-size transformer.<n>Our approach relies on simulating Post machines, a Turing-complete computational model.
  arXiv  Detail & Related papers  (2025-05-22T02:45:38Z)
• On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning [87.73401758641089]
  Chain-of-thought (CoT) reasoning has improved the performance of modern language models (LMs)<n>We show that LMs can represent the same family of distributions over strings as probabilistic Turing machines.
  arXiv  Detail & Related papers  (2024-06-20T10:59:02Z)
• RFR-WWANet: Weighted Window Attention-Based Recovery Feature Resolution Network for Unsupervised Image Registration [7.446209993071451]
  The Swin transformer has attracted attention in medical image analysis due to its computational efficiency and long-range modeling capability. The registration models based on transformers combine multiple voxels into a single semantic token. This merging process limits the transformers to model and generate coarse-grained spatial information. We propose Recovery Feature Resolution Network (RFRNet), which allows the transformer to contribute fine-grained spatial information.
  arXiv  Detail & Related papers  (2023-05-07T09:57:29Z)
• Vision Transformer with Quadrangle Attention [76.35955924137986]
  We propose a novel quadrangle attention (QA) method that extends the window-based attention to a general quadrangle formulation. Our method employs an end-to-end learnable quadrangle regression module that predicts a transformation matrix to transform default windows into target quadrangles. We integrate QA into plain and hierarchical vision transformers to create a new architecture named QFormer, which offers minor code modifications and negligible extra computational cost.
  arXiv  Detail & Related papers  (2023-03-27T11:13:50Z)
• Token Turing Machines [53.22971546637947]
  Token Turing Machines (TTM) is a sequential, autoregressive Transformer model with memory for real-world sequential visual understanding. Our model is inspired by the seminal Neural Turing Machine, and has an external memory consisting of a set of tokens which summarise the previous history.
  arXiv  Detail & Related papers  (2022-11-16T18:59:18Z)
• AAformer: Auto-Aligned Transformer for Person Re-Identification [82.45385078624301]
  We introduce an alignment scheme in transformer architecture for the first time. We propose the auto-aligned transformer (AAformer) to automatically locate both the human parts and nonhuman ones at patch level. AAformer integrates the part alignment into the self-attention and the output [PART]s can be directly used as part features for retrieval.
  arXiv  Detail & Related papers  (2021-04-02T08:00:25Z)
• Addressing Some Limitations of Transformers with Feedback Memory [51.94640029417114]
  Transformers have been successfully applied to sequential, auto-regressive tasks despite being feedforward networks. We propose the Feedback Transformer architecture that exposes all previous representations to all future representations. We demonstrate on a variety of benchmarks in language modeling, machine translation, and reinforcement learning that the increased representation capacity can create small, shallow models with much stronger performance than comparable Transformers.
  arXiv  Detail & Related papers  (2020-02-21T16:37:57Z)
• Non-Autoregressive Machine Translation with Disentangled Context Transformer [70.95181466892795]
  State-of-the-art neural machine translation models generate a translation from left to right and every step is conditioned on the previously generated tokens. We propose an attention-masking based model, called Disentangled Context (DisCo) transformer, that simultaneously generates all tokens given different contexts. Our model achieves competitive, if not better, performance compared to the state of the art in non-autoregressive machine translation while significantly reducing decoding time on average.
  arXiv  Detail & Related papers  (2020-01-15T05:32:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.