Capsule 03: Indexing Algorithms - Overview

🎯 Capsule objective

Understand WHY indexing algorithms (HNSW, IVF, PQ) achieve O(log n) search vs brute force O(n), and WHEN to use each algorithm based on trade-offs.

By the end of this capsule:

• ✅ You'll explain the difference between brute force O(n) and indexing O(log n)
• ✅ You'll compare HNSW, IVF, PQ (accuracy, speed, memory)
• ✅ You'll decide which algorithm to use based on your RAG system's requirements

Estimated time: 8-10 minutes

---

🧮 Problem: Brute force O(n) doesn't scale

What is brute force search?

Definition: Compute similarity between the query and ALL vectors in the database, then sort and return the top-k.

Conceptual code:

def brute_force_search(query, database, k=10):
    similarities = []
    for vector in database:  # ❌ Iterates over ALL vectors
        sim = cosine_similarity(query, vector)
        similarities.append((sim, vector))
    
    # Sort and return top-k
    similarities.sort(reverse=True)
    return similarities[:k]

Complexity: O(n) where n = number of vectors in the database.

Why is it a problem in RAG?

Typical production RAG scenario:

• Database: 1,000,000 vectors (product documentation)
• Vector dimension: 1536 (OpenAI text-embedding-3-small)
• Requirement: Latency < 500ms for a chatbot

Brute force benchmark with numpy:

Vectors	Latency (numpy)	Meets the requirement?
10K	15 ms	✅ Yes
100K	150 ms	✅ Yes
500K	750 ms	❌ No (>500ms)
1M	1500 ms	❌ No (3x the limit)
10M	15000 ms	❌ No (30x the limit)

Conclusion: Brute force fails at >100K vectors with a <500ms requirement.

Solution? Indexing algorithms that avoid comparing against ALL vectors.

---

🎯 Solution: Indexing Algorithms

What is indexing?

Definition: Building a specialized data structure that organizes vectors so that search is O(log n) or better.

Analogy:

Without an index (brute force):

• Like searching for a name in an unsorted phone book
• You have to read ALL the pages (O(n))

With an index (HNSW, IVF):

• Like searching in a phone book sorted alphabetically
• You jump straight to the right section (O(log n))

Main indexing algorithms

Algorithm	Type	Complexity	Used by
HNSW	Hierarchical navigable graph	O(log n)	ChromaDB, Weaviate, Qdrant
IVF	Clustering (k-means)	O(sqrt(n))	Faiss, Milvus
PQ	Vector compression	O(n) compressed	Faiss, Milvus (addon)
ScaNN	Learned quantization	O(log n)	Google Research
NSW	Navigable graph (non-hierarchical)	O(n^(1/2))	Predecessor of HNSW

In this guide we focus on: HNSW, IVF, PQ (the most used in production).

---

🔍 Algorithm 1: HNSW (Hierarchical Navigable Small World)

What is it?

Definition: A navigable graph organized in hierarchical layers, where you navigate from the top layer (long jumps) to the bottom layer (short jumps).

How it works (conceptual)

Analogy: A highway system

• Top layer (highways): Few nodes, long jumps (100 km)
• Middle layer (roads): More nodes, medium jumps (10 km)
• Bottom layer (streets): All the nodes, short jumps (1 km)

Navigation:

1. You start at the top layer (highway)
2. You go down to the middle layer when you're close
3. You go down to the bottom layer for final precision

Advantage: You don't visit all the nodes (O(log n) instead of O(n)).

Trade-offs

Advantages:

• ✅ High accuracy: 95-99% (almost perfect)
• ✅ Low latency: 10-20ms for 1M vectors
• ✅ Incremental updates: You can add vectors one by one

Disadvantages:

• ❌ High memory: 4-8 GB for 1M vectors (1536-dim)
• ❌ Slow build time: 5-10 min for 1M vectors

Used by

• ChromaDB (default)
• Weaviate
• Qdrant
• Milvus (option)

When to use HNSW

Use HNSW when:

