Everything K-culture — comebacks to K-beauty, straight to your inboxGet it in your inbox

METAL MEDIA

On the Expressive Power of Transformers

arXiv:2608.126712026-08-14

A survey measuring exactly how powerful transformers are, using circuit theory as the ruler

This is a survey paper that maps out what transformers, the core building block behind nearly all of today's LLMs, can and cannot compute, using circuit complexity as the yardstick. It formalizes transformers as language recognizers and shows how choices like attention type and numerical precision determine which circuit classes they land in. It also shows that chain-of-thought reasoning can push transformers far beyond these limits, up to simulating arbitrary Turing machines.

METAL MEDIA explanatory visual

A survey measuring exactly how powerful transformers are, using circuit theory as the ruler

  1. 01The paper formally defines transformers as language recognizers, distinguishing encoders (which output accept/reject) from decoders (which generate tokens one at a time, autoregressively).
  2. 02Instead of classical automata theory or the Chomsky hierarchy, the survey uses circuit complexity, because transformers compute in parallel, fixed-depth layers, which maps naturally onto Boolean/threshold circuits rather than sequential state machines.
  3. 03It compiles known results showing that whether attention is 'hard' or softmax, and how many bits of precision are used, determines whether a transformer's power stays within AC0 or reaches the larger class TC0.
  4. 04Without chain-of-thought, transformer expressivity is largely bounded within TC0; but with chain-of-thought of increasing length, transformers can reach LOGSPACE, PTIME, and with unbounded chain-of-thought, simulate arbitrary Turing machines.
  5. 05The paper itself doesn't introduce new proofs but organizes and connects existing results from the field into a coherent overview.
An explanatory diagram made by METAL MEDIA, not a figure supplied by the paper's authors.

What they did

  1. The paper formally defines transformers as language recognizers, distinguishing encoders (which output accept/reject) from decoders (which generate tokens one at a time, autoregressively).
  2. Instead of classical automata theory or the Chomsky hierarchy, the survey uses circuit complexity, because transformers compute in parallel, fixed-depth layers, which maps naturally onto Boolean/threshold circuits rather than sequential state machines.
  3. It compiles known results showing that whether attention is 'hard' or softmax, and how many bits of precision are used, determines whether a transformer's power stays within AC0 or reaches the larger class TC0.
  4. Without chain-of-thought, transformer expressivity is largely bounded within TC0; but with chain-of-thought of increasing length, transformers can reach LOGSPACE, PTIME, and with unbounded chain-of-thought, simulate arbitrary Turing machines.
  5. The paper itself doesn't introduce new proofs but organizes and connects existing results from the field into a coherent overview.
Figure 1: A high-level view of the encoder architecture.
Figure 1: A high-level view of the encoder architecture.
𝐲i=𝐖(O)​(∑j=1nαi,j​𝐯j),𝐯j=𝐖(V)​𝐱j,αi,∗=𝒮⁡(si,∗),(1)
si,j=𝐪i⊤​𝐤jdkey,𝐪i=𝐖(Q)​𝐱i,𝐤j=𝐖(K)​𝐱j.(2)
Figure 2: An encoder (left) and a decoder (right).
Figure 2: An encoder (left) and a decoder (right).
(𝐲1(ℓ),…,𝐲n(ℓ)):=∑h=1H𝗌𝖺(h,ℓ)​(𝐱1(ℓ−1),…,𝐱n(ℓ−1))+(𝐱1(ℓ−1),…,𝐱n(ℓ−1)),
(𝐱1(ℓ),…,𝐱n(ℓ)):=(𝖿𝖿(ℓ)​(𝐲1(ℓ)),…,𝖿𝖿(ℓ)​(𝐲n(ℓ)))+(𝐲1(ℓ),…,𝐲n(ℓ)).
F𝒯0​(w):=w
F𝒯i​(w):=F𝒯i−1​(w)⋅F𝒯​(F𝒯i−1​(w))​ for ​i≥1,

Why it matters

Understanding these computational limits clarifies why LLMs succeed at some tasks and fundamentally struggle at others, which matters for setting realistic expectations about model capabilities. It also highlights that chain-of-thought is not just a prompting trick but can genuinely expand a model's computational power in a formal sense.

Terms in this paper

  • circuit complexity · the study of how efficiently logic circuits built from gates like AND/OR/NOT can solve computational problems
  • AC0 / TC0 · classes of problems solvable by constant-depth logic circuits; TC0 additionally allows majority-vote gates, making it more powerful than AC0
  • hard attention / softmax attention · hard attention only looks at the highest-scoring position(s), while softmax attention (used in real LLMs) assigns weighted probabilities across all positions
  • precision · the number of bits used for internal computations; low precision limits expressivity, while logarithmic precision enables operations like addition
  • chain-of-thought (CoT) · a method where the model generates intermediate reasoning tokens and feeds them back as input before producing a final answer

Original abstract (English)

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.

Authors · Phokion Kolaitis, Rik Sengupta

Read on arXiv

Latest papers

All papers →

Latest from METAL MEDIA

Figures: Phokion Kolaitis et al., arXiv:2608.12671, CC BY 4.0