LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions

Ravindran Kannan, Chiranjib Bhattacharyya, Praneeth Kacham +1

A central problem related to transformers can be stated as follows: given two $n\times d$ matrices $Q$ and $K$, and a non-negative function $f$, define the matrix $A$ as follows:…