HNSW vs DiskANN vs IVF-PQ: Vector Index Internals, Quantization and Recall Trade-offs

Most teams pick a vector index by copying the default from whichever database they installed first, and it works until the corpus grows tenfold. Then the memory bill triples, recall quietly drops on filtered queries, or a nightly rebuild stops fitting in its window. The choice between graph indexes and compression-first indexes is not cosmetic, because each family bends a different resource: RAM, SSD reads, build time, or recall.

This guide compares HNSW vs DiskANN and the older workhorse IVF-PQ at the level where decisions actually get made: what each structure stores, what a single query touches, and what the memory arithmetic looks like at 100 million 1024-dimension vectors. It leans on primary sources (the HNSW, DiskANN, FreshDiskANN, and RaBitQ papers, plus pgvector, Qdrant, Milvus, and FAISS documentation) and marks every number that is illustrative rather than measured. You will leave with a mental model of each index, a runnable sketch, and a decision matrix.

What this covers: the approximate nearest neighbor problem, HNSW internals and parameters, Vamana and DiskANN on SSD, IVF with product quantization, scalar, binary and RaBitQ quantization, memory math, filtered search, updates and deletes, and how to choose.

Context and Background

Exact nearest neighbor search in high dimensions has no known sublinear method that beats a scan in the worst case, a limitation often called the curse of dimensionality. A brute-force scan over 100 million float32 vectors of 1024 dimensions reads roughly 410 GB per query, which is why every production system uses approximate nearest neighbor (ANN) search: give up a small, measurable fraction of recall in exchange for orders of magnitude less work. Recall here means the share of the true top-k neighbors that the index returns, usually written recall@k.

Three families dominate. Graph indexes link each vector to a handful of near neighbors and answer queries by walking the graph; HNSW (Malkov and Yashunin, first posted to arXiv in 2016) is the canonical example. Partition-plus-compression indexes cluster the space into cells and store compressed codes inside each cell; that is IVF with product quantization, from the FAISS lineage and the 2011 product quantization paper by Jégou, Douze and Schmid. Disk-resident graphs, led by DiskANN (Subramanya et al., NeurIPS 2019), keep a compressed copy in RAM and the full-precision graph on SSD.

The engines map onto these families as follows, according to their documentation. pgvector ships HNSW and IVFFlat indexes inside PostgreSQL. Qdrant uses HNSW and layers scalar, binary and product quantization on top. Milvus documents IVF_PQ, HNSW with SQ, PQ and PRQ variants, SCANN, and a separate DISKANN index. FAISS exposes essentially all of the primitives (flat, IVF, PQ, HNSW, RaBitQ) behind index factory strings. Microsoft maintains the DiskANN library, which its README now describes as a Rust workspace, with the earlier C++ code archived on a separate branch.

If you are still deciding between a Postgres extension and a purpose-built engine, start with our comparison of pgvector versus a dedicated vector database; this article goes one level lower and explains the index structures those products wrap. A useful framing to carry through: the index decides the shape of your cost curve, while the engine decides how much operational work it takes to ride that curve.

The three numbers that matter

Every ANN decision reduces to three coupled quantities. Recall@k is the quality you deliver. Latency (usually p95 or p99) and throughput are what you pay in CPU and I/O per query. Memory and build time are what you pay in infrastructure. Tuning any parameter moves a point along a Pareto frontier among them. The honest way to compare indexes is therefore at a fixed recall target, such as 0.95 recall@10, and then to ask what each costs. Benchmark tables that quote speed without a recall level are not comparable, and I will avoid quoting any such figure.

HNSW: Layered Small-World Graphs

HNSW (Hierarchical Navigable Small World) stores every vector once in a multi-layer proximity graph. The bottom layer contains all points; each higher layer contains an exponentially smaller random subset. A query enters at the top, greedily walks toward the query on sparse layers to get close quickly, then runs a wider beam search on the bottom layer. The paper reports roughly logarithmic scaling of search cost with dataset size.

Figure 1: HNSW query descent through sparse upper layers to a beam search on layer 0, and the four insertion steps that build the graph.

Figure 1 shows the two paths. At query time the algorithm keeps a candidate list of size efSearch on layer 0 and returns the best k found. At insert time each new point draws a maximum layer, searches down from the top to find candidates, picks neighbors with a diversity heuristic, and adds bidirectional links that are pruned to a cap.

Layer assignment, M, and the neighbor heuristic

