A Bandit Approach to Maximum Inner Product Search

Rui Liu, Tianyi Wu, Barzan MozafariAAAI 2019 · DOI

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.

Validation of theoretical suboptimality bounds for BOUNDEDME.

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.
Precision vs. speedup comparison on Netflix and Yahoo datasets.

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

BibTeX
@inproceedings{liu2019bandit,
  author = {Rui Liu and Tianyi Wu and Barzan Mozafari},
  title = {{A Bandit Approach to Maximum Inner Product Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33014376},
}
Figure