Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences
This work addresses the computational bottleneck in processing long sequences for Transformer models, offering a practical improvement for applications like natural language processing, though it is incremental relative to prior methods like Linformer and Informer.
The paper tackles the inefficiency of Transformer self-attention for long sequences by proposing Skeinformer, which accelerates self-attention and improves accuracy through matrix sketching techniques, achieving better performance on the Long Range Arena benchmark with reduced time and space usage.
Transformer-based models are not efficient in processing long sequences due to the quadratic space and time complexity of the self-attention modules. To address this limitation, Linformer and Informer are proposed to reduce the quadratic complexity to linear (modulo logarithmic factors) via low-dimensional projection and row selection respectively. These two models are intrinsically connected, and to understand their connection, we introduce a theoretical framework of matrix sketching. Based on the theoretical analysis, we propose Skeinformer to accelerate self-attention and further improve the accuracy of matrix approximation to self-attention with three carefully designed components: column sampling, adaptive row normalization and pilot sampling reutilization. Experiments on the Long Range Arena (LRA) benchmark demonstrate that our methods outperform alternatives with a consistently smaller time/space footprint.