Each new element gets a top layer l = floor(-ln(u) * mL), where u is uniform in (0,1) and the paper’s recommended normalization is mL = 1/ln(M). That makes the expected number of layers grow with the logarithm of the data size, and the share of points present at layer 1 equal to roughly 1/M. In practice, with M = 16, about one point in sixteen reaches layer 1 and one in 256 reaches layer 2. The upper layers are cheap: they hold a small fraction of the points and each hop at those layers jumps a long distance.

The parameter M is the number of links created per new element on layers above zero. Layer 0 allows up to 2M links per node, a cap written Mmax0 in the paper. That detail drives the memory formula: FAISS documents HNSW memory as (d * 4 + M * 2 * 4) bytes per vector, which is the float32 vector plus 2M four-byte neighbor ids, ignoring the upper layers and allocator overhead. Defaults you will meet in the wild: pgvector uses m = 16 and ef_construction = 64, and Qdrant uses m = 16 and ef_construct = 100. FAISS allows 4 to 64 for M, and Milvus documents a much wider accepted range for M of 2 to 2048.

The neighbor selection heuristic is the quiet reason HNSW works on clustered data. Instead of linking a new node to its M closest candidates, which in a tight cluster would all be redundant, the heuristic accepts a candidate only if it is closer to the new node than to any neighbor already chosen. The result is a graph with some longer edges that bridge clusters. The paper credits this heuristic for much of the improvement at high recall and on highly clustered data.

efConstruction and efSearch

efConstruction is the candidate-list size used while inserting. Larger values find better neighbors, which improves graph quality and final recall, at the cost of slower builds. It is paid once per insert and cannot be changed after the fact without rebuilding. efSearch (pgvector calls it hnsw.ef_search, default 40) is the candidate-list size at query time on layer 0, and it is the knob you turn per query to trade latency for recall. It must be at least k, and in pgvector a query asking for LIMIT 100 with ef_search at 40 cannot return 100 results from the index.

A practical rule: raise efConstruction until recall at a fixed efSearch stops improving, then treat efSearch as the runtime dial. Doubling efSearch roughly doubles the number of distance computations on layer 0, so latency grows close to linearly in it while recall saturates.

Why HNSW is the default and where it hurts

HNSW wins on query latency at high recall when everything fits in RAM. It needs no training step, accepts incremental inserts, and has well-tested implementations. Its costs are structural. The graph plus the raw vectors must be memory-resident for good performance, because every hop is a random access; paging that to disk turns each hop into an I/O. Build is expensive, since every insert is itself a search. And deletion is awkward: removing a node leaves in-edges pointing at it, so implementations either mark entries as deleted and skip them (hnswlib offers mark_deleted for this) or repair neighborhoods during maintenance. FAISS’s guideline page states plainly that its HNSW index does not support removing vectors.

DiskANN and Vamana: Graphs Designed for SSD

DiskANN is a system, and Vamana is the graph inside it. The NeurIPS 2019 paper claims that a single workstation with 64 GB of RAM and an inexpensive SSD can index, store and search a billion-point dataset, and reports over 5,000 queries per second with mean latency under 3 ms and 95%+ 1-recall@1 on SIFT1B using a 16-core machine. It also reports that FAISS and IVFOADC+G+P, at similar memory, plateau around 50% 1-recall@1, and claims 5 to 10 times more points per node than HNSW or NSG at high recall. These are the authors’ own results on one benchmark; treat them as evidence of the design point, not a forecast for your data.

Figure 2: DiskANN query flow. PQ codes in RAM rank candidates cheaply, while each hop reads whole sectors from SSD that hold both the full vector and its neighbor list.

The Vamana graph

Where HNSW builds layers, Vamana builds one flat graph with a bounded out-degree R. Construction starts from a random R-regular graph, picks a medoid as the single entry point, and then makes two passes over the data. For each point it runs a greedy search from the medoid, collects the visited nodes, and applies a pruning rule called RobustPrune, then adds reverse edges and prunes again where needed. RobustPrune takes a distance-relaxation parameter alpha, which is the notable design choice: with alpha greater than 1, an edge is kept unless another chosen neighbor is substantially closer to the candidate, which preserves some long-range edges and shortens the number of hops a search needs. That matters on SSD, where hops cost I/O rather than nanoseconds. (The description of RobustPrune and alpha follows the published algorithm as I recall it; I did not re-fetch the full paper this run, so verify details against the source before implementing.)

