Fetching the paper…
Reading the bibliography…
We show that a constant number of self-attention layers can efficiently simulate, and be simulated by, a constant number of communication rounds of Massively Parallel Computation.
Communication complexity
Christos H. Papadimitriou and Michael Sipser · 1982
Earlier work this paper cites.
Lower bounds on communication complexity
Pavol Duris, Zvi Galil, and Georg Schnitger · 1984
Earlier work this paper cites.
Rounds in communication complexity revisited
Noam Nisan and Avi Wigderson · 1993
Earlier work this paper cites.
Learning long-term dependencies with gradient descent is difficult
Y. Bengio, P. Simard, and P. Frasconi · 1994
Earlier work this paper cites.
Mapreduce: Simplified data processing on large clusters
Jeffrey Dean and Sanjay Ghemawat · 2004
Earlier work this paper cites.
Stream order and order statistics: Quantile estimation in random-order streams
Sudipto Guha and Andrew McGregor · 2009
Earlier work this paper cites.
A model of computation for mapreduce
Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii · 2010
Earlier work this paper cites.
Sorting, searching, and simulation in the mapreduce framework
Michael T Goodrich, Nodari Sitchinava, and Qin Zhang · 2011
Earlier work this paper cites.
A reliable effective terascale linear learning system
Alekh Agarwal, Olivier Chapelle, Miroslav Dudík, and John Langford · 2014
Earlier work this paper cites.
Parallel algorithms for geometric graph problems
Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev · 2014
Earlier work this paper cites.
Empirical evaluation of gated recurrent neural networks on sequence modeling
Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio · 2014
Earlier work this paper cites.
Adam: A method for stochastic optimization, 2014
Diederik P. Kingma and Jimmy Ba · 2014
Earlier work this paper cites.
The power of depth for feedforward neural networks
Ronen Eldan and Ohad Shamir · 2016
Earlier work this paper cites.
Benefits of depth in neural networks
Matus Telgarsky · 2016
Earlier work this paper cites.
Communication steps for parallel query processing
Paul Beame, Paraschos Koutris, and Dan Suciu · 2017
Earlier work this paper cites.
Depth separation for neural networks
Amit Daniely · 2017
Earlier work this paper cites.
Attention is all you need
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin · 2017
Earlier work this paper cites.
Parallel graph connectivity in log diameter rounds
Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, and Peilin Zhong · 2018
Earlier work this paper cites.
Shuffles and circuits (on lower bounds for modern parallel computation)
Tim Roughgarden, Sergei Vassilvitskii, and Joshua Wang · 2018
Earlier work this paper cites.
Massively parallel computation of matching and mis in sparse graphs
Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M Karp, and Jara Uitto · 2019
Earlier work this paper cites.
What does bert look at? an analysis of bert’s attention
Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher D Manning · 2019
Earlier work this paper cites.
Conditional hardness results for massively parallel computation from distributed lower bounds
Mohsen Ghaffari, Fabian Kuhn, and Jara Uitto · 2019
Cited alongside, same era.
What graph neural networks cannot learn: depth vs width
Andreas Loukas · 2019
Cited alongside, same era.
Language models are unsupervised multitask learners
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever · 2019
Cited alongside, same era.
Longformer: The long-document transformer, 2020
Iz Beltagy, Matthew E. Peters, and Arman Cohan · 2020
Cited alongside, same era.
On the ability and limitations of transformers to recognize formal languages
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal · 2020
Cited alongside, same era.
New lower bounds for massively parallel computation from query complexity, 2020
Llm.int8(): 8-bit matrix multiplication for transformers at scale
Tim Dettmers, Mike Lewis, Younes Belkada, and Luke Zettlemoyer · 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
Later among the works it cites.
Pure transformers are powerful graph learners, 2022
Jinwoo Kim, Tien Dat Nguyen, Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Seunghoon Hong · 2022
Later among the works it cites.
Systematic generalization and emergent structures in transformers trained on structured tasks, 2022
Yuxuan Li and James L. McClelland · 2022
Later among the works it cites.
Transformers learn shortcuts to automata, 2022
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang · 2022
Later among the works it cites.
A logic for expressing log-precision transformers, 2022
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Moses Charikar, Weiyun Ma, and Li-Yang Tan · 2020
Cited alongside, same era.
Theoretical limitations of self-attention in neural sequence models
Michael Hahn · 2020
Cited alongside, same era.
Are transformers universal approximators of sequence-to-sequence functions?
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar · 2020
Cited alongside, same era.
Graph streaming lower bounds for parameter estimation and property testing via a streaming xor lemma
Sepehr Assadi and Vishvajeet N · 2021
Cited alongside, same era.
A mathematical framework for transformer circuits
Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova DasSarma, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds, Danny Hernandez, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah · 2021
Cited alongside, same era.
Highly accurate protein structure prediction with alphafold
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Žídek, Anna Potapenko, et al · 2021
Cited alongside, same era.
On the expressive power of self-attention matrices
Valerii Likhosherstov, Krzysztof Choromanski, and Adrian Weller · 2021
Cited alongside, same era.
William Merrill and Ashish Sabharwal · 2022
Later among the works it cites.
Saturated transformers are constant-depth threshold circuits
William Merrill, Ashish Sabharwal, and Noah A. Smith · 2022
Later among the works it cites.
Quantformer: Learning extremely low-precision vision transformers
Ziwei Wang, Changyuan Wang, Xiuwei Xu, Jie Zhou, and Jiwen Lu · 2022
Later among the works it cites.
Masked hard-attention transformers and boolean rasp recognize exactly the star-free languages, 2023
Dana Angluin, David Chiang, and Andy Yang · 2023
Later among the works it cites.
Birth of a transformer: A memory viewpoint, 2023
Alberto Bietti, Vivien Cabannes, Diane Bouchacourt, Herve Jegou, and Leon Bottou · 2023
Later among the works it cites.
Mamba: Linear-time sequence modeling with selective state spaces, 2023
Albert Gu and Tri Dao · 2023
Later among the works it cites.
Massively parallel computation: Algorithms and applications
Sungjin Im, Ravi Kumar, Silvio Lattanzi, Benjamin Moseley, Sergei Vassilvitskii, et al · 2023
Later among the works it cites.
Polysketchformer: Fast transformers via sketches for polynomial kernels, 2023
Praneeth Kacham, Vahab Mirrokni, and Peilin Zhong · 2023
Later among the works it cites.
Auto-regressive next-token predictors are universal learners, 2023
Eran Malach · 2023
Later among the works it cites.
Mpi allreduce, 2023
MPICH · 2023
Later among the works it cites.
Representational strengths and limitations of transformers, 2023
Clayton Sanford, Daniel Hsu, and Matus Telgarsky · 2023
Later among the works it cites.
Average-hard attention transformers are constant-depth uniform threshold circuits, 2023
Lena Strobl · 2023
Later among the works it cites.
Transformers as recognizers of formal languages: A survey on expressivity, 2023
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin · 2023
Later among the works it cites.
Unveiling transformers with lego: a synthetic reasoning task, 2023
Yi Zhang, Arturs Backurs, Sébastien Bubeck, Ronen Eldan, Suriya Gunasekar, and Tal Wagner · 2023
Later among the works it cites.
Transformers are multi-state rnns, 2024
Matanel Oren, Michael Hassid, Yossi Adi, and Roy Schwartz · 2024
Closest in time.