Semantic Search at Scale: From Theory to Production

The billion-point wall

In 2019, a team at Microsoft Research India in Bengaluru — Suhas Jayaram Subramanya and colleagues — published a paper with a blunt title: DiskANN, "Fast Accurate Billion-point Nearest Neighbor Search on a Single Node" (NeurIPS 2019). The problem they were solving was not "how do we search text semantically" — that part, encoding a query into a dense vector and comparing it against document vectors, you already know how to do. The problem was that once a catalog crosses a few hundred million vectors, the search itself stops being a modeling question and becomes a systems-engineering question: the index no longer fits in RAM, brute-force comparison no longer fits in a latency budget, and every trick you use to fix one of those breaks something else. This chapter is about that layer — the part of semantic search that sits between "we have embeddings" and "users get an answer in under 100 milliseconds against a billion-row index." A companion chapter in this curriculum covers how embedding models are trained and how a RAG pipeline is assembled end to end; this one assumes vectors already exist and asks a narrower, harder question: how do you find the nearest ones, fast, at scale, without lying too much about which ones are actually nearest?

Why brute force fails: the arithmetic

Start with the naive approach: given a query vector, compute its cosine similarity (equivalently, dot product, if vectors are pre-normalized) against every vector in the index, then sort. For a typical dense embedding of dimensionality d = 768 (the size used by models like BGE-large or many sentence-transformer checkpoints), a single dot product costs 768 multiplications and 768 additions — call it roughly 1,536 floating-point operations per comparison.

Now scale to a realistic production catalog: n = 100 million vectors — not an exaggeration for a large e-commerce or document-search system. One query costs:

100,000,000 comparisons × 1,536 FLOPs = 1.536 × 10^11 FLOPs = 153.6 GFLOPs

A single CPU core doing scalar floating-point work sustains roughly 5–10 GFLOP/s in practice once memory bandwidth and cache misses are accounted for (this is not a peak theoretical number — it is what a naive loop over 768-dimensional arrays actually achieves, because at 100 million vectors the working set blows through L2 and L3 cache on every query). At 10 GFLOP/s:

153.6 GFLOPs / 10 GFLOP/s ≈ 15.36 seconds per query

Even with aggressive SIMD vectorization pushing a core to 50 GFLOP/s, that is still 153.6 / 50 ≈ 3.07 seconds. A production search SLA is typically 50–150 milliseconds end to end, including network hops, reranking, and response assembly — brute force is two to three orders of magnitude too slow before you have spent a single millisecond on anything else. This is the wall every large-scale semantic search system hits, and the rest of this chapter is a tour of the three engineering responses to it: approximate search structures that skip most of the comparisons, compression that shrinks what has to be compared, and hybrid retrieval that fixes what approximation quietly breaks.

Approximate nearest neighbor: the honest tradeoff triangle

Every production vector index makes a deliberate trade: it gives up the guarantee of finding the true top-k nearest neighbors in exchange for speed and memory. The quality metric is recall@k — of the true top-k nearest vectors (as brute force would find them), what fraction did the approximate index actually return? A system reporting 92% recall@10 means that on average, roughly 9 of the 10 results shown to the user are genuinely among the 10 closest vectors in the embedding space; one slipped through the approximation.

Three quantities are in permanent tension: recall (how close to exact), latency (query time), and memory (index size, which determines how many machines and how much RAM/SSD you need). Every algorithm below is a different point on this three-way tradeoff surface, and every production tuning knob — cluster count, graph degree, quantization bits — is a dial that moves you along it. There is no configuration that maximizes all three simultaneously; understanding the mechanism of each structure is what lets you pick the right point deliberately instead of by trial and error.

Clustering the space: inverted file (IVF) indexes

The oldest and still most widely deployed idea (formalized in the Faiss library by Johnson, Douze, and Jégou, "Billion-scale similarity search with GPUs," IEEE Transactions on Big Data, vol. 7, no. 3, 2021 (originally arXiv 2017), though the underlying inverted-file concept predates it) is to partition the vector space into clusters using k-means, then at query time only search the clusters whose centroids are closest to the query — skipping the rest of the dataset entirely.

Concretely: run k-means offline to produce nlist centroids, and assign every one of the n indexed vectors to its nearest centroid, forming nlist inverted lists. At query time, compare the query against all nlist centroids, pick the nprobe closest clusters, and only scan the vectors inside those clusters.