A single entry point and no hierarchy is possible because the long edges do the job that HNSW’s upper layers do. The trade-off is that the search path from the medoid can be longer than a layered descent, which is acceptable when the first several hops are served from cache.

The SSD layout and the compressed copy

DiskANN keeps two representations. In RAM sits a product-quantized copy of every vector, typically tens of bytes each. On SSD sits the graph, where each node record packs the full-precision vector together with its neighbor list so one aligned read returns everything needed to expand that node. A query runs beam search with beam width W: it ranks frontier nodes using PQ distances from RAM, issues W reads in parallel, and on arrival computes exact distances to the full vectors in the fetched sectors. Those exact distances are retained for a final rerank, which repairs the error introduced by compression during navigation.

Two consequences follow. Latency is dominated by the number of sequential hop rounds times SSD read latency, so NVMe quality matters more than CPU. And memory scales with compressed size per vector, not raw size, which is the whole point: the RAM requirement for the 100M-vector example later in this article drops from hundreds of gigabytes to single digits.

Streaming updates and filters

Plain Vamana is static, like most graph indexes. FreshDiskANN (Singh et al., arXiv 2105.09613, 2021) addresses that. Its abstract says it supports thousands of concurrent inserts, deletes and searches per second each, maintains over 95% 5-recall@5 under the update load, can index over a billion points on one workstation with SSD, and cuts the cost of keeping an index fresh by 5 to 10 times versus rebuilding approaches. The mechanism, as I understand it from the paper but did not re-verify in this run, is a small in-memory graph that absorbs new points, a lazily applied delete list, and periodic merges into the on-disk graph. The current Microsoft repository states that it supports stable recall under long update streams and offers hooks for attribute filters. The repository also links the Filtered-DiskANN paper, which I summarize in the filtered-search section below.

IVF-PQ: Partition, Then Compress

IVF-PQ is the oldest and most memory-frugal of the three, and the one whose behavior is easiest to reason about because it is a sequence of two simple ideas.

Figure 3: IVF-PQ pipeline. Offline, k-means creates coarse cells and product quantizers encode residuals; online, a query probes a few cells and sums table lookups per code.

Inverted file: coarse partitioning

The inverted file (IVF) step runs k-means on a training sample to produce nlist centroids and assigns each vector to its nearest centroid, storing vector ids in a list per centroid. A query finds the nprobe nearest centroids and scans only those lists. Scanning cost scales with nprobe divided by nlist, so with nlist = 4,096 and nprobe = 16 the scan touches roughly 0.4% of the data, assuming balanced lists. Recall rises with nprobe because the true neighbor often sits in an adjacent cell; this is the IVF equivalent of efSearch.

Sizing guidance is documented. The FAISS wiki says K should be 4sqrt(N) to 16sqrt(N) for datasets under 1M vectors and that you need between 30K and 256K training vectors. For 1M to 10M it suggests IVF65536_HNSW32, for 10M to 100M IVF262144_HNSW32, and for 100M to 1B IVF1048576_HNSW32, where an HNSW graph over the centroids replaces the brute-force centroid scan, and notes training gets slower at each step. pgvector’s IVFFlat guidance is lists = rows/1000 up to 1M rows and sqrt(rows) beyond, with probes starting near sqrt(lists); its default probes value is 1.

Product quantization

Product quantization (PQ) splits each D-dimensional vector into m subvectors of D/m dimensions and runs k-means on each subspace to learn a codebook, typically 256 centroids so one subvector costs one byte. A vector becomes m bytes. The compression ratio is exact arithmetic: a 1024-dimension float32 vector occupies 4,096 bytes, and with m = 64 its code is 64 bytes, a 64x reduction; with m = 128 it is 32x. Milvus exposes the same knobs as m and nbits (default 8, range 1 to 24), and requires that dim be divisible by m.

Distance computation uses asymmetric distance computation (ADC). The query stays in full precision; for each of the m subspaces the engine precomputes a table of distances from the query subvector to all 256 centroids. The estimated distance to any stored code is then the sum of m table lookups, with no multiplications over D dimensions. FAISS also supports 4-bit codes with SIMD “fast scan” layouts, at M/2 bytes per vector according to its wiki.

In IVF-PQ it is common to encode the residual (vector minus its coarse centroid), because residuals have smaller variance and quantize with less error. The scan is cheap and cache-friendly, which is why IVF-PQ does well on throughput and on GPUs. The error floor is the weakness. PQ is lossy, so recall saturates below 1.0 no matter how large nprobe grows, and the usual remedy is to rerank a shortlist (say the top 100 to 1,000 candidates) using full-precision vectors fetched from slower storage. The FAISS wiki also notes that for larger code sizes, scalar quantization is usually as accurate and faster than PQ with M above 64.

