H-Transformer-1D: Fast One-Dimensional Hierarchical Attention for Sequences

2021/07/25 by Zhenhai Zhu, Radu Soricut, Zhu, Zhenhai +1 · 5 citations
Computer Science · #Computation and Language (cs.CL) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Multimodal Machine Learning Applications #Natural Language Processing Techniques #Topic Modeling

paper · pdf · doi:10.48550/arxiv.2107.11906

openalex publication_date 2021/07/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We describe an efficient hierarchical method to compute attention in the Transformer architecture. The proposed attention mechanism exploits a matrix structure similar to the Hierarchical Matrix (H-Matrix) developed by the numerical analysis community, and has linear run time and memory complexity. We perform extensive experiments to show that the inductive bias embodied by our hierarchical attention is effective in capturing the hierarchical structure in the sequences typical for natural language and vision tasks. Our method is superior to alternative sub-quadratic proposals by over +6 points on average on the Long Range Arena benchmark. It also sets a new SOTA test perplexity on One-Billion Word dataset with 5x fewer model parameters than that of the previous-best Transformer-based models.

Citations

• Effective Approaches to Attention-based Neural Machine Translation
• Stand-Alone Self-Attention in Vision Models
• Reformer: The Efficient Transformer
• Axial Attention in Multidimensional Transformers
• Longformer: The Long-Document Transformer
• Synthesizer: Rethinking Self-Attention in Transformer Models
• Language Models are Few-Shot Learners
• Conv-Linformer: Boosting Linformer's Performance with Convolution in Small-Scale Settings
• Informer: Beyond Efficient Transformer for Long Sequence Time-Series Forecasting

Cited by

• Hierarchical Self-Attention: Generalizing Neural Attention Mechanics to Multi-Scale Problems
• Multipole Semantic Attention: A Fast Approximation of Softmax Attention for Pretraining
• Customizing the Inductive Biases of Softmax Attention using Structured Matrices
• Natively Trainable Sparse Attention for Hierarchical Point Cloud Datasets
• Linear Attention with Global Context: A Multipole Attention Mechanism for Vision and Physics

Related

• Hierarchical Self-Attention: Generalizing Neural Attention Mechanics to Multi-Scale Problems
• SEA: Sparse Linear Attention with Estimated Attention Mask
• Combiner: Full Attention Transformer with Sparse Computation Cost
• Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers
• Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding