# Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)

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

## Key facts

- Cited by 109 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 May 2014.

## Built on by (most cited first, 30 of 109)

- [REALM: Retrieval-Augmented Language Model Pre-Training](https://mlsanity.com/paper/2002.08909/) (2020)
- [Socratic Models: Composing Zero-Shot Multimodal Reasoning with Language](https://mlsanity.com/paper/2204.00598/) (2022)
- [Actions Speak Louder than Words: Trillion-Parameter Sequential Transducers for Generative Recommendations](https://mlsanity.com/paper/2402.17152/) (2024)
- [Retrieving and Reading: A Comprehensive Survey on Open-domain Question Answering](https://mlsanity.com/paper/2101.00774/) (2021)
- [Scatterbrain: Unifying Sparse and Low-rank Attention Approximation](https://mlsanity.com/paper/2110.15343/) (2021)
- [REVEAL: Retrieval-Augmented Visual-Language Pre-Training with Multi-Source Multimodal Knowledge Memory](https://mlsanity.com/paper/2212.05221/) (2022)
- [The Lazy Neuron Phenomenon: On Emergence of Activation Sparsity in Transformers](https://mlsanity.com/paper/2210.06313/) (2022)
- [Open-domain Visual Entity Recognition: Towards Recognizing Millions of Wikipedia Entities](https://mlsanity.com/paper/2302.11154/) (2023)
- [MagicPIG: LSH Sampling for Efficient LLM Generation](https://mlsanity.com/paper/2410.16179/) (2024)
- [TopiOCQA: Open-domain Conversational Question Answering with Topic Switching](https://mlsanity.com/paper/2110.00768/) (2021)
- [End-to-End Training of Neural Retrievers for Open-Domain Question Answering](https://mlsanity.com/paper/2101.00408/) (2021)
- [Neural Machine Translation with Monolingual Translation Memory](https://mlsanity.com/paper/2105.11269/) (2021)
- [The Web Is Your Oyster - Knowledge-Intensive NLP against a Very Large Web Corpus](https://mlsanity.com/paper/2112.09924/) (2021)
- [Learning to Rank in Generative Retrieval](https://mlsanity.com/paper/2306.15222/) (2023)
- [Multi-task Retrieval for Knowledge-Intensive Tasks](https://mlsanity.com/paper/2101.00117/) (2021)
- [SelfExplain: A Self-Explaining Architecture for Neural Text Classifiers](https://mlsanity.com/paper/2103.12279/) (2021)
- [SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2111.08566/) (2021)
- [Contextual Bandits with Large Action Spaces: Made Practical](https://mlsanity.com/paper/2207.05836/) (2022)
- [Does Preprocessing Help Training Over-parameterized Neural Networks?](https://mlsanity.com/paper/2110.04622/) (2021)
- [Rethinking the Role of Token Retrieval in Multi-Vector Retrieval](https://mlsanity.com/paper/2304.01982/) (2023)
- [Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing](https://mlsanity.com/paper/2211.14227/) (2022)
- [Multi-Step Reasoning Over Unstructured Text with Beam Dense Retrieval](https://mlsanity.com/paper/2104.05883/) (2021)
- [Topology Distillation for Recommender System](https://mlsanity.com/paper/2106.08700/) (2021)
- [HashAttention: Semantic Sparsity for Faster Inference](https://mlsanity.com/paper/2412.14468/) (2024)
- [RetGen: A Joint framework for Retrieval and Grounded Text Generation Modeling](https://mlsanity.com/paper/2105.06597/) (2021)
- [Improving Biomedical Information Retrieval with Neural Retrievers](https://mlsanity.com/paper/2201.07745/) (2022)
- [A Survey for Efficient Open Domain Question Answering](https://mlsanity.com/paper/2211.07886/) (2022)
- [Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures](https://mlsanity.com/paper/2111.15139/) (2021)
- [Logarithmic Smoothing for Pessimistic Off-Policy Evaluation, Selection and Learning](https://mlsanity.com/paper/2405.14335/) (2024)
- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)

## Abstract (arXiv)

We present the first provably sublinear time algorithm for approximate Maximum Inner Product Search (MIPS). Our proposal is also the first hashing algorithm for searching with (un-normalized) inner product as the underlying similarity measure. Finding hashing schemes for MIPS was considered hard. We formally show that the existing Locality Sensitive Hashing (LSH) framework is insufficient for solving MIPS, and then we extend the existing LSH framework to allow asymmetric hashing schemes. Our proposal is based on an interesting mathematical phenomenon in which inner products, after independent asymmetric transformations, can be converted into the problem of approximate near neighbor search. This key observation makes efficient sublinear hashing scheme for MIPS possible. In the extended asymmetric LSH (ALSH) framework, we provide an explicit construction of provably fast hashing scheme for MIPS. The proposed construction and the extended LSH framework could be of independent theoretical interest. Our proposed algorithm is simple and easy to implement. We evaluate the method, for retrieving inner products, in the collaborative filtering task of item recommendations on Netflix and Movielens datasets.