Maximum Inner Product Search (MIPS)

MIPS formalizes retrieval as: given a query vector q and a database of document vectors D, return the document d* that maximizes the inner product ⟨q, d⟩. This is mathematically equivalent to finding the nearest neighbor under cosine similarity when all vectors are L2-normalized. The dot product captures both the magnitude and direction of vectors, making it sensitive to both semantic relevance and document importance.

A naive linear scan computes ⟨q, d⟩ for every document, which is O(N) per query. For modern vector databases containing billions of embeddings, this is computationally prohibitive. MIPS algorithms trade a small, controlled amount of accuracy for orders-of-magnitude speedups, typically achieving sub-linear or logarithmic query times. This trade-off is essential for production systems requiring sub-100ms latency.

MIPS is a specific instance of the broader Approximate Nearest Neighbor (ANN) problem. While ANN traditionally targets Euclidean or cosine distance, MIPS directly optimizes for the inner product metric. Key algorithms adapted for MIPS include:

• HNSW: Builds a navigable small-world graph where edges connect vectors with high inner products
• IVF: Partitions the space using k-means and only searches the most promising clusters
• FAISS: Provides native MIPS support via IndexIVFFlat and IndexHNSWFlat with METRIC_INNER_PRODUCT

In dense retrieval systems like DPR, the query encoder and document encoder are independently parameterized. This creates an asymmetric search scenario: the query vector q and document vectors d reside in the same space but are produced by different functions. MIPS algorithms must handle this asymmetry without assuming a single generative distribution, which complicates indexing strategies that rely on symmetric distance properties.

A common technique transforms MIPS into a standard nearest neighbor problem by appending an additional dimension. Given vectors q and d, we construct augmented vectors q' and d' such that Euclidean distance between them preserves the inner product ordering. This allows any ANN library optimized for L2 distance to perform MIPS without modification. The transformation relies on knowing the maximum norm of document vectors.

Billion-scale MIPS requires compressing vectors to fit in RAM. Product Quantization (PQ) decomposes each d-dimensional vector into m sub-vectors and quantizes each independently using a learned codebook. This reduces memory from d × 32 bits to m × log₂(k) bits, where k is the number of centroids per sub-space. The inner product is then approximated efficiently using precomputed distance lookup tables, enabling sub-millisecond search over compressed representations.

The primary evaluation metric for MIPS-based retrieval systems, measuring the proportion of truly relevant items that appear within the top-K retrieved results.

• Formula: Recall@K = |Relevant ∩ Retrieved@K| / |Relevant|
• A retriever with Recall@100 = 0.95 finds 95% of all relevant documents in its top 100 results
• Complementary metric: MRR evaluates ranking quality of the first relevant result
• In RAG pipelines, higher Recall@K directly correlates with answer quality
• Typical production targets: Recall@100 > 0.90 for open-domain QA