Maximum Inner Product Search (MIPS)

MIPS is the core mathematical operation behind collaborative filtering and matrix factorization models like Word2Vec and GloVe. When user and item embeddings are learned such that a high dot product indicates preference, MIPS efficiently retrieves top-K recommendations. For example, in a movie streaming service, a user's embedding is dotted with all movie embeddings to find the most relevant suggestions.

• Key Models: Matrix Factorization, Neural Collaborative Filtering.
• Optimization: Algorithms like ScaNN are specifically tuned for the MIPS objective.

In Retrieval-Augmented Generation (RAG), Dense Passage Retrievers often use a dual-encoder architecture. The relevance score between a query and a passage is computed as the dot product of their dense embeddings. MIPS is therefore the retrieval mechanism. This is distinct from cosine similarity search, as the model is trained end-to-end to maximize the inner product for relevant pairs.

• Architecture: Query encoder and passage encoder produce embeddings in the same vector space.
• Training: Uses a contrastive loss (e.g., negative log-likelihood) where positive pairs have high inner products.

The scaled dot-product attention layer in Transformer models is a batched, in-memory MIPS operation. For each query vector (Q), it computes the dot product with all key vectors (K) in a sequence. The resulting scores determine the attention weights for the value vectors (V). Optimizing this operation is critical for inference latency in large language models.

• Operation: Attention(Q, K, V) = softmax((Q * K^T) / sqrt(d_k)) * V
• Scale: This is performed for every token and across multiple attention heads, making it a massive computational bottleneck.

In pointwise and pairwise learning-to-rank approaches, a scoring function f(q, d) often takes the form of an inner product between learned query and document representations. During the ranking phase, MIPS is used to find the documents with the highest predicted scores for a given query. This applies to web search, ad placement, and content ranking.

• Model: The scoring model is typically a shallow neural network whose final layer is a dot product.
• Efficiency: Fast MIPS enables real-time re-ranking of large candidate sets.

In probabilistic models like topic modeling (e.g., Latent Dirichlet Allocation) or sparse coding, inference often involves finding the latent representation that maximizes the posterior probability given observed data. This optimization problem frequently reduces to a MIPS problem in the latent space. Efficient MIPS algorithms accelerate the E-step of the Expectation-Maximization algorithm.

• Mathematical Form: argmax_z P(z | x) ∝ argmax_z log P(x | z) + log P(z).
• Reduction: Under certain exponential family distributions, this becomes an inner product search.

While cosine similarity is a common metric, for unit vectors (embeddings normalized to length 1), cosine similarity is equivalent to the inner product: cos(q, d) = q · d. Therefore, any system using cosine similarity with normalized embeddings is a MIPS problem. This includes many semantic search systems built on models like Sentence-BERT, where embeddings are L2-normalized as a standard practice.

• Critical Detail: The equivalence argmax(q · d) = argmax(cos(q, d)) holds only if ||d|| is constant. For normalized vectors, this is true.
• Optimization: ANN libraries like Faiss provide IndexFlatIP for direct inner product search on normalized vectors.

A family of algorithms designed to efficiently find vectors in a high-dimensional dataset that are most similar to a query vector. ANN is the foundational problem that MIPS is often reduced to for efficient solving.

• Key Trade-off: Sacrifices perfect accuracy for orders-of-magnitude reductions in search latency and computational cost.
• Relation to MIPS: Many MIPS problems are transformed into nearest neighbor search via techniques like adding a dimension or using asymmetric transformations, then solved with ANN algorithms.
• Common Use: Enables real-time semantic search and recommendation over billion-scale vector datasets.

The fundamental engineering compromise in approximate search systems, where increasing search accuracy (recall) typically requires more computational work and time (latency).

• Governed by Parameters: In algorithms like HNSW (efSearch) and IVF (nprobe), tuning these parameters adjusts this trade-off.
• System Design Impact: Drives architectural choices like multi-stage retrieval, where a fast, low-recall first stage is followed by a slower, high-precision reranker.
• SLA Definition: Critical for defining production service-level agreements, where P95 or P99 latency targets are set against minimum recall thresholds.

A leading vector compression technique that enables billion-scale search in memory-constrained environments by drastically reducing storage footprint and accelerating distance computations.

• Mechanism: Decomposes the high-dimensional vector space into subspaces, quantizes each independently, and represents vectors as short codes.
• Memory Efficiency: Can reduce vector storage by 96-99% (e.g., from 4KB to 64 bytes per vector), allowing massive datasets to reside in RAM.
• Hybrid Indexes: Often combined with Inverted File Index (IVF) in the IVFPQ method, which first prunes search space via clustering, then uses PQ for fine-grained comparison.

A state-of-the-art, graph-based approximate nearest neighbor search algorithm known for its high recall and low query latency.

• Graph Structure: Constructs a multi-layered graph where long-range connections on top layers enable fast, greedy traversal to the query's neighborhood.
• Parameter efSearch: Controls the size of the dynamic candidate list during search, directly managing the recall-latency trade-off.
• MIPS Adaptation: While designed for Euclidean distance, HNSW can be applied to MIPS by using the negative inner product as a distance function or via other transformations.

A cascaded retrieval architecture that optimizes the overall precision-latency trade-off by employing successive, increasingly accurate but slower search stages.

• First Stage: Uses a fast, approximate method (e.g., ANN/MIPS over a compressed index) to retrieve a broad candidate set (e.g., 1000 documents) with high recall.
• Second Stage: Applies a computationally intensive, precise model (e.g., a cross-encoder reranker) to the smaller candidate set to achieve high final precision.
• System Benefit: Provides near the accuracy of a brute-force search at a fraction of the cost and latency, making it essential for production RAG and search systems.