Position: The Turing-Completeness of Real-World Autoregressive Transformers Relies Heavily on Context Management

# Position: The Turing-Completeness of Real-World Autoregressive Transformers Relies Heavily on Context Management
Source: [https://arxiv.org/html/2605.19514](https://arxiv.org/html/2605.19514)
###### Abstract

Many works make the eye\-catching claim that Transformers are Turing\-complete\. However, the literature often conflates two distinct settings: \(i\) a*fixed Transformer system*setting, in which a fixed autoregressive Transformer is coupled with a fixed context\-management method to process inputs of different lengths step by step, and \(ii\) a*scaling\-family*setting, in which a family of different models \(with increasing context\-window length or numerical precision\) is used to handle different input lengths\. Existing proofs of Transformer Turing\-completeness are frequently established in setting \(ii\), whereas real\-world LLM deployment and the standard notion of Turing\-completeness correspond more naturally to setting \(i\)\. In this paper, we first formalize the fixed\-system setting, thereby providing a concrete characterization of how real\-world LLMs operate\. We then argue that results proved in the scaling\-family setting provide theoretically meaningful resource bounds but do not establish Turing\-completeness, thereby clarifying a common misinterpretation of existing results\. Finally, we show that different context\-management methods can yield sharply different computational power, and we advocate the position that context management is a central component that critically determines the computational power of real\-world autoregressive Transformers\.

Turing\-Completeness, Autoregressive Transformers, Context Management

## 1Introduction

The computational power of Transformer variants has been studied extensively, motivated by the striking capabilities of Transformer\-based large language models \(LLMs\)\. A prominent line of work claims that Transformers are Turing\-complete\(Dehghani et al\.,[2019](https://arxiv.org/html/2605.19514#bib.bib11); Pérez et al\.,[2019](https://arxiv.org/html/2605.19514#bib.bib38); Bhattamishra et al\.,[2020](https://arxiv.org/html/2605.19514#bib.bib7); Giannou et al\.,[2023](https://arxiv.org/html/2605.19514#bib.bib17); Merrill & Sabharwal,[2024](https://arxiv.org/html/2605.19514#bib.bib32); Li et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib29); Roberts,[2024](https://arxiv.org/html/2605.19514#bib.bib41); Back De Luca & Fountoulakis,[2024](https://arxiv.org/html/2605.19514#bib.bib5); Malach,[2024](https://arxiv.org/html/2605.19514#bib.bib31); Nowak et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib33); Qiu et al\.,[2025](https://arxiv.org/html/2605.19514#bib.bib39); Hou et al\.,[2025](https://arxiv.org/html/2605.19514#bib.bib22); Li & Wang,[2025](https://arxiv.org/html/2605.19514#bib.bib28); Jiang et al\.,[2026](https://arxiv.org/html/2605.19514#bib.bib24); Schuurmans,[2023](https://arxiv.org/html/2605.19514#bib.bib45); Schuurmans et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib46)\)\. In other words, Transformers are expressive enough to compute any computable function\. However, existing proofs typically rely on assumptions that are not fully justified for real\-world LLMs, which correspondingly weakens the solidity of these Turing\-completeness claims\. This leaves a natural question:Do the theoretical assumptions made in existing Turing\-completeness claims actually apply to autoregressive Transformers as they are used in practice?

In prior work, it is common to adopt assumptions such as allowing the Transformer context window to grow with the decoding step, or requiring the numerical precision of token embeddings to increase with the number of tokens processed so far\. However, such assumptions do not characterize the capability of a single Transformer; rather, they effectively describe the computational power of a collection of different Transformers used at different input lengths\. As a result, these works study an object that deviates from the single\-Transformer setting we aim to understand, and therefore do not reflect how LLMs are used in practice\. Motivated by this observation, we categorize existing works into two regimes depending on whether the Transformer is assumed to be fixed: a*fixed\-system*regime and a*scaling\-family*regime\.

In the fixed\-system regime, one fixes a single pretrained Transformer with a fixed context windowNN, fixed finite numerical precision, and fixed weights, as in real\-world Transformer\-based LLMs\. Given an input token sequence, the model processes it autoregressively by placing tokens into the context window and appending the decoded token to the end of the current sequence until a stopping condition is reached\. However, when the length of input or intermediate results exceedsNN, the current sequence cannot be fed into the context window directly\. In this case, autoregressive decoding must be coupled with a fixed context\-management mechanism that determines which tokens are provided to the context window at each step, thereby enabling the system to process arbitrarily long inputs\.

On the other hand, in the scaling\-family regime, one considers a family of models with different context\-window length, numerical precision, or depth, and uses them to process inputs of different lengths\. Many universality results fall into this second regime, even when they are informally interpreted as statements about the first\. We summarize several common assumptions that, when adopted, move the analysis away from a single fixed pretrained model and implicitly place it in the scaling\-family regime:

- •Scaling or unbounded window:assuming that inputs of arbitrary length fit into the context window, or that during autoregressive decoding each token can attend to the entire input and all previously generated tokens\.
- •Scaling or unbounded precision:assuming internal representations require precision that grows with the input length, for example log\-precision, or directly using unbounded rationals or real numbers\.

In contrast to the above assumptions, a real\-world Transformer has a fixed maximum context\-window length and fixed internal numerical precision that does not vary with the input length\. Hence, once these assumptions are adopted, the object of study is no longer a fixed real\-world Transformer, but rather a family of Transformers, where different Transformers are used for sequences of different lengths\.

#### Position and Contributions\.

We argue that theoretical studies of the computational power of Transformers should explicitly state their assumptions and distinguish scaling\-family settings from realistic fixed\-system settings\. Scaling or unbounded context windows, as well as growing or unbounded numerical precision, change the object of study from a single deployed Transformer system to a family of models\. For real\-world LLMs,the way context management, or more broadly the model’s “harness”, is coupled with the Transformer is not a peripheral implementation detail but a central component that can fundamentally change the induced computational model\.

We support this position through three contributions:

- •We formalize a computational model for a fixed Transformer system\. This provides a reference setting for discussing real\-world autoregressive LLM deployment\.
- •We distinguish fixed\-system and scaling\-family regimes and explain how common assumptions such as scaling context windows and growing numerical precision should be interpreted\. Results in the scaling\-family regime are meaningful, but they do not establish Turing\-completeness of a fixed deployed Transformer system\.
- •Under the fixed\-system formalization, we provide simple derivations showing that summarization\-style context management yields only constant\-space computation, while appending\-style methods achieve linear space; more sophisticated mechanisms can even be Turing\-complete\. These examples illustrate why context management is a central component of the induced computational model\.

#### Related Work\.

Our work is primarily motivated by a blog post\(Akhlaghpour,[2024](https://arxiv.org/html/2605.19514#bib.bib2)\)that informally argues that many Turing\-completeness claims for Transformers involve implicit issues\. However, the blog post is informal and presents these concerns by surveying related works in chronological order\. In contrast, we provide an explicit formalization, clearly separate existing settings into the fixed\-system and scaling\-family regimes, and highlight a key observation largely absent from the blog discussion: how the choice of context manager can substantially affect the computational power of real\-world LLM systems\.

#### Roadmap\.

Section[2](https://arxiv.org/html/2605.19514#S2)reviews the background needed for our formalization and analysis\. Section[3](https://arxiv.org/html/2605.19514#S3)defines the computational process of a fixed Transformer system\(T,D,C\)\(T,D,C\)\. Section[4](https://arxiv.org/html/2605.19514#S4)explains why interpreting scaling\-family results as “autoregressive Transformers are Turing\-complete” reflects a misconception, and surveys representative claims by identifying the scaling assumptions they rely on\. Section[5](https://arxiv.org/html/2605.19514#S5)analyzes the computational power and separations of fixed Transformer systems under different context\-management methods\. Finally, Section[6](https://arxiv.org/html/2605.19514#S6)summarizes our conclusion and presents a call to action\.

## 2Preliminaries

This section reviews the background concepts that will be used later: \(i\) Turing machines \(TMs\), transducers, and complexity classes, \(ii\) Boolean circuits, and \(iii\) a minimal abstraction of Transformers and autoregressive decoding\.

### 2\.1Notation

LetΣ\\Sigmabe a finite alphabet\. A string overΣ\\Sigmais an element ofΣ∗≔⋃ℓ=0∞Σℓ\\Sigma^\{\*\}\\coloneqq\\bigcup\_\{\\ell=0\}^\{\\infty\}\\Sigma^\{\\ell\}, whereΣ0=\{ϵ\}\\Sigma^\{0\}=\\left\\\{\\epsilon\\right\\\}andϵ\\epsilondenotes the empty string\. For a stringxx, let\|x\|\|x\|denote its length\. For integers1≤a≤b≤\|x\|1\\leq a\\leq b\\leq\|x\|, we writexa:bx\_\{a:b\}for the substringxa​⋯​xbx\_\{a\}\\cdots x\_\{b\}\. A languageLLoverΣ\\Sigmais a set of strings, i\.e\.,L⊆Σ∗L\\subseteq\\Sigma^\{\*\}\. A partial function fromAAtoBB, denotedg:A⇀Bg:A\\rightharpoonup B, is a mapping that may be undefined for somea∈Aa\\in A\.

### 2\.2TMs, Transducers, and Complexity Classes

Turing machines\(TMs\) are a classical computational model proposed by Alan Turing\(Turing,[1937](https://arxiv.org/html/2605.19514#bib.bib49)\)to formalize the notion of computability\. Informally, a \(multi\-tape\) Turing machine consists ofkktapes, each extending infinitely in one direction and divided into cells that store symbols\. Each tape is equipped with a read\-write head that can move left or right\. Initially, the input is written on the tape\(s\) according to a fixed convention, and all other cells contain a blank symbol\. At each step, the machine reads symbols, updates its state, writes symbols, and moves the heads according to a finite set of rules\. Atransduceris a machine that maps an input string to an output string; one convenient model is a TM with a read\-only input tape, a work tape, and a write\-only output tape\. We use standard complexity classes such asDTIME​\(t​\(n\)\)\\textsf\{DTIME\}\(t\(n\)\)andDSPACE​\(s​\(n\)\)\\textsf\{DSPACE\}\(s\(n\)\)for languages that can be decided deterministically inO​\(t​\(n\)\)O\(t\(n\)\)time orO​\(s​\(n\)\)O\(s\(n\)\)auxiliary space\. We useFDTIME​\(t​\(n\)\)\\textsf\{FDTIME\}\(t\(n\)\)andFDSPACE​\(s​\(n\)\)\\textsf\{FDSPACE\}\(s\(n\)\)for the corresponding function problems\. When discussing space complexity, we can ignore the constant number of tapes, since anykk\-tape Turing machine can be simulated by a single\-tape one using at most a factor\-kkincrease in space\.

### 2\.3Boolean Circuits

ABoolean circuitis a computational model for a Boolean functionf:\{0,1\}n→\{0,1\}mf:\\left\\\{0,1\\right\\\}^\{n\}\\to\\left\\\{0,1\\right\\\}^\{m\}\. It can be represented as a finite directed acyclic graph \(DAG\) withnnsource nodesx1,⋯,xnx\_\{1\},\\cdots,x\_\{n\}as inputs andmmsink nodesy1,⋯,ymy\_\{1\},\\cdots,y\_\{m\}as outputs\. All other nodes are logic gates such as AND, OR, NOT, and edges are wires carrying bits\. Given an input assignmentx∈\{0,1\}nx\\in\\left\\\{0,1\\right\\\}^\{n\}to the input nodes, each gate is evaluated by applying its operation to the values on its incoming wires, and the values at the output nodes definef​\(x\)∈\{0,1\}mf\(x\)\\in\\left\\\{0,1\\right\\\}^\{m\}\. Unlike a single Turing machine which can process inputs of arbitrary length, a single Boolean circuit only handles inputs of a fixed length\. Therefore, in circuit complexity, we typically study afamilyof circuits\{Cn:n∈ℕ\}\\left\\\{C\_\{n\}:n\\in\\mathbb\{N\}\\right\\\}, whereCnC\_\{n\}handles inputs of lengthnn\.

### 2\.4Turing\-Completeness

Turing\-completenessis a notion used to characterize whether a class of objects is at least as expressive as Turing machines\. To define Turing\-completeness, we first define Turing\-computable functions\. A partial functionf:Σ∗⇀Σ∗f:\\Sigma^\{\*\}\\rightharpoonup\\Sigma^\{\*\}isTuring\-computableif there exists a TMMMsuch that for allx,y∈Σ∗x,y\\in\\Sigma^\{\*\},f​\(x\)=yf\(x\)=yif and only ifMMhalts on inputxxand outputsyy\. A collection of objects𝒩\\mathcal\{N\}isTuring\-completeif for every Turing\-computable partial functionffthere exists an objectN∈𝒩N\\in\\mathcal\{N\}that computesff\. From this definition, a necessary condition for Turing\-completeness is that each object supports inputs of unbounded length\.

### 2\.5Transformers

The Transformer\(Vaswani et al\.,[2017](https://arxiv.org/html/2605.19514#bib.bib50)\)model is a well\-known neural network architecture designed for sequence modeling which relies primarily on self\-attention mechanism to capture the content of the sentence and to generate results\. Transformer models can be broadly categorized by whether they include encoder layers and/or decoder layers into three families: encoder\-only Transformers \(e\.g\., BERT\(Devlin et al\.,[2019](https://arxiv.org/html/2605.19514#bib.bib12)\), RoBERTa\(Liu et al\.,[2019](https://arxiv.org/html/2605.19514#bib.bib30)\)\), encoder\-decoder Transformers \(e\.g\., the vanilla Transformer\(Vaswani et al\.,[2017](https://arxiv.org/html/2605.19514#bib.bib50)\), T5\(Raffel et al\.,[2020](https://arxiv.org/html/2605.19514#bib.bib40)\), BART\(Lewis et al\.,[2020a](https://arxiv.org/html/2605.19514#bib.bib26)\)\), and decoder\-only Transformers \(e\.g\., GPT\(Brown et al\.,[2020](https://arxiv.org/html/2605.19514#bib.bib8); Achiam et al\.,[2023](https://arxiv.org/html/2605.19514#bib.bib1)\), LLaMA\(Touvron et al\.,[2023](https://arxiv.org/html/2605.19514#bib.bib48)\), Gemini\(Gemini Team et al\.,[2023](https://arxiv.org/html/2605.19514#bib.bib15),[2024](https://arxiv.org/html/2605.19514#bib.bib16)\), DeepSeek\(DeepSeek\-AI et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib10); Guo et al\.,[2025](https://arxiv.org/html/2605.19514#bib.bib20)\), and Qwen\(Bai et al\.,[2023](https://arxiv.org/html/2605.19514#bib.bib6); Yang et al\.,[2025](https://arxiv.org/html/2605.19514#bib.bib51)\)\)\.

Given an input sentence, a tokenizer is applied before the Transformer to map the raw text to a sequence of discrete tokens from a finite vocabularyΣ\\Sigma\. This token sequence is then fed into the Transformer\. In practice, tokens are mapped to token IDs before being input to the Transformer\. Since this is only an encoding choice, we still treatΣ\\Sigmaas the token domain\. A pretrained decoder\-only Transformer with context window lengthNNand fixed numerical precision can be abstracted as a fixed functionTTthat maps anNN\-token sequence111Although the Transformer’s input length is fixed toNN, in practice a single forward pass can process any input sequence of length at mostNN\. If the input is shorter thanNN, it is padded with<pad\>\. When we say that a sequence of length<N<Nis placed into the context window, we omit the padding step for brevity\.to next\-token logits, and hence to a distribution overΣ\\Sigma\. Formally,T:ΣN→Δ​\(Σ\)T:\\Sigma^\{N\}\\to\\Delta\(\\Sigma\), whereΔ​\(Σ\)\\Delta\(\\Sigma\)denotes the set of all distributions onΣ\\Sigma\. As a supplement, many Transformer architectures use positional encodings to incorporate token\-position information, either at the embedding stage \(e\.g\., the sinusoidal PE in the vanilla Transformer\(Vaswani et al\.,[2017](https://arxiv.org/html/2605.19514#bib.bib50)\)or the learned PE in BERT\(Devlin et al\.,[2019](https://arxiv.org/html/2605.19514#bib.bib12)\)\) or within self\-attention \(e\.g\., RoPE\(Su et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib47)\)\)\. In this case, we may regard the input within the context window as a length\-NNstring overΣ×𝒫\\Sigma\\times\\mathcal\{P\}, where𝒫=\{0,1\}ppos\\mathcal\{P\}=\\left\\\{0,1\\right\\\}^\{p\_\{\\text\{pos\}\}\}for a fixedpposp\_\{\\text\{pos\}\}\. Thus, using positional encodings only enlarges the alphabet by a constant factor, and we will not mention them separately in what follows\. For our purposes, the architectural details of attention are not essential and are deferred to Appendix[A](https://arxiv.org/html/2605.19514#A1)\. What matters is that \(i\) the input length \(the context\-window length\) of a single Transformer is a fixed constantNN, and \(ii\) all parameters and internal representations use fixed finite precision\.

### 2\.6Autoregressive Decoding and Context Management

Decoder\-only Transformers are typically used via autoregressive decoding\. Given a current token sequencex=x1​⋯​xℓx=x\_\{1\}\\cdots x\_\{\\ell\}, we feedxxinto the TransformerTTto obtain a next\-token distributionT​\(x\)T\(x\), apply a decoding ruleDDto select the next tokenxℓ\+1x\_\{\\ell\+1\}, and append it to the end ofxxto form the new sequence, iterating this procedure\. This process is well defined when the sequence length does not exceed the context\-window lengthNN\. To continue decoding when the sequence length exceedsNN, one must introduce a context\-management mechanismCCthat determines which tokens are provided to the context window at each step\. Section[3](https://arxiv.org/html/2605.19514#S3)formalizes this computation process as a fixed system\.

## 3The Fixed\-System Regime for Transformers

We now formalize computation of autoregressive Transformers in the fixed\-system regime\. The goal is to make explicit what is fixed and what can grow with the decoding steps\.

### 3\.1The System\(T,D,C\)\(T,D,C\)and Its Execution

Fix a finite token vocabularyΣ\\Sigmaand a context window lengthNN\. A*fixed Transformer system*is a triple\(T,D,C\)\(T,D,C\):

- •TTis a fixed pretrained Transformer, viewed as a function that maps any stringw∈ΣNw\\in\\Sigma^\{N\}in its context window to a distributionμw∈Δ​\(Σ\)\\mu\_\{w\}\\in\\Delta\(\\Sigma\)over the next token\.
- •DDis a deterministic222For simplicity, we assume the next\-token selection rule is deterministic and single\-valued\. If not, one can adopt a nondeterministic\-TM\-style convention and define the Transformer’s output as the set of all valid next tokens\.constant\-time decoding rule that maps a distribution overΣ\\Sigmato an output token inΣ\\Sigma\. Typical choices include greedy decoding \(arg⁡max\\arg\\max\) or a fixed\-temperature softmax sampling with a fixed seed\.
- •CCis a deterministic context manager\. At steptt, it maintains internal state and stringsr\(t\)∈Σ∗r^\{\(t\)\}\\in\\Sigma^\{\*\}, produces a context stringw\(t\)∈ΣNw^\{\(t\)\}\\in\\Sigma^\{N\}viaw\(t\)=Cw​\(r\(t\)\)w^\{\(t\)\}=C\_\{w\}\\left\(r^\{\(t\)\}\\right\), and then updates its state and strings after decodingx^t\+1\\hat\{x\}\_\{t\+1\}by settingr\(t\+1\)=Cr​\(x^t\+1,r\(t\)\)∈Σ∗r^\{\(t\+1\)\}=C\_\{r\}\\left\(\\hat\{x\}\_\{t\+1\},r^\{\(t\)\}\\right\)\\in\\Sigma^\{\*\}\.

Given an input stringx=x1​x2​⋯​xn∈Σ∗x=x\_\{1\}x\_\{2\}\\cdots x\_\{n\}\\in\\Sigma^\{\*\}, we feed it toCCand setr\(1\)=xr^\{\(1\)\}=x\. The system then repeatedly appliesw\(t\)=Cw​\(r\(t\)\)w^\{\(t\)\}=C\_\{w\}\\left\(r^\{\(t\)\}\\right\)to form the token sequence fed into the context window,x^t\+1=D​\(T​\(w\(t\)\)\)\\hat\{x\}\_\{t\+1\}=D\\left\(T\\left\(w^\{\(t\)\}\\right\)\\right\)to obtain the next token, andr\(t\+1\)=Cr​\(x^t\+1,r\(t\)\)r^\{\(t\+1\)\}=C\_\{r\}\\left\(\\hat\{x\}\_\{t\+1\},r^\{\(t\)\}\\right\)to update its maintained strings, until a stopping condition ofCCis met\. The system output is the generated token sequence \(or a final answer extracted by a fixed convention\)\. For decision problems, we can designate special accept and reject tokens and say that the system decides a language by eventually emitting exactly one of them\. For function computation, we view the system as a transducer that outputs a string\.

### 3\.2Some Common Context\-Management Methods

We summarize several common context\-management methods that will be referenced later\.

#### Summarization\-Style\.

A common approach is to compress earlier parts of the history via summarization, e\.g\., latent compression methods such as AutoCompressor\(Chevalier et al\.,[2023](https://arxiv.org/html/2605.19514#bib.bib9)\)and ICAE\(Ge et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib14)\), or the/compressor/compactcommands as used in Gemini\-CLI\(Google,[2026a](https://arxiv.org/html/2605.19514#bib.bib18)\), OpenAI Codex CLI\(OpenAI,[2026a](https://arxiv.org/html/2605.19514#bib.bib34)\), and Claude Code\(Anthropic,[2026a](https://arxiv.org/html/2605.19514#bib.bib3)\), which replaces part of the earlier context with a shorter summary\. Given an input sequencex=x1​⋯​xn∈Σ∗x=x\_\{1\}\\cdots x\_\{n\}\\in\\Sigma^\{\*\}and settingr\(1\)=xr^\{\(1\)\}=x, an example summarization\-style context\-management process operates as follows:

- •Normal decoding phase\.If\|r\(t\)\|<N−1\|r^\{\(t\)\}\|<N\-1, the context manager providesw\(t\)=r\(t\)w^\{\(t\)\}=r^\{\(t\)\}to the Transformer\. Given the decoded next tokenx^t\+1\\hat\{x\}\_\{t\+1\}, there are two cases\. Ifx^t\+1\\hat\{x\}\_\{t\+1\}is the end\-of\-sequence token<EOS\>, the system terminates\. Otherwise, setr\(t\+1\)=r\(t\)∘x^t\+1r^\{\(t\+1\)\}=r^\{\(t\)\}\\circ\\hat\{x\}\_\{t\+1\}\.
- •Summarization phase\.If\|r\(t\)\|≥N−1\|r^\{\(t\)\}\|\\geq N\-1, the context manager providesw\(t\)=<s\>∘r1:N−1\(t\)w^\{\(t\)\}=\\texttt\{<s\>\}\\circ r^\{\(t\)\}\_\{1:N\-1\}to the Transformer, where<s\>is a summary\-instruction token that triggers summarization\. The Transformer then decodesx^t\+1\\hat\{x\}\_\{t\+1\}as a summary of the contents in the window, and we updater\(t\+1\)=x^t\+1∘rN:\|r\(t\)\|\(t\)r^\{\(t\+1\)\}=\\hat\{x\}\_\{t\+1\}\\circ r^\{\(t\)\}\_\{N:\|r^\{\(t\)\}\|\}\. For simplicity, we assume that the summary is a single token\. To generate a multi\-token summary, we can reserve a budget oftttokens \(with1<t≤N/21<t\\leq N/2\) in the context window, that is, trigger summarization when\|r\(t\)\|≥N−t\|r^\{\(t\)\}\|\\geq N\-tinstead ofN−1N\-1\. Once summarization is triggered, the model can generate a length\-<t<tsummary autoregressively \(i\.e\., by invoking the normal decoding phase as a subroutine\) and prepend the resulting summary sequence tor\(t\)r^\{\(t\)\}\.

Figure[1](https://arxiv.org/html/2605.19514#S3.F1)illustrates the summarization\-style context manager described above\.

Transformerx^\\hat\{x\}Transformerx^\\hat\{x\}⟹\\Longrightarrowx^\\hat\{x\}Figure 1:Illustration of summarization\-style context management\. Left: normal decoding phase\. Right: summarization phase\. Teal tokens indicate the segment to be summarized, the red token is the summary\-instruction token<s\>, and the yellow token denotes the generated summaryx^\\hat\{x\}\.
#### Appending\-Style\.

Another method, similar to that used by Schuurmans et al\.\(Schuurmans et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib46)\), treats the Transformer’s context window as a sliding window and appends predicted tokens to the end of the sequence\. Given an input sequencex=x1​⋯​xn∈Σ∗x=x\_\{1\}\\cdots x\_\{n\}\\in\\Sigma^\{\*\}and settingr\(1\)=xr^\{\(1\)\}=x, an example appending\-style context\-management process operates as follows\. At steptt, the context manager providesw\(t\)=r1:min⁡\{\|r\(t\)\|,N\}\(t\)w^\{\(t\)\}=r^\{\(t\)\}\_\{1:\\min\\left\\\{\|r^\{\(t\)\}\|,N\\right\\\}\}to the Transformer and obtainsx^t\+1\\hat\{x\}\_\{t\+1\}\. Ifx^t\+1\\hat\{x\}\_\{t\+1\}is a halting token in a designated setHH, the system terminates\. Otherwise, it appends the decoded token to the end ofr\(t\)r^\{\(t\)\}and shifts the window forward by one token, i\.e\.,r\(t\+1\)=r2:\|r\(t\)\|\(t\)∘x^t\+1r^\{\(t\+1\)\}=r^\{\(t\)\}\_\{2:\|r^\{\(t\)\}\|\}\\circ\\hat\{x\}\_\{t\+1\}\. Figure[2](https://arxiv.org/html/2605.19514#S3.F2)illustrates the appending\-style context manager described above\.

Transformerx^\\hat\{x\}⟹\\LongrightarrowTransformerx^\\hat\{x\}Figure 2:Illustration of appending\-style context management\. Left: decode a new tokenx^\\hat\{x\}to append to the end of the sequence\. Right: shift the window forward by11token\.
#### Other Methods and Remark on the Power ofCC\.

Beyond the two methods mentioned above, many other context\-management mechanisms have been proposed\. For example, many systems write important information to external storage and retrieve it when needed, as in retrieval\-augmented generation and external\-memory\-based agents\(Guu et al\.,[2020](https://arxiv.org/html/2605.19514#bib.bib21); Lewis et al\.,[2020b](https://arxiv.org/html/2605.19514#bib.bib27); Packer et al\.,[2023](https://arxiv.org/html/2605.19514#bib.bib37)\)\. Other systems, such as ToolFormer\(Schick et al\.,[2023](https://arxiv.org/html/2605.19514#bib.bib44)\), GPT\(OpenAI,[2026b](https://arxiv.org/html/2605.19514#bib.bib35)\), Claude\(Anthropic,[2026b](https://arxiv.org/html/2605.19514#bib.bib4)\), and Gemini\(Google,[2026b](https://arxiv.org/html/2605.19514#bib.bib19)\), also incorporate tool calls or function calls to access external resources\. We remark that the definition of a context managerCCis very broad\. With such an unrestrictedCC, the overall system can become trivially powerful\. For example, ifCCcan call a Turing\-complete tool \(e\.g\., by executing Python programs\), then\(T,D,C\)\(T,D,C\)is Turing\-complete regardless ofTT\. Therefore, when we analyze several of these methods in Section[5](https://arxiv.org/html/2605.19514#S5), we explicitly restrict the capabilities ofCC, while still covering common deployed mechanisms such as summarization and sliding windows\.

## 4Alternative Views

Many works make \(or are commonly interpreted as making\) the claim:*Autoregressive Transformers are Turing\-complete\.*To interpret this claim precisely, one must specify the computational regime\. In the fixed\-system regime, Turing\-completeness would mean that for any Turing machine, there exists a single fixed system\(T,D,C\)\(T,D,C\)can correctly simulate it on inputs of arbitrary length\. In contrast, in the scaling\-family regime, it suffices to prove that for each input lengthnn\(or number of stepstt\), there exists a Transformer model whose context\-window length or numerical precision depends onnn\(ortt\) that simulates the desired computation\. Only the fixed\-system regime matches the way real\-world LLMs are deployed, where the pretrained model is fixed and inputs are handled by a fixed context\-manager\.

In this section, we first clarify why Turing machine simulation results proved in the scaling\-family regime should not be interpreted as establishing Turing\-completeness\. We then survey representative works and identify whether they implicitly adopt the assumptions listed in Section[1](https://arxiv.org/html/2605.19514#S1), which place their analysis in the scaling\-family regime and therefore do not by themselves establish Turing\-completeness of a fixed autoregressive Transformer system\.

### 4\.1Scaling Models Does Not Mean Turing\-Complete

By Definition[2\.4](https://arxiv.org/html/2605.19514#S2.SS4), to establish Turing\-completeness for autoregressive Transformers in the fixed\-system regime, one must show that for every Turing\-computable partial functionffthere exists a single system\(T,D,C\)\(T,D,C\)that computesffon inputs of unbounded length\. In contrast, showing that longer inputs or longer decoding runs can be simulated by a scaled model only yields a resource bound for Transformers to handle different input lengths\. This is closer in spirit to a circuit\-complexity result\. Savage\(Savage,[1972](https://arxiv.org/html/2605.19514#bib.bib43)\)showed that if a languageLLis decidable in timeDTIME​\(T​\(n\)\)\\textsf\{DTIME\}\(T\(n\)\), then for eachnnthere exists a circuitCnC\_\{n\}of sizeO​\(\(T​\(n\)\)2\)O\(\(T\(n\)\)^\{2\}\)that decidesLLon length\-nninputs\. Scaling circuit size withnndoes not make a single circuit universal\. It produces a family of circuits, one for each input length\. Similarly, scaling the context\-window length or the numerical precision yields a scaling\-family viewpoint rather than Turing\-completeness of a fixed pretrained Transformer system\. Beyond this conceptual misalignment, real\-world LLMs operate with a fixed finite context window and rely on context management to handle inputs of arbitrary length, whereas the scaling\-family regime assumes that arbitrarily long histories can be placed into the context window\. This also departs from how LLMs are used in practice\.

### 4\.2Works That Scale Transformers

In this subsection, we review representative works that claim Turing\-completeness for Transformers, or claim that Turing machines can be simulated by Transformers, and identify which ones explicitly or implicitly fall into the scaling\-family regime\. We group these works into two categories\.

#### Group A: Scaling Window\.

A large fraction of “Transformer simulates TM” arguments implicitly assume that, given an input sequence of lengthnn, at decoding stepttthe token at positionn\+tn\+tcan attend to all tokens in the sequence within a single Transformer forward pass\. This effectively requires the context\-window length at stepttto be at leastn\+tn\+t\. Works that explicitly or implicitly adopt this assumption include\(Dehghani et al\.,[2019](https://arxiv.org/html/2605.19514#bib.bib11); Pérez et al\.,[2019](https://arxiv.org/html/2605.19514#bib.bib38); Bhattamishra et al\.,[2020](https://arxiv.org/html/2605.19514#bib.bib7); Merrill & Sabharwal,[2024](https://arxiv.org/html/2605.19514#bib.bib32); Li et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib29); Roberts,[2024](https://arxiv.org/html/2605.19514#bib.bib41); Malach,[2024](https://arxiv.org/html/2605.19514#bib.bib31); Nowak et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib33); Qiu et al\.,[2025](https://arxiv.org/html/2605.19514#bib.bib39); Hou et al\.,[2025](https://arxiv.org/html/2605.19514#bib.bib22); Jiang et al\.,[2026](https://arxiv.org/html/2605.19514#bib.bib24)\)\. This group also includes looped or recurrent Transformer variants that repeatedly modify a fixed length input\. Although the context\-window length may not grow with the number of decoding steps in these formulations, handling longer inputs still requires a model with a larger context window\. Thus, these works are also scaling the window in essence\. Works that explicitly or implicitly adopt this assumption include\(Giannou et al\.,[2023](https://arxiv.org/html/2605.19514#bib.bib17); Back De Luca & Fountoulakis,[2024](https://arxiv.org/html/2605.19514#bib.bib5); Li & Wang,[2025](https://arxiv.org/html/2605.19514#bib.bib28)\)\.

#### Group B: Scaling Precision\.

Several constructions require the precision of token embeddings or internal representation matrices to grow with the input lengthnnor the number of decoding stepstt, or they assume exact unbounded\-precision real or rational arithmetic\. This is incompatible with the fixed finite precision of deployed models\. Works that explicitly or implicitly adopt this assumption include\(Dehghani et al\.,[2019](https://arxiv.org/html/2605.19514#bib.bib11); Pérez et al\.,[2019](https://arxiv.org/html/2605.19514#bib.bib38); Bhattamishra et al\.,[2020](https://arxiv.org/html/2605.19514#bib.bib7); Giannou et al\.,[2023](https://arxiv.org/html/2605.19514#bib.bib17); Merrill & Sabharwal,[2024](https://arxiv.org/html/2605.19514#bib.bib32); Li et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib29); Roberts,[2024](https://arxiv.org/html/2605.19514#bib.bib41); Back De Luca & Fountoulakis,[2024](https://arxiv.org/html/2605.19514#bib.bib5); Nowak et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib33); Qiu et al\.,[2025](https://arxiv.org/html/2605.19514#bib.bib39); Hou et al\.,[2025](https://arxiv.org/html/2605.19514#bib.bib22); Jiang et al\.,[2026](https://arxiv.org/html/2605.19514#bib.bib24)\)\.

Table[1](https://arxiv.org/html/2605.19514#S4.T1)summarizes the assumptions used in related works\. Regarding the context\-window length, all related works in the scaling\-family setting assume a non\-constant context window\. Regarding numerical precision, only two works assume constant precision\. These misalignments make the corresponding Turing\-completeness claims more subtle and arguably debatable\.

Table 1:Assumptions used in representative works\. “Window” denotes the context\-window length, i\.e\., the sequence length processed by a single self\-attention operation\. “Precision” denotes the number of bits used to represent one token\. Herenndenotes the initial input length,ttdenotes the number of decoding steps \(often interpreted as the CoT length\), ands​\(n\)s\(n\)denotes the space complexity to recognize the language\. “Unbounded” precision means the proof assumes exact real / rational computation without a concrete precision bound\.WindowPrecisionWorkn\+tn\+tunbounded\(Dehghani et al\.,[2019](https://arxiv.org/html/2605.19514#bib.bib11)\)\*,\(Pérez et al\.,[2019](https://arxiv.org/html/2605.19514#bib.bib38); Bhattamishra et al\.,[2020](https://arxiv.org/html/2605.19514#bib.bib7); Roberts,[2024](https://arxiv.org/html/2605.19514#bib.bib41); Nowak et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib33); Jiang et al\.,[2026](https://arxiv.org/html/2605.19514#bib.bib24)\)poly​\(n\)\\mathrm\{poly\}\(n\)\(Li et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib29)\)†\\daggerO​\(log⁡\(n\+t\)\)O\(\\log\(n\+t\)\)\(Merrill & Sabharwal,[2024](https://arxiv.org/html/2605.19514#bib.bib32); Li et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib29)\)†\\dagger,\(Qiu et al\.,[2025](https://arxiv.org/html/2605.19514#bib.bib39)\),\(Hou et al\.,[2025](https://arxiv.org/html/2605.19514#bib.bib22)\)\*O​\(1\)O\(1\)\(Malach,[2024](https://arxiv.org/html/2605.19514#bib.bib31)\)\*†\\daggernnunbounded\(Back De Luca & Fountoulakis,[2024](https://arxiv.org/html/2605.19514#bib.bib5)\)O​\(log⁡n\)O\(\\log n\)\(Giannou et al\.,[2023](https://arxiv.org/html/2605.19514#bib.bib17)\)s​\(n\)s\(n\)O​\(1\)O\(1\)\(Li & Wang,[2025](https://arxiv.org/html/2605.19514#bib.bib28)\)
- \*The original paper does not explicitly state an upper bound on the numerical precision, to the best of our understanding\.
- †\\daggerThe original paper does not explicitly claim that Turing\-completeness has been proved; instead, it claims that one can construct a Transformer that simulates the execution of a Turing machine on a given input instance\.

### 4\.3Works with a Fixed Transformer

Two works highlight that, even with fixed numerical precision and a fixed context window, computational universality can arise by modifying the overall system, especially the context\-management interface\.

1. 1\.Schuurmans\(Schuurmans,[2023](https://arxiv.org/html/2605.19514#bib.bib45)\)claims that a fixed Transformer\-based LLM will be Turing\-complete when augmented with access to external memory\. The paper provides experimental evidence that a real LLM can simulate all single\-step operations of a Turing\-complete language, but it does not give a constructive theoretical proof of how a Transformer realizes these operations\.
2. 2\.Schuurmans et al\.\(Schuurmans et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib46)\)propose an extended autoregressive decoding system with a fixed context window that can be Turing\-complete by generating up to two output tokens per step and appending them to the token sequence for future processing\.

These works suggest that, in the fixed Transformer system regime, Turing\-completeness may be achieved by modifying the decoding procedure or designing different context\-management mechanisms, so scaling the Transformer itself is not necessary\. Section[5](https://arxiv.org/html/2605.19514#S5)further analyzes how different context\-management methods affect the computational power of a fixed Transformer system\.

## 5Our Position: Context Management Matters for Real\-World Transformers

In Section[4](https://arxiv.org/html/2605.19514#S4), we point out that existing studies often conflate settings that align with real\-world Transformers with settings that depart from them, while broadly claiming that Transformers are Turing\-complete\. Our position is different\. We argue that, in the fixed Transformer system setting that better reflects real\-world deployed Transformers, the method of context management has a greater impact on the system’s computational power than the Transformer itself\.

To support our view, we use simple theoretical derivations to analyze how different context\-management methods affect the upper bound of the computational power of the entire system\. Specifically, we examine two context\-management methods, namely summarization\-style context management and appending\-style context management\. We prove that, when combined with a fixed\-context\-window, fixed\-precision Transformer, summarization\-style context management leads to a system bounded by a constant\-space Turing machine, whereas appending\-style context management yields a system with the same power as a linear\-space Turing machine\. In addition, drawing on existing works, we point out that the resulting systems are Turing\-complete if the Transformer is allowed to read from and write to memory through a context\-management mechanism, or if the Transformer is allowed to decode one or two tokens at a time\.

Through the survey in Section[4\.2](https://arxiv.org/html/2605.19514#S4.SS2)and Section[4\.3](https://arxiv.org/html/2605.19514#S4.SS3), we show that most papers focus only on the importance of the Transformer itself while overlooking the importance of harnesses such as context management\. Therefore, our position paper highlights an issue that has been overlooked by the community and provides corrective guidance for subsequent research in this direction by emphasizing the importance of context management\.

### 5\.1Analysis of Different Context\-Management Methods

Next, we discuss how different context\-management methods affect the computational power of Transformer systems with a fixed context\-window size and fixed precision\. As discussed in Section[3](https://arxiv.org/html/2605.19514#S3), an unrestricted context managerCCcan make the overall system trivially powerful\. Accordingly, we focus on “simple enough” context managers\. Such a manager maintains onlyNNmemory cells for the Transformer’s context window andO​\(1\)O\(1\)auxiliary memory cells for states, beyond storing token strings organized in simple data structures such as queues\. It can apply only fixed local operations to these maintained strings, for example extracting a prefix by popping a constant number of tokens, shifting a window by a constant amount, appending tokens by pushing them to the tail, and querying the Transformer for the next token\. This convention captures the summarization\-style and appending\-style context managers described in Section[3\.2](https://arxiv.org/html/2605.19514#S3.SS2), while excluding the ability to run general algorithms\.

#### Summarization\-Style Context Management\.

Next, we show that the system induced by summarization\-style context management is upper bounded by a deterministic constant\-space Turing machine, orFDSPACE​\(1\)\\textsf\{FDSPACE\}\(1\)333Strictly speaking, space complexity classes are defined for machines that halt on all inputs\. A machine using bounded space need not halt, so our use of space\-complexity notation is a mild abuse adopted for notational convenience\. The same caveat applies throughout\.\.

###### Proposition 5\.1\.

Any fixed Transformer system\(T,D,C\)\(T,D,C\), whereCCis a summarization\-style context manager, can be simulated by a Turing machine using constant space\.

###### Proof\.

AssumeTThas context\-window lengthN=O​\(1\)N=O\(1\)tokens, with each input token inΣ\\Sigma\. An observation that will be used implicitly in what follows is that a single decoding step of a Transformer,D​\(T​\(⋅\)\):ΣN→ΣD\(T\(\\cdot\)\):\\Sigma^\{N\}\\to\\Sigma, can be simulated by a Turing machine in constant space \(with the constant depending onNN\)\.

We construct a one\-way transducer to simulate each stepttof the computation process of the system\(T,D,C\)\(T,D,C\), where the head of the read\-only input tape never moves left \(recall that a transducer can be formalized as a three\-tape Turing machine with a read\-only input tape, a read/write work tape, and a write\-only output tape\)\.

Initialization\.At initialization, the input tape contains the input stringx=x1​⋯​xn∈Σ∗x=x\_\{1\}\\cdots x\_\{n\}\\in\\Sigma^\{\*\}, the other two tapes are blank, and all heads start at the first cell\. We write a boundary marker\#\\\#in cellN\+1N\+1of the work tape to partition the tape into two parts: cells11throughNNsimulate the contents of the Transformer’s context windoww\(t\)w^\{\(t\)\}, while cellN\+2N\+2onward is the workspace region used to simulate a single Transformer decoding stepD​\(T​\(w\(t\)\)\)D\(T\(w^\{\(t\)\}\)\)\.

Simulating stepttof the system\.At the beginning of the simulation of thett\-th step of a Transformer system with summarization\-style context management, we copy \(token by token\) the symbol under the input head and append it to the end of the token string on the work tape, until either the number of tokens on the work tape reachesN−1N\-1or the input tape is exhausted\. We then distinguish two cases based on the number of tokens currently on the work tape:

- •If the number of tokens on the work tape is less thanN−1N\-1\(denote the length byℓ<N−1\\ell<N\-1\), we simulate one Transformer decoding stepD​\(T​\(⋅\)\)D\(T\(\\cdot\)\)in the workspace region using these tokens as input\. We then write the decoded tokenx^t\+1\\hat\{x\}\_\{t\+1\}into cellℓ\+1\\ell\+1, and finally clear the workspace region\.
- •If the number of tokens on the work tape isN−1N\-1, we shift these tokens one cell to the right and write the summary token<s\>in the first cell\. We then simulate one Transformer decoding stepD​\(T​\(⋅\)\)D\(T\(\\cdot\)\)in the workspace using these length\-NNtoken sequence, write the decoded tokenx^t\+1\\hat\{x\}\_\{t\+1\}into the first cell of the work tape, and finally clear the work tape so that onlyx^t\+1\\hat\{x\}\_\{t\+1\}in the first cell and the boundary marker \# in cellN\+1N\+1remain\.

The transducer then proceeds to simulate stept\+1t\+1of the system\. It is easy to see that, during the simulation of any steptt, the token sequence on the work tape \(excluding the boundary marker\#\\\#\), concatenated with the token sequence on the input tape at and to the right of the input head, is always equal tor\(t\)r^\{\(t\)\}\. The first case, in which placing all ofr\(t\)r^\{\(t\)\}into the context window yields a length no greater thanN−1N\-1, corresponds exactly to\|r\(t\)\|<N−1\|r^\{\(t\)\}\|<N\-1, while the second case corresponds to\|r\(t\)\|≥N−1\|r^\{\(t\)\}\|\\geq N\-1\. In both cases, the Turing machine simulates the Transformer system correctly\. Consequently, the above Turing machine correctly simulates the behavior of\(T,D,C\)\(T,D,C\)\. For the space bound, the length of the work\-tape portion ofr\(t\)r^\{\(t\)\}is at mostNN, and the simulation additionally requires constant space to simulate one Transformer decoding step\. Hence, the total space usage is constant\. ∎

A standard fact of regular languages is thatREG=DSPACE​\(1\)=NSPACE​\(1\)\\textsf\{REG\}=\\textsf\{DSPACE\}\(1\)=\\textsf\{NSPACE\}\(1\)\(see, e\.g\.,\(Gasarch,[2015](https://arxiv.org/html/2605.19514#bib.bib13); Rothvoss,[2024](https://arxiv.org/html/2605.19514#bib.bib42)\)\), whereREGdenotes the class of regular languages, andNSPACE​\(1\)\\textsf\{NSPACE\}\(1\)denotes constant space on a nondeterministic Turing machine\. Therefore, whenCCis summarization\-style and the Transformer’s context\-window length, depth, and numerical precision are fixed constants \(i\.e\., do not scale with the input lengthnn\), the system\(T,D,C\)\(T,D,C\)can recognize only regular languages \(assuming it halts\), even if decoding is nondeterministic\. In particular, such a fixed system cannot recognize non\-regular languages such as equality\{x​\#​x:x∈Σ∗\}\\left\\\{x\\\#x:x\\in\\Sigma^\{\*\}\\right\\\}, palindromes\{x​\#​xR:x∈Σ∗\}\\left\\\{x\\\#x^\{R\}:x\\in\\Sigma^\{\*\}\\right\\\}, or binary addition\{bin​\(x\)​\#​bin​\(y\)​\#​bin​\(z\):x\+y=z\}\\left\\\{\\mathrm\{bin\}\(x\)\\\#\\mathrm\{bin\}\(y\)\\\#\\mathrm\{bin\}\(z\):x\+y=z\\right\\\}\.

Another point worth noting is that in our construction, the workspace uses spacessthat is at least of the same order asNN\(with an additional contribution coming from the space needed to simulate the Transformer\)\. When translating this into an equivalent finite\-state automaton, the resulting upper bound on the number of states grows exponentially inss, which in a sense provides an alternative perspective on scaling laws\(Kaplan et al\.,[2020](https://arxiv.org/html/2605.19514#bib.bib25)\)\. Although this does not change the theoretical fact that the decidable languages remain regular, the languages the system can decide become more complex from the perspective of the number of states required by the corresponding finite\-state automaton\.

#### Appending\-Style Context Management\.

Next, we discuss the computational power of appending\-style context management\.

###### Proposition 5\.2\.

Any fixed Transformer system\(T,D,C\)\(T,D,C\), whereCCis an appending\-style context manager, can be simulated by a deterministic Turing machine using space linear in the input lengthnn\.

###### Proof\.

The construction is straightforward\. At initialization, the Turing machine copies the entire current sequence to the work tape\. At decoding steptt, it copies the firstNNtokens into a workspace region starting from celln\+1n\+1, simulates one Transformer decoding step, and obtainsx^t\+1\\hat\{x\}\_\{t\+1\}\. It writesx^t\+1\\hat\{x\}\_\{t\+1\}into celln\+1n\+1, shifts the content in cells22throughn\+1n\+1one position to the left, and clears all other cells on the work tape\. ∎

The proposition above shows that any fixed Transformer system with appending\-style context management can be simulated by a linear\-space Turing machine\. We can also show the converse direction\. Before stating the proposition and its proof, we briefly review the extended autoregressive decoding system defined by Schuurmans et al\.\(Schuurmans et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib46)\)\. TheirNN\-gram extended autoregressive decoding is based on a sliding window\. Initially, the current token string is set to the inputx=x1​⋯​xnx=x\_\{1\}\\cdots x\_\{n\}\. At each decoding step, the firstNNtokens are fed into a fixed decoding functionM:ΣN→Σ∗M:\\Sigma^\{N\}\\to\\Sigma^\{\*\}, which outputs a decoded token string \(and the process halts if the output falls in a designated halting set\)\. The decoded string is appended to the end of the current sequence, and the first token is removed\. When the output length ofMMis at mostKK, the resulting system is called an\(N,K\)\(N,K\)\-restricted system\. We also need the following lemma \(Lemma[5\.3](https://arxiv.org/html/2605.19514#S5.Thmtheorem3)\), whose proof is deferred to Appendix[B](https://arxiv.org/html/2605.19514#A2)\.

###### Lemma 5\.3\.

LetΣ\\Sigmabe a finite alphabet\. For any functionf:Σ2→Σf:\\Sigma^\{2\}\\to\\Sigma, there exists a decoder\-only TransformerTTsuch that for every length\-22context\(a,b\)∈Σ2\(a,b\)\\in\\Sigma^\{2\}, greedy decoding outputsf​\(a,b\)f\(a,b\)\.

We are now ready to state and prove the converse direction\.

###### Proposition 5\.4\.

Any deterministic Turing machine that uses linear space can be simulated by a fixed Transformer system\(T,D,C\)\(T,D,C\), whereTThas context\-window length22andCCis an appending\-style context manager\.

###### Proof\.

By the definition of an\(N,K\)\(N,K\)\-restricted system, our fixed Transformer system with an appending\-style context manager is a special case withK=1K=1, where the decoding functionMMis implemented by the composition of a TransformerTTand a decoding ruleDD444In the definition of\(Schuurmans et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib46)\), whenK=1K=1the decoding output ofMMcan contain zero or one token\. In our appending\-style context management, this can be modeled by including an empty symbol inΣ\\Sigmaand ignoring it when appending\.\. Schuurmans et al\.\(Schuurmans et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib46)\)show that the computation of any linear\-space Turing machine can be simulated by a\(2,1\)\(2,1\)\-restricted system\. According to Lemma[5\.3](https://arxiv.org/html/2605.19514#S5.Thmtheorem3), any functionf:Σ2→Σf:\\Sigma^\{2\}\\to\\Sigmacan be realized by a TransformerTTwith context\-window length22coupled with the greedy decoding rule, and the claim follows\. ∎

Propositions[5\.2](https://arxiv.org/html/2605.19514#S5.Thmtheorem2)and[5\.4](https://arxiv.org/html/2605.19514#S5.Thmtheorem4)suggest that a single fixed Transformer system with appending\-style context management has the same computational power as a linear\-space Turing machine\. In particular, it can decide exactly the class of deterministic context\-sensitive languages,DCSL=DSPACE​\(n\)\\textsf\{DCSL\}=\\textsf\{DSPACE\}\(n\)\(see, e\.g\.,\(Ibarra,[1991](https://arxiv.org/html/2605.19514#bib.bib23); Otto,[2006](https://arxiv.org/html/2605.19514#bib.bib36)\)\)\. Schuurmans et al\.\(Schuurmans et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib46)\)also show that a\(2,2\)\(2,2\)\-restricted system is Turing\-complete\. If one could extend Lemma[5\.3](https://arxiv.org/html/2605.19514#S5.Thmtheorem3)to show that a context\-window\-22Transformer can realize any functionΣ2→Σ2\\Sigma^\{2\}\\to\\Sigma^\{2\}by applying greedy decoding to the two output positions𝒀​\(1,:\)\\boldsymbol\{Y\}\(1,:\)and𝒀​\(2,:\)\\boldsymbol\{Y\}\(2,:\), then this would yield a Turing\-complete system as well\. Note that this changes the decoding interface from next\-token decoding to next\-two\-tokens decoding\. In Appendix[C](https://arxiv.org/html/2605.19514#A3), we briefly discuss how one might preserve next\-token decoding by modifying the context manager to perform two decoding steps and then discard one of the produced tokens\.

Table[2](https://arxiv.org/html/2605.19514#S5.T2)summarizes the computational power of a fixed Transformer system under different context managers\. We conclude that different context managers can endow the same underlying model with markedly different computational power, which supports our position:the Turing\-completeness of real\-world autoregressive Transformers relies heavily on context management\.

Table 2:Computational power under different context managers\. Here≡\\equivdenotes equivalence and≤\\leqdenotes no more powerful than\.WorkContext ManagementPower\(Schuurmans,[2023](https://arxiv.org/html/2605.19514#bib.bib45)\)read / write memory≡\\equivTM\(Schuurmans et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib46)\)\(2,2\)\(2,2\)\-restricted sys\.≡\\equivTM\(Schuurmans et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib46)\)\(2,1\)\(2,1\)\-restricted sys\.≡O​\(n\)\\equiv O\(n\)\-space TMOursappending\-style≡O​\(n\)\\equiv O\(n\)\-space TMOurssummarization\-style≤O​\(1\)\\leq O\(1\)\-space TM

## 6Summary and Call to Action

In this paper, we formalized the computation of a fixed Transformer system and distinguished two settings for the Turing\-completeness of autoregressive Transformers\. We showed that the scaling\-family setting is theoretically misaligned with the notion of Turing\-completeness and, in practice, does not match how real\-world LLMs are deployed and used\. We then analyzed the fixed\-system setting and demonstrated that context management can substantially affect the computational power of Transformers\.

We conclude with three calls to action\.

- •First, claims about Transformer Turing\-completeness shouldexplicitly state their computational setting and assumptions\. Scaling\-family results are valuable for understanding resource requirements, such as context length, precision, and depth, but should not be interpreted as Turing\-completeness of a fixed real\-world Transformer system\.
- •Second, since real\-world deployed LLM systems consist of a fixed\-context\-window, fixed\-precision Transformer together with a particular context\-management method, theoretical work shoulddevote more attention to the capabilities of the overall system obtained by combining different context\-management methods with a fixed Transformer\.
- •Third, the community shouldgo beyond qualitative Turing\-completeness results and develop resource\-sensitive, system\-level notions of Transformer capability under realistic deployment constraints, since Turing\-completeness concerns computability under a specified encoding rather than problem understanding or learning\.

## Acknowledgements

This research was supported in part by National Natural Science Foundation of China \(No\. L2524018, No\. U2241212, No\. 92470128, No\. 62472430\) and by Industrial AI Solutions, Li Auto Inc\. We also wish to acknowledge the support provided by the fund for building world\-class universities \(disciplines\) of Renmin University of China, by Engineering Research Center of Next\-Generation Intelligent Search and Recommendation, Ministry of Education, by Intelligent Social Governance Interdisciplinary Platform, Major Innovation & Planning Interdisciplinary Platform for the “Double\-First Class” Initiative, Public Policy and Decision\-making Research Lab, and Public Computing Cloud, Renmin University of China\.

The work was partially done at Gaoling School of Artificial Intelligence, Beijing Key Laboratory of Research on Large Models and Intelligent Governance, Engineering Research Center of Next\-Generation Intelligent Search and Recommendation, MOE, and Pazhou Laboratory \(Huangpu\), Guangzhou, Guangdong 510555, China\.

We would also like to thank Hessameddin Akhlaghpour for the blog postAre Transformers Turing\-Complete? A Good Disguise Is All You Need, which inspired us to further examine and carefully distinguish the assumptions in existing theoretical works that align with real\-world practice from those that do not\. It also motivated us to investigate, under assumptions that better reflect real\-world Transformers, how the capabilities of these models are closely tied to context management\. We also thank the anonymous reviewers for their valuable comments\.

## References

- Achiam et al\. \(2023\)Achiam, J\., Adler, S\., Agarwal, S\., Ahmad, L\., Akkaya, I\., Aleman, F\. L\., Almeida, D\., Altenschmidt, J\., Altman, S\., Anadkat, S\., et al\.GPT\-4 technical report\.*arXiv preprint arXiv:2303\.08774*, 2023\.
- Akhlaghpour \(2024\)Akhlaghpour, H\.Are transformers turing\-complete? a good disguise is all you need\., October 2024\.URL[https://lifeiscomputation\.com/transformers\-are\-not\-turing\-complete/](https://lifeiscomputation.com/transformers-are-not-turing-complete/)\.Blog post\. Updated: 2024\-10\-14\.
- Anthropic \(2026a\)Anthropic\.Commands\.Claude Code Documentation, 2026a\.URL[https://code\.claude\.com/docs/en/commands](https://code.claude.com/docs/en/commands)\.Accessed: 2026\-05\-12\.
- Anthropic \(2026b\)Anthropic\.Tool use with claude\.Claude Docs, 2026b\.URL[https://platform\.claude\.com/docs/en/agents\-and\-tools/tool\-use/overview](https://platform.claude.com/docs/en/agents-and-tools/tool-use/overview)\.Accessed: 2026\-05\-12\.
- Back De Luca & Fountoulakis \(2024\)Back De Luca, A\. and Fountoulakis, K\.Simulation of graph algorithms with looped transformers\.In*Proceedings of the 41st International Conference on Machine Learning*, pp\. 2319–2363, 2024\.
- Bai et al\. \(2023\)Bai, J\., Bai, S\., Chu, Y\., Cui, Z\., Dang, K\., Deng, X\., Fan, Y\., Ge, W\., Han, Y\., Huang, F\., et al\.Qwen technical report\.*arXiv preprint arXiv:2309\.16609*, 2023\.
- Bhattamishra et al\. \(2020\)Bhattamishra, S\., Patel, A\., and Goyal, N\.On the computational power of transformers and its implications in sequence modeling\.In*Proceedings of the 24th Conference on Computational Natural Language Learning*, pp\. 455–475, 2020\.
- Brown et al\. \(2020\)Brown, T\., Mann, B\., Ryder, N\., Subbiah, M\., Kaplan, J\. D\., Dhariwal, P\., Neelakantan, A\., Shyam, P\., Sastry, G\., Askell, A\., et al\.Language models are few\-shot learners\.*Advances in neural information processing systems*, 33:1877–1901, 2020\.
- Chevalier et al\. \(2023\)Chevalier, A\., Wettig, A\., Ajith, A\., and Chen, D\.Adapting language models to compress contexts\.In Bouamor, H\., Pino, J\., and Bali, K\. \(eds\.\),*Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing*, pp\. 3829–3846, Singapore, 12 2023\. Association for Computational Linguistics\.
- DeepSeek\-AI et al\. \(2024\)DeepSeek\-AI, Liu, A\., Feng, B\., Xue, B\., Wang, B\., Wu, B\., Lu, C\., Zhao, C\., Deng, C\., Zhang, C\., Ruan, C\., et al\.DeepSeek\-V3 technical report\.*arXiv preprint arXiv:2412\.19437*, 2024\.
- Dehghani et al\. \(2019\)Dehghani, M\., Gouws, S\., Vinyals, O\., Uszkoreit, J\., and Kaiser, L\.Universal transformers\.In*International Conference on Learning Representations*, 2019\.
- Devlin et al\. \(2019\)Devlin, J\., Chang, M\.\-W\., Lee, K\., and Toutanova, K\.BERT: Pre\-training of deep bidirectional transformers for language understanding\.In*Proceedings of the 2019 conference of the North American chapter of the association for computational linguistics: human language technologies, volume 1 \(long and short papers\)*, pp\. 4171–4186, 2019\.
- Gasarch \(2015\)Gasarch, W\.Classifying problems into complexity classes\.University of Maryland, College Park, 11 2015\.URL[https://www\.cs\.umd\.edu/~gasarch/papers/classcomp\.pdf](https://www.cs.umd.edu/~gasarch/papers/classcomp.pdf)\.Accessed: 2026\-01\-22\.
- Ge et al\. \(2024\)Ge, T\., Jing, H\., Wang, L\., Wang, X\., Chen, S\.\-Q\., and Wei, F\.In\-context autoencoder for context compression in a large language model\.In*The Twelfth International Conference on Learning Representations*, 2024\.
- Gemini Team et al\. \(2023\)Gemini Team, Anil, R\., Borgeaud, S\., Alayrac, J\.\-B\., Yu, J\., Soricut, R\., Schalkwyk, J\., Dai, A\. M\., Hauth, A\., Millican, K\., et al\.Gemini: A family of highly capable multimodal models\.*arXiv preprint arXiv:2312\.11805*, 2023\.
- Gemini Team et al\. \(2024\)Gemini Team, Georgiev, P\., Lei, V\. I\., Burnell, R\., Bai, L\., Gulati, A\., Tanzer, G\., Vincent, D\., Pan, Z\., Wang, S\., et al\.Gemini 1\.5: Unlocking multimodal understanding across millions of tokens of context\.*arXiv preprint arXiv:2403\.05530*, 2024\.
- Giannou et al\. \(2023\)Giannou, A\., Rajput, S\., Sohn, J\.\-y\., Lee, K\., Lee, J\. D\., and Papailiopoulos, D\.Looped transformers as programmable computers\.In*International Conference on Machine Learning*, pp\. 11398–11442\. PMLR, 2023\.
- Google \(2026a\)Google\.CLI Commands\.Gemini CLI Documentation, 2026a\.URL[https://google\-gemini\.github\.io/gemini\-cli/docs/cli/commands\.html](https://google-gemini.github.io/gemini-cli/docs/cli/commands.html)\.Accessed: 2026\-05\-12\.
- Google \(2026b\)Google\.Function calling with the Gemini API\.Gemini API Docs, 2026b\.URL[https://ai\.google\.dev/gemini\-api/docs/function\-calling](https://ai.google.dev/gemini-api/docs/function-calling)\.Accessed: 2026\-05\-12\.
- Guo et al\. \(2025\)Guo, D\., Yang, D\., Zhang, H\., Song, J\., Wang, P\., Zhu, Q\., Xu, R\., Zhang, R\., Ma, S\., Bi, X\., et al\.DeepSeek\-R1 incentivizes reasoning in llms through reinforcement learning\.*Nature*, 645\(8081\):633–638, 2025\.
- Guu et al\. \(2020\)Guu, K\., Lee, K\., Tung, Z\., Pasupat, P\., and Chang, M\.Retrieval augmented language model pre\-training\.In*International conference on machine learning*, pp\. 3929–3938\. PMLR, 2020\.
- Hou et al\. \(2025\)Hou, K\., Brandfonbrener, D\., Kakade, S\. M\., Jelassi, S\., and Malach, E\.Universal length generalization with turing programs\.In*International Conference on Machine Learning*, pp\. 23873–23893\. PMLR, 2025\.
- Ibarra \(1991\)Ibarra, O\. H\.On resetting dlba’s\.*ACM SIGACT News*, 22\(1\):62–63, 1991\.
- Jiang et al\. \(2026\)Jiang, H\., Hahn, M\., Zetzsche, G\., and Lin, A\. W\.Softmax transformers are turing\-complete\.In*The Fourteenth International Conference on Learning Representations*, 2026\.
- Kaplan et al\. \(2020\)Kaplan, J\., McCandlish, S\., Henighan, T\., Brown, T\. B\., Chess, B\., Child, R\., Gray, S\., Radford, A\., Wu, J\., and Amodei, D\.Scaling laws for neural language models\.*arXiv preprint arXiv:2001\.08361*, 2020\.
- Lewis et al\. \(2020a\)Lewis, M\., Liu, Y\., Goyal, N\., Ghazvininejad, M\., Mohamed, A\., Levy, O\., Stoyanov, V\., and Zettlemoyer, L\.BART: Denoising sequence\-to\-sequence pre\-training for natural language generation, translation, and comprehension\.In*Proceedings of the 58th annual meeting of the association for computational linguistics*, pp\. 7871–7880, 2020a\.
- Lewis et al\. \(2020b\)Lewis, P\., Perez, E\., Piktus, A\., Petroni, F\., Karpukhin, V\., Goyal, N\., Küttler, H\., Lewis, M\., Yih, W\.\-t\., Rocktäschel, T\., et al\.Retrieval\-augmented generation for knowledge\-intensive nlp tasks\.*Advances in neural information processing systems*, 33:9459–9474, 2020b\.
- Li & Wang \(2025\)Li, Q\. and Wang, Y\.Constant bit\-size transformers are turing complete\.*Advances in Neural Information Processing Systems*, 38:62273–62292, 2025\.
- Li et al\. \(2024\)Li, Z\., Liu, H\., Zhou, D\., and Ma, T\.Chain of thought empowers transformers to solve inherently serial problems\.In*The Twelfth International Conference on Learning Representations*, 2024\.
- Liu et al\. \(2019\)Liu, Y\., Ott, M\., Goyal, N\., Du, J\., Joshi, M\., Chen, D\., Levy, O\., Lewis, M\., Zettlemoyer, L\., and Stoyanov, V\.RoBERTa: A robustly optimized BERT pretraining approach\.*arXiv preprint arXiv:1907\.11692*, 2019\.
- Malach \(2024\)Malach, E\.Auto\-regressive next\-token predictors are universal learners\.In*Proceedings of the 41st International Conference on Machine Learning*, pp\. 34417–34431, 2024\.
- Merrill & Sabharwal \(2024\)Merrill, W\. and Sabharwal, A\.The expressive power of transformers with chain of thought\.In*The Twelfth International Conference on Learning Representations*, 2024\.
- Nowak et al\. \(2024\)Nowak, F\., Svete, A\., Butoi, A\., and Cotterell, R\.On the representational capacity of neural language models with chain\-of\-thought reasoning\.In*Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\)*, pp\. 12510–12548, 2024\.
- OpenAI \(2026a\)OpenAI\.Slash commands in Codex CLI\.OpenAI Developers Documentation, 2026a\.URL[https://developers\.openai\.com/codex/cli/slash\-commands\#keep\-transcripts\-lean\-with\-compact](https://developers.openai.com/codex/cli/slash-commands#keep-transcripts-lean-with-compact)\.Accessed: 2026\-05\-12\.
- OpenAI \(2026b\)OpenAI\.Function calling\.OpenAI API Docs, 2026b\.URL[https://developers\.openai\.com/api/docs/guides/function\-calling](https://developers.openai.com/api/docs/guides/function-calling)\.Accessed: 2026\-05\-12\.
- Otto \(2006\)Otto, F\.Restarting automata\.In*Recent Advances in Formal Languages and Applications*, volume 25, pp\. 269–303\. Springer, 2006\.
- Packer et al\. \(2023\)Packer, C\., Wooders, S\., Lin, K\., Fang, V\., Patil, S\. G\., Stoica, I\., and Gonzalez, J\. E\.MemGPT: Towards llms as operating systems\.*arXiv preprint arXiv:2310\.08560*, 2023\.
- Pérez et al\. \(2019\)Pérez, J\., Marinković, J\., and Barceló, P\.On the turing completeness of modern neural network architectures\.In*International Conference on Learning Representations*, 2019\.
- Qiu et al\. \(2025\)Qiu, R\., Xu, Z\., Bao, W\., and Tong, H\.Ask, and it shall be given: On the turing completeness of prompting\.In*The Thirteenth International Conference on Learning Representations*, 2025\.
- Raffel et al\. \(2020\)Raffel, C\., Shazeer, N\., Roberts, A\., Lee, K\., Narang, S\., Matena, M\., Zhou, Y\., Li, W\., and Liu, P\. J\.Exploring the limits of transfer learning with a unified text\-to\-text transformer\.*Journal of machine learning research*, 21\(140\):1–67, 2020\.
- Roberts \(2024\)Roberts, J\.How powerful are decoder\-only transformer neural models?In*2024 International Joint Conference on Neural Networks \(IJCNN\)*, pp\. 1–8\. IEEE, 2024\.
- Rothvoss \(2024\)Rothvoss, T\.Computational complexity i\.CSE 531 \(Winter 2024\) lecture notes, University of Washington, 2024\.URL[https://sites\.math\.washington\.edu/~rothvoss/archive/lecturenotes/complexity\-CSE531\-Winter2024\.pdf](https://sites.math.washington.edu/~rothvoss/archive/lecturenotes/complexity-CSE531-Winter2024.pdf)\.Accessed: 2026\-05\-12\.
- Savage \(1972\)Savage, J\. E\.Computational work and time on finite machines\.*Journal of the ACM \(JACM\)*, 19\(4\):660–674, 1972\.
- Schick et al\. \(2023\)Schick, T\., Dwivedi\-Yu, J\., Dessì, R\., Raileanu, R\., Lomeli, M\., Hambro, E\., Zettlemoyer, L\., Cancedda, N\., and Scialom, T\.Toolformer: Language models can teach themselves to use tools\.*Advances in Neural Information Processing Systems*, 36:68539–68551, 2023\.
- Schuurmans \(2023\)Schuurmans, D\.Memory augmented large language models are computationally universal\.*arXiv preprint arXiv:2301\.04589*, 2023\.
- Schuurmans et al\. \(2024\)Schuurmans, D\., Dai, H\., and Zanini, F\.Autoregressive large language models are computationally universal\.*arXiv preprint arXiv:2410\.03170*, 2024\.
- Su et al\. \(2024\)Su, J\., Ahmed, M\., Lu, Y\., Pan, S\., Bo, W\., and Liu, Y\.Roformer: Enhanced transformer with rotary position embedding\.*Neurocomputing*, 568:127063, 2024\.
- Touvron et al\. \(2023\)Touvron, H\., Lavril, T\., Izacard, G\., Martinet, X\., Lachaux, M\.\-A\., Lacroix, T\., Rozière, B\., Goyal, N\., Hambro, E\., Azhar, F\., et al\.LLaMA: Open and efficient foundation language models\.*arXiv preprint arXiv:2302\.13971*, 2023\.
- Turing \(1937\)Turing, A\. M\.On computable numbers, with an application to the entscheidungsproblem\.*Proceedings of the London Mathematical Society*, s2\-42\(1\):230–265, 1937\.
- Vaswani et al\. \(2017\)Vaswani, A\., Shazeer, N\., Parmar, N\., Uszkoreit, J\., Jones, L\., Gomez, A\. N\., Kaiser, Ł\., and Polosukhin, I\.Attention is all you need\.*Advances in neural information processing systems*, 30, 2017\.
- Yang et al\. \(2025\)Yang, A\., Li, A\., Yang, B\., Zhang, B\., Hui, B\., Zheng, B\., Yu, B\., Gao, C\., Huang, C\., Lv, C\., et al\.Qwen3 technical report\.*arXiv preprint arXiv:2505\.09388*, 2025\.

\\appendixpage

## Appendix AMore Details of Transformers

We first introduce our notation for vectors and matrices\. Bold lowercase letters such as𝒙\\boldsymbol\{x\}denote vectors \(column vectors unless stated otherwise\), and bold uppercase letters such as𝑿\\boldsymbol\{X\}denote matrices\. We write𝒙​\(i\)\\boldsymbol\{x\}\(i\)for theii\-th entry of𝒙\\boldsymbol\{x\}\. For a matrix𝑿\\boldsymbol\{X\},𝑿​\(i,:\)\\boldsymbol\{X\}\(i,:\)denotes theii\-th row \(as a row vector\),𝑿​\(:,j\)\\boldsymbol\{X\}\(:,j\)denotes thejj\-th column \(as a column vector\), and𝑿​\(i,j\)\\boldsymbol\{X\}\(i,j\)denotes the\(i,j\)\(i,j\)\-th entry\.

Below, we describe in detail a single forward pass of a Transformer:

- •Embedding:A Transformer first maps each token ID to a token embedding vector of dimensiondd\. This is done by an embedding layer that applies a pointwise lookup\-table functiong:\[\|Σ\|\]→ℝdg:\[\|\\Sigma\|\]\\to\\mathbb\{R\}^\{d\}to each token ID\. In some architectures, positional information is incorporated at the embedding stage by adding a positional encoding \(PE\) to the embedding vectors, such as the sinusoidal PE in the vanilla Transformer\(Vaswani et al\.,[2017](https://arxiv.org/html/2605.19514#bib.bib50)\)or the learned PE in BERT\(Devlin et al\.,[2019](https://arxiv.org/html/2605.19514#bib.bib12)\), to make the model aware of token positions\. In other cases, positional information is introduced within self\-attention \(described later\), for example via RoPE\(Su et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib47)\), which is used by many LLMs\. In summary, the embedding layer can be formulated as a mappingemb:\[\|Σ\|\]N×ℕN→ℝN×d\\mathrm\{emb\}:\[\|\\Sigma\|\]^\{N\}\\times\\mathbb\{N\}^\{N\}\\to\\mathbb\{R\}^\{N\\times d\}, which maps at mostNNtoken IDs \(whereNNis the context window length, i\.e\., the maximum input length accepted by the Transformer\) together with their position indices to an embedding matrix\.
- •Multi\-head masked self\-attention decoding:The self\-attention mechanism is one of the most fundamental components of Transformers\. First, in theℓ\\ell\-th self\-attention decoding layer, we apply linear maps to obtain the query, key, and value matrices𝑸\(ℓ\),𝑲\(ℓ\),𝑽\(ℓ\)∈ℝN×d\\boldsymbol\{Q\}^\{\(\\ell\)\},\\boldsymbol\{K\}^\{\(\\ell\)\},\\boldsymbol\{V\}^\{\(\\ell\)\}\\in\\mathbb\{R\}^\{N\\times d\}, namely𝑸\(ℓ\)=𝑿\(ℓ\)​𝑾Q\(ℓ\)\\boldsymbol\{Q\}^\{\(\\ell\)\}=\\boldsymbol\{X\}^\{\(\\ell\)\}\\boldsymbol\{W\}^\{\(\\ell\)\}\_\{Q\},𝑲\(ℓ\)=𝑿\(ℓ\)​𝑾K\(ℓ\)\\boldsymbol\{K\}^\{\(\\ell\)\}=\\boldsymbol\{X\}^\{\(\\ell\)\}\\boldsymbol\{W\}^\{\(\\ell\)\}\_\{K\}, and𝑽\(ℓ\)=𝑿\(ℓ\)​𝑾V\(ℓ\)\\boldsymbol\{V\}^\{\(\\ell\)\}=\\boldsymbol\{X\}^\{\(\\ell\)\}\\boldsymbol\{W\}^\{\(\\ell\)\}\_\{V\}, where𝑿\(ℓ\)∈ℝN×d\\boldsymbol\{X\}^\{\(\\ell\)\}\\in\\mathbb\{R\}^\{N\\times d\}is the input embedding matrix and𝑾Q\(ℓ\),𝑾K\(ℓ\),𝑾V\(ℓ\)∈ℝd×d\\boldsymbol\{W\}^\{\(\\ell\)\}\_\{Q\},\\boldsymbol\{W\}^\{\(\\ell\)\}\_\{K\},\\boldsymbol\{W\}^\{\(\\ell\)\}\_\{V\}\\in\\mathbb\{R\}^\{d\\times d\}are weight matrices\. For multi\-head masked self\-attention, we split each matrix along the embedding dimension intoHHsubmatrices\{𝑸h\(ℓ\),𝑲h\(ℓ\),𝑽h\(ℓ\)∈ℝN×dh:h∈\[H\]\}\\left\\\{\\boldsymbol\{Q\}^\{\(\\ell\)\}\_\{h\},\\boldsymbol\{K\}^\{\(\\ell\)\}\_\{h\},\\boldsymbol\{V\}^\{\(\\ell\)\}\_\{h\}\\in\\mathbb\{R\}^\{N\\times d\_\{h\}\}:h\\in\[H\]\\right\\\}such that∑h∈\[H\]dh=d\\sum\_\{h\\in\[H\]\}d\_\{h\}=d, and assign them toHHattention heads\. On each head, the masked self\-attention output is computed as 𝑿~h\(ℓ\)=softmax​\(𝑸h\(ℓ\)​\(𝑲h\(ℓ\)\)⊤dh\+𝑴\)​𝑽h\(ℓ\),\\tilde\{\\boldsymbol\{X\}\}^\{\(\\ell\)\}\_\{h\}=\\mathrm\{softmax\}\\left\(\\frac\{\\boldsymbol\{Q\}^\{\(\\ell\)\}\_\{h\}\(\\boldsymbol\{K\}^\{\(\\ell\)\}\_\{h\}\)^\{\\top\}\}\{\\sqrt\{d\_\{h\}\}\}\+\\boldsymbol\{M\}\\right\)\\boldsymbol\{V\}^\{\(\\ell\)\}\_\{h\},\(1\)where𝑴∈\{0,−∞\}N×N\\boldsymbol\{M\}\\in\\left\\\{0,\-\\infty\\right\\\}^\{N\\times N\}is the causal mask, defined by𝑴​\(i,j\)=−∞\\boldsymbol\{M\}\(i,j\)=\-\\inftyif and only ifi<ji<j\. We then concatenate\{𝑿~h\(ℓ\):h∈\[H\]\}\\left\\\{\\tilde\{\\boldsymbol\{X\}\}^\{\(\\ell\)\}\_\{h\}:h\\in\[H\]\\right\\\}to recover the original shape, add the result to the input𝑿\(ℓ\)\\boldsymbol\{X\}^\{\(\\ell\)\}via a residual connection, and feed it into an MLP \(also with a residual connection\) to obtain the layer output𝑿\(ℓ\+1\)\\boldsymbol\{X\}^\{\(\\ell\+1\)\}\.
- •Classification head:After the final decoding layer, we map the output matrix𝑿\(L\)∈ℝN×d\\boldsymbol\{X\}^\{\(L\)\}\\in\\mathbb\{R\}^\{N\\times d\}through a linear projection𝑾∈ℝd×\|Σ\|\\boldsymbol\{W\}\\in\\mathbb\{R\}^\{d\\times\|\\Sigma\|\}to obtain the token logits at each position, i\.e\.,𝒀=𝑿\(L\)​𝑾∈ℝN×\|Σ\|\\boldsymbol\{Y\}=\\boldsymbol\{X\}^\{\(L\)\}\\boldsymbol\{W\}\\in\\mathbb\{R\}^\{N\\times\|\\Sigma\|\}\.

## Appendix BProof of Lemma[5\.3](https://arxiv.org/html/2605.19514#S5.Thmtheorem3)

See[5\.3](https://arxiv.org/html/2605.19514#S5.Thmtheorem3)

###### Proof\.

Without loss of generality, assumeΣ=\{1,2,⋯,K\}\\Sigma=\\left\\\{1,2,\\cdots,K\\right\\\}\. Letdmodel=K\+2​K\+K2d\_\{\\text\{model\}\}=K\+2K\+K^\{2\}, and partition each token embedding \(row\) vector𝒙∈ℝ1×dmodel\\boldsymbol\{x\}\\in\\mathbb\{R\}^\{1\\times d\_\{\\text\{model\}\}\}555All arithmetic operations in this proof can be carried out to constant precision \(with constants depending only on\|Σ\|\|\\Sigma\|\); we useℝ\\mathbb\{R\}only for notational convenience\.into three blocks,𝒙≔\(𝒙tok;𝒙feat;𝒙pair\)\\boldsymbol\{x\}\\coloneqq\\left\(\\boldsymbol\{x\}^\{\\text\{tok\}\};\\boldsymbol\{x\}^\{\\text\{feat\}\};\\boldsymbol\{x\}^\{\\text\{pair\}\}\\right\), with dimensionsKK,2​K2K, andK2K^\{2\}, respectively\.

We construct a one\-layer decoder\-only Transformer that consists of \(i\) multi\-head self\-attention with two heads \(denotedprev\\mathrm\{prev\}andself\\mathrm\{self\}\), each withdk=Kd\_\{k\}=K, followed by a residual connection, and \(ii\) a position\-wise feed\-forward network \(FFN\), followed by a residual connection\. We do not use positional encodings, LayerNorm, or dropout\. The construction is summarized as follows:

- •Embedding\.For a tokenaa, set its embedding to\(𝒆a;𝟎;𝟎\)\(\\boldsymbol\{e\}\_\{a\};\\boldsymbol\{0\};\\boldsymbol\{0\}\), where𝒆a∈ℝ1×K\\boldsymbol\{e\}\_\{a\}\\in\\mathbb\{R\}^\{1\\times K\}is the one\-hot vector corresponding toaa\.
- •Self\-attention\.After applying self\-attention to the two input tokens, the representation at position22has the form\(∗;\(𝒐2\(prev\),𝒐2\(self\)\);𝟎\)\(\*;\(\\boldsymbol\{o\}\_\{2\}^\{\(\\mathrm\{prev\}\)\},\\boldsymbol\{o\}\_\{2\}^\{\(\\mathrm\{self\}\)\}\);\\boldsymbol\{0\}\)\.
- •FFN\.Using the affine map𝑿​𝑾1\+𝟏​𝒃1⊤\\boldsymbol\{X\}\\boldsymbol\{W\}\_\{1\}\+\\boldsymbol\{1\}\\boldsymbol\{b\}\_\{1\}^\{\\top\}, we first recover\(∗;\(𝒆a,𝒆b\);𝟎\)\(\*;\(\\boldsymbol\{e\}\_\{a\},\\boldsymbol\{e\}\_\{b\}\);\\boldsymbol\{0\}\)from\(∗;\(𝒐\(prev\),𝒐\(self\)\);𝟎\)\(\*;\(\\boldsymbol\{o\}^\{\(\\mathrm\{prev\}\)\},\\boldsymbol\{o\}^\{\(\\mathrm\{self\}\)\}\);\\boldsymbol\{0\}\), and then apply a second affine map to produce\(∗;∗;𝒆\(a−1\)​K\+b\)\(\*;\*;\\boldsymbol\{e\}\_\{\(a\-1\)K\+b\}\)\.
- •Output head\.Finally, we map𝒆\(a−1\)​K\+b\\boldsymbol\{e\}\_\{\(a\-1\)K\+b\}in the pair block to logits using the classification head\.

The details are as follows:

#### Step 1: Embedding\.

Given input tokens\(a,b\)∈Σ2\(a,b\)\\in\\Sigma^\{2\}, define the two token representations

𝑿≔\[𝒙1𝒙2\]=\[𝒆a𝟎𝟎𝒆b𝟎𝟎\]∈ℝ2×dmodel,\\boldsymbol\{X\}\\coloneqq\\begin\{bmatrix\}\\boldsymbol\{x\}\_\{1\}\\\\ \\boldsymbol\{x\}\_\{2\}\\end\{bmatrix\}=\\begin\{bmatrix\}\\boldsymbol\{e\}\_\{a\}&\\boldsymbol\{0\}&\\boldsymbol\{0\}\\\\ \\boldsymbol\{e\}\_\{b\}&\\boldsymbol\{0\}&\\boldsymbol\{0\}\\end\{bmatrix\}\\in\\mathbb\{R\}^\{2\\times d\_\{\\text\{model\}\}\},where𝒙1=\(𝒆a;𝟎;𝟎\)\\boldsymbol\{x\}\_\{1\}=\(\\boldsymbol\{e\}\_\{a\};\\boldsymbol\{0\};\\boldsymbol\{0\}\)and𝒙2=\(𝒆b;𝟎;𝟎\)\\boldsymbol\{x\}\_\{2\}=\(\\boldsymbol\{e\}\_\{b\};\\boldsymbol\{0\};\\boldsymbol\{0\}\)\.

#### Step 2: Two\-Head Self\-Attention\.

Let the query matrices be

𝑾Q\(prev\)≔\[K​\(𝑱−𝑰K\)𝟎2​K×K𝟎K2×K\],𝑾Q\(self\)≔\[K​𝑰K𝟎2​K×K𝟎K2×K\],\\boldsymbol\{W\}\_\{Q\}^\{\(\\mathrm\{prev\}\)\}\\coloneqq\\begin\{bmatrix\}\\sqrt\{K\}\(\\boldsymbol\{J\}\-\\boldsymbol\{I\}\_\{K\}\)\\\\ \\boldsymbol\{0\}\_\{2K\\times K\}\\\\ \\boldsymbol\{0\}\_\{K^\{2\}\\times K\}\\end\{bmatrix\},\\qquad\\boldsymbol\{W\}\_\{Q\}^\{\(\\mathrm\{self\}\)\}\\coloneqq\\begin\{bmatrix\}\\sqrt\{K\}\\boldsymbol\{I\}\_\{K\}\\\\ \\boldsymbol\{0\}\_\{2K\\times K\}\\\\ \\boldsymbol\{0\}\_\{K^\{2\}\\times K\}\\end\{bmatrix\},and for each headh∈\{prev,self\}h\\in\\left\\\{\\mathrm\{prev\},\\mathrm\{self\}\\right\\\}define

𝑾K\(h\)=𝑾V\(h\)≔\[𝑰K𝟎2​K×K𝟎K2×K\]∈ℝdmodel×K\.\\boldsymbol\{W\}\_\{K\}^\{\(h\)\}=\\boldsymbol\{W\}\_\{V\}^\{\(h\)\}\\coloneqq\\begin\{bmatrix\}\\boldsymbol\{I\}\_\{K\}\\\\ \\boldsymbol\{0\}\_\{2K\\times K\}\\\\ \\boldsymbol\{0\}\_\{K^\{2\}\\times K\}\\end\{bmatrix\}\\in\\mathbb\{R\}^\{d\_\{\\text\{model\}\}\\times K\}\.For headhh, the query at position22is

𝒒2\(h\)≔𝒙2​𝑾Q\(h\)=\{K​\(𝟏−𝒆b\),h=prev,K​𝒆b,h=self,\\boldsymbol\{q\}^\{\(h\)\}\_\{2\}\\coloneqq\\boldsymbol\{x\}\_\{2\}\\boldsymbol\{W\}\_\{Q\}^\{\(h\)\}=\\begin\{cases\}\\sqrt\{K\}\(\\boldsymbol\{1\}\-\\boldsymbol\{e\}\_\{b\}\),&h=\\mathrm\{prev\},\\\\ \\sqrt\{K\}\\boldsymbol\{e\}\_\{b\},&h=\\mathrm\{self\},\\end\{cases\}and fort∈\{1,2\}t\\in\\left\\\{1,2\\right\\\}the keys and values satisfy

𝒌t\(h\)≔𝒙t​𝑾K\(h\)=𝒗t\(h\)≔𝒙t​𝑾V\(h\)=\{𝒆a,t=1,𝒆b,t=2\.\\boldsymbol\{k\}^\{\(h\)\}\_\{t\}\\coloneqq\\boldsymbol\{x\}\_\{t\}\\boldsymbol\{W\}\_\{K\}^\{\(h\)\}=\\boldsymbol\{v\}^\{\(h\)\}\_\{t\}\\coloneqq\\boldsymbol\{x\}\_\{t\}\\boldsymbol\{W\}\_\{V\}^\{\(h\)\}=\\begin\{cases\}\\boldsymbol\{e\}\_\{a\},&t=1,\\\\ \\boldsymbol\{e\}\_\{b\},&t=2\.\\end\{cases\}Define the attention weights

α2,t\(h\)≔exp⁡\(⟨𝒒2\(h\),𝒌t\(h\)⟩/K\)∑u∈\{1,2\}exp⁡\(⟨𝒒2\(h\),𝒌u\(h\)⟩/K\)\\displaystyle\\alpha^\{\(h\)\}\_\{2,t\}\\coloneqq\\frac\{\\exp\\left\(\\langle\\boldsymbol\{q\}^\{\(h\)\}\_\{2\},\\boldsymbol\{k\}^\{\(h\)\}\_\{t\}\\rangle/\\sqrt\{K\}\\right\)\}\{\\sum\_\{u\\in\\left\\\{1,2\\right\\\}\}\\exp\\left\(\\langle\\boldsymbol\{q\}^\{\(h\)\}\_\{2\},\\boldsymbol\{k\}^\{\(h\)\}\_\{u\}\\rangle/\\sqrt\{K\}\\right\)\}=exp⁡\(⟨𝒒2\(h\),𝒌t\(h\)⟩/K\)exp⁡\(⟨𝒒2\(h\),𝒆a⟩/K\)\+exp⁡\(⟨𝒒2\(h\),𝒆b⟩/K\)\\displaystyle=\\frac\{\\exp\\left\(\\langle\\boldsymbol\{q\}^\{\(h\)\}\_\{2\},\\boldsymbol\{k\}^\{\(h\)\}\_\{t\}\\rangle/\\sqrt\{K\}\\right\)\}\{\\exp\\left\(\\langle\\boldsymbol\{q\}^\{\(h\)\}\_\{2\},\\boldsymbol\{e\}\_\{a\}\\rangle/\\sqrt\{K\}\\right\)\+\\exp\\left\(\\langle\\boldsymbol\{q\}^\{\(h\)\}\_\{2\},\\boldsymbol\{e\}\_\{b\}\\rangle/\\sqrt\{K\}\\right\)\}=\{exp⁡\(⟨𝟏−𝒆b,𝒌t\(h\)⟩\)exp⁡\(𝕀​\[a≠b\]\)\+1,h=prev,exp⁡\(⟨𝒆b,𝒌t\(h\)⟩\)exp⁡\(𝕀​\[a=b\]\)\+e,h=self\.\\displaystyle=\\begin\{cases\}\\dfrac\{\\exp\\left\(\\langle\\boldsymbol\{1\}\-\\boldsymbol\{e\}\_\{b\},\\boldsymbol\{k\}^\{\(h\)\}\_\{t\}\\rangle\\right\)\}\{\\exp\\left\(\\mathbb\{I\}\[a\\neq b\]\\right\)\+1\},&h=\\mathrm\{prev\},\\\\\[6\.0pt\] \\dfrac\{\\exp\\left\(\\langle\\boldsymbol\{e\}\_\{b\},\\boldsymbol\{k\}^\{\(h\)\}\_\{t\}\\rangle\\right\)\}\{\\exp\\left\(\\mathbb\{I\}\[a=b\]\\right\)\+e\},&h=\\mathrm\{self\}\.\\end\{cases\}We next compute the head outputs at position22, denoted𝒐2\(h\)∈ℝ1×K\\boldsymbol\{o\}\_\{2\}^\{\(h\)\}\\in\\mathbb\{R\}^\{1\\times K\}\. Since

𝒐2\(h\)≔∑t∈\{1,2\}α2,t\(h\)​𝒗t\(h\)=α2,1\(h\)​𝒆a\+α2,2\(h\)​𝒆b,\\boldsymbol\{o\}\_\{2\}^\{\(h\)\}\\coloneqq\\sum\_\{t\\in\\left\\\{1,2\\right\\\}\}\\alpha^\{\(h\)\}\_\{2,t\}\\boldsymbol\{v\}^\{\(h\)\}\_\{t\}=\\alpha^\{\(h\)\}\_\{2,1\}\\boldsymbol\{e\}\_\{a\}\+\\alpha^\{\(h\)\}\_\{2,2\}\\boldsymbol\{e\}\_\{b\},we obtain

𝒐2\(prev\)=\{ee\+1​𝒆a\+1e\+1​𝒆b,a≠b,12​𝒆a\+12​𝒆b,a=b,𝒐2\(self\)=\{1e\+1​𝒆a\+ee\+1​𝒆b,a≠b,12​𝒆a\+12​𝒆b,a=b\.\\boldsymbol\{o\}\_\{2\}^\{\(\\mathrm\{prev\}\)\}=\\begin\{cases\}\\frac\{e\}\{e\+1\}\\boldsymbol\{e\}\_\{a\}\+\\frac\{1\}\{e\+1\}\\boldsymbol\{e\}\_\{b\},&a\\neq b,\\\\ \\frac\{1\}\{2\}\\boldsymbol\{e\}\_\{a\}\+\\frac\{1\}\{2\}\\boldsymbol\{e\}\_\{b\},&a=b,\\end\{cases\}\\qquad\\boldsymbol\{o\}\_\{2\}^\{\(\\mathrm\{self\}\)\}=\\begin\{cases\}\\frac\{1\}\{e\+1\}\\boldsymbol\{e\}\_\{a\}\+\\frac\{e\}\{e\+1\}\\boldsymbol\{e\}\_\{b\},&a\\neq b,\\\\ \\frac\{1\}\{2\}\\boldsymbol\{e\}\_\{a\}\+\\frac\{1\}\{2\}\\boldsymbol\{e\}\_\{b\},&a=b\.\\end\{cases\}
Let the concatenated head outputs be

Attn​\(𝑿\)≔\[𝒐1\(prev\)𝒐1\(self\)𝒐2\(prev\)𝒐2\(self\)\]∈ℝ2×2​K\.\\mathrm\{Attn\}\(\\boldsymbol\{X\}\)\\coloneqq\\begin\{bmatrix\}\\boldsymbol\{o\}\_\{1\}^\{\(\\mathrm\{prev\}\)\}&\\boldsymbol\{o\}\_\{1\}^\{\(\\mathrm\{self\}\)\}\\\\ \\boldsymbol\{o\}\_\{2\}^\{\(\\mathrm\{prev\}\)\}&\\boldsymbol\{o\}\_\{2\}^\{\(\\mathrm\{self\}\)\}\\end\{bmatrix\}\\in\\mathbb\{R\}^\{2\\times 2K\}\.Choose the attention output projection𝑾O≔\[𝟎2​K×K𝑰2​K𝟎2​K×K2\]∈ℝ2​K×dmodel\\boldsymbol\{W\}\_\{O\}\\coloneqq\\begin\{bmatrix\}\\boldsymbol\{0\}\_\{2K\\times K\}&\\boldsymbol\{I\}\_\{2K\}&\\boldsymbol\{0\}\_\{2K\\times K^\{2\}\}\\end\{bmatrix\}\\in\\mathbb\{R\}^\{2K\\times d\_\{\\text\{model\}\}\}so thatAttn​\(𝑿\)​𝑾O\\mathrm\{Attn\}\(\\boldsymbol\{X\}\)\\boldsymbol\{W\}\_\{O\}writes the twoKK\-dimensional head outputs into the middle feature block \(and zeros elsewhere\)\. Let𝒁≔𝑿\+Attn​\(𝑿\)​𝑾O\\boldsymbol\{Z\}\\coloneqq\\boldsymbol\{X\}\+\\mathrm\{Attn\}\(\\boldsymbol\{X\}\)\\boldsymbol\{W\}\_\{O\}be the post\-attention representation matrix\. Then

𝒁​\(2,:\)=\(𝒆b;\(𝒐2\(prev\);𝒐2\(self\)\);𝟎\)\.\\boldsymbol\{Z\}\(2,:\)=\\left\(\\boldsymbol\{e\}\_\{b\};\\left\(\\boldsymbol\{o\}\_\{2\}^\{\(\\mathrm\{prev\}\)\};\\boldsymbol\{o\}\_\{2\}^\{\(\\mathrm\{self\}\)\}\\right\);\\boldsymbol\{0\}\\right\)\.

#### Step 3: The FFN Builds a Pair Indicator\.

A key observation is that𝒆a=ee−1​𝒐2\(prev\)−1e−1​𝒐2\(self\)\\boldsymbol\{e\}\_\{a\}=\\frac\{e\}\{e\-1\}\\boldsymbol\{o\}\_\{2\}^\{\(\\mathrm\{prev\}\)\}\-\\frac\{1\}\{e\-1\}\\boldsymbol\{o\}\_\{2\}^\{\(\\mathrm\{self\}\)\}and𝒆b=ee−1​𝒐2\(self\)−1e−1​𝒐2\(prev\)\\boldsymbol\{e\}\_\{b\}=\\frac\{e\}\{e\-1\}\\boldsymbol\{o\}\_\{2\}^\{\(\\mathrm\{self\}\)\}\-\\frac\{1\}\{e\-1\}\\boldsymbol\{o\}\_\{2\}^\{\(\\mathrm\{prev\}\)\}\. These identities follow by inverting the corresponding linear system whena≠ba\\neq b, and one can verify that they also hold fora=ba=b\.

Let

𝑾A≔\[𝟎K×K𝟎K×K𝟎K×K𝟎K×K2𝟎K×Kee−1​𝑰K×K−1e−1​𝑰K×K𝟎K×K2𝟎K×K−1e−1​𝑰K×Kee−1​𝑰K×K𝟎K×K2𝟎K2×K𝟎K2×K𝟎K2×K𝟎K2×K2\]∈ℝdmodel×dmodel,\\boldsymbol\{W\}\_\{A\}\\coloneqq\\begin\{bmatrix\}\\boldsymbol\{0\}\_\{K\\times K\}&\\boldsymbol\{0\}\_\{K\\times K\}&\\boldsymbol\{0\}\_\{K\\times K\}&\\boldsymbol\{0\}\_\{K\\times K^\{2\}\}\\\\ \\boldsymbol\{0\}\_\{K\\times K\}&\\frac\{e\}\{e\-1\}\\boldsymbol\{I\}\_\{K\\times K\}&\-\\frac\{1\}\{e\-1\}\\boldsymbol\{I\}\_\{K\\times K\}&\\boldsymbol\{0\}\_\{K\\times K^\{2\}\}\\\\ \\boldsymbol\{0\}\_\{K\\times K\}&\-\\frac\{1\}\{e\-1\}\\boldsymbol\{I\}\_\{K\\times K\}&\\frac\{e\}\{e\-1\}\\boldsymbol\{I\}\_\{K\\times K\}&\\boldsymbol\{0\}\_\{K\\times K^\{2\}\}\\\\ \\boldsymbol\{0\}\_\{K^\{2\}\\times K\}&\\boldsymbol\{0\}\_\{K^\{2\}\\times K\}&\\boldsymbol\{0\}\_\{K^\{2\}\\times K\}&\\boldsymbol\{0\}\_\{K^\{2\}\\times K^\{2\}\}\\end\{bmatrix\}\\in\\mathbb\{R\}^\{d\_\{\\text\{model\}\}\\times d\_\{\\text\{model\}\}\},so that\(𝒁​𝑾A\)​\(2,:\)=\(𝟎;\(𝒆a;𝒆b\);𝟎\)\(\\boldsymbol\{Z\}\\boldsymbol\{W\}\_\{A\}\)\(2,:\)=\\left\(\\boldsymbol\{0\};\\left\(\\boldsymbol\{e\}\_\{a\};\\boldsymbol\{e\}\_\{b\}\\right\);\\boldsymbol\{0\}\\right\)\.

Next, let

𝑾B≔\[𝟎𝟎⋯𝟎𝟎⋯𝟎⋯𝟎𝒆1⊤𝒆1⊤⋯𝒆1⊤𝒆2⊤⋯𝒆K⊤⋯𝒆K⊤𝒆1⊤𝒆2⊤⋯𝒆K⊤𝒆1⊤⋯𝒆1⊤⋯𝒆K⊤𝟎𝟎⋯𝟎𝟎⋯𝟎⋯𝟎\]∈ℝdmodel×K2\.\\boldsymbol\{W\}\_\{B\}\\coloneqq\\begin\{bmatrix\}\\boldsymbol\{0\}&\\boldsymbol\{0\}&\\cdots&\\boldsymbol\{0\}&\\boldsymbol\{0\}&\\cdots&\\boldsymbol\{0\}&\\cdots&\\boldsymbol\{0\}\\\\ \\boldsymbol\{e\}\_\{1\}^\{\\top\}&\\boldsymbol\{e\}\_\{1\}^\{\\top\}&\\cdots&\\boldsymbol\{e\}\_\{1\}^\{\\top\}&\\boldsymbol\{e\}\_\{2\}^\{\\top\}&\\cdots&\\boldsymbol\{e\}\_\{K\}^\{\\top\}&\\cdots&\\boldsymbol\{e\}\_\{K\}^\{\\top\}\\\\ \\boldsymbol\{e\}\_\{1\}^\{\\top\}&\\boldsymbol\{e\}\_\{2\}^\{\\top\}&\\cdots&\\boldsymbol\{e\}\_\{K\}^\{\\top\}&\\boldsymbol\{e\}\_\{1\}^\{\\top\}&\\cdots&\\boldsymbol\{e\}\_\{1\}^\{\\top\}&\\cdots&\\boldsymbol\{e\}\_\{K\}^\{\\top\}\\\\ \\boldsymbol\{0\}&\\boldsymbol\{0\}&\\cdots&\\boldsymbol\{0\}&\\boldsymbol\{0\}&\\cdots&\\boldsymbol\{0\}&\\cdots&\\boldsymbol\{0\}\\end\{bmatrix\}\\in\\mathbb\{R\}^\{d\_\{\\text\{model\}\}\\times K^\{2\}\}\.Equivalently, the\(\(i−1\)​K\+j\)\(\(i\-1\)K\+j\)\-th column of𝑾B\\boldsymbol\{W\}\_\{B\}is\(𝟎;𝒆i;𝒆j;𝟎\)⊤∈ℝdmodel\(\\boldsymbol\{0\};\\boldsymbol\{e\}\_\{i\};\\boldsymbol\{e\}\_\{j\};\\boldsymbol\{0\}\)^\{\\top\}\\in\\mathbb\{R\}^\{d\_\{\\text\{model\}\}\}, and hence for any row vector𝒙∈ℝ1×dmodel\\boldsymbol\{x\}\\in\\mathbb\{R\}^\{1\\times d\_\{\\text\{model\}\}\},\(𝒙​𝑾B\)​\(\(i−1\)​K\+j\)=𝒙​\(K\+i\)\+𝒙​\(2​K\+j\)\(\\boldsymbol\{x\}\\boldsymbol\{W\}\_\{B\}\)\(\(i\-1\)K\+j\)=\\boldsymbol\{x\}\(K\+i\)\+\\boldsymbol\{x\}\(2K\+j\)\.

Let𝑾1≔𝑾A​𝑾B\\boldsymbol\{W\}\_\{1\}\\coloneqq\\boldsymbol\{W\}\_\{A\}\\boldsymbol\{W\}\_\{B\}and𝒃1≔−𝟏\\boldsymbol\{b\}\_\{1\}\\coloneqq\-\\boldsymbol\{1\}\. Then\(ReLU​\(𝒁​𝑾1\+𝟏​𝒃1⊤\)\)​\(2,:\)=𝒆\(a−1\)​K\+b∈ℝ1×K2\(\\mathrm\{ReLU\}\(\\boldsymbol\{Z\}\\boldsymbol\{W\}\_\{1\}\+\\boldsymbol\{1\}\\boldsymbol\{b\}\_\{1\}^\{\\top\}\)\)\(2,:\)=\\boldsymbol\{e\}\_\{\(a\-1\)K\+b\}\\in\\mathbb\{R\}^\{1\\times K^\{2\}\}\.

Finally, choose the second\-layer parameters as𝑾2≔\[𝟎K2×K𝟎K2×2​K𝑰K2\]∈ℝK2×dmodel\\boldsymbol\{W\}\_\{2\}\\coloneqq\\begin\{bmatrix\}\\boldsymbol\{0\}\_\{K^\{2\}\\times K\}&\\boldsymbol\{0\}\_\{K^\{2\}\\times 2K\}&\\boldsymbol\{I\}\_\{K^\{2\}\}\\end\{bmatrix\}\\in\\mathbb\{R\}^\{K^\{2\}\\times d\_\{\\text\{model\}\}\}and𝒃2≔𝟎\\boldsymbol\{b\}\_\{2\}\\coloneqq\\boldsymbol\{0\}\. Let

𝑿\(1\)≔𝒁\+\(ReLU​\(𝒁​𝑾1\+𝟏​𝒃1⊤\)​𝑾2\+𝟏​𝒃2⊤\)\\boldsymbol\{X\}^\{\(1\)\}\\coloneqq\\boldsymbol\{Z\}\+\\left\(\\mathrm\{ReLU\}\(\\boldsymbol\{Z\}\\boldsymbol\{W\}\_\{1\}\+\\boldsymbol\{1\}\\boldsymbol\{b\}\_\{1\}^\{\\top\}\)\\boldsymbol\{W\}\_\{2\}\+\\boldsymbol\{1\}\\boldsymbol\{b\}\_\{2\}^\{\\top\}\\right\)denote the FFN output with the residual connection\. Then

𝑿\(1\)​\(2,:\)=\(𝒆b;\(𝒐2\(prev\);𝒐2\(self\)\);𝒆\(a−1\)​K\+b\)\.\\boldsymbol\{X\}^\{\(1\)\}\(2,:\)=\\left\(\\boldsymbol\{e\}\_\{b\};\\left\(\\boldsymbol\{o\}\_\{2\}^\{\(\\mathrm\{prev\}\)\};\\boldsymbol\{o\}\_\{2\}^\{\(\\mathrm\{self\}\)\}\\right\);\\boldsymbol\{e\}\_\{\(a\-1\)K\+b\}\\right\)\.

#### Step 4: Output\.

Define𝑾∈ℝdmodel×K\\boldsymbol\{W\}\\in\\mathbb\{R\}^\{d\_\{\\text\{model\}\}\\times K\}such that𝑾​\(i,j\)=0\\boldsymbol\{W\}\(i,j\)=0fori∈\{1,2,⋯,3​K\}i\\in\\left\\\{1,2,\\cdots,3K\\right\\\}andj∈\{1,2,⋯,K\}j\\in\\left\\\{1,2,\\cdots,K\\right\\\}, and𝑾​\(3​K\+\(i−1\)​K\+j,k\)=𝕀​\[f​\(i,j\)=k\]\\boldsymbol\{W\}\(3K\+\(i\-1\)K\+j,k\)=\\mathbb\{I\}\[f\(i,j\)=k\]fori,j,k∈\{1,2,⋯,K\}i,j,k\\in\\left\\\{1,2,\\cdots,K\\right\\\}\. Let𝒀≔𝑿\(1\)​𝑾\\boldsymbol\{Y\}\\coloneqq\\boldsymbol\{X\}^\{\(1\)\}\\boldsymbol\{W\}\. Then for anyk∈\{1,2,⋯,K\}k\\in\\left\\\{1,2,\\cdots,K\\right\\\},

𝒀​\(2,k\)=∑\(i,j\)∈\{1,⋯,K\}2:f​\(i,j\)=k𝑿\(1\)​\(2,3​K\+\(i−1\)​K\+j\)=𝒆f​\(a,b\)​\(k\)\.\\boldsymbol\{Y\}\(2,k\)=\\sum\_\{\\begin\{subarray\}\{c\}\(i,j\)\\in\\left\\\{1,\\cdots,K\\right\\\}^\{2\}:\\\\ f\(i,j\)=k\\end\{subarray\}\}\\boldsymbol\{X\}^\{\(1\)\}\\left\(2,3K\+\(i\-1\)K\+j\\right\)=\\boldsymbol\{e\}\_\{f\(a,b\)\}\(k\)\.Therefore, the greedy decoding outputarg⁡max⁡𝒀​\(2,:\)\\arg\\max\\boldsymbol\{Y\}\(2,:\)is unique and equalsf​\(a,b\)f\(a,b\)\. ∎

## Appendix CDiscussion on Modifying the Context Manager to Simulate Next\-Two\-Tokens Decoding

In this appendix, we show how to simulate a\(2,2\)\(2,2\)\-restricted system while preserving the interface in which each Transformer call decodes a single token\. LetΣ\\Sigmabe a finite alphabet, and let<1\>,<2\>∉Σ\\texttt\{<1\>\},\\texttt\{<2\>\}\\notin\\Sigmabe two control tokens\. Define the extended alphabetΣ¯≔Σ∪\{<1\>,<2\>\}\\bar\{\\Sigma\}\\coloneqq\\Sigma\\cup\\left\\\{\\texttt\{<1\>\},\\texttt\{<2\>\}\\right\\\}\. Assume that for every functionf:Σ2→Σ2f:\\Sigma^\{2\}\\to\\Sigma^\{2\}, writingf​\(a,b\)=\(f1​\(a,b\),f2​\(a,b\)\)f\(a,b\)=\(f\_\{1\}\(a,b\),f\_\{2\}\(a,b\)\), there exists a context\-window\-33Transformer overΣ¯\\bar\{\\Sigma\}such that for all\(a,b\)∈Σ2\(a,b\)\\in\\Sigma^\{2\}, greedy decoding on input\(<1\>,a,b\)\(\\texttt\{<1\>\},a,b\)outputsf1​\(a,b\)f\_\{1\}\(a,b\), and greedy decoding on input\(<2\>,a,b\)\(\\texttt\{<2\>\},a,b\)outputsf2​\(a,b\)f\_\{2\}\(a,b\)\. Under this assumption, we can simulate any\(2,2\)\(2,2\)\-restricted system\.

Concretely, consider a\(2,2\)\(2,2\)\-restricted system specified by a functionM:Σ2→Σ2M:\\Sigma^\{2\}\\to\\Sigma^\{2\}\.666Schuurmans et al\.\(Schuurmans et al\.,[2024](https://arxiv.org/html/2605.19514#bib.bib46)\)require the output length ofMMto be at most22\. IfMMoutputs the empty string, we treat it as\(ϵ,ϵ\)\(\\epsilon,\\epsilon\)\. IfMMoutputs a single tokenaa, we treat it as\(a,ϵ\)\(a,\\epsilon\), whereϵ\\epsilonis a special empty symbol that is ignored when appending\.Applying the assumption withf≡Mf\\equiv M, we obtain a TransformerTTthat produces the two components ofM​\(a,b\)M\(a,b\)via the control tokens<1\>and<2\>\. Now consider stepttof the simulated\(2,2\)\(2,2\)\-restricted system, where the current window content is\(a,b\)\(a,b\)\. The modified context manager first feeds\(<1\>,a,b\)\(\\texttt\{<1\>\},a,b\)toTTand appends the decoded token to the end of the current sequence\. It then feeds\(<2\>,a,b\)\(\\texttt\{<2\>\},a,b\)toTTand appends the decoded token as well\. Finally, it deletes the first token of the current sequence, thereby shifting the window forward by one position\. This procedure exactly reproduces one step of the\(2,2\)\(2,2\)\-restricted system using two single\-token decoding calls\. Therefore, it suffices to establish that the assumption above holds\. We note that this follows by a direct extension of Lemma[5\.3](https://arxiv.org/html/2605.19514#S5.Thmtheorem3)to the context\-window\-33setting, and we omit the details\.