Approaching I/O-optimality for Approximate Attention

Pál András Papp, Aleksandros Sobczyk, Anastasios Zouzias

We revisit the I/O complexity of attention in large language models. Given query-key-value matrices $Q,K,V\in {\mathbb{R}}^{n\times d}$, and a machine with fast memory size $M$, the g…