Module 2: How Vector Databases Work (Conceptual)

Capsule 05: IVF - Inverted File Index

Next →

🎯 Capsule objective

Understand HOW IVF works (vector clustering), why it's better than HNSW for >1M vectors, and when to use it in RAG systems.

By the end of this capsule:

  • ✅ You'll explain what IVF is and how it uses clustering (k-means)
  • ✅ You'll understand the trade-off: lower accuracy + lower memory
  • ✅ You'll know the key parameters (nlist, nprobe)
  • ✅ You'll decide when to migrate from HNSW to IVF

Estimated time: 8-10 minutes

🗂️ What is IVF?

Definition

IVF = Inverted File Index

It's an algorithm that divides vectors into clusters using k-means, then searches only in the clusters closest to the query (not in all of them).

Analogy: An organized library

Without IVF (brute force):

  • Books piled up in one giant, disordered stack
  • Finding book X = checking ALL the books
  • O(n) = 1,000,000 books

With IVF:

  • Books organized on shelves by category
    • Shelf 1: Science (10K books)
    • Shelf 2: History (15K books)
    • Shelf 3: Fiction (20K books)
    • ... (100 shelves total)
  • Finding a science book = checking ONLY the science shelf
  • O(n/k) where k = number of clusters = 10K books (not 1M)

Speedup: 100x (1M → 10K searches)

🏗️ IVF architecture

Step 1: Build (Build Index)

1. Clustering with k-means

# Conceptual
def build_ivf_index(vectors, nlist=100):
    # 1. Run k-means to find the centroids
    centroids = kmeans(vectors, k=nlist)
    # Result: 100 centroids (they represent the clusters)
    
    # 2. Assign each vector to its closest cluster
    for vector in vectors:
        cluster_id = find_nearest_centroid(vector, centroids)
        inverted_index[cluster_id].append(vector)
    
    # Result: Dictionary {cluster_id: [vectors]}
    # Example: {0: [v1, v2, ...], 1: [v100, v101, ...], ...}

Visualization:

1M vectors                     100 clusters
──────────────────────────────────────────
v1, v2, v3, ..., v1M   →      Cluster 0: [v1, v5, v12, ...] (10K vectors)
                              Cluster 1: [v2, v8, v20, ...] (9K vectors)
                              Cluster 2: [v3, v7, v15, ...] (11K vectors)
                              ...
                              Cluster 99: [v4, v9, v18, ...] (10K vectors)

Key parameter: nlist = number of clusters

2. Store the inverted index

inverted_index = {
    0: [v1, v5, v12, ...],  # Cluster 0
    1: [v2, v8, v20, ...],  # Cluster 1
    ...
    99: [v4, v9, v18, ...],  # Cluster 99
}

centroids = [c0, c1, c2, ..., c99]  # k-means centroids

Step 2: Search (Query)

1. Find the closest clusters

def query_ivf(query, nprobe=10):
    # 1. Find the nprobe clusters closest to the query
    nearest_clusters = find_nearest_centroids(query, centroids, k=nprobe)
    # Example: [5, 12, 23, 45, ...] (10 clusters)
    
    # 2. Search only in those clusters
    candidates = []
    for cluster_id in nearest_clusters:
        candidates.extend(inverted_index[cluster_id])
    
    # 3. Compute similarity with the candidates (not with all vectors)
    results = []
    for candidate in candidates:
        sim = cosine_similarity(query, candidate)
        results.append((sim, candidate))
    
    # 4. Sort and return top-k
    results.sort(reverse=True)
    return results[:10]

Key parameter: nprobe = number of clusters to explore

Visualization:

Query: "Python asyncio tutorial"
           ↓ (embedding)
   [0.1, 0.5, 0.8, ...]
           ↓
   Find nearest centroids
           ↓
   Clusters: [5, 12, 23, 45, 67, 78, 81, 92, 95, 99]
           ↓
   Search only in these 10 clusters (100K vectors, not 1M)
           ↓
   Top-10 results

Speedup: 10x (searching 100K vs 1M vectors)

📊 Why IVF is O(sqrt(n))

Complexity analysis

Brute force:

for vector in database:  # n = 1M
    compare(query, vector)

→ O(n)

IVF:

# Step 1: Find nearest centroids
for centroid in centroids:  # nlist = 100
    compare(query, centroid)

# Step 2: Search in nprobe clusters
for cluster in top_nprobe_clusters:  # nprobe = 10
    for vector in cluster:  # ~n/nlist per cluster
        compare(query, vector)

→ O(nlist + nprobe * (n/nlist))
→ Optimal when nlist ≈ sqrt(n) → O(sqrt(n))

Benchmark: Real comparisons

