IVF-PQ vs HNSW vs DiskANN vs ScaNN

What it is

Four approximate nearest neighbour index families that make different trades between memory, recall, build cost and query latency. The choice is decided almost entirely by whether the vectors fit in RAM and by how often the corpus changes.

                MEMORY      RECALL@10   BUILD    UPDATES
HNSW            highest     best        slow     incremental
                (graph +                          (with a
                 vectors)                          delete
                                                   problem)
IVF-PQ          lowest      good        needs     re-train the
                (codes,     with        training  codebook
                 not         reranking            eventually
                 vectors)
DiskANN         low RAM,    good        slow      rebuild
                high SSD
ScaNN           medium      very good   medium    rebuild
                            at speed

Commonly confused as a quality ranking. They are different points on a memory-recall-latency surface, and at the same memory budget their recall is much closer than the headline benchmarks suggest, because the benchmarks usually compare at equal configuration rather than at equal memory.

Also commonly confused with the vector database. These are index structures inside a database, and most vector databases offer more than one, so "we use Pinecone" or "we use pgvector" does not answer this question.

The problem it solves

Exact nearest neighbour search is linear, and the alternatives that work in low dimensions do not work in high ones.

EXACT
  50M vectors x 768 dims = 38 billion multiply-adds per
  query. Hundreds of milliseconds even with good SIMD.

TREES (kd-tree, ball tree)
  Degrade to linear scan above roughly 20 dimensions,
  because the volume of a high-dimensional space
  concentrates and pruning stops working.
  -> This failure is why graph and quantisation methods
     exist, and naming it is a good signal.

LSH
  Works, and needs many hash tables for good recall, so its
  memory cost is high for the recall it delivers. Largely
  superseded in practice.

So the practical field is: graph traversal (HNSW, DiskANN), inverted-file partitioning plus quantisation (IVF-PQ), and learned partitioning with anisotropic quantisation (ScaNN).

Mechanics

The memory arithmetic, which decides most cases

50M vectors, 768 dimensions.

HNSW, fp32 vectors + graph (M=32)
  vectors: 768 x 4 = 3,072 B
  graph:   ~8 x M  =   282 B
  -> 167 GB

HNSW, int8 vectors + graph
  vectors: 768 x 1 =   768 B
  graph:              282 B
  -> 52 GB

IVF-PQ (m=96 sub-quantisers, 8 bits each)
  code:    96 x 1  =    96 B
  + coarse centroid id, ~4 B
  + codebooks (small, shared)
  -> ~5 GB
  *** 30x less than HNSW fp32. ***

DiskANN
  RAM: compressed PQ vectors for routing, ~5-10 GB
  SSD: full vectors + graph, ~180 GB on disk
  -> fits a single machine that HNSW could not

That table is the decision for most systems. If 52 GB fits your node, HNSW with int8 is the best recall-per-latency available. If it does not, the question becomes which compromise, and the answer depends on whether you have SSD headroom (DiskANN) or want to stay in RAM (IVF-PQ).

HNSW: best recall, highest memory

Covered in depth in HNSW internals. The summary for comparison purposes:

+ Best recall-versus-latency curve at in-memory scale.
+ No training step, so it works on a new corpus immediately.
+ Incremental insertion.
- Highest memory: full vectors plus a graph.
- No true delete. Tombstones stay, memory is never
  reclaimed, and recall degrades as the deleted fraction
  grows.
- Build is O(n log n x efConstruction) and slow.

IVF-PQ: partition, then compress

Two independent ideas that are usually combined and are worth separating.

IVF (inverted file): partition the space
  1. k-means over a sample to find nlist centroids
     (typically sqrt(n) as a starting point, so ~7,000 for
     50M vectors).
  2. Assign every vector to its nearest centroid.
  3. At query time, search only the nprobe nearest
     partitions.

  nprobe is the recall/latency dial:
    nprobe=1     fast, poor recall
    nprobe=32    typical
    nprobe=nlist exhaustive, which defeats the point

