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.
Compare the query against every vector, return the exact top k. No structure, no build step, no parameters, no approximation. It is the thing every other index is trying to avoid doing — and understanding precisely why it is slow is what makes the rest make sense.
Bandwidth is a socket-level shared resource: a second concurrent query does not get its own bus, it competes for the same one. A 64-core machine gives roughly the same flat throughput as an 8-core one.
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.
Under about 100,000 vectors. For a small entitled set — exact search on 500 vectors is sub-millisecond and it is perfect recall. And as ground truth, offline, where slowness does not matter.
Flat search would compare the query against every vector.
k-means finds nlist centroids; every vector is assigned to its nearest; the vectors are physically reordered so each bucket is contiguous.
Score the query against the centroids — nlist comparisons, the routing scan.
Open the nearest nprobe buckets. Here, two of five.
Every vector inside them, exactly. The other three were never read.
1. Scatter nlist points at random — the starting centroids. 2. Assign every vector to its nearest. 3. Move each centroid to the average position of what it holds. 4. Repeat until they stop moving — usually a few dozen passes.
They group by meaning, because meaning is all the clustering could see.
Uncompressed, exactly as the model produced them.
Each value compressed from four bytes to one.
The vector is split into sub-vectors, each replaced by a codebook id.
Four steps. How many vectors can I scan in the latency budget, at my bandwidth? Keep about forty per cent headroom. Divide by the nprobe I intend to use — that gives vectors per bucket. Divide the corpus by that to get nlist.
nlist is build-time: changing it means new k-means, new assignment, new memory layout, a full rebuild. nprobe goes in the request — per query, no rebuild, no restart, no deploy.
A query lands near a boundary, so its true top ten is split across two regions.
The neighbours on the other side are unreachable.
nprobe above 1. Hedging across the nearest few regions is exactly what the knob is for.
A bulk load into a clustering fitted to older data skews bucket sizes and moves the corpus away from its centroids.
Connect every vector to its nearby neighbours and walk towards the query — on a stack of graphs that gets coarser as you go up.
1,000,000 nodes.
A shrinking random sample — roughly one in M.
Long coarse hops to get roughly right.
Short precise steps to get exactly right.
The width of every step. When the walk arrives at a node, the engine reads its M entries and scores them. One list per layer — a vector present in three layers holds three separate address books.
Not the number of layers. The layer count is not a setting at all — it falls out of the random draws. And 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.
Pick the best unexplored candidate on the shortlist.
Read its M neighbours and score them.
Merge in, keep the best efSearch, drop the rest.
Stop when the best unexplored is already worse than the worst held.
Or every slot in the shortlist is an answer and there is no room to explore — recall collapses.
~260 MB of edge lists at 1M × M=32.
Centroids plus a directory.
Roughly 25× the index overhead of IVF.
Scores ~2,000 vectors where IVF scores ~17,000.
0.1% overhead against 8.5%.
The graph walk is random access across the whole structure, so once pages come from disk you are paying a disk seek per hop — and there are dozens of hops per query.
Why is flat search slow, and why do cores not fix it?
How would you choose nlist?
Explain HNSW, and what M and efSearch control.
IVF or HNSW?
Why does an approximate index lose recall at all?
The team says search got slower after a data load.
QIs HNSW always better than IVF?
For latency at equal recall on a corpus that fits in memory, usually — which is why it is the default nearly everywhere. It loses on index overhead by ~25×, on build time, on delete handling, and on how much it gains from quantisation. At a hundred million vectors those stop being footnotes.
QCan I change M without rebuilding?
No. M determines the size of every neighbour list, so changing it means building the structure again — hours of CPU, though the vectors themselves are untouched and there is no re-embedding. Which is why efSearch is the knob you reach for first.
QWhat is a sensible starting point for M and efSearch?
M 16–32, efSearch 64–128, efConstruction around 200. But treat those as a starting point for a sweep rather than an answer — deriving all three from a budget is what an interviewer is actually asking for.
QDoes IVF have anything equivalent to efSearch?
nprobe plays the same role — a per-query dial trading latency for recall without touching the structure. The difference is what the dial buys: nprobe reads more regions, sequentially; efSearch keeps more candidates alive during a walk, randomly. Same tradeoff, completely different cost profile on the hardware.
QWhy 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 1M at M=32 lands at four or five layers — nobody chose that. Good to volunteer, because the follow-up is “so how do you tune the depth?” and the answer is you tune M.
QIs IVF-PQ the same thing as product quantisation?
IVF-PQ is IVF with PQ applied to the vectors inside the buckets. Two separable ideas that compose: IVF decides which vectors you look at, PQ decides how compactly each is stored. And the confusing part — both use k-means, for completely different purposes.
QWhat happens to HNSW if the index does not fit in RAM?
It falls apart, faster than intuition suggests. The walk is random access across the whole graph, so once pages come from disk you pay a disk seek per hop — and there are dozens of hops per query.
QHow do I measure recall if I do not know the true answer?
Compute it with flat search over a sample. A few hundred real queries, an exact scan 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.
Every approximate index is a decision to not look at most of your corpus — and the recall you lose is the part it declined to look at, returned silently with plausible scores. IVF declines by region and fails at boundaries; HNSW declines by route and fails in local minima. So the number that makes any latency figure meaningful is recall measured against flat search on your own corpus — because you can always be fast if you are allowed to be wrong. And the choice between them is three questions: how much data, how much RAM, and what the write pattern is.
Which index type, and why that one?
What is your measured recall, and against what ground truth?
Is nprobe or efSearch tuned per traffic class, or global?
Does the whole index fit in RAM on one node?
For IVF: when was the clustering last refitted, and has recall drifted?
What triggers a rebuild — a calendar, or a signal?