--- title: "Vector databases under the hood: HNSW and IVF-PQ" description: "ANN search trades accuracy for speed. How HNSW graphs and IVF-PQ quantisation work, which knobs move recall, and how to choose an index." url: https://articles.sythra.ai/articles/vector-databases-under-the-hood slug: vector-databases-under-the-hood author: "vaibhavkothari" author_url: https://articles.sythra.ai/writers/vaibhavkothari date_published: 2026-08-29T09:26:49.323Z date_modified: 2026-08-29T10:22:15.966Z topics: ["Ai", "Machine Learning", "Python", "Databases"] reading_time_minutes: 12 publisher: "Sythra" publisher_url: https://sythra.ai access: free language: en --- # Vector databases under the hood: HNSW and IVF-PQ > ANN search trades accuracy for speed. How HNSW graphs and IVF-PQ quantisation work, which knobs move recall, and how to choose an index. Source: https://articles.sythra.ai/articles/vector-databases-under-the-hood · Author: vaibhavkothari · Published: 2026-08-29 · Reading time: 12 min · Topics: Ai, Machine Learning, Python, Databases 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 ANN 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 ```python 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. ```text 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 HNSW 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. ```text 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 ```python 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 | Knob | When | Effect | Cost | |---|---|---|---| | `M` | Build | Neighbours per node on layer 0. Higher = better connectivity, higher recall ceiling | Memory: `M × 8–16` bytes per vector, plus build time | | `ef_construction` | Build | Beam width while *inserting*. Higher = better-chosen neighbours | Build time only — free at query time | | `ef_search` | Query | Beam width at search time. **The recall/latency dial.** | Latency, roughly linearly | 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. ```text 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-PQ. 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. ```text +-------+-------+-------+ | 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. ```text 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 ``` ```python 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. ```python 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 | Situation | Index | Reasoning | |---|---|---| | Under 100k vectors | Flat (exact) | Genuinely fast enough. Do not add approximation you do not need. | | 100k – 10M, RAM available | HNSW | Best recall per millisecond. The default for a reason. | | 10M+, RAM constrained | IVF-PQ + rerank | 32× compression is the only thing that fits | | 10M+, RAM available, recall critical | HNSW + int8 scalar quantisation | 4× smaller, about one point of recall lost | | Heavy inserts and deletes | IVF, or a compacting store | HNSW tombstones accumulate | | Strict metadata filtering | Depends heavily — see below | | **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. ```python 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. ```remember # Remember this `ef_search` (HNSW) / `nprobe` (IVF) -> the recall/latency dial PQ -> 32x smaller, distances become table lookups Rerank the shortlist -> recovers most of what quantisation cost --- ANN search is approximate by design. Deletes in HNSW are tombstones, and filtering is where vector databases actually differ. ``` ## 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](https://articles.sythra.ai/articles/rag-chunking-retrieval-evaluation-reranking) - [Embeddings explained mathematically](https://articles.sythra.ai/articles/embeddings-explained-mathematically) - [Production ML architecture](https://articles.sythra.ai/articles/production-ml-architecture) ## Glossary (terms defined in this article) - **ANN** (advanced) — Approximate Nearest Neighbour search: returns very-probably-nearest vectors instead of provably-nearest ones, in exchange for orders of magnitude more speed - **HNSW** (advanced) — Hierarchical Navigable Small World: a layered proximity graph you greedily walk from a sparse top layer down to a dense bottom layer - **IVF-PQ** (advanced) — Inverted File index with Product Quantisation: cluster the space, then store each vector as a handful of bytes instead of thousands