Capsule 04: HNSW - Hierarchical Navigable Small World

🎯 Capsule objective

Understand HOW HNSW works (hierarchical navigable graph) conceptually, why it achieves O(log n), and when to use it in RAG systems.

By the end of this capsule:

• ✅ You'll explain what a hierarchical navigable graph is
• ✅ You'll understand why HNSW is O(log n) (not O(n))
• ✅ You'll know the key parameters (M, efConstruction, efSearch)
• ✅ You'll decide when to use HNSW vs other algorithms

Estimated time: 10-12 minutes

---

🧩 What is HNSW?

Definition

HNSW = Hierarchical Navigable Small World

It's a navigable graph organized into hierarchical layers, where each layer has a subset of nodes and long-range connections (small world property).

Small World Graph (a prior concept)

Small World is a property of graphs where:

• Most nodes are NOT directly connected
• But any pair of nodes is a few jumps apart

Example: A social network (6 degrees of separation)

• You don't know everyone directly
• But you can reach any person in ~6 jumps (friend of friend of friend...)

Applied to vectors:

• Each vector is a node
• Similar nodes are connected
• You can reach any similar vector in a few jumps (O(log n))

---

🏗️ HNSW architecture

Hierarchical layers

HNSW organizes vectors into multiple layers (levels), where:

• Top layer (Layer 2+): Few nodes, long connections (big jumps)
• Middle layer (Layer 1): More nodes, medium connections
• Base layer (Layer 0): ALL nodes, short connections

Visualization:

Layer 2 (Top):    A ←─────────→ B
                  │             │
                  │             │
Layer 1:          A ←─→ C ←─→ D ←─→ B
                  │    │     │     │
                  │    │     │     │
Layer 0 (Base):   A→C→E→F→G→D→H→I→B
                  (all the vectors)

Key:

• Layer 2: Only A and B (long jump A→B)
• Layer 1: A, B, C, D (medium jumps)
• Layer 0: All the vectors (short jumps)

Why hierarchical?

Analogy: A transportation system

Without hierarchy (brute force):

• You only walk (no highways)
• From A to B = 100 km walking = 20 hours

With hierarchy (HNSW):

• Walk to the train station (1 km = 15 min)
• Train to a nearby city (90 km = 1 hour)
• Walk to the final destination (1 km = 15 min)
• Total: 1h 30min (vs 20 hours)

Applied to search:

• Layer 2: Long jumps (find the right region)
• Layer 1: Medium jumps (refine the region)
• Layer 0: Short jumps (find the exact neighbor)

---

🔍 How it works: Search in HNSW

Navigation algorithm (conceptual)

def search_hnsw(query, graph, k=10):
    # Step 1: Start at the top layer with a random node
    current_layer = max_layer
    current_node = entry_point  # Starting node
    
    # Step 2: Navigate downward
    while current_layer > 0:
        # Find the neighbor closest to the query in the current layer
        current_node = greedy_search(query, current_node, current_layer)
        
        # Go down to the lower layer
        current_layer -= 1
    
    # Step 3: Final search in the base layer (Layer 0)
    candidates = greedy_search(query, current_node, layer=0)
    
    # Step 4: Return the top-k most similar
    return top_k(candidates, k)

Step-by-step example

Scenario: Search for a document similar to the query "Python asyncio tutorial"

Database: 1,000,000 vectors in HNSW with 3 layers

Step 1: Start at Layer 2 (Top)

Query embedding: [0.1, 0.5, 0.8, ...]

Layer 2:  A ←─────────→ B
         (entry_point)

Compare the query with A and B:
- Similarity(query, A) = 0.3
- Similarity(query, B) = 0.7  ← Closer

→ Move to B

Step 2: Go down to Layer 1

Layer 1:  A ←─→ C ←─→ D ←─→ B
                          (current)

Neighbors of B in Layer 1: C, D
Compare the query with the neighbors:
- Similarity(query, C) = 0.6
- Similarity(query, D) = 0.8  ← Closer

→ Move to D

Step 3: Go down to Layer 0 (Base)

Layer 0:  ... → D → H → I → J → ...
                (current)

