Vector databases under the hood: HNSW and IVF-PQ

Every vector database sells the same thing: nearest-neighbour search over millions of embeddings in single-digit milliseconds. Every one of them delivers it by not finding the true nearest neighbours.

That is not a criticism. It is the entire design. Exact search is O(n·d) per query — 10 million vectors at 768 dimensions is 7.7 billion multiply-adds, and no amount of engineering makes that a 5 ms operation. So ANNApproximate Nearest Neighbour search: returns very-probably-nearest vectors instead of provably-nearest ones, in exchange for orders of magnitude more speed search trades a few percent of recall for two or three orders of magnitude of speed.

If you use a vector database, the useful thing to understand is precisely what you traded and which knob buys it back.

Baseline: what exact search costs

import numpy as np


def exact_search(query, vectors, k=10):
    # vectors: (n, d), L2-normalised. Cosine similarity = dot product.
    sims = vectors @ query        # every single vector, every single time
    return np.argpartition(-sims, k)[:k]

Perfect recall, linear cost. Keep this around — you cannot measure an approximate index without an exact one to compare against.

n = 10,000,000 vectors, d = 768
per query: 7.68e9 FLOPs -> ~2-4 seconds single-threaded
target:    < 10 ms
required speedup: ~500x

You do not get 500× from better SIMD. You get it by not looking at most of the vectors.

HNSW: navigate, do not scan

HNSWHierarchical Navigable Small World: a layered proximity graph you greedily walk from a sparse top layer down to a dense bottom layer is the default index in Qdrant, Weaviate, Milvus, pgvector's hnsw and Lucene-based engines. It is a graph, not a tree, and the idea is borrowed from how you navigate a city: motorway most of the way, surface streets at the end.

The structure

Every vector is a node, connected to its approximate neighbours. Crucially there are multiple layers: layer 0 holds every vector with dense local links; each layer above holds a random subset with long-range links.

layer 2   A ----------------------- K          sparse, long hops
          |                         |
layer 1   A ------ E ------ H ----- K          medium
          |        |        |       |
layer 0   A-B-C-D-E-F-G-H-I-J-K-L-M-N          every vector, dense
                    ^
                    query lands near here

A node's maximum layer is drawn from an exponentially decaying distribution, so higher layers are exponentially sparser. That gives the search a logarithmic number of layers to descend.

The search

import heapq


def hnsw_search(graph, query, entry, ef, k):
    """Greedy descent through upper layers, then beam search on layer 0."""
    cur = entry
    for layer in range(graph.max_layer, 0, -1):
        improved = True
        while improved:                    # pure greedy: take the best neighbour
            improved = False
            for nb in graph.neighbours(cur, layer):
                if dist(nb, query) < dist(cur, query):
                    cur, improved = nb, True

    # Layer 0: beam search keeping ef candidates alive
    visited = {cur}
    frontier = [(dist(cur, query), cur)]        # min-heap
    best = [(-dist(cur, query), cur)]           # max-heap of results

    while frontier:
        d, node = heapq.heappop(frontier)
        if d > -best[0][0] and len(best) >= ef:
            break                               # frontier is worse than results
        for nb in graph.neighbours(node, 0):
            if nb in visited:
                continue
            visited.add(nb)
            dn = dist(nb, query)
            if len(best) < ef or dn < -best[0][0]:
                heapq.heappush(frontier, (dn, nb))
                heapq.heappush(best, (-dn, nb))
                if len(best) > ef:
                    heapq.heappop(best)

    return [n for _, n in sorted((-d, n) for d, n in best)][:k]

The upper layers are pure greedy — one path, no backtracking — which is fast and approximate. Layer 0 uses a beam of width ef, which is where accuracy is recovered. A query touches perhaps a few thousand nodes out of ten million.

The three knobs that matter

Practical guidance:

• M = 16 is a sane default; 32–64 for high-dimensional or high-recall requirements. Below 8 the graph fragments and recall collapses.
• ef_construction = 200 is a good default. It costs build time and nothing else, so be generous — it is the cheapest recall you will ever buy.
• ef_search must be at least k. Sweep it: 50, 100, 200, 400. This is the only one of the three you can change without rebuilding, so it is the per-workload dial.

ef_search    recall@10    p95 latency
   16          0.82          1.1 ms
   50          0.95          2.4 ms
  100          0.98          4.1 ms
  200          0.993         7.6 ms
  400          0.997        14.9 ms    <- paying 2x for 0.4 points