• ✅ Accuracy is critical (>95% required)
• ✅ You have enough RAM (4-8 GB per 1M vectors)
• ✅ Latency must be <50ms
• ✅ The dataset grows incrementally (not batch)

RAG example: Customer support chatbot (accuracy critical, <100K vectors, latency <500ms).

---

🗂️ Algorithm 2: IVF (Inverted File Index)

What is it?

Definition: Divides vectors into clusters using k-means, then searches only in the clusters closest to the query.

How it works (conceptual)

Analogy: A library organized by categories

• Step 1: Group books into categories (science, history, fiction) → Clustering
• Step 2: When you look for a science book, you only search the science shelf (not all of them) → Query on a subset

Search:

1. Find the cluster closest to the query (using centroids)
2. Search only within that cluster
3. Return the top-k results

Advantage: You search in 1-10 clusters (not in 1M vectors).

Trade-offs

Advantages:

• ✅ Less memory: 1-2 GB for 1M vectors (vs 4-8 GB HNSW)
• ✅ Fast build time: 2-3 min for 1M vectors
• ✅ Good for batch updates: Rebuild clusters periodically

Disadvantages:

• ❌ Lower accuracy: 90-95% (vs 98% HNSW)
• ❌ Higher latency with few clusters: 30-50ms
• ❌ Requires tuning: The number of clusters (nlist) matters a lot

Used by

• Faiss (Facebook AI Research)
• Milvus (option)

When to use IVF

Use IVF when:

• ✅ You have >1M vectors (IVF scales better than HNSW)
• ✅ 90-95% accuracy is acceptable
• ✅ Memory is limited (< 4 GB available)
• ✅ Batch updates (rebuild clusters every day)

RAG example: E-commerce search (1M+ products, 90% accuracy OK, nightly batch updates).

---

📦 Algorithm 3: PQ (Product Quantization)

What is it?

Definition: Compresses vectors by dividing them into sub-vectors and replacing them with codes (codebook), reducing memory 4-8x.

How it works (conceptual)

Analogy: Image compression (JPEG)

• Original: Uncompressed image (10 MB)
• Compressed: JPEG image (1 MB)
• Trade-off: Slightly lower quality

For vectors:

• Original: A 1536-dim vector (6 KB)
• Compressed: A 384-dim vector (1.5 KB)
• Trade-off: 85-90% accuracy (vs 100% original)

Process:

1. Divide the vector into sub-vectors (1536 dims → 8 sub-vectors of 192 dims)
2. Find the closest centroid for each sub-vector (codebook)
3. Replace the sub-vector with a code (8 bits instead of 768 bytes)

Trade-offs

Advantages:

• ✅ 4-8x less memory: 500 MB for 1M vectors (vs 4 GB HNSW)
• ✅ Acceptable latency: 20-40ms
• ✅ Economical: You can hold 10M+ vectors in RAM

Disadvantages:

• ❌ Lower accuracy: 85-90% (vs 98% HNSW)
• ❌ Slow build time: Computing the codebook takes time
• ❌ Requires tuning: The number of sub-vectors affects accuracy

Used by

• Faiss (IVF + PQ combined)
• Milvus (PQ addon)

When to use PQ

Use PQ when:

• ✅ You have >5M vectors and limited RAM
• ✅ 85-90% accuracy is enough
• ✅ Memory cost is critical
• ✅ You can tolerate 30-50ms latency

RAG example: Internal knowledge base (10M documents, 85% accuracy OK, limited RAM).

---

📊 Comparison: HNSW vs IVF vs PQ

Comparison table

Dimension	HNSW	IVF	PQ
Complexity	O(log n)	O(sqrt(n))	O(n) compressed
Accuracy	95-99%	90-95%	85-90%
Latency (1M vecs)	15-20 ms	30-50 ms	20-40 ms
Memory (1M vecs)	4-8 GB	1-2 GB	0.5-1 GB
Build time (1M vecs)	5-10 min	2-3 min	10-15 min
Incremental updates	✅ Yes	❌ No (rebuild)	❌ No (rebuild)
Used by	ChromaDB, Weaviate	Faiss, Milvus	Faiss, Milvus

Trade-off visualization

