CAST: Clustering Self-Attention using Surrogate Tokens for Efficient Transformers
This addresses the problem of scaling Transformers to long sequences for researchers and practitioners, offering an incremental improvement over existing efficient methods.
The paper tackles the computational inefficiency of Transformers due to quadratic self-attention complexity by proposing CAST, a clustering mechanism using surrogate tokens, which reduces complexity to O(αN) and achieves comparable or better performance on long-range tasks with higher time and memory efficiency than other efficient transformers.
The Transformer architecture has shown to be a powerful tool for a wide range of tasks. It is based on the self-attention mechanism, which is an inherently computationally expensive operation with quadratic computational complexity: memory usage and compute time increase quadratically with the length of the input sequences, thus limiting the application of Transformers. In this work, we propose a novel Clustering self-Attention mechanism using Surrogate Tokens (CAST), to optimize the attention computation and achieve efficient transformers. CAST utilizes learnable surrogate tokens to construct a cluster affinity matrix, used to cluster the input sequence and generate novel cluster summaries. The self-attention from within each cluster is then combined with the cluster summaries of other clusters, enabling information flow across the entire input sequence. CAST improves efficiency by reducing the complexity from $O(N^2)$ to $O(αN)$ where N is the sequence length, and α is constant according to the number of clusters and samples per cluster. We show that CAST performs better than or comparable to the baseline Transformers on long-range sequence modeling tasks, while also achieving higher results on time and memory efficiency than other efficient transformers.