Long-range Sequence Modeling with Predictable Sparse Attention
Self-attention mechanism has been shown to be an effective approach for capturing global context dependencies in sequence modeling, but it suffers from quadratic complexity in time and memory usage. Due to the sparsity of the attention matrix, much computation is redundant. Therefore, in this paper, we design an efficient Transformer architecture, named Fourier Sparse Attention for Transformer (FSAT), for fast long-range sequence modeling. We provide a brand-new perspective for constructing sparse attention matrix, i.e. making the sparse attention matrix predictable. Two core sub-modules are: (1) A fast Fourier transform based hidden state cross module, which captures and pools L^2 semantic combinations in \mathcal{O}(L\log L) time complexity. (2) A sparse attention matrix estimation module, which predicts dominant elements of an attention matrix based on the output of the previous hidden state cross module. By reparameterization and gradient truncation, FSAT successfully learned the index of dominant elements. The overall complexity about the sequence length is reduced from \mathcal{O}(L^2) to \mathcal{O}(L\log L). Extensive experiments (natural language, vision, and math) show that FSAT remarkably outperforms the standard multi-head attention and its variants in various long-sequence tasks with low computational costs, and achieves new state-of-the-art results on the Long Range Arena benchmark.
Code (0)
등록된 구현이 없습니다.
Tasks
MathSimilar Papers 제목 키워드 기반
Generative Temporal Models with Memory
We consider the general problem of modeling temporal data with long-range dependencies, wherein new observations are fully or partially predictable based on temporally-distant, past observations. A sufficiently powerful …
Variational InferenceSparse Attentive Memory Network for Click-through Rate Prediction with Long Sequences
Sequential recommendation predicts users' next behaviors with their historical interactions. Recommending with longer sequences improves recommendation accuracy and increases the degree of personalization. As sequences g…
Click-Through Rate PredictionRecommendation SystemsSequential RecommendationEfficient Long-Range Transformers: You Need to Attend More, but Not Necessarily at Every Layer
Pretrained transformer models have demonstrated remarkable performance across various natural language processing tasks. These models leverage the attention mechanism to capture long- and short-range dependencies in the …
8kComputational EfficiencyDecoderLanguage Modeling+1Sparse Modular Activation for Efficient Sequence Modeling
Recent hybrid models combining Linear State Space Models (SSMs) with self-attention mechanisms have demonstrated impressive results across a range of sequence modeling tasks. However, current approaches apply attention m…
ChunkingLanguage ModelingLanguage ModellingLong-range modeling+1Cluster-Former: Clustering-based Sparse Transformer for Long-Range Dependency Encoding
Transformer has become ubiquitous in the deep learning field. One of the key ingredients that destined its success is the self-attention mechanism, which allows fully-connected contextual encoding over input tokens. Howe…
ClusteringLanguage ModellingOpen-Domain Question AnsweringQuestion Answering