Track B · Document 09 · Embeddings and index
The baseline that is not an index, the one that divides the space, and the one that walks a graph — with the arithmetic that decides which of them you should be running.
An index is a structure built on top of your data so you can find things without scanning everything — exactly like the index at the back of a textbook. The word then gets used in three different senses, often inside one sentence, and being precise about which one you mean is a genuine architect-level signal.
“Index choice — flat, IVF, HNSW, DiskANN or ScaNN” means sense (a) literally: which search structure do you build over your vectors. That is the subject of this document and the next one.
Flat search compares the query against every vector and returns the exact top k. There is no structure, no build step, no parameters and no approximation. It is the thing every other index in this runbook is trying to avoid doing — and understanding precisely why it is slow is what makes the rest make sense.
The 50 GB/s default is deliberately conservative. A modern server socket advertises more, but you rarely see the sticker number in practice — and planning against the advertised figure is how capacity estimates end up wrong by a factor of two. Move the slider to see how little the conclusion changes.
Under roughly 100,000 vectors, a flat scan is a few milliseconds.
Exact answers, zero parameters, nothing to rebuild, nothing to tune. Take it.
A user who can see 500 chunks does not need a graph over ten million.
Scanning 500 vectors exactly is sub-millisecond and it is perfect recall.
Flat is how you measure every approximate index.
Run flat once over a sample to get the true top k, then measure what your ANN index returned against it. Without this you have no recall number at all.
A million 768-dimension vectors is 61 ms and about sixteen queries a second per node.
And more cores do not help.
Every approximate index has a recall figure, and a recall figure requires knowing the true answer. Flat search over a sample of your own corpus is where that truth comes from. If a vendor quotes latency without recall, the number is meaningless — you can always be fast if you are allowed to be wrong.
The first real index. Group the vectors into buckets once, at build time; at query time work out which few buckets the answer is probably in, and read only those.
A centroid is not a real vector. It is the average position of the vectors assigned to it — a made-up point that sits at the middle of its group, recomputed until it stops moving. Nothing is stored there; it exists only to answer “which bucket is this query nearest to?”
The clustering step is simpler than it sounds, and being able to describe it plainly is worth more than naming it.
nlist points at random through the space — these are the starting centroidsTwo things follow that people get wrong. A centroid is not a real vector — it is an average position, a made-up point at the middle of its group, and nothing is stored there. And the buckets are semantic, not logical: they group vectors by meaning, because meaning is all the clustering could see. No metadata influenced them, which is why filtering interacts badly with IVF and is the subject of document 14.
Two knobs, and they are not independent. What actually determines the work is the fraction of the corpus you scan, which is a function of both.
“What nprobe should I use?” has no answer without nlist. Push nlist to 10,000 at the same nprobe and the bucket scan gets ten times smaller while the routing scan gets ten times larger — and recall drops, because your true neighbours are now spread across ten times as many buckets. They are one decision expressed as two numbers.
The suffix says how the vectors inside the buckets are stored. The IVF part — centroids, buckets, routing — is identical in all three.
| Variant | Storage inside a bucket | 1M × 768-d | Recall |
|---|---|---|---|
| IVF-Flat | Uncompressed, exactly as the model produced them | 3.07 GB | Highest. The only approximation is routing — if the right bucket is opened, the right answer is found exactly |
| IVF-SQ | Each value compressed from four bytes to one | 768 MB — 4× | One to two points lower, and most of that is recoverable by rescoring the top candidates |
| IVF-PQ | The vector is split into sub-vectors, each replaced by a codebook identifier | ~96 MB — 32× | Materially lower, and effectively requires rescoring. Document 12 |
Four times fewer bytes to move means roughly four times faster scanning at the same nprobe, on the same hardware. That is why the suffix is a performance decision as much as a memory one — and why quantisation helps IVF more than it helps a graph index, which is a point that comes back in section 9.
nprobe is the dial you turn in production; nlist is the number you have to get right at build time. Deal with them in that order, because only one of them is expensive to change.
| nprobe | Vectors scanned | % of corpus | Recall@10 |
|---|---|---|---|
| 1 | ~2,000 | 0.2% | ~0.65 |
| 4 | ~5,000 | 0.5% | ~0.82 |
| 8 | ~9,000 | 0.9% | ~0.88 |
| 16 | ~17,000 | 1.7% | ~0.94 |
| 32 | ~33,000 | 3.3% | ~0.97 |
| 64 | ~65,000 | 6.5% | ~0.99 |
| 128 | ~129,000 | 12.9% | ~0.995 |
1M vectors, nlist = 1000, indicative figures for a typical text corpus. Note the shape: the first few probes buy enormous amounts of recall and the last few buy almost nothing while costing linearly more. Find the knee on your own gold set and sit just past it.
The weak answer is “square root of N”. It is a real heuristic and it is often roughly right — but reciting it demonstrates nothing and it cannot respond when the budget changes. Derive it, then check that the answer is in the same neighbourhood as the heuristic; if it is wildly different, one of your other assumptions is wrong.
Four failure modes, and the first one is not a bug — it is what partitioning is.
This is the structural cost of prune-by-region, and it is the reason IVF recall has a ceiling you buy your way up rather than a bug you fix.
| Failure | What happens | What to do |
|---|---|---|
| Boundary loss | A query near a boundary has its true neighbours split across regions; the ones you did not probe are never read | nprobe above 1. This is the whole purpose of the knob |
| Centroid drift | Centroids were fitted to the corpus as it was. As content is added they no longer sit at the middle of anything, and recall decays without any change on your side | Refit periodically. Track recall on the gold set as the early warning — the decay is gradual and nothing alerts on it |
| Bucket imbalance | Real corpora are lumpy, so one bucket ends up holding a disproportionate share. Every probe that opens it is slow, so your p99 is decided by whichever queries land there | Check the bucket size distribution, not the mean. A long tail there is a latency tail here |
| Filters | Buckets are semantic, so a metadata filter scatters its matches across all of them and post-filtering discards most of what you scanned | This is IVF’s structural weakness and the main reason graph indexes dominate in filtered workloads. Document 14 |
A different idea entirely. Instead of dividing the space into regions, connect every vector to its nearby neighbours and walk towards the query — on a stack of graphs that gets coarser as you go up.
Nobody chose four layers. It fell out of the random draws — each vector picks its own top layer from a distribution shaped by M, and the pyramid narrows by roughly a factor of M each level. This is a skip list generalised from one dimension to many, and if you have seen skip lists the express-lane intuition transfers directly.
Forget layers for a moment. M is about a single vector’s address book. A vector sitting in layer zero surrounded by a million others cannot know about all of them — that would be flat search again — so it keeps a short list of vectors near it. M is how many entries that list holds. At M = 32 it stores thirty-two identifiers, and that is the entire definition.
| What M is | What M is not |
|---|---|
| The width of every step. When the walk arrives at a node, the engine reads its M entries, scores the query against those M vectors, and hops to the closest. No list, no way to move | Not the number of layers. The layer count is not a setting at all — it falls out of the random draws |
| One list per layer. A vector present in three layers holds three separate address books: far-apart neighbours up top, close ones at the bottom | Not a guarantee. It is a cap. A node in a sparse region still gets filled to M, but with whatever is least far away — which is the origin of the local-minimum failure |
M has two effects at once, because the level multiplier that decides how fast the pyramid narrows is itself derived from M. Raise M and you get richer neighbour lists and a shallower hierarchy. One number, two structural consequences — which is why it is tuned carefully in document 11 and why changing it means a rebuild.
Layer zero is usually allowed a larger cap, commonly 2×M, because it does the precision work and benefits from richer connectivity.
Search enters at the top layer, descends greedily to get roughly right, and then runs a beam search at layer zero to get exactly right. efSearch is the width of that beam.
efSearch is not how many neighbours you read — that is M. It is how many good candidates you remember while walking, and it is the one knob you can change per query without rebuilding anything.
Two questions decide whether the graph is worth it: how much work does a query do, and how much memory does the structure add.
And the sensitivity, so you are not caught out. Raise efSearch and HNSW does more hops and more random reads, narrowing its advantage. Raise nprobe and IVF moves more sequential bytes, widening its disadvantage. Neither number is a property of the algorithm; both are properties of the operating point you chose.
At a million vectors that difference is academic. At a hundred million it is the deciding factor: IVF’s overhead is a rounding error and HNSW’s is another machine. And it gets worse under compression — quantising the vectors to int8 takes the table from 3.07 GB to 768 MB while the graph does not shrink at all, because identifiers are identifiers. The overhead ratio jumps from 8.5 percent to about 34 percent.
You cannot cleanly delete a node from an HNSW graph. Removing it would break the neighbour lists of every node pointing at it, potentially disconnecting whole regions. So engines tombstone: mark the vector deleted, keep it in the graph as a routing waypoint, and filter it out of the results.
The consequence is worth stating: HNSW handles inserts incrementally and gracefully, and does not handle deletes at all. A corpus with heavy deletion still needs a rebuild cadence — a useful nuance when somebody claims a graph index has no maintenance burden, and the reason dead vectors are a large line in the capacity arithmetic of document 12.
A greedy walk can arrive somewhere with no neighbour closer to the query than the current node, and stop — while the true answer sits in a region the graph never connected to. Two things guard against it: efSearch above 1, which keeps several candidates alive so the walk can back out of a dead end; and efConstruction, which decides how carefully the neighbour lists were built in the first place. Sparse regions of the space are where this bites, because a node there is filled to M with whatever is least far away rather than with genuine neighbours.
Six dimensions, and the honest summary is that HNSW wins the one people care about most and loses the ones that decide large deployments.
One nuance worth volunteering: quantisation makes HNSW’s structural cost proportionally worse. Compressing vectors to int8 takes the table from 3.07 GB to 768 MB, but the graph does not shrink — identifiers are identifiers. The overhead ratio jumps from about 8.5 percent to about 34 percent.
“How much data, how much RAM, and what is the write pattern? HNSW wins on latency-per-recall and takes incremental inserts gracefully, so it is the default for interactive search. IVF is cheaper in index memory by more than an order of magnitude and rebuilds cleanly, so it wins when the corpus is large enough that the graph overhead becomes a machine, or when the corpus is rebuilt in bulk anyway, or when I intend to quantise heavily — because quantisation helps sequential scanning more than random access.
And if the whole thing does not fit in RAM, both answers are wrong and the conversation moves to DiskANN.”
| Symptom | Most likely cause | What to check first |
|---|---|---|
| Latency is fine, CPU looks healthy, and throughput will not rise with more cores | Flat search — you are bandwidth-bound, not compute-bound | Bytes scanned per query against memory bandwidth. Stalled cores report as busy |
| Recall is stuck around 0.65 no matter how you tune | nprobe = 1, or efSearch equal to k | Both defaults are wrong. nprobe 1 loses every boundary query; efSearch = k leaves no room to explore |
| Recall decayed slowly over months and nothing changed | IVF centroid drift — the corpus moved away from the clustering | When k-means last ran, and gold-set recall over time |
| p99 is far worse than p50 on an IVF index | Bucket imbalance — some queries open a very large bucket | The distribution of bucket sizes, not the mean |
| Raising nlist made recall worse | At fixed nprobe, more buckets means each covers less space, so a fixed probe count covers less of the neighbourhood | Whether nprobe was raised alongside nlist. They move together |
| Memory is far higher than vectors × dimensions × 4 | The graph, if HNSW — about 8.5% at fp32 and about 34% once quantised | N × 2M × 4 bytes. And then document 12 for the other five additions |
| Deleting a lot of content did not free any memory | Tombstones. A graph node cannot be removed without breaking its neighbours’ lists | Compaction or rebuild cadence |
| Filtered queries are far slower than unfiltered ones on IVF | Buckets are semantic, so the filtered subset scatters across all of them | Selectivity, and whether the engine filters during the scan or after it — document 14 |
| Build takes far longer than expected | HNSW builds by inserting every vector, and each insertion is itself a search | efConstruction, and whether the build is parallelised at all |
ArchitectWhy is flat search slow, and why does adding cores not fix it?
Because it is a bandwidth problem rather than a maths problem. Every query reads every vector, so the time is bytes divided by memory bandwidth — a million 768-dimension float32 vectors is 3.07 GB, and at a realistic 50 GB/s that is about 61 ms.
Cores do not help because bandwidth is a socket-level shared resource: a second concurrent query does not get its own bus, it competes for the same one. So a 64-core machine gives roughly the same flat throughput as an 8-core machine. The operational tell is distinctive — CPU graphs look healthy while latency collapses, because a stalled core still reports as busy.
ArchitectExplain IVF to me.
Partition the space once at build time with k-means into nlist buckets, each with a centroid that is the average position of its members. At query time, score the query against the nlist centroids, rank them, open the nearest nprobe buckets, and scan every vector inside those exactly.
Two things worth adding. A centroid is not a real vector — it is a made-up average, and nothing is stored there. And the buckets are semantic: they group by meaning, because meaning is all the clustering could see, which is exactly why metadata filtering interacts badly with IVF.
ArchitectHow would you choose nlist?
I would derive it from the latency budget rather than recite the square-root rule. Four steps: how many vectors can I scan in the budget, at my bandwidth; keep about forty percent headroom; divide by the nprobe I intend to use, which gives vectors per bucket; and divide the corpus by that to get nlist.
On fifty million vectors with a ten-millisecond budget that lands around eight thousand, which happens to be near √N — and that agreement is a coincidence of the example. The point of deriving it is that it responds when the interviewer halves the budget mid-answer, and the heuristic cannot, because it does not know the budget exists.
ArchitectWhat is the difference between nlist and nprobe, operationally?
nlist is set at build time — changing it means new k-means, new assignment, new memory layout, a full rebuild. nprobe goes in the request, so it is per query, with no rebuild, no restart and no deploy.
That asymmetry has a direct design consequence: derive nlist carefully and correct nprobe by measurement. And it enables a genuinely useful production pattern — different nprobe values for different traffic classes against one index, so an interactive path can run cheap and an analytical path can run thorough.
ArchitectExplain HNSW, and what M and efSearch each control.
A stack of graphs over the same vectors. Layer zero holds everything; each layer above is a shrinking random sample, roughly one in M. Search enters at the top, takes long coarse hops to get roughly right, and descends to layer zero for short precise steps.
M is how many neighbours each node keeps — the width of every step, and a build-time decision because changing it means rebuilding. efSearch is the size of the candidate shortlist kept during the bottom-layer walk — how many good candidates you remember, not how many you read — and it is a per-query dial. The one rule is that efSearch must exceed k, or every slot in the shortlist is an answer and there is no room to explore.
ArchitectIVF or HNSW?
I would ask three things first: how much data, how much RAM, and what the write pattern is. HNSW wins on latency at equal recall — it scores about two thousand vectors where IVF scores seventeen thousand, because it reads a route rather than a region — and it takes incremental inserts gracefully.
IVF wins on index overhead by more than an order of magnitude, about 0.1 percent against 8.5 percent, which is academic at a million vectors and another machine at a hundred million. It also rebuilds fast and benefits more from quantisation, because sequential scanning is bandwidth-bound and random access is latency-bound.
So: HNSW by default for interactive search; IVF when memory overhead dominates at scale, when the corpus is rebuilt in bulk anyway, or when I intend to quantise heavily. And if the whole thing does not fit in RAM, both are wrong and the conversation moves to DiskANN.
ArchitectWhy does an approximate index lose recall at all?
Because both mechanisms deliberately decline to look at most of the corpus, and sometimes the answer is in what they declined to look at. For IVF it is boundary loss: a query near a boundary has its neighbours split across regions, and the ones you did not probe are never read — not ranked low, never read. For HNSW it is the walk terminating in a local minimum, or the beam being too narrow to hold a promising detour.
In both cases the recall loss is silent: you get k results with plausible scores. Which is why every ANN index needs a recall figure measured against flat search on your own corpus, and why a latency number quoted without one means nothing.
Eng managerThe team says search got slower after a data load. Where do you point them?
First, which index. On IVF I would look at bucket imbalance and drift — a bulk load into a clustering fitted to older data both skews the bucket sizes and moves the corpus away from the centroids, so p99 rises before p50 does and recall decays without anything alerting. The check is the bucket size distribution and gold-set recall over time.
On HNSW I would look at whether the working set still fits in memory, because the graph walk is random access and it falls off a cliff the moment it starts touching disk. Both are capacity questions wearing a performance costume, which is usually the right first hypothesis after a data load.
Eng managerHow do you decide when to rebuild an index?
On evidence rather than a calendar, and there are three signals worth watching. Gold-set recall drifting down, which catches IVF centroid drift. The proportion of tombstoned vectors, which catches the delete problem — a graph index cannot reclaim that space any other way. And resident memory rising while the live count is flat, which is the same thing seen from the infrastructure side.
I would set thresholds on those and let them trigger the rebuild, and I would size the machines so a rebuild is possible at all — a node at 85 percent memory is a node that can never be reindexed, which is a capacity decision made months earlier.
Is HNSW always better than IVF?
For latency at equal recall on a corpus that fits in memory, usually yes, and that is why it is the default nearly everywhere. It loses on index overhead by roughly twenty-five times, on build time, on delete handling, and on how much it gains from quantisation. At a hundred million vectors those stop being footnotes: the graph is a machine, the rebuild is a day, and the compression you need to fit at all helps IVF more.
Can I change M without rebuilding?
No. M determines the size of every neighbour list in the structure, so changing it means building the structure again — hours of CPU on a large index, though the vectors themselves are untouched and there is no re-embedding. This is why M sits in the middle of the cost hierarchy rather than at the cheap end, and why efSearch is the knob you reach for first.
What is a sensible starting point for M and efSearch?
M of 16 to 32 and efSearch of 64 to 128 will be in the right neighbourhood for most text corpora, with efConstruction somewhere around 200. But treat those as a starting point for a sweep rather than an answer — document 11 derives all three from a budget, which is what an interviewer is actually asking for when they ask about defaults.
Does IVF have anything equivalent to efSearch?
nprobe plays the same role: a per-query dial that trades latency for recall without touching the structure. The difference is what the dial buys. Raising nprobe reads more regions, sequentially; raising efSearch keeps more candidates alive during a walk, randomly. Same shape of tradeoff, completely different cost profile on the hardware.
Why is the HNSW layer count not a parameter?
Because each vector draws its own top layer at random from a distribution whose shape is set by M. The pyramid narrows by roughly a factor of M per level, so a million vectors at M = 32 lands at four or five layers — nobody chose that. It is a good detail to volunteer, because the follow-up question is usually “so how do you tune the depth?” and the answer is that you tune M and the depth follows.
Is IVF-PQ the same thing as product quantisation?
IVF-PQ is IVF with product quantisation applied to the vectors inside the buckets. The two are separable ideas that compose: IVF decides which vectors you look at, PQ decides how compactly each one is stored. Document 12 covers PQ properly, including the confusing part — that IVF and PQ both use k-means, for completely different purposes.
What happens to HNSW if the index does not fit in RAM?
It falls apart, and faster than intuition suggests. The walk is random access across the whole graph, so once pages start coming from disk you are paying a disk seek per hop rather than a memory read — and there are dozens of hops per query. This is precisely the gap DiskANN was built for, and it is the subject of the next document.
How do I measure recall if I do not know the true answer?
Compute it with flat search over a sample. Take a few hundred real queries, run an exact scan over the corpus (or a large representative sample of it) to get the true top k, then measure what your approximate index returned against that. It is slow and it does not matter, because you run it offline. Without this step you have latency numbers and no idea what they cost you.
“Flat search compares against everything, so its cost is bytes over bandwidth — about 61 milliseconds for a million 768-dimension vectors, and more cores do not help because bandwidth is shared at the socket. It is still what I use as ground truth, because every approximate index needs a recall number measured against something exact.
IVF partitions the space with k-means into nlist buckets and opens the nearest nprobe of them at query time, so it prunes by region — and once you pick a bucket you read all of it. nlist is a rebuild and nprobe is a request parameter, so I derive nlist from the latency budget and correct nprobe by measurement.
HNSW is a stack of graphs: coarse layers for long jumps, layer zero for short precise ones. M is how many neighbours each node keeps and efSearch is how many candidates the walk holds alive. It prunes by path, scoring about two thousand vectors where IVF scores seventeen thousand, so it wins latency at equal recall — and it costs roughly twenty-five times more index memory, builds slower, and cannot really delete.
Default HNSW for interactive search. Reach for IVF when the graph overhead becomes a machine, when the corpus is rebuilt in bulk anyway, or when I intend to quantise heavily.”
| Thread from this document | Resolved in |
|---|---|
| Why deleting from a graph index leaves the memory behind | 03 · Identity, updates and deletes |
| Why a restrictive filter fights a graph walk | 04 · Access control and freshness |
| When neither of these fits in RAM | 10 · DiskANN, ScaNN and choosing |
| Deriving M, efConstruction, efSearch, nlist and nprobe properly | 11 · Parameters and the tuning runbook |
| What the suffixes SQ and PQ actually do to a vector | 12 · Quantisation and capacity |
| Selectivity bands, and filtering during the walk | 14 · Filtered search and multi-tenancy |
| Measuring recall against a flat baseline | 16 · Evaluation and observability |