The costs nobody mentions in the tutorial

Memory. HNSW keeps the full vectors and the graph in RAM. Ten million 768-dim float32 vectors is 30 GB before the graph, which at M=16 adds several GB more. This number decides your infrastructure bill, and it is why quantisation exists.

Deletes are not deletes. Removing a node would sever the paths routing through it, so implementations tombstone instead. Deleted vectors keep occupying memory and keep being traversed. A collection with heavy churn degrades until you rebuild the segment. If your workload is delete-heavy, ask your database how it compacts — the answer decides whether it is viable.

Build cost is substantial. Insertion is O(log n) per vector but with a large constant. Bulk-loading 10M vectors is a job to plan, not an afterthought.

IVF-PQ: partition, then compress

When the vectors do not fit in RAM, the answer is IVF-PQInverted File index with Product Quantisation: cluster the space, then store each vector as a handful of bytes instead of thousands. This is FAISS's workhorse and what most billion-scale systems run.

Part 1 — IVF, the partitioning

Run k-means over the corpus to get nlist centroids. Each vector joins its nearest centroid's list. At query time, search only the nprobe closest lists.

        +-------+-------+-------+
        |  o 1  |  o 2  |  o 3  |     nlist = 9 partitions
        +-------+-------+-------+
        |  o 4  | [o 5] |  o 6  |     query lands in 5
        +-------+-------+-------+
        |  o 7  |  o 8  |  o 9  |     nprobe = 3 -> search 5, 2, 4
        +-------+-------+-------+
                                      scanned: 3/9 of the corpus

nprobe is IVF's equivalent of ef_search. Its failure mode is specific and worth knowing: if the true nearest neighbour sits just across a partition boundary and you did not probe that partition, it is simply invisible. Raising nprobe widens the net.

Rule of thumb: nlist ≈ 4·sqrt(n), then tune nprobe from 1 up to about nlist/20.

Part 2 — PQ, the compression

This is the clever part. Split each 768-dim vector into m sub-vectors and replace each sub-vector with the ID of its nearest centroid in a small per-subspace codebook.

original vector, d = 768, float32 = 3072 bytes

split into m = 96 sub-vectors of 8 dims each
  |- sub 1  (8 dims) --> nearest of 256 centroids --> 1 byte
  |- sub 2  (8 dims) --> nearest of 256 centroids --> 1 byte
  |- ...
  +- sub 96 (8 dims) --> nearest of 256 centroids --> 1 byte

stored: 96 bytes.   compression: 32x

import numpy as np
from sklearn.cluster import KMeans


class ProductQuantizer:
    def __init__(self, d, m=96, nbits=8):
        self.m, self.dsub, self.ncent = m, d // m, 2 ** nbits
        self.codebooks = None                     # (m, ncent, dsub)

    def fit(self, X):
        subs = X.reshape(len(X), self.m, self.dsub)
        self.codebooks = np.stack([
            KMeans(self.ncent, n_init=3).fit(subs[:, i, :]).cluster_centers_
            for i in range(self.m)
        ])
        return self

    def encode(self, X):
        subs = X.reshape(len(X), self.m, self.dsub)
        codes = np.empty((len(X), self.m), dtype=np.uint8)
        for i in range(self.m):
            d = ((subs[:, i, :, None] - self.codebooks[i].T[None]) ** 2).sum(1)
            codes[:, i] = d.argmin(1)
        return codes                              # (n, m) uint8

    def search(self, query, codes, k=10):
        """Asymmetric distance: the query stays full precision."""
        q = query.reshape(self.m, self.dsub)
        # Distance from each query sub-vector to all 256 centroids, precomputed
        lut = np.stack([
            ((self.codebooks[i] - q[i]) ** 2).sum(1) for i in range(self.m)
        ])                                        # (m, ncent)
        # Each stored vector: m lookups + m-1 adds. No d-dimensional maths.
        dists = lut[np.arange(self.m), codes].sum(1)
        return np.argpartition(dists, k)[:k]

The search method is the whole trick. A distance computation becomes 96 table lookups and 95 additions instead of 768 multiply-adds — and the stored data is 32× smaller, so far more of it fits in cache. This is asymmetric distance computation: the query is never quantised, only the database, which recovers a meaningful share of the accuracy quantisation costs.

What quantisation costs you

PQ is lossy. Two distinct vectors can map to identical codes, and the distances you compute are approximations of approximations. Typical recall@10 for IVF-PQ lands in the 0.75–0.90 range, against 0.95–0.99 for a well-tuned HNSW.

The standard remedy is rerank against exact vectors: retrieve 10× more candidates from the compressed index, then rescore that shortlist with full-precision vectors from disk or cache.

candidates = ivfpq.search(query, k=100)          # fast, approximate
exact = full_vectors[candidates] @ query          # 100 exact dot products
top10 = candidates[np.argsort(-exact)[:10]]

Same shortlist-then-rescore pattern as cross-encoder reranking in RAG, one layer lower in the stack.

Choosing an index

Scalar quantisation deserves more attention than it gets. Storing int8 instead of float32 is 4× compression for roughly one point of recall, it works with HNSW, and it is usually a single config flag. If your problem is "HNSW almost fits in RAM", try this before restructuring to IVF-PQ.

The filtering problem

This is where vector databases genuinely differ, and where public benchmarks mislead.

You want "the 10 nearest vectors where tenant_id = 42 and status = 'active'". Three strategies exist:

Pre-filter — build the allowed ID set first, search only those. Correct, and it destroys HNSW: the graph's edges lead mostly to filtered-out nodes, the walk stalls, recall craters. Fine for IVF, and fine when the filter is so selective that exact search over the survivors is cheap.

Post-filter — search normally, drop non-matching results. Fast, and it silently returns fewer than k results — sometimes zero — when the filter is selective. Everyone meets this in production: the query "works" and returns three results out of ten.

Filtered search — apply the predicate during traversal, with the graph adapted to stay connected under filtering. This is what the good implementations do, and it is the real differentiator between vector databases.

The practical advice: benchmark your filters, not just your vectors. A database excellent at unfiltered recall can be unusable at 1% selectivity, and no public benchmark will tell you that about your metadata distribution.

Measure your own recall

Every parameter above is a trade, and you cannot manage a trade you have not measured.

import time
import numpy as np


def measure_recall(index, vectors, queries, k=10):
    """Compare the approximate index against brute force on a query sample."""
    hits = 0
    for q in queries:
        truth = set(np.argpartition(-(vectors @ q), k)[:k])
        approx = set(index.search(q, k=k))
        hits += len(truth & approx)
    return hits / (len(queries) * k)


for ef in [16, 32, 64, 128, 256, 512]:
    index.set_ef(ef)
    t0 = time.perf_counter()
    r = measure_recall(index, vectors, sample_queries)
    ms = (time.perf_counter() - t0) / len(sample_queries) * 1e3
    print(f"ef={ef:4d}  recall={r:.3f}  {ms:.2f} ms")

A thousand sampled queries and one brute-force pass gives you the whole curve. Pick the point that matches your latency budget — and re-check it after any significant change to the corpus, because recall is a property of the data distribution, not only of the parameters.

Frequently asked questions

Why does my vector search miss obvious results?

Because ANN indexes are approximate by construction. Raise ef_search (HNSW) or nprobe (IVF) and see whether the missing result appears. If it never appears at any setting, the problem is upstream — embedding, chunking or normalisation — not the index.

HNSW or IVF-PQ?

RAM decides it. If the vectors fit in memory, HNSW gives better recall for the same latency. If they do not, IVF-PQ's 32× compression is what makes the workload possible at all, and you recover accuracy by reranking the shortlist against exact vectors.

Do I need a dedicated vector database?

Under a few million vectors, pgvector alongside your existing Postgres is usually right — you keep transactions, joins and metadata filtering in one place. Dedicated engines earn their operational cost at larger scale, with heavy filtering, or when you need multi-vector or sparse-dense hybrid retrieval.

What does ef_search actually control?

The beam width during the layer-0 search: how many candidate nodes stay alive as the search explores. Larger beam, more graph explored, higher recall, proportionally more latency. It is a query-time parameter, so you can set it per request — high for an offline job, low for autocomplete.

Why did recall drop after I deleted a lot of vectors?

HNSW tombstones deletions rather than removing nodes, because removing them would sever the paths routing through them. Traversal still pays for them and graph quality degrades. Rebuild or compact the affected segments.

Next reading on Sythra Articles

• Building RAG properly: chunking, evaluation and reranking
• Embeddings explained mathematically
• Production ML architecture