Worked numbers: take n = 100,000,000, and choose nlist = 10,000 clusters (a standard heuristic keeps clusters at roughly √n to a few × √n; here average cluster size = n / nlist = 10,000). Set nprobe = 8, meaning we search the 8 nearest clusters out of 10,000.

centroid comparisons:        nlist            = 10,000
in-cluster comparisons:      nprobe × (n/nlist) = 8 × 10,000 = 80,000
total distance computations: 10,000 + 80,000  = 90,000
reduction vs brute force:    100,000,000 / 90,000 ≈ 1,111×

That is the entire mechanism: a ~1,111× cut in distance computations for one query, at the cost of possibly missing a true neighbor whose vector happened to fall into one of the 9,992 unprobed clusters — which is exactly why IVF's recall depends on nprobe, and why doubling nprobe roughly doubles latency while only partially closing the recall gap (returns diminish because the clusters probed second are, by construction, farther from the query than the ones probed first).

Shrinking the vectors: product quantization

IVF reduces how many vectors you compare; product quantization (PQ), introduced by Jégou, Douze, and Schmid ("Product Quantization for Nearest Neighbor Search," IEEE TPAMI 2011), reduces how much each vector costs to store and compare. The idea: split each d-dimensional vector into m contiguous sub-vectors, and for each of the m sub-spaces independently, learn a small codebook of 256 centroids via k-means (256 because that fits in a single byte, 2⁸). Every vector is then stored not as d floats, but as m single-byte codes — the index of the nearest centroid in each sub-space.

Take the same 100-million-vector, 768-dimensional catalog, with m = 96 subquantizers (chosen so that d/m = 8 dimensions per sub-vector, a common ratio in practice):

d = 768
n = 100_000_000

uncompressed_bytes = d * 4 * n          # float32 vectors
m = 96                                   # number of PQ subquantizers
sub_dim = d // m                         # dimensions per subvector
compressed_bytes = m * n                 # 1 byte (256 centroids) per subvector

print(f"sub_dim = {sub_dim}")
print(f"uncompressed = {uncompressed_bytes / 1e9:.1f} GB")
print(f"compressed   = {compressed_bytes / 1e9:.1f} GB")
print(f"ratio        = {uncompressed_bytes / compressed_bytes:.0f}x")

Traced by hand: uncompressed_bytes = 768 × 4 × 100,000,000 = 307,200,000,000 → 307.2 GB. compressed_bytes = 96 × 100,000,000 = 9,600,000,000 → 9.6 GB. Running this exact script confirms it:

sub_dim = 8
uncompressed = 307.2 GB
compressed   = 9.6 GB
ratio        = 32x

A 32× memory reduction — turning a catalog too large for a single machine's RAM into one that comfortably fits — at the cost of approximating every distance computation using only the quantized codes (asymmetric distance computation, ADC, precomputes distances between the query and each of the 96 × 256 codebook centroids once per query, then looks up and sums 96 values per candidate instead of doing 768 multiplications). This is why PQ and IVF are almost always combined in production (Faiss's IVF-PQ index): IVF cuts how many vectors are touched, PQ cuts what touching one costs.

Graph-based search: HNSW

A different family of index skips clustering entirely and instead builds a navigable graph over the vectors, introduced by Malkov and Yashunin ("Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs," IEEE TPAMI 2018). HNSW builds several layers of graphs stacked on top of each other. The bottom layer, Layer 0, contains every single point in the dataset, each connected to a handful of its approximate nearest neighbors. Each higher layer contains a randomly chosen, exponentially shrinking subset of those same points (the probability a point is promoted to layer l decays roughly as 1/2ˡ), with sparser but longer-range connections.

A query is answered by greedy search: start at a fixed entry point in the topmost, sparsest layer. At each step, move to whichever neighbor of the current node is closer to the query than the current node itself; when no neighbor is closer (a local minimum for that layer), drop down one layer at the same point and repeat the greedy walk with access to a denser set of edges. By the time the walk reaches Layer 0, it has already been steered into the right neighborhood of the space using only a handful of long hops, and the final layer's dense connectivity refines the answer with short hops among many candidates — most of which exist nowhere except this bottom layer.

