Atlas Vector Search looks, from the outside, like one more aggregation stage: you hand $vectorSearch a query vector and it hands back the nearest documents. Underneath it is a Lucene HNSW index, and every knob it exposes — numCandidates, quantization, filter — is a dial on an explicit maths trade between recall, latency, and RAM. Get the arithmetic wrong and you either pay for four times the hardware you need or quietly ship a retriever that misses a third of the relevant documents with no error at all. This piece works through that maths from first principles: the cost of the exact search you approximate, the graph that replaces it, what quantization buys, why filtering is the sharpest edge, and how to turn it all into a node count you can budget.
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.
Why pre-filtering still degrades, and the ENN escape hatch
Pre-filtering is the right default, but it is not free, for a structural reason. The HNSW graph was built over all N points; its edges encode proximity in the unfiltered space. When you mask out (1 - s) of the nodes, you walk a subgraph whose edges were never chosen with that subset in mind. A node with 2M neighbours retains about 2M * s usable ones:
M = 16, 2M = 32 edges per node
s = 0.10 → ~3.2 live neighbours (navigable, some recall loss)
s = 0.01 → ~0.3 live neighbours (graph fragments; greedy walk stalls)Below a percent or so of selectivity the filtered subgraph shatters into disconnected islands and the greedy descent dead-ends far from the true neighbours. The right response is not to raise numCandidates, which spends latency fighting a topology problem, but to switch to exact: true: a brute-force scan over the fifty thousand survivors is both fast and exactly right. Selective filter, small survivor set, use ENN is one of the most reliable rules here.
A cost model you can actually budget with
Everything above collapses into one question: how many search nodes, each with usable RAM R, does the index need? Dedicated Search Nodes isolate this memory pressure from the operational database, so the two do not evict each other’s working sets.
index_GB = N * d * B / 1e9 + N * 2M * 4 * 1.07 / 1e9
nodes = ceil( index_GB * overhead / R ) * replicas overhead ≈ 1.25
N = 20e6, d = 1536, M = 16, R = 60 GB usable, replicas = 2
fp32 : 122.9 + 2.7 = 125.6 GB → ceil(157/60) = 3 → 6 nodes
scalar : 30.7 + 2.7 = 33.4 GB → ceil( 42/60) = 1 → 2 nodes
binary : 3.8 + 2.7 = 6.5 GB → ceil( 8/60) = 1 → 2 nodesScalar quantization takes this deployment from six nodes to two for a recall cost typically under a point — a two-thirds saving from one line in an index definition. Note that binary and scalar land on the same node count here: once the index fits comfortably, further compression buys nothing on the bill and only costs recall. Compress until you fit, then stop.
Pitfalls worth internalising
A short list of failures that happen in production, each a direct consequence of the maths above:
| Symptom | Cause | Fix |
|---|---|---|
Returns fewer than limit results | Filtering after the stage, not inside it | Move the predicate into filter; declare the field as type filter |
| Recall collapses for one tenant | Selectivity below ~1%; subgraph fragmented | Switch to exact: true on selective filters |
| p99 latency far above median | Index exceeds RAM; graph walk hitting disk | Quantize, or add a node |
The unifying theme is that none of these raise an exception. Approximate search degrades quietly by definition, so the only real defence is measurement: keep a few hundred labelled queries, run them periodically against an exact: true baseline, and track recall as a first-class production metric alongside latency.
O(N*d) scan with a logarithmic descent through a layered proximity graph; numCandidates buys recall with per-query latency, while efConstruction buys it with one-off build time, so be generous with the second and careful with the first. Quantization is the biggest lever on cost — scalar gives roughly 3.7× and binary roughly 20×, both short of the vector-only ratio because the graph does not compress — but compress only until the index fits in RAM, then stop. Filtering is the sharpest edge: pre-filter inside the stage, never after it, and when selectivity falls below about a percent the graph fragments, so switch to exact search. Above all, approximate retrieval fails silently — measure recall against an exact baseline in production, or you will not find out.