PQ (product quantisation): compress the vectors
  1. Split the 768-dim vector into m sub-vectors
     (m=96 -> 8 dims each).
  2. Run k-means per sub-space to get 256 centroids
     (8 bits).
  3. Store the 96 centroid IDs, not the vector.
     -> 96 bytes instead of 3,072.

  Distances are computed from a precomputed lookup table
  per query: for each sub-space, the distance from the
  query's sub-vector to each of the 256 centroids. Then a
  candidate's distance is 96 table lookups and adds, with
  no vector arithmetic at all.
  *** That table trick is why PQ is fast as well as
      small. ***

The property that makes IVF-PQ usable despite the compression loss: rerank with full vectors.

1. IVF-PQ returns 500 candidates using compressed distances.
2. Fetch the FULL vectors for those 500 only.
3. Recompute exact distances and take the top 10.

  Recall approaches exact, memory stays low for the index,
  and the full vectors live on SSD or in a separate store
  because only 500 are read per query.

Reranking is what makes the recall respectable, and an IVF-PQ deployment without it is leaving most of its quality behind.

The costs to name:

- Needs TRAINING on a representative sample. If the data
  distribution shifts, the centroids and codebooks get
  worse and you eventually retrain, which is a rebuild.
- The partition boundary problem: a query near a boundary
  has its true neighbours in a partition it did not probe.
  Higher nprobe mitigates it and costs latency.
- Tuning is a two-dimensional search (nlist x nprobe) plus
  m and the bit depth.

DiskANN: when it does not fit in RAM

THE IDEA
  Build a graph designed so that traversal touches few
  nodes, then keep the graph and full vectors on SSD, with
  a compressed (PQ) copy of every vector in RAM for
  routing.

  Query:
    1. Traverse using the in-RAM compressed vectors to
       decide where to go.
    2. Read the small number of full vectors actually
       needed from SSD.
    3. Rerank exactly.

  A query is a handful of SSD reads rather than thousands,
  which is what makes it viable at all.

+ Billions of vectors on one machine.
+ Recall close to in-memory graph methods.
- Query latency is higher: SSD reads are ~100 µs against
  ~100 ns for RAM, so it is milliseconds rather than
  hundreds of microseconds.
- Build is expensive and it is not incremental in the same
  way HNSW is.

The design insight worth stating: the graph is built to minimise the number of SSD reads per query, which is a different objective from minimising hops, and that is what distinguishes it from "HNSW on disk", which performs badly because a general graph traversal is a random-read storm.

ScaNN: quantisation aligned to the metric

THE OBSERVATION
  Standard PQ minimises RECONSTRUCTION error: how close is
  the compressed vector to the original? But what you care
  about is preserving the INNER PRODUCT ranking, and those
  are not the same objective.

  An error component parallel to the query direction
  changes the inner product; a perpendicular one barely
  does. Standard PQ treats both equally.

ANISOTROPIC VECTOR QUANTISATION
  Weight the quantisation loss to penalise parallel error
  more than perpendicular error.
  -> Better ranking accuracy at the same bit budget.

+ Strong recall-per-latency, particularly for
  maximum-inner-product search, which is what
  recommendation retrieval actually is.
- More complex, and the implementation ecosystem is
  narrower than FAISS or HNSW.

The reason to know it: it is a reminder that the quantisation objective should match the task. For cosine or inner-product retrieval, minimising reconstruction error is a proxy, and optimising the proxy leaves recall on the table.

Choosing

Does it fit in RAM with int8 vectors (roughly d bytes +
8M per vector)?
    YES, and the corpus changes often
        -> HNSW. Best recall, incremental inserts, and
           plan for the rebuild that the delete problem
           forces.
    YES, and the corpus is static
        -> HNSW still, or ScaNN if you are doing
           inner-product retrieval and want the extra
           recall per unit of latency.

Does it NOT fit in RAM?
    Do you have SSD and can you tolerate low-millisecond
    latency?
        -> DiskANN.
    Do you need to stay in RAM at very low cost per
    vector?
        -> IVF-PQ with reranking.

