Introduction
Maximum Inner Product Search (MIPS) is a critical component in modern AI, powering recommender systems, structural SVMs, and multiclass prediction. Given a query vector $q$ and a large collection of data vectors $S$, the objective is to find the vector $v \in S$ that maximizes the dot product $q^T v$.
Traditional approaches to MIPS often rely on a "preprocessing tax." Methods like Locality-Sensitive Hashing (LSH) or PCA-trees require building complex data structures before answering queries. This creates significant overhead for dynamic datasets and lacks a mechanism for users to explicitly guarantee result accuracy. Researchers at the University of Michigan have introduced BOUNDEDME, a novel algorithm that reframes MIPS as a multi-armed bandit problem with zero preprocessing requirements.
Reframing MIPS as a Bandit Problem
The core innovation of BOUNDEDME is treating each data vector as an "arm" in a Best Arm Identification problem. In this setting, "pulling an arm" involves calculating the product of a single coordinate pair between the query and a data vector.
Unlike standard bandit algorithms that assume infinite populations, MIPS deals with a finite number of coordinates ($N$). The authors formalize this as Multi-Armed Bandit with Bounded Pulls (MAB-BP). BOUNDEDME utilizes a "Median Elimination" strategy, iteratively sampling coordinates and discarding the bottom half of performing vectors until the top candidates remain. This approach is sub-linear in dimension, with a complexity of $O(\frac{n\sqrt{N}}{\epsilon} \log \frac{1}{\delta})$.
Theoretical Guarantees: The Accuracy Knob
BOUNDEDME provides users with an "accuracy knob" through two parameters: $\epsilon$ (error tolerance) and $\delta$ (failure probability). The algorithm theoretically guarantees an $\epsilon$-optimal solution with probability $1-\delta$. Empirical tests confirm that the actual suboptimality of the results remains well within the bounds defined by the user.
Experimental Evaluation
The researchers evaluated BOUNDEDME against three major baselines—LSH-MIPS, GREEDY-MIPS, and PCA-MIPS—using synthetic and real-world datasets, including Netflix and Yahoo-Music. Each dataset contained $10^4$ vectors with $10^5$ dimensions.
Key Results
- Zero Preprocessing: BOUNDEDME is immediately ready for dynamic datasets, avoiding the time-consuming indexing required by LSH or PCA-based methods.
- Speed and Precision: The algorithm achieved 5–10x query speedups over state-of-the-art methods. Crucially, while the precision of competing methods drops sharply at higher speedup factors, BOUNDEDME maintains high precision.
Conclusion and Future Work
BOUNDEDME demonstrates that a bandit-based approach can outperform traditional indexing for MIPS, especially in scenarios requiring immediate results or high precision control. While the current algorithm is linear in the number of vectors ($n$), future work aims to combine these bandit techniques with geometric pruning to achieve sub-linear performance in both dimensionality and dataset size.
Summary updated