2023

What Formal Languages Can Transformers Express? A Survey

Strobl, Lena, Merrill, William, Weiss, Gail et al.

Understand

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.

Built on

Language models are few-shot learners
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020 · 1901
Earlier work this paper cites.
The algebraic theory of context-free languages
N. Chomsky and M. P. Schützenberger. 1963 · 1963
Earlier work this paper cites.
Counter machines and counter languages
Patrick C. Fischer, Albert R. Meyer, and Arnold L. Rosenberg. 1968 · 1968
Earlier work this paper cites.
Tense Logic and the Theory of Linear Order
Johan Anthony Willem Kamp. 1968 · 1968
Earlier work this paper cites.
Counter-Free Automata
Robert McNaughton and Seymour A. Papert. 1971 · 1971
Earlier work this paper cites.
On tape-bounded complexity classes and multihead finite automata
I. H. Sudborough. 1975 · 1975
Earlier work this paper cites.
Complete problems for deterministic polynomial time
Neil D. Jones and William T. Laaser. 1976 · 1976
Earlier work this paper cites.
Constant depth reducibility
Ashok K. Chandra, Larry Stockmeyer, and Uzi Vishkin. 1984 · 1984
Earlier work this paper cites.
Parity, circuits, and the polynomial-time hierarchy
Merrick Furst, James B. Saxe, and Michael Sipser. 1984 · 1984
Earlier work this paper cites.
The Boolean formula value problem is in ALOGTIME
Samuel R. Buss. 1987 · 1987
Earlier work this paper cites.
Problems complete for deterministic logarithmic space
Stephen A. Cook and Pierre McKenzie. 1987 · 1987
Earlier work this paper cites.
Bounded-width polynomial-size branching programs recognize exactly those languages in 𝑁𝐶 1 \mathit{NC^{1}}
David A. Barrington. 1989 · 1989
Earlier work this paper cites.
Approximation by superpositions of a sigmoidal function
G. Cybenko. 1989 · 1989
Earlier work this paper cites.
Multilayer feedforward networks are universal approximators
Kurt Hornik, Maxwell B. Stinchcombe, and Halbert White. 1989 · 1989
Earlier work this paper cites.
On uniformity within 𝑁𝐶 1 \mathit{NC^{1}}
David A. Mix Barrington, Neil Immerman, and Howard Straubing. 1990 · 1990
Earlier work this paper cites.
Regular languages in 𝑁𝐶 1 \mathit{NC^{1}}
David A. Barrington, Kevin Compton, Howard Straubing, and Denis Thérien. 1992 · 1992
Earlier work this paper cites.
Time, hardware, and uniformity
David Mix Barrington and Neil Immerman. 1994 · 1994
Earlier work this paper cites.
Circuit Complexity and Neural Networks
Ian Parberry. 1994 · 1994
Earlier work this paper cites.
Analog computation via neural networks
Hava T. Siegelmann and Eduardo D. Sontag. 1994 · 1994
Earlier work this paper cites.
Finite Automata, Formal Logic, and Circuit Complexity
Howard Straubing. 1994 · 1994
Earlier work this paper cites.
Limits to Parallel Computation: P-Completeness Theory
Raymond Greenlaw, H. James Hoover, and Walter L. Ruzzo. 1995 · 1995
Earlier work this paper cites.
On the computational power of neural nets
Hava T. Siegelmann and Eduardo D. Sontag. 1995 · 1995
Earlier work this paper cites.
Discrete Neural Computation
Kai-Yeung Siu, Vwani Roychowdhury, and Thomas Kailath. 1995 · 1995
Earlier work this paper cites.
On the circuit complexity of sigmoid feedforward neural networks
Valeriu Beiu and John G. Taylor. 1996 · 1996
Earlier work this paper cites.
Languages that capture complexity classes
Neil Immerman. 1997 · 1997
Earlier work this paper cites.
Languages, automata, and logic
Wolfgang Thomas. 1997 · 1997
Earlier work this paper cites.
The permanent requires large uniform threshold circuits
Eric Allender. 1999 · 1999
Earlier work this paper cites.
Descriptive Complexity
Neil Immerman. 1999 · 1999
Earlier work this paper cites.

Similar

