ANN Index Types
Describe how Flat, IVF and HNSW indexes work and pick one for a given scale and memory budget.
Three ways to organise vectors
A vector index is a structure built ahead of time so that a search can find near neighbours without comparing the query against everything. Dozens of index designs exist, but three cover almost everything you will meet in practice: Flat, IVF and HNSW. Each one makes a different trade between speed, memory, build time and recall (the share of the true nearest neighbours that the search actually finds).
Three common index types. Flat is exact, IVF searches nearby clusters, HNSW walks a graph of neighbours.
Flat: no shortcuts at all
A Flat index is not really an index. It keeps every vector in a list and, for each query, compares the query with all of them. It is exact (recall is always 1.0), it takes no time to build, and it uses no extra memory. Its one weakness is search time, which grows in step with the number of vectors. Flat indexes suit small collections, and they supply the true answers when you test other indexes.
IVF: search only the nearest clusters
Think about how India Post handles a letter. Nobody compares your letter with every address in the country. The PIN code sends it to one sorting district, and only the addresses inside that district are looked at. An IVF index, short for inverted file index, does the same for vectors: it sorts them into districts ahead of time and searches only the districts nearest the query.
To build the index, an algorithm called k-means finds the district centres. It starts with guessed centre points, assigns every vector to its nearest centre, moves each centre to the middle of its vectors, and repeats until the centres settle. Each centre with its vectors is a cluster, and this step is called training. Every vector is then stored in the list of its nearest centre.
To search, the query is compared with the centres first, and only the vectors in the closest few clusters are checked. The number of clusters searched is called nprobe (or probes). A vector near the edge of its cluster can be a true neighbour of a query just across the border, so searching one cluster sometimes misses it. Raising nprobe catches these cases and slows the search.
Explore both settings below.
More clusters means fewer points in each, so one probe does less work, but it also means more borders for neighbours to fall across. IVF adds very little memory on top of the vectors. Its weak point is that the clusters must be trained on a representative sample of the data.
HNSW: hop through a network of neighbours
HNSW stands for Hierarchical Navigable Small World. It was published by Yury Malkov and Dmitry Yashunin in 2016 and has become the most widely used vector index in production.
HNSW builds a graph. Every vector is a point, linked to a handful of its nearest neighbours. Searching means standing on a point, looking at the points it links to, and hopping to whichever is closest to the query. When no linked point is closer than the current one, the search stops. It is how you find a house in an unfamiliar town: ask someone, walk to the person they point to, and ask again.
Hopping between close neighbours is slow over long distances, so HNSW stacks several graphs in layers. Think of travelling from Delhi to one street in Bengaluru: a flight first (few stops, huge jumps), then the metro, then an auto for the last lanes. The top layer holds very few points joined by long links, and the bottom layer holds every vector. A search starts at the top and drops down a layer each time it can get no closer.
Step through a search yourself. Start with one layer, then add the highway layer and compare the number of hops and comparisons.
With only 2 links per point, the walk reaches a dead end: no linked neighbour is closer, although closer points exist. Real HNSW indexes give each point more links, and during a search they keep a short list of the best candidates found so far instead of a single current point, so the search can back out of a dead end. Those two guards are the settings you tune.
| Setting | When it applies | What it controls | Raising it gives |
|---|---|---|---|
| M | Build | How many neighbours each point links to | Better recall, more memory |
| ef_construction | Build | How carefully neighbours are chosen | A better graph, a slower build |
| ef_search | Each query | The length of the candidate list during search | Better recall, slower queries |
A graph search in thirty lines
The program below builds a one-layer graph over 2,000 points and searches it by hopping, exactly as in the lab. The points have only two numbers each so that it runs quickly; the method is the same for 1,024.
Expected output:
query [0.9 0.2]: 25 hops, compared 209 of 2000, found true nearest: True
query [0.5 0.5]: 11 hops, compared 97 of 2000, found true nearest: True
query [0.1 0.9]: 24 hops, compared 201 of 2000, found true nearest: True
| Part of the code | What it does |
|---|---|
links = [...] |
Finds the 8 nearest neighbours of every point. This list is the graph, and building it is the slow part. |
best = min(neighbours, key=dist) |
Looks only at the points linked to the current one and picks the one closest to the query. |
if dist(best) >= dist(current) |
If no linked point is closer, the search has arrived. Otherwise it hops to best and repeats. |
true_nearest = ... |
A Flat search over all 2,000 points, used to check the answer. |
Each search compared about a tenth of the points and still found the true nearest one. Change M to 2 and run it again to see dead ends appear, just as they did in the lab.
Comparing them
| Flat | IVF | HNSW | |
|---|---|---|---|
| Recall | Always exact | Good; depends on nprobe | Very high; depends on ef_search |
| Search speed at large scale | Slow | Fast | Very fast |
| Extra memory | None | Small | Moderate to large |
| Build | Instant | Needs a training step | Slower, no training |
| Adding new vectors | Trivial | Easy (clusters may drift) | Easy |
| Typical use | Small sets, testing | Very large sets, tight memory | Most production search |