Transformer Expressivity

Follow this topic Ask about this topic

Transformer expressivity asks which functions, sequence rules, and algorithms a Transformer can compute or approximate, and what resources that requires. Researchers use circuit complexity, automata and temporal logic, approximation theory, and VC-dimension bounds to compare architectures and design choices such as depth, attention patterns, positional encodings, and numerical precision. These analyses cover capabilities including parity, retrieval, arithmetic, symbolic computation, and approximation of continuous targets. A central tension is that formal universality may rely on growing context or precision and special mechanisms, while fixed practical models can face limits in learnability, efficiency, and generalization to longer inputs.

Latest papers

54 papers7 papers in the last four weeks, up 40% on the four weeks before. 0.0% of all new papers.

Putting Transformer Theories to the Test
Oct 23, 2026Awni Altabaa, Tobias Schnabel, Kiran TomlinsonTransformer Transformer Expressivity
Yale University · Microsoft Research
Copying Under Repetition: From Prefix Matching to Position Hashing
Oct 19, 2026Anxin Guo, Tianlong Huang, Chenxiao Yang +1Transformer Repetition in Language Generation
Northwestern University · Duke University · Toyota Technological Institute at Chicago
Formally Verified Autoresearch for Analyzing the Expressivity of Multi-Head Attention
Oct 18, 2026Karthik Viswanathan, Plamen Dimitrov, Stefano Rocca +1Transformer Expressivity Multi-Head Attention
Verified Mechanisms · MATS Research · University of California, Berkeley
Learning When to Abort in Transformer Planning: A Mechanistic Study
Oct 18, 2026Shi Feng, Qimin Zhong, Siwei Wang +4Language Model Error Detection Transformer Interpretability
Harvard University · Shenzhen University · Microsoft Research Asia +1
Exact-Solution Volume and Length Generalization in Transformers
Oct 6, 2026Yijia Jessica Zhu, David ChiangTransformer Expressivity Transformer
University of Notre Dame
Quasi Linear Kernel Attention with Infinite Capacity
Sep 28, 2026Nicolaj Rux, Johannes Hertrich, Sebastian NeumayerTransformer Expressivity Attention Mechanisms
Faculty of Mathematics, Chemnitz University of Technology, 09126 Chemnitz, Germany · Institute of Computer Science, University of Göttingen, 37073 Göttingen, Germany
Universality and Generalization of Causal Transformers Across Context Lengths
Sep 28, 2026Takashi Furuya, Maarten V. de Hoop, Gabriel PeyréNeural Network Generalization Transformer Expressivity
Doshisha University, RIKEN AIP · Rice University · CNRS, ENS, PSL Université
VC Dimension and Expressivity of Real-Valued Transformers
Sep 25, 2026Gavin Dooley, Andy Yang, Yijia Jessica Zhu +3VC Dimension Transformer Expressivity
University of Notre Dame
Latest Exact Match Attention
Sep 22, 2026Moritz BrösamleTransformer Expressivity Memory-Augmented Language Models
Department of Mathematics, University of Tübingen, Germany
Transformer Heads Looking for Order
Sep 22, 2026Jasper van Doornmalen, Alexander Kozachinskiy, Corinna Mathwieser +4Transformer Expressivity Multi-Head Attention
IMC UC · CENIA · Centre for Credible AI +1
Length Generalization for Transformers via Compression
Sep 8, 2026Georg Zetzsche, Hongjian Jiang, Andy Yang +4Transformer Expressivity Transformer
Max Planck Institute for Software Systems (MPI-SWS) · RPTU Kaiserslautern-Landau · University of Notre Dame
Universal Transformers for Circuit Computations: Perfect Length Generalization in Tiny Transformers
Aug 31, 2026Takuya Ito, Ruchir Puri, Murray Campbell +1Transformer Expressivity Length Generalization
IBM Research
Gated Recurrent Transformers: Expressive Depth through Recurrent Modulation
Aug 15, 2026Amr Hegazy, Amr Alanwar, Mostafa ElhoushiRecurrent Transformers Transformer Expressivity
The German University in Cairo · Technical University of Munich · Cerebras Systems Inc.
On the Expressive Power of Transformers
Aug 13, 2026Phokion Kolaitis, Rik SenguptaTransformer Expressivity Circuit Complexity
University of California Santa Cruz Santa Cruz, CA · IBM Research Cambridge, MA
Disentangling the Expressivity of RoPE
Aug 12, 2026Selim Jerad, Anej Svete, Jiaoda Li +1Rotary Positional Embeddings Transformer Expressivity
Toyota Technological Institute at Chicago · ETH Zürich
Training-Free Universal Approximation by Prompting Random Transformers
Aug 10, 2026Alexander Hsu, Rongjie LaiTransformer Expressivity Prompt Learning
Department of Mathematics, Purdue University
Transcript-Managed Transformers: Monotone Multi-Agent Collapse and Universality with Two Pop-Enabled Transcripts
Jul 31, 2026Sergey SalishevTransformer Expressivity Transformer
AI Foundry San Francisco, CA, USA
A Compositional Theory of Causally Masked Transformers
Jul 29, 2026Franz Nowak, Ryan Cotterell, Reda BoumasmoudTransformer Expressivity Transformer
1ETH Zürich
The Entropic Bound for Transformers: Why Static Rank Fails and Attention-Native Rank Recovers
Jul 25, 2026Byeong Hoon YoonSoftmax Attention Transformer Expressivity
Independent Researcher
On the Computational Complexity of Structural Generalization
Jul 21, 2026Zichao WeiTransformer Expressivity Compositional Generalization
Department of Language Science and Technology Saarland University Saarbrücken, Germany
Exploring the Cryptographic Limits of Transformer Networks
Jun 28, 2026Stefan Domunco, Andis Draguns, Philip Torr +2Transformer Expressivity Circuit Complexity
University of Oxford · Contramont Research
An expressivity analysis of hierarchical modelling in deep transformers via bounded-depth grammars
Jun 16, 2026Vinoth Nandakumar, Qiang Qu, Pramod Thebe +2Transformer Expressivity Hierarchical Representation Learning
University of Sydney · San Francisco State University · IIT Madras
A theoretical model for task routing in mixture-of-expert transformers
Jun 12, 2026Vinoth Nandakumar, Yongli Xiang, Yunzhi Yao +2Transformer Expressivity Mixture of Experts
University of Sydney · Zhejiang University · Google Research
How Linear Is a Transformer Feed-Forward Block? Per-Block Linear Recoverability Is Learned, Not Architectural
Jun 12, 2026Stuart WhippTransformer FFNs Transformer Expressivity
Independent Research
Tight Sample Complexity of Transformers
Jun 8, 2026Chenxiao Yang, Nathan Srebro, Zhiyuan LiTransformer Expressivity Transformer
Toyota Technological Institute at Chicago (TTIC)
Understanding the Parameter Space Geometry of Transformers Encoding Boolean Functions
Jun 7, 2026Blanka Köver, Alexandra Butoi, Anej Svete +2Transformer Expressivity Boolean Function Learning
Department of Mathematics, ETH Zürich, Zürich, Switzerland · Department of Computer Science, ETH Zürich, Zürich, Switzerland · Department of Language Science and Technology, Saarland University, Saarbrücken, Germany.
Representational Capacity: Geometric Limits on Feature Representation in Transformer Language Models
Jun 1, 2026Alexander GuhaFeature Superposition Transformer Expressivity
Arizona State University
Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
Jun 1, 2026Qian Li, Xinyu Mao, Shang-Hua TengTransformer Expressivity Transformer
Shenzhen Research Institute of Big Data · University of Southern California
Fixed Universal Transformers
May 29, 2026Jingwen Liu, Alexandr Andoni, Daniel HsuTransformer Expressivity Transformer
Columbia University New York, NY
Trading Complexity for Expressivity Through Structured Generalized Linear Token Mixing
May 29, 2026Erwan Fagnou, Paul Caillon, Blaise Delattre +1Transformer Expressivity Autoregressive Language Modeling
Miles Team, LAMSADE, Université Paris Dauphine-PSL, Paris, France · Department of Computer Science, School of Computing, Institute of Science Tokyo, Tokyo, Japan · ESPCI PSL, Paris, France

