What Formal Languages Can Transformers Express? A Survey

2023/11/01 by Lena Strobl, William Merrill, Gail Weiss +3 · 2 voices · 6 citations
Computer Science · #Computer science #Electrical engineering #Natural Language Processing Techniques #Semantic Web and Ontologies #Topic Modeling #Transformer #cs.CL #cs.FL #cs.LG #cs.LO

paper · pdf · doi:10.1162/tacl_a_00663

arxiv published 2023/11/01 · openalex publication_date 2024/01/01 · arxiv updated 2024/09/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06

Abstract

Abstract As transformers have gained prominence in natural language processing, some researchers have investigated theoretically what problems they can and cannot solve, by treating problems as formal languages. Exploring such questions can help clarify the power of transformers relative to other models of computation, their fundamental capabilities and limits, and the impact of architectural choices. Work in this subarea has made considerable progress in recent years. Here, we undertake a comprehensive survey of this work, documenting the diverse assumptions that underlie different results and providing a unified framework for harmonizing seemingly contradictory findings.

Citations

• Languages that Capture Complexity Classes
• Problems complete for deterministic logarithmic space
• Undirected connectivity in log-space
• Parity, circuits, and the polynomial-time hierarchy
• On the Computational Power of Neural Nets
• Approximation by superpositions of a sigmoidal function
• Multilayer feedforward networks are universal approximators
• Gaussian Error Linear Units (GELUs)
• On the Turing Completeness of Modern Neural Network Architectures
• Theoretical Limitations of Self-Attention in Neural Sequence Models
• On the Linguistic Capacity of Real-Time Counter Automata
• A Survey of Neural Networks and Formal Languages
• Bounded-width polynomial-size branching programs recognize exactly those languages in NC1
• Neural Networks and the Chomsky Hierarchy
• Advances in Neural Information Processing Systems 32 (NeurIPS 2019)
• Physics of Language Models: Part 1, Learning Hierarchical Language Structures
• Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits
• Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages

Cited by

• An Algebraic View of the Expressivity of Recurrent Language Models
• Length Generalization Bounds for Transformers
• When Is Compositional Reasoning Learnable from Verifiable Rewards?
• On the Role of Computation in Reinforcement Learning
• Protoreasoning in Tiny Transformers
• Exploring Compositional Generalization (in COGS/ReCOGS_pos) by Transformers using Restricted Access Sequence Processing (RASP)

Discussions

• https://arxiv.org/abs/2311.00208 ) * Simulating Hard Attention using Soft Attention ( https://arxiv.org/abs/2412.09925 ) * Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages [bsky, 1 points, 0 comments]
• arxiv.org/abs/2311.00208 Chain of thought might get around this a little but that's assuming we have traces for all problems we want to solve. Reccurance through sheer inductive bias can solve proble [bsky, 0 points, 0 comments]

Related

• Why transformers are obviously good models of language
• The Role of Logic and Automata in Understanding Transformers
• On the Universality of Transformer Architectures; How Much Attention Is Enough?
• Formal Algorithms for Transformers
• A Comparative Study on Code Generation with Transformers