Vector Indexing at Scale: HNSW vs. IVF-PQ in 100M-Vector Repositories

When vector retrieval systems scale past 10 million embeddings, engineering teams usually absorb the memory bill without questioning the underlying indexing architecture. When that corpus expands to 100 million 1536-dimensional vectors—the standard operational scale for enterprise code intelligence, legal discovery, and multi-tenant RAG repositories—the standard approach collapses into a hardware wall. A naive Hierarchical Navigable Small World (HNSW) graph in full 32-bit floating point precision demands over 1.28 terabytes of resident RAM. At prevailing hyperscaler rates, maintaining that single in-memory index burns between $13,800 and $16,500 every month in cloud infrastructure.

The immediate architectural dilemma splits every platform engineering team into two camps: preserve sub-5-millisecond latency and 99% recall by paying the multi-terabyte memory penalty, or compress embeddings with Inverted File Product Quantization (IVF-PQ) to run on a $780-per-month commodity node while accepting an 8% to 15% drop in top-10 retrieval accuracy. Between these extremes lies a spectrum of quantization schemes, memory-mapped disk graphs, and two-stage reranking pipelines that alter the cost-performance Pareto frontier.

1. The HNSW Microarchitecture: Skip-Lists in High-Dimensional Space

Hierarchical Navigable Small World graphs translate the probabilistic skip-list concept into multi-dimensional metric spaces. Rather than evaluating brute-force k-Nearest Neighbor (k-NN) scans across the entire corpus—which requires 100 million vector dot products per query—HNSW organizes vectors into a hierarchy of proximity graphs. The top layers contain long-range highway edges connecting sparse cluster representatives, while the bottom layer (Layer 0) contains every vector connected to its M nearest neighbors.

During query routing, the search algorithm begins at the top layer, greedily traversing neighbor links that minimize distance to the query vector. Once a local minimum is reached in layer l, the search drops to layer l – 1, using the entry point found above. This logarithmic routing continues until reaching Layer 0, where a bounded priority queue of size ef_search explores the local graph neighborhood to return the final top-k candidates.

The fatal flaw of HNSW at 100-million scale is not its search speed—which remains blistering at 4.2 milliseconds P95 latency—but its total intolerance for disk-based paging. Graph traversal is fundamentally random access. Following an edge requires jumping to an arbitrary memory address holding the neighbor’s coordinate vector. When an in-memory HNSW index exceeds physical RAM and spills into NVMe swap or memory-mapped files, every graph step triggers random 4KB OS page faults.

Under PCIe Gen 5 NVMe SSDs with random read latencies around 45 to 70 microseconds, an ef_search traversal examining 128 nodes accumulates over 8 milliseconds of raw kernel I/O wait per query. Under concurrent load (500 queries per second), OS page cache contention triggers severe thread stalling, collapsing throughput from 1,150 QPS down to fewer than 65 QPS.

2. IVF-PQ Deconstructed: Subspace Decomposition and Precomputed Codebooks

Inverted File with Product Quantization addresses the memory wall by attacking two independent dimensions: search space reduction (IVF) and vector representation size (PQ). Instead of maintaining an explicit graph over every entity, IVF partitions the high-dimensional vector space into nlist Voronoi cells using k-means clustering.

During indexing, each vector is assigned to its nearest centroid. At search time, the query vector evaluates distances to all nlist centroids and only inspects the vectors stored inside the nprobe closest cells. If nlist = 16,384 and nprobe = 32, the query only searches 0.195% of the total corpus.

However, coarse Voronoi pruning alone does not solve the memory crisis. Storing 100 million uncompressed 1536-dimensional vectors inside inverted lists still demands 614.4 GB of RAM. This is where Product Quantization applies aggressive lossy compression.

By compressing each 1536-dimensional embedding from 6,144 bytes down to 96 bytes (a 98.4% reduction), the total raw vector storage for 100 million embeddings drops from 614.4 GB to just 9.6 GB. Even after factoring in inverted list posting overhead, inverted index pointers, and coarse centroid tables, the entire 100M index occupies roughly 68 GB of RAM.

3. Empirical Benchmarks: 100M Vectors on AMD EPYC 9654 Hardware

To quantify the true operational differences between graph-based and quantization-based engines, we deployed a standardized 100-million vector evaluation harness across dedicated hardware: dual AMD EPYC 9654 processors (192 physical cores, 384 threads), 1.5 TB DDR5-4800 ECC memory, and four enterprise Samsung PM1743 PCIe 5.0 NVMe SSDs configured in RAID 0.

The benchmark dataset consists of 100,000,000 synthetic text embeddings generated to mirror the cosine similarity distribution of OpenAI text-embedding-3-small (1536 dimensions, normalized unit vectors). All tests measured index build duration, steady-state resident memory, Recall@10 against an exact flat brute-force index, and P95 latency under sustained 500 QPS load.

The benchmark numbers expose a striking economic reality: while pure in-memory HNSW delivers the highest absolute search fidelity (99.1% Recall@10 at 4.2ms latency), scaling to 100 million vectors requires a multi-node cluster or an exotic 1.5 TB memory server costing over $14,000 per month. IVF-PQ slashes index construction time from 18.4 hours to 3.2 hours and fits the entire 100M-vector dataset into 68 GB of RAM, but drops recall by nearly 8 percentage points.

4. The Metadata Filtering Failure: How Predicates Shatter HNSW Graphs