Division is in uniform TC 0
William Hesse. 2001 · 2001
Cited alongside, same era.
General-purpose computation with neural networks: A survey of complexity theoretic results
Jiří Šíma and Pekka Orponen. 2003 · 2003
Cited alongside, same era.
On the linguistic capacity of real-time counter automata
Original
William Merrill. 2020 · 2004
Cited alongside, same era.
First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
David A. Mix Barrington, Neil Immerman, Clemens Lautemann, Nicole Schweikardt, and Denis Thérien. 2005 · 2005
Cited alongside, same era.
A survey of neural networks and formal languages
Original
Joshua Ackerman and George Cybenko. 2020 · 2006
Cited alongside, same era.
Undirected connectivity in log-space
Omer Reingold. 2008 · 2008
Cited alongside, same era.
Computational Complexity: A Modern Approach
Sanjeev Arora and Boaz Barak. 2009 · 2009
Cited alongside, same era.
RNNs can generate bounded hierarchical languages with optimal memory
John Hewitt, Michael Hahn, Surya Ganguli, Percy Liang, and Christopher D. Manning. 2020 · 2010
Cited alongside, same era.
Introduction to the Theory of Computation , 3rd edition
Michael Sipser. 2013 · 2013
Cited alongside, same era.
Neural machine translation by jointly learning to align and translate
Original
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015 · 2015
Cited alongside, same era.
Layer normalization
Original
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. 2016 · 2016
Cited alongside, same era.
Gaussian error linear units (GELUs)
Original
Dan Hendrycks and Kevin Gimpel. 2016 · 2016
Cited alongside, same era.

Then

Attention is Turing-complete
Jorge Pérez, Pablo Barceló, and Javier Marinkovic. 2021 · 2021
Later among the works it cites.
Thinking like Transformers
Gail Weiss, Yoav Goldberg, and Eran Yahav. 2021 · 2021
Later among the works it cites.
Self-attention networks can process bounded hierarchical languages
Shunyu Yao, Binghui Peng, Christos Papadimitriou, and Karthik Narasimhan. 2021 · 2021
Later among the works it cites.
Overcoming a theoretical limitation of self-attention
David Chiang and Peter Cholak. 2022 · 2022
Later among the works it cites.
Formal language recognition by hard attention Transformers: Perspectives from circuit complexity
Yiding Hao, Dana Angluin, and Robert Frank. 2022 · 2022
Later among the works it cites.
The annotated Transformer
Austin Huang, Suraj Subramanian, Jonathan Sum, Khalid Almubarak, and Stella Biderman. 2022 · 2022
Later among the works it cites.
A survey of transformers
Tianyang Lin, Yuxin Wang, Xiangyang Liu, and Xipeng Qiu. 2022 · 2022
Later among the works it cites.
Saturated transformers are constant-depth threshold circuits
William Merrill, Ashish Sabharwal, and Noah A. Smith. 2022 · 2022
Later among the works it cites.
Show your work: Scratchpads for intermediate computation with language models
Maxwell Nye, Anders Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena. 2022 · 2022
Later among the works it cites.
On learning interpreted languages with recurrent models
Denis Paperno. 2022 · 2022
Later among the works it cites.
Formal algorithms for transformers
Original
Mary Phuong and Marcus Hutter. 2022 · 2022
Later among the works it cites.
Physics of language models: Part 1, context-free grammar
Original
Zeyuan Allen-Zhu and Yuanzhi Li. 2023 · 2023
Closest in time.
Masked hard-attention transformers and Boolean RASP recognize exactly the star-free languages
Original
Dana Angluin, David Chiang, and Andy Yang. 2023 · 2023
Closest in time.
Simplicity bias in Transformers and their ability to learn sparse Boolean functions
Satwik Bhattamishra, Arkil Patel, Varun Kanade, and Phil Blunsom. 2023 · 2023
Closest in time.
Tighter bounds on the expressivity of transformer encoders
David Chiang, Peter Cholak, and Anand Pillay. 2023 · 2023
Closest in time.
Neural networks and the Chomsky hierarchy
Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A. Ortega. 2023 · 2023
Closest in time.
Towards revealing the mystery behind Chain of Thought: A theoretical perspective
Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. 2023 · 2023
Closest in time.
Learning Transformer programs
Dan Friedman, Alexander Wettig, and Danqi Chen. 2023 · 2023
Closest in time.
Entity tracking in language models
Najoung Kim and Sebastian Schuster. 2023 · 2023
Closest in time.
Tracr: Compiled transformers as a laboratory for interpretability
David Lindner, János Kramár, Matthew Rahtz, Thomas McGrath, and Vladimir Mikulik. 2023 · 2023
Closest in time.
Transformers learn shortcuts to automata
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. 2023 · 2023
Closest in time.
Formal languages and the NLP black box
William Merrill. 2023 · 2023
Closest in time.
GPT-4 technical report
Original
OpenAI. 2023 · 2023
Closest in time.
Representational strengths and limitations of transformers
Clayton Sanford, Daniel Hsu, and Matus Telgarsky. 2023 · 2023
Closest in time.
Average-hard attention transformers are constant-depth uniform threshold circuits
Original
Lena Strobl. 2023 · 2023
Closest in time.
Logical languages accepted by transformer encoders with hard attention
Pablo Barceló, Alexander Kozachinskiy, Anthony Widjaja Lin, and Vladimir Podolskii. 2024 · 2024
Closest in time.
The expressive power of transformers with chain of thought
William Merrill and Ashish Sabharwal. 2024 · 2024
Closest in time.
What algorithms can Transformers learn? A study in length generalization
Hattie Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Josh Susskind, Samy Bengio, and Preetum Nakkiran. 2024 · 2024
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…