Oct 23, 2026J/K move · Enter open · S save

Putting Transformer Theories to the Test

Awni Altabaa, Tobias Schnabel, Kiran Tomlinson

Yale University · Microsoft Research

Transformer Transformer Expressivity

Open paper AskPDF arXiv

Several formal theories have been developed to characterize the capabilities and limitations of the transformer architecture, each employing different abstractions that capture different features of the architecture. Due to the differences in their underlying assumptions and conceptual frameworks, these theories can disagree in their predictions about what tasks transformers find easy or hard. We map out seven theories of transformer capability (Star-free,

\mathsf{AC}^0

\mathsf{TC}^0

, C-RASP, MPC, BAPO, and Sensitivity) and translate their results into a common matrix of predictions across a suite of tasks covering different computational structures. We provide new theoretical results to complete this matrix. We then evaluate theoretical predictions through controlled experiments measuring in-distribution sample complexity, length generalization, and pretrained language model performance. We find that no single theory explains the observed pattern of successes and failures. When a theory does not capture the transformer behaviors relevant to a task, its predictions break down; for instance, we show that the

k

-hop induction task is predicted hard by C-RASP because it does not model content-dependent attention, but we train small transformers on this task that length-generalize. Similarly, theories assuming hard attention like

\mathsf{AC}^0

and BAPO predict binary majority to be hard, for which we also find success in practice. Together, our results point to several specific features that a theory of transformers must capture: soft rather than hard attention, dynamic content-dependent retrieval, bounded computation at each position, an account of learnability and inductive biases, and a combination of upper and lower bounds.