The first of three ideas behind modern ANN: cut the vector space into regions so every query only searches the regions that could possibly contain its neighbors.
Part 2 of Approximate Nearest Neighbors
The previous article left us in an awkward place. In high dimensions, a kd-tree's pruning test almost always fails, and the naive linear scan is the only algorithm that still works. Distances concentrate, corners swallow the volume, and the geometry pushes back against anything clever.
But there is an important asterisk on that story. The experiments in Article 1 used points sampled uniformly at random in the unit cube. That is a worst case. Real embeddings never look like that. A sentence embedding from a language model sits in 768 or 1536 dimensions, but the vectors a real corpus actually produces cluster heavily: by topic, by language, by style, by whatever the model learned to care about. The ambient space is high-dimensional, but the data lives on a much lower-dimensional manifold inside it.
This is the opening that partitioning exploits. If the data clumps, we can group those clumps into regions and store the grouping. At query time we find the few regions near the query and scan only those. The partitioning idea shows up in three main forms, each answering the same question differently: IVF draws its regions around learned centroids, LSH draws them with random hyperplanes, and graph methods like HNSW trade explicit regions for a navigable mesh of local neighborhoods.
The most intuitive partition is the one you would invent on a napkin. Run k-means on the database. You get k centroids. Assign every vector to its closest centroid. That builds an inverted file, one posting list per centroid, hence the name IVF. At query time you compare the query to the k centroids (cheap, because k is small) and scan the posting list attached to the nearest one.
This is fast. The query does a distance computation to k centroids plus a scan of one posting list, not the whole database. If the centroids carve the data into roughly equal cells of size N/k, each query inspects about 1/k of the points. For k = 100 and N = 1 million, that is 10,000 distance checks instead of a million.
IVF also inherits a nice property from k-means: the centroids themselves describe where the data concentrates. A centroid with a big posting list sits in a dense region. An empty cell means no vector fell closer to that centroid than to any other. This is why the first thing any production IVF index does is train on a representative sample of the data rather than picking random centroids.
nprobe
Single-cell search has an obvious failure mode. If the query lands near a cell boundary,
the true nearest neighbor may be just on the other side. Voronoi cells are convex and
sharp; a single point of displacement can land the query in the wrong cell entirely.
The fix is to scan not just the closest cell but the
nprobe closest cells. This trades
speed for recall in a knob the user controls.
As nprobe grows from 1 toward k, recall climbs toward exact and speed
degrades toward a linear scan. In between there is a sweet spot where you catch nearly
all the true neighbors while still inspecting a small fraction of the database. This
tradeoff is so fundamental that every partition-based ANN method has some version of it,
even when the "cells" are not literal Voronoi regions.
nprobe slider. On the
left, each additional probed cell joins the scanned region in teal. On the right,
the curve plots recall against the fraction of points actually scanned. The dot marks
the current position. Low nprobe
is fast but sometimes misses neighbors near a boundary; high
nprobe approaches exact search.
This tradeoff shape is the core of every partition-based ANN method.
There is a simple mental model for when boundary mistakes happen. A neighbor gets missed
when it is closer to the query than the query's own chosen centroid is, but closer to a
different centroid than to the query's chosen centroid. Geometrically, the bad points
live in thin slivers along cell boundaries. More clusters means more boundaries, which
means more slivers, which means you need a higher nprobe to sweep them up.
Fewer, bigger clusters hide fewer neighbors but each scan is larger. That is the tuning
problem.
IVF works because k-means finds centroids where the data concentrates. That requires training, and the resulting cells only make sense for the dataset they were fit to. A different approach gives up trying to know where clusters are and just partitions with random hyperplanes. This is the core idea of locality-sensitive hashing, or LSH.
A single random hyperplane through the origin splits space into two halves. Every vector falls on one side or the other, so you can assign it a single bit. Stack h independent random hyperplanes and each vector becomes an h-bit hash code. The hash function has a useful property: two points that are close together are likely to land on the same side of any random hyperplane, so they are likely to share their hash code. Two points that are far apart are likely to be split.
LSH is elegant because it needs no training. The hash function is picked once, at random, and works for any dataset. It also has provable guarantees: you can bound the probability that near points collide and far points do not, given the number of hyperplanes and the distance threshold. In practice a single hash table is too noisy, so real LSH uses multiple independent tables and takes the union of the buckets each returns. More tables means more candidates, which means better recall at the cost of more work.
The weakness of LSH is the same as its strength. Because the hyperplanes ignore the data, they waste capacity on empty regions and overfill dense ones. Data-aware methods use the structure of the dataset and reach higher recall for the same work. In the last decade LSH has been quietly losing ground to graph methods on the standard benchmarks. It remains useful for theoretical analysis and for settings where the dataset changes too fast to retrain centroids.
The method that currently dominates production ANN is neither centroids nor hyperplanes but a graph. The idea is to precompute a structure where every vector is a vertex connected to some of its nearest neighbors, and then to answer a query by walking that graph. Start at some entry node. Look at its neighbors. Move to whichever is closest to the query. Repeat. When no neighbor is closer, you have found a local minimum, which is almost always a true nearest neighbor if the graph was built well.
A plain k-NN graph gets you most of the way but struggles when the query is far from the entry node: the greedy walk has to cross the whole dataset one short hop at a time. HNSW (Hierarchical Navigable Small World) fixes this by building multiple layers. The top layer has very few nodes, connected by long edges. The bottom layer has every node, connected to its near neighbors. The query descends layer by layer: a few long jumps at the top put it in the right neighborhood, then progressively shorter hops zoom in. It is the same trick an airline uses. Hubs plus spokes beats a mesh.
HNSW's build cost is high. Every vector has to be inserted, which involves running a query-like walk to find the neighbors to connect to. For a million vectors in 768 dimensions, this can take hours on a single machine. Its memory footprint is also substantial, because each vector stores its edge list on top of the vector itself. In exchange it gives the best recall-per-query-time among open-source indexes and scales gracefully to tens of millions of vectors. Almost every vector database, lancedb and Weaviate and pgvector included, ships HNSW as a default choice.
Every partition method is navigating the same recall-versus-speed plane. What differs is the slope of the curve and the shape of the knobs. Here is a stylized picture of where the three methods sit. The curves are representative, not taken from any specific benchmark, but their ordering matches what ann-benchmarks.com has shown on most datasets for years.
A short summary of the practical character of each method:
nprobe). Quality depends on k-means capturing the data's structure.There is one more thing to say before moving on. All three methods reduce the number of full-vector distance computations a query has to perform, but they do not make any single distance computation faster. Each comparison still touches every dimension of two vectors. If the vectors are 1536-dimensional floats, that is 6 KB per vector and a few thousand multiply-adds to compare them. When the database grows into the hundreds of millions of vectors, even a tiny fraction of "let me look at this one" becomes a lot of arithmetic.
Partitioning decides which vectors to look at. The next article asks what if we made each vector itself cheaper to look at? Product quantization, binary codes, and their friends trade a little accuracy in the distance computation for an order-of-magnitude drop in memory and CPU per comparison. Stacked on top of IVF or HNSW, compression is what lets a billion-vector index run on a single machine.