# Linear-Time Self Attention with Codeword Histogram for Efficient Recommendation

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2021.

## Built on by (most cited first, 7 of 7)

- [Learning Vector-Quantized Item Representation for Transferable Sequential Recommenders](https://mlsanity.com/paper/2210.12316/) (2022)
- [A Comprehensive Survey on Trustworthy Recommender Systems](https://mlsanity.com/paper/2209.10117/) (2022)
- [Distill-VQ: Learning Retrieval Oriented Vector Quantization By Distilling Knowledge from Dense Embeddings](https://mlsanity.com/paper/2204.00185/) (2022)
- [Cooperative Retriever and Ranker in Deep Recommenders](https://mlsanity.com/paper/2206.14649/) (2022)
- [AttMEMO : Accelerating Transformers with Memoization on Big Memory Systems](https://mlsanity.com/paper/2301.09262/) (2023)
- [CoVE: Compressed Vocabulary Expansion Makes Better LLM-based Recommender Systems](https://mlsanity.com/paper/2506.19993/) (2025)
- [Balanced Co-Clustering of Users and Items for Embedding Table Compression in Recommender Systems](https://mlsanity.com/paper/2604.18351/) (2026)

## Abstract (arXiv)

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.