The baseline you are approximating
Exact k-nearest-neighbour search over N embeddings of dimension d is a brute-force scan: for each stored vector compute one similarity against the query, keeping a heap of the best k:
V: [N, d] query q: [d]
score_i = sim(q, V_i) for i = 1 .. N
cost = O(N * d) multiply-adds + O(N * log k) heap ops
memory = N * d * 4 bytes (float32)Put numbers on it. With N = 5,000,000 documents and d = 1536, one query touches 5e6 × 1536 ≈ 7.7 billion multiply-adds — hundreds of milliseconds of pure arithmetic before a document is read. Atlas will do this happily ($vectorSearch accepts exact: true), and it is right for small or heavily filtered collections. But the cost is linear in N, and that is the wall every approximate index climbs over. HNSW answers the same question in time closer to O(log N * d), at the price of sometimes returning a neighbour that is merely very good rather than provably best.
The three similarity metrics and why they nearly coincide
An Atlas vector index declares one of euclidean, cosine, or dotProduct, and they are less independent than they look. Expand the squared Euclidean distance:
||q - v||^2 = ||q||^2 - 2 (q · v) + ||v||^2
cos(q, v) = (q · v) / (||q|| * ||v||)
if ||q|| = ||v|| = 1:
||q - v||^2 = 2 - 2 (q · v) = 2 - 2 cos(q, v)On unit-normalised vectors, ranking by Euclidean distance, cosine, and dot product produces identical orderings — the metrics differ only by a monotone transform. It stops being cosmetic once norms vary: un-normalised dotProduct rewards long vectors, so a document can rank highly by being big rather than relevant, while cosine divides that magnitude out. Pick the metric your embedding model was trained under, normalise at write time, and the question disappears.
HNSW: a skip list over a proximity graph
Hierarchical Navigable Small World is a skip list generalised from one dimension to many. Every vector is a node in a proximity graph, and each node is assigned a maximum layer drawn from an exponential distribution:
m_L = 1 / ln(M)
level = floor( -ln(U) * m_L ), U ~ Uniform(0,1)
P(level ≥ l) = M^(-l) → layer l holds ≈ N / M^l nodes
expected layers ≈ log_M(N)Layer 0 contains every node; each layer above holds roughly 1/M of the layer below, so the top is a sparse, long-range sketch of the dataset. A search enters at the top, greedily walks to the neighbour closest to the query, drops a layer when it can no longer improve, and repeats: upper layers cover distance cheaply, lower layers refine. With M = 16 and N = 5e6, that is log_16(5e6) ≈ 5.5 layers, and a query visits a few hundred nodes rather than five million — a linear scan turned into a logarithmic descent.
M, efConstruction, numCandidates: the three real knobs
Each parameter buys recall with a different currency.
| Knob | What it controls | Cost of raising it |
|---|---|---|
M | Edges per node (layer 0 allows up to 2M) | RAM, permanently — the graph is not compressible |
efConstruction | Beam width while building the graph | Index build time only; free at query time |
numCandidates | Beam width at query time | Latency, on every single query |
The asymmetry matters. efConstruction is a one-off tax that improves graph quality forever, so generosity there is nearly free; numCandidates is paid on every query. Atlas requires numCandidates ≥ limit, and useful values sit around 10×–20× the requested limit. Recall against this knob is steeply concave: it climbs quickly, then flattens. Tune it by measuring recall against an exact: true run on a held-out query set, not by intuition.
The RAM formula that decides your bill
HNSW is fast because the graph and the vectors are resident in memory. Spilling to disk does not cost a few percent; it reshapes the whole latency distribution, because a graph walk is a chain of random accesses with no locality. So sizing reduces to one question: how many bytes does the index occupy?
vector bytes = N * d * B B = 4 (fp32), 1 (int8), 1/8 (binary)
graph bytes ≈ N * 2M * 4 (layer-0 neighbour ids, 4-byte ints)
* (1 + 1/(M-1)) upper layers, a small correction
N = 5e6, d = 1536, M = 16, fp32:
vectors = 5e6 * 1536 * 4 = 30.7 GB
graph = 5e6 * 32 * 4 * 1.07 = 0.68 GB
total ≈ 31.4 GBTwo things fall out. The vectors dominate the graph by roughly forty to one, which is why quantization is the highest-leverage change available; and the graph term is fixed, a floor on what any quantization can save.
Quantization: scalar, binary, and the rescoring safety net
Scalar quantization maps each float32 component onto an 8-bit integer using per-dimension bounds learned from a sample, clipped at a quantile so outliers cannot destroy the scale:
scalar: q_j = round( (v_j - lo_j) / (hi_j - lo_j) * 255 )
binary: b_j = 1 if v_j > 0 else 0, distance = popcount(a XOR b)Rerun the RAM model on the same 5 million × 1536 collection. Scalar: 7.7 GB vectors plus the same 0.68 GB graph, about 8.4 GB — a 3.7× reduction, matching the ~3.75× MongoDB cites. Binary: 0.96 + 0.68, about 1.6 GB, roughly 20×. Neither reaches the vector-only ratio of 4× and 32×: the incompressible graph drags the total down, harder the more aggressive the quantization. Binary throws away everything except sign, so Atlas pairs it with rescoring — retrieve an overfetched set by cheap Hamming distance, then re-score those few hundred against the full-fidelity vectors on disk. One small read recovers most of the lost precision, which is why binary plus rescoring typically holds recall in the mid-nineties.
Filtering: the sharpest edge in the system
Real queries are rarely pure vector queries: you want the nearest neighbours among documents this tenant owns, published this year. There are two ways to combine that with a graph search, and they behave very differently. Let s be the selectivity — the fraction of the collection passing the filter.
post-filter: search ANN for C candidates, then drop non-matches
expected survivors = C * s
to return k you need C ≈ k / s
k = 10, s = 0.001 → C ≈ 10,000 (and Atlas caps numCandidates at 10,000)
pre-filter: restrict the graph traversal to matching nodes
cost independent of s, but connectivity degrades as s → 0Post-filtering fails catastrophically and silently on selective filters — it returns three documents where you asked for ten, no error. This is why the filter operand lives inside the $vectorSearch stage rather than a following $match: Atlas applies it as a Lucene pre-filter during traversal. Fields used this way must be declared with type filter, or the query silently degenerates to post-filtering.