Scalar, Binary and RaBitQ Quantization

PQ is not the only way to shrink vectors, and for modern embedding models simpler schemes are often competitive. These compose with any of the three index families.

Scalar quantization (SQ) maps each float32 component to an 8-bit integer using a per-dimension or global range. Qdrant’s documentation says this gives 4x compression, enables SIMD-friendly comparisons, and typically introduces less than 1% error in its experiments, with the caveat that this depends on data and that a quantile parameter can be tuned. Milvus offers IVF_SQ8 and HNSW_SQ for the same purpose. pgvector offers halfvec (float16): storage is 2 bytes per dimension plus 8, indexable up to 4,000 dimensions versus 2,000 for the full vector type.

Binary quantization (BQ) keeps one bit per component, the sign. That is 32x compression and the distance becomes a Hamming distance computed with popcount instructions. Qdrant claims up to 32x compression and up to 40x speedup, and states results such as 0.98 recall@100 with 4x oversampling for 1536-dimension OpenAI ada-002 embeddings and 0.98 recall@50 with 2x oversampling for 4096-dimension Cohere embeddings. Its guidance is blunt: use BQ only with rescoring, only for high-dimensional vectors, and expect trouble below roughly a thousand dimensions or where components are not centered. pgvector supports it through binary_quantize with bit_hamming_ops via expression indexes and recommends re-ranking with the original vectors.

RaBitQ (Gao and Long, SIGMOD 2024, arXiv 2405.12497) is also one bit per dimension, but it is a randomized scheme with a theoretical error bound. The abstract states that PQ and its variants lack such a bound and can fail badly on some real-world datasets, that RaBitQ estimates distances using bitwise or SIMD operations, and that experiments show it beating PQ and variants on the accuracy-efficiency trade-off “by a clear margin.” FAISS now lists RaBitQ factory strings including IVFK,RaBitQN and a FastScan variant, with memory documented as (d/8 + 8) bytes per vector and a random rotation as preprocessing. I have not verified independent benchmark numbers for RaBitQ in this run, so no performance figures are quoted here. The practical takeaway is that 1-bit codes with a principled estimator plus rescoring have become a credible alternative to PQ for high-dimensional embeddings.

The rescoring pattern

Every lossy scheme above shares one escape hatch: oversample, then rescore. Retrieve k times an oversampling factor of candidates using compressed distances, fetch their full-precision vectors, compute exact distances and keep the best k. Qdrant defines oversampling concretely (an oversampling of 2.4 with limit 100 pre-selects 240 candidates) and warns that rescoring can hurt speed when originals live on disk. The cost model is simple: the extra random reads equal the oversampling factor times k, so a 4x oversampling at k = 10 is 40 random fetches per query. That is trivial from RAM and meaningful from network storage, which is why DiskANN designs the rerank into the sector read itself.

Memory Arithmetic for 100 Million 1024-Dimension Vectors

Numbers beat adjectives, so here is the footprint of a hypothetical corpus: N = 100,000,000 vectors, d = 1024. All figures below are my own arithmetic from the formulas cited earlier, rounded, using decimal gigabytes. They are illustrative sizing estimates, not benchmark results, and they ignore allocator overhead, replication, and the payload (metadata) you store next to each vector.

Representation	Bytes per vector	Total for 100M	Notes
Raw float32	4,096	about 410 GB	Brute-force scan reads this per query
HNSW, M = 16, float32	4,096 + 128 = 4,224	about 422 GB	FAISS formula d4 + M2*4; upper layers add a little more
HNSW over float16	2,048 + 128	about 218 GB	Halves vectors, links unchanged
HNSW over int8 SQ	1,024 + 128	about 115 GB	Plus raw vectors if you rescore from disk
Binary, 1 bit per dimension	128	about 12.8 GB	32x; needs rescoring against originals
PQ, m = 64, 8-bit	64	about 6.4 GB	64x; add roughly 0.8 GB for 8-byte ids
PQ, m = 128, 8-bit	128	about 12.8 GB	32x; better recall ceiling
DiskANN style, RAM tier	64 (PQ code)	about 6.4 GB	Navigation copy only
DiskANN style, SSD tier (R = 64)	about 4,356 unpadded	about 436 GB	Vector + 64 neighbor ids of 4 bytes + count; sector padding can raise it