Neighbors of D in Layer 0: H, I, J, K, ...
Compare the query with the neighbors:
- Similarity(query, H) = 0.75
- Similarity(query, I) = 0.85  ← Top 1
- Similarity(query, J) = 0.82  ← Top 2
- ...

→ Return top-10: [I, J, K, ...]

Total comparisons: ~50-100 (vs 1,000,000 in brute force)

Speedup: 10,000x - 20,000x

---

📊 Why HNSW is O(log n)

Complexity analysis

Brute force:

for vector in database:  # n iterations
    compare(query, vector)

→ O(n)

HNSW:

# Layer 2: ~10 nodes, ~5 comparisons
# Layer 1: ~100 nodes, ~10 comparisons
# Layer 0: ~1000 nodes, ~20 comparisons

Total comparisons ≈ log2(n) * M
→ O(log n)

Where:

• n = total number of vectors
• M = number of connections per node (configurable parameter)

Benchmark: Real comparisons

Vectors (n)	Brute Force	HNSW	Speedup
10K	10,000	50	200x
100K	100,000	75	1,333x
1M	1,000,000	100	10,000x
10M	10,000,000	150	66,666x

Key: HNSW grows logarithmically (100→150 comparisons when n grows 10x).

---

⚙️ Key HNSW parameters

1. M (Connections per node)

Definition: The maximum number of bidirectional connections per node in each layer.

Impact:

• High M (64, 128):

  • ✅ Higher accuracy (more alternative paths)
  • ❌ More memory (more connections stored)
  • ❌ Slower build time

• Low M (4, 8):

  • ✅ Less memory
  • ✅ Faster build
  • ❌ Lower accuracy (fewer paths)

Recommended:

• M = 16 (default ChromaDB, Weaviate) → Accuracy/memory balance
• M = 32 (high accuracy) → Cases where accuracy is critical
• M = 8 (low memory) → Cases with limited memory

2. efConstruction (Effort Construction)

Definition: The number of candidates explored during index construction.

Impact:

• High efConstruction (200, 400):

  • ✅ Higher-quality index (better accuracy)
  • ❌ Slower build time

• Low efConstruction (50, 100):

  • ✅ Fast build
  • ❌ Lower accuracy

Recommended:

• efConstruction = 200 (default) → Balance
• efConstruction = 400 (high accuracy) → Critical production
• efConstruction = 100 (fast build) → Development/testing

3. efSearch (Effort Search)

Definition: The number of candidates explored during search (query time).

Impact:

• High efSearch (200, 500):

  • ✅ Higher accuracy (explores more neighbors)
  • ❌ Higher latency (more comparisons)

• Low efSearch (50, 100):

  • ✅ Lower latency
  • ❌ Lower accuracy

Recommended:

• efSearch = 100 (default) → Balance
• efSearch = 200 (high accuracy) → Critical RAG
• efSearch = 50 (fast query) → Performance-critical

Trade-offs visualized

Accuracy vs Speed vs Memory

                  efConstruction=400
High Accuracy     M=32, efSearch=200
(98%)            ▲
                 │  ← High Memory (8 GB)
                 │     Slow Build (10 min)
Medium           │     Fast Query (15ms)
Accuracy         │
(95%)            │  efConstruction=200
                 │  M=16, efSearch=100
                 │  ← Medium Memory (4 GB)
Low Accuracy     │     Medium Build (5 min)
(92%)            │     Medium Query (25ms)
                 │
                 └──────────────────────
                   Low ← Resources → High

---

🏭 HNSW in practice

ChromaDB configuration

ChromaDB uses HNSW by default. You can configure the parameters:

import chromadb

# Create a collection with custom HNSW
collection = client.create_collection(
    name="my_docs",
    metadata={
        "hnsw:space": "cosine",  # Distance metric
        "hnsw:M": 32,  # More connections (higher accuracy)
        "hnsw:construction_ef": 200,  # Build quality
        "hnsw:search_ef": 100,  # Query quality
    }
)

When to tune:

• Accuracy <90% → Increase M and efSearch
• Build time very slow → Reduce efConstruction
• Query latency >100ms → Reduce efSearch

