The job: top-K nearest neighbors, without scanning everything
Formally, you store a set of vectors {v_1, …, v_N} in R^d and, for a query q, want the K items minimizing a distance dist(q, v_i). The honest way is brute force: compute all N distances and keep the smallest K. That is exact and costs O(N · d) per query.
Do the arithmetic and see why that fails at scale. With N = 10^7 vectors of dimension d = 768, one query is roughly 7.7 × 10^9 multiply-adds — tens of milliseconds on a good CPU core, for a single query with no concurrency. Multiply by thousands of queries per second and brute force is hopeless. So the entire field is about avoiding the full scan: pre-build a data structure — the ANN index — that inspects a tiny fraction of the vectors and still usually finds the true neighbors. Everything else exists to feed, filter, scale, and maintain that index.
Embedding storage: the vectors themselves have a price
Before you can search, you have to keep the vectors. Stored densely, a collection is an [N, d] matrix of 32-bit floats: 4 bytes per dimension. The raw-storage math is unforgiving — N = 10^7, d = 768, at 4 bytes is 10^7 × 768 × 4 ≈ 30.7 GB just for the coordinates, before any index overhead.
Alongside each vector the store keeps its ID and a payload of metadata (source document, timestamp, tags, access labels) and often the original text. This is deliberately separated from the index: the index maps vector geometry to candidate IDs, while a key-value or columnar store maps IDs back to full records. That separation lets you rebuild the index without touching the source of truth, and lets metadata filters run against columns the index never sees. The first sizing question in any deployment is whether N × d × bytes fits in RAM — and when it does not, quantization (below) is how you make it fit.
Distance metrics: what , '’': close’ means, and why normalization matters
Three metrics dominate. L2 (Euclidean): ||q - v|| = sqrt(Σ_i (q_i - v_i)^2) — straight-line distance, smaller is nearer. Dot product: q · v = Σ_i q_i v_i — larger is nearer, and it rewards large-magnitude vectors. Cosine: cos(q, v) = (q · v) / (||q|| · ||v||) — the dot product with magnitude divided out, so it measures pure orientation.
The key identity: if every vector is L2-normalized to unit length, then cosine, dot, and L2 rank neighbors identically, because ||q - v||^2 = 2 - 2(q · v) when ||q|| = ||v|| = 1. That is why most pipelines normalize once at insert time and then let the index run the cheaper dot product. Metric-choice note: pick the metric the embedding model was trained with — most sentence and text encoders are cosine-trained, so normalize and use cosine/dot; reserve raw L2 for spaces where magnitude is meaningful, and never mix metrics between index and query.
The ANN index: HNSW, IVF, and PQ as the three families
The index is where the sub-linear magic lives, and three families cover most of it — treated here as pointers, since each deserves its own article. HNSW (Hierarchical Navigable Small World) builds a multi-layer proximity graph: a query greedily walks from a coarse top layer down to dense lower layers, hopping to ever-closer neighbors. Query cost is roughly O(log N) hops, at the cost of a graph that can add 50–100% memory overhead.
IVF (Inverted File) instead partitions the space into nlist cells around centroids; a query probes only the nprobe nearest cells, scanning a small slice of N. PQ (Product Quantization) is orthogonal — it compresses vectors into short codes so distances are estimated cheaply from lookup tables, and is usually layered onto IVF (as IVF-PQ). The single knob every family exposes — efSearch in HNSW, nprobe in IVF — trades how much of the index you touch (latency) for how often you find the true neighbor (recall).
Metadata filtering: pre- vs post-filtering and the recall problem
Real queries are rarely pure geometry. You want ‘nearest vectors where lang = "en" and tenant = 42 and date > 2026-01-01.’ There are two ways to combine the filter with the search, and both have a failure mode.
Post-filtering runs the ANN search first, then discards results that fail the predicate. It is simple and index-agnostic, but if the filter is selective the top-K may be decimated — ask for 10, the index returns its 10 nearest, and 9 get filtered out, leaving one result. You over-fetch (grab top-100, filter, hope 10 survive) and still risk empty pages. Pre-filtering restricts the search to matching IDs first, so every candidate is valid — but it fights the index: a graph walk that can only step to allowed nodes may fragment, and an IVF scan of only matching items may miss cells, both lowering recall. Modern engines compromise with filtered ANN — evaluating the predicate during traversal — but the tension is fundamental: filters and approximate search do not compose for free.
Quantization: buying memory back with a little accuracy
When N × d × 4 bytes will not fit, you shrink each number. Scalar quantization maps each 32-bit float to an 8-bit integer — an instant 4× shrink, turning that 30.7 GB collection into about 7.7 GB with typically negligible recall loss. Product quantization goes further: split the d-dim vector into m sub-vectors, cluster each into 256 centroids, and store m single-byte codes. A 768-dim float32 vector (3072 bytes) becomes m = 96 bytes — a 32× reduction.
The cost is that distances are now estimated from compressed codes, so recall drops — which is why PQ systems keep the full-precision vectors on disk and re-rank the top candidates exactly after the cheap approximate pass. Quantization is the clearest example of the governing trade: you spend accuracy to buy memory, then spend a little latency (the re-rank) to buy some accuracy back. The right setting depends entirely on how much RAM you have and how much recall your application can tolerate.
Sharding and replication: scaling past one machine
Two axes of scale, two different problems. Sharding splits the collection across nodes when it no longer fits — in memory or in query budget — on one machine. Each shard holds a disjoint subset of vectors and its own index; a query fans out to all shards, each returns its local top-K, and a coordinator merges the partial results into a global top-K. Because nearest neighbors can live in any shard, you must query every shard, so tail latency is set by the slowest shard.
Replication copies each shard onto multiple nodes for two reasons: throughput (queries load-balance across replicas) and availability (a node dies, a replica serves). The two combine — S shards each with R replicas is S × R nodes. Sharding divides the data; replication multiplies the copies. Too few shards and each is too big; too many and the fan-out merge and slowest-shard tail dominate.