On the Expressive Power of Transformers

# On the Expressive Power of Transformers
Source: [https://arxiv.org/html/2608.12671](https://arxiv.org/html/2608.12671)
Phokion G\. KolaitisAffiliation:University of California Santa CruzAffiliation:Santa Cruz, CAEmail:[kolaitis@ucsc\.edu](mailto:)

August 2026

###### Abstract

Multi\-layer transformers form the critical component of essentially all large language models \(LLMs\) in use today\. Because of their ubiquity and computational capability, there is a rapidly growing body of work that aims to precisely calibrate the expressive power of transformers as language recognizers by comparing them against standard models of computation studied for decades by the theoretical computer science community\. In this endeavor, circuit complexity has by and large emerged as the “correct” branch of computational complexity to analyze the expressive power of transformers; the reason is that parameterizing transformers by the various resources they use, such as attention and precision, leads to direct comparisons with different classes of circuits parameterized by resources such as type of gates, size, and depth\. Here, we present an overview of selected results that delineate the expressive power of transformers using concepts and methods from circuit complexity\.

Keywords:transformers; models of computation; circuit complexity\.

###### Contents

1. [1Introduction](https://arxiv.org/html/2608.12671#S1)
2. [2The Architecture](https://arxiv.org/html/2608.12671#S2)1. [2\.1Transformers as Language Recognizers](https://arxiv.org/html/2608.12671#S2.SS1) 2. [2\.2Characteristics and Parameters of a Transformer](https://arxiv.org/html/2608.12671#S2.SS2) 3. [2\.3Encoder Computation](https://arxiv.org/html/2608.12671#S2.SS3) 4. [2\.4Decoder Computation](https://arxiv.org/html/2608.12671#S2.SS4)
3. [3Classical and Circuit Complexity](https://arxiv.org/html/2608.12671#S3)1. [3\.1The “Right” Hierarchy](https://arxiv.org/html/2608.12671#S3.SS1) 2. [3\.2Definitions](https://arxiv.org/html/2608.12671#S3.SS2) 3. [3\.3Descriptive Complexity](https://arxiv.org/html/2608.12671#S3.SS3)
4. [4Expressivity Results](https://arxiv.org/html/2608.12671#S4)1. [4\.1Without Chain\-of\-Thought](https://arxiv.org/html/2608.12671#S4.SS1) 2. [4\.2With Chain\-of\-Thought](https://arxiv.org/html/2608.12671#S4.SS2)
5. [5Concluding Remarks](https://arxiv.org/html/2608.12671#S5)
6. [References](https://arxiv.org/html/2608.12671#bib)

## 1Introduction

Transformers have become the default computational substrate of modern large language models \(LLMs\), and yet their formal capabilities remain only partially understood at best\. For researchers in logic and computational complexity, this presents a challenge and an opportunity: formalize an architecture that has extraordinary empirical success in order to study it as a family of resource\-bounded computation models and to compare its power with classical hierarchies underlying standard models of computation\. Indeed, a large body of recent literature has pursued this exact endeavor\. By treating sequence length, depth, attention heads, numerical precision, positional encodings, and so on as explicit resources, one obtains variants of transformers whose expressive power can be related to that of automata and circuit classes\.

This brief survey focuses on transformers as language recognizers and their connections to circuit complexity\. The underlying principle is that attention layers behave like structured, parallel stages of computation, which makes them comparable to bounded\-depth circuits with restrictions on gates, fan\-in, size, and uniformity\. This perspective clarifies both what transformers can simulate and where limitations arise\. It also exposes how small choices in setting up the architecture — soft versus hard attention, fixed versus unbounded precision, and so on — can significantly affect the expressive power\. Our aim is to set up the formal architecture carefully, highlight a few of the results established so far, and provide a flavor of some of the proof techniques\.

For a more detailed overview, we refer the reader to several other extensive surveys of the field, including ones on neural networks and formal languages\[[1](https://arxiv.org/html/2608.12671#bib.bib6)\], RNNs and transformers\[[21](https://arxiv.org/html/2608.12671#bib.bib7)\], transformer expressivity\[[24](https://arxiv.org/html/2608.12671#bib.bib8)\], and the transformer cookbook\[[29](https://arxiv.org/html/2608.12671#bib.bib9)\]\.

## 2The Architecture

### 2\.1Transformers as Language Recognizers

Before describing each of its components formally, we describe the transformer architecture informally, so that we establish how transformers can serve as language recognizers\. A transformer can be viewed as a particular neural network consisting of an input layer, one or more hidden layers, and an output layer\. The input to a transformer is a nonempty input string over some alphabetΣ\\Sigma, whose lengthnnis called the*context length*\. Each character of this input alphabet is called a*token*\(in practice, tokens are often substrings rather than individual characters; input text is broken up into tokens using a highly nontrivial process called*tokenization*, which is beyond the scope of this survey\)\. The input layer of the transformer embeds each token in a vector space by mapping it to add\-dimensional real vector, whereddis a parameter of the transformer\. Each hidden layer thereafter takes a sequence of lengthnnofdd\-dimensional real vectors as its input, and applies a*length\-preserving*function to this sequence, resulting in a sequence of lengthnnofdd\-dimensional real vectors as the output of that layer\. The output layer is different depending on the type of transformer considered\.

- •In a transformer*encoder*\(the model adopted in viewing transformers as*classifiers*\), the output layer converts the final sequence ofdd\-dimensional vectors into a single probabilitypout∈\[0,1\]p\_\{\\text\{out\}\}\\in\[0,1\], and*accepts*the input string if and only ifpout≥1/2p\_\{\\text\{out\}\}\\geq 1/2\.
- •In a transformer*decoder*\(the model adopted in viewing transformers as*language models*\), the output layer outputs a new token111The new token can be viewed as being drawn from an implicit probability distribution overΣ\\Sigma\. This distribution is effectively learned during training and is encoded in the architecture of the model, thus the model’s output procedure is completely deterministic\. In practice, however, the final token is often selected using decoding procedures such as Top\-K sampling or Top\-p sampling\[[11](https://arxiv.org/html/2608.12671#bib.bib28)\], which restrict the candidate set before sampling; thus the forward computation is deterministic, while the realized output may be stochastic unless greedy decoding or a fixed random seed is used\., appends it to the original input, and then continues to do this*autoregressively*, i\.e\., by sequentially generating new tokens by consuming all the ones generated in previous timesteps, for a pre\-specified number of timesteps\. This is the version of a transformer used for text generation\. Furthermore, a decoder can be easily turned into a language recognizer as well: in the final timestep, it behaves similarly to an encoder, outputs a probabilitypoutp\_\{\\text\{out\}\}\(instead of a new token\), and*accepts*the original input string if and only ifpout≥1/2p\_\{\\text\{out\}\}\\geq 1/2\.

### 2\.2Characteristics and Parameters of a Transformer

We are now ready to describe the transformer architecture formally\. To begin with, every transformer has several characteristics\.

#### Hard/Soft Attention\.

The richness of the language of transformers comes from a mechanism inside the hidden layers called*attention*\[[26](https://arxiv.org/html/2608.12671#bib.bib23)\], which is essentially a scaled dot\-product that combines information across different vectors in the sequence\. The breakthrough idea behind defining attention was the realization that a model did not need to process language only in a fixed order or compress everything into a single hidden state\. Instead, each token could directly “look at” the other tokens in a long enough sequence and decide which ones were most relevant\. This made models far better at capturing long\-range relationships, easier to train in parallel, and scalable to much larger systems — essentially laying the foundation for modern transformers and large language models\. The assumptions on the attention mechanism form a core distinguishing feature of the transformer’s behavior\. Attention can be either*hard*or*soft*, of which the latter tends to have more expressive power than the former\[[9](https://arxiv.org/html/2608.12671#bib.bib24),[10](https://arxiv.org/html/2608.12671#bib.bib12),[22](https://arxiv.org/html/2608.12671#bib.bib16),[17](https://arxiv.org/html/2608.12671#bib.bib14),[16](https://arxiv.org/html/2608.12671#bib.bib25)\]\. Standard choices for the attention include𝖴𝖧𝖠𝖳\\mathsf\{UHAT\}\(“unique hard attention”\),𝖠𝖧𝖠𝖳\\mathsf\{AHAT\}\(“average hard attention”\), and𝖲𝖬𝖠𝖳\\mathsf\{SMAT\}\(“softmax attention”\), of which, only the last is widely used in practice\.

#### Masking/No Masking\.

In an encoder, we typically assume a model without*masking*, which means that every position can*a priori*attend to all other positions\. By contrast, in a decoder, we typically assume an autoregressive model that uses*future masking*, where a position can only attend to positions before it\.

The evolutions of LLMs has seen a shift from encoder models \(e\.g\., BERT\) to decoder models \(e\.g\., GPT, Claude, Gemini, LLaMA\), because of the autoregressive nature of the latter that can be leveraged for text generation\. Furthermore, encoder models can be shown theoretically to be strictly more powerful than decoder models222It should be noted that these “less” powerful decoders do not have*chain\-of\-thought*, an added capability we describe next\.for language recognition; also, as shown in\[[5](https://arxiv.org/html/2608.12671#bib.bib5)\], lower bounds on encoder models imply lower bounds on constant\-depth symmetric circuits; this would be a technical breakthrough, as techniques for circuit lower bound, such as the random restriction method, do not work on symmetric functions\.

#### Chain\-of\-Thought\.

In autoregressive decoder models, the architecture can output intermediate tokens during its computation, which are then fed back to the architecture by appending them to the input\. This process is called*chain\-of\-thought*\(CoT\); it is known that transformers with this ability are strictly more powerful than transformers without\[[5](https://arxiv.org/html/2608.12671#bib.bib5),[20](https://arxiv.org/html/2608.12671#bib.bib2),[14](https://arxiv.org/html/2608.12671#bib.bib4)\]\. Most modern LLMs exploit CoT\-style intermediate reasoning\.

#### Parameters\.

In addition to the preceding characteristics, a transformer has the following parameters\.

- •Number of layers:the number of hidden layers in the transformer, denoted byLL\. We will always assumeLLto be a constant, and index the layers asℓ∈\[L\]\\ell\\in\[L\]\.
- •Number of attention heads:the number of attention heads, typically denoted byHH\. We will again assume thatHHis a constant, and index the heads ash∈\[H\]h\\in\[H\]\.
- •Embedding dimension:the length of the embedded vectors, denoted bydd\. There are often two additional dimensions, the*key width*dkeyd\_\{\\text\{key\}\}and the*hidden width*dhiddend\_\{\\text\{hidden\}\}\. Each of these parameters is allowed to depend on the context lengthnn, though they are often fixed constants in practice\.
- •Level of precision:the number of bits of precision allowed to carry out all computations within the architecture, denoted bypp\. This parameter is also, in general, a function of the input lengthnn; in fact, we often assumeppto beΘ⁡\(log⁡n\)\\Theta\(\\log n\)\(see the discussion at the start of Section[4](https://arxiv.org/html/2608.12671#S4)\)\.
- •Amount of chain\-of\-thought:for transformers with chain\-of\-thought, the number of intermediate tokens allowed to be generated, as a functionf⁡\(n\)f\(n\)of the input lengthnn\. In Section[4\.2](https://arxiv.org/html/2608.12671#S4.SS2), we shall see the difference in expressivity resulting from different asymptotic choices for the functionf⁡\(n\)f\(n\)\.

Sometimes, the numberLLof layers is called the*depth*of the transformer, while the productH​d​pHdpof the embedding dimension, number of attention heads, and number of precision bits used is called its*width*\.

It should be emphasized that the context lengthnn\(i\.e\., the lengthnnof an input\) is*not*a parameter of a transformer\. The reason is that a transformer can process arbitrarily long inputs, the same way a finite automaton can process arbitrarily long strings\. This useful abstraction allows us to view transformers as language recognizers\. In real\-world transformers, the context length, also called the*context window*, is bounded by some large, but fixed, value \(e\.g\., 256k\)\.

### 2\.3Encoder Computation

![Refer to caption](https://arxiv.org/html/2608.12671v1/architecture.png)Figure 1:A high\-level view of the encoder architecture\.IfXXis a set, we will writeX∗X^\{\*\}to denote the set of all finite sequences with elements fromXX, while we will writeX\+X^\{\+\}to denote the set of all non\-empty such sequences\. The set of all real numbers will be denoted byℝ\\mathbb\{R\}\. Furthermore, ifmmis a natural number, we will write\[m\]\[m\]to denote the set\{1,…,m\}\\\{1,\\ldots,m\\\}\.

#### Input Layer\.

In the input layer, a string of lengthnnis mapped to a sequence ofnnvectors overℝd\\mathbb\{R\}^\{d\}via a length\-preserving function𝖾𝗆𝖻𝖾𝖽:Σ∗→\(ℝd\)∗\\mathsf\{embed\}:\\Sigma^\{\\ast\}\\to\(\\mathbb\{R\}^\{d\}\)^\{\\ast\}\. To obtain the result of applying the function𝖾𝗆𝖻𝖾𝖽\\mathsf\{embed\}on a stringw∈Σ∗w\\in\\Sigma^\{\\ast\}, we take each input characterwiw\_\{i\}in turn, and take the sum of two functions: the*word embedding*function𝖶𝖤:Σ→ℝd\\mathsf\{WE\}:\\Sigma\\to\\mathbb\{R\}^\{d\}applied to the characterwiw\_\{i\}, and the*positional encoding*function𝖯𝖤:\[n\]→ℝd\\mathsf\{PE\}:\[n\]\\to\\mathbb\{R\}^\{d\}applied to the indexii\. The output of the input layer is the resulting sequence\(𝐱1\(0\),…,𝐱n\(0\)\)∈\(ℝd\)n\(\\mathbf\{x\}^\{\(0\)\}\_\{1\},\\ldots,\\mathbf\{x\}^\{\(0\)\}\_\{n\}\)\\in\(\\mathbb\{R\}^\{d\}\)^\{n\}\. In other words, we have:

𝐱i\(0\)=𝖶𝖤⁡\(wi\)\+𝖯𝖤⁡\(i\),for all​i∈\[n\]\.\\mathbf\{x\}^\{\(0\)\}\_\{i\}=\\mathsf\{WE\}\(w\_\{i\}\)\+\\mathsf\{PE\}\(i\),\\text\{ for all \}i\\in\[n\]\.

#### Hidden Layers\.

Each hidden layerℓ∈\[L\]\\ell\\in\[L\]of the transformer is a length\-preserving functionℒ\(ℓ\):\(ℝd\)∗→\(ℝd\)∗\\mathcal\{L\}^\{\(\\ell\)\}:\(\\mathbb\{R\}^\{d\}\)^\{\\ast\}\\to\(\\mathbb\{R\}^\{d\}\)^\{\\ast\}that takes a sequence\(𝐱1\(ℓ−1\),…,𝐱n\(ℓ−1\)\)∈\(ℝd\)n\(\\mathbf\{x\}^\{\(\\ell\-1\)\}\_\{1\},\\ldots,\\mathbf\{x\}^\{\(\\ell\-1\)\}\_\{n\}\)\\in\(\\mathbb\{R\}^\{d\}\)^\{n\}as input and outputs a sequence\(𝐱1\(ℓ\),…,𝐱n\(ℓ\)\)∈\(ℝd\)n\(\\mathbf\{x\}^\{\(\\ell\)\}\_\{1\},\\ldots,\\mathbf\{x\}^\{\(\\ell\)\}\_\{n\}\)\\in\(\\mathbb\{R\}^\{d\}\)^\{n\}\. To describe a hidden layer, we need the notions of a*self\-attention*sublayer and a*position\-wise feed\-forward*sublayer\.

A*self\-attention sublayer*with widthddand key\-widthdkeyd\_\{\\text\{key\}\}is a length\-preserving function𝗌𝖺:\(ℝd\)\+→\(ℝd\)\+\\mathsf\{sa\}:\(\\mathbb\{R\}^\{d\}\)^\{\+\}\\to\(\\mathbb\{R\}^\{d\}\)^\{\+\}, in essence the weighted sums of*value*vectors in allnnpositions, where the weights are a function of*query*vectors and*key*vectors\. In other words, we have three matrices𝐖\(Q\),𝐖\(K\),𝐖\(V\)∈ℝdkey×d\\mathbf\{W\}^\{\(Q\)\},\\mathbf\{W\}^\{\(K\)\},\\mathbf\{W\}^\{\(V\)\}\\in\\mathbb\{R\}^\{d\_\{\\text\{key\}\}\\times d\}, together with a length\-preserving*weighting function*𝒮:ℝ\+→ℝ\+\\mathcal\{S\}:\\mathbb\{R\}^\{\+\}\\to\\mathbb\{R\}^\{\+\}and an output matrix𝐖\(O\)∈ℝd×dkey\\mathbf\{W\}^\{\(O\)\}\\in\\mathbb\{R\}^\{d\\times d\_\{\\text\{key\}\}\}, computing the following in an encoder model:

𝗌𝖺⁡\(𝐱1,…,𝐱n\)\\displaystyle\\mathsf\{sa\}\(\\mathbf\{x\}\_\{1\},\\ldots,\\mathbf\{x\}\_\{n\}\)=\(𝐲1,…,𝐲n\),where:\\displaystyle=\(\\mathbf\{y\}\_\{1\},\\ldots,\\mathbf\{y\}\_\{n\}\),\\text\{ where:\}𝐲i\\displaystyle\\mathbf\{y\}\_\{i\}=𝐖\(O\)​\(∑j=1nαi,j​𝐯j\),\\displaystyle=\\mathbf\{W\}^\{\(O\)\}\\left\(\\sum\_\{j=1\}^\{n\}\\alpha\_\{i,j\}\\mathbf\{v\}\_\{j\}\\right\),𝐯j\\displaystyle\\mathbf\{v\}\_\{j\}=𝐖\(V\)​𝐱j,\\displaystyle=\\mathbf\{W\}^\{\(V\)\}\\mathbf\{x\}\_\{j\},αi,∗\\displaystyle\\alpha\_\{i,\\ast\}=𝒮⁡\(si,∗\),\\displaystyle=\\mathcal\{S\}\(s\_\{i,\\ast\}\),\(1\)si,j\\displaystyle s\_\{i,j\}=𝐪i⊤​𝐤jdkey,\\displaystyle=\\frac\{\\mathbf\{q\}\_\{i\}^\{\\top\}\\mathbf\{k\}\_\{j\}\}\{\\sqrt\{d\_\{\\text\{key\}\}\}\},𝐪i\\displaystyle\\mathbf\{q\}\_\{i\}=𝐖\(Q\)​𝐱i,\\displaystyle=\\mathbf\{W\}^\{\(Q\)\}\\mathbf\{x\}\_\{i\},𝐤j\\displaystyle\\mathbf\{k\}\_\{j\}=𝐖\(K\)​𝐱j\.\\displaystyle=\\mathbf\{W\}^\{\(K\)\}\\mathbf\{x\}\_\{j\}\.\(2\)
Here,si,∗:=\(si,1,…,si,n\)s\_\{i,\\ast\}:=\(s\_\{i,1\},\\ldots,s\_\{i,n\}\)is the vector of*attention scores*, whileαi,∗:=\(αi,1,…,αi,n\)\\alpha\_\{i,\\ast\}:=\(\\alpha\_\{i,1\},\\ldots,\\alpha\_\{i,n\}\)is the vector of*attention weights*\.

Note that the weightsαi,∗\\alpha\_\{i,\\ast\}are obtained by applying a weighting function𝒮\\mathcal\{S\}to the attention scoressi,∗s\_\{i,\\ast\}\. The*softmax*function is the most common choice for a weighting function, where:

\[𝗌𝗈𝖿𝗍𝗆𝖺𝗑⁡\(a1,…,an\)\]i=exp⁡\(ai\)∑j=1nexp⁡\(aj\)\.\\displaystyle\[\\mathsf\{softmax\}\(a\_\{1\},\\ldots,a\_\{n\}\)\]\_\{i\}=\\frac\{\\exp\(a\_\{i\}\)\}\{\\sum\_\{j=1\}^\{n\}\\exp\(a\_\{j\}\)\}\.In the literature, several alternatives to softmax have been considered, such as*hard*attention, where the attention only focuses on the position/s with the maximum score, and either takes one of them \(in the𝖴𝖧𝖠𝖳\\mathsf\{UHAT\}model\), or takes an average over those positions \(in the𝖠𝖧𝖠𝖳\\mathsf\{AHAT\}model\)\. Since most variants of hard attention can be simulated by softmax attention using positional encodings or other techniques\[[28](https://arxiv.org/html/2608.12671#bib.bib27)\], we focus on the𝖲𝖬𝖠𝖳\\mathsf\{SMAT\}model here\.

A*position\-wise feed\-forward sublayer*with widthddand hidden widthdhiddend\_\{\\text\{hidden\}\}is a function𝖿𝖿:ℝd→ℝd\\mathsf\{ff\}:\\mathbb\{R\}^\{d\}\\to\\mathbb\{R\}^\{d\}, in essence a piecewise affine transformation on every position\. Thus, we have matrices𝐖1∈ℝdhidden×d\\mathbf\{W\}\_\{1\}\\in\\mathbb\{R\}^\{d\_\{\\text\{hidden\}\}\\times d\},𝐖2∈ℝd×dhidden\\mathbf\{W\}\_\{2\}\\in\\mathbb\{R\}^\{d\\times d\_\{\\text\{hidden\}\}\}, and vectors𝐛1∈ℝdhidden\\mathbf\{b\}\_\{1\}\\in\\mathbb\{R\}^\{d\_\{\\text\{hidden\}\}\},𝐛2∈ℝd\\mathbf\{b\}\_\{2\}\\in\\mathbb\{R\}^\{d\}, so that:

𝖿𝖿⁡\(𝐱\)=𝐲,where​𝐲:=𝐖2​𝐳\+𝐛2​and​𝐳:=ReLU​\(𝐖1​𝐱\+𝐛1\)\.\\mathsf\{ff\}\(\\mathbf\{x\}\)=\\mathbf\{y\},\\text\{ where \}\\mathbf\{y\}:=\\mathbf\{W\}\_\{2\}\\mathbf\{z\}\+\\mathbf\{b\}\_\{2\}\\text\{ and \}\\mathbf\{z\}:=\\text\{ReLU\}\(\\mathbf\{W\}\_\{1\}\\mathbf\{x\}\+\\mathbf\{b\}\_\{1\}\)\.Here, the*rectified linear unit*functionReLU​\(x\)=max⁡\(0,x\)\\text\{ReLU\}\(x\)=\\max\(0,x\)is applied coordinatewise\.

Now, for every layerℓ∈\[L\]\\ell\\in\[L\]and every attention headh∈\[H\]h\\in\[H\], let𝗌𝖺\(h,ℓ\)\\mathsf\{sa\}^\{\(h,\\ell\)\}be a self\-attention sublayer with widthdd\. Similarly, for every layerℓ∈\[L\]\\ell\\in\[L\], let𝖿𝖿\(ℓ\)\\mathsf\{ff\}^\{\(\\ell\)\}be a feed\-forward sublayer with widthdd\. The*transformer layer*for layerℓ∈\[L\]\\ell\\in\[L\]is defined as:

ℒ\(ℓ\)​\(𝐱1\(ℓ−1\),…,𝐱n\(ℓ−1\)\)\\displaystyle\\mathcal\{L\}^\{\(\\ell\)\}\(\\mathbf\{x\}^\{\(\\ell\-1\)\}\_\{1\},\\ldots,\\mathbf\{x\}^\{\(\\ell\-1\)\}\_\{n\}\)=\(𝐱1\(ℓ\),…,𝐱n\(ℓ\)\),where:\\displaystyle=\(\\mathbf\{x\}^\{\(\\ell\)\}\_\{1\},\\ldots,\\mathbf\{x\}^\{\(\\ell\)\}\_\{n\}\),\\text\{ where: \}\(𝐲1\(ℓ\),…,𝐲n\(ℓ\)\)\\displaystyle\(\\mathbf\{y\}^\{\(\\ell\)\}\_\{1\},\\ldots,\\mathbf\{y\}^\{\(\\ell\)\}\_\{n\}\):=∑h=1H𝗌𝖺\(h,ℓ\)​\(𝐱1\(ℓ−1\),…,𝐱n\(ℓ−1\)\)\+\(𝐱1\(ℓ−1\),…,𝐱n\(ℓ−1\)\),\\displaystyle:=\\sum\_\{h=1\}^\{H\}\\mathsf\{sa\}^\{\(h,\\ell\)\}\(\\mathbf\{x\}^\{\(\\ell\-1\)\}\_\{1\},\\ldots,\\mathbf\{x\}^\{\(\\ell\-1\)\}\_\{n\}\)\+\(\\mathbf\{x\}^\{\(\\ell\-1\)\}\_\{1\},\\ldots,\\mathbf\{x\}^\{\(\\ell\-1\)\}\_\{n\}\),\(𝐱1\(ℓ\),…,𝐱n\(ℓ\)\)\\displaystyle\(\\mathbf\{x\}^\{\(\\ell\)\}\_\{1\},\\ldots,\\mathbf\{x\}^\{\(\\ell\)\}\_\{n\}\):=\(𝖿𝖿\(ℓ\)​\(𝐲1\(ℓ\)\),…,𝖿𝖿\(ℓ\)​\(𝐲n\(ℓ\)\)\)\+\(𝐲1\(ℓ\),…,𝐲n\(ℓ\)\)\.\\displaystyle:=\(\\mathsf\{ff\}^\{\(\\ell\)\}\(\\mathbf\{y\}^\{\(\\ell\)\}\_\{1\}\),\\ldots,\\mathsf\{ff\}^\{\(\\ell\)\}\(\\mathbf\{y\}^\{\(\\ell\)\}\_\{n\}\)\)\+\(\\mathbf\{y\}^\{\(\\ell\)\}\_\{1\},\\ldots,\\mathbf\{y\}^\{\(\\ell\)\}\_\{n\}\)\.While carrying out its computations on an input stringw∈Σ∗w\\in\\Sigma^\{\\ast\}, the hidden layers of the transformer apply the functionℒ\(ℓ\)\\mathcal\{L\}^\{\(\\ell\)\}sequentially over the layersℓ∈\[L\]\\ell\\in\[L\], where the input to layer11is the sequence𝖾𝗆𝖻𝖾𝖽⁡\(w\)\\mathsf\{embed\}\(w\)\. In effect, therefore, the hidden layers compute the composition:

ℒ\(L\)∘⋯∘ℒ\(1\)\(𝖾𝗆𝖻𝖾𝖽\(w\)\)\.\\displaystyle\\mathcal\{L\}^\{\(L\)\}\\circ\\cdots\\circ\\mathcal\{L\}^\{\(1\)\}\(\\mathsf\{embed\}\(w\)\)\.Note that we have omitted the details of*layer normalization*\(or*layernorm*for short\), which is a commonly used normalization technique that reduces training time\. Layer normalization can change the expressivity of the transformer architecture drastically, depending on how it is modeled; for details, we refer the reader to[29](https://arxiv.org/html/2608.12671#bib.bib9)\.

#### Output Layer\.

The last layerLLoutputs a sequence of length\-ddvectors\(𝐱1\(L\),…,𝐱n\(L\)\)\(\\mathbf\{x\}^\{\(L\)\}\_\{1\},\\ldots,\\mathbf\{x\}^\{\(L\)\}\_\{n\}\)\. Then, the transformer takes a fixed one of these vectors \(typically,𝐱n\(L\)\\mathbf\{x\}^\{\(L\)\}\_\{n\}\), linearly projects it into a scalar, applies a sigmoid function to it to obtain a real number in\(0,1\)\(0,1\), rounds this number to00or11, and outputs the result \(interpreted as rejection and acceptance respectively\)\. Thus, we have a vector𝐰∈ℝd\\mathbf\{w\}\\in\\mathbb\{R\}^\{d\}and a scalarb∈ℝb\\in\\mathbb\{R\}such thatp=σ⁡\(𝐰⊤⋅𝐱n\(L\)\+b\)p=\\sigma\(\\mathbf\{w\}^\{\\top\}\\cdot\\mathbf\{x\}^\{\(L\)\}\_\{n\}\+b\), whereσ\\sigmais the*sigmoid function*, i\.e\.,σ⁡\(x\)=1/\(1\+e−x\)\\sigma\(x\)=1/\(1\+e^\{\-x\}\)\. The output of the transformer is⌊p\+1/2⌋∈\{0,1\}\\lfloor p\+1/2\\rfloor\\in\\\{0,1\\\}\.

### 2\.4Decoder Computation

The decoder model is very similar to the encoder model, with the following two important distinctions\.

#### Masking\.

In encoders, there is no restriction on which positions any particular position can attend to\. In decoders, however, each position attends only to the current and previous positions\. This is enforced by settingsi,j=−∞s\_\{i,j\}=\-\\infty, for alli<ji<jin equations[1](https://arxiv.org/html/2608.12671#S2.E1)and[2](https://arxiv.org/html/2608.12671#S2.E2)\(everything else remains the same\)\. As a consequence of this, all terms withi<ji<jin the expressions vanish\. This is called*future masking*\. Several other related variants of masking have also been considered in the literature\.

#### Output Layer\.

In encoders, the output layer projects the vector𝐱n\(L\)\\mathbf\{x\}\_\{n\}^\{\(L\)\}into a scalar, and then converts this scalar into a probability\. In decoders, the output layer uses𝐱n\(L\)\\mathbf\{x\}\_\{n\}^\{\(L\)\}to produce a token from the alphabetΣ\\Sigma, which can be thought of as the transformer drawing from an implicit probability distribution over the tokens inΣ\\Sigma\. Thus, we have an output functionγ:ℝd→Σ\\gamma:\\mathbb\{R\}^\{d\}\\to\\Sigmaparameterized as a linear transformation\. The output of the transformer is simplyγ⁡\(𝐱n\(L\)\)\\gamma\(\\mathbf\{x\}\_\{n\}^\{\(L\)\}\)\.

In decoders with chain\-of\-thoughtf⁡\(n\)f\(n\), the autoregressive nature is leveraged in order to output a sequence of intermediate tokens, forf⁡\(n\)f\(n\)timesteps\. Formally, for a fixed decoder𝒯\\mathcal\{T\}, letF𝒯:Σ∗→ΣF\_\{\\mathcal\{T\}\}:\\Sigma^\{\\ast\}\\to\\Sigmabe the function mapping an input string to a token \(parameterized by𝒯\\mathcal\{T\}\)\. For everyw=w1​…​wn∈Σ∗w=w\_\{1\}\\ldots w\_\{n\}\\in\\Sigma^\{\\ast\}, define:

F𝒯0​\(w\)\\displaystyle F\_\{\\mathcal\{T\}\}^\{0\}\(w\):=w\\displaystyle:=wF𝒯i​\(w\)\\displaystyle F\_\{\\mathcal\{T\}\}^\{i\}\(w\):=F𝒯i−1​\(w\)⋅F𝒯​\(F𝒯i−1​\(w\)\)​for​i≥1,\\displaystyle:=F\_\{\\mathcal\{T\}\}^\{i\-1\}\(w\)\\cdot F\_\{\\mathcal\{T\}\}\(F\_\{\\mathcal\{T\}\}^\{i\-1\}\(w\)\)\\text\{ for \}i\\geq 1,where⋅\\cdotdenotes concatenation\. Forj≥1j\\geq 1, letwn\+j:=F𝒯​\(F𝒯j−1​\(w\)\)w\_\{n\+j\}:=F\_\{\\mathcal\{T\}\}\(F\_\{\\mathcal\{T\}\}^\{j\-1\}\(w\)\)be the output token in timestepjj\. Then, the output of the transformer is the sequence of tokens:

\(wn\+1,…,wn\+f⁡\(n\)\)\.\(w\_\{n\+1\},\\ldots,w\_\{n\+f\(n\)\}\)\.This transformer can, of course, be easily converted to a language recognizer: instead of generating the final tokenwn\+f⁡\(n\)w\_\{n\+f\(n\)\}, the output layer takes thedd\-dimensional vector𝐱n\+f⁡\(n\)−1\(L\)\\mathbf\{x\}\_\{n\+f\(n\)\-1\}^\{\(L\)\}and outputs a probability just as an encoder’s output layer does, rounding it up or down to represent acceptance or rejection respectively\.

Pictorially, the difference between an encoder and a decoder \(with CoTf⁡\(n\)f\(n\)\) can be visualized as follows:

![Refer to caption](https://arxiv.org/html/2608.12671v1/non-chain-of-thought.png)

![Refer to caption](https://arxiv.org/html/2608.12671v1/chain-of-thought.png)

Figure 2:An encoder \(left\) and a decoder \(right\)\.

## 3Classical and Circuit Complexity

### 3\.1The “Right” Hierarchy

By and large, circuit complexity has emerged as a particularly well\-aligned branch of computational complexity to calibrate the expressive power of transformers\. The lens of circuit complexity is more effective than, say, the lens of the Chomsky hierarchy, mainly because the defining inductive bias for transformers is parallel, fixed\-depth computation over continuous vectors, rather than discrete symbolic recursion over strings\. The Chomsky hierarchy classifies formal languages by the power of grammars or automata, which would be well\-suited for models with explicit sequential state transitions \(e\.g\., RNNs\)\. In contrast, transformers operate as layered compositions of attention and feedforward blocks that can be formalized as Boolean or threshold circuits with bounded depth and large fan\-in\. This alignment is reinforced by empirical and theoretical results\.

### 3\.2Definitions

Formally, a*circuit \(onnn\-bit inputs\)*is a directed acyclic graph \(DAG\)CnC\_\{n\}, whose vertices are called*gates*\. A circuitCnC\_\{n\}onnn\-bit inputs and sizess\(fors\>ns\>n\) is a DAG onssnodes with some*topological ordering*v1,…,vsv\_\{1\},\\ldots,v\_\{s\}of the nodes, i\.e\., a linear ordering of the nodes such that every nodeuuappears before every nodevvwith an edge fromuutovv\. The firstnnnodesv1,…,vnv\_\{1\},\\ldots,v\_\{n\}are sources \(called the*input gates*\), the nodevsv\_\{s\}is a sink \(called the*output gate*\), and there are no other sources or sinks\. Each gateviv\_\{i\}forn\+1≤i≤sn\+1\\leq i\\leq sis labeled with a symbolσi∈\{¬,∧,∨,𝖬𝖠𝖩\}\\sigma\_\{i\}\\in\\\{\\lnot,\\land,\\lor,\\mathsf\{MAJ\}\\\}\. The in\-degree of every gate labeled¬\\lnotis11, while the in\-degree of the other gates can be bigger than11\. The labels represent standard connectives in Boolean logic with𝖬𝖠𝖩\\mathsf\{MAJ\}being the*majority*function, which evaluates to11if and only if a \(strict\) majority of its inputs are11\.

For anynn\-bit input𝐱=\(x1,…,xn\)\\mathbf\{x\}=\(x\_\{1\},\\ldots,x\_\{n\}\), the circuitCnC\_\{n\}*evaluates*this input as follows: the*value*ofviv\_\{i\}for1≤i≤n1\\leq i\\leq nis defined to bexix\_\{i\}; for eachi≥n\+1i\\geq n\+1, the value ofviv\_\{i\}is the Boolean function corresponding to the labelσi\\sigma\_\{i\}evaluated on the values of the in\-neighbors ofviv\_\{i\}\(note that all Boolean functions considered here are commutative\); the*output*ofCnC\_\{n\}on input𝐱\\mathbf\{x\}is defined as the value ofvsv\_\{s\}\. Hence, the circuitCnC\_\{n\}can be viewed as a language recognizer over\{0,1\}n\\\{0,1\\\}^\{n\}\. Stated in other words,CnC\_\{n\}*accepts*annn\-bit input𝐱\\mathbf\{x\}if and only if the value ofvsv\_\{s\}on𝐱\\mathbf\{x\}is11\.

A*circuit family*𝒞\\mathcal\{C\}is a sequence\{Cn\}n∈ℕ\\\{C\_\{n\}\\\}\_\{n\\in\\mathbb\{N\}\}, where eachCnC\_\{n\}is a circuit onnn\-bit inputs\. Given any𝐱∈\{0,1\}∗\\mathbf\{x\}\\in\\\{0,1\\\}^\{\\ast\}, we can chooseC\|𝐱\|∈𝒞C\_\{\|\\mathbf\{x\}\|\}\\in\\mathcal\{C\}, and evaluateC\|𝐱\|C\_\{\|\\mathbf\{x\}\|\}on input𝐱\\mathbf\{x\}to obtain an output in\{0,1\}\\\{0,1\\\}\. Therefore, each circuit family computes a particular Boolean functionf:\{0,1\}∗→\{0,1\}f:\\\{0,1\\\}^\{\\ast\}\\to\\\{0,1\\\}\.

Note that a priori, a circuit family has an arbitrary circuitCnC\_\{n\}for eachn∈ℕn\\in\\mathbb\{N\}, but typically we want this family to be presented effectively by some low\-complexity function that generatesCnC\_\{n\}given the value ofnnin unary\. This is the standard notion of circuit*uniformity*\. We will only concern ourselves with uniform circuits\.

The complexity measures of a circuit family are its*size*\(the parameterss, which is the number of gates inCnC\_\{n\}\), its*depth*\(the length of the largest path from an input gate to an output gate inCnC\_\{n\}\), its*fan\-in*\(the maximum number of inputs to any gate ofCnC\_\{n\}\), and its*basis*\(the set of gate labels\{σi\}\\\{\\sigma\_\{i\}\\\}\)\. The first three of these are functions ofnn\. A circuit family is*constant depth*if its depth is a constant independent ofnn\. It is*bounded fan\-in*if its fan\-in is a constant independent ofnn\. All circuit families we consider are allowed to have size polynomial innn\.

Circuit complexity classes are obtained by constraining how size and depth grow withnn, and by deciding whether to include the𝖬𝖠𝖩\\mathsf\{MAJ\}label in the basis\. We will focus on the following two circuit classes:

- •𝖠𝖢0\\mathsf\{AC\}^\{0\}: constant\-depth, unbounded fan\-in, basis\{¬,∧,∨\}\\\{\\lnot,\\land,\\lor\\\}
- •𝖳𝖢0\\mathsf\{TC\}^\{0\}: constant\-depth, unbounded fan\-in, basis\{¬,∧,∨,𝖬𝖠𝖩\}\\\{\\lnot,\\land,\\lor,\\mathsf\{MAJ\}\\\}\.

It is well\-known that:

𝖠𝖢0⊊𝖳𝖢0⊆𝖫𝖮𝖦𝖲𝖯𝖠𝖢𝖤⊆𝖯𝖳𝖨𝖬𝖤,\\mathsf\{AC\}^\{0\}\\subsetneq\\mathsf\{TC\}^\{0\}\\subseteq\\mathsf\{LOGSPACE\}\\subseteq\\mathsf\{PTIME\},\(3\)where𝖫𝖮𝖦𝖲𝖯𝖠𝖢𝖤\\mathsf\{LOGSPACE\}is the class of languages recognized by a Turing machine with a logarithmic number of cells in its work tape and𝖯𝖳𝖨𝖬𝖤\\mathsf\{PTIME\}is the class of languages recognized by a Turing machine in polynomial time\. The first inclusion is strict because the𝖬𝖠𝖩\\mathsf\{MAJ\}function is provably not in𝖠𝖢0\\mathsf\{AC\}^\{0\}\[[8](https://arxiv.org/html/2608.12671#bib.bib21)\]; the next two inclusions are not known to be strict\. In particular, it is open whether𝖳𝖢0=𝖯𝖳𝖨𝖬𝖤\\mathsf\{TC\}^\{0\}=\\mathsf\{PTIME\}\.

### 3\.3Descriptive Complexity

It is known that the main computational complexity classes \(such as𝖯𝖳𝖨𝖬𝖤\\mathsf\{PTIME\}and𝖭𝖯\\mathsf\{NP\}\) and the main circuit complexity classes \(such as𝖠𝖢0\\mathsf\{AC\}^\{0\}and𝖳𝖢0\\mathsf\{TC\}^\{0\}\) have the same expressive power as certain logical formalisms\. In particular,𝖠𝖢0\\mathsf\{AC\}^\{0\}is equivalent to first\-order logic with the BIT predicate, where the𝖠𝖢0\\mathsf\{AC\}^\{0\}\-circuits are computed by a random access Turing machine in logarithmic time\. Furthermore,𝖳𝖢0\\mathsf\{TC\}^\{0\}is equivalent to first\-order logic with the BIT predicate and “majority” quantifiers, while𝖯𝖳𝖨𝖬𝖤\\mathsf\{PTIME\}is equivalent to least fixed\-point logic𝖫𝖥𝖯\\mathsf\{LFP\}on ordered structures\. For a detailed account of the research in this area, which is known as*descriptive complexity*, see the monograph by[12](https://arxiv.org/html/2608.12671#bib.bib22)\.

Results in descriptive complexity have been leveraged in studying the expressivity of transformers\. For example,[6](https://arxiv.org/html/2608.12671#bib.bib1)use an extension of first\-order logic to show that𝖳𝖢0\\mathsf\{TC\}^\{0\}contains fixed\-precision transformers with softmax attention \([7](https://arxiv.org/html/2608.12671#bib.bib11)shows that this holds for log\-precision transformers as well\)\.

## 4Expressivity Results

In this section, we provide some known expressivity results about transformers, with the corresponding assumptions on the parameters\.

However, before proceeding any further, we need to raise the issue of the precisionpp\(see Section[2](https://arxiv.org/html/2608.12671#S2)\), which is an important parameter of the transformer architecture\. Allowing this precision to arbitrary real numbers can increase the expressivity significantly, but has been widely characterized as unrealistic in practice\. On the other hand, limiting the precision toO⁡\(1\)O\(1\)bits prevents transformers from attending uniformly to length\-nnstrings for growingnn\[[18](https://arxiv.org/html/2608.12671#bib.bib10)\]; indeed, from a complexity point of view,O⁡\(1\)O\(1\)bits of precision collapses the expressivity of transformers down to𝖠𝖢0\\mathsf\{AC\}^\{0\}\[[14](https://arxiv.org/html/2608.12671#bib.bib4), Theorem 3\.1\]even with polynomial embedding dimension andO⁡\(log⁡n\)O\(\\log n\)steps of chain\-of\-thought, and the model of computation becomes somewhat less informative for distinguishing transformer variants \(see Section[3](https://arxiv.org/html/2608.12671#S3)\)\. A common choice of precision isΘ⁡\(log⁡n\)\\Theta\(\\log n\), which is rich enough to allow for addition and rounding conventions\.

### 4\.1Without Chain\-of\-Thought

Most expressivity results about transformers*without*chain\-of\-thought are based on simulation: one fixes a transformer architecture of constant depth and then shows that its computation on a given input can be simulated by an ad hoc circuit family in a low\-level circuit class\. The relevant circuit class depends strongly on two modeling choices: the type of attention and the amount of numerical precision available as a function of the input lengthnn\.

Thus, the majority of results in this realm take the form of upper bounds, i\.e\., they assert that the language recognized by the transformer under consideration is computable by a circuit family of low circuit complexity\. The following theorem describes some of the essential containments known, although we encourage the reader to refer to the relevant work for the exact assumptions on the architecture\.

###### Theorem 4\.1\.

The following statements are true:

- •𝖴𝖧𝖠𝖳\\mathsf\{UHAT\}encoders with arbitrary \(rational\) precision only recognize languages in𝖠𝖢0\\mathsf\{AC\}^\{0\}\[[10](https://arxiv.org/html/2608.12671#bib.bib12)\]\.
- •𝖲𝖬𝖠𝖳\\mathsf\{SMAT\}and𝖠𝖧𝖠𝖳\\mathsf\{AHAT\}encoders withO⁡\(1\)O\(1\)precision only recognize languages in𝖠𝖢0\\mathsf\{AC\}^\{0\}\[[17](https://arxiv.org/html/2608.12671#bib.bib14),[6](https://arxiv.org/html/2608.12671#bib.bib1),[14](https://arxiv.org/html/2608.12671#bib.bib4)\]\.
- •𝖲𝖬𝖠𝖳\\mathsf\{SMAT\}and𝖠𝖧𝖠𝖳\\mathsf\{AHAT\}encoders withO⁡\(log⁡n\)O\(\\log n\)\-precision only recognize languages in𝖳𝖢0\\mathsf\{TC\}^\{0\}\[[19](https://arxiv.org/html/2608.12671#bib.bib15),[25](https://arxiv.org/html/2608.12671#bib.bib26),[7](https://arxiv.org/html/2608.12671#bib.bib11)\]\.

The basic simulation argument used to prove Theorem[4\.1](https://arxiv.org/html/2608.12671#S4.Thmtheorem1)is captured by, e\.g\.,[10](https://arxiv.org/html/2608.12671#bib.bib12), who take an arbitrary encoder withLLlayers, consider its computation on any fixed arbitrary input, construct small Boolean circuit gadgets to carry out each part of the computation within each transformer layer, and then stitch together these circuit gadgets from different layers\. SinceLLis a constant, this still creates only a constant\-depth circuit that simulates the computation of the transformer\.𝖴𝖧𝖠𝖳\\mathsf\{UHAT\}is weak enough to be simulated only with∧\\land,∨\\lor, and¬\\lnotgates, and so this process gives rise to an𝖠𝖢0\\mathsf\{AC\}^\{0\}circuit family\. More sophisticated𝖠𝖧𝖠𝖳\\mathsf\{AHAT\}or𝖲𝖬𝖠𝖳\\mathsf\{SMAT\}machines require the computation of an*average*ofnnnumbers withO⁡\(log⁡n\)O\(\\log n\)precision, and this requires threshold gates to compute, resulting in𝖳𝖢0\\mathsf\{TC\}^\{0\}circuits\.

At this juncture, it is reasonable to ask whether or not each containment in Theorem[4\.1](https://arxiv.org/html/2608.12671#S4.Thmtheorem1)is tight\.[2](https://arxiv.org/html/2608.12671#bib.bib13)show that the result in the first bullet point in Theorem[4\.1](https://arxiv.org/html/2608.12671#S4.Thmtheorem1)is not tight: there are𝖠𝖢0\\mathsf\{AC\}^\{0\}languages not recognized by any𝖴𝖧𝖠𝖳\\mathsf\{UHAT\}transformers\. However, they show that𝖴𝖧𝖠𝖳\\mathsf\{UHAT\}transformers do recognize all languages definable in first\-order logic with arbitrary unary numerical predicates, which is a rich fragment of𝖠𝖢0\\mathsf\{AC\}^\{0\}\. Furthermore, the same paper shows that𝖠𝖧𝖠𝖳\\mathsf\{AHAT\}transformers recognize all languages definable in first\-order logic with unary numerical predicates*and*counting terms\. The results in the second and third bullet points are essentially tight:[14](https://arxiv.org/html/2608.12671#bib.bib4)show that, when one allows𝗉𝗈𝗅𝗒⁡\(n\)\\mathsf\{poly\}\(n\)embedding dimension, transformers withO⁡\(1\)O\(1\)precision andO⁡\(log⁡n\)O\(\\log n\)precision capture all of𝖠𝖢0\\mathsf\{AC\}^\{0\}and𝖳𝖢0\\mathsf\{TC\}^\{0\}, respectively\.

There are also several results with a slightly different flavor, utilizing logical characterizations or the Chomsky hierarchy rather than circuit classes\. For instance, using an intermediate logic called Boolean RASP \(or B\-RASP\),[27](https://arxiv.org/html/2608.12671#bib.bib3)show that𝖴𝖧𝖠𝖳\\mathsf\{UHAT\}decoders \(without positional encodings\) have the same expressive power as first\-order logic over the natural numbers with the<<relation \(equivalently, they recognize the class of star\-free languages\)\.

### 4\.2With Chain\-of\-Thought

Section[4\.1](https://arxiv.org/html/2608.12671#S4.SS1)highlights that essentially all known results about the expressivity of transformers*without*chain\-of\-thought tend to put them inside𝖳𝖢0\\mathsf\{TC\}^\{0\}\. Chain\-of\-thought breaks that barrier by going into classical complexity classes beyond𝖳𝖢0\\mathsf\{TC\}^\{0\}, including𝖫𝖮𝖦𝖲𝖯𝖠𝖢𝖤\\mathsf\{LOGSPACE\}and𝖯𝖳𝖨𝖬𝖤\\mathsf\{PTIME\}, which are believed to be significantly more powerful than𝖳𝖢0\\mathsf\{TC\}^\{0\}\(see the hierarchy in \([3](https://arxiv.org/html/2608.12671#S3.E3)\)\)\. This is achieved with appropriate bounds on the chain\-of\-thought; furthermore, transformers with unbounded chain\-of\-thought can simulate arbitrary Turing machines\.

Some known key results are summarized as follows\.

###### Theorem 4\.2\.

The following statements are true:

- •𝖲𝖬𝖠𝖳\\mathsf\{SMAT\}decoders withO⁡\(log⁡n\)O\(\\log n\)CoT andO⁡\(1\)O\(1\)precision only recognize languages in𝖠𝖢0\\mathsf\{AC\}^\{0\}\[[14](https://arxiv.org/html/2608.12671#bib.bib4)\]\.
- •𝖲𝖬𝖠𝖳\\mathsf\{SMAT\}decoders withO⁡\(log⁡n\)O\(\\log n\)CoT andO⁡\(log⁡n\)O\(\\log n\)precision only recognize languages in𝖳𝖢0\\mathsf\{TC\}^\{0\}\[[20](https://arxiv.org/html/2608.12671#bib.bib2),[14](https://arxiv.org/html/2608.12671#bib.bib4)\]\.
- •𝖠𝖧𝖠𝖳\\mathsf\{AHAT\}decoders withO⁡\(n\)O\(n\)CoT andO⁡\(log⁡n\)O\(\\log n\)precision only recognize languages in𝖣𝖳𝖨𝖬𝖤⁡\[n2\]\\mathsf\{DTIME\}\[n^\{2\}\], i\.e\., deterministic quadratic time\[[20](https://arxiv.org/html/2608.12671#bib.bib2)\]\.
- •𝖠𝖧𝖠𝖳\\mathsf\{AHAT\}decoders with𝗉𝗈𝗅𝗒⁡\(n\)\\mathsf\{poly\}\(n\)CoT andO⁡\(log⁡n\)O\(\\log n\)precision recognize precisely the languages in𝖯𝖳𝖨𝖬𝖤\\mathsf\{PTIME\}\[[20](https://arxiv.org/html/2608.12671#bib.bib2)\]\.
- •𝖠𝖧𝖠𝖳\\mathsf\{AHAT\}decoders with unbounded CoT and arbitrary precision can simulate arbitrary Turing machines\[[22](https://arxiv.org/html/2608.12671#bib.bib16),[4](https://arxiv.org/html/2608.12671#bib.bib17),[23](https://arxiv.org/html/2608.12671#bib.bib18),[15](https://arxiv.org/html/2608.12671#bib.bib19)\]\.
- •𝖲𝖬𝖠𝖳\\mathsf\{SMAT\}decoders with unbounded CoT andO⁡\(log⁡n\)O\(\\log n\)precision can simulate arbitrary Turing machines\[[13](https://arxiv.org/html/2608.12671#bib.bib29)\]\.

The arguments used to prove Theorem[4\.2](https://arxiv.org/html/2608.12671#S4.Thmtheorem2)typically involve simulating finite state machines and Turing machines by transformers with chain\-of\-thought, keeping track of the state and the tape contents by using the generated intermediate tokens, and carrying out each step of the machine computation\. Since the contents of the \(infinite\) tape of the Turing machine cannot be stored in a transformer, the key idea is to encode the computation history by means of the generated tokens\. Recognizing the current state of the Turing machine is straightforward to track using the decoder architecture\. The difficulty arises in reconstructing the tape symbol being read currently\. Roughly speaking, the basic idea leveraged for this is to use the following three steps:

1. 1\.Use autoregression to compute the sum of the previous head movements, to reconstruct the current head position \(using nontrivial techniques such as*layernorm hash*from[20](https://arxiv.org/html/2608.12671#bib.bib2)\);
2. 2\.Find the most recent timestepttwhen the head was in the same position;
3. 3\.Read off the symbol written on the tape at timesteptt\.

Once again, it is reasonable to ask whether or not the inclusions in the statement of Theorem[4\.2](https://arxiv.org/html/2608.12671#S4.Thmtheorem2)are tight\. We have already discussed in Section[4\.1](https://arxiv.org/html/2608.12671#S4.SS1)about the first and second bullet points being near equivalences, for𝗉𝗈𝗅𝗒⁡\(n\)\\mathsf\{poly\}\(n\)embedding dimension\. The third bullet point has a weak partial converse: Every linear\-time function is computable by an𝖠𝖧𝖠𝖳\\mathsf\{AHAT\}decoder withO⁡\(n\)O\(n\)chain\-of\-thought\. The fourth and fifth bullet points are equivalences: every recursively enumerable language is computable by a𝖴𝖧𝖠𝖳\\mathsf\{UHAT\}decoder with an unbounded amount of chain\-of\-thought333Note that this requires a model we have not formalized\. Specifically, all our CoT models require the numberf⁡\(n\)f\(n\)of intermediate tokens to be given in advance; however, transformers that compute arbitrary Turing\-recognizable languages do not havef⁡\(n\)f\(n\)given in advance, but rather have a specific “acceptance” token, such that the computation stops and accepts if this token is ever generated\. We omit the details here\.\.[3](https://arxiv.org/html/2608.12671#bib.bib20)systematically compute lower bounds on the amount of chain\-of\-thought required by transformers for various natural algorithmic problems\.

## 5Concluding Remarks

We gave an overview of the expressive power of transformer models by relating them to circuit complexity classes and logic\.

Overall, the complexity\-theoretic study of transformer expressivity reveals a nuanced picture: self\-attention endows these models with powerful mechanisms for context\-dependent computation, yet their abilities depend critically on such resources as depth, width, precision, positional encoding, and input length\. As the field matures, a central challenge is to relate these formal expressivity results to the behavior of real\-life trained models, turning insights from worst\-case complexity analysis into a sharper understanding of where and why transformers succeed, and where they encounter fundamental limitations\.

## Acknowledgments

We would like to thank Subhash Khot and Andy Yang for very helpful comments on early drafts of this survey\.

## References

- \[1\]J\. Ackerman and G\. Cybenko\(2020\)A survey of neural networks and formal languages\.External Links:2006\.01338,[Link](https://arxiv.org/abs/2006.01338)Cited by:[§1](https://arxiv.org/html/2608.12671#S1.p3.1)\.
- \[2\]P\. Barceló, A\. Kozachinskiy, A\. W\. Lin, and V\. Podolskii\(2024\)Logical languages accepted by transformer encoders with hard attention\.InThe Twelfth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=gbrHZq07mq)Cited by:[§4\.1](https://arxiv.org/html/2608.12671#S4.SS1.p4.1)\.
- \[3\]A\. A\. Bavandpour, X\. Huang, M\. Rofin, and M\. Hahn\(2025\)Lower bounds for chain\-of\-thought reasoning in hard\-attention transformers\.InForty\-second International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=Oh9sG5ae2b)Cited by:[§4\.2](https://arxiv.org/html/2608.12671#S4.SS2.p4.1)\.
- \[4\]S\. Bhattamishra, A\. Patel, and N\. Goyal\(2020\)On the computational power of transformers and its implications in sequence modeling\.InProceedings of the 24th Conference on Computational Natural Language Learning,R\. Fernández and T\. Linzen \(Eds\.\),Online,pp\. 455–475\.External Links:[Link](https://aclanthology.org/2020.conll-1.37/),[Document](https://dx.doi.org/10.18653/v1/2020.conll-1.37)Cited by:[5th item](https://arxiv.org/html/2608.12671#S4.I2.i5.p1.1)\.
- \[5\]L\. Chen, B\. Peng, and H\. Wu\(2024\)Theoretical limitations of multi\-layer transformer\.2025 IEEE 66th Annual Symposium on Foundations of Computer Science \(FOCS\),pp\. 2631–2653\.External Links:[Link](https://api.semanticscholar.org/CorpusID:274464787)Cited by:[§2\.2](https://arxiv.org/html/2608.12671#S2.SS2.SSS0.Px2.p2.1),[§2\.2](https://arxiv.org/html/2608.12671#S2.SS2.SSS0.Px3.p1.1)\.
- \[6\]D\. Chiang, P\. Cholak, and A\. Pillay\(2023\)Tighter bounds on the expressivity of transformer encoders\.InProceedings of the 40th International Conference on Machine Learning,A\. Krause, E\. Brunskill, K\. Cho, B\. Engelhardt, S\. Sabato, and J\. Scarlett \(Eds\.\),Proceedings of Machine Learning Research, Vol\.202,pp\. 5544–5562\.External Links:[Link](https://proceedings.mlr.press/v202/chiang23a.html)Cited by:[§3\.3](https://arxiv.org/html/2608.12671#S3.SS3.p2.1),[2nd item](https://arxiv.org/html/2608.12671#S4.I1.i2.p1.1)\.
- \[7\]D\. Chiang\(2025\)Transformers in uniform TC0\{\{\}^\{0\}\}\.Transactions on Machine Learning Research\.Note:External Links:ISSN 2835\-8856,[Link](https://openreview.net/forum?id=ZA7D4nQuQF)Cited by:[§3\.3](https://arxiv.org/html/2608.12671#S3.SS3.p2.1),[3rd item](https://arxiv.org/html/2608.12671#S4.I1.i3.p1.1)\.
- \[8\]M\. L\. Furst, J\. B\. Saxe, and M\. Sipser\(1984\)Parity, circuits, and the polynomial\-time hierarchy\.Math\. Syst\. Theory17\(1\),pp\. 13–27\.External Links:[Link](https://doi.org/10.1007/BF01744431),[Document](https://dx.doi.org/10.1007/BF01744431)Cited by:[§3\.2](https://arxiv.org/html/2608.12671#S3.SS2.p6.3)\.
- \[9\]M\. Hahn\(2020\)Theoretical limitations of self\-attention in neural sequence models\.Transactions of the Association for Computational Linguistics8,pp\. 156–171\.External Links:[Link](https://aclanthology.org/2020.tacl-1.11/),[Document](https://dx.doi.org/10.1162/tacl%5Fa%5F00306)Cited by:[§2\.2](https://arxiv.org/html/2608.12671#S2.SS2.SSS0.Px1.p1.1)\.
- \[10\]Y\. Hao, D\. Angluin, and R\. Frank\(2022\)Formal language recognition by hard attention transformers: perspectives from circuit complexity\.Transactions of the Association for Computational Linguistics10,pp\. 800–810\.External Links:[Link](https://aclanthology.org/2022.tacl-1.46/),[Document](https://dx.doi.org/10.1162/tacl%5Fa%5F00490)Cited by:[§2\.2](https://arxiv.org/html/2608.12671#S2.SS2.SSS0.Px1.p1.1),[1st item](https://arxiv.org/html/2608.12671#S4.I1.i1.p1.1),[§4\.1](https://arxiv.org/html/2608.12671#S4.SS1.p3.1)\.
- \[11\]A\. Holtzman, J\. Buys, L\. Du, M\. Forbes, and Y\. Choi\(2020\)The curious case of neural text degeneration\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=rygGQyrFvH)Cited by:[footnote 1](https://arxiv.org/html/2608.12671#footnote1)\.
- \[12\]N\. Immerman\(1999\)Descriptive complexity\.Graduate texts in computer science,Springer\.External Links:[Link](https://doi.org/10.1007/978-1-4612-0539-5),[Document](https://dx.doi.org/10.1007/978-1-4612-0539-5),ISBN 978\-1\-4612\-6809\-3Cited by:[§3\.3](https://arxiv.org/html/2608.12671#S3.SS3.p1.1)\.
- \[13\]H\. Jiang, M\. Hahn, G\. Zetzsche, and A\. W\. Lin\(2026\)Softmax transformers are Turing\-complete\.InThe Fourteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=FdkPOHlChS)Cited by:[6th item](https://arxiv.org/html/2608.12671#S4.I2.i6.p1.1)\.
- \[14\]Z\. Li, H\. Liu, D\. Zhou, and T\. Ma\(2024\)Chain of thought empowers transformers to solve inherently serial problems\.InInternational Conference on Learning Representations,B\. Kim, Y\. Yue, S\. Chaudhuri, K\. Fragkiadaki, M\. Khan, and Y\. Sun \(Eds\.\),Vol\.2024,pp\. 11911–11943\.External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2024/file/3309b4112c9f04a993f2bbdd0274bba1-Paper-Conference.pdf)Cited by:[§2\.2](https://arxiv.org/html/2608.12671#S2.SS2.SSS0.Px3.p1.1),[2nd item](https://arxiv.org/html/2608.12671#S4.I1.i2.p1.1),[1st item](https://arxiv.org/html/2608.12671#S4.I2.i1.p1.1),[2nd item](https://arxiv.org/html/2608.12671#S4.I2.i2.p1.1),[§4\.1](https://arxiv.org/html/2608.12671#S4.SS1.p4.1),[§4](https://arxiv.org/html/2608.12671#S4.p2.1)\.
- \[15\]E\. Malach\(2024\)Auto\-regressive next\-token predictors are universal learners\.InForty\-first International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=i56plqPpEa)Cited by:[5th item](https://arxiv.org/html/2608.12671#S4.I2.i5.p1.1)\.
- \[16\]W\. Merrill, V\. Ramanujan, Y\. Goldberg, R\. Schwartz, and N\. A\. Smith\(2021\)Effects of parameter norm growth during transformer training: inductive bias from gradient descent\.InProceedings of the 2021 Conference on Empirical Methods in Natural Language Processing,M\. Moens, X\. Huang, L\. Specia, and S\. W\. Yih \(Eds\.\),Online and Punta Cana, Dominican Republic,pp\. 1766–1781\.External Links:[Link](https://aclanthology.org/2021.emnlp-main.133/),[Document](https://dx.doi.org/10.18653/v1/2021.emnlp-main.133)Cited by:[§2\.2](https://arxiv.org/html/2608.12671#S2.SS2.SSS0.Px1.p1.1)\.
- \[17\]W\. Merrill, A\. Sabharwal, and N\. A\. Smith\(2022\)Saturated transformers are constant\-depth threshold circuits\.Transactions of the Association for Computational Linguistics10,pp\. 843–856\.External Links:[Link](https://aclanthology.org/2022.tacl-1.49/),[Document](https://dx.doi.org/10.1162/tacl%5Fa%5F00493)Cited by:[§2\.2](https://arxiv.org/html/2608.12671#S2.SS2.SSS0.Px1.p1.1),[2nd item](https://arxiv.org/html/2608.12671#S4.I1.i2.p1.1)\.
- \[18\]W\. Merrill and A\. Sabharwal\(2023\)A logic for expressing log\-precision transformers\.InAdvances in Neural Information Processing Systems,A\. Oh, T\. Naumann, A\. Globerson, K\. Saenko, M\. Hardt, and S\. Levine \(Eds\.\),Vol\.36,pp\. 52453–52463\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2023/file/a48e5877c7bf86a513950ab23b360498-Paper-Conference.pdf)Cited by:[§4](https://arxiv.org/html/2608.12671#S4.p2.1)\.
- \[19\]W\. Merrill and A\. Sabharwal\(2023\)The parallelism tradeoff: limitations of log\-precision transformers\.Transactions of the Association for Computational Linguistics11,pp\. 531–545\.External Links:[Link](https://aclanthology.org/2023.tacl-1.31/),[Document](https://dx.doi.org/10.1162/tacl%5Fa%5F00562)Cited by:[3rd item](https://arxiv.org/html/2608.12671#S4.I1.i3.p1.1)\.
- \[20\]W\. Merrill and A\. Sabharwal\(2024\)The expressive power of transformers with chain of thought\.InInternational Conference on Learning Representations,B\. Kim, Y\. Yue, S\. Chaudhuri, K\. Fragkiadaki, M\. Khan, and Y\. Sun \(Eds\.\),Vol\.2024,pp\. 7690–7706\.External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2024/file/1f59721c106ea80f613299039112f651-Paper-Conference.pdf)Cited by:[§2\.2](https://arxiv.org/html/2608.12671#S2.SS2.SSS0.Px3.p1.1),[2nd item](https://arxiv.org/html/2608.12671#S4.I2.i2.p1.1),[3rd item](https://arxiv.org/html/2608.12671#S4.I2.i3.p1.1),[4th item](https://arxiv.org/html/2608.12671#S4.I2.i4.p1.1),[item 1](https://arxiv.org/html/2608.12671#S4.I3.i1.p1.1)\.
- \[21\]W\. Merrill\(2023\)Formal languages and the NLP black box\.InDevelopments in Language Theory: 27th International Conference, DLT 2023, Umeå, Sweden, June 12–16, 2023, Proceedings,Berlin, Heidelberg,pp\. 1–8\.External Links:ISBN 978\-3\-031\-33263\-0,[Link](https://doi.org/10.1007/978-3-031-33264-7_1),[Document](https://dx.doi.org/10.1007/978-3-031-33264-7%5F1)Cited by:[§1](https://arxiv.org/html/2608.12671#S1.p3.1)\.
- \[22\]J\. Pérez, P\. Barceló, and J\. Marinkovic\(2021\)Attention is Turing complete\.J\. Mach\. Learn\. Res\.22\(1\)\.External Links:ISSN 1532\-4435Cited by:[§2\.2](https://arxiv.org/html/2608.12671#S2.SS2.SSS0.Px1.p1.1),[5th item](https://arxiv.org/html/2608.12671#S4.I2.i5.p1.1)\.
- \[23\]R\. Qiu, Z\. Xu, W\. Bao, and H\. Tong\(2025\)Ask, and it shall be given: on the Turing completeness of prompting\.InInternational Conference on Learning Representations,Y\. Yue, A\. Garg, N\. Peng, F\. Sha, and R\. Yu \(Eds\.\),Vol\.2025,pp\. 6286–6309\.External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2025/file/123d3e814e257e0781e5d328232ead9b-Paper-Conference.pdf)Cited by:[5th item](https://arxiv.org/html/2608.12671#S4.I2.i5.p1.1)\.
- \[24\]L\. Strobl, W\. Merrill, G\. Weiss, D\. Chiang, and D\. Angluin\(2024\)What formal languages can transformers express? A survey\.Transactions of the Association for Computational Linguistics12,pp\. 543–561\.External Links:[Link](https://aclanthology.org/2024.tacl-1.30/),[Document](https://dx.doi.org/10.1162/tacl%5Fa%5F00663)Cited by:[§1](https://arxiv.org/html/2608.12671#S1.p3.1)\.
- \[25\]L\. Strobl\(2023\)Average\-hard attention transformers are constant\-depth uniform threshold circuits\.External Links:2308\.03212,[Link](https://arxiv.org/abs/2308.03212)Cited by:[3rd item](https://arxiv.org/html/2608.12671#S4.I1.i3.p1.1)\.
- \[26\]A\. Vaswani, N\. Shazeer, N\. Parmar, J\. Uszkoreit, L\. Jones, A\. N\. Gomez, L\. Kaiser, and I\. Polosukhin\(2017\)Attention is all you need\.InAdvances in Neural Information Processing Systems,I\. Guyon, U\. V\. Luxburg, S\. Bengio, H\. Wallach, R\. Fergus, S\. Vishwanathan, and R\. Garnett \(Eds\.\),Vol\.30,pp\.\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf)Cited by:[§2\.2](https://arxiv.org/html/2608.12671#S2.SS2.SSS0.Px1.p1.1)\.
- \[27\]A\. Yang, D\. Chiang, and D\. Angluin\(2024\)Masked hard\-attention transformers recognize exactly the star\-free languages\.InThe Thirty\-eighth Annual Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=FBMsBdH0yz)Cited by:[§4\.1](https://arxiv.org/html/2608.12671#S4.SS1.p5.1)\.
- \[28\]A\. Yang, L\. Strobl, D\. Chiang, and D\. Angluin\(2025\)Simulating hard attention using soft attention\.External Links:2412\.09925,[Link](https://arxiv.org/abs/2412.09925)Cited by:[§2\.3](https://arxiv.org/html/2608.12671#S2.SS3.SSS0.Px2.p4.2)\.
- \[29\]A\. Yang, C\. Watson, A\. Xue, S\. Bhattamishra, J\. Llarena, W\. Merrill, E\. D\. S\. Ferreira, A\. Svete, and D\. Chiang\(2026\)The transformer cookbook\.Transactions on Machine Learning Research\.Note:External Links:ISSN 2835\-8856,[Link](https://openreview.net/forum?id=sPshCSvDrX)Cited by:[§1](https://arxiv.org/html/2608.12671#S1.p3.1),[§2\.3](https://arxiv.org/html/2608.12671#S2.SS3.SSS0.Px2.p6.3)\.