Trace the highlighted path in the diagram: the walk starts at the amber entry point in Layer 2, hops once to a closer node in the same sparse layer, drops down to Layer 1 at that node, hops again to a closer neighbor using the denser mid-layer edges, drops to Layer 0, and takes one final short hop to a point that exists only at Layer 0 — most of the dataset was never promoted to a higher layer, which is exactly why the algorithm needs the bottom layer to be exhaustive even though the top layers are sparse. Total edges examined on this walk: five, against a graph that might hold a hundred million points. That logarithmic-ish hop count (empirically close to O(log n) for well-tuned graphs) is HNSW's entire advantage over IVF's cluster-scan approach, at the cost of a different resource: the full graph, with all its edges, must live in RAM, since graph traversal is fundamentally a pointer-chasing, latency-sensitive operation that page faults badly.

Beyond RAM: DiskANN and SSD-resident indexes

That RAM requirement is precisely the wall DiskANN was built to break through. HNSW's graph plus full-precision vectors for a billion 768-dimensional points would require well over a terabyte of RAM — economically painful and, at the largest scales, physically unavailable on a single node. DiskANN's answer is the Vamana graph algorithm: build a single-layer graph (no hierarchy) with a carefully bounded out-degree and a specific edge-pruning rule that guarantees good navigability even when most of the graph lives on SSD rather than RAM. Only a compressed, PQ-quantized version of every vector stays in memory for fast approximate distance checks during the walk; the full-precision vector and its graph neighbor list are fetched from SSD only when the walk actually visits that node, and modern NVMe random-read latency (tens of microseconds) is fast enough that a handful of such fetches per query stays within budget. The result, as reported in the original paper, was billion-point search on a single commodity machine with an SSD, at latencies competitive with pure-RAM graph indexes on far smaller datasets — the systems contribution was not a smarter distance metric, it was accepting that memory is a scarce resource and designing the graph's access pattern around a slower, cheaper storage tier.

Hybrid retrieval: fusing lexical and semantic signals