Is the corpus under ~100k vectors?
    -> BRUTE FORCE. Exact, single-digit milliseconds with
       SIMD, no build, no parameters, no delete problem.
       This threshold is higher than people expect.

Is a filter applied to most queries?
    -> The filter selectivity matters more than the index
       family. See filtered vector search.

A worked example: the same corpus, three budgets

CORPUS: 200M product embeddings, 768 dims, updated
continuously (2% of items change daily). Target: recall@10
above 0.95, p99 under 50 ms.

OPTION A: HNSW, int8
  memory: 200M x (768 + 282) = 210 GB
  -> Needs a 256 GB machine, or 4 shards on 64 GB nodes.
  recall: ~0.97 at ef=128
  latency: ~8 ms
  updates: incremental inserts work; deletes accumulate,
    so a rebuild every ~6 weeks at 2% daily churn (which
    reaches ~25% tombstones in about 6 weeks even
    accounting for re-adds).
  cost: 4 x 64 GB memory-optimised nodes, replicated 3x
    = 12 nodes.

OPTION B: IVF-PQ with reranking
  memory: 200M x ~100 B = 20 GB for the index
  full vectors on SSD for reranking: 600 GB
  -> Fits ONE 32 GB node for the index.
  recall: ~0.93 with nprobe=32, ~0.96 with reranking of
    top 500
  latency: ~12 ms including the rerank SSD reads
  updates: inserts are cheap (assign to a centroid,
    encode); the codebook degrades as the distribution
    shifts, so retrain quarterly.
  cost: 3 nodes with SSD, replicated. 4x cheaper than A.

OPTION C: DiskANN
  memory: 200M x ~100 B = 20 GB routing copy
  SSD: ~640 GB
  recall: ~0.95
  latency: ~15 ms
  updates: not incremental in the same way; rebuild
    weekly.
  cost: similar to B.

THE DECISION
  Option B, because:
    - the recall target is met with reranking
    - the latency budget has room at 12 ms
    - it is 4x cheaper, and at 200M vectors that is a
      material number
    - the continuous update pattern suits IVF's cheap
      inserts better than DiskANN's rebuild

  And the deciding factor was NOT recall, which all three
  met. It was cost, and the update pattern.

WHAT WOULD FLIP IT
  A p99 budget of 10 ms -> HNSW, and pay for the memory.
  A static corpus -> DiskANN becomes attractive because
    the rebuild cost stops mattering.
  50M vectors instead of 200M -> HNSW int8 is 52 GB,
    fits one node, and the cost argument disappears.

The generalisable point: all three met the recall target, so recall was not the deciding variable. The headline benchmark number is rarely what decides these, and cost and update pattern usually are.

Production evidence

Malkov and Yashunin's HNSW paper (2016) and hnswlib are the reference for the graph family, and ANN-Benchmarks consistently shows HNSW at the top of the recall-versus-QPS curve at in-memory scale.

Jégou, Douze and Schmid, "Product Quantization for Nearest Neighbor Search" (TPAMI 2011) is the PQ paper, and FAISS is the reference implementation of IVF-PQ and its composite index strings (IVF4096,PQ64), which is also the clearest expression of how the pieces compose.

Subramanya et al., "DiskANN" (NeurIPS 2019) documents the SSD-resident graph and its central design goal of minimising reads per query, and Microsoft's use of it for billion-scale search is the production evidence.

Guo et al., "Accelerating Large-Scale Inference with Anisotropic Vector Quantization" (ICML 2020) is ScaNN, and its argument that the quantisation objective should preserve inner-product ranking rather than reconstruction is the contribution worth knowing.

ANN-Benchmarks (Aumüller, Bernhardsson and Faithfull) is the standard comparison, and the right citation for relative performance claims rather than vendor material. Its per-dataset results also show how much the ranking depends on the data, which is the caution against a universal answer.

The debate

The case for HNSW as the default: best recall-per-latency at in-memory scale, no training step, incremental inserts, and the most mature tooling. If the vectors fit, it is the strongest choice and everything else is a compromise.

