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

Zhenhai Zhu, Radu Soricut

TL;DR

This paper introduces H-Transformer-1D, a novel attention mechanism for sequence models that achieves linear time and memory complexity by leveraging hierarchical matrix structures. This efficiency breakthrough allows Transformers to process significantly longer sequences, outperforming existing methods on challenging long-range benchmarks and achieving state-of-the-art results in language modeling with fewer parameters.

What Problem Does This Paper Address?

The Transformer architecture, a cornerstone of modern NLP and other AI fields, relies on an attention mechanism that computes pairwise interactions between all elements in a sequence. While powerful, this mechanism has a quadratic time and memory complexity with respect to sequence length ($O(L^2)$). This quadratic scaling becomes a critical bottleneck when processing long sequences (e.g., documents, long audio clips, or high-resolution images represented as sequences), limiting the practical applicability of Transformers in these domains. Existing sub-quadratic attention methods often sacrifice performance or introduce complex approximations.

Methods

The core innovation is a hierarchical attention mechanism inspired by Hierarchical Matrices (H-Matrices) from numerical analysis. Instead of computing a dense attention matrix, H-Transformer-1D approximates it using a hierarchical structure. This involves:

  • Hierarchical Partitioning: The attention matrix is recursively partitioned into blocks, creating a hierarchy of interactions.
  • Low-Rank Approximation: Off-diagonal blocks at coarser levels of the hierarchy are approximated using low-rank factorizations. This is motivated by the observation that interactions between distant elements in a sequence can often be represented more compactly.
  • Matrix Structure Exploitation: The method leverages the properties of H-Matrices to achieve linear time and memory complexity ($O(L)$). This is done by efficiently computing and applying the attention matrix through a series of coarsening and interpolation steps, similar to multigrid methods.
  • Inductive Bias: The hierarchical structure is hypothesized to embody a useful inductive bias ("sharp nearby, fuzzy far away") that aligns with the nature of sequential data, where local context is often more critical than distant context.

Datasets

  • Long Range Arena (LRA) benchmark: This benchmark is specifically designed to evaluate long-range Transformer architectures and includes tasks like ListOps, Text, Retrieval, Image, and Pathfinder.
  • One-Billion Word dataset: Used for language modeling to evaluate perplexity and model efficiency.

Key Insights and Ideas

  • Hierarchical structure as an inductive bias: The paper posits that the inherent hierarchical structure of natural language and other sequential data can be effectively captured by a hierarchical attention mechanism, leading to better performance.
  • Linear complexity for attention: By borrowing ideas from numerical analysis (H-Matrices), the authors demonstrate that it's possible to achieve linear time and memory complexity for attention, overcoming the quadratic bottleneck of standard Transformers.
  • Efficiency and performance synergy: The proposed method not only achieves significant speedups but also improves performance, suggesting that the inductive bias is not just about efficiency but also about learning better representations for long sequences.
  • Practical implementation: The method is designed to be compatible with existing dense linear algebra libraries optimized for GPUs and TPUs, facilitating its adoption.

Key Results

  • Long Range Arena (LRA) Benchmark: H-Transformer-1D achieved an average accuracy of 61.41, outperforming the previous best model (BigBird) by 6.4 points. It showed particularly large improvements on tasks involving long sequences like ListOps, Text, and Retrieval.
  • One-Billion Word Language Modeling: The H-Transformer-1D model achieved a new state-of-the-art test perplexity of 20.25, while using 5x fewer model parameters than the previous best Transformer-based models.
  • Computational Complexity: The proposed method has a linear time and memory complexity of $O(dL)$, where $d$ is the embedding dimension and $L$ is the sequence length. This is a significant improvement over the standard Transformer's $O(L^2d)$ complexity.

Limitations and Future Work

  • Limitations: The paper acknowledges that the construction of the hierarchical attention matrix can be computationally intensive if the original attention matrix needs to be formed first. However, their method avoids this by directly constructing the hierarchical structure. The paper also notes that the numerical rank ($N_r$) is a model hyperparameter that influences the inductive bias.
  • Future Work: The authors suggest extending the hierarchical attention to:
  • Music and genomics tasks.
  • Developing proper inductive biases for cross-attention mechanisms.
  • Extending the one-dimensional hierarchical attention to 2D images.

Summary updated

BibTeX
@inproceedings{zhu2021h,
  author = {Zhenhai Zhu and Radu Soricut},
  title = {{H-Transformer-1D: Fast One-Dimensional Hierarchical Attention for Sequences}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
  url = {https://openreview.net/forum?id=eL-pf7_Kxqd},
}
Figure