Common misconception: a frequent assumption is that dense semantic search strictly dominates classic keyword search (BM25) — that since embeddings understand meaning, they should win on every query. This is false, and the failure mode is specific and important: dense embeddings are trained to cluster semantically similar text together, which means they systematically under-discriminate on exact, low-frequency tokens — SKU numbers, GST identifiers, model numbers, error codes, a specific IRCTC PNR-format string. Two product descriptions differing only in a part number often land extremely close together in embedding space, because the training signal never taught the model that "XJ-4471" and "XJ-4472" are supposed to be far apart — nothing about their semantic content differs. BM25, built on exact term-frequency statistics, will always separate those correctly. Production systems that rely on one method exclusively (Vespa, Weaviate, and Elasticsearch's vector modes all learned this the same way) converge on hybrid retrieval: run both a lexical index and a dense ANN index for every query, and fuse the two ranked lists.

The dominant fusion method is Reciprocal Rank Fusion (RRF), from Cormack, Clarke, and Buettcher ("Reciprocal Rank Fusion Outperforms Condorcet and Individual Rank Learning Methods," SIGIR 2009). RRF deliberately ignores the raw similarity scores from each retriever — BM25 scores and cosine similarities live on incompatible scales and are not safely comparable — and instead uses only rank position:

RRF(d) = Σ over each ranked list containing d of  1 / (k + rank(d))

with k = 60 conventionally, chosen to dampen the dominance of any single rank-1 result and let cross-list agreement matter more. Worked example: a BM25 search returns [A, B, C]; a dense ANN search on the same query returns [B, D, A]. Run this exact fusion function:

def reciprocal_rank_fusion(rankings, k=60):
    scores = {}
    for ranking in rankings:
        for rank, doc_id in enumerate(ranking, start=1):
            scores[doc_id] = scores.get(doc_id, 0.0) + 1.0 / (k + rank)
    return sorted(scores.items(), key=lambda x: x[1], reverse=True)

bm25_ranking = ["A", "B", "C"]
dense_ranking = ["B", "D", "A"]

fused = reciprocal_rank_fusion([bm25_ranking, dense_ranking])
for doc_id, score in fused:
    print(f"{doc_id}: {score:.6f}")

Tracing by hand: A gets 1/(60+1) from BM25 plus 1/(60+3) from dense = 1/61 + 1/63 = 0.032266. B gets 1/(60+2) from BM25 plus 1/(60+1) from dense = 1/62 + 1/61 = 0.032522. C appears only in BM25 at rank 3: 1/63 = 0.015873. D appears only in dense at rank 2: 1/62 = 0.016129. Running the script confirms it exactly:

B: 0.032522
A: 0.032266
D: 0.016129
C: 0.015873

Notice what happened: B, which was only rank 2 on BM25, overtakes A (rank 1 on BM25) because B also ranked highly on the dense side — cross-method agreement wins. And D, found only by the dense retriever, outranks C, found only by BM25, purely because D's single rank (2) was better than C's single rank (3). This is the mechanism, not a side effect: RRF rewards a document for showing up near the top of any list, which is exactly the property you want when combining a lexical signal (good at exact matches) with a semantic signal (good at paraphrase and intent).

Late interaction reranking: ColBERT

Fusion improves the candidate set; reranking refines the final order among the top few hundred candidates using a more expensive, more accurate model. The most accurate option, a cross-encoder, concatenates the query and each candidate document and runs a full transformer forward pass per pair — accurate, but with a cost that scales linearly with candidates evaluated per query, since nothing about a document can be precomputed (the query and document attend to each other jointly). Khattab and Zaharia's ColBERT ("Efficient and Effective Passage Search via Contextualized Late Interaction over BERT," SIGIR 2020) is the alternative used at scale: encode every token of every document independently and offline, storing one contextual embedding per token. At query time, encode only the query's tokens (cheap — one short forward pass), then score each candidate document with a MaxSim operator: for every query token, take the maximum cosine similarity against any of that document's precomputed token embeddings, and sum across query tokens. Nothing about the document requires a fresh transformer pass at query time; the expensive joint computation a cross-encoder redoes for every query is replaced by a lightweight sum of dot products against embeddings computed once, offline, and reused for every future query. The tradeoff for this speed is storage: ColBERT keeps one embedding per document token instead of one per document, multiplying index size by average document length in tokens — a cost that is usually worth paying only for the reranking stage, over a few hundred candidates, not the full billion-point retrieval stage.

Production system tradeoffs

Two engineering problems recur once these pieces are assembled into a live system. First, sharding: a billion-vector index does not fit on one machine even after PQ compression, so it is partitioned across nodes — either by hashing vectors to shards (simple, but every query fans out to every shard) or by clustering vectors so that semantically related content lands on the same shard (harder to build, but a query can sometimes be routed to fewer shards). Either way, results from all queried shards must be merged and re-sorted before returning to the user, and that merge step needs its own latency budget. Second, metadata filtering — "search these product embeddings, but only within category=electronics and in_stock=true" — interacts badly with graph indexes specifically because of how HNSW navigates: pre-filtering the graph down to only matching nodes before search can sever the very edges the greedy walk relies on to reach a good answer, causing the search to terminate early having wandered into a disconnected pocket of the filtered subgraph, especially when the filter matches a small fraction of the index. Production systems typically compensate with post-filtering plus over-fetch (retrieve, say, 5× the candidates needed, then filter) or specialized filtered-graph variants that maintain connectivity guarantees per attribute value — there is no fully free way to combine hard filters with graph-based ANN.

Active recall

Attempt each question before reading its answer.

1. A catalog has 500 million vectors of dimensionality 512. Using PQ with m = 64 subquantizers and 8-bit codes, compute the compression ratio and total compressed memory footprint.
2. In the RRF worked example above, suppose k is changed from 60 to 0, and the dense ranking is extended to [B, D, A, C] (C now also appears, at rank 4). Recompute the full fused ranking and explain what changed and why.
3. Why can pre-filtering by metadata sometimes cause an HNSW search to return zero or too few results, even when qualifying documents exist in the index?
4. An ANN system returns 10 results for a query whose true top-10 (by brute force) is known; 8 of the 10 returned results are correct. State the recall@10. If the HNSW parameter ef_search (candidate list size explored during the walk) is then halved to cut latency, what happens to this number and why?
5. A cross-encoder reranker scores 100 candidates per query, at 5 ms per (query, document) pair evaluated sequentially. Query volume is 200 queries per second. What raw pair-scoring throughput must the serving system sustain, and why does ColBERT-style late interaction sidestep this bottleneck rather than just requiring more GPUs?
6. True or false, with justification: increasing nlist (the number of IVF clusters) always improves recall for a fixed nprobe.

Answers

1. Uncompressed bytes = 512 × 4 × 500,000,000 = 1,024,000,000,000 = 1,024 GB. Sub-vector dimension = 512 / 64 = 8. Compressed bytes = 64 × 500,000,000 = 32,000,000,000 = 32 GB. Ratio = 1,024 / 32 = 32×. Note this is the same 32× ratio as the chapter's worked example even though n and d both changed — the ratio depends only on (4 bytes per float) × (d/m, the sub-vector dimension), which is 8 in both cases. Total footprint scales with n, but the compression ratio does not; a student who assumed the ratio would change because the catalog got smaller and d got smaller has conflated footprint with ratio.
2. With k = 0, RRF(d) = Σ 1/rank(d). BM25 gives A: 1/1 = 1, B: 1/2 = 0.5, C: 1/3 = 0.3333. Dense (now [B,D,A,C]) gives B: 1/1 = 1, D: 1/2 = 0.5, A: 1/3 = 0.3333, C: 1/4 = 0.25. Totals: A = 1 + 0.3333 = 1.3333, B = 0.5 + 1 = 1.5, C = 0.3333 + 0.25 = 0.5833, D = 0.5. Fused order: B (1.5) > A (1.3333) > C (0.5833) > D (0.5) — verified by running the fusion function with k=0 and the extended lists. Two things changed relative to the k=60 example: first, C now appears in both lists (it was dense-absent before), pulling it decisively ahead of D, which the k=60 version could not show since C wasn't in the dense list at all; second, with k=0 the scores are far more spread out (1.5 vs 0.5, a 3× ratio, versus 0.0325 vs 0.0159, a 2× ratio at k=60) because a rank-1 finish is now worth a full point instead of a small fractional boost — k's job is precisely to prevent one list's rank-1 result from dominating the fused score, and setting it to zero removes that damping.
3. HNSW's greedy walk depends on the graph's edges connecting nodes that are close in the full vector space; applying a metadata filter before search effectively deletes the non-matching nodes from the graph, which can disconnect or badly sparsify the remaining subgraph. The walk can reach a local minimum within the filtered remnant and terminate having never reached the qualifying region of the space, especially when the filter selects a small fraction of the index — the fix is to over-fetch unfiltered candidates and filter afterward, or use a filtered-graph variant that preserves per-attribute connectivity.
4. Recall@10 = 8/10 = 80%. Halving ef_search shrinks the candidate list explored at each layer of the walk, which lowers latency but also increases the chance that the true nearest neighbors are missed because fewer nodes were considered before the walk converged — recall drops below 80%. This is the textbook recall-latency tradeoff: ef_search is a direct dial on it, unlike nlist or m in IVF/PQ which are fixed at index-build time.
5. Required throughput = 100 pairs/query × 200 queries/sec = 20,000 pairs/sec. At 5 ms/pair sequential, one stream manages 1/0.005 = 200 pairs/sec, so roughly 100× parallelism (batching across GPU cores, multiple GPUs, or both) is needed just to keep up — and that cost scales linearly with both candidates-per-query and QPS. ColBERT does not remove this cost by adding hardware; it removes it structurally, since document token embeddings are computed once, offline, and reused for every future query — the only per-query cost is encoding the (short) query and computing MaxSim, a set of dot products, against precomputed vectors, so online compute no longer scales with query volume the way a cross-encoder's joint forward pass does.
6. False. Increasing nlist decreases average cluster size (n/nlist), so for a fixed nprobe the number of vectors actually scanned (nprobe × n/nlist) shrinks — fewer clusters' worth of data is examined per query. Finer partitioning also increases the chance that true nearest neighbors, which may sit near a cluster boundary, land in a different cluster than the query and get skipped entirely if their cluster isn't among the nprobe probed. Recall and nlist have a joint, not a one-directional, relationship: raising nlist without also raising nprobe typically lowers recall, even though it always lowers latency and per-query compute.

Think About It

Think about this: How would you explain semantic search at scale: from theory to production to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind semantic search at scale: from theory to production, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.