Subquadratic Algorithms and Hardness for Attention with Any Temperature

Shreya Gupta, Boyang Huang, Barna Saha +2

Despite the popularity of the Transformer architecture, the standard algorithm for computing Attention suffers from quadratic time complexity in context length $n$. Alman and Song…