Reproduce “Subquadratic Algorithms and Hardness for Attention with Any Temperature” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Shreya Gupta, Boyang Huang, Barna Saha, Yinzhan Xu, Christopher Ye
Researchers at the University of California, San Diego, developed the first truly subquadratic algorithms for the Attention mechanism, which scale polylogarithmically with input entry magnitudes (any temperature), for models with constant head dimensions. They also provided a comprehensive fine-grained complexity characterization of Attention, establishing conditional lower bounds across various head dimension regimes.
Key insights
- Truly subquadratic Attention algorithms are possible for constant head dimensions (d=O(1)), scaling polylogarithmically with input value range 'B' and avoiding exponential dependence on 'B'.
- The Attention gradient can also be computed in a truly subquadratic fashion for constant 'd', impacting the efficiency of LLM training.
- Attention is fundamentally hard (requiring near-quadratic time) for moderate head dimensions (d = 2^Ω(log* n)) and large head dimensions (d = poly(n)), conditionally matching the performance of standard algorithms.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.