ANN indexes under the hood: HNSW, IVF, and when each wins

A startup deployed their semantic search index on a Tuesday and it worked beautifully in staging. Three weeks later, after their CMS sync had updated 2 million of the 8 million documents — every update a delete plus a reinsert — p95 search latency had climbed from 12 ms to 340 ms and relevance complaints were trickling in. No error. No alert. The HNSW index wasn't corrupted; it was full of tombstones. Deleted vectors aren't unwired from the graph — they're flagged and skipped at query time — so every search was still traversing millions of dead nodes and widening its beam to route around them. The fix was forcing a rebuild — four hours of degraded search over the weekend.

That story is specific, but the failure mode is universal: ANN indexes make a structural commitment at build time, and understanding what that commitment is tells you when the index is solid and when it's lying to you about recall.

What "approximate" means and why you want it

A nearest-neighbor search finds the exact K vectors closest to a query in some metric space. Brute-force does this in O(N × D) time — every vector, every dimension, every query. At 10 million 1536-dimensional vectors this is about 15B multiply-accumulate operations per query. Modern SIMD cores chew through those fast enough that the real bottleneck is memory bandwidth: streaming 61 GB of vectors from RAM at 100–200 GB/s puts a well-optimized multi-threaded scan at roughly 0.5–3 seconds per query. Useful for auditing; not useful for production.

Approximate nearest-neighbor search accepts that a few percent of the true nearest neighbors might be missed in exchange for queries that run in milliseconds. The tradeoff is formalized as recall@K: what fraction of the true top-K did the approximate search return? A production target of 95% recall@10 means that across your query distribution, the approximate index returns at least 9.5 of the true top 10, on average.

Two algorithm families dominate production: HNSW and IVF. They take fundamentally different approaches to the approximation, and those differences map directly to operational tradeoffs.

HNSW: the layered graph

Hierarchical Navigable Small-World (HNSW) was introduced by Malkov and Yashunin in 2016 and remains the default index in most vector databases (Qdrant, Weaviate, and Milvus all default to it; Pinecone runs a proprietary index and has argued publicly against pure in-memory HNSW at serverless scale). The core insight combines two older ideas: navigable small-world graphs (NSW) and skip-lists.

How insertion works

When a vector is inserted, HNSW assigns it a random maximum layer level drawn from an exponentially decaying distribution — most vectors land at layer 0 (the base), a smaller fraction reach layer 1, fewer still reach layer 2, and so on. This probabilistic assignment creates a hierarchy where upper layers are sparse and lower layers are dense.

At each layer, the new vector is wired to its M nearest neighbors among existing vectors at that layer. M is a build-time parameter (commonly 16–32). The algorithm for finding those neighbors is itself a greedy graph search on the current layer, starting from the entry point.

{ "type": "hnsw", "mode": "build", "title": "HNSW: building the layered graph" }

The result is a multi-layer structure where:

• Layer 2+: sparse long-range connections, fast coarse navigation
• Layer 1: intermediate density
• Layer 0: dense base layer, all vectors present, short-range edges

How search works

Query traversal starts at the entry point of the highest non-empty layer and greedily hops to the neighbor closest to the query. It descends to the next layer when no neighbor is closer than the current node. At layer 0 it performs a beam search with beam width ef — keeping the ef best candidates explored so far — and returns the top K from that candidate set.

sequenceDiagram
    participant Q as Query
    participant L2 as Layer 2 (sparse)
    participant L1 as Layer 1
    participant L0 as Layer 0 (dense)

    Q->>L2: enter at global entry point
    L2->>L2: greedy hop to nearest neighbor
    L2->>L1: descend when no closer neighbor
    L1->>L1: greedy hop (more nodes available)
    L1->>L0: descend
    L0->>L0: beam search (width = ef)
    L0-->>Q: top-K results

Query complexity is O(log N) in the number of hops across layers, with the constant factor controlled by ef. Setting ef = 10 is fast but low-recall; ef = 200 is slower but high-recall. The parameter can be tuned at query time without rebuilding the index, which makes HNSW convenient for recall-latency sweeps.

HNSW memory math

HNSW must keep the entire graph in RAM. Memory usage breaks down as:

• Raw vectors: N × D × sizeof(float32) = N × D × 4 bytes
• Graph edges: each node at layer 0 stores 2M edges (bidirectional), each edge is a 4-byte integer node ID. Upper layers store M edges.
• Rough total: (N × D × 4) + (N × 2M × 4) bytes for the base layer, plus overhead for upper layers.

With M=16, D=1536, N=10M:

vectors:    10M × 1536 × 4 ≈ 61 GB
base edges: 10M × 32 × 4   ≈ 1.3 GB
upper layers: only ~1/M ≈ 6% of nodes exist above layer 0,
              each storing M edges → ~50 MB