Read the table as a set of regimes. Plain HNSW at this scale wants roughly half a terabyte of RAM per replica before you add sharding, which is why hosted systems split it across many nodes. Quantizing the in-memory copy to int8 or 1-bit changes the picture to a one- or two-node deployment, provided you store originals on cheaper storage for rescoring. The DiskANN-style layout moves almost all bytes to SSD and leaves single-digit gigabytes in RAM, which is the same trick the paper used to put a billion points on a 64 GB machine.

Two cautions. First, a smaller code lowers your recall ceiling, so a 64-byte PQ code over a 1024-dimension embedding may need heavy reranking to reach 0.95 recall; choose m by measuring on your embeddings, not by the table. Second, the graph in HNSW is not free: at M = 16 it is only about 3% of the footprint with float32, but next to a 1-bit vector it is as large as the code itself, because 128 bytes of links match a 128-byte code. Once you quantize aggressively, the links dominate, which is the reason quantized HNSW configurations often lower M.

Build time and training cost

Memory is half the bill. HNSW build cost scales with N times the cost of one search at efConstruction, and it parallelizes across threads but with locking on neighbor lists. IVF-PQ needs k-means training on a sample of at least 30 * nlist vectors per the FAISS guidance, then one cheap assignment-and-encode pass; it builds fastest and is simple to shard. Vamana builds take two passes of greedy searches plus pruning and are usually the slowest of the three per vector at the same quality. FAISS flags that clustering with a million or more centroids gets slow enough that GPU-only training or two-level clustering is suggested. Plan the rebuild cadence before choosing: an index you can only rebuild weekly implies a delta structure for fresh data.

A Runnable Sketch with hnswlib and FAISS

The code below builds the same random dataset under HNSW and under IVF-PQ and measures recall against an exact search, so you can see the knobs move. It uses synthetic Gaussian data, which has no cluster structure and is harder for IVF than real embeddings; use it to learn the API and the shape of the trade-off, then rerun on your own vectors. Install with pip install hnswlib faiss-cpu numpy.

import time
import numpy as np
import faiss
import hnswlib

rng = np.random.default_rng(0)
N, D, NQ, K = 200_000, 128, 1_000, 10
xb = rng.standard_normal((N, D)).astype("float32")
xq = rng.standard_normal((NQ, D)).astype("float32")

# Ground truth with exact search
flat = faiss.IndexFlatL2(D)
flat.add(xb)
_, gt = flat.search(xq, K)

def recall(ids):
    hits = sum(len(set(a) & set(b)) for a, b in zip(ids, gt))
    return hits / (NQ * K)

# 1) HNSW via hnswlib: M and ef_construction fixed at build time
hn = hnswlib.Index(space="l2", dim=D)
hn.init_index(max_elements=N, M=16, ef_construction=200)
t = time.time(); hn.add_items(xb); print("hnsw build s", round(time.time() - t, 1))
for ef in (16, 32, 64, 128, 256):
    hn.set_ef(ef)                       # the runtime recall dial
    t = time.time(); ids, _ = hn.knn_query(xq, k=K)
    print("hnsw ef", ef, "recall", round(recall(ids), 3),
          "ms/query", round((time.time() - t) / NQ * 1000, 3))

# 2) IVF-PQ via FAISS: nlist cells, m subquantizers of 8 bits each
nlist, m = 1024, 16                     # D must be divisible by m
quant = faiss.IndexFlatL2(D)
ivfpq = faiss.IndexIVFPQ(quant, D, nlist, m, 8)
ivfpq.train(xb[:100_000])               # at least 30 * nlist training vectors
ivfpq.add(xb)
print("code bytes per vector", m)       # 16 bytes vs 512 raw
for nprobe in (1, 4, 16, 64):
    ivfpq.nprobe = nprobe
    t = time.time(); _, ids = ivfpq.search(xq, K)
    print("ivfpq nprobe", nprobe, "recall", round(recall(ids), 3),
          "ms/query", round((time.time() - t) / NQ * 1000, 3))

# 3) Rescoring: oversample with PQ, then rerank exactly with raw vectors
ivfpq.nprobe = 16
_, cand = ivfpq.search(xq, K * 10)
out = np.empty((NQ, K), dtype="int64")
for i in range(NQ):
    c = cand[i][cand[i] >= 0]
    d = ((xb[c] - xq[i]) ** 2).sum(1)
    out[i] = c[np.argsort(d)[:K]]
