# Faster Maximum Inner Product Search in High Dimensions

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 104 references that are in the map.
- First posted on arXiv 14 Dec 2022.

## Builds on (most cited first, 30 of 33)

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Improving language models by retrieving from trillions of tokens](https://mlsanity.com/paper/2112.04426/) (2021)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Non-stochastic Best Arm Identification and Hyperparameter Optimization](https://mlsanity.com/paper/1502.07943/) (2015)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)](https://mlsanity.com/paper/1405.5869/) (2014)
- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [On Symmetric and Asymmetric LSHs for Inner Product Search](https://mlsanity.com/paper/1410.5518/) (2014)
- [Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures](https://mlsanity.com/paper/2111.15139/) (2021)
- [Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS)](https://mlsanity.com/paper/1410.5410/) (2014)
- [Off the Beaten Path: Let's Replace Term-Based Retrieval with k-NN Search](https://mlsanity.com/paper/1610.10001/) (2016)
- [A Unified Optimization View on Generalized Matching Pursuit and Frank-Wolfe](https://mlsanity.com/paper/1702.06457/) (2017)
- [A Greedy Approach for Budgeted Maximum Inner Product Search](https://mlsanity.com/paper/1610.03317/) (2016)
- [Medoids in almost linear time via multi-armed bandits](https://mlsanity.com/paper/1711.00817/) (2017)
- [Norm-Explicit Quantization: Improving Vector Quantization for Maximum Inner Product Search](https://mlsanity.com/paper/1911.04654/) (2019)
- [Ultra Fast Medoid Identification via Correlated Sequential Halving](https://mlsanity.com/paper/1906.04356/) (2019)
- [Accelerating Large-Scale Inference with Anisotropic Vector Quantization](https://mlsanity.com/paper/1908.10396/) (2019)
- [Accelerating Frank-Wolfe Algorithm using Low-Dimensional and Adaptive Data Structures](https://mlsanity.com/paper/2207.09002/) (2022)
- [Polysemous codes](https://mlsanity.com/paper/1609.01882/) (2016)
- [Norm-Ranging LSH for Maximum Inner Product Search](https://mlsanity.com/paper/1809.08782/) (2018)
- [Adaptive Monte Carlo Multiple Testing via Multi-Armed Bandits](https://mlsanity.com/paper/1902.00197/) (2019)
- [A Bandit Approach to Maximum Inner Product Search](https://mlsanity.com/paper/1812.06360/) (2018)
- [Understanding and Improving Proximity Graph based Maximum Inner Product Search](https://mlsanity.com/paper/1909.13459/) (2019)
- [Reverse Maximum Inner Product Search: How to efficiently find users who would like to buy my item?](https://mlsanity.com/paper/2110.07131/) (2021)
- [Reinforcement Routing on Proximity Graph for Efficient Recommendation](https://mlsanity.com/paper/2201.09290/) (2022)
- [Approximate Function Evaluation via Multi-Armed Bandits](https://mlsanity.com/paper/2203.10124/) (2022)
- [FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2206.11408/) (2022)
- [Diamond Sampling for Approximate Maximum All-pairs Dot-product (MAD) Search](https://mlsanity.com/paper/1506.03872/) (2015)
- [Permutation Search Methods are Efficient, Yet Faster Search is Possible](https://mlsanity.com/paper/1506.03163/) (2015)
- [Sublinear Maximum Inner Product Search using Concomitants of Extreme Order Statistics](https://mlsanity.com/paper/2012.11098/) (2020)

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

- [Scaling Autoregressive Multi-Modal Models: Pretraining and Instruction Tuning](https://mlsanity.com/paper/2309.02591/) (2023)
- [Ask in Any Modality: A Comprehensive Survey on Multimodal Retrieval-Augmented Generation](https://mlsanity.com/paper/2502.08826/) (2025)
- [SPT: Fine-Tuning Transformer-based Language Models Efficiently with Sparsification](https://mlsanity.com/paper/2312.10365/) (2023)

## Abstract (arXiv)

Maximum Inner Product Search (MIPS) is a ubiquitous task in machine learning applications such as recommendation systems. Given a query vector and n atom vectors in d-dimensional space, the goal of MIPS is to find the atom that has the highest inner product with the query vector. Existing MIPS algorithms scale at least as O(√d), which becomes computationally prohibitive in high-dimensional settings. In this work, we present BanditMIPS, a novel randomized MIPS algorithm whose complexity is independent of d. BanditMIPS estimates the inner product for each atom by subsampling coordinates and adaptively evaluates more coordinates for more promising atoms. The specific adaptive sampling strategy is motivated by multi-armed bandits. We provide theoretical guarantees that BanditMIPS returns the correct answer with high probability, while improving the complexity in d from O(√d) to O(1). We also perform experiments on four synthetic and real-world datasets and demonstrate that BanditMIPS outperforms prior state-of-the-art algorithms. For example, in the Movie Lens dataset (n=4,000, d=6,000), BanditMIPS is 20× faster than the next best algorithm while returning the same answer. BanditMIPS requires no preprocessing of the data and includes a hyperparameter that practitioners may use to trade off accuracy and runtime. We also propose a variant of our algorithm, named BanditMIPS-α, which achieves further speedups by employing non-uniform sampling across coordinates. Finally, we demonstrate how known preprocessing techniques can be used to further accelerate BanditMIPS, and discuss applications to Matching Pursuit and Fourier analysis.