HNSW vs IVF-PQ vs LSH: Approximate Nearest Neighbor Algorithms Compared

HNSW, IVF-PQ, and LSH are the three most-deployed algorithms for approximate nearest neighbor (ANN) search over vector embeddings. They are all answers to the same bargain — trade a little recall for a large speedup — so the only honest way to compare them is to plot that trade-off on the same data. Use HNSW when recall matters and memory is plentiful, IVF-PQ when the corpus is billion-scale and memory is the constraint, and LSH when you need streaming inserts with theoretical guarantees.

Interactive Algorithm Comparison

The explorer below is real: it builds an IVF index, an LSH index, and a kNN graph over the same GloVe vectors, sweeps each method's knob, and overlays the recall@10 vs fraction-scanned curves. The closer a curve sits to the top-left, the more recall it buys per unit of work.

The one plot that matters

Every ANN method exposes a knob — ef for graphs, nprobe for IVF, the number of tables for LSH — that walks a curve from cheap-and-approximate to exhaustive-and-exact:

A method is "better" when its whole curve dominates — more recall at every level of work. In the explorer, at ~⅓ of the corpus scanned the graph reaches ~0.95 recall, IVF ~0.89, and LSH only ~0.6. That ordering — graph > IVF > LSH for in-memory recall — is exactly what the published ANN benchmarks show.

The three families

• HNSW (graph). A multi-layer neighbor graph searched by greedy walk. Best recall-per-query in memory, because a walk converges in a logarithmic number of hops — but it stores every node's edge list (high RAM) and is awkward to update.
• IVF-PQ (partition + compress). Cluster into cells (IVF), then store each vector as a product-quantization code. Tiny memory and fast build; the standard choice once the index no longer fits in RAM.
• LSH (hashing). Hash vectors so near points collide, and only compare within a bucket. Weaker recall at small scale, but its guarantees and cheap streaming inserts shine on adversarial or constantly-changing data.

Head-to-head

Typical behavior at million-scale (absolute numbers shift with data and tuning):

In FAISS the choice is literally one configuration string:

import faiss
hnsw   = faiss.index_factory(d, "HNSW32")        # graph: best recall, more RAM
ivf_pq = faiss.index_factory(d, "IVF4096,PQ16")  # partition + compress: tiny memory
lsh    = faiss.index_factory(d, "LSH")           # hashing: cheap streaming inserts

Choosing

The decision rule is short: HNSW when recall is the priority and the index fits in memory; IVF-PQ when the corpus is too big for RAM; LSH when inserts are constant and guarantees matter. Beyond these three, Annoy (random-projection trees) and ScaNN (anisotropic quantization) occupy the same curve at different points, and DiskANN extends graphs to SSD. Whatever you pick, measure the recall/work curve on your data before committing — the rankings are stable, the crossover points are not.

References

• Malkov & Yashunin "Efficient and robust approximate nearest neighbor search using HNSW"
• Jégou et al. "Product Quantization for Nearest Neighbor Search" (IVF-ADC)
• Aumüller et al. "ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms"

Related concepts