Skip to content

LearnIndex & store

IVF index

Inverted file index · IVF

A vector index that clusters vectors around k-means centroids and, at query time, searches only the few clusters nearest the query.

In DocSlurpGlossary entry

On this page

An IVF (inverted file) index groups vectors into clusters and searches only the clusters nearest the query.

At build time, k-means picks a set of centroids from a sample of the data, and every vector is assigned to its nearest centroid. Each centroid keeps a list of its vectors, like a word’s posting list in an inverted index, which is where the name comes from. At query time, the search measures the query against the centroids, picks the closest few (the nprobe setting), and measures only the vectors in those clusters.

With 1,000,000 vectors in 1,000 clusters of about 1,000 each, nprobe = 10 means about 1,000 centroid distances plus 10,000 vector distances: roughly 1.1% of an exhaustive scan.

The gotchas

  • Neighbors near a border get missed. A query close to the edge of its cluster may have true neighbors in the cluster next door. Raising nprobe checks more clusters and recovers them, at proportional cost.
  • Training needs data. k-means needs a representative sample, and clusters trained on old data fit new data worse as the corpus drifts, until the index is rebuilt.
  • Tight filters waste probes. If a filter excludes most vectors, the probed clusters may contain few eligible ones.

IVF is often combined with compression (product quantization, as in IVF-PQ) or with a graph inside each cluster. LanceDB’s IVF_HNSW_SQ index, which DocSlurp uses, puts an HNSW graph in each partition; DocSlurp creates one partition per million rows, so most project tables are a single partition.

In DocSlurp

In DocSlurp

LanceDB’s HNSW_SQ index sits inside an IVF layout, but DocSlurp sets one partition per million rows (core/worker/src/stages/lancedb-maintenance.ts), so tables under a million rows are a single partition searched by HNSW alone.

Sources

Jump to