Paper deep dive
On the Expressive Power of Transformers
Phokion Kolaitis, Rik Sengupta
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 8/14/2026, 4:54:39 AM
Summary
This paper surveys the expressive power of multi-layer transformers as language recognizers by mapping their computational capabilities to circuit complexity classes. It analyzes how architectural parameters—such as attention type (hard vs. soft), precision, depth, and the use of Chain-of-Thought (CoT)—determine whether a transformer can recognize specific formal languages, comparing them against bounded-depth circuits and automata.
Entities (8)
Relation Signals (5)
Transformer → analyzedusing → Circuit Complexity
confidence 95% · circuit complexity has by and large emerged as the 'correct' branch of computational complexity to analyze the expressive power of transformers
Chain-of-Thought → increasespowerof → Transformer
confidence 92% · it is known that transformers with this ability are strictly more powerful than transformers without
Soft Attention → hasmoreexpressivepowerthan → Hard Attention
confidence 90% · the latter [soft attention] tends to have more expressive power than the former [hard attention]
Encoder → isstrictlymorepowerfulthan → Decoder
confidence 88% · encoder models can be shown theoretically to be strictly more powerful than decoder models for language recognition
Transformer → comparedagainst → Chomsky Hierarchy
confidence 85% · The lens of circuit complexity is more effective than, say, the lens of the Chomsky hierarchy
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2608.12671v1
- Canonical: https://arxiv.org/abs/2608.12671v1
Trouble viewing inline? Open PDF directly →
Full Text
45,952 characters extracted from source content.
Expand or collapse full text
On the Expressive Power of Transformers Phokion G. Kolaitis Affiliation: University of California Santa Cruz Affiliation: Santa Cruz, CA Email: kolaitis@ucsc.edu Rik Sengupta Affiliation: IBM Research Affiliation: Cambridge, MA Email: rik@ibm.com 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 Introduction 2 The Architecture 2.1 Transformers as Language Recognizers 2.2 Characteristics and Parameters of a Transformer 2.3 Encoder Computation 2.4 Decoder Computation 3 Classical and Circuit Complexity 3.1 The “Right” Hierarchy 3.2 Definitions 3.3 Descriptive Complexity 4 Expressivity Results 4.1 Without Chain-of-Thought 4.2 With Chain-of-Thought 5 Concluding Remarks References 1 Introduction 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], RNNs and transformers [21], transformer expressivity [24], and the transformer cookbook [29]. 2 The Architecture 2.1 Transformers 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 Σ , whose length n is 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 a d-dimensional real vector, where d is a parameter of the transformer. Each hidden layer thereafter takes a sequence of length n of d-dimensional real vectors as its input, and applies a length-preserving function to this sequence, resulting in a sequence of length n of d-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 of d-dimensional vectors into a single probability pout∈[0,1]p_out∈[0,1], and accepts the input string if and only if pout≥1/2p_out≥ 1/2. • In a transformer decoder (the model adopted in viewing transformers as language models), the output layer outputs a new token11 1 The new token can be viewed as being drawn from an implicit probability distribution over Σ . 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], 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 probability poutp_out (instead of a new token), and accepts the original input string if and only if pout≥1/2p_out≥ 1/2. 2.2 Characteristics 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], 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, 10, 22, 17, 16]. Standard choices for the attention include UHAT (“unique hard attention”), AHAT (“average hard attention”), and 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 models22 2 It 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], 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, 20, 14]. 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 by L. We will always assume L to be a constant, and index the layers as ℓ∈[L] ∈[L]. • Number of attention heads: the number of attention heads, typically denoted by H. We will again assume that H is a constant, and index the heads as h∈[H]h∈[H]. • Embedding dimension: the length of the embedded vectors, denoted by d. There are often two additional dimensions, the key width dkeyd_key and the hidden width dhiddend_hidden. Each of these parameters is allowed to depend on the context length n, 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 by p. This parameter is also, in general, a function of the input length n; in fact, we often assume p to be Θ(logn) ( n) (see the discussion at the start of Section 4). • Amount of chain-of-thought: for transformers with chain-of-thought, the number of intermediate tokens allowed to be generated, as a function f(n)f(n) of the input length n. In Section 4.2, we shall see the difference in expressivity resulting from different asymptotic choices for the function f(n)f(n). Sometimes, the number L of layers is called the depth of the transformer, while the product HdpHdp of the embedding dimension, number of attention heads, and number of precision bits used is called its width. It should be emphasized that the context length n (i.e., the length n of 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.3 Encoder Computation Figure 1: A high-level view of the encoder architecture. If X is a set, we will write X∗X^* to denote the set of all finite sequences with elements from X, while we will write X+X^+ to denote the set of all non-empty such sequences. The set of all real numbers will be denoted by ℝR. Furthermore, if m is a natural number, we will write [m][m] to denote the set 1,…,m\1,…,m\. Input Layer. In the input layer, a string of length n is mapped to a sequence of n vectors over ℝdR^d via a length-preserving function :Σ∗→(ℝd)∗ embed: →(R^d) . To obtain the result of applying the function embed on a string w∈Σ∗w∈ , we take each input character wiw_i in turn, and take the sum of two functions: the word embedding function :Σ→ℝd WE: ^d applied to the character wiw_i, and the positional encoding function :[n]→ℝd PE:[n] ^d applied to the index i. The output of the input layer is the resulting sequence (1(0),…,n(0))∈(ℝd)n(x^(0)_1,…,x^(0)_n)∈(R^d)^n. In other words, we have: i(0)=(wi)+(i), for all i∈[n].x^(0)_i= WE(w_i)+ PE(i), for all i∈[n]. Hidden Layers. Each hidden layer ℓ∈[L] ∈[L] of the transformer is a length-preserving function ℒ(ℓ):(ℝd)∗→(ℝd)∗L^( ):(R^d) →(R^d) that takes a sequence (1(ℓ−1),…,n(ℓ−1))∈(ℝd)n(x^( -1)_1,…,x^( -1)_n)∈(R^d)^n as input and outputs a sequence (1(ℓ),…,n(ℓ))∈(ℝd)n(x^( )_1,…,x^( )_n)∈(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 width d and key-width dkeyd_key is a length-preserving function :(ℝd)+→(ℝd)+ sa:(R^d)^+→(R^d)^+, in essence the weighted sums of value vectors in all n positions, where the weights are a function of query vectors and key vectors. In other words, we have three matrices (Q),(K),(V)∈ℝdkey×dW^(Q),W^(K),W^(V) ^d_key× d, together with a length-preserving weighting function :ℝ+→ℝ+S:R^+ ^+ and an output matrix (O)∈ℝd×dkeyW^(O) ^d× d_key, computing the following in an encoder model: (1,…,n) sa(x_1,…,x_n) =(1,…,n), where: =(y_1,…,y_n), where: i _i =(O)(∑j=1nαi,jj), =W^(O) ( _j=1^n _i,jv_j ), j _j =(V)j, =W^(V)x_j, αi,∗ _i, =(si,∗), =S(s_i, ), (1) si,j s_i,j =i⊤jdkey, = q_i k_j d_key, i _i =(Q)i, =W^(Q)x_i, j _j =(K)j. =W^(K)x_j. (2) Here, si,∗:=(si,1,…,si,n)s_i, :=(s_i,1,…,s_i,n) is the vector of attention scores, while αi,∗:=(αi,1,…,αi,n) _i, :=( _i,1,…, _i,n) is the vector of attention weights. Note that the weights αi,∗ _i, are obtained by applying a weighting function S to the attention scores si,∗s_i, . The softmax function is the most common choice for a weighting function, where: [(a1,…,an)]i=exp(ai)∑j=1nexp(aj). [ softmax(a_1,…,a_n)]_i= (a_i) _j=1^n (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 UHAT model), or takes an average over those positions (in the AHAT model). Since most variants of hard attention can be simulated by softmax attention using positional encodings or other techniques [28], we focus on the SMAT model here. A position-wise feed-forward sublayer with width d and hidden width dhiddend_hidden is a function :ℝd→ℝd f:R^d ^d, in essence a piecewise affine transformation on every position. Thus, we have matrices 1∈ℝdhidden×dW_1 ^d_hidden× d, 2∈ℝd×dhiddenW_2 ^d× d_hidden, and vectors 1∈ℝdhiddenb_1 ^d_hidden, 2∈ℝdb_2 ^d, so that: ()=, where :=2+2 and :=ReLU(1+1). f(x)=y, where y:=W_2z+b_2 and z:=ReLU(W_1x+b_1). Here, the rectified linear unit function ReLU(x)=max(0,x)ReLU(x)= (0,x) is applied coordinatewise. Now, for every layer ℓ∈[L] ∈[L] and every attention head h∈[H]h∈[H], let (h,ℓ) sa^(h, ) be a self-attention sublayer with width d. Similarly, for every layer ℓ∈[L] ∈[L], let (ℓ) f^( ) be a feed-forward sublayer with width d. The transformer layer for layer ℓ∈[L] ∈[L] is defined as: ℒ(ℓ)(1(ℓ−1),…,n(ℓ−1)) ^( )(x^( -1)_1,…,x^( -1)_n) =(1(ℓ),…,n(ℓ)), where: =(x^( )_1,…,x^( )_n), where: (1(ℓ),…,n(ℓ)) (y^( )_1,…,y^( )_n) :=∑h=1H(h,ℓ)(1(ℓ−1),…,n(ℓ−1))+(1(ℓ−1),…,n(ℓ−1)), := _h=1^H sa^(h, )(x^( -1)_1,…,x^( -1)_n)+(x^( -1)_1,…,x^( -1)_n), (1(ℓ),…,n(ℓ)) (x^( )_1,…,x^( )_n) :=((ℓ)(1(ℓ)),…,(ℓ)(n(ℓ)))+(1(ℓ),…,n(ℓ)). :=( f^( )(y^( )_1),…, f^( )(y^( )_n))+(y^( )_1,…,y^( )_n). While carrying out its computations on an input string w∈Σ∗w∈ , the hidden layers of the transformer apply the function ℒ(ℓ)L^( ) sequentially over the layers ℓ∈[L] ∈[L], where the input to layer 11 is the sequence (w) embed(w). In effect, therefore, the hidden layers compute the composition: ℒ(L)∘⋯∘ℒ(1)((w)). ^(L) ·s ^(1)( 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. Output Layer. The last layer L outputs a sequence of length-d vectors (1(L),…,n(L))(x^(L)_1,…,x^(L)_n). Then, the transformer takes a fixed one of these vectors (typically, n(L)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 to 00 or 11, and outputs the result (interpreted as rejection and acceptance respectively). Thus, we have a vector ∈ℝdw ^d and a scalar b∈ℝb such that p=σ(⊤⋅n(L)+b)p=σ(w ·x^(L)_n+b), where σ is the sigmoid function, i.e., σ(x)=1/(1+e−x)σ(x)=1/(1+e^-x). The output of the transformer is ⌊p+1/2⌋∈0,1 p+1/2 ∈\0,1\. Remark 2.1. In practice, the weight matrices and vectors throughout the architecture are learned during training and then held fixed at inference time. For expressivity results, it is often useful to impose boundedness assumptions (e.g., on the norm or Lipschitz constant), since such conditions control how the output can change under perturbations of the input and rule out pathological behavior. We do not concern ourselves with these considerations in this survey. 2.4 Decoder 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 setting si,j=−∞s_i,j=-∞, for all i<ji<j in equations 1 and 2 (everything else remains the same). As a consequence of this, all terms with i<ji<j in 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)x_n^(L) into a scalar, and then converts this scalar into a probability. In decoders, the output layer uses n(L)x_n^(L) to produce a token from the alphabet Σ , which can be thought of as the transformer drawing from an implicit probability distribution over the tokens in Σ . Thus, we have an output function γ:ℝd→Σγ:R^d→ parameterized as a linear transformation. The output of the transformer is simply γ(n(L))γ(x_n^(L)). In decoders with chain-of-thought f(n)f(n), the autoregressive nature is leveraged in order to output a sequence of intermediate tokens, for f(n)f(n) timesteps. Formally, for a fixed decoder T, let F:Σ∗→ΣF_T: → be the function mapping an input string to a token (parameterized by T). For every w=w1…wn∈Σ∗w=w_1… w_n∈ , define: F0(w) F_T^0(w) :=w :=w Fi(w) F_T^i(w) :=Fi−1(w)⋅F(Fi−1(w)) for i≥1, :=F_T^i-1(w)· F_T(F_T^i-1(w)) for i≥ 1, where ⋅· denotes concatenation. For j≥1j≥ 1, let wn+j:=F(Fj−1(w))w_n+j:=F_T(F_T^j-1(w)) be the output token in timestep j. Then, the output of the transformer is the sequence of tokens: (wn+1,…,wn+f(n)).(w_n+1,…,w_n+f(n)). This transformer can, of course, be easily converted to a language recognizer: instead of generating the final token wn+f(n)w_n+f(n), the output layer takes the d-dimensional vector n+f(n)−1(L)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 CoT f(n)f(n)) can be visualized as follows: Figure 2: An encoder (left) and a decoder (right). 3 Classical and Circuit Complexity 3.1 The “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.2 Definitions Formally, a circuit (on n-bit inputs) is a directed acyclic graph (DAG) CnC_n, whose vertices are called gates. A circuit CnC_n on n-bit inputs and size s (for s>ns>n) is a DAG on s nodes with some topological ordering v1,…,vsv_1,…,v_s of the nodes, i.e., a linear ordering of the nodes such that every node u appears before every node v with an edge from u to v. The first n nodes v1,…,vnv_1,…,v_n are sources (called the input gates), the node vsv_s is a sink (called the output gate), and there are no other sources or sinks. Each gate viv_i for n+1≤i≤sn+1≤ i≤ s is labeled with a symbol σi∈¬,∧,∨, _i∈\ , , , MAJ\. The in-degree of every gate labeled ¬ is 11, while the in-degree of the other gates can be bigger than 11. The labels represent standard connectives in Boolean logic with MAJ being the majority function, which evaluates to 11 if and only if a (strict) majority of its inputs are 11. For any n-bit input =(x1,…,xn)x=(x_1,…,x_n), the circuit CnC_n evaluates this input as follows: the value of viv_i for 1≤i≤n1≤ i≤ n is defined to be xix_i; for each i≥n+1i≥ n+1, the value of viv_i is the Boolean function corresponding to the label σi _i evaluated on the values of the in-neighbors of viv_i (note that all Boolean functions considered here are commutative); the output of CnC_n on input x is defined as the value of vsv_s. Hence, the circuit CnC_n can be viewed as a language recognizer over 0,1n\0,1\^n. Stated in other words, CnC_n accepts an n-bit input x if and only if the value of vsv_s on x is 11. A circuit family C is a sequence Cnn∈ℕ\C_n\_n , where each CnC_n is a circuit on n-bit inputs. Given any ∈0,1∗x∈\0,1\ , we can choose C||∈C_|x| , and evaluate C||C_|x| on input x to obtain an output in 0,1\0,1\. Therefore, each circuit family computes a particular Boolean function f:0,1∗→0,1f:\0,1\ →\0,1\. Note that a priori, a circuit family has an arbitrary circuit CnC_n for each n∈ℕn , but typically we want this family to be presented effectively by some low-complexity function that generates CnC_n given the value of n in 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 parameter s, which is the number of gates in CnC_n), its depth (the length of the largest path from an input gate to an output gate in CnC_n), its fan-in (the maximum number of inputs to any gate of CnC_n), and its basis (the set of gate labels σi\ _i\). The first three of these are functions of n. A circuit family is constant depth if its depth is a constant independent of n. It is bounded fan-in if its fan-in is a constant independent of n. All circuit families we consider are allowed to have size polynomial in n. Circuit complexity classes are obtained by constraining how size and depth grow with n, and by deciding whether to include the MAJ label in the basis. We will focus on the following two circuit classes: • 0 AC^0: constant-depth, unbounded fan-in, basis ¬,∧,∨\ , , \ • 0 TC^0: constant-depth, unbounded fan-in, basis ¬,∧,∨,\ , , , MAJ\. It is well-known that: 0⊊0⊆, AC^0 TC^0 LOGSPACE PTIME, (3) where LOGSPACE is the class of languages recognized by a Turing machine with a logarithmic number of cells in its work tape and PTIME is the class of languages recognized by a Turing machine in polynomial time. The first inclusion is strict because the MAJ function is provably not in 0 AC^0 [8]; the next two inclusions are not known to be strict. In particular, it is open whether 0= TC^0= PTIME. 3.3 Descriptive Complexity It is known that the main computational complexity classes (such as PTIME and NP) and the main circuit complexity classes (such as 0 AC^0 and 0 TC^0) have the same expressive power as certain logical formalisms. In particular, 0 AC^0 is equivalent to first-order logic with the BIT predicate, where the 0 AC^0-circuits are computed by a random access Turing machine in logarithmic time. Furthermore, 0 TC^0 is equivalent to first-order logic with the BIT predicate and “majority” quantifiers, while PTIME is equivalent to least fixed-point logic 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. Results in descriptive complexity have been leveraged in studying the expressivity of transformers. For example, 6 use an extension of first-order logic to show that 0 TC^0 contains fixed-precision transformers with softmax attention (7 shows that this holds for log-precision transformers as well). 4 Expressivity 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 precision p (see Section 2), 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 to O(1)O(1) bits prevents transformers from attending uniformly to length-n strings for growing n [18]; indeed, from a complexity point of view, O(1)O(1) bits of precision collapses the expressivity of transformers down to 0 AC^0 [14, Theorem 3.1] even with polynomial embedding dimension and O(logn)O( n) steps of chain-of-thought, and the model of computation becomes somewhat less informative for distinguishing transformer variants (see Section 3). A common choice of precision is Θ(logn) ( n), which is rich enough to allow for addition and rounding conventions. 4.1 Without 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 length n. 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: • UHAT encoders with arbitrary (rational) precision only recognize languages in 0 AC^0 [10]. • SMAT and AHAT encoders with O(1)O(1) precision only recognize languages in 0 AC^0 [17, 6, 14]. • SMAT and AHAT encoders with O(logn)O( n)-precision only recognize languages in 0 TC^0 [19, 25, 7]. The basic simulation argument used to prove Theorem 4.1 is captured by, e.g., 10, who take an arbitrary encoder with L layers, 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. Since L is a constant, this still creates only a constant-depth circuit that simulates the computation of the transformer. UHAT is weak enough to be simulated only with ∧ , ∨ , and ¬ gates, and so this process gives rise to an 0 AC^0 circuit family. More sophisticated AHAT or SMAT machines require the computation of an average of n numbers with O(logn)O( n) precision, and this requires threshold gates to compute, resulting in 0 TC^0 circuits. At this juncture, it is reasonable to ask whether or not each containment in Theorem 4.1 is tight. 2 show that the result in the first bullet point in Theorem 4.1 is not tight: there are 0 AC^0 languages not recognized by any UHAT transformers. However, they show that UHAT transformers do recognize all languages definable in first-order logic with arbitrary unary numerical predicates, which is a rich fragment of 0 AC^0. Furthermore, the same paper shows that 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 show that, when one allows (n) poly(n) embedding dimension, transformers with O(1)O(1) precision and O(logn)O( n) precision capture all of 0 AC^0 and 0 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 show that 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.2 With Chain-of-Thought Section 4.1 highlights that essentially all known results about the expressivity of transformers without chain-of-thought tend to put them inside 0 TC^0. Chain-of-thought breaks that barrier by going into classical complexity classes beyond 0 TC^0, including LOGSPACE and PTIME, which are believed to be significantly more powerful than 0 TC^0 (see the hierarchy in (3)). 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: • SMAT decoders with O(logn)O( n) CoT and O(1)O(1) precision only recognize languages in 0 AC^0 [14]. • SMAT decoders with O(logn)O( n) CoT and O(logn)O( n) precision only recognize languages in 0 TC^0 [20, 14]. • AHAT decoders with O(n)O(n) CoT and O(logn)O( n) precision only recognize languages in [n2] DTIME[n^2], i.e., deterministic quadratic time [20]. • AHAT decoders with (n) poly(n) CoT and O(logn)O( n) precision recognize precisely the languages in PTIME [20]. • AHAT decoders with unbounded CoT and arbitrary precision can simulate arbitrary Turing machines [22, 4, 23, 15]. • SMAT decoders with unbounded CoT and O(logn)O( n) precision can simulate arbitrary Turing machines [13]. The arguments used to prove Theorem 4.2 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. 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); 2. Find the most recent timestep t when the head was in the same position; 3. Read off the symbol written on the tape at timestep t. Once again, it is reasonable to ask whether or not the inclusions in the statement of Theorem 4.2 are tight. We have already discussed in Section 4.1 about the first and second bullet points being near equivalences, for (n) poly(n) embedding dimension. The third bullet point has a weak partial converse: Every linear-time function is computable by an AHAT decoder with O(n)O(n) chain-of-thought. The fourth and fifth bullet points are equivalences: every recursively enumerable language is computable by a UHAT decoder with an unbounded amount of chain-of-thought33 3 Note that this requires a model we have not formalized. Specifically, all our CoT models require the number f(n)f(n) of intermediate tokens to be given in advance; however, transformers that compute arbitrary Turing-recognizable languages do not have f(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 systematically compute lower bounds on the amount of chain-of-thought required by transformers for various natural algorithmic problems. 5 Concluding 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 Cited by: §1. [2] P. Barceló, A. Kozachinskiy, A. W. Lin, and V. Podolskii (2024) Logical languages accepted by transformer encoders with hard attention. In The Twelfth International Conference on Learning Representations, External Links: Link Cited by: §4.1. [3] A. A. Bavandpour, X. Huang, M. Rofin, and M. Hahn (2025) Lower bounds for chain-of-thought reasoning in hard-attention transformers. In Forty-second International Conference on Machine Learning, External Links: Link Cited by: §4.2. [4] S. Bhattamishra, A. Patel, and N. Goyal (2020) On the computational power of transformers and its implications in sequence modeling. In Proceedings of the 24th Conference on Computational Natural Language Learning, R. Fernández and T. Linzen (Eds.), Online, p. 455–475. External Links: Link, Document Cited by: 5th item. [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), p. 2631–2653. External Links: Link Cited by: §2.2, §2.2. [6] D. Chiang, P. Cholak, and A. Pillay (2023) Tighter bounds on the expressivity of transformer encoders. In Proceedings 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, p. 5544–5562. External Links: Link Cited by: §3.3, 2nd item. [7] D. Chiang (2025) Transformers in uniform TC0^0. Transactions on Machine Learning Research. Note: External Links: ISSN 2835-8856, Link Cited by: §3.3, 3rd item. [8] M. L. Furst, J. B. Saxe, and M. Sipser (1984) Parity, circuits, and the polynomial-time hierarchy. Math. Syst. Theory 17 (1), p. 13–27. External Links: Link, Document Cited by: §3.2. [9] M. Hahn (2020) Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics 8, p. 156–171. External Links: Link, Document Cited by: §2.2. [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 Linguistics 10, p. 800–810. External Links: Link, Document Cited by: §2.2, 1st item, §4.1. [11] A. Holtzman, J. Buys, L. Du, M. Forbes, and Y. Choi (2020) The curious case of neural text degeneration. In International Conference on Learning Representations, External Links: Link Cited by: footnote 1. [12] N. Immerman (1999) Descriptive complexity. Graduate texts in computer science, Springer. External Links: Link, Document, ISBN 978-1-4612-6809-3 Cited by: §3.3. [13] H. Jiang, M. Hahn, G. Zetzsche, and A. W. Lin (2026) Softmax transformers are Turing-complete. In The Fourteenth International Conference on Learning Representations, External Links: Link Cited by: 6th item. [14] Z. Li, H. Liu, D. Zhou, and T. Ma (2024) Chain of thought empowers transformers to solve inherently serial problems. In International Conference on Learning Representations, B. Kim, Y. Yue, S. Chaudhuri, K. Fragkiadaki, M. Khan, and Y. Sun (Eds.), Vol. 2024, p. 11911–11943. External Links: Link Cited by: §2.2, 2nd item, 1st item, 2nd item, §4.1, §4. [15] E. Malach (2024) Auto-regressive next-token predictors are universal learners. In Forty-first International Conference on Machine Learning, External Links: Link Cited by: 5th item. [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. In Proceedings 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, p. 1766–1781. External Links: Link, Document Cited by: §2.2. [17] W. Merrill, A. Sabharwal, and N. A. Smith (2022) Saturated transformers are constant-depth threshold circuits. Transactions of the Association for Computational Linguistics 10, p. 843–856. External Links: Link, Document Cited by: §2.2, 2nd item. [18] W. Merrill and A. Sabharwal (2023) A logic for expressing log-precision transformers. In Advances in Neural Information Processing Systems, A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (Eds.), Vol. 36, p. 52453–52463. External Links: Link Cited by: §4. [19] W. Merrill and A. Sabharwal (2023) The parallelism tradeoff: limitations of log-precision transformers. Transactions of the Association for Computational Linguistics 11, p. 531–545. External Links: Link, Document Cited by: 3rd item. [20] W. Merrill and A. Sabharwal (2024) The expressive power of transformers with chain of thought. In International Conference on Learning Representations, B. Kim, Y. Yue, S. Chaudhuri, K. Fragkiadaki, M. Khan, and Y. Sun (Eds.), Vol. 2024, p. 7690–7706. External Links: Link Cited by: §2.2, 2nd item, 3rd item, 4th item, item 1. [21] W. Merrill (2023) Formal languages and the NLP black box. In Developments in Language Theory: 27th International Conference, DLT 2023, Umeå, Sweden, June 12–16, 2023, Proceedings, Berlin, Heidelberg, p. 1–8. External Links: ISBN 978-3-031-33263-0, Link, Document Cited by: §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-4435 Cited by: §2.2, 5th item. [23] R. Qiu, Z. Xu, W. Bao, and H. Tong (2025) Ask, and it shall be given: on the Turing completeness of prompting. In International Conference on Learning Representations, Y. Yue, A. Garg, N. Peng, F. Sha, and R. Yu (Eds.), Vol. 2025, p. 6286–6309. External Links: Link Cited by: 5th item. [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 Linguistics 12, p. 543–561. External Links: Link, Document Cited by: §1. [25] L. Strobl (2023) Average-hard attention transformers are constant-depth uniform threshold circuits. External Links: 2308.03212, Link Cited by: 3rd item. [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. In Advances in Neural Information Processing Systems, I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30, p. . External Links: Link Cited by: §2.2. [27] A. Yang, D. Chiang, and D. Angluin (2024) Masked hard-attention transformers recognize exactly the star-free languages. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, External Links: Link Cited by: §4.1. [28] A. Yang, L. Strobl, D. Chiang, and D. Angluin (2025) Simulating hard attention using soft attention. External Links: 2412.09925, Link Cited by: §2.3. [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 Cited by: §1, §2.3.