PLASH: Provably Linear-Time Attention with Selective Higher-Order Feature Sketching
Attention selects information from long contexts, but standard softmax attention scales as $O(N_qN_k)$ in the number of queries $N_q$ and keys $N_k$, making long-context training and inference expensive. We propose PLASH, an attention block with provably linear-time complexity in $N_k$ that preserve…