print("ivfpq + rescore recall", round(recall(out), 3))

Expect the pattern rather than specific numbers, which depend on your hardware and are therefore not quoted here: recall rises and latency grows as ef or nprobe increase; the PQ-only recall plateaus below the HNSW curve; and the rescoring step lifts the plateau toward the exact ceiling at the cost of N-independent extra work. For DiskANN, the maintained Microsoft repository is the place to start, and a Rust toolchain is required for the current code; the earlier C++ implementation lives on its cpp_main branch and is described as no longer actively maintained.

Filtered Search: Where Recall Quietly Breaks

Real queries almost never ask for pure similarity. They ask for the nearest documents for this tenant, in this date range, with this status. Filtering interacts with every index above, and it is where most production recall regressions begin.

Post-filtering and the shrinking result set

The simplest strategy runs the ANN search and then discards rows that fail the predicate. pgvector’s README is explicit that filtering is applied after the index is scanned. With HNSW and the default hnsw.ef_search of 40, a filter that matches 10% of rows leaves about 4 matches on average out of 40 candidates, which means a LIMIT 10 query returns fewer rows than requested. Recall against the filtered ground truth collapses even though the index is working as designed.

pgvector’s mitigations are worth knowing as a pattern. Since 0.8.0 it offers iterative index scans (hnsw.iterative_scan in strict_order or relaxed_order modes) that keep scanning until enough rows pass the filter, bounded by hnsw.max_scan_tuples, which defaults to 20,000. Relaxed order trades slightly out-of-order results for better recall. It also recommends partial indexes when there are few distinct filter values and partitioning when there are many, and notes that exact scans work well when the predicate is highly selective.

Pre-filtering and graph disconnection

The opposite strategy applies the predicate during the graph walk, only following or returning nodes that match. When the filter keeps most points this is fine. When it keeps a small, scattered subset, the allowed nodes no longer form a connected subgraph, so the walk gets stuck far from the best matches and recall falls. Qdrant describes its answer: the planner estimates filter cardinality from payload indexes, uses plain HNSW when the filter is weak, switches to the payload index with full rescoring when the filter is strict, and, for the awkward middle, extends the HNSW graph with additional edges built per indexed payload value. Its docs say those extra edges are per payload index, not for every combination, so combined strict filters can still disconnect the graph. They also say to create payload indexes right after creating the collection, and that adding one after ingestion requires an index rebuild.

The research counterpart for DiskANN is Filtered-DiskANN, linked from the Microsoft repository. As I recall the paper (not re-verified in this run), it builds graphs that connect nodes sharing label values so that a filtered walk stays connected, with variants such as stitching per-label subgraphs together. Treat that description as unverified and read the paper before relying on it. For IVF-based indexes the common implementation is to scan the probed lists and test the predicate per candidate, which is robust but spends scan work on rows that fail.

Figure 4: A decision path for choosing between graph, quantized-graph, DiskANN-style and IVF-PQ indexes based on RAM fit, filter heaviness and latency budget.

Figure 4 compresses the whole article into one path, and the section on recommendations below turns it into a checklist.

Updates, Deletes and Index Freshness

Vectors change. Documents get edited, records are deleted for compliance, embedding models are upgraded. How an index handles that determines whether you operate it or babysit it.

HNSW supports incremental insert natively. Deletes are the soft spot: the graph relies on in-edges to reach each node, so removing one can strand neighbors or degrade connectivity. Implementations commonly tombstone entries and skip them during search; hnswlib exposes mark_deleted for this. Tombstones accumulate, wasting memory and lengthening searches, until a vacuum, repair or rebuild. In Postgres, pgvector’s HNSW participates in normal MVCC and VACUUM, which is convenient but means the deletion and repair cost is paid through vacuum activity. FAISS’s own HNSW class documents that it supports sequential adds only and does not support removing vectors.

IVF-PQ handles inserts well because assignment is just nearest-centroid plus an encode, and deletes are list removals. The hidden risk is drift: centroids and codebooks were trained on yesterday’s distribution. If new data differs (a new embedding model, a new tenant with different content), recall degrades silently until you retrain. Monitoring recall on a held-out probe set is the safeguard.

