Maximum Inner Product Search (MIPS)

The fundamental goal of MIPS is to find the database vectors x that maximize the inner product (dot product) with a query vector q: argmax_i (q ⋅ x_i). This is the primary objective in scenarios like:

• Recommendation systems, where user and item embeddings are not normalized and their dot product directly predicts engagement probability.
• Neural network inference, particularly in attention mechanisms where query-key matching is a dot product operation.
• Unlike Cosine Similarity, MIPS is sensitive to vector magnitude, making it suitable for scoring relevance where magnitude indicates confidence or popularity.

MIPS is not equivalent to Nearest Neighbor Search under common metrics without transformation. This is a critical distinction for algorithm selection.

• Euclidean distance minimization: argmin_i ||q - x_i||^2 is equivalent to argmax_i (q ⋅ x_i - ||x_i||^2/2) only if ||q|| is constant for all queries, which is often not the case.
• Cosine Similarity maximization: argmax_i ( (q ⋅ x_i) / (||q|| * ||x_i||) ) is equivalent to MIPS only if all database vectors x_i have the same magnitude (are normalized).
• Therefore, standard ANN indexes optimized for L2 or cosine distance require algorithmic adaptation or data transformation to solve MIPS accurately.

A common technique solves MIPS by transforming vectors so the problem becomes Euclidean Nearest Neighbor search. The maximum inner product search transformation appends extra dimensions to each vector.

• For a database vector x, create a new vector x' = [x; √(M² - ||x||²)] where M is a constant larger than the norm of any x.
• For the query vector q, create q' = [q; 0].
• It can be shown that ||q' - x'||² = ||q||² + M² - 2(q ⋅ x). Since ||q||² + M² is constant for a given query, minimizing this transformed Euclidean distance is equivalent to maximizing (q ⋅ x).
• This allows the use of highly optimized L2-ANN indexes like HNSW or IVF after the transformation.

MIPS is the fundamental retrieval mechanism in modern, large-scale recommendation systems.

• Two-tower models: A user tower and an item tower generate embeddings u and i. The prediction score is s(u, i) = u ⋅ i.
• At serving time, for a given user u, the system must find the items i in a corpus of millions or billions that maximize this score. This is a pure MIPS problem.
• Performance is critical: latency must be milliseconds, and recall must be high to ensure relevant items are not missed. This drives the need for highly optimized MIPS-ANN indexes.

In real-world applications, MIPS is rarely performed in isolation. It is typically combined with metadata filters in a hybrid search pipeline.

• Example: "Find movies with high predicted relevance (MIPS) that are also Comedies released after 2010 and available in the user's region."
• This requires an index that can efficiently execute a filtered MIPS query, where the search is constrained to vectors satisfying metadata conditions.
• Implementation strategies include:
  • Pre-filtering: Applying metadata filters first, then performing MIPS on the subset.
  • Post-filtering: Performing MIPS first, then filtering the results (risk of insufficient final results).
  • Integrated indexes: Using specialized data structures like Faiss IDSelector or vector databases with native filtered search support.

Approximate Nearest Neighbor Search (ANN) is a class of algorithms designed to find vectors in a dataset that are most similar to a query vector with high probability, trading off perfect accuracy for significantly faster, sub-linear query times compared to exhaustive search. ANN is the overarching framework within which MIPS is often solved.

• Key Relationship to MIPS: Many MIPS problems are transformed into standard nearest neighbor search problems (e.g., using Euclidean distance on normalized vectors) so that standard ANN indexes like HNSW or IVF can be applied.
• Core Trade-off: All ANN algorithms, including those used for MIPS, navigate the recall-latency trade-off, balancing result accuracy against query speed.

Cosine similarity is a metric that measures the cosine of the angle between two non-zero vectors, quantifying their orientation similarity irrespective of their magnitude. It is defined as the dot product of the vectors divided by the product of their L2 norms.

• Relationship to MIPS: For L2-normalized vectors, cosine similarity is mathematically equivalent to the inner product (dot product). Therefore, MIPS on normalized vectors is identical to a maximum cosine similarity search.
• Common Use Case: This equivalence is why many text and image embedding models (e.g., from sentence transformers) output L2-normalized vectors, allowing standard cosine-similarity ANN indexes to perform MIPS efficiently.

Asymmetric Distance Computation (ADC) is a method for estimating the distance (or similarity) between a raw, uncompressed query vector and a database vector that has been compressed using quantization (e.g., via Product Quantization).

• Principle: ADC computes the distance between the raw query and the quantized database point. This is more accurate than Symmetric Distance Computation (SDC), which compares two quantized vectors.
• Critical for MIPS with Compression: When using compression techniques like Product Quantization (PQ) to reduce memory footprint, ADC is essential for accurately approximating inner products. The IVFADC index combines an Inverted File with ADC for efficient, compressed MIPS.

The k-Nearest Neighbors (k-NN) problem involves finding the 'k' vectors in a dataset that are closest to a query vector according to a specified distance metric, such as Euclidean distance (L2) or cosine distance.

• MIPS as a Special Case: MIPS can be framed as a k-NN problem where the "closeness" metric is the negative inner product (since maximizing the inner product is equivalent to minimizing its negative). However, the negative inner product does not satisfy all metric axioms, complicating direct use of metric-based indexes.
• Transformation to Metric Space: A common technique is to transform vectors by appending a zero or using the MIPS-to-L2 transformation (e.g., adding a dimension), converting the MIPS problem into a standard Euclidean nearest neighbor search.

The recall-precision trade-off in ANN and MIPS search describes the inverse relationship where increasing the search scope or computation to improve recall (finding all true top matches) typically comes at the cost of higher latency and computational load.

• Recall@K: The primary metric for MIPS accuracy, measuring the fraction of the true top-K highest inner product vectors returned by the approximate search.
• Engineering Control: This trade-off is managed via algorithm parameters:
  • Graph-based (HNSW): efSearch (size of the dynamic candidate list).
  • IVF-based: nprobe (number of cells to search).
  • Increasing these parameters improves recall but linearly increases query time.