Abstract
Self-attention has become increasingly popular in a variety of sequence modeling tasks from natural language processing to recommendation, due to its effectiveness. However, self-attention suffers from quadratic computational and memory complexities, prohibiting its applications on long sequences. Existing approaches that address this issue mainly rely on a sparse attention context, either using a local window, or a permuted bucket obtained by locality-sensitive hashing (LSH) or sorting, while crucial information may be lost. Inspired by the idea of vector quantization that uses cluster centroids to approximate items, we propose LISA (LInear-time Self Attention), which enjoys both the effectiveness of vanilla self-attention and the efficiency of sparse attention. LISA scales linearly with the sequence length, while enabling full contextual attention via computing differentiable histograms of codeword distributions. Meanwhile, unlike some efficient attention methods, our method poses no restriction on casual masking or sequence length. We evaluate our method on four real-world datasets for sequential recommendation. The results show that LISA outperforms the state-of-the-art efficient attention methods in both performance and speed; and it is up to 57x faster and 78x more memory efficient than vanilla self-attention.
Introduction
The success of Transformer-based models in sequential recommendation is largely attributed to the self-attention mechanism. However, self-attention faces a "quadratic bottleneck": computational and memory costs scale with the square of the sequence length ($L^2$). This limitation makes vanilla Transformers prohibitively expensive for long user histories, where capturing long-term dependencies is crucial for accurate modeling.
Existing "efficient" attention models usually rely on sparsity—limiting each query to attend only to a small window or a few "buckets" of keys. However, these methods often lose global information by clipping the receptive field. LISA (LInear-time Self Attention) addresses this challenge by leveraging vector quantization to represent items as "codewords." By computing differentiable histograms of these codewords, LISA performs full contextual attention in linear time ($O(L)$), achieving significant speedups and memory savings while maintaining or even exceeding the accuracy of vanilla self-attention.
Methodology: The LISA Architecture
The core innovation of LISA lies in its ability to approximate the dense attention matrix through a finite set of codewords, drawing inspiration from vector quantization (VQ) and Maximum Inner Product Search (MIPS).
Embedding Quantization and Histograms
Instead of high-dimensional continuous vectors, items are represented as a composition of codewords from multiple codebooks. For instance, an item can be approximated by the sum of one codeword from each of several different codebooks. Since many items in a sequence may map to the same codewords, the model avoids redundant inner-product computations by generating a codeword histogram that represents the frequency of each codeword across the sequence.
Linear-Time Attention
Attention is performed between the query and the finite set of codewords ($W$), where $W \ll L$. This reduces the complexity from $O(L^2)$ to $O(L \cdot W)$. To handle the unidirectional nature of recommendation tasks (where future items must be masked), LISA employs a prefix-sum algorithm. This allows the model to compute unique histograms for every position in the sequence in $O(L)$ time.
The architecture supports several variants to balance efficiency and expressiveness:
- LISA-Base: Uses hard codeword assignments for maximum compression.
- LISA-Soft: Uses soft (probabilistic) assignments for better gradient flow and performance on certain datasets.
- LISA-Mini: Optimizes for shorter sequences using a reduced set of codebooks.
Experimental Evaluation
LISA was evaluated on four real-world sequential recommendation datasets: Alibaba (long click logs), Amazon Video Games (sparse reviews), and MovieLens (1M & 25M).
Performance and Efficiency
LISA-Base consistently outperformed state-of-the-art efficient attention baselines, such as Reformer, Linformer, and Sinkhorn Transformer, often matching or slightly exceeding the accuracy of vanilla Transformers. The efficiency gains were substantial: on sequences of length 16K, LISA demonstrated a 57x speedup and was 78x more memory-efficient than vanilla self-attention. While vanilla Transformers encountered "Out of Memory" errors on a 16GB GPU at 16K, LISA scaled effortlessly to 64K and beyond.
Key Insights
- Redundancy and Denoising: By quantizing items, LISA eliminates redundant computations in long sequences. Interestingly, LISA-Base often outperformed vanilla Transformers on noisy datasets like Amazon Video Games, suggesting that codeword summarization acts as a denoising filter, removing "jitter" in user behavior.
- Online Efficiency: In a live production environment, a user's entire history can be represented as a fixed-size histogram. When a user takes a new action, the system simply updates the histogram in constant time, rather than re-processing the entire sequence.
Conclusion
LISA provides a scalable and effective alternative to vanilla self-attention for long-sequence modeling in recommendation systems. By combining vector quantization with differentiable histograms, it achieves linear complexity without sacrificing the benefits of full contextual attention. Future work may explore the application of LISA to other domains, such as Natural Language Processing (NLP) and large-scale language modeling.
Summary updated