Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 36 ยท Indexing and ANN Search

IVF: Searching Only the Nearest Clusters

Learn how inverted file (IVF) vector indexes use k-means clusters and the nprobe setting to search a fraction of the data, with a complete Python implementation.

An IVF index (inverted file index) takes the oldest trick for searching a big collection: divide it into groups and look only in the promising groups. A library does this with shelves. You do not scan every book to find one about volcanoes; you walk to the geology section.

For vectors, the "shelves" are clusters found by k-means. Each vector is filed under its nearest cluster centre. At query time you compare the query with the centres, pick the few closest clusters, and scan only the vectors inside those clusters. IVF is the second big ANN family after graphs: it builds fast, uses little extra memory, and is the base of billion-scale systems when combined with compression.

How IVF works

flowchart TD
    D["All vectors"] --> K["k-means: nlist centroids"]
    K --> L["Assign each vector to its nearest centroid (inverted lists)"]
    Q["Query"] --> C["Compare with nlist centroids"]
    C --> P["Pick nprobe closest lists"]
    L --> S
    P --> S["Scan only those lists, return top-k"]

Build once, then each query touches nprobe lists instead of the whole collection.

Two settings control it:

  • nlist: how many clusters (lists) to build.
  • nprobe: how many of the closest lists to scan per query.

If nprobe = nlist you scan everything: exact search. If nprobe = 1 you scan one list: very fast, but you miss neighbors that fell just across a cluster border.

Implement IVF in NumPy

First a small k-means (Lloyd's algorithm), then the index.

Python An IVF index from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last row (nprobe = nlist) scans 100% and has recall 1.00: it is exact search. The interesting rows are at the top: scanning just 1.8% of the data already finds 96% of the true neighbors, and 3.3% finds all of them. Compare with the scan-a-random-fraction toy, where scanning 25% gave about 28% recall: choosing which part to scan by cluster is worth far more than scanning a random part. (This data has clear clusters, so it flatters IVF; fuzzier real embeddings need a larger nprobe.)

Choosing nlist

More clusters mean smaller lists (cheaper to scan) but more centroid comparisons per query. The query cost is roughly:

cost = nlist (compare with centroids) + nprobe * (n / nlist) (scan lists)

For a fixed nprobe, this is smallest near nlist = sqrt(nprobe * n). A common rule of thumb is nlist between sqrt(n) and 4 * sqrt(n); for 1 million vectors that is about 1,000 to 4,000 lists.

Python The cost of different nlist values

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Total work bottoms out at 0.60% of the data for nlist around 2,000 to 4,000 (against 8% with only 100 lists). Making nlist huge starts costing more in centroid comparisons than it saves in scanning, so there is a sweet spot near the square-root rule. Larger nlist also needs a higher nprobe for the same recall, so the right pair is found by benchmarking.

Training and its pitfalls

  • Training data: k-means runs once on a sample (tens of thousands to millions of vectors) of the collection. Train on data that looks like production: centroids learned from a tiny or unrepresentative set give uneven lists.
  • Unbalanced lists: if a few clusters hold most vectors, queries that land there scan a lot. Check the list size spread (the program printed min and max).
  • Drift: as new vectors arrive, they are filed into the existing clusters. If the data changes a lot (new topics), re-train periodically and rebuild. Unlike HNSW, plain inserts are cheap; the cost is occasional retraining.
  • Border effect: a query near the edge of a cluster has neighbors in the next one. That is exactly what nprobe > 1 is for.
  • Metric consistency: cluster with the same metric you search with (here, cosine on unit vectors).

IVF versus HNSW

IVF HNSW
Build time Fast (k-means) Slower (graph insertion)
Extra memory Small (centroids + list ids) Large (links per vector)
Query speed at high recall Good Usually better
Inserts Cheap, but needs retraining over time Cheap, graph updates in place
Needs training Yes No
Pairs well with Product quantization (IVF-PQ), disk storage Scalar quantization, in-memory

A common production recipe for very large collections is IVF-PQ: clusters narrow the search, and compressed codes make each scanned vector tiny. See product quantization.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is stored in an IVF 'inverted list'?

    Each centroid has a list of the vectors filed under it; queries scan only the selected lists.
  2. 2. What happens when nprobe equals nlist?

    All lists are scanned, so recall is perfect and the speed advantage is gone.
  3. 3. Why might a true neighbor be missed with nprobe = 1?

    A neighbor close to the query may belong to a different cluster than the one the query was assigned to.
  4. 4. What is a good first guess for nlist when you have 1 million vectors?

    Rules of thumb put nlist between sqrt(n) and 4*sqrt(n), then you tune it with benchmarks.
  5. 5. Compared with HNSW, IVF typically:

    IVF learns centroids first and adds only small per-vector overhead, which makes it a good base for compression.

Summary

  • IVF clusters vectors with k-means and scans only the nprobe clusters closest to the query.
  • nlist sets list size and centroid cost; sqrt(n) to 4*sqrt(n) is a sensible start.
  • nprobe is the speed-versus-recall dial; nprobe = nlist is exact search.
  • Train on representative data, watch list balance, and retrain when the data drifts.
  • IVF builds quickly, uses little extra memory and combines well with product quantization.

Next: Product Quantization and Vector Compression