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

arXiv: https://arxiv.org/abs/2107.11906 · HTML: https://mlsanity.com/paper/2107.11906/

## Key facts

- Cited by 47 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 50 references that are in the map.
- First posted on arXiv 25 Jul 2021.

## Builds on (most cited first, 30 of 32)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Informer: Beyond Efficient Transformer for Long Sequence Time-Series Forecasting](https://mlsanity.com/paper/2012.07436/) (2020)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Effective Approaches to Attention-based Neural Machine Translation](https://mlsanity.com/paper/1508.04025/) (2015)
- [Efficient Transformers: A Survey](https://mlsanity.com/paper/2009.06732/) (2020)
- [Image Transformer](https://mlsanity.com/paper/1802.05751/) (2018)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [Stand-Alone Self-Attention in Vision Models](https://mlsanity.com/paper/1906.05909/) (2019)
- [Efficient Content-Based Sparse Attention with Routing Transformers](https://mlsanity.com/paper/2003.05997/) (2020)
- [Attention Augmented Convolutional Networks](https://mlsanity.com/paper/1904.09925/) (2019)
- [Axial Attention in Multidimensional Transformers](https://mlsanity.com/paper/1912.12180/) (2019)
- [One Billion Word Benchmark for Measuring Progress in Statistical Language Modeling](https://mlsanity.com/paper/1312.3005/) (2013)
- [Inductive Biases for Deep Learning of Higher-Level Cognition](https://mlsanity.com/paper/2011.15091/) (2020)
- [Sparse Sinkhorn Attention](https://mlsanity.com/paper/2002.11296/) (2020)
- [Adaptive Input Representations for Neural Language Modeling](https://mlsanity.com/paper/1809.10853/) (2018)
- [Music Transformer](https://mlsanity.com/paper/1809.04281/) (2018)
- [Synthesizer: Rethinking Self-Attention in Transformer Models](https://mlsanity.com/paper/2005.00743/) (2020)
- [Mesh-TensorFlow: Deep Learning for Supercomputers](https://mlsanity.com/paper/1811.02084/) (2018)
- [Blockwise Self-Attention for Long Document Understanding](https://mlsanity.com/paper/1911.02972/) (2019)
- [Hierarchical Transformers for Multi-Document Summarization](https://mlsanity.com/paper/1905.13164/) (2019)
- [Sharp Nearby, Fuzzy Far Away: How Neural Language Models Use Context](https://mlsanity.com/paper/1805.04623/) (2018)
- [Document-Level Neural Machine Translation with Hierarchical Attention Networks](https://mlsanity.com/paper/1809.01576/) (2018)

## Built on by (most cited first, 30 of 47)

- [FEDformer: Frequency Enhanced Decomposed Transformer for Long-term Series Forecasting](https://mlsanity.com/paper/2201.12740/) (2022)
- [Simplified State Space Layers for Sequence Modeling](https://mlsanity.com/paper/2208.04933/) (2022)
- [Diagonal State Spaces are as Effective as Structured State Spaces](https://mlsanity.com/paper/2203.14343/) (2022)
- [Memorizing Transformers](https://mlsanity.com/paper/2203.08913/) (2022)
- [FiLM: Frequency improved Legendre Memory Model for Long-term Time Series Forecasting](https://mlsanity.com/paper/2205.08897/) (2022)
- [Liquid Structural State-Space Models](https://mlsanity.com/paper/2209.12951/) (2022)
- [Block-Recurrent Transformers](https://mlsanity.com/paper/2203.07852/) (2022)
- [Advancing Transformer Architecture in Long-Context Large Language Models: A Comprehensive Survey](https://mlsanity.com/paper/2311.12351/) (2023)
- [Radial Attention: O(nlog n) Sparse Attention with Energy Decay for Long Video Generation](https://mlsanity.com/paper/2506.19852/) (2025)
- [Dynamic Context Pruning for Efficient and Interpretable Autoregressive Transformers](https://mlsanity.com/paper/2305.15805/) (2023)
- [Mamba-360: Survey of State Space Models as Transformer Alternative for Long Sequence Modelling: Methods, Applications, and Challenges](https://mlsanity.com/paper/2404.16112/) (2024)
- [Log-Linear Attention](https://mlsanity.com/paper/2506.04761/) (2025)
- [Transformer-VQ: Linear-Time Transformers via Vector Quantization](https://mlsanity.com/paper/2309.16354/) (2023)
- [Efficient Attention via Control Variates](https://mlsanity.com/paper/2302.04542/) (2023)
- [Erwin: A Tree-based Hierarchical Transformer for Large-scale Physical Systems](https://mlsanity.com/paper/2502.17019/) (2025)
- [Transformer Uncertainty Estimation with Hierarchical Stochastic Attention](https://mlsanity.com/paper/2112.13776/) (2021)
- [Sequence Modeling with Multiresolution Convolutional Memory](https://mlsanity.com/paper/2305.01638/) (2023)
- [Learning Long Sequences in Spiking Neural Networks](https://mlsanity.com/paper/2401.00955/) (2023)
- [Recasting Self-Attention with Holographic Reduced Representations](https://mlsanity.com/paper/2305.19534/) (2023)
- [Multi Resolution Analysis (MRA) for Approximate Self-Attention](https://mlsanity.com/paper/2207.10284/) (2022)
- [Wavelet-Based Image Tokenizer for Vision Transformers](https://mlsanity.com/paper/2405.18616/) (2024)
- [ZETA: Leveraging Z-order Curves for Efficient Top-k Attention](https://mlsanity.com/paper/2501.14577/) (2025)
- [IceFormer: Accelerated Inference with Long-Sequence Transformers on CPUs](https://mlsanity.com/paper/2405.02842/) (2024)
- [Holographic Global Convolutional Networks for Long-Range Prediction Tasks in Malware Detection](https://mlsanity.com/paper/2403.17978/) (2024)
- [Trainable Log-linear Sparse Attention for Efficient Diffusion Transformers](https://mlsanity.com/paper/2512.16615/) (2025)
- [PoNet: Pooling Network for Efficient Token Mixing in Long Sequences](https://mlsanity.com/paper/2110.02442/) (2021)
- [Recursion in Recursion: Two-Level Nested Recursion for Length Generalization with Scalability](https://mlsanity.com/paper/2311.04449/) (2023)
- [Linear Attention with Global Context: A Multipole Attention Mechanism for Vision and Physics](https://mlsanity.com/paper/2507.02748/) (2025)
- [LongVQ: Long Sequence Modeling with Vector Quantization on Structured Memory](https://mlsanity.com/paper/2404.11163/) (2024)
- [Linear Attention for Efficient Bidirectional Sequence Modeling](https://mlsanity.com/paper/2502.16249/) (2025)

## Abstract (arXiv)

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.