HNSW vs IVF vs Flat Indexes

Vector Indexing Algorithms

A Vector Database cannot perform brute-force search across millions of vectors for real-time production APIs.

It builds a Vector Index data structure to navigate high-dimensional space efficiently.

Three primary vector index families dominate modern AI systems:

┌──────────────────────────┬──────────────────────────┬──────────────────────────┐
│ 1. FLAT INDEX (FLAT)     │ 2. INVERTED FILE (IVF)   │ 3. GRAPH-BASED (HNSW)    │
├──────────────────────────┼──────────────────────────┼──────────────────────────┤
│ Brute-force exact search.│ Clusters space into      │ Multi-layer proximity    │
│ 100% Exact Recall.       │ Voronoi cells.           │ small-world graph.       │
│ Slow $O(N \cdot d)$      │ Fast, low RAM.           │ Industry Standard SOTA!  │
│ Best for $<10k$ vectors. │ Needs training step.     │ Highest speed & recall!  │
└──────────────────────────┴──────────────────────────┴──────────────────────────┘

1. Flat Index (Exact Brute-Force)

Measures exact distance from query vector $q$ to every single vector in the database.

• Recall: $100%$ (Exact match guaranteed).
• Build Time: $0$ seconds (No index training required).
• Search Complexity: $\mathcal{O}(N \cdot d)$.
• Use Case: Small datasets ($N < 10,000$) where exact recall is required.

2. Inverted File Index (IVF)

Divides vector space into $K$ Voronoi Cells using k-Means clustering:

  HIGH DIMENSIONAL SPACE SPLIT INTO VORONOI CELLS
  ┌──────────┬──────────┬──────────┐
  │ Cell 1   │ Cell 2   │ Cell 3   │
  │   (•)    │   (•)    │   (•)    │ ◄── Centroids!
  ├──────────┼──────────┼──────────┤
  │ Cell 4   │ Cell 5   │ Cell 6   │
  └──────────┴──────────┴──────────┘

Search Process

1. Find nearest Voronoi centroid to query vector $q$.
2. Search vectors ONLY inside the nprobe closest Voronoi cells, ignoring the rest of the database!

• nlist: Total number of Voronoi clusters constructed during indexing.
• nprobe: Number of adjacent Voronoi cells searched per query (e.g. nprobe = 16).
  • High nprobe $\implies$ Higher Recall, Slower Speed.
  • Low nprobe $\implies$ Lower Recall, Faster Speed.

3. Hierarchical Navigable Small World (HNSW - Malkov & Yashunin, 2018)

HNSW is the state-of-the-art index for vector search (used in Qdrant, Pinecone, FAISS).

It builds a Multi-Layer Proximity Graph inspired by Skip Lists:

  Layer 2 (Top Layer - Long Jumps!):     [ Node A ] ───────────────────────► [ Node Z ]
                                             │                                  │
  Layer 1 (Middle Layer):                [ Node A ] ────────► [ Node M ] ──────► [ Node Z ]
                                             │                   │              │
  Layer 0 (Bottom Layer - Dense Graph):  [ Node A ] ──► [ B ] ──►[ M ] ──►[ P ]─►[ Z ]

HNSW Query Traversal

1. Start at top layer (Layer 2) with sparse long-distance links $\to$ Perform fast greedy routing jumps toward target neighborhood.
2. Drop down to middle layers $\to$ Refine routing trajectory.
3. Drop down to Layer 0 (dense local graph) $\to$ Perform fine-grained local neighbor search.

Search complexity scales to $\mathcal{O}(\log N)$ logarithmic time, delivering sub-millisecond search speeds with $99%$ recall!

Detailed Index Comparison Matrix

Say this out loud

Flat indexing performs 100 percent exact brute force search for small datasets under 10k vectors. IVF clusters vector space into Voronoi cells, searching only nprobe candidate clusters. HNSW builds multi layer proximity small world graphs, routing fast long distance jumps on top layers and fine local searches on bottom layers to deliver sub millisecond logarithmic search speed.

Followups to expect

1. What is Product Quantization (IVF-PQ)? Combining IVF cell routing with Product Quantization, compressing 1024-d vectors into 64-byte codebook bytes to store billions of vectors in system RAM.
2. What is the HNSW ef_construction and ef_search hyperparameter? ef_construction controls graph quality during build time. ef_search controls dynamic candidate queue size during search time (higher ef_search increases recall at the cost of higher latency).