Accuracy vs Memory

High Accuracy (98%) ┤  HNSW
                    │    │
                    │    │
Medium Accuracy     │      IVF
(93%)               │        │
                    │        │
Low Accuracy (88%)  │          PQ
                    │
                    └──────────────────
                      Low ← Memory → High
                      0.5GB  2GB  8GB

Which one to choose?

Decision tree:

Is >95% accuracy required?
│
├─ Yes → HNSW
│        (ChromaDB, Weaviate)
│
└─ No → Is memory limited?
        │
        ├─ Yes → PQ
        │        (Faiss IVF+PQ)
        │
        └─ No → >1M vectors?
                │
                ├─ Yes → IVF
                │        (Faiss, Milvus)
                │
                └─ No → HNSW
                        (ChromaDB)

---

🏭 Algorithm 4: ScaNN (Bonus)

What is it?

ScaNN (Scalable Nearest Neighbors) is a Google Research algorithm that uses learned quantization + anisotropic vector quantization.

Trade-offs

Advantages:

• ✅ Accuracy similar to HNSW (97-99%)
• ✅ Latency 2-3x better than HNSW with >5M vectors
• ✅ Memory comparable to HNSW

Disadvantages:

• ❌ High implementation complexity
• ❌ Requires TensorFlow (not standalone)
• ❌ Very slow build time (research-grade)

Used by

• Google Vertex AI Matching Engine
• Research projects (not mainstream in OSS)

Recommendation: As an AI Engineer, focus on HNSW/IVF/PQ. ScaNN is for edge cases.

---

✅ Comprehension checklist

Verify that you understood this capsule:

• Why doesn't brute force O(n) scale?

  • Answer: With 1M vectors it takes 1500ms. The typical requirement is <500ms. It doesn't meet it.

• What is indexing?

  • Answer: Building a data structure (graph, clusters, codebook) for O(log n) vs O(n) search.

• What is the trade-off of HNSW vs IVF?

  • Answer: HNSW = higher accuracy (98%) + more memory (8 GB). IVF = lower accuracy (93%) + less memory (2 GB).

• When to use PQ?

  • Answer: When you have >5M vectors, limited RAM, and 85-90% accuracy is enough.

• Which algorithm does ChromaDB use?

  • Answer: HNSW (default). High accuracy, good latency, simple setup.

If you answered 4-5/5 correctly → ✅ Ready for Capsule 04 (HNSW in depth)

---

🔗 Connection with RAG

How does this help in RAG?

Choosing a vector database based on the algorithm

Scenario A: RAG MVP (10K documents)

• Algorithm: HNSW (ChromaDB)
• Reason: High accuracy, simple setup, enough memory
• Latency: <20ms

Scenario B: Production RAG (1M documents)

• Algorithm: HNSW (Pinecone, Weaviate)
• Reason: Accuracy critical, managed service scales automatically
• Latency: <50ms

Scenario C: Massive RAG (10M documents, limited budget)

• Algorithm: IVF + PQ (Faiss self-hosted)
• Reason: Limited memory, 90% accuracy OK
• Latency: <100ms (acceptable for batch)

Debugging accuracy issues

Problem: "My RAG returns irrelevant results."

Diagnosis with algorithm knowledge:

1. Check the index accuracy:
   • HNSW → 98% accuracy expected
   • IVF → 93% accuracy expected
   • PQ → 88% accuracy expected
2. If accuracy is lower than expected → an embeddings problem (not indexing)
3. If accuracy is as expected → a prompt/chunking problem

---

🚀 Next step

In capsule 03 you saw the overview of the algorithms. Now we'll go deeper into HNSW (the most used).

Next capsule: 04 - HNSW (Hierarchical Navigable Small World)

You'll learn:

• How the hierarchical navigable graph works (conceptual)
• Why it's O(log n) (navigation vs full visit)
• Key parameters (efConstruction, M)
• Why ChromaDB uses HNSW

Key: You'll understand HNSW's architecture enough to configure and debug it (without implementing it from scratch).

---

Reading time: 8-10 minutes
Next: 04-hnsw-in-depth.md