Fetching the paper…
Reading the bibliography…
Recent theoretical work has identified surprisingly simple reasoning problems, such as checking if two nodes in a graph are connected or simulating finite-state machines, that are provably unsolvable by standard transformers that answer immediately after reading their input.
Classes of languages and linear-bounded automata
S-Y Kuroda · 1964
Earlier work this paper cites.
General context-free recognition in less than cubic time
Leslie G. Valiant · 1975
Earlier work this paper cites.
On time versus space
John E. Hopcroft, Wolfgang J. Paul, and Leslie G. Valiant · 1977
Earlier work this paper cites.
The complexity of graph connectivity
Avi Wigderson · 1992
Earlier work this paper cites.
Introduction to automata theory, languages, and computation
John E Hopcroft, Rajeev Motwani, and Jeffrey D Ullman · 2001
Earlier work this paper cites.
Fast context-free grammar parsing requires fast boolean matrix multiplication
Lillian Lee · 2002
Earlier work this paper cites.
On the practical computational power of finite precision RNNs for language recognition
Gail Weiss, Yoav Goldberg, and Eran Yahav · 2018
Earlier work this paper cites.
Root mean square layer normalization
Biao Zhang and Rico Sennrich · 2019
Earlier work this paper cites.
On the linguistic capacity of real-time counter automata
William Merrill · 2020
Earlier work this paper cites.
On layer normalization in the transformer architecture
Ruibin Xiong, Yunchang Yang, Di He, Kai Zheng, Shuxin Zheng, Chen Xing, Huishuai Zhang, Yanyan Lan, Liwei Wang, and Tie-Yan Liu · 2020
Earlier work this paper cites.
Effects of parameter norm growth during transformer training: Inductive bias from gradient descent
William Merrill, Vivek Ramanujan, Yoav Goldberg, Roy Schwartz, and Noah A. Smith · 2021
Cited alongside, same era.
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 · 2021
Cited alongside, same era.
Attention is Turing complete
Jorge Pérez, Pablo Barceló, and Javier Marinkovic · 2021
Cited alongside, same era.
Thinking like transformers
Gail Weiss, Yoav Goldberg, and Eran Yahav · 2021
Cited alongside, same era.
Self-attention networks can process bounded hierarchical languages
Shunyu Yao, Binghui Peng, Christos Papadimitriou, and Karthik Narasimhan · 2021
Cited alongside, same era.
Faith and fate: Limits of transformers on compositionality
Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jian, Bill Yuchen Lin, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D. Hwang, Soumya Sanyal, Sean Welleck, Xiang Ren, Allyson Ettinger, Zaïd Harchaoui, and Yejin Choi · 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
Closest in time.
Transformers learn shortcuts to automata
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang · 2023
Closest in time.
Auto-regressive next-token predictors are universal learners
Eran Malach · 2023
Closest in time.
Formal languages and neural models for learning on sequences
William Merrill · 2023
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Formal language recognition by hard attention transformers: Perspectives from circuit complexity
Sophie Hao, Dana Angluin, and Roberta Frank · 2022
Cited alongside, same era.
Saturated transformers are constant-depth threshold circuits
William Merrill, Ashish Sabharwal, and Noah A. Smith · 2022
Cited alongside, same era.
Chain of thought prompting elicits reasoning in large language models
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoc V Le, and Denny Zhou · 2022
Cited alongside, same era.
Tighter bounds on the expressivity of transformer encoders
David Chiang, Peter Cholak, and Anand Pillay · 2023
Cited alongside, same era.
A logic for expressing log-precision transformers
William Merrill and Ashish Sabharwal
Cited in the paper.
The parallelism tradeoff: Limitations of log-precision transformers
William Merrill and Ashish Sabharwal
Cited in the paper.
Dale Schuurmans · 2023
Closest in time.
How language model hallucinations can snowball
Muru Zhang, Ofir Press, William Merrill, Alisa Liu, and Noah A. Smith · 2023
Closest in time.
Personal communication, March 2024
David Chiang · 2024
Closest in time.
Transformers as recognizers of formal languages: A survey on expressivity
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin · 2024
Closest in time.