Nyströmformer: A Nyström-based Algorithm for Approximating Self-Attention
Yunyang Xiong 1 Zhanpeng Zeng 1 Rudrasis Chakraborty 2 Mingxing Tan 3 Glenn Fung 4 Yin Li 1 Vikas Singh 1
Abstract
Transformers have emerged as a powerful tool for a broad range of natural language processing tasks. A key component that drives the impressive performance of Transformers is the self-attention mechanism that encodes the influence or dependence of other tokens on each specific token. While beneficial, the quadratic complexity of self-attention on the input sequence length has limited its application to longer sequences – a topic being actively studied in the community. To address this limitation, we propose Nyströmformer – a model that exhibits favorable scalability as a function of sequence length. Our idea is based on adapting the Nyström method to approximate standard self-attention with $O(n)$ complexity. The scalability of Nyströmformer enables application to longer sequences with thousands of tokens. We perform evaluations on multiple downstream tasks on the GLUE benchmark and IMDB reviews with standard sequence length, and find that our Nyströmformer performs comparably, or in a few cases, even slightly better, than standard self-attention. On longer sequence tasks in the Long Range Arena (LRA) benchmark, Nyströmformer performs favorably relative to other efficient self-atte
中文速览
Transformer的自注意力机制虽然效果强大，但计算复杂度随序列长度呈平方级增长，导致处理长文本时内存和时间开销极高。受数值分析中Nyström矩阵近似方法的启发，作者提出了Nyströmformer，通过从查询和键中抽取少量"地标点"来重建完整的softmax注意力矩阵，将复杂度从O(n²)降至O(n)。在GLUE和IMDB等标准任务上，Nyströmformer的表现与原版BERT相当甚至略有超越；在需要处理超长序列的Long Range Arena基准测试中，相比Reformer、Linformer、Performer等高效注意力方法平均准确率高出约3.4%。这项工作为在有限计算资源下将Transformer扩展到数千甚至更长token的序列提供了一条切实可行的路径。
原文 arXiv:2102.03902;中英对照 + 大白话阅读 https://aha.fim.ai/paper/2102.03902v3