• Problem: given a query vector u, find the closest item vectors among billions. Exact search = one dot product per item = linear, too slow online.
• ANN finds the approximately closest vectors in roughly log time. Trade a tiny bit of recall for a huge speedup.
• This is the concrete mechanism that makes Two-Tower Model retrieval fast over billions of items.

Common methods

• HNSW (graph-based): a navigable small-world graph; walk greedily toward the query. Fast, high recall, memory-heavy.
• IVF (inverted file / clustering): cluster vectors, search only the nearest few clusters.
• Product Quantization (PQ): compress vectors into codes so more fit in memory and distances are cheap. Often combined with IVF.

Libraries

• FAISS (Meta), ScaNN (Google). Production vector search uses these under the hood.

Trade-off to state

• Higher recall ↔ more clusters/graph search ↔ higher latency. You tune the recall/latency point for the product.

References