Vectors (n)nlistnprobeComparisonsvs Brute Force
100K10010~10K10x faster
1M31610~31K32x faster
10M100010~100K100x faster

Key: IVF gains more as n grows (better for >1M vectors).

⚙️ Key IVF parameters

1. nlist (Number of clusters)

Definition: The number of clusters to divide the vectors into (the k in k-means).

Impact:

  • High nlist (1000, 5000):

    • ✅ Higher accuracy (more specific clusters)
    • ❌ Slower build time (k-means with more clusters)
    • ❌ Slightly slower query (more centroids to compare)

  • Low nlist (50, 100):

    • ✅ Fast build
    • ✅ Fast query
    • ❌ Lower accuracy (very broad clusters)

Optimal rule: nlist ≈ sqrt(n)

VectorsRecommended nlist
100K316
1M1000
10M3162
100M10000

2. nprobe (Clusters to explore)

Definition: The number of closest clusters to explore during a query.

Impact:

  • High nprobe (50, 100):

    • ✅ Higher accuracy (explores more clusters)
    • ❌ Slower query (more vectors to compare)

  • Low nprobe (5, 10):

    • ✅ Fast query
    • ❌ Lower accuracy (may skip the correct cluster)

Practical rule: nprobe = nlist / 10 (10% of clusters)

Trade-off visualized:

Accuracy vs Query Speed

High Accuracy    nprobe=100 (explores 100 clusters)
(95%)           ▲  ❌ Slow (100ms)
                │
Medium          │  nprobe=20 (explores 20 clusters)
Accuracy        │  ⚖️ Balanced (30ms)
(92%)           │
                │  nprobe=5 (explores 5 clusters)
Low Accuracy    │  ✅ Fast (10ms)
(88%)           └──────────────────────
                  Fast ← Speed → Slow

3. Metric (Distance)

IVF supports different similarity metrics:

MetricFormulaUsed for
Cosine1 - dot(a,b) / (norm(a)*norm(b))Text embeddings (default)
L2sqrt(sum((a-b)^2))Image embeddings
Dot Productdot(a,b)Pre-normalized embeddings

For RAG: Use cosine (the standard for text embeddings).

🆚 HNSW vs IVF: A direct comparison

Comparison table

DimensionHNSWIVF
ComplexityO(log n)O(sqrt(n))
Accuracy95-99%90-95%
Latency (1M vecs)15-20 ms30-50 ms
Latency (10M vecs)20-30 ms40-60 ms
Memory (1M vecs)4-8 GB1-2 GB
Build time (1M vecs)5-10 min2-3 min
Incremental updates✅ Yes❌ No (rebuild clusters)
Best for<1M vectors>1M vectors

When to use IVF