In production enterprise RAG, search is almost never unconstrained. Production queries consistently append business predicates: WHERE tenant_id = 'org_492' AND created_at > 1725148800 AND access_level IN ('engineering', 'admin'). Standard documentation glosses over how metadata predicates interact with proximity graphs, yet this interaction represents the single most common cause of silent production recall outages.

When an enterprise query has high selectivity—meaning the filter matches only an effective selectivity fraction s ≪ 1 of the corpus (e.g., s = 0.01 or 0.001, matching 1% or 0.1% of vectors)—standard HNSW graph routing mathematically disintegrates:

The ACORN Paradigm: Developed at Stanford (Patel et al., SIGMOD 2024), ACORN solves this via permissive routing and two-hop exploration. Non-matching nodes are permitted to act as navigational bridges—they are visited and used to explore subsequent neighbors, but excluded from the final top-k result heap. ACORN-1 executes this dynamically at query time: if direct neighbors fail predicate P, it immediately evaluates neighbors-of-neighbors, bridging graph voids and maintaining 95%+ recall without forcing flat scans over millions of vectors.

5. The Deletion Tombstone & Segment Compaction OOM Trap

In high-velocity production systems (Slack channels, customer support threads, code repositories), vector data is dynamic. However, in an HNSW graph, physically deleting a vector requires re-computing neighbor connections for every one of its M incoming and outgoing edges across all layers. Executing full graph re-wiring on every delete under real-time concurrent query traffic causes immediate thread lock contention. Consequently, vector databases implement soft deletes using tombstones (bitsets marked in Roaring Bitmaps).

As tombstones accumulate, two critical failure modes emerge:

1. The Latency Tax: Greedy search continues to traverse tombstone nodes because they act as topological bridges. Dead vectors consume priority queue slots in ef_search, starving live candidates. At 30% tombstone density, retaining a target Recall@10 requires inflating ef_search by 1.43x, degrading P99 query latency by 35% to 50%.

2. The 2x Memory Merge Spike (The OOM Killer Trap): To reclaim dead memory, the database executes background segment compaction. Existing Segments A and B must remain resident in RAM to serve live search queries while the background thread constructs a brand-new Segment C from scratch. During compaction, memory consumption spikes to 2.0x–2.2x of baseline. If your host is running at 65% RAM utilization, a background merge operation will push total allocation past 100%, triggering the Linux Out-Of-Memory (OOM) killer to abruptly terminate the vector database process.

# Apply to production Qdrant collections to prevent unconstrained merge spikes:
PATCH /collections/enterprise_rag_100m
{
  "optimizers_config": {
    "deleted_threshold": 0.20,         # Only vacuum when >20% vectors are dead tombstones
    "vacuum_min_vector_number": 100000,# Prevent premature vacuuming of small warm segments
    "max_segment_size": 2000000,       # Cap max segment size to ~2 GB (prevents 50GB merge spikes)
    "indexing_threshold": 25000,       # Accumulate batches before triggering HNSW build
    "flush_interval_sec": 15,          # Buffer writes to reduce continuous disk churn
    "max_optimization_threads": 1      # CRITICAL: Enforce serial merging to prevent concurrent 2x spikes
  }
}

6. The 12x Compound Compression Engine: Matryoshka Embeddings (MRL) + SQ8

Modern embedding models—most notably OpenAI text-embedding-3 and Google Gemini embeddings—are trained using Matryoshka Representation Learning (MRL) (Kusupati et al., NeurIPS 2022). Unlike traditional embedding models where variance is distributed uniformly across all dimensions, MRL forces the most critical semantic features into the earliest coordinates during contrastive training.

This architectural property allows engineering teams to truncate vectors before constructing proximity graphs or applying quantization:

7. NUMA Architecture: Why Cross-Socket Interconnects Throttle Throughput

When running vector databases across high-memory dual-socket enterprise servers (such as dual AMD EPYC 9654 or Intel Xeon Platinum hosts), the physical memory bus is partitioned into distinct Non-Uniform Memory Access (NUMA) domains. Accessing local DDR5 memory attached directly to Socket 0 takes 75 to 85 nanoseconds. Accessing remote memory attached to Socket 1 via AMD Infinity Fabric or Intel UPI takes 180 to 210 nanoseconds.

Because HNSW graph traversal is fundamentally a latency-bound, pointer-chasing workload that cannot be hardware-prefetched, stalling on remote NUMA nodes degrades single-thread traversal latency by 60% to 120%. Running numactl --interleave=all is a common anti-pattern: while it balances bandwidth, it guarantees that exactly 50% of all graph pointer dereferences must cross the socket interconnect.

8. Production Engine Showdown: Qdrant vs. OpenSearch vs. Milvus vs. Faiss

Implementing these theoretical algorithms in real enterprise infrastructure requires navigating software runtime differences. Vector databases handle concurrent writes, segment merging, metadata payload filtering, and cluster failover with vastly different operational overheads.

9. Production Decision Matrix: Which Index Architecture Should You Deploy?

The decision of which vector indexing architecture to deploy is governed by a strict tripartite trade-off between vector scale, latency SLAs, and monthly infrastructure budgets:

10. The Production Takeaway

Vector databases are fundamentally memory management engines wrapped in similarity search APIs. At 100-million scale, defaulting to standard HNSW in FP32 precision is an architectural anti-pattern that squanders cloud capital. By understanding the microarchitectural mechanics of skip-list graph traversal versus product quantization codebooks, implementing single-stage ACORN filtering, and exploiting Matryoshka Representation Learning, systems architects can achieve sub-5ms search latencies and 98% recall while reducing infrastructure expenditure by more than 85%.