Vector Database Indexing Benchmarks: HNSW vs IVF-PQ Across 1 Billion Vectors

The explosion of generative AI and semantic search has pushed vector databases from niche research tools into the core of modern data infrastructure. As embedding models generate higher-dimensional vectors and datasets scale into the billions, the choice of indexing algorithm becomes make-or-break for application performance. Two approaches dominate the landscape: Hierarchical Navigable Small Worlds (HNSW) and Inverted File with Product Quantization (IVF-PQ). Benchmarking these algorithms across one billion vectors reveals profound trade-offs between speed, memory efficiency, and recall that directly shape architectural decisions for large-scale AI applications.

Before diving into benchmarks, it's critical to understand why the one-billion threshold matters. At this scale, brute-force search is computationally infeasible—scanning a billion 1536-dimensional vectors per query would take seconds per search, even on optimized hardware. Approximate Nearest Neighbor (ANN) indexing trades a small amount of recall for orders-of-magnitude speedups. However, the scaling characteristics of different indexing algorithms diverge dramatically at this scale. Memory consumption becomes a primary constraint; storing a billion float32 vectors in raw form requires over 6 terabytes, far exceeding typical server memory capacities. Both HNSW and IVF-PQ address this challenge but through fundamentally different mechanisms.

HNSW is a graph-based algorithm that constructs a multi-layered navigable graph where each vector is a node connected to its nearest neighbors. Search begins at the top layer with sparse connections, progressively descending to denser lower layers to refine results. This greedy graph traversal delivers exceptional query performance with high recall.

At the one-billion-vector scale, HNSW's strengths and weaknesses become pronounced. On the positive side, it consistently achieves the highest queries per second (QPS) at any given recall target. In benchmarks with 1536-dimensional OpenAI embeddings, HNSW typically delivers 2-3x higher QPS than IVF-PQ at 95% recall. Its latency profile is also more predictable, with p99 latency often 30-50% lower than IVF-PQ under high concurrency. The graph structure naturally adapts to data distribution, maintaining consistent performance across different vector datasets.

However, HNSW's memory footprint is its Achilles' heel. The graph structure requires storing neighbor pointers alongside vectors, adding roughly 30-40% memory overhead compared to raw vectors. For one billion vectors, this translates to 8-10 terabytes of RAM for full in-memory operation. Building the index is also computationally expensive, often taking days on a single machine and requiring careful batch insertion to avoid performance cliffs. HNSW also struggles with dynamic updates; inserting new vectors can degrade graph quality over time, necessitating periodic re-indexing.

IVF-PQ combines two techniques: Inverted File indexing for coarse partitioning and Product Quantization for aggressive compression. IVF divides the vector space into clusters using k-means, and queries only search the most relevant clusters. Product Quantization further compresses each vector into a compact code—typically 256-512 times smaller than the original—by splitting vectors into subspaces and quantizing each independently.

At billion-scale, IVF-PQ's memory efficiency is transformative. With 64-bit PQ codes, a billion vectors fit in just 80 gigabytes—two orders of magnitude less than HNSW. This makes it feasible to run billion-vector indexes on commodity servers or even in GPU memory. Disk-based deployments become practical; the compressed codes are small enough that even SSD-based IVF-PQ can deliver competitive latency.

The trade-off is query performance. At equivalent recall levels, IVF-PQ generally achieves 30-50% of HNSW's QPS. The quantization introduces irreversible information loss, making it harder to reach very high recall targets—achieving 99% recall with IVF-PQ often requires scanning more clusters, which erodes the performance advantage. IVF-PQ also requires careful parameter tuning: the number of centroids, PQ code length, and nprobe parameter all interact in complex ways that depend heavily on data distribution.

Real-world benchmarks across billion-vector datasets reveal nuanced decision points. For latency-critical applications like real-time recommendation systems where sub-20ms p99 latency is required and recall targets are moderate (90-95%), HNSW is usually the clear winner despite higher infrastructure costs. For cost-sensitive applications with looser latency requirements—such as batch semantic search or archival retrieval—IVF-PQ delivers 90% of the value at 10% of the infrastructure cost.

The picture becomes more interesting when considering hybrid approaches. Many production systems use HNSW for hot data and IVF-PQ for cold archival data, implementing tiered search that routes queries based on freshness requirements. Some vector databases now offer HNSW with scalar quantization (HNSW-SQ), which closes the memory gap by compressing vectors to 8-bit integers while preserving most of HNSW's speed advantage.

The HNSW versus IVF-PQ debate is not about which algorithm is "better"—it's about matching the right tool to the right constraints at the right scale. At one billion vectors, these constraints become impossible to ignore. HNSW offers the gold standard for query performance and simplicity of operation at the cost of significant infrastructure investment. IVF-PQ provides unmatched memory efficiency and cost-effectiveness, requiring more engineering effort to tune and operate. As vector databases continue to evolve—with innovations like disk-optimized HNSW variants and learned indexing approaches—the billion-vector benchmark will remain the critical proving ground where theoretical algorithmic advantages translate into real-world application performance.