The central bottleneck of the Transformer architecture is the self-attention mechanism, which scales quadratically ($O(N^2)$) with the sequence length $N$. This cost becomes prohibitive when processing long documents, high-resolution images, or temporal video data. To overcome this, a growing body of research leverages Locality-Sensitive Hashing (LSH) to approximate the dense attention matrix, transforming the computational complexity from quadratic to near-linear or log-linear.
The Intuition: Attention as a Search Problem
In standard attention, every query token must "look" at every key token to determine its relevance. However, in most tasks, a query only assigns significant weight to a small subset of highly similar keys. If we can identify these relevant keys without checking every pair, we can skip the vast majority of redundant computations.
LSH provides a mathematical shortcut for this search. Unlike traditional cryptographic hashes designed to avoid collisions, LSH is designed to maximize collisions for similar vectors. By projecting high-dimensional query and key vectors into discrete "buckets" based on their angular or spatial proximity, the model can restrict attention calculations to tokens within the same bucket. As Kitaev et al. demonstrate in the Reformer architecture, this bucketing reduces complexity to $O(N \log N)$, enabling the processing of sequences up to 64,000 tokens on a single GPU.
Hashing for Non-Local Vision Tasks
While LSH was popularized in natural language processing, its impact is perhaps more visible in computer vision, where "non-local" dependencies—finding similar textures or patterns across distant parts of an image—are crucial for restoration.
In image super-resolution, Mei et al. introduce Non-Local Sparse Attention (NLSA), which uses spherical LSH to group similar image patches. By only computing attention within these angularly similar buckets, the authors achieve linear complexity relative to the number of pixels. This allows the model to fuse textures from across the entire image to repair local defects, a task previously limited by the memory constraints of dense attention. Similarly, Lee et al. utilize LSH in the k-NN Image Transformer (KiT) to identify non-local patterns for denoising and deblurring, proving that global context can be captured with the efficiency of local convolutions.
Probabilistic and Theoretical Foundations
The shift from dense to hashed attention is not merely a heuristic; it has deep probabilistic and theoretical justifications.
- Attention as Sampling: Zeng et al. propose the YOSO (You Only Sample Almost Once) framework, which reformulates attention as an expectation of Bernoulli random variables. By using LSH to sample these variables, the authors approximate the softmax distribution with linear cost, leveraging the fact that LSH collision probabilities naturally mirror the monotonic properties of the exponential functions used in standard attention.
- Parallel Efficiency: Beyond raw speed, hashing-based mechanisms offer better theoretical scaling for massively parallel hardware. Liu et al. show that Approximate Nearest Neighbor Attention (ANNA) can simulate complex reasoning tasks using near-linear resources, whereas standard attention requires quadratic resources to achieve the same degree of parallel simulation.
Hybrid Architectures and Domain Adaptation
Recent work has begun integrating LSH-based attention into hybrid systems to address the specific weaknesses of other efficient models. For instance, while State-Space Models (SSMs) like Mamba are fast, they often struggle with precise, content-based memory retrieval. Zhan et al. introduce HAX, which augments SSMs with LSH-based sparse attention. This allows the model to perform dynamic, content-based routing across long sequences without losing the linear-time benefits of the SSM backbone.
The versatility of this approach extends to specialized data types:
- Hyperspectral Imaging: Cai et al. use hashing to cluster tokens across spectral dimensions, capturing fine-grained self-similarity in 3D data cubes.
- Remote Sensing: Qiu et al. employ Super-bit LSH to make global feature fusion computationally feasible for high-resolution satellite imagery.
- Translation: Petrick et al. demonstrate that while LSH attention enables document-level context in machine translation, it introduces a slight trade-off in translation quality, highlighting the ongoing challenge of balancing approximation accuracy with computational gain.
By treating attention as a similarity-search problem rather than a dense matrix operation, these researchers have turned the quadratic barrier into a manageable, near-linear process, paving the way for models that can reason over increasingly vast horizons of data.
Key Foundational Work
Reformer: The Efficient Transformer (2020) — contributed 2 concept elements to this direction.
Shifted Chunk Transformer for Spatio-Temporal Representational Learning (2021) — contributed 2 concept elements to this direction.
Reformer-TTS: Neural Speech Synthesis with Reformer Network (2020) — contributed 1 concept elements to this direction.