Transformer Expressivity

Follow this topic Ask about this topic

Momentum

5 papers in the last four weeks, up 25% on the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 39

All topics

Position: The Turing-Completeness of Autoregressive Transformers Relies Heavily on Context Management
May 19, 2026Guanyu Cui, Zhewei Wei, Kun HeTransformer Expressivity Transformer
Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China · DEKE Lab, Renmin University of China, Beijing, China
The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought
May 18, 2026Moritz Brösamle, Stephan EcksteinTransformer Expressivity Transformer
Department of Mathematics, University of Tübingen, Germany.
InfoFlow: A Framework for Multi-Layer Transformer Analysis
May 18, 2026Penghao Yu, Haotian Jiang, Zeyu Bao +1Transformer Expressivity Transformer
Department of Mathematics National University of Singapore · Institute for Functional Intelligent Materials National University of Singapore · National University of Singapore +1
Lower bounds for one-layer transformers that compute parity
May 12, 2026Daniel HsuTransformer Expressivity Self-Attention
Encoder-Decoder Transformers: Logical Characterizations and Periodicity
May 8, 2026Veeti Ahvonen, Damian Heiman, Antti Kuusisto +2Transformer Expressivity Transformer
Mathematics Research Centre, Tampere University, Tampere, Finland
Average Attention Transformers and Arithmetic Circuits
May 6, 2026Lena Ehrmuth, Laura StriekerTransformer Expressivity Transformer
Institute for Theoretical Computer Science, Leibniz University Hanover, Hanover, Germany
Characterizing the Expressivity of Local Attention in Transformers
May 1, 2026Jiaoda Li, Ryan CotterellTransformer Expressivity Transformer
Barriers to Universal Reasoning With Transformers (And How to Overcome Them)
Apr 28, 2026Oliver Kraus, Yash Sarrof, Yuekun Yao +2Transformer Expressivity CoT Reasoning
1Saarland University · 2Ohio State University
Expressivity of Transformers: A Tropical Geometry Perspective
Apr 16, 2026Ye Su, Yong LiuTransformer Expressivity Transformer
Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen 518055, China · University of Chinese Academy of Sciences, Beijing 101407, China · Gaoling School of Artificial Intelligence, Renmin University of China, Beijing 100872, China

May 19, 2026, cs.AIJ/K move · Enter open · S save

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

Guanyu Cui, Zhewei Wei, Kun He

Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China · DEKE Lab, Renmin University of China, Beijing, China

Transformer Expressivity Transformer LLM Context Management

Open paper AskPDF arXiv

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

Momentum

Related topics

Latest papers 39