DiskANN in its original form is static, and FreshDiskANN exists precisely because rebuilding a billion-point graph is expensive. The paper’s claim is real-time inserts and deletes with recall above 95% for 5-recall@5 while supporting thousands of operations per second, and the current repository advertises stable recall over long update streams. As of the sources I fetched, managed-product support for those streaming features varies, and I did not verify which vendors expose them, so check the engine you actually use.

A rule of thumb across all three: when more than a few percent of your corpus churns per day, favor a design with explicit compaction or a two-tier structure (a small fresh index plus a large frozen one) over relying on in-place deletes.

HNSW vs DiskANN vs IVF-PQ: Decision Matrix

No single index wins, and the matrix below states where each one is the defensible default. The ratings are my qualitative judgment from the mechanisms above, not measured results.

Criterion	HNSW	DiskANN / Vamana	IVF-PQ
RAM per vector	Highest (raw vector plus links) unless quantized	Lowest (compressed code only)	Lowest (code plus id)
Where full vectors live	RAM	SSD	Optional, for rescoring
Latency at high recall	Best when in RAM	Low single-digit ms reported on SIFT1B, SSD bound	Good throughput, recall ceiling needs rerank
Build cost	High, incremental	Highest per vector, batch oriented	Lowest, needs training
Incremental inserts	Native	Needs FreshDiskANN style design	Native, with drift risk
Deletes	Tombstone then repair	Lazy deletes plus merge	Simple list removal
Filtered search	Needs iterative scan or filter-aware edges	Filter-aware variants exist in research	Per-candidate predicate during scan
Tuning surface	M, efConstruction, efSearch	R, search list size, beam width, PQ size	nlist, nprobe, m, nbits
Typical sweet spot	Up to tens of millions in RAM	Hundreds of millions to billions on one box	Very large, cost-sensitive, batch or GPU

Use cases make this concrete. For a retrieval-augmented generation service with 5 million chunks, a few filters, and a p99 target of tens of milliseconds, HNSW in a single node (possibly with int8 scalar quantization) is the boring and correct answer. For an image-similarity catalogue of several hundred million items where RAM budget is the constraint and the SSD is fast, a DiskANN-style index is the natural fit. For a recommendation candidate generator that scans enormous catalogues in batch or on GPUs and tolerates a rerank stage, IVF-PQ remains hard to beat on cost per vector. Our comparisons of pgvector, Qdrant and LanceDB and the hybrid search and reranking ADR apply these index choices to concrete engines and retrieval pipelines.

A counterintuitive thesis: the index is rarely the bottleneck, the recall target is

Teams argue about HNSW vs DiskANN as if the structure decides quality. In practice, two things dominate. First, whether the embedding model’s own recall ceiling justifies chasing 0.99 index recall; if the model’s top-10 is only moderately relevant, the difference between 0.95 and 0.99 index recall is invisible in end-to-end answer quality, while its cost in efSearch and rescoring is large. Second, whether the quantization scheme matches the embedding geometry. A scheme that loses 1% distance fidelity on one model can lose far more on another, which is why you should evaluate recall per embedding model rather than per index. Pick the cheapest configuration that holds your end-to-end metric, then add margin for drift.

Trade-offs, Gotchas, and What Goes Wrong

Benchmarks that hide the trade-off. A speed number without a recall level and a hardware description is not a comparison. Published results such as the DiskANN paper’s SIFT1B numbers are real for that dataset and that machine, but SIFT descriptors behave differently from 1024-dimension text embeddings, and a billion-point recall@1 figure says little about recall@10 under filters. Benchmark on your own queries with ground truth from an exact scan.

Parameters locked at build time. M and efConstruction in HNSW, nlist and the PQ codebooks in IVF-PQ, and R and alpha in Vamana cannot be changed without rebuilding. Runtime knobs (efSearch, nprobe, beam width) are forgiving; build knobs are not. Build a staging index and test before committing a billion-vector rebuild.

Dimension and distribution mismatches in quantization. Binary quantization assumes roughly centered components and high dimensionality; Qdrant’s documentation warns of significant precision loss below about a thousand dimensions. PQ with too few subquantizers pushes the recall ceiling down. Both fail silently: queries still return results, just worse ones. Always keep a probe set with exact answers and alert on its recall.

Rescoring from slow storage. Oversampling is cheap when originals are in RAM and costly when they sit on network disks. A 4x oversampling at k = 20 is 80 random reads per query; at 1,000 queries per second that is 80,000 reads per second, which can saturate a cloud volume before the index does.

