At real-world scale, you can’t look at everything.

A search engine with billions of pages can’t score every document per query. A recommendation system with millions of items can’t run a heavy model on each one in real time. The first challenge is narrowing this massive pool to a small, relevant set fast.

Embedding-based retrieval does exactly that. It maps queries and items into the same vector space and uses approximate nearest neighbor search to quickly find the closest matches.

Traditional retrieval relies on exact matching. Keyword search with inverted indexes (BM25, TF-IDF) works well when users type queries that literally match document terms. But it breaks down in three situations:

Even setting aside semantic limitations, brute-force scoring doesn't scale. If your ranking model takes 1ms per item and your catalog has 100 million items, scoring everything takes 100,000 seconds per query. You need a way to pre-filter candidates to a few hundred or a few thousand before the expensive ranking model sees them.

Embedding-based retrieval doesn't replace keyword search entirely. In practice, most systems combine both: BM25 for exact lexical matches and embedding retrieval for semantic matches, then merge the candidate sets before ranking.

The core idea is straightforward: map both queries and items into vectors in the same high-dimensional space (typically 64-768 dimensions), then find items whose vectors are closest to the query vector.

The process has two phases:

Offline (index build)

Encode every item in the catalog through the item encoder to produce a vector. Build an ANN index over all item vectors. For 100 million items with 256-dimensional embeddings, this index might take 100-200 GB of memory depending on the algorithm.

Online (query time)

Encode the incoming query through the query encoder to get a query vector. Search the ANN index for the top-K nearest vectors. Return those items as retrieval candidates. This typically takes 1-10ms regardless of catalog size.

The similarity metric is usually dot product or cosine similarity. Dot product is faster to compute and allows the model to learn both relevance and item "quality" through vector magnitude. Cosine similarity normalizes vectors to unit length, focusing purely on directional similarity. In practice, most production systems use dot product because it gives the model more expressive power.

The query and item encoders can share weights (a siamese architecture) or have completely separate architectures (a dual encoder). Most production systems use dual encoders because queries and items are fundamentally different types of input.

The critical architectural choice here is that queries and items are encoded independently. The query encoder never "sees" any specific item when producing the query vector, and vice versa. This independence is what makes the pattern scalable:

The trade-off is that independent encoding limits how much the model can capture query-item interactions. A query vector and an item vector can only interact through their dot product, which is a single number. More complex interactions (like "this word in the query matches that phrase in the document") get compressed away. This is why embedding retrieval is a candidate generation step, not the final ranker.

The next chapter covers the two-tower architecture in detail, including training strategies like contrastive loss and hard negative mining that make these dual encoders work well in practice.

Exact nearest neighbor search computes the distance between the query vector and every item vector, which is O(N) per query. For 100 million items, that's too slow. Approximate nearest neighbor (ANN) algorithms trade a small amount of recall for massive speed improvements, going from O(N) to O(log N) or better.

Three families of ANN algorithms dominate production systems: graph-based (HNSW), partition-based (IVF), and compression-based (product quantization). Most real systems combine two or three of these.

HNSW (Hierarchical Navigable Small World)

HNSW builds a multi-layer graph where each node is a vector and edges connect nearby vectors. The top layers are sparse (long-range connections for fast navigation), and the bottom layers are dense (short-range connections for precision).

Search starts at the top layer and greedily moves to the nearest neighbor at each step. Once it can't get closer at the current layer, it drops down to the next layer (which has more connections) and continues. This is similar to how skip lists work for sorted data, but in high-dimensional space.

HNSW's strength is consistently high recall (95-99%) with low latency (sub-millisecond for millions of vectors). The downside is memory: it stores the full vectors plus the graph edges, which typically adds 1.5-2x overhead on top of the raw vector data.

IVF (Inverted File Index)

IVF partitions the vector space into clusters using k-means. At query time, it identifies the closest cluster centroids and only searches vectors within those clusters.

The key parameter is nprobe, the number of clusters to search. With 1000 clusters and nprobe=10, you search only 1% of the data. Higher nprobe gives better recall at the cost of higher latency. Typical values range from 8 to 64.

