liveBook · Manning

Approximate nearest neighbor search

As explained in Retrieval Augmented Generation, The Foundational Ideas

Approximate nearest-neighbor search efficiently finds vectors close to a query vector without exhaustively comparing every stored vector.

Approximate nearest-neighbor (ANN) search finds vectors close to a query without comparing the query with every stored vector. It trades some recall for much lower latency, making semantic search practical when collections contain millions or billions of items. section 2.2 section 2.2.1

The baseline is exact brute-force similarity search: calculate the query's similarity with every vector and rank the results. This works on small collections but becomes unusable for global catalogs or billions of documents. ANN indexing replaces exhaustive comparison with a faster search strategy, while evaluation must balance recall, latency, and memory. section 2.2.1 section 2.2.3

Production ANN design commonly weighs these concerns:

  • Use approximation when a small loss in recall is preferable to query times that users will not tolerate. section 2.2.3
  • Choose an indexing strategy according to required recall, speed, and memory use rather than treating complexity as automatically better. section 2.2.3
  • Monitor latency, recall, and memory as the index grows, because operational behavior can drift over time. section 2.2.3

From a small catalog to enterprise retrieval

Comparing a query with roughly 6,500 movie embeddings requires fewer than one million floating-point operations and can take a fraction of a millisecond. Applying the same exhaustive method to Amazon's catalog of more than 200 million items or to billions of web documents makes real-time retrieval impractical; ANN enables the scale required by interactive semantic search and RAG. section 2.2.1 section 2.2.3

Figure 2.3 FAISS's Two-Stage Search Strategy.

Use the two-stage search diagram to distinguish indexed candidate retrieval from the broader similarity-search problem. section 2.2.1

How Retrieval Augmented Generation, The Foundational Ideas covers it

How deep it goes
Contrasts brute-force and approximate search, then emphasizes recall, latency, memory, and monitoring without detailing index internals.
Examples
Uses movie embeddings, Amazon's 200-million-item catalog, and billion-document web search as scale comparisons.
What it assumes
Assumes vector similarity and exact brute-force search, while grounding scale problems through embedding and cosine-similarity examples.
What you can do after
Evaluate ANN deployments by balancing recall, query latency, memory use, and index-growth behavior.
How it connects
Connects vector embeddings, cosine similarity, semantic search, FAISS, and retrieval-augmented generation.

Also explained in

Compare how 7 books explain 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.