Fetching the paper…
Reading the bibliography…
Self-attention is at the heart of the popular Transformer architecture, yet suffers from quadratic time and memory complexity.
Codes correcteurs d’erreurs
Alexis Hocquenghem · 1959
Earlier work this paper cites.
On A class of error correcting binary group codes
R. C. Bose and Dwijendra K. Ray-Chaudhuri · 1960
Earlier work this paper cites.
I/o complexity: The red-blue pebble game
Jia-Wei Hong and Hsiang-Tsung Kung · 1981
Earlier work this paper cites.
The input/output complexity of sorting and related problems
Alok Aggarwal and Jeffrey Scott Vitter · 1988
Earlier work this paper cites.
On showing lower bounds for external-memory computational geometry problems
Lars Arge and Peter Bro Miltersen · 1998
Earlier work this paper cites.
Graph expansion analysis for communication costs of fast rectangular matrix multiplication
Grey Ballard, James Demmel, Olga Holtz, Benjamin Lipshitz, and Oded Schwartz · 2012
Earlier work this paper cites.
Graph expansion and communication costs of fast matrix multiplication
Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz · 2012
Earlier work this paper cites.
The input/output complexity of triangle enumeration
Rasmus Pagh and Francesco Silvestri · 2014
Earlier work this paper cites.
The input/output complexity of sparse matrix multiplication
Rasmus Pagh and Morten Stöckel · 2014
Earlier work this paper cites.
Matrix multiplication i/o-complexity by path routing
Jacob Scott, Olga Holtz, and Oded Schwartz · 2015
Earlier work this paper cites.
The I/O complexity of strassen’s matrix multiplication with recomputation
Gianfranco Bilardi and Lorenzo De Stefani · 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.
Improved rectangular matrix multiplication using powers of the coppersmith-winograd tensor
Francois Le Gall and Florent Urrutia · 2018
Cited alongside, same era.
Space lower bounds for linear prediction in the streaming model
Yuval Dagan, Gil Kur, and Ohad Shamir · 2019
Cited alongside, same era.
On communication complexity of classification problems
Daniel Kane, Roi Livni, Shay Moran, and Amir Yehudayoff · 2019
Cited alongside, same era.
Fast learning requires good memory: A time-space lower bound for parity learning
Ran Raz · 2019
Cited alongside, same era.
Memory-sample tradeoffs for linear regression with small error
Vatsal Sharan, Aaron Sidford, and Gregory Valiant · 2019
Cited alongside, same era.
Open problem: The oracle complexity of convex optimization with limited memory
Blake E. Woodworth and Nathan Srebro · 2019
Rethinking attention with performers
Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamás Sarlós, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy J. Colwell, and Adrian Weller · 2021
Later among the works it cites.
Memory bounds for continual learning
Xi Chen, Christos H. Papadimitriou, and Binghui Peng · 2022
Later among the works it cites.
Flashattention: Fast and memory-efficient exact attention with io-awareness
Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré · 2022
Later among the works it cites.
Efficient convex optimization requires superlinear memory
Annie Marsden, Vatsal Sharan, Aaron Sidford, and Gregory Valiant · 2022
Later among the works it cites.
Memory bounds for the experts problem
Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, and Samson Zhou · 2022
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
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
Cited alongside, same era.
Towards a combinatorial characterization of bounded-memory learning
Alon Gonen, Shachar Lovett, and Michal Moshkovitz · 2020
Cited alongside, same era.
Reformer: The efficient transformer
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya · 2020
Cited alongside, same era.
Transformers are rnns: Fast autoregressive transformers with linear attention
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret · 2020
Cited alongside, same era.
Big bird: Transformers for longer sequences
Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontañón, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and Amr Ahmed · 2020
Cited alongside, same era.
Scatterbrain: Unifying sparse and low-rank attention
Beidi Chen, Tri Dao, Eric Winsor, Zhao Song, Atri Rudra, and Christopher Ré · 2021
Cited alongside, same era.
Josh Alman and Zhao Song · 2023
Later among the works it cites.
Memory-query tradeoffs for randomized convex optimization
Xi Chen and Binghui Peng · 2023
Later among the works it cites.
Flashattention-2: Faster attention with better parallelism and work partitioning
Tri Dao · 2023
Later among the works it cites.
Hyperattention: Long-context attention in near-linear time
Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David P. Woodruff, and Amir Zandieh · 2023
Later among the works it cites.
Near optimal memory-regret tradeoff for online learning
Binghui Peng and Aviad Rubinstein · 2023
Later among the works it cites.
Online prediction in sub-linear space
Binghui Peng and Fred Zhang · 2023
Later among the works it cites.
New bounds for matrix multiplication: from alpha to omega
Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou · 2023
Later among the works it cites.