Weaviate configuration

collection_config = {
    "vectorIndexType": "hnsw",
    "vectorIndexConfig": {
        "maxConnections": 64,  # M parameter
        "efConstruction": 128,
        "ef": 100,  # efSearch
    }
}

Pinecone (HNSW-like custom)

Pinecone uses an algorithm similar to HNSW (it doesn't expose the parameters directly):

# Pinecone handles tuning automatically
index.query(
    vector=query_embedding,
    top_k=10,
    # You don't configure M, ef (managed service)
)

---

✅ Advantages and disadvantages of HNSW

Advantages

1. High accuracy (95-99%)

   • Better than IVF (90-95%) and PQ (85-90%)
   • Almost perfect vs brute force

2. Predictable latency

   • O(log n) guaranteed
   • 15-20ms for 1M vectors (consistent)

3. Incremental updates

   • You can add vectors one by one
   • No full rebuild required (vs IVF)

4. Mature open source

   • hnswlib (C++ library)
   • Integrated in ChromaDB, Weaviate, Qdrant

Disadvantages

1. High memory

   • 4-8 GB for 1M vectors (1536-dim)
   • Connections (edges) stored in RAM

2. Slow build time

   • 5-10 min for 1M vectors
   • Trade-off: Better index quality

3. No vector compression

   • Full dimensionality stored
   • To compress, combine with PQ

4. Costly delete operations

   • Requires rebuilding connections
   • Better to use soft deletes (metadata filter)

---

🔗 Connection with RAG

Why is HNSW ideal for RAG?

Typical RAG requirements:

1. Critical accuracy (>95%) → HNSW meets it (98%)
2. Latency <500ms → HNSW meets it (15-20ms)
3. Incremental updates (adding documents daily) → HNSW supports it
4. Moderate scale (100K-1M documents MVP) → HNSW handles well

Acceptable trade-off:

• High memory (4-8 GB) is OK for MVP/mid-size RAG

RAG + HNSW use cases

Case A: Customer Support Chatbot

• Documents: 50K support articles
• Requirement: Accuracy >95%, Latency <500ms
• Solution: ChromaDB with HNSW (default config)
• Result: 98% accuracy, 15ms latency, 2 GB RAM

Case B: Internal Knowledge Base

• Documents: 500K Confluence pages + Slack messages
• Requirement: Accuracy >90%, Latency <1s
• Solution: Weaviate with HNSW (M=32, efSearch=200)
• Result: 97% accuracy, 50ms latency, 16 GB RAM

Case C: Legal Document Search

• Documents: 1M legal cases
• Requirement: Accuracy >98% (critical)
• Solution: Pinecone (HNSW-like, managed)
• Result: 99% accuracy, 30ms latency, managed RAM

---

✅ Comprehension checklist

Verify that you understood this capsule:

• What is HNSW?

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

• Why is HNSW O(log n)?

  • Answer: You don't visit all the nodes (n), you only navigate ~log2(n) * M nodes using the hierarchy.

• What does the M parameter do?

  • Answer: The number of connections per node. High M = higher accuracy + more memory. Low M = less memory + lower accuracy.

• When to use HNSW vs IVF?

  • Answer: HNSW when accuracy is critical (>95%), you have enough RAM, and updates are incremental. IVF when >1M vectors and 90% accuracy is OK.

• Why does ChromaDB use HNSW?

  • Answer: A perfect balance for RAG: High accuracy (98%), low latency (15ms), incremental updates, simple setup.

If you answered 4-5/5 correctly → ✅ Ready for Capsule 05 (IVF)

---

🚀 Next step

Now that you understand HNSW deeply, you'll learn about IVF (Inverted File Index).

Next capsule: 05 - IVF (Inverted File Index)

You'll learn:

• How vector clustering works (k-means)
• Why IVF is better than HNSW for >1M vectors
• The accuracy vs memory trade-off
• When to migrate from HNSW to IVF

Key: IVF sacrifices accuracy (93% vs 98% HNSW) but gains in memory and scale.

---

Reading time: 10-12 minutes
Next: 05-ivf-clustering.md