# On Symmetric and Asymmetric LSHs for Inner Product Search

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

## Key facts

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

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

- [Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time](https://mlsanity.com/paper/2310.17157/) (2023)
- [Efficient Passage Retrieval with Hashing for Open-domain Question Answering](https://mlsanity.com/paper/2106.00882/) (2021)
- [HashAttention: Semantic Sparsity for Faster Inference](https://mlsanity.com/paper/2412.14468/) (2024)
- [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)
- [TPU-KNN: K Nearest Neighbor Search at Peak FLOP/s](https://mlsanity.com/paper/2206.14286/) (2022)
- [You Only Sample (Almost) Once: Linear Cost Self-Attention Via Bernoulli Sampling](https://mlsanity.com/paper/2111.09714/) (2021)
- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [Linear Bandit Algorithms with Sublinear Time Complexity](https://mlsanity.com/paper/2103.02729/) (2021)
- [Fast Variational AutoEncoder with Inverted Multi-Index for Collaborative Filtering](https://mlsanity.com/paper/2109.05773/) (2021)
- [IceFormer: Accelerated Inference with Long-Sequence Transformers on CPUs](https://mlsanity.com/paper/2405.02842/) (2024)
- [Sublinear Time Algorithm for Online Weighted Bipartite Matching](https://mlsanity.com/paper/2208.03367/) (2022)
- [Flashlight: Scalable Link Prediction with Effective Decoders](https://mlsanity.com/paper/2209.10100/) (2022)
- [Efficient Link Prediction via GNN Layers Induced by Negative Sampling](https://mlsanity.com/paper/2310.09516/) (2023)
- [Implicit Two-Tower Policies](https://mlsanity.com/paper/2208.01191/) (2022)
- [Faster Maximum Inner Product Search in High Dimensions](https://mlsanity.com/paper/2212.07551/) (2022)
- [Curator: Efficient Indexing for Multi-Tenant Vector Databases](https://mlsanity.com/paper/2401.07119/) (2024)
- [SINDI: An Efficient Index for Sparse Vector Approximate Maximum Inner Product Search](https://mlsanity.com/paper/2509.08395/) (2025)
- [Fast Vocabulary Projection Method via Clustering for Multilingual Machine Translation on GPU](https://mlsanity.com/paper/2208.06874/) (2022)
- [SAH: Shifting-aware Asymmetric Hashing for Reverse k-Maximum Inner Product Search](https://mlsanity.com/paper/2211.12751/) (2022)
- [Amortized Maximum Inner Product Search with Learned Support Functions](https://mlsanity.com/paper/2603.08001/) (2026)
- [Fast-MWEM: Private Data Release in Sublinear Time](https://mlsanity.com/paper/2602.03732/) (2026)
- [NBQ: Next-Best-Question for Dynamic Profiling](https://mlsanity.com/paper/2606.00809/) (2026)

## Abstract (arXiv)

We consider the problem of designing locality sensitive hashes (LSH) for inner product similarity, and of the power of asymmetric hashes in this context. Shrivastava and Li argue that there is no symmetric LSH for the problem and propose an asymmetric LSH based on different mappings for query and database points. However, we show there does exist a simple symmetric LSH that enjoys stronger guarantees and better empirical performance than the asymmetric LSH they suggest. We also show a variant of the settings where asymmetry is in-fact needed, but there a different asymmetric LSH is required.