Use IVF when:

  • ✅ You have >1M vectors (IVF scales better)
  • ✅ 90-95% accuracy is enough (you don't need 98%)
  • ✅ Memory is limited (<4 GB available)
  • ✅ Batch updates (rebuild nightly OK)

RAG example: E-commerce product search with 5M products.

When to use HNSW

Use HNSW when:

  • ✅ Accuracy is critical (>95% required)
  • ✅ You have enough RAM (4-8 GB)
  • ✅ <1M vectors
  • ✅ Incremental updates (adding docs daily)

RAG example: Customer support chatbot with 100K articles.

🏭 IVF in practice: Faiss

Faiss (Facebook AI Similarity Search) is a library optimized for IVF.

Basic setup

import faiss
import numpy as np

# 1. Create the IVF index
dimension = 1536  # OpenAI embedding dimension
nlist = 1000  # Number of clusters
quantizer = faiss.IndexFlatL2(dimension)  # Quantizer for the centroids
index = faiss.IndexIVFFlat(quantizer, dimension, nlist, faiss.METRIC_L2)

# 2. Train (build the clusters with k-means)
vectors = np.random.random((1_000_000, dimension)).astype('float32')
index.train(vectors)  # ← This runs k-means

# 3. Add vectors to the index
index.add(vectors)

# 4. Query
query = np.random.random((1, dimension)).astype('float32')
index.nprobe = 10  # Explore 10 clusters
distances, indices = index.search(query, k=10)

IVF + PQ (Additional compression)

You can combine IVF with PQ to reduce memory 4-8x:

# IVF + PQ (Product Quantization)
nlist = 1000
m = 8  # Sub-vectors
bits = 8  # Bits per sub-vector

index = faiss.IndexIVFPQ(quantizer, dimension, nlist, m, bits)
index.train(vectors)
index.add(vectors)

# Result: 4-8x less memory with 85-90% accuracy

Trade-off: IVF alone = 90-95% accuracy. IVF+PQ = 85-90% accuracy.

📊 Benchmark: IVF vs HNSW in production

Scenario A: 1M vectors

MetricHNSW (ChromaDB)IVF (Faiss)Winner
Accuracy98%93%HNSW
Latency18 ms35 msHNSW
Memory6 GB2 GBIVF
Build time8 min3 minIVF

Conclusion: HNSW is better for 1M vectors (accuracy + latency).

Scenario B: 10M vectors

MetricHNSW (Weaviate)IVF (Faiss)Winner
Accuracy98%92%HNSW
Latency45 ms55 msHNSW
Memory48 GB12 GBIVF (4x less)
Build time120 min25 minIVF (5x faster)

Conclusion: IVF is competitive for 10M vectors (memory is critical).

Scenario C: 100M vectors

MetricHNSWIVF (Faiss)Winner
Accuracy97%91%HNSW
Latency80 ms75 msIVF
Memory400 GB ❌80 GB ✅IVF (5x less)
Build time1200 min180 minIVF (6x faster)

Conclusion: IVF is better for 100M vectors (HNSW is impractical in RAM).

✅ Advantages and disadvantages of IVF

Advantages

  1. Memory efficient

    • 2-4x less memory than HNSW
    • Lets you handle >10M vectors

  2. Fast build time

    • 2-3x faster than HNSW
    • Rebuilding clusters is fast (batch updates)

  3. Linear scalability

    • Predictable performance with large n
    • O(sqrt(n)) guaranteed

  4. Easy tuning

    • Only 2 parameters: nlist, nprobe
    • Simple rules (nlist≈sqrt(n), nprobe≈nlist/10)

Disadvantages

  1. Lower accuracy (90-95%)

    • vs 98% HNSW
    • Can be a problem if accuracy is critical

  2. Higher latency

    • 30-50ms vs 15-20ms HNSW
    • Especially with high nprobe

  3. No incremental updates

    • Adding vectors requires rebuilding the clusters
    • Better for batch updates (nightly)

  4. Requires training

    • k-means needs a representative dataset
    • If the distribution changes → rebuild index

🔗 Connection with RAG

When to migrate from HNSW to IVF in RAG

Signs you need IVF:

  1. Insufficient memory

    • HNSW consumes >64 GB RAM
    • IVF reduces it to 16 GB

  2. Dataset >1M vectors

    • HNSW latency increases significantly
    • IVF keeps latency stable

  3. 90-95% accuracy is OK

    • Not critically customer-facing
    • Internal search/analytics

  4. Batch updates

    • Adding documents nightly (not real-time)
    • Rebuilding clusters is fast (30 min)

Example: Internal knowledge base with 5M Confluence pages + Slack messages.

Hybrid architecture (HNSW + IVF)

Some systems combine both:

Hot data (recent, <100K vectors):

  • HNSW for high accuracy + low latency
  • Last 30 days of documents

Cold data (old, >1M vectors):

  • IVF for memory efficiency
  • Historical data (>30 days)

Query strategy:

  • Search HNSW first (recent docs)
  • If not enough results → Search IVF (historical)

✅ Comprehension checklist

Verify that you understood this capsule:

  • What is IVF?

    • Answer: An algorithm that divides vectors into clusters (k-means), then searches only in the clusters closest to the query.

  • Why does IVF use less memory than HNSW?

    • Answer: It doesn't store a graph of connections (edges). It only stores the inverted index (cluster_id → vectors).

  • What does the nprobe parameter do?

    • Answer: The number of clusters to explore during a query. High nprobe = higher accuracy + higher latency.

  • When to use IVF vs HNSW?

    • Answer: IVF when >1M vectors, limited memory, 90% accuracy is OK, batch updates. HNSW when accuracy is critical (>95%), <1M vectors, incremental updates.

  • Why doesn't IVF support incremental updates?

    • Answer: Adding vectors requires recomputing the clusters (k-means). A full rebuild is necessary.

If you answered 4-5/5 correctly → ✅ Ready for Capsule 06 (PQ)

🚀 Next step

Now that you understand IVF (clustering), you'll learn PQ (Product Quantization) for extreme compression.

Next capsule: 06 - PQ (Product Quantization)

You'll learn:

  • How to compress vectors 4-8x (1536 dims → 384 dims)
  • The accuracy vs memory trade-off (85% vs 98%)
  • When to use PQ (>5M vectors, RAM critical)
  • Combining IVF + PQ for extreme scale

Key: PQ sacrifices accuracy (85-90%) but gains memory massively (10M vectors in 5 GB).

Reading time: 8-10 minutes
Next: 06-pq-compression.md

← PreviousCapsule 04: HNSW - Hierarchical Navigable Small WorldNext →Capsule 06: PQ - Product Quantization