IVF is faster to build than HNSW and uses less memory since it doesn't store graph edges. But recall is generally lower for the same latency budget because cluster boundaries can split genuinely similar items.

Product Quantization (PQ)

Product quantization is a compression technique, not a search algorithm on its own. It splits each vector into subvectors, then quantizes each subvector to the nearest centroid in a learned codebook. A 256-dimensional float32 vector (1024 bytes) can be compressed to 32-64 bytes with PQ, a 16-32x memory reduction.

The compressed vectors enable approximate distance computation without decompressing. This makes PQ essential when your index needs to fit in memory but the raw vectors are too large. The accuracy loss from quantization is typically small (1-3% recall drop) but compounds as you compress more aggressively.

Combining Algorithms

Production systems rarely use a single algorithm in isolation. The most common combinations:

Libraries like FAISS (Meta), ScaNN (Google), and Annoy (Spotify) implement these algorithms. Managed vector databases like Pinecone, Weaviate, and Milvus handle the infrastructure layer on top.

A common production pattern is a two-phase search: use IVF+PQ for a fast initial search that returns 10x the final candidate count, then re-rank those candidates using exact distance on the full (uncompressed) vectors. This gets you the memory savings of PQ with recall close to exact search.

Building an ANN index over 100 million vectors takes minutes to hours depending on the algorithm and hardware. The real operational challenge isn't the initial build, it's keeping the index fresh as your catalog changes.

New items added after index construction don't exist in the index. For a video platform uploading 500,000 new videos daily, those videos are invisible to embedding retrieval until the next index rebuild. This is the freshness problem.

Three strategies for managing index freshness:

Periodic full rebuild is the simplest approach. Rebuild the entire index every few hours or daily. Swap the old index for the new one atomically. This works well when your catalog doesn't change rapidly and a few hours of delay for new items is acceptable.

Incremental updates add new vectors to an existing index without rebuilding. HNSW supports this natively since adding a node just means connecting it to nearby nodes in the graph. IVF is harder to update incrementally because adding items to existing clusters skews the cluster distribution over time. After enough incremental updates, a full rebuild restores optimal cluster balance.

Sidecar index is the production-grade approach for high-churn catalogs. Keep a large, periodically rebuilt main index alongside a small, frequently updated sidecar index. Query both, merge results. YouTube and similar systems use this pattern: the main index covers the stable catalog, while the sidecar catches recently uploaded content. The sidecar is small enough to rebuild in minutes.

Deleted items are typically handled with a filter rather than removing them from the index. The ANN search returns candidates, and a post-retrieval filter removes any that have been deleted, flagged, or are otherwise ineligible. Rebuilding the index to remove deleted items happens during the periodic full rebuild.

Embedding-based retrieval is the right choice when you need to find semantically similar items from a large catalog at low latency. But it's not always the right tool.

A common mistake is reaching for embedding retrieval when simpler approaches work. If your catalog has 5,000 items and a basic collaborative filtering model retrieves good candidates in 10ms, adding an embedding layer and ANN index adds complexity without meaningful improvement.

Another mistake is using embedding retrieval as the only retrieval source. Production search and recommendation systems almost always use multiple retrieval paths (embedding-based, keyword-based, popularity-based, user-history-based) and merge the candidate sets. This covers different types of relevance that no single method handles alone.

Every design decision in embedding-based retrieval involves a trade-off. The table below summarizes the main dimensions:

Embedding dimension has diminishing returns. Going from 64 to 256 dimensions meaningfully improves representation quality. Going from 256 to 768 helps less but doubles memory and slows ANN search. Most production systems settle between 128 and 256.

Recall vs latency is the central ANN trade-off. You can always improve recall by searching more of the index (higher ef_search in HNSW, higher nprobe in IVF), but each increment adds latency. The goal is to find the knee of the curve where you get 95%+ recall within your latency budget.

K (number of candidates) determines how much work the downstream ranking model has to do. Retrieving more candidates improves the chance that the best item is in the set, but ranking 2,000 candidates costs 10x more compute than ranking 200. The right K depends on the ranking model's cost and the diversity requirements. YouTube retrieves around 1,000 candidates from embedding retrieval, while simpler systems might retrieve 100-300.