The case for IVF-PQ: memory is the binding constraint in most large deployments, and a 30x reduction changes the machine class and therefore the cost. With reranking the recall gap largely closes, so you are trading a training step and a tuning exercise for a much cheaper deployment.

The case for DiskANN: billions of vectors on one machine without sharding, which removes the scatter-gather latency and operational surface that sharding brings.

The case for brute force: below roughly 100,000 vectors it is exact, single-digit milliseconds with SIMD, and has no build, no parameters and no delete problem. More production "vector search" problems are this size than people expect.

My position: brute force under ~100k, HNSW with int8 when it fits in RAM, IVF-PQ with reranking when it does not, and DiskANN when you want billions on one machine and can spend milliseconds.

The decision is memory first, and everything else second, because it is the variable that changes the machine class rather than a parameter. At 50 million vectors, int8 HNSW is 52 GB and fits comfortably, so the question does not arise. At 200 million it is 210 GB, and now the cost difference between index families is a material number rather than an implementation preference.

The detail that makes IVF-PQ competitive rather than a compromise is reranking with full vectors. Retrieve 500 candidates on compressed distances, fetch those 500 full vectors, recompute exactly, take the top 10. Recall approaches exact, the index stays small, and the full vectors can live on SSD because you read a few hundred per query. An IVF-PQ deployment without reranking is leaving most of its quality behind, and that is the most common implementation mistake in this family.

On DiskANN, the insight worth carrying is that it is not "HNSW on disk": the graph is constructed to minimise SSD reads per query, which is a different objective from minimising hops. Putting a general graph index on disk performs badly because traversal becomes a random-read storm, and knowing why is the difference between understanding the family and listing it.

And the threshold I would state plainly: check the corpus size before building an index at all. Under about a hundred thousand vectors, brute force with SIMD is exact, single-digit milliseconds, and has none of the operational surface: no build job, no parameters, no tombstone accumulation, no rebuild schedule. That threshold is higher than people expect and a meaningful share of vector search projects sit below it.

Where I would push back on a benchmark-driven choice: the headline recall number is rarely what decides these. In the worked example all three families met the recall target, and the decision came down to cost and the update pattern. Comparing at equal configuration rather than at equal memory budget also systematically flatters HNSW, so the published curves need reading carefully.

Follow-up Q&A

"How do you choose between these?" Memory first, because it is the variable that changes the machine class rather than a parameter. Compute the footprint: HNSW is roughly the vector size plus eight times M per vector, so 50 million 768-dimensional int8 vectors is about 52 gigabytes and fits one node. Two hundred million is 210 gigabytes and now the family choice is a cost decision. If it fits, HNSW. If not, IVF-PQ with reranking to stay in RAM, or DiskANN if you have SSD and can spend milliseconds.

"What is IVF-PQ actually doing?" Two independent things usually combined. IVF partitions the space with k-means into nlist cells and searches only the nprobe nearest ones, which is the recall-latency dial. PQ splits each vector into sub-vectors, quantises each to one of 256 centroids, and stores 96 bytes of centroid ids instead of 3,072 bytes of floats. And distances come from a precomputed lookup table per query, so scoring a candidate is 96 lookups and adds with no vector arithmetic, which is why it is fast as well as small.

"Doesn't that compression destroy recall?" It would, without reranking, and that is the most common implementation mistake in this family. The fix is to retrieve 500 candidates on compressed distances, fetch the full vectors for just those 500, recompute exactly and take the top 10. Recall approaches exact, the index stays small, and the full vectors can live on SSD because you only read a few hundred per query.

"What makes DiskANN different from putting HNSW on disk?" The graph is constructed to minimise SSD reads per query, which is a different objective from minimising hops. A general graph traversal on disk is a random-read storm and performs badly. DiskANN keeps a compressed copy of every vector in RAM for routing decisions, so it only reads the small number of full vectors it actually needs, and a query becomes a handful of SSD reads rather than thousands.

