FAST: Factorizable Attention for Speeding up Transformers
This addresses a fundamental bottleneck in scaling transformers for applications requiring long sequences, though it appears incremental relative to prior fast attention methods.
The paper tackles the quadratic computational and memory complexity of transformer attention mechanisms by introducing a factorable attention method that reduces complexity from O(N²) to O(N) while maintaining full attention matrix representation and all-to-all token relationships. Results show robust performance in standard settings.
Motivated by the factorization inherent in the original fast multipole method and the improved fast Gauss transform we introduce a factorable form of attention that operates efficiently in high dimensions. This approach reduces the computational and memory complexity of the attention mechanism in transformers from $O(N^2)$ to $O(N)$. In comparison to previous attempts, our work presents a linearly scaled attention mechanism that maintains the full representation of the attention matrix without compromising on sparsification and incorporates the all-to-all relationship between tokens. We explore the properties of our new attention metric and conduct tests in various standard settings. Results indicate that our attention mechanism has a robust performance and holds significant promise for diverse applications where self-attention is used.