Vector indexes

Read these first

• Similarity metrics and matching the metric to the model

What you will know

• Measure recall, latency, and memory for exact search, flat search, IVF, and HNSW on a representative workload

  The useful comparison is the workload-specific Pareto frontier, including resident memory and tail latency rather than just average query time.

• Tune the search-time parameter and show the recall curve

  Search-time parameters move you along a recall-versus-latency curve; find where yours sits.

• Choose between index types for a stated corpus size

  Index type choice follows from corpus size, update rate and memory budget.

• Measure actual recall against exact search

  Measure actual recall against exact search rather than trusting defaults.

• Reproduce a recall failure caused by stale data, metric mismatch, or an under-provisioned index, then patch it

  Normalization, distance functions, deleted vectors, and insufficient graph or probe settings can make a healthy-looking service return systematically wrong neighbors.

Chapters

1. 1

   Exact search is the baseline every index has to beat

   A 200k-chunk corpus at 768 float32 dimensions is roughly 600 MB, and a linear scan over it returns the true top-k in single-digit milliseconds with nothing to tune and no recall to lose. Work that arithmetic yourself, so you can answer the teammate who proposes HNSW at that scale and so every approximate index later has a number to beat rather than an assumption to inherit.

   Read chapter
2. 2

   Index recall and retrieval relevance are two different numbers

   Recall for an ANN index means the overlap between what it returns and what brute-force search would have returned for the same query: a property of the index alone. An nDCG or recall@10 score on a judged query set measures whether the corpus answers the question, and stays put whether the index is 99% faithful or 79%. Here you build the exact-search ground truth the first number is computed against.

   Read chapter
3. 3

   IVF splits the space into cells and nprobe picks how many you visit

   Clustering the corpus into nlist cells turns a search into two steps: find the nearest centroids, then scan only what is inside them. The miss is structural rather than noisy, because a true neighbour sitting just across a cell boundary stays invisible unless nprobe reaches its cell. You will see why nlist is frozen when the index is trained while nprobe stays free on every query.

   Read chapter
4. 4

   M and efConstruction set HNSW's ceiling, ef_search only walks under it

   The layered proximity graph is built once and its links per node are decided then; raising ef_search widens the beam that walks it and buys recall until the graph runs out of edges to follow. That is exactly what a curve climbing from 0.86 to 0.91 and then refusing to move is telling you. Sort M, efConstruction, ef_search, nlist and nprobe into build-time and query-time, and know why that line matters more than any single knob.

   Read chapter
5. 5

   Approximation loss lands on a predictable population of queries

   A recall of 0.86 is not 14% of every query going slightly wrong; it is a specific set of queries going badly wrong while the rest are exact. The ones that lose are the queries whose true neighbours sit in sparse or unusually dense regions of the graph, the ones with many near-ties where a small beam picks an arbitrary subset, the ones far from the distribution the index was built or trained on, and the documents that entered late through incremental insertion with fewer or worse links than their neighbours. Learning to name that population is what lets you predict which queries a defaulted index will fail before you measure, and what gives the next chapters a theory of which failure shapes are possible.

   Read chapter
6. 6

   Sweeping the query-time knob traces the curve you will ship on

   For each ef_search or nprobe value, record three numbers on your own corpus: recall against exact search, p95 latency, and peak resident memory. Do it for exact search, a flat index, IVF and HNSW built over the same data, so the frontier spans index types and not only the knob inside one of them. Average query time hides the tail users actually feel, and a published benchmark on a million SIFT descriptors predicts nothing about three million chunks of your prose. What falls out is a Pareto frontier, and choosing a point on it is the real decision.

   Read chapter
7. 7

   Corpus size, update rate and memory budget narrow the index choice

   HNSW's graph costs memory on top of the vectors and is expensive to rebuild; IVF needs a training pass and decays as new data drifts away from its centroids; flat needs neither and simply stops scaling somewhere. Put all three against a stated corpus — how many vectors, how many queries per second, how often documents change, what the box has — and you are down to one or two candidates before benchmarking anything.

   Read chapter
8. 8

   Systematically wrong neighbours are an index bug, not approximation noise

   When roughly 15% of queries return plainly wrong results at normal latency, with model and metric already confirmed, the shape of that number is the clue: random approximation error does not concentrate on a subset this way. Three index-level causes account for most of it, and each has its own check. Recall that climbs toward exact search as ef_search rises means the search was simply under-provisioned. Work and memory that stay flat while results degrade, with a rebuild restoring them, means tombstoned deletes are still being traversed. Scores that track vector magnitude mean vectors went in unnormalised under an inner-product distance. Reaching for ef_search before running those checks buys latency and, for two of the three, fixes nothing.

   Read chapter