Cold starts and page cache. Memory-mapped graphs perform well once the working set is cached and badly after a restart. For HNSW on disk, the first queries after deployment can be orders of magnitude slower, so warm the index before shifting traffic.

Filter drift. A filter that was selective in January can become weak by October as the data changes. Query plans, partial indexes and payload indexes need periodic review. The failure shows up as a recall drop without any code change.

Hubness and duplicates. In high dimensions a few points appear in many neighbor lists, and near-duplicate vectors can crowd a graph neighborhood with redundant edges. The diversity heuristic mitigates this in HNSW and RobustPrune does in Vamana, but deduplicating at ingest remains cheaper than relying on pruning.

Treating the engine as the index. Operational features (replication, snapshots, ACLs, observability) differ widely between engines that share the same underlying algorithm. Do not decide on algorithm alone.

Practical Recommendations

Start from your constraints, not from fashion. Compute the raw footprint (N times d times 4 bytes), add roughly 3% for HNSW links at M = 16, and compare against the RAM you can afford per replica. If it fits, use HNSW with sensible defaults (M = 16, efConstruction 100 to 200, efSearch tuned per query class), and move to scalar or half-precision storage before moving to a new index family. If it does not fit even after int8, then decide between binary or RaBitQ-style codes with rescoring (when you can keep originals on cheaper storage and your embeddings are high-dimensional) and a DiskANN-style SSD index (when you need low latency without paying for terabytes of RAM).

Choose IVF-PQ when cost per vector and batch throughput matter more than tail latency, when you have GPUs or SIMD-heavy hardware, or when you must pack the largest corpus into the smallest memory and can afford a rerank stage. Re-train periodically.

Treat filtering as a first-class design input. Measure recall on filtered ground truth, not just unfiltered, and give each tenant or high-cardinality predicate its own partition when feasible.

Fix a recall target (for example 0.95 recall@10) and a latency budget before benchmarking.
Generate exact ground truth on a sample of real queries, including filtered ones.
Compare indexes at equal recall, not equal parameters.
Keep a held-out probe set and monitor recall continuously.
Quantize the in-memory copy first; keep originals for rescoring.
Plan for deletes and drift: compaction schedule, retraining cadence.
Document build-time parameters so a rebuild is reproducible.

Frequently Asked Questions

Is HNSW or DiskANN better?

Neither is universally better. HNSW usually gives the lowest latency at high recall when the graph and vectors fit in RAM, and it is simple to operate. DiskANN pays more latency per query because it reads SSD sectors, but it holds only compressed vectors in memory, so it serves far larger corpora per node. Choose by whether your data fits in memory at acceptable cost, then validate recall on your own queries.

What does IVF-PQ stand for and how does it work?

IVF-PQ combines an inverted file with product quantization. K-means splits vectors into nlist cells; at query time only the nprobe nearest cells are scanned. Inside each cell, vectors are stored as short product-quantization codes, and distances are estimated by summing precomputed table lookups. It is very memory efficient, but recall saturates below 1.0 unless you rerank a shortlist with the original vectors.

How much memory does HNSW need per vector?

FAISS documents about (d * 4 + M * 2 * 4) bytes per vector. For 1024 dimensions and M = 16 that is 4,224 bytes, so 100 million vectors need roughly 422 GB before replication and overhead. Storing float16 or int8 vectors cuts the vector part by 2x or 4x, and the links remain. Always add headroom for upper layers, metadata and the operating system.

Does quantization hurt recall?

Yes, by an amount that depends on the scheme and the data. Qdrant reports scalar quantization error is usually under 1% in its experiments, while binary quantization needs high-dimensional, centered vectors and rescoring to reach recall such as 0.98. Product quantization has a ceiling set by code size. Oversample and rescore with original vectors, and measure recall on your own embeddings rather than trusting averages.

Why does filtered vector search return fewer results than requested?

Many engines filter after the index scan. With HNSW and an efSearch of 40, a filter matching 10% of rows leaves about four candidates on average, as pgvector’s documentation explains. Fixes include iterative index scans, larger efSearch, partial indexes, partitioning, filter-aware graph edges as in Qdrant, or exact scans when the filter is very selective.

Can I delete or update vectors in these indexes?

Yes, with different costs. HNSW implementations typically tombstone deleted entries and reclaim space during repair or rebuild; the FAISS HNSW class does not support removal. IVF-PQ deletes are simple list removals but codebooks can drift as data changes. FreshDiskANN was designed for streaming inserts and deletes on a graph index, though support in specific products varies.