---
Index total: ~63 GB. Provision ~1.5× raw (≈90 GB) end-to-end:
the extra is the database around the index — storage engine,
WAL, query buffers, allocator overhead, headroom — not the graph.

Note the shape of that breakdown: at 1536 dims the graph edges are a rounding error (~2%) next to the vectors themselves. The oft-quoted "HNSW costs 2× raw" comes from low-dimensional benchmarks (128-dim SIFT, where 32 edge IDs rival the vector's own size) and from whole-service provisioning guidance — not from the graph. Your memory problem at high dimensions is the float32 vectors, which is exactly what quantization attacks.

This is why "just use HNSW" stops being free past about 50M vectors — at that point you're looking at 300+ GB of raw vectors alone before service overhead. Purpose-built vector databases like Qdrant and Milvus implement HNSW with memory-mapped files and compressed edge storage to push this boundary, but the vectors still have to live somewhere fast.

IVF: cluster first, search less

Inverted File (IVF) is conceptually simpler. At build time, run k-means over the corpus to produce nlist cluster centroids. Each vector is assigned to its nearest centroid. At query time, find the nprobe nearest centroids to the query and do exhaustive search only within those clusters.

flowchart LR
    subgraph Build
        V["All vectors"] --> KM["k-means training\n(nlist = 4096 centroids)"]
        KM --> C1["Cluster 1\n~2.4K vectors"]
        KM --> C2["Cluster 2\n~2.4K vectors"]
        KM --> CN["...Cluster 4096"]
    end
    subgraph Query
        Q["Query vector"] --> NC["Find nearest\nnprobe centroids"]
        NC --> SCAN["Exhaustive scan\nnprobe × cluster_size vectors"]
        SCAN --> R["Top-K results"]
    end

If nlist = 4096 and nprobe = 64, each query scans 64/4096 = 1.6% of the corpus. That's O(N × nprobe/nlist) — a fixed fraction of the dataset, not O(log N). At large N, IVF latency is slower per query than HNSW (for the same recall tier), but the memory footprint is dramatically smaller because IVF does not store a graph — just the vectors and the centroid table.

Choosing nlist and nprobe

A common heuristic: nlist ≈ sqrt(N) for N up to a few million, then tune up from there. For 10M vectors, sqrt(10M) ≈ 3162, so nlist = 4096 is a reasonable start. The training corpus for k-means needs to be representative — Faiss recommends at least 39 × nlist training vectors.

nprobe is the recall-latency knob:

nprobe (% of nlist)	Typical recall	Relative query time
1%	70–80%	1×
5%	88–93%	~5×
10%	92–96%	~10×
25%	96–98%	~25×
100%	~99%	~100× (approaches flat)

The relationship is roughly linear: doubling nprobe roughly doubles query time. If you need 97%+ recall with fast queries, IVF is fighting against itself; HNSW handles that operating point better.

Quantization: the orthogonal compression layer

Both HNSW and IVF store vectors in whatever precision you specify. Quantization compresses those vectors independently of the index structure.

INT8 scalar quantization

Each float32 dimension (4 bytes) is linearly mapped to an int8 (1 byte): 4× compression. The quantization range is calibrated from the training set distribution. Recall degradation is typically 0.5–2% on standard benchmarks. This is the first move when HNSW memory overhead is painful.

For the 10M × 1536 corpus above: full float32 HNSW is a ~63 GB index on a ~90 GB machine. HNSW with INT8 vectors takes the raw vector component down to ~15 GB; with graph edges the index drops to roughly 17 GB, comfortably provisioned on a 32 GB instance. That's the difference between a 128 GB machine and one a quarter the size.

Binary quantization

Each float32 dimension is quantized to 1 bit (positive vs negative): 32× compression. Binary quantization alone is too lossy for most applications, but the standard pattern is binary quantization + float32 re-ranking: retrieve 10× the final K using the binary index (extremely fast — comparisons collapse to XOR + popcount), then re-rank the candidates against the original float32 vectors. This recovers most of the lost recall and can achieve final recall within 2–5% of the unquantized baseline.

Binary quantization cost example:
  10M × 1536 float32 ≈ 61 GB
  10M × 1536 bit     = 10M × 192 bytes ≈ 1.9 GB binary index
  + 61 GB original vectors for re-ranking step
  Net: serve queries from 1.9 GB, re-rank from RAM or SSD

Weaviate, Qdrant, and Milvus all ship binary quantization with re-ranking as a first-class feature as of 2025–2026. Metadata Filtering, Scaling, and Production Cost Control covers the cost math in more depth.

Product Quantization (PQ)

PQ splits each high-dimensional vector into m equal-length sub-vectors, quantizes each sub-vector independently to one of 256 codewords, and stores only the codeword indices. A 1536-dim vector split into 96 subspaces of 16 dims each, with 8-bit codewords, occupies 96 bytes instead of 6144 bytes — 64× compression.

The cost: distance approximation quality degrades noticeably, and PQ typically requires a re-ranking step to achieve acceptable final recall. PQ is the right choice when memory is the hard constraint (billion-scale, 1–2 GB RAM budget), not when you want both compression and high recall out of the box.

The metadata filter footgun

This is the production failure mode that isn't in the algorithm papers.

HNSW's graph is built on the global data distribution. When you apply a metadata filter (e.g., status = 'published' AND tenant_id = 42), you're asking the index to find nearest neighbors within a subset of the graph. If that subset is sparse — say, 5% of nodes match the filter — then HNSW's greedy traversal will frequently encounter graph paths through nodes that don't match, effectively dead-ending before reaching the true nearest matching vectors.

At high filter selectivity (>90% of vectors excluded), HNSW recall can drop below 50% without raising an error. The query returns K results; you have no way to know they aren't the actual nearest neighbors unless you validate externally.

flowchart TD
    Q["Query + filter: tenant=42"] --> HNSW["HNSW graph traversal"]
    HNSW --> N1["Node 1 ✓ tenant=42"]
    HNSW --> N2["Node 2 ✗ tenant=99\n(dead-end for this filter)"]
    HNSW --> N3["Node 3 ✗ tenant=7\n(dead-end)"]
    N2 -->|"graph edge leads here\nbut filter excludes"| MISS["True nearest neighbor\nnever reached"]
    style MISS fill:#ff2e88,color:#111
    style N2 fill:#ffaa00,color:#111
    style N3 fill:#ffaa00,color:#111

IVF handles this somewhat better: if the filtered vectors happen to cluster together (which is likely for tenant-based partitioning), probing the right clusters still finds them. But IVF with high-selectivity filters on non-clustered predicates (e.g., created_at > now() - 7 days) has the same problem.

The practical mitigations:

• Namespace per tenant: many vector databases let you create separate collections or namespaces per tenant, each with its own index. Filters within a namespace hit 100% of that namespace's graph nodes. This is the cleanest solution for multi-tenant systems with O(100–10K) tenants.
• Pre-filter with a separate inverted index: some databases (Weaviate, Qdrant 1.9+) build a separate inverted index for filterable attributes and use it to restrict the search space before ANN traversal — effectively filtering to a sub-corpus first, then doing ANN on the survivors.
• Qdrant's learning-based query planner: as of 2025, Qdrant dynamically selects between pre-filter, post-filter, and a payload-aware traversal strategy per query based on estimated selectivity. This is the kind of thing that needs to be supported at the vector database level, not something you can implement yourself in application code.

For more on how filtering interacts with ANN at scale, including the ACORN algorithm, see Metadata Filtering, Scaling, and Production Cost Control.

What breaks

HNSW on large corpora without memory budgeting

Engineers pick HNSW because it's the default, provision a machine that exactly fits the raw vectors, and discover under load that the process OOMs — not because of graph edges (a few percent at high dimensions) but because the database around the index needs real memory too: storage engine, WAL, query buffers, allocator fragmentation, and the traffic spike you didn't load-test. The fix (resizing the instance or enabling disk-backed HNSW) requires index downtime. Provision ~1.5× raw vector RAM from the start and treat anything tighter as a deliberate bet.

HNSW under deletes and updates

HNSW handles inserts gracefully; deletes are its weak spot, and nobody's marketing page mentions it. Removing a node from the graph properly would mean re-wiring every neighbor that pointed at it, so no production engine does that. Instead, deletes are tombstoned: the vector is flagged as dead, excluded from results, but its node stays in the graph and traversal still walks through it. An update is a delete plus a reinsert, so a corpus where documents change constantly accumulates tombstones even if its total size never grows. The consequences compound: queries pay traversal cost for nodes that can never be returned, the beam has to widen to find enough live candidates (latency climbs), and live regions of the graph slowly lose the shortcut edges that used to run through now-dead nodes (recall sags). This is exactly the failure in the opening anecdote — 25% of the graph dead after a churn-heavy month, p95 up 28×.

Engines compensate with periodic cleanup: Qdrant runs a vacuum that rebuilds affected segments once tombstones cross a threshold (configurable, ~20% by default), and Lucene-based systems (Elasticsearch, OpenSearch) fold dead vectors out during segment merges. The operational takeaway: if your workload is update-heavy, HNSW is still usually the right index — but treat "tombstone ratio" as a first-class metric, know your engine's vacuum/merge trigger, and schedule rebuilds before the graph decays instead of after the pager tells you.

IVF with stale cluster assignments

IVF's k-means centroids are fixed at build time. Insert a million vectors and they go into their assigned clusters, but those assignments were computed on the original distribution. After substantial inserts, cluster sizes become uneven, frequently queried clusters get overcrowded, and recall drops for queries that would have been handled by the new vector distribution. Remediation is a full retrain of the k-means centroids, which for 100M vectors can take hours. For workloads with continuous high-velocity inserts, HNSW is the better architecture; IVF works well for batch-loaded, mostly-static corpora.

Quantization precision loss compounding with borderline queries

INT8 quantization causes 0.5–2% aggregate recall loss on benchmark datasets. The problem is that benchmarks measure average recall across a diverse query distribution. For your actual queries — especially if they're domain-specific or borderline (the true nearest neighbor is only marginally closer than the 11th result) — the loss can be 5–10%. Before deploying a quantized index in production, measure recall on your actual query distribution and actual corpus, not on ANN benchmarks. What Are Embeddings? covers why embedding geometry varies by domain and why standard benchmarks can mislead.

Trusting recall numbers from vendor benchmarks

Pinecone's p99 latency is measured under single-tenant synthetic workloads. Qdrant's recall benchmarks use standardized datasets that may not match your vector distribution. ANN-benchmarks.com is the cleanest third-party comparison, but even those are point-in-time measurements on specific hardware. Validate on your data, with your query patterns, at your target concurrency.

Build time surprises

HNSW build time is O(N × M × log N). For 10M vectors with M=16 on a 32-core machine, expect 1–3 hours. For 100M vectors, expect a full day or more. This matters when you need to re-index after an embedding model version change — which forces a complete rebuild because the vector space is different. See Choosing an Embedding Model in 2026 for why model versioning is a bigger operational concern than most engineers plan for.

The decision in practice

Pick your index based on the intersection of four variables: corpus size, insert velocity, RAM budget, and required recall.

flowchart TD
    A{{"N < 100K?"}} -->|Yes| FLAT["Flat/brute-force\nSimplest, 100% recall"]
    A -->|No| B{{"RAM ≥ 1.5× raw vectors?"}}
    B -->|Yes| C{{"High insert velocity\n(>10K/day)?"}}
    B -->|No| D["IVF + INT8\n~4× compression\n90–95% recall"]
    C -->|Yes| HNSW["HNSW\nO(log N), handles inserts"]
    C -->|No| E{{"Need >95% recall?"}}
    E -->|Yes| HNSW
    E -->|No| IVF["IVF Flat\nSlightly lower recall\nbetter RAM efficiency"]
    D --> BSCALE{{"N > 500M?"}}
    BSCALE -->|Yes| PQ["IVF + PQ\nor DiskANN-style\nextreme compression"]
    BSCALE -->|No| D

A few sharper rules of thumb:

Use HNSW when your dataset is under 50M vectors, insert rate is meaningful (documents change, new content arrives daily), and you have the RAM to cover the graph overhead. HNSW's query latency at 95% recall is typically 2–5× faster than IVF at equivalent recall because it avoids scanning entire clusters.

Use IVF when your corpus is large (50M+) and mostly static, you need predictable memory footprint, or you're stacking quantization aggressively. IVF + INT8 at 100M vectors of 1536 dims fits in roughly 160 GB and achieves 90–93% recall; that's often the right engineering trade-off against float32 HNSW at ~630 GB of index (more once the service around it is provisioned).

Use IVF + PQ when memory is the hard constraint and you can tolerate a re-ranking step. Billion-scale deployments at companies like Meta use FAISS IVF + PQ precisely because the alternatives don't fit in any realistic memory budget. Accept the recall degradation, re-rank with a smaller float32 candidate set, and measure end-to-end recall including the re-ranking step.

Mix in quantization opportunistically. INT8 is almost always worth it on HNSW — the recall loss is small and the memory savings let you fit a larger index on the same hardware. Binary quantization with re-ranking is worth exploring when INT8 still leaves you over budget.

The Vector Database Landscape 2026 article covers how specific databases expose these knobs — Qdrant's HNSW configuration, Milvus's IVF variants, and pgvector's choice of index type — with the concrete operational differences that affect which database you'd select for a given scale point. And if you're building the retrieval layer for a RAG pipeline, Hybrid Search: Fusing Dense Vectors and Sparse BM25 Correctly covers how these ANN indexes combine with sparse keyword indexes, because pure ANN search will fail on queries containing rare proper nouns or product codes regardless of how well you've tuned ef or nprobe.

The index choice is durable — you're usually stuck with it until you can afford a re-index. Get the memory math right before you provision.