"What is ScaNN's contribution?" Aligning the quantisation objective with the task. Standard PQ minimises reconstruction error, how close the compressed vector is to the original, and what you actually care about is preserving the inner-product ranking. Error parallel to the query direction changes the inner product; perpendicular error barely does, and standard PQ treats them equally. Anisotropic quantisation weights the loss accordingly, giving better ranking accuracy at the same bit budget. The general lesson is that optimising a proxy leaves recall on the table.

"When would you not build an index at all?" Under about a hundred thousand vectors. Brute force with SIMD is exact, single-digit milliseconds, and has no build job, no parameters, no tombstone accumulation and no rebuild schedule. That threshold is higher than people expect and a meaningful share of vector search projects sit below it, where an index is pure operational surface for no benefit.

"Which has the best recall?" At equal configuration, HNSW, and that comparison flatters it. At equal memory budget the gap narrows a lot, because IVF-PQ at the same footprint can afford far more of everything else. And in the case I worked, all three families met the recall target, so recall was not the deciding variable at all: cost and the update pattern were. The headline benchmark number is rarely what decides these.

"How do updates differ?" HNSW supports incremental inserts and has no true delete, so tombstones accumulate, memory is never reclaimed, and effective recall falls, which forces a periodic rebuild-and-swap. IVF-PQ inserts cheaply, assign to a centroid and encode, but the codebook degrades as the data distribution shifts, so it needs periodic retraining, which is also a rebuild. DiskANN is not incremental in the same way and is typically rebuilt. So all three eventually need a rebuild pipeline, and the difference is the cadence and what triggers it.

"Does the filtering story change the answer?" Substantially, and it is worth raising. Filtered approximate search has a recall cliff, because graph traversal assumes connectivity and filtering disconnects it, so at low selectivity you can lose most of your recall silently. IVF handles some filters more gracefully because you can restrict which partitions to probe. But the bigger lever is routing by estimated cardinality: exact scan below about ten thousand candidates, partitioned index where the filter is a partition key.

Common misconceptions

"HNSW is simply the best." It has the best recall-per-latency at equal configuration and the highest memory cost. At equal memory budget the comparison is much closer.

"PQ destroys recall." Without reranking, largely yes. With reranking of a few hundred candidates on full vectors, recall approaches exact.

"DiskANN is HNSW on SSD." Its graph is built to minimise reads per query. A general graph on disk is a random-read storm.

"Pick the index by benchmark recall." In practice all viable candidates usually meet the recall target and the decision is cost and update pattern.

"You always need an ANN index." Under about 100k vectors brute force is exact, fast and has no operational surface at all.

Interview delivery note

Lead with the variable that actually decides it: "Memory first, because it's the thing that changes the machine class rather than a parameter. HNSW is roughly the vector plus eight times M per vector, so fifty million 768-dimensional int8 vectors is about fifty-two gigabytes and fits one node. Two hundred million is two hundred and ten, and now the family choice is a cost decision."

Explain PQ mechanically, because the lookup-table trick is the part people cannot usually produce: "PQ splits the vector into ninety-six sub-vectors, quantises each to one of two hundred and fifty-six centroids, and stores ninety-six bytes instead of three thousand. And distances come from a lookup table computed once per query, so scoring a candidate is ninety-six lookups and adds with no vector arithmetic. That's why it's fast as well as small."

Then the detail that makes it viable: "And you rerank. Five hundred candidates on compressed distances, fetch those five hundred full vectors, recompute exactly. Recall approaches exact and the index stays small. An IVF-PQ deployment without reranking is leaving most of its quality behind, and that's the most common mistake in this family."

Distinguish DiskANN properly: "DiskANN isn't HNSW on disk. Its graph is built to minimise SSD reads per query, which is a different objective from minimising hops, and a general graph traversal on disk is a random-read storm."

Close on the two things that reframe the question: "Though in the case I worked all three families met the recall target, so recall wasn't the deciding variable, cost and the update pattern were. And I'd check the corpus size first: under about a hundred thousand vectors, brute force is exact, single-digit milliseconds, and has no build, no parameters and no delete problem."

The Staff & Team Lead Interview Reference