Vector IVF Index

IVF stands for Inverted File Index. It is one of the oldest and most reliable approximate nearest neighbor index strategies. When combined with Product Quantization (PQ), it scales to billions of vectors on modest hardware. This topic explains how IVF works and when to use it.

The City Neighborhood Analogy

Imagine you are looking for a specific restaurant in a city of 10 million people. Instead of checking every street, you first identify which neighborhood the restaurant is likely in — Italian food in Little Italy, sushi in Japantown — then search only that neighborhood in detail.

IVF works identically. It divides the entire vector space into neighborhoods (called clusters) using a training step, then routes each query to the most relevant clusters and searches only those.

How IVF Is Built

BUILD PHASE (done once, before inserting data):

STEP 1: Train cluster centers using k-means clustering
────────────────────────────────────────────────────
  Sample vectors → k-means algorithm → finds nlist centroids

  Example with nlist = 4 (simplified 2D):

     ●  ●              ★ = centroid (cluster center)
       ★  (Cluster 1)
  ●  ●  ●

         ●  ●  ●
           ★    (Cluster 2)
         ●

  ●  ●                         ●  ●  ●
    ★  (Cluster 3)               ★   (Cluster 4)
  ●  ●                         ●  ●

STEP 2: Assign every vector to its nearest centroid
  Each vector joins a cluster → stored in that cluster's list

How IVF Searches

QUERY PHASE:

Query vector Q arrives
  ↓
STEP 1: Find the nprobe nearest centroids to Q
  (nprobe = how many clusters to search, default: 1–10)

  nprobe = 2 means: search the 2 closest clusters

  Full vector space:  ●●●●●●●●●●●●●●●●●●●●  (all 4 clusters)
  With nprobe=2:      ●●●●  ●●●●             (only 2 clusters)

  ↓
STEP 2: Search only vectors inside those nprobe clusters
  ↓
STEP 3: Return top-k nearest vectors found

The nlist and nprobe Parameters

nlist — Number of Clusters

Controls how many clusters the index builds. More clusters means each cluster is smaller and faster to search, but requires more training time and memory for centroids.

A common rule: set nlist to approximately √(number of vectors). For 1 million vectors, nlist ≈ 1,024.

nprobe — Clusters to Search at Query Time

Controls accuracy vs. speed at query time. You change nprobe without rebuilding the index.

nprobe = 1:   fastest, lowest recall (~80%)
nprobe = 10:  balanced (~95% recall)
nprobe = 50:  slower, high recall (~99%)
nprobe = nlist: exact search (same as brute force)

IVF + PQ: Scaling to Billions of Vectors

IVF by itself still stores full vectors inside each cluster. For billions of vectors this demands enormous memory. Product Quantization (PQ) compresses each vector into a compact code, dramatically cutting memory use.

WITHOUT PQ:
  1 billion vectors × 768 dimensions × 4 bytes = 3 TB of RAM

WITH PQ (compression ratio ~32x):
  1 billion vectors × compressed code           = ~94 GB of RAM

HOW PQ COMPRESSES:
  Original vector (768 dims):
  [0.23, 0.87, 0.45, 0.12, 0.78, 0.34, ...]
        ↓ Split into M sub-vectors
  Sub1: [0.23, 0.87]  → nearest code in codebook → code 47
  Sub2: [0.45, 0.12]  → nearest code in codebook → code 12
  Sub3: [0.78, 0.34]  → nearest code in codebook → code 91
  ...
  Final compressed form: [47, 12, 91, ...]  (integers, not floats)

The accuracy loss from PQ compression is usually 2–5%, which is acceptable for large-scale applications.

IVF vs. HNSW: Which to Choose

When to Use IVF

• Your dataset has more than 10 million vectors
• RAM is a hard constraint and compression is acceptable
• You can afford an upfront training phase before indexing data
• Your data distribution is relatively stable (adding large batches of data can shift cluster quality over time)

Facebook's FAISS library is the most popular implementation of IVF and IVF+PQ. Many vector databases (Milvus, Weaviate, Qdrant) use FAISS under the hood when you select IVF-based indexes.