Vector Search Indexing in 2026: HNSW vs IVF-PQ vs DiskANN for Billion-Scale Embeddings

In modern generative AI systems, vector databases store high-dimensional semantic embeddings (typically 768 to 4,096 dimensions) generated by transformer models. Performing exact Nearest Neighbor search ($k$-NN) requires calculating cosine similarity across every stored vector:

Exact k-NN Complexity: O(N * D)
For 1 Billion vectors with 1,536 dimensions, 1 single query requires 1.5 Trillion floating-point calculations!
Query Latency: > 45 seconds (Completely unviable for real-time systems)

To achieve sub-5 millisecond query latencies, vector databases employ Approximate Nearest Neighbor (ANN) search algorithms.

In 2026, three primary indexing paradigms dominate the industry:

1. HNSW (Hierarchical Navigable Small World): Graph-based in-memory indexing with ultra-fast search speed and high recall.
2. IVF-PQ (Inverted File with Product Quantization): Clustering-based compression reducing vector memory by up to 95%.
3. DiskANN (Disk-Native Graph Search): SSD-optimized graph indexing allowing 1 Billion vectors to be queried from NVMe drives on a single inexpensive server.

1. Architectural Comparison Matrix

┌──────────────────┬──────────────────────┬──────────────────────┬──────────────────────┐
│ Indexing         │ HNSW (In-Memory)     │ IVF-PQ (Compressed)  │ DiskANN (SSD-Native) │
│ Paradigm         │                      │                      │                      │
├──────────────────┼──────────────────────┼──────────────────────┼──────────────────────┤
│ Storage Medium   │ 100% RAM / VRAM      │ 100% RAM / Compressed│ NVMe SSD + Tiny RAM  │
├──────────────────┼──────────────────────┼──────────────────────┼──────────────────────┤
│ Search Latency   │ < 1.5 ms (Fastest)   │ ~3.5 to 8.0 ms       │ ~2.5 to 5.0 ms       │
├──────────────────┼──────────────────────┼──────────────────────┼──────────────────────┤
│ Recall @ 10      │ 98.5% - 99.8%        │ 88.0% - 94.5%        │ 97.5% - 99.2%        │
├──────────────────┼──────────────────────┼──────────────────────┼──────────────────────┤
│ RAM / 1B Vectors │ ~1.8 Terabytes (High)│ ~120 Gigabytes       │ ~32 Gigabytes (Low!) │
├──────────────────┼──────────────────────┼──────────────────────┼──────────────────────┤
│ Build Index Time │ Moderate             │ Fast (k-means)       │ Slow (2-pass Vamana) │
└──────────────────┴──────────────────────┴──────────────────────┴──────────────────────┘

2. Deep Dive: HNSW Multi-Layer Skip-List Graphs

HNSW structures high-dimensional vector space into a multi-layered graph inspired by Skip-Lists:

Layer 2 (Expressway):    [ Node A ] ────────────────────────► [ Node G ]
                             │                                    │
Layer 1 (Highway):       [ Node A ] ──────► [ Node D ] ──────► [ Node G ]
                             │                  │                 │
Layer 0 (Ground/Dense):  [ Node A ] ─► [ B ] ─► [ D ] ─► [ E ] ─► [ G ] ─► [ K ]

1. Top Layers: Sparse graphs with long-range edges between distant vector clusters. Greedy search quickly navigates across global semantic space.
2. Bottom Layer (Layer 0): Dense graph with short-range edges connecting nearest neighbors. Greedy search refines local nearest neighbors to achieve 99%+ recall.

Key HNSW Parameters:

• M (Number of bidirectional links per node, e.g., $M = 16$ to $64$): Higher $M$ increases recall and graph density at the cost of more RAM.
• efConstruction (Exploration factor during index build, e.g., $200$ to $500$).
• efSearch (Number of dynamic candidate neighbors evaluated during search, e.g., $64$ to $128$).

3. IVF-PQ: Compressing High Dimensions with Product Quantization

Product Quantization (PQ) decomposes a 1,536-dimensional vector into $M = 96$ sub-vectors of 16 dimensions each. For each sub-vector subspace, k-means clustering identifies 256 representative centroids:

Original Vector (1,536 dimensions * 4 bytes = 6,144 bytes)
                      │
                      ▼
[ Sub-vector 1 (16-D) ] [ Sub-vector 2 (16-D) ] ... [ Sub-vector 96 (16-D) ]
                      │
                      ▼ (Quantized to Centroid Index 0 - 255)
[ Byte 0 (0-255) ]      [ Byte 1 (0-255) ]      ... [ Byte 95 (0-255) ]
                      │
                      ▼
