acceptodds
Under review as a conference paper at ICLR 2027

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

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.

Primary area:
learning theory
Keywords:
Turing completeness, transformers, large language model

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_5N4ROpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper shows that transformers without positional encoding using adaptive sliding window attention can simulate Post machines, hence are Turing-complete.

Critical strengths

This paper is well written for the most part and easy to follow. It has a clear contribution and its proofs seem valid.

Critical weaknesses

My main concern with this work is the fact that they consider transformers with adaptive window size, which do not correspond to the architectures used in practice. Related to this Table 1 suggests that the window size is an architectural parameter, which seems to be contradictory.

While the paper is generally well-written, I would encourage the authors to do a few modifications to make it even stronger. These do not modify my assessment of this work.

  • Related to the point above, the terms "window" and "queue" seem to be interchanged in the beginning of Section 3, which makes it a bit confusing.
  • I feel like the paragraph from lines 76 to 80 is confusing.
  • It would be nice to compare the assumptions of Remark 4 to those of previous work.
  • Some abbreviations and notations (such as TM for Turing Machine, or V∗\mathcal V^* for the set of words) are not introduced.
  • Mainly, Section 5 could be improved by adding a sketch of the proof or intuition. As a side note, it would be better to introduce the purpose of the "finite control-label set" before introducing it, and you forgot to mention the window in Theorem 8.
  • It would be useful to have a table showing the exact changes between the architectural parameters of a Post machine and that of the HIST simulating it (eg Σ→Σ2\Sigma\rightarrow\Sigma^2, Q→Q×ΣQ\rightarrow Q\times\Sigma), and the same thing for HIST$\rightarrow$transformer.
Questions for authors

Can you adapt your proof to fixed window size?

Additionally, what prevents you from reducing the CoT size and the precision? Why can't you adapt techniques from Li & Wang (2025/2026) for instance?

2 comments

We thank the reveiwer for the constructive feedback. Below we address the two main questions. As for other detailed suggestions for improving the writing and overall presentation, we will adopt them in late revisions.

Q1: Can you adapt your proof to fixed window size?

A1: Our completeness result also holds with a window whose length is fixed throughout the computation. To simulate a Turing machine using space S=O(s(n))S = O(s(n)), we can choose a window length before generation, initialize the window with the required padding, and keep the window length fixed throughout the entire computation. The transformer weights do not depend on nn or SS. Here “fixed” means fixed during a run; SS may grow with input length, since an absolute constant window for all inputs would indeed yield only a finite-state system.

The adaptive window length is an optional strengthening, introduced to address the limitation of the fixed-window length already discussed in Remark 3 (also posed as an open problem in [Li and Wang, NeurIPS 2025]): a fixed-window simulation requires an a priori upper bound s(n)s(n), usually a worst-case bound over all inputs of length nn. Adaptive growth removes this requirement and lets the window grow according to the space actually used by a particular computation.

Q2: Reducing CoT length and precision; comparison with Li & Wang.

A2: The O(s)O(s) CoT overhead arises in the Turing-machine-to-queue reduction: a leftward tape move can require rotating through the queue. Subsequent simulations add constant overhead; Theorem 8 uses at most four tokens per HIST transition. Improving that constant would leave the queue-simulation factor unchanged.

Uniform attention represents individual contributions at scale 1/m1/m for context length mm. The front-recovery signal and exact output gap have this scale. Appendix A.3 shows that O(log⁡s)O(\log s)-bit arithmetic is sufficient.

Li & Wang (2025, 2026) use PE to select specific queue locations, whereas we do not use PE. We note that the PEs used in Li & Wang (2025, 2026) are carefully designed and depend on the input length nn, which does not reflect the PEs used in practice.

I thank the authors for their answer. I would encourage them to discuss the window size question more clearly in their manuscript. As is, it might be confusing for readers not familiar with complexity theory, who are unaware that it is standard for the parameters to scale with the size of the problem.

This paper has a modest but clear contribution: positional encoding can be replaced by sliding window to prove the universality of transformers. It is also clear and well-written. I moved my score to 3 as a result.

Reviewer_bZp3OpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper shows that sliding-window Transformers without positional encodings can still achieve Turing completeness by introducing the HIST model and sliding-window can provide sufficient sequential information for universal computation.

Critical strengths
  1. The motivation of this paper is very interesting. Whether Transformers without positional encodings can achieve Turing completeness through a sliding-window mechanism is indeed a question worth investigating.

  2. The paper introduces the HIST model to facilitate the theoretical analysis, which is a novel approach. The proposed model may also provide useful insights for studying other problems.

Critical weaknesses
  1. Based on my current understanding, the paper considers an adaptive-length sliding-window mechanism (lines 281–282), where the context window can expand during generation. This seems somewhat different from the fixed-length sliding-window mechanism commonly used in practice. It would be helpful to further clarify this distinction and discuss the extent to which the theoretical results rely on the adaptive window-update mechanism.

  2. The organization and presentation of the theoretical results could be further improved. For example, Theorem 5 presents an established result that serves as a foundation for the subsequent analysis, rather than a main contribution of this paper. It might be helpful to distinguish such preliminary results more clearly from the paper's main theoretical contributions and reconsider the organization and numbering of the theorems accordingly.

Notice: I am not very familiar with the related literature in this specific area, so my comments and suggestions are for reference only.

Questions for authors

see Weakness.

1 comment

We thank the reveiwer for the constructive feedback.

Q1: How essential is the adaptive window?

A1: This is a good question. Our completeness result also holds with a window whose length is fixed throughout the computation. To simulate a Turing machine using space S=O(s(n))S = O(s(n)), we can choose a window length before generation, initialize the window with the required padding, and keep the window length fixed throughout the entire computation. The transformer weights do not depend on nn or SS. Here “fixed” means fixed during a run; SS may grow with input length, since an absolute constant window for all inputs would indeed yield only a finite-state system.

The adaptive window length is an optional strengthening, introduced to address the limitation of the fixed-window length already discussed in Remark 3 (also posed as an open problem in [Li and Wang, NeurIPS 2025]): a fixed-window simulation requires an a priori upper bound s(n)s(n), usually a worst-case bound over all inputs of length nn. Adaptive growth removes this requirement and lets the window grow according to the space actually used by a particular computation.

The operation of adaptive window length is simple: previously generated token are never recomputed. At each generation step, if a specified bit, named "control bit", in the newest token is 00, we delete the oldeset token from the window (intuitively, the window slides one cell to the right, and keeps its length unchanged); if the control bit is 11, then we keep the oldest token in the window (intuitively, the window length is increased by 11).

Q2: Distinguishing preliminaries from contributions.

A2: We agree. We will present Theorem 5 as a cited preliminary proposition.

Reviewer_AgX4OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper gives a theoretical construction showing that positional encodings are not necessary for the Turing completeness of autoregressive transformers with sliding context windows. It introduces a histogram-based intermediate model that has no direct positional access, but can recover the symbol leaving a sliding window through a specially designed edge encoding and thereby simulate a Turing-complete Post machine. The authors then construct a positional-encoding-free transformer that simulates this model, establishing universality using the temporal dynamics of the sliding window itself as the source of sequential information. The work is entirely theoretical and provides no empirical experiments demonstrating that this mechanism arises in or benefits practical transformer models.

Critical strengths
  • The paper asks a clear and interesting theoretical question,
  • The HIST model is a useful abstraction for isolating what information is really needed for universal computation.
  • The paper is reasonably careful about the scope of the theorem.
Critical weaknesses
  • The paper contains no experiments at all, so there is no evidence that the proposed mechanism matters for practical transformers. There is a noticeable gap between the practical motivation and the actual result. The introduction discusses long-form reasoning, efficiency, and length extrapolation, but these are not empirically studied. Overall, the theoretical result is interesting, but its implications for modern LLMs or practical positional-encoding design remain unclear.
Questions for authors

Could the authors discuss whether this is plausible in practice?

2 comments

We thank the reviewer for the constructive feedback.

Our paper addresses a fundamental theoretical question motivated by the practical success of transformers: Is positional encoding necessary for computational universality, or can sliding-window attention itself supply sufficient sequential structure? We show that sliding-window transformers remain Turing complete without positional encoding. We note that previous Turing completeness results rely on carefully designed PEs, which are not used in practice.

Our goal in this paper is to identify sufficient structural conditions for computational universality, rather than to model practical learning architectures or establish their efficiency or learnability. Such a mathematical characterization clarifies the computational role of architectural choices and provides a foundation for examining what is essential to achieve efficient computation and learnability.

Specifically, the HIST abstraction isolates the mechanism that supplies sufficient sequential structure in the absence of positional encoding, and our transformer construction implements it explicitly. The central claim is therefore one of computational sufficiency, established by a mathematical construction and proof.

Because Turing completeness concerns the ability to perform arbitrary computations (given unbounded resources), establishing this property requires a mathematical argument rather than any finite collection of experiments. Experiments may complement the theoretical analysis by examining efficiency and learnability, but are not required to establish the Turing completeness result.

The reviewer’s experimental suggestions are valuable for future investigations of how this mechanism operates under finite resource constraints and whether it can be learned through training. These questions form a natural next step beyond the present characterization.

We will revise the introduction to make this theoretical objective explicit and to distinguish the practical motivation from the scope and implications of our results.

Thanks for the response, and it addresses my questions. I've moved my score up to 3.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.