How cluster indexes search

Graph indexes navigate. Cluster indexes divide. It’s the other main answer to the same problem, it makes opposite trade-offs, and it’s what most systems fall back on when memory is the binding constraint.

The naive approach, again

Compare the query against every vector. Linear in collection size, exact, doesn’t scale. Same starting point as graph indexes.

The graph answer was: precompute links between nearby points and navigate them.

The cluster answer is different: carve the space into regions in advance, work out which region the query falls in, and search only that region.

The idea: partition, then probe

Before any queries arrive, group the vectors into clusters. Each cluster gets a representative point — its centroid, the average of its members.

Build:

train(vectors, nlist):
    centroids ← k-means(vectors, k = nlist)     # on a sample is fine
    for v in vectors:
        c ← nearest centroid to v
        append v to list[c]
    return centroids, lists

Now you have nlist buckets, each holding the vectors closest to one centroid. This is an inverted file index — the IVF family — by analogy with text search, where an inverted file maps each term to the documents containing it. Here it maps each centroid to the vectors assigned to it.

Search:

search(query, k, nprobe):
    near ← the `nprobe` centroids closest to query
    candidates ← concat(list[c] for c in near)
    return the k closest of candidates to query, by exact distance

Two stages. First a cheap comparison against nlist centroids — a few thousand, say, rather than ten million. Then an exhaustive scan of only the vectors in the selected buckets.

If you have ten million vectors in four thousand clusters, each cluster holds about 2,500 vectors. Probing one means 4,000 centroid comparisons plus 2,500 vector comparisons, instead of 10,000,000. That’s the win, and it’s substantial.

How it fails: the boundary problem

Here’s the flaw, and it’s inherent rather than a matter of tuning.

Cluster assignment is a hard partition. Every vector belongs to exactly one bucket. But the query doesn’t respect those boundaries — it lands wherever it lands, and the true nearest neighbour to your query may sit just across a boundary, in a cluster you didn’t probe.

Picture a query near the edge between two clusters. Its closest centroid is cluster A, so you search A. The genuinely nearest vector is three units away in cluster B. You never look at B. You return A’s best, which is worse, and nothing tells you this happened.

This isn’t rare. In high dimensions a great deal of the volume of any region is near its boundary, so a large fraction of queries land in exactly this situation.

The fix: probe more clusters

Search the nprobe nearest clusters instead of just one.

That’s the parameter. nprobe = 1 is fastest and loses the most to boundary effects. nprobe = 10 searches ten times as many vectors and catches most near-boundary cases. nprobe = nlist searches everything — exact, and slower than a flat scan, since you paid for the centroid comparisons too.

This is the recall knob for cluster indexes, exactly parallel to search breadth in a graph index. Both spend more comparisons to reduce the chance of missing the answer.

The relationship is usefully predictable, which is a genuine advantage over graph indexes: the work is roughly nprobe / nlist of the collection, plus the centroid comparisons. You can estimate latency from the parameters. Graph traversal cost is much harder to predict because it depends on where the walk goes.

Choosing nlist

nlist — the number of clusters — trades the two stages against each other.

• Too few clusters: each is large, so probing one scans a lot of vectors. The second stage dominates.
• Too many clusters: each is small, but you compare against a great many centroids, and the first stage dominates. Boundary effects also get worse, because more clusters means more boundary, so you need a higher nprobe to compensate.

A common heuristic is to set nlist on the order of the square root of the vector count, which balances the two stages. Treat it as a starting point rather than a rule — the right value depends on how your data is distributed and how much of it clusters cleanly.

The other thing nlist interacts with is training data. K-means needs enough examples per cluster to place centroids sensibly. Asking for many clusters from a small sample produces centroids fitted to noise, and the partition it induces is poor.

Training, and the drift problem

Cluster indexes have a property graph indexes don’t: they require a training step before you can insert anything. You run k-means over a representative sample to establish the centroids, and only then can vectors be assigned.

Two consequences that matter in practice.

You need representative data up front. Train on the first 10,000 documents when they’re all from one category, and your centroids describe that category’s region of the space. Everything inserted later gets assigned to whichever of those poorly-placed centroids is least wrong.

Centroids don’t move as data arrives. New vectors are assigned to existing clusters. If the distribution shifts — new topics, new languages, new document types — the partition gradually stops matching the data. Clusters become unbalanced, some grow huge, and effective recall at a given nprobe declines.

The symptom is a slow degradation in result quality with no infrastructure change, and the fix is retraining, which means rebuilding. This is a real operational cost that graph indexes don’t have, and it’s worth knowing about before choosing.

Where cluster indexes win

Given all that, why use them?

Memory. This is the main reason. A graph index needs its structure resident for random access. A cluster index’s structure is just centroids plus assignments — small. The vectors themselves can live on disk and be read in bulk, because a cluster’s vectors are stored contiguously and a probe is a sequential read. Sequential reads from disk are enormously more forgiving than the random access a graph traversal needs.

That single property makes cluster indexes the practical choice for collections too large to hold in RAM.

Composability with quantization. IVF combines naturally with quantization: partition first, then store each cluster’s vectors in compressed form. IVF-PQ, the standard combination, is how very large collections get served from modest hardware.

Predictable cost. You can compute the work from the parameters.

Cheaper updates in some respects. Inserting means finding a centroid and appending to a list — no graph surgery, no edge pruning. Deletes are a list removal. Neither degrades the structure the way graph deletes do. The catch is centroid drift, which is a slower, larger problem.

Filtering is less catastrophic. A filtered scan within a probed cluster is straightforward — you’re already doing an exhaustive pass over those candidates, so skipping non-matching ones is nearly free. Compare that to graph traversal, where filtering can strand the walk entirely. Cluster indexes don’t handle selective filters well, exactly, but they degrade more gracefully.

Graph versus cluster, as a shape

	Graph (HNSW family)	Cluster (IVF family)
Structure	Neighbour lists per vector	Centroids + assignment lists
Structure size	Large, scales with vectors × degree	Small, scales with clusters
Needs full residency	Yes	No — vectors can be on disk
Recall knob	Search breadth	nprobe
Cost predictability	Poor	Good
Needs training	No	Yes
Degrades over time from	Tombstones	Centroid drift
Selective filters	Can strand the traversal	Degrades gracefully
Typical strength	Best recall-per-latency in memory	Scale beyond memory

Neither is better. Graph indexes bet that you can afford to keep everything in RAM and want the best possible recall-per-millisecond. Cluster indexes bet that you can’t, and buy scale with a coarser partition and a predictable cost model.

The knob is the same knob in both cases, wearing a different name — and what it’s really controlling is your position on the recall-latency curve.