# Quantization based Fast Inner Product Search

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Sep 2015.

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

- [Extreme Compression of Large Language Models via Additive Quantization](https://mlsanity.com/paper/2401.06118/) (2024)
- [Retrieval Augmented Code Generation and Summarization](https://mlsanity.com/paper/2108.11601/) (2021)
- [The Web Is Your Oyster - Knowledge-Intensive NLP against a Very Large Web Corpus](https://mlsanity.com/paper/2112.09924/) (2021)
- [Multi-task Retrieval for Knowledge-Intensive Tasks](https://mlsanity.com/paper/2101.00117/) (2021)
- [A Survey for Efficient Open Domain Question Answering](https://mlsanity.com/paper/2211.07886/) (2022)
- [LUT-NN: Empower Efficient Neural Network Inference with Centroid Learning and Table Lookup](https://mlsanity.com/paper/2302.03213/) (2023)
- [Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures](https://mlsanity.com/paper/2111.15139/) (2021)
- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [Extreme Zero-Shot Learning for Extreme Text Classification](https://mlsanity.com/paper/2112.08652/) (2021)
- [Scalable Cross-Entropy Loss for Sequential Recommendations with Large Item Catalogs](https://mlsanity.com/paper/2409.18721/) (2024)
- [Revisiting Neural Retrieval on Accelerators](https://mlsanity.com/paper/2306.04039/) (2023)
- [Optimal Quantization for Matrix Multiplication](https://mlsanity.com/paper/2410.13780/) (2024)
- [Transductive Learning for Unsupervised Text Style Transfer](https://mlsanity.com/paper/2109.07812/) (2021)
- [Retrieval is Accurate Generation](https://mlsanity.com/paper/2402.17532/) (2024)
- [Linear Bandit Algorithms with Sublinear Time Complexity](https://mlsanity.com/paper/2103.02729/) (2021)
- [RECE: Reduced Cross-Entropy Loss for Large-Catalogue Sequential Recommenders](https://mlsanity.com/paper/2408.02354/) (2024)
- [Fast Variational AutoEncoder with Inverted Multi-Index for Collaborative Filtering](https://mlsanity.com/paper/2109.05773/) (2021)
- [Agile Modeling: From Concept to Classifier in Minutes](https://mlsanity.com/paper/2302.12948/) (2023)
- [Efficient Document Ranking with Learnable Late Interactions](https://mlsanity.com/paper/2406.17968/) (2024)
- [Augmenting Poetry Composition with Verse by Verse](https://mlsanity.com/paper/2103.17205/) (2021)
- [Retrieval with Learned Similarities](https://mlsanity.com/paper/2407.15462/) (2024)
- [HAKES: Scalable Vector Database for Embedding Search Service](https://mlsanity.com/paper/2505.12524/) (2025)
- [Efficient Approximate Search for Sets of Vectors](https://mlsanity.com/paper/2107.06817/) (2021)
- [SAH: Shifting-aware Asymmetric Hashing for Reverse k-Maximum Inner Product Search](https://mlsanity.com/paper/2211.12751/) (2022)
- [Stars: Tera-Scale Graph Building for Clustering and Graph Learning](https://mlsanity.com/paper/2212.02635/) (2022)
- [Contrastive and Transfer Learning for Effective Audio Fingerprinting through a Real-World Evaluation Protocol](https://mlsanity.com/paper/2507.06070/) (2025)
- [Amortized Maximum Inner Product Search with Learned Support Functions](https://mlsanity.com/paper/2603.08001/) (2026)
- [Mitigating scalability challenges in LUT-based neural networks via pruning optimisations](https://mlsanity.com/paper/2407.02362/) (2024)
- [Agile Deliberation: Concept Deliberation for Subjective Visual Classification](https://mlsanity.com/paper/2512.10821/) (2025)

## Abstract (arXiv)

We propose a quantization based approach for fast approximate Maximum Inner Product Search (MIPS). Each database vector is quantized in multiple subspaces via a set of codebooks, learned directly by minimizing the inner product quantization error. Then, the inner product of a query to a database vector is approximated as the sum of inner products with the subspace quantizers. Different from recently proposed LSH approaches to MIPS, the database vectors and queries do not need to be augmented in a higher dimensional feature space. We also provide a theoretical analysis of the proposed approach, consisting of the concentration results under mild assumptions. Furthermore, if a small sample of example queries is given at the training time, we propose a modified codebook learning procedure which further improves the accuracy. Experimental results on a variety of datasets including those arising from deep neural networks show that the proposed approach significantly outperforms the existing state-of-the-art.