AI Engineer Roadmap All lessons Interactive Quiz GitHub

IVF Index

Advanced · 9 min read · Updated · By Saurabh Pathak

In short: An IVF (Inverted File) index groups vectors into clusters, then at query time searches only the few clusters closest to the query instead of every vector.

Play the interactive lesson: IVF indexRead on GitHub
On this page
  1. Explain it like I'm new
  2. Watch it
  3. How it works
  4. Code example
  5. When to use it / when not to
  6. Common mistakes
  7. Recap
  8. Interview questions
  9. Go deeper

Level: Advanced · Reading time: 9 min · Phase: 1 — RAG Foundations

Before you start: Vector Databases and HNSW. You should know that a vector is a list of numbers that stands for the meaning of a chunk of text, and that an index is a structure that makes searching faster.

Explain it like I'm new

Imagine a huge library with no catalogue. To find a book about volcanoes you would check every shelf. Now imagine the books are sorted into sections: Geology, Cooking, History. You walk to Geology (and maybe Geography, just in case) and search only there. You skip 95% of the library.

IVF does this with vectors:

The risk: the true nearest neighbour might sit just across a cluster border, in a cluster you did not probe. Probing more clusters (bigger nprobe) lowers that risk and costs more time.

Words to know:

Watch it

IVF index: Group vectors into clusters, then search only the nearest clusters.
IVF index: Group vectors into clusters, then search only the nearest clusters.

It plays on a loop. Read the caption in the box, one step at a time. Want to go at your own pace? Step through it with Previous and Next.

How it works

Training and adding

  1. Run k-means on a sample of vectors to get nlist centroids. This is the training step.
  2. Assign every vector to its nearest centroid and append its ID to that cluster's list.

Searching

  1. Compute the distance from the query to all nlist centroids.
  2. Pick the nprobe nearest clusters.
  3. Compute exact distances to every vector inside those clusters.
  4. Return the best k.
          centroid A           centroid B
         .  . A  .            .   B .  .
          .  .  .               .  .  .
                         q  <- query is near A and B
          centroid C           centroid D
         .  . C  .            .  D  .
nprobe=1 -> search only A          (fast, may miss a neighbour in B)
nprobe=2 -> search A and B         (slower, safer)
nprobe=4 -> search everything      (= brute force)

Worked example from the demo: 200 vectors in 4 clusters, nlist = 4. With nprobe = 1, a query costs 4 centroid comparisons + about 50 vectors ≈ 54 distance computations, versus 200 for brute force. On the demo's random queries, recall@1 is 0.98 at nprobe = 1 and 1.00 at nprobe = 2. (Toy data; real recall depends on your data and settings.)

A common heuristic is to make nlist grow with the square root of the collection size (a few times √N for N vectors), then tune nprobe while measuring recall.

Worked example

Picture the diagram above with 200 vectors split into 4 clusters (A to D) of about 50 each, and a query q that lies between A and B.

  1. Compare q with the 4 centroids. A is closest, then B. That costs 4 comparisons.
  2. With nprobe = 1, search only the roughly 50 vectors in A. Total is about 54 comparisons instead of 200. If the true best match is in B, you miss it. That is the risk.
  3. With nprobe = 2, search A and B (about 100 vectors). Total is about 104. Now the match in B is found.

The demo agrees: recall@1 goes from 0.98 (nprobe = 1, 54 computations) to 1.00 (nprobe = 2, 104 computations).

Code example

From code/rag_hnsw_ivf.py:

class IVFIndex:
    def __init__(self, vectors, nlist=4, seed=0):
        self.vectors = vectors
        self.centroids, assign = kmeans(vectors, nlist, seed=seed)   # training
        self.lists = {c: [] for c in range(nlist)}
        for i, c in enumerate(assign):
            self.lists[c].append(i)                                   # inverted lists

    def search(self, query, k=1, nprobe=1):
        order = sorted(range(len(self.centroids)),
                       key=lambda c: dist(query, self.centroids[c]))
        candidates = [i for c in order[:nprobe] for i in self.lists[c]]
        candidates.sort(key=lambda i: dist(query, self.vectors[i]))
        return candidates[:k]

Run python rag_hnsw_ivf.py to print recall and work for nprobe = 1, 2, 4.

In real projects (pip install faiss-cpu numpy):

import faiss
import numpy as np

d, nlist = 128, 100
xb = np.random.rand(100_000, d).astype("float32")
quantizer = faiss.IndexFlatL2(d)                  # holds the centroids
index = faiss.IndexIVFFlat(quantizer, d, nlist)
index.train(xb)                                   # k-means
index.add(xb)
index.nprobe = 8                                  # clusters to search
D, I = index.search(xb[:5], 4)

IndexIVFPQ adds product quantization (compressing each vector into a few bytes) for very large collections.

When to use it / when not to

nprobeSpeedRecall
1FastestLowest
~1–10% of nlistCommon balanceUsually high
= nlistSame as brute forceExact

Common mistakes

Recap

If you remember only three things:

Interview questions

1. How does an IVF index speed up search? <details><summary>Answer</summary> It clusters vectors with k-means and, at query time, only searches the nprobe clusters whose centroids are closest to the query, skipping most of the data. </details>

2. What do nlist and nprobe control? <details><summary>Answer</summary> nlist is the number of clusters (set at build time). nprobe is how many clusters are searched per query; higher nprobe means better recall and slower queries. </details>

3. Why can IVF miss the true nearest neighbour? <details><summary>Answer</summary> The neighbour may sit in a cluster near a border that was not among the nprobe probed clusters. Raising nprobe reduces this. </details>

Go deeper

Prev: HNSW · Next: Hybrid Search · Back to phase: Phase 1