Faster Maximum Inner Product Search in High Dimensions

Overview

Published as arXiv:2212.07551, this paper addresses Maximum Inner Product Search (MIPS) in high-dimensional spaces—a problem closely related to but distinct from nearest neighbor search.

What is MIPS?

Maximum Inner Product Search finds vectors with the highest inner product (dot product) with a query vector:

• Different from nearest neighbor (uses distance, not inner product)
• Important for recommendation systems
• Fundamental to neural network operations
• Common in machine learning applications

Why MIPS Matters

Recommendation Systems

User-item scores often computed as inner products of embedding vectors

Neural Networks

Attention mechanisms rely on inner product computations

Information Retrieval

Some relevance models use inner product for scoring

Matrix Factorization

Finding top components in factorized representations

High-Dimensional Challenge

As dimensionality increases:

• Naive algorithms become computationally expensive
• Traditional ANN techniques don't directly apply
• Inner product structure differs from distance-based search
• Need specialized algorithms

Key Contributions

The paper likely presents:

• Faster algorithms specifically designed for MIPS
• Theoretical analysis of complexity
• Practical heuristics for high dimensions
• Experimental validation on real-world datasets

Relationship to ANN

MIPS can be transformed to nearest neighbor search, but:

• Transformation increases dimensionality
• Direct MIPS algorithms can be more efficient
• Different index structures may be optimal

Use Cases

• Large-scale recommendation engines (millions of items)
• Neural network inference optimization
• Collaborative filtering systems
• Embedding-based retrieval
• Top-K selection in high-dimensional spaces

Practical Impact

Many real-world systems use MIPS:

• Product recommendations in e-commerce
• Content recommendations in streaming services
• Ad targeting systems
• Search ranking

Faster MIPS algorithms directly improve user experience and reduce infrastructure costs.

Availability

ArXiv preprint arXiv:2212.07551 with algorithmic details and performance analysis.