5. IVF: Inverted File Index and Clustering

Overview

IVF (Inverted File Index) is an alternative to HNSW based on clustering: it divides the space into regions (clusters), assigns each vector to a cluster, and when searching it only checks the clusters near the query. It uses less memory than HNSW but typically has lower precision.

---

The core idea

Analogy: A library with themed sections:

The slow method (brute force):

• Check EVERY book in the whole library

The fast method (IVF):

1. Divide the library into sections (Fiction, Science, History, etc.)
2. Query: "a science book about physics"
3. Go straight to the Science section
4. Search only in that section (don't check Fiction or History)

IVF does the same thing with vectors: it divides the space into clusters and searches only in the relevant ones.

---

The IVF algorithm

Phase 1: Building (offline)

1. Take all the vectors in the dataset
2. Apply clustering (e.g. k-means) to create N clusters
   - Typically N = √(dataset_size)
   - E.g. 1M vectors → 1000 clusters
3. Assign each vector to its nearest cluster
4. Store the inverted index:
   - Cluster 1 → [vector_23, vector_891, ...]
   - Cluster 2 → [vector_45, vector_102, ...]
   - ...

---

Phase 2: Searching (online)

Query: The query vector

1. Find the nprobe clusters closest to the query
   - nprobe = 1: Only the closest cluster
   - nprobe = 10: The 10 closest clusters

2. Search exhaustively only within those clusters
   - Compute similarity(query, vector) for the vectors in the selected clusters

3. Return the top-K vectors with the highest similarity

---

Visualization (simplified 2D)

The space divided into 4 clusters:

        |
  C1    |    C2
   •  • | • •  •
  •  •  |  • •
────────────────── Query ⭐
  • •   |     •
   •  • | •  •  •
  C3    |    C4
        |

Query ⭐ is near the boundary between C2 and C4

With nprobe=1:

• Search only in C4 (the closest cluster)
• It can miss results in C2 ❌

With nprobe=2:

• Search in C2 and C4
• A greater chance of finding all the top-K ✅

---

Advantages of IVF

1. Less memory than HNSW:

• It only needs to store: the vectors + the cluster assignments + the centroids
• HNSW needs: the vectors + the complete graph (more connections)

2. Fast for searching:

• With a small nprobe, it checks only a fraction of the dataset
• E.g. nprobe=10 out of 1000 clusters → it checks ~1% of the vectors

3. Simple to understand and implement:

• Standard clustering (k-means)
• No complex structures like graphs

---

Disadvantages of IVF

1. Lower precision than HNSW:

• Typically ~95-98% vs HNSW's ~98-99%
• It can miss results if they're in the "wrong cluster"

2. Sensitive to clustering quality:

• If the clusters are poorly formed → worse precision
• It requires periodic re-clustering when you add many vectors

3. A more pronounced trade-off:

• A small nprobe → fast but imprecise
• A large nprobe → slow, approaching brute force

---

Configuration parameters

nlist (the number of clusters):

nlist = sqrt(N)  → The rule of thumb
E.g. 1M vectors → 1000 clusters

nprobe (the clusters to search):

nprobe = 1   → Very fast, ~90% precision
nprobe = 10  → Fast, ~95% precision
nprobe = 100 → Slow, ~98% precision

A typical trade-off: nlist=1000, nprobe=10 (95% precision, fast)

---

IVF vs HNSW

Aspect	HNSW	IVF
Precision	~98-99% ✅	~95-98% ⚠️
Speed	Very fast ✅	Fast ✅
Memory	High (2-3x the vectors) ⚠️	Medium (1.2-1.5x the vectors) ✅
Scalability	Millions ✅	Billions ✅
Inserts	More expensive ⚠️	Easier (reassign to a cluster) ✅
Typical use	General production	Massive datasets on a memory budget

---

IVF variants

IVF-Flat:

• The basic form: clustering + exact search within the clusters
• High precision inside the clusters

IVF-PQ (Product Quantization):

• IVF + vector compression
• Far less memory (~10-20x compression)
• Lower precision but it scales to billions

IVF-HNSW (hybrid):

• IVF for the first stage (finding the clusters)
• HNSW for the second stage (searching within the clusters)
• It combines the advantages of both

---

IVF in production

FAISS (Facebook):

• IVF is one of the main indexes
• Multiple variants (IVF-Flat, IVF-PQ, IVF-HNSW)
• Manual configuration required

Weaviate:

• Support for IVF as an alternative to HNSW
• Less common (HNSW is the default)

Milvus:

• Full support for IVF and its variants
• Recommended for datasets > 10M vectors with memory constraints

---

When to use IVF

Use IVF when:

• The dataset is very large (> 10M vectors)
• Memory is limited
• ~95% precision is acceptable
• Inserts are frequent (easier than with HNSW)

Use HNSW when:

• Precision is critical (~99% required)
• Memory is available
• The dataset is < 10M vectors
• There are few inserts (periodic batches)

---

Summary

Key points:

• IVF: Clustering + searching within the relevant clusters
• nprobe: Controls the precision vs speed trade-off
• Advantages: Less memory, simpler
• Disadvantages: Lower precision than HNSW
• Use: Massive datasets with memory constraints

---

Next capsule: 06-tradeoffs-and-decisions.md — When to use each index.