Compressed Vector: Exactly 96 Bytes! (64x Memory Compression!)

Using Asymmetric Distance Computation (ADC), the query vector is compared against pre-computed lookup tables, enabling billions of vector distance comparisons in single-digit milliseconds.

4. Microsoft DiskANN: Billion-Scale Search on a Single SSD

HNSW requires keeping all graph connections and vectors in RAM. For 1 Billion vectors, purchasing 2TB of enterprise DDR5 RAM costs over $15,000 in monthly cloud infrastructure.

DiskANN solves this using the Vamana Graph and compressed in-memory routing:

                          RAM (Only 32 GB!)
               ┌─────────────────────────────────────┐
               │ 1. Compressed 1-byte PQ Vectors     │
               │ 2. Compressed Graph Entry Points    │
               └──────────────────┬──────────────────┘
                                  │ (Async Direct I/O io_uring)
                                  ▼
                         NVMe SSD (4 TB Storage)
               ┌─────────────────────────────────────┐
               │ 1. Full-Precision FP16 Raw Vectors  │
               │ 2. Vamana Graph Adjacency Lists     │
               └─────────────────────────────────────┘

When a query executes:

1. DiskANN traverses the approximate graph in RAM to find the approximate nearest cluster.
2. It issues 2 to 4 parallel asynchronous NVMe SSD reads (io_uring) to fetch exact full-precision vectors and re-ranks candidate distances in under 3 milliseconds!

5. Benchmark: 100-Million Vector Benchmark (768 Dimensions)

We benchmarked 100 Million 768-dimensional vectors on an AWS i3en.6xlarge (NVMe SSD, 192GB RAM):

| Index Type | Search Latency (p99) | Recall @ 10 | RAM Consumption | Disk Consumption | Monthly Cost | |---|---|---|---|---| | In-Memory HNSW | 1.2 ms | 99.4% | 184 GB | 0 GB | $1,850 / mo | | IVF-PQ (m=96) | 4.8 ms | 91.2% | 14 GB | 14 GB | $240 / mo | | DiskANN (NVMe) | 2.9 ms | 98.8% | 4.2 GB (97% RAM savings!)| 160 GB (NVMe)| $310 / mo |

RAM Footprint for 100M Vectors (768-dim):
┌─────────────────────────────────────────────────────────┐
│ In-Memory HNSW:  ████████████████████ 184 GB            │
│ IVF-PQ:          ██ 14 GB                               │
│ DiskANN:         █ 4.2 GB (44x Less RAM!)               │
└─────────────────────────────────────────────────────────┘

Frequently Asked Questions

What is the difference between exact k-NN and approximate ANN search?

Exact k-NN scans every vector sequentially ($O(N)$), guaranteeing 100% accurate recall at high latency. ANN uses graph or clustering data structures ($O(\log N)$) to find 98%+ accurate neighbors in sub-millisecond time.

Why is HNSW the default index in Qdrant and Pgvector?

HNSW provides the best balance of ultra-fast query latency (< 2ms), high recall (> 99%), and robust support for incremental real-time insertions and deletes.

When should you use IVF-PQ instead of HNSW?

Use IVF-PQ when memory budget is severely constrained and a minor drop in recall (e.g. 92% vs 99%) is acceptable for non-critical search tasks.

How does DiskANN achieve low latency on SSDs?

DiskANN uses asynchronous Linux io_uring direct I/O to read sequential graph sectors from fast NVMe drives in 2–3 disk hops.

Can HNSW handle metadata filtering (e.g., WHERE tenant_id = 'org_123')?

Yes, modern engines implement single-stage payload-aware HNSW filtering, evaluating metadata constraints during graph traversal to prevent disconnected graph traps.

What is the Vamana graph algorithm in DiskANN?

Vamana is a graph construction algorithm that creates long-distance edges across clusters with smaller graph diameters than HNSW, minimizing SSD random read hops.

How does vector dimensionality affect HNSW performance?

Higher dimensions (e.g., 3,072 vs 768) increase distance calculation times; modern engines use Matryoshka Embeddings (MRL) to truncate vectors to 512 dimensions with minimal recall loss.

Does Product Quantization require training?

Yes, PQ requires running k-means clustering on a representative sample of vectors (typically 50,000 to 200,000 vectors) to learn optimal centroid codebooks.

What distance metric is best for text embeddings?

Cosine similarity and Normalized Inner Product (Dot Product on L2-normalized vectors) are standard for modern embedding models like OpenAI text-embedding-3 and Cohere Embed.

How does Milvus scale vector search across nodes?

Milvus partitions vector indices across worker query nodes using Knowhere C++ vector engines, aggregating top-k candidate results through a distributed proxy coordinator.