Sparse Attention with Learning to Hash

Zhiqing Sun, Yiming Yang, Shinjae YooICLR 2022 · OpenReview

TL;DR

This paper introduces Learning-to-Hash Attention (LHA), a method designed to make Transformers efficient for long sequences by replacing standard self-attention with a learnable, sparse alternative. Unlike previous methods that rely on random or fixed hashing, LHA learns separate hash functions for queries and keys to account for their distinct data distributions. This approach achieves $O(N^{1.5})$ complexity while outperforming other "efficient" Transformer variants on benchmarks like Long-Range Arena.

The Problem: Quadratic Complexity and Hashing Flaws

The standard Transformer architecture relies on self-attention, which has a major computational bottleneck: its cost grows quadratically ($O(N^2)$) with the sequence length. To process long documents or high-resolution images, researchers often employ "sparse attention," where each token only attends to a small subset of other tokens.

Existing sparse methods frequently use Approximate Nearest Neighbor (ANN) techniques, such as Locality-Sensitive Hashing (LSH), to group similar queries and keys into "buckets." However, the authors identify two critical failures in these traditional methods:

  1. Distribution Mismatch: They assume queries and keys live in the exact same vector space, which is rarely true in trained models.
  2. Bucket Imbalance: Random hashing often leads to some buckets being overcrowded (which slows down computation) and others being nearly empty (which wastes capacity). This results in a poor approximation of the full attention matrix.
Statistics of queries and keys in LSH buckets showing severe imbalance

The LHA Solution: Data-Driven Sparse Attention

To resolve these imbalances, the authors propose Learning-to-Hash Attention (LHA), which takes a data-driven approach to attention sparsification:

  • Learnable Hash Functions: Instead of using random hyperplanes like standard LSH, LHA uses small neural networks (MLPs) to predict which bucket a query or key belongs to. Crucially, it uses separate parameters for queries and keys, acknowledging their different distributions.
  • Attention Utility (AU): The authors define a novel metric called "Attention Utility," which quantifies how much of the "total attention energy" is captured by a specific bucketing strategy. Since finding the absolute optimal buckets is mathematically NP-hard, they use this AU metric to guide the training of their hash functions.
  • End-to-End Training: The hash functions are trained alongside the main Transformer model. A KL-divergence loss is used to encourage the hash functions to select buckets that maximize the Attention Utility.
  • Efficiency via Kernelization: To avoid the $O(N^2)$ cost of calculating the "ideal" buckets during training, LHA leverages Random Fourier Features (RFF) to approximate the attention utilities in $O(N \cdot B)$ time (where $B$ is the number of buckets).

Key Insights

  • Asymmetry is Key: Forcing queries and keys into the same hashing space (as seen in models like Reformer) actually exacerbates bucket imbalance. By allowing separate hash functions, LHA adapts to the natural mismatch between query and key distributions.
  • A Theoretical Framework: The "Attention Utility" metric provides a theoretical grounding to measure why a sparse pattern is effective, moving the field away from random pattern selection toward optimizing for the most informative connections.
  • Plug-and-Play Architecture: LHA does not require the "tied weights" constraint (where $Q=K$) that some other efficient models demand. This makes it much easier to drop into existing, pre-trained Transformer pipelines.

Key Results and Performance

The model was rigorously evaluated across a diverse set of benchmarks, including WikiText-103, the GLUE Benchmark, Long-Range-Arena (LRA), and ETT for time series forecasting.

  • Natural Language Understanding (GLUE): LHA maintained performance comparable to the full-attention RoBERTa baseline while using significantly fewer connections, proving that sparsity does not have to come at the cost of accuracy.
GLUE benchmark results comparing LHA to RoBERTa and other sparse variants
  • Long-Range Arena (LRA): LHA achieved an average score of 53.1, outperforming strong efficient competitors like BigBird (50.0), Performer (45.0), and Reformer (46.2).
  • Time Series Forecasting: On the ETT datasets, LHA significantly reduced Mean Squared Error (MSE) compared to the previous state-of-the-art "Informer" model, often by 20-30%.
  • Computational Efficiency: LHA successfully reduces the attention complexity from $O(N^2)$ to roughly $O(N^{1.5})$. In practice, this allows for significant throughput gains on long sequences, running up to 1.5x faster than vanilla Transformers on 4K-length sequences.

Limitations and Future Work

While highly effective, LHA has a few acknowledged limitations. First, regarding causal masking, the primary Attention Utility metric doesn't yet fully account for the constraints of autoregressive generation, though the authors propose a "joint hash" workaround. Second, the overhead of running MLPs for hashing means the speed benefits are most apparent only at very long sequence lengths (e.g., >1024 tokens); for short sequences, standard attention may still be faster. Finally, validating LHA on massive, multi-billion parameter models remains an important next step for future research.

Summary updated

Abstract

Transformer has become ubiquitous in sequence modeling tasks. As a key component of Transformer, self-attention does not scale to long sequences due to its quadratic time and space complexity with respect to the sequence length. To tackle this problem, recent work developed dynamic attention sparsification techniques based on Approximate Nearest Neighbor (ANN) methods, where similar queries and keys are allocated to the same hash bucket with high probability. However, the effectiveness of those ANN methods relies on the assumption that queries and keys should lie in the same space, which is not well justified. Besides, some of the ANN methods such as Locality-Sensitive Hashing (LSH) are randomized and cannot fully utilize the available real data distributions. To overcome these issues, this paper proposes a new strategy for sparse attention, namely LHA (Learning-to-Hash Attention), which directly learns separate parameterized hash functions for queries and keys, respectively. Another advantage of LHA is that it does not impose extra constraints for queries and keys, which makes it applicable to the wide range of pre-trained Transformer models. Our experiments on evaluation of the WikiText-103 dataset for language modeling, the GLUE benchmark for natural language understanding, and the Lang-Range-Arena benchmark for multiple tasks (text/image classification, retrieval, etc.) show the superior performance of LHA over other strong Transformer variants.
BibTeX
@inproceedings{sun2022sparse,
  author = {Zhiqing Sun and Yiming Yang and Shinjae Yoo},
  title = {{Sparse Attention with Learning to Hash}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=VGnOJhd5Q1q},
}
Figure