liveBook · Manning

Maximum inner product search

As explained in Retrieval Augmented Generation, The Foundational Ideas

Maximum inner product search finds database vectors having the largest inner products with a query vector.

Maximum inner product search (MIPS) finds the database vectors with the largest inner products with a query vector. In a retrieval-augmented language model, it helps the retriever select documents for the language model to use. The difficult part is keeping search useful while the retriever—and therefore the document embeddings—changes during training. section 3.2

The search strategy differs between training and evaluation:

  • During REALM training, an index builder periodically recomputes document embeddings and supplies a fresh index to the trainer. The trainer continues with a slightly stale index rather than rebuilding one after every gradient update; an example refresh interval is 500 steps. section 3.2
  • For REALM++ final evaluation, exact MIPS replaces approximate nearest-neighbor search. This selects the highest-scoring documents and tests the model weights without approximate retrieval affecting the comparison. section 3.4

MIPS is the search mechanism, not the signal that makes a document useful. In REALM, a document receives a positive retriever update only when using it improves the language model’s task performance relative to the average document. Periodic indexing makes that jointly trained retrieval practical, while exact search provides a clearer evaluation of what the learned vector space can retrieve. section 3.2 section 3.4

How Retrieval Augmented Generation, The Foundational Ideas covers it

How deep it goes
Explains asynchronous index refresh and contrasts exact with approximate search, but does not derive inner-product search algorithms.
Examples
Uses a 500-step index-refresh interval and a switch to exact MIPS for final evaluation.
What it assumes
Assumes familiarity with document embeddings and search indexes; does not teach inner-product search from first principles.
What you can do after
Evaluate/understand it by distinguishing the stale-index compromise during training from exact-search evaluation.
How it connects
Connects document embeddings and search indexes to end-to-end retriever training, masked language modeling, and approximate nearest-neighbor search.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Retrieval Augmented Generation, The Foundational Ideas. The section links point to the parts of the book it draws on.