Approximate nearest neighbor search: how HNSW, IVF, product quantization and hashing trade recall for speed

Rafael

• 2025-09-10

Finding the exact nearest neighbors of a query means comparing it with every vector in the index. With 1 million vectors of 768 numbers each, that is 768 million multiplications for one query, and the cost doubles when the collection does. Approximate nearest neighbor search, ANN for short, skips most of that work and accepts a small chance of missing a true neighbor.

This is part 2 of 3 on how vector search works. Part 1 covered the measures that define "nearest". This part covers the four families of index that make it fast, and how we use one of them, HNSW. Part 3 covers how to measure the results.

The trade: recall for speed

An ANN index is judged on two numbers. Recall@k is the share of the exact top k that the index returns: if the exact top 3 are A, B and C and the index returns A, B and D, recall@3 is 2 of 3. The other number is queries per second at that recall. Every index has a dial that moves along the curve between the two.

Recall here compares the index with exact search. It does not say whether the neighbors are relevant to the person asking, which is a different question for part 3. ANN-Benchmarks, by Martin Aumüller, Erik Bernhardsson and Alexander Faithfull, compares algorithms on this curve. Its main finding is that very different approaches reach comparable quality and speed trade-offs. So the choice comes down to the constraints around the index: memory, build time, updates and filters.

HNSW: a graph with express lanes

Hierarchical Navigable Small World graphs, introduced by Yu. A. Malkov and D. A. Yashunin in the 2016 HNSW paper, connect each vector to a few of its near neighbors. A search starts somewhere and keeps hopping to whichever neighbor is closer to the query, until no neighbor is closer.

On its own that walk can take many hops. HNSW adds layers. Each vector gets a top layer chosen at random with an exponentially decaying probability, so the upper layers hold few vectors with long links between them. The search enters at the top, hops greedily, drops a layer when it can get no closer, and refines on the bottom layer, which holds every vector. The paper reports that this gives logarithmic complexity scaling.

Three settings control it:

The defaults come from the pgvector README and the HNSW-Sharp parameters page. What HNSW costs: memory, because the graph sits next to the vectors (1 million vectors of 768 floats is about 3GB before any links), and build time. pgvector's README says HNSW has a better speed and recall trade-off than its IVFFlat index, at the price of slower builds and more memory. HNSW needs no training step, so you can create the index on an empty table.

Two limits matter for enterprise data. Filters are one: when a permission or a type filter removes most candidates, the walk wastes hops on vectors it then discards. The ACORN paper, by Liana Patel, Peter Kraft, Carlos Guestrin and Matei Zaharia, extends HNSW for search with predicates. HNSW-Sharp has an optional ACORN-γ build mode for it. Deletes are the other: the HNSW-Sharp documentation lists incremental inserts but no deletes.

IVF: search only the nearest cells

An inverted file index, IVF, groups the vectors first. A clustering step, k-means, picks centroids, and each vector is filed under its nearest one. A query is compared with the centroids, and only the vectors in the closest few cells are checked. The number of cells to check is called nprobe in Faiss and pgvector.

The failure is visible in the figure: a neighbor just across a border belongs to a cell you did not open. Raising nprobe fixes it and costs more distance checks. Compared with HNSW, pgvector's README says its IVFFlat index builds faster and uses less memory, with a lower speed and recall trade-off. Unlike HNSW it needs the centroids first, so it needs data to learn from. pgvector suggests starting with rows divided by 1,000 cells up to 1 million rows, and the square root of the rows above that.

Product quantization: smaller vectors

Product quantization, PQ, attacks memory instead of the number of comparisons. It splits each vector into sub-vectors and replaces each one with the number of its nearest entry in a small codebook. The Faiss wiki describes PQ as splitting vectors into sub-vectors that are each quantized to a few bits, usually 8.

As an example, a 768 float vector takes 3,072 bytes. Split into 96 sub-vectors of 8 numbers, each stored as one byte, it takes 96 bytes, 32 times less. Distances are computed from the codes, so they are approximate. A common pattern uses PQ to find candidates, then re-checks the best few against the full vectors. Faiss combines PQ with IVF, and the Faiss paper by Jeff Johnson, Matthijs Douze and Hervé Jégou builds on PQ for search on GPUs. It reports a k-NN graph over 1 billion vectors built in under 12 hours on four GPUs.

Hashing: nearby vectors share a code

Locality-sensitive hashing, LSH, maps each vector to a short code so that near vectors tend to get the same code. For cosine, the usual hash uses random hyperplanes: each hyperplane gives one bit, on which side the vector falls. Two vectors at angle θ get a different bit with probability θ/π, so near vectors agree on most bits. A query only checks the vectors that share its code, and several independent tables give a near neighbor more chances to collide.

Faiss offers IndexLSH, which stores binary codes and compares them with Hamming distance. Tyler Neylon's Introduction to locality-sensitive hashing is a good first read; its hash functions are random projections for Euclidean distance rather than hyperplanes, but the bucket idea is the same.

Side by side

These combine. Faiss lists IVF with PQ (IndexIVFPQ) and a graph over PQ codes (IndexHNSWPQ). It lists flat, IVF, PQ, HNSW and LSH indexes in one place, which makes it a good way to compare them on your own vectors.

What we use

We use HNSW, through HNSW-Sharp, a C# implementation we publish as the HNSW.Net NuGet package. Per its documentation it takes any distance function and has SIMD cosine variants. It writes a built graph to a stream, so a restart does not rebuild it, and it has the optional ACORN-γ mode for filtered search. The core of using it is short:

var graph = new SmallWorld<float[], float>(
    CosineDistance.SIMDForUnits,
    DefaultRandomGenerator.Instance,
    new SmallWorldParameters { M = 15, EfSearch = 50, LevelLambda = 1 / Math.Log(15) });

graph.AddItems(vectors);

foreach (var hit in graph.KNNSearch(query, 10).OrderBy(r => r.Distance))
    Console.WriteLine($"id={hit.Id} dist={hit.Distance:F4}");

The snippet is from the HNSW-Sharp quick start. Its documentation gives a tuning order we follow: pick M first, build once with the defaults, measure recall against brute force on real queries, then turn efSearch, because it changes at query time without a rebuild.

What the figures do and do not show

Each figure computes real distances in your browser. The exact top 3 or top 5 comes from a full scan, so the recall it prints is measured, not drawn. They are small, two dimensional and seeded, so the shapes are right and the numbers are not benchmarks. HNSW is not always the answer: with a few hundred vectors a plain scan is simpler and faster, and the HNSW-Sharp documentation says as much. Run your own recall measurement before you pick an index or a setting.

Further reading

• Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs, Yu. A. Malkov and D. A. Yashunin. The paper behind HNSW.
• ANN-Benchmarks, Martin Aumüller, Erik Bernhardsson and Alexander Faithfull. How to compare ANN algorithms on recall and speed.
• Billion-scale similarity search with GPUs, Jeff Johnson, Matthijs Douze and Hervé Jégou. The Faiss paper, with product quantization at scale.
• Introduction to locality-sensitive hashing, Tyler Neylon. LSH from first principles, with plots.
• ACORN, Liana Patel, Peter Kraft, Carlos Guestrin and Matei Zaharia. Filtered search on top of HNSW.