Vector DB Internals: HNSW & IVF

Vector database internals explain why similarity search can be fast without scanning every embedding. This chapter covers Hierarchical Navigable Small World (HNSW), inverted file (IVF) indexing, recall-latency tradeoffs, and the operational knobs behind nearest-neighbor retrieval.

Recursive Language Models showed how to organize compute over huge external context. This chapter starts the retrieval section from the other side: before an agent or RAG pipeline can reason over documents, the system has to find the candidate chunks quickly enough to fit an interactive product.

Imagine finding a specific returns-support ticket in an archive with millions of cases, but instead of an exact ticket ID, you only have a vague description of the customer problem. If you had to check every case one by one, the search would take too long for an interactive product. This is the challenge of similarity search in modern AI systems.

When you ask an AI model a question, it converts your query into a vector (a long list of numbers). To find relevant answers, for example in a RAG (Retrieval-Augmented Generation) system where an LLM grounds its responses in your documents, the database must search through millions or billions of other vectors to find the ones most similar to yours.

This article builds on the embedding idea you learned earlier: text gets turned into vectors so a machine can compare meaning. Here, we'll look at how a production database actually finds the closest vectors when there are millions of them. By the end, you'll know how to choose between the two main index families, tune their knobs, and spot the mistakes that make vector search slow or inaccurate in production.

The brute-force problem

The simplest method, called Exact Search (or k-NN for k-Nearest Neighbors), calculates the distance from your query vector to every vector in the database.

Mathematically, given a query $q$ and a database of $N$ vectors each with $d$ dimensions, exact search has $O(N \cdot d)$ complexity. That notation means the work grows in direct proportion to both the number of vectors and the number of dimensions.

Let's make that concrete. Suppose you have 100 million product-review embeddings, each with 1,536 dimensions, stored as 4-byte floats. A flat query scores all 100 million vectors, or 153.6 billion scalar components before considering vectorization, batching, memory bandwidth, or accelerator hardware. Whether that fits an SLA is a benchmark question, not something dimensionality alone can answer.

The memory picture is just as stark:

$100{,}000{,}000 \text{ vectors} \times 1{,}536 \text{ dims} \times 4 \text{ bytes} \approx 614 \text{ GB} \approx 572 \text{ GiB}$

That's raw vector storage alone, before any index overhead (the lab below reports the same quantity in GiB, the binary units RAM is usually measured in). A single ordinary server won't keep that raw collection in RAM. Approximate Nearest Neighbor (ANN) indexes reduce scored candidates by accepting that some true neighbors may be missed.

For large, weakly filtered collections, ANN is usually the practical serving path. Exact flat search still matters: it's the ground truth for measuring recall, and it can be the right production execution path when a metadata filter leaves only a small candidate set. For example, pgvector performs exact nearest-neighbor search by default and documents exact search as useful for selective filter conditions.^[1]

The main quality metric is Recall@k: of the true top-k nearest neighbors, how many did your ANN index recover? Latency numbers without recall are misleading because an index can look fast simply by missing good candidates. A system that returns random vectors in 1 ms has terrible recall. A system that takes 20 ms and finds 99 of the true top 100 has excellent recall.

Key insight: Latency without recall is incomplete. Keep an exact-search evaluation set, measure ANN recall against it, and choose a latency-recall operating point that satisfies the product requirement.

HNSW (Hierarchical Navigable Small World)

HNSW is a widely used in-memory ANN index because it can provide a strong recall-latency trade-off without a separate centroid-training phase.^[2] Whether it beats another index on your data still needs measurement under the same memory and recall constraints.

Core concept

HNSW is based on a multi-layer graph structure that mimics how people find things in the real world. Think of zooming in on a map: you start at the continent level, narrow down to a country, then a city, then a street. Each layer has more detail than the one above it.

• Top Layers: Sparse graphs with long-range links. These are used for coarse navigation to quickly "zoom in" to the target neighborhood.
• Bottom Layer (Layer 0): A dense graph containing all vectors. This is used for fine-grained local search.

This hierarchical structure is analogous to a skip list (a data structure that uses multiple layers of linked lists to allow fast search by skipping over intermediate nodes), but it's generalized for graphs.

In the figure, Layer 2 has only a few nodes with long-range links, Layer 1 holds more nodes for regional refinement, and Layer 0 contains every node in a dense local graph. The parameters M, ef_search, and Layer 0 density (often 2M) control the recall-latency trade-off.

A worked example: tracing one insertion

To see how the layers work in practice, imagine you are building an HNSW index with just 8 vectors. The graph already has 7 vectors arranged across three layers. You now insert vector 8.

1. Sample a level. A random process decides that vector 8 will live on Layers 0 and 1 (but not Layer 2).
2. Zoom in. The entry point is on Layer 2. You greedily walk Layer 2 to find the node closest to vector 8, then drop to Layer 1.
3. Connect on Layer 1. On Layer 1, you run a beam search with ef_construction candidates, pick the best neighbors (up to M), and add bidirectional edges. You also check if any existing neighbor now has too many edges and prune if needed.
4. Drop to Layer 0. You repeat the connection step on Layer 0, but this time you allow up to 2M neighbors because the base layer is denser.
5. Update entry point. If vector 8 had been assigned to Layer 2 or 3, it would become the new entry point because it's now the highest node in the graph.

This incremental construction is why HNSW doesn't need a training phase. Every new vector is wired into the existing graph using local search.

Insert algorithm

The code below is simplified educational pseudocode. The key steps are: sample a level, zoom in through upper layers, connect on each layer, and update the entry point if the new node is taller than the current graph.

Search algorithm

Search mirrors insertion in reverse. The algorithm starts at the sparse top layers for fast coarse routing, then runs a bounded best-first search at layer 0. That last step isn't exhaustive over the full dataset. It only explores a candidate set of size ef_search, which is why raising ef_search improves recall at the cost of more work. On good graphs, search often behaves close to logarithmic, but HNSW doesn't provide a hard worst-case logarithmic guarantee.

If you set ef_search = 5 but ask for k = 10, most implementations enforce ef_search >= k because you need at least k candidates to return k results. The real risk is subtler: if ef_search is only slightly larger than k, you might miss better neighbors outside the explored candidate set. That's the recall-latency trade-off in action.

Common mistake: Setting ef_search from intuition rather than an evaluation curve. A small beam can miss true neighbors; an unnecessarily large beam spends latency without a useful recall gain. Measure ef_search values against exact top-k results on representative queries.

Key parameters

Tuning HNSW requires balancing the quality of the graph (which impacts recall) against the memory consumption and indexing speed. The most critical parameters control the number of edges and the beam width used during the graph traversal.

ef_search is a query-time knob. You can trade latency for recall dynamically without rebuilding the index.

IVF (Inverted File Index)

While HNSW is graph-based, IVF is a partition-based algorithm. It divides the vector space into distinct regions called Voronoi cells, where every point is closer to one centroid than to any other centroid. During search, the algorithm only looks inside a small subset of those cells.

Core concept: the warehouse zone map

The easiest way to think about IVF is a warehouse zone map. Instead of checking every bin in the building, you find the zone whose centroid is closest to the query and only search those bins. If the item might be in a neighboring zone, you check a few extra zones to protect recall.

The process is broken down into three phases:

1. Train: Run K-means clustering on a representative sample of your vectors to identify a set of $C$ cluster centers, known as centroids. In Faiss terminology, this count is usually called nlist.
2. Index: During ingestion, assign each vector to its nearest centroid. That places the vector into one inverted list.
3. Search: When a query vector arrives, first score the centroids, keep the closest nprobe lists, then do exact distance calculations only inside those selected lists.

A worked example: counting comparisons

Suppose you have 1 million embeddings with 128 dimensions. Here's how the operation count breaks down for brute force versus IVF.

Brute force

• Distance computations per query: $1{,}000{,}000$

IVF with nlist = 1,024 and nprobe = 5

• Centroid scoring: $1{,}024$ distance computations
• Average vectors per list: $1{,}000{,}000 / 1{,}024 \approx 977$
• Exact scans inside probed lists: $5 \times 977 \approx 4{,}885$
• Total: roughly $5{,}909$ distance computations

That's about a 170x reduction in distance computations. The actual speedup in a real system is smaller because of overhead, but the principle is clear: IVF avoids scanning most of the database.

Implementation with Faiss

Faiss is a widely used implementation of IVF-style ANN indexing and documents the IndexIVFFlat behavior used below.^[3] The example builds an IVF index, trains its coarse quantizer, assigns vectors to cells, and searches the selected lists.

Recall vs nprobe: The nprobe parameter is the most important knob for tuning an IVF index in production. It controls how many inverted lists are visited during search. If the inverted lists were perfectly balanced, the scanned fraction would be roughly nprobe / nlist. Real systems deviate from that because list sizes are uneven, but the intuition is still useful: more probes mean higher recall and more work.

Distance metrics

The choice of distance metric affects both training and search. Faiss supports L2 and inner product directly across its main ANN indexes, and cosine similarity is usually implemented by normalizing vectors and then using inner product search.

L2 distance is the standard Euclidean objective. It's a good fit when vector magnitude carries signal or when your model was trained with an L2-style loss.

Inner product (IP) is the right objective for maximum inner product search. Query norm doesn't affect ranking, but database vector norms do, so large-norm items can dominate if that's how your embeddings behave.

Cosine similarity ignores magnitude and keeps only direction. In practice, you normalize both database vectors and query vectors, then use inner product search. On normalized vectors, L2 and inner product give equivalent rankings because $||x-y||^2 = 2 - 2\langle x, y \rangle$.

Metric choice changes the geometry seen by the coarse quantizer. If you switch an IVF system from raw L2 search to cosine search, retrain the centroids on normalized vectors rather than reusing the old clustering.

HNSW vs IVF

The biggest operational difference is that IVF requires a training step on representative data before indexing. If your vector distribution drifts over time, stale coarse centroids can unbalance lists or lower recall. HNSW doesn't have that centroid-training dependency, but commonly pays with more memory and slower construction.

Product Quantization (PQ)

For billion-scale datasets, storing full float32 vectors in RAM is usually impractical on a single RAM-resident node.

$10^9 \text{ vectors} \times 768 \text{ dims} \times 4 \text{ bytes} \approx 3 \text{ TB RAM}$

This calculation shows that one billion vectors, each with 768 float32 dimensions (4 bytes each), requires about 3 TB just for raw vector storage. That's before index overhead, operating-system buffers, or any other application memory.

Product Quantization (PQ) compresses vectors by breaking them into smaller chunks and quantizing those chunks independently.^[4] Combined with IVF, PQ is one established way to make billion-point memory budgets tractable; whether a deployment also needs sharding depends on code size, metadata, throughput, and availability requirements.

The algorithm

Product Quantization operates by dividing the high-dimensional space into several lower-dimensional subspaces and quantizing each subspace independently. This avoids the "curse of dimensionality" that makes standard K-Means clustering computationally infeasible for very large vectors.

The compression process follows three distinct steps:

1. Split: Divide the original $d$-dimensional vector into $m$ smaller sub-vectors, each having a dimension of $d^* = d/m$. For instance, a 768-dimension vector split into 96 sub-vectors would yield sub-vectors of dimension 8.
2. Cluster: For each of the $m$ independent subspaces, run K-Means clustering over your training data to find a set of centroids (often $k=256$). This collection of centroids for a given subspace is called its "codebook".
3. Encode: For every vector in your database, map each of its sub-vectors to the nearest centroid in the corresponding codebook. Replace the actual sub-vector values with the ID of that centroid.

In an IVF-PQ system, those PQ codes are usually built on the residual vector after subtracting the assigned coarse centroid, not on the raw vector itself.^[3] Quantizing the smaller residual usually gives better accuracy for the same code size.

By using $k=256$ centroids, an ID requires just 1 byte of storage (since $2^8 = 256$). A 768-dim float vector (3072 bytes) compressed with $m=96$ becomes an array of 96 single-byte IDs, taking up exactly 96 bytes. That achieves a massive 32x compression ratio, enabling billion-scale search on reasonable hardware.

OPQ: rotating before you split

Plain PQ has a weakness: it splits dimensions into fixed contiguous chunks. If the variance in your embeddings is unevenly spread across dimensions, some subspaces carry most of the signal while others are nearly constant, and the per-chunk codebooks waste their 256 centroids on the wrong directions. Optimized Product Quantization (OPQ) addresses this by learning an orthogonal rotation matrix $R$ and applying it before the split so the quantizer can distribute useful variation across chunks.^[5] An orthogonal rotation preserves L2 distances, so it costs one matrix multiply per query but loses no geometric information before quantization.

In Faiss you can request OPQ with the factory string OPQ96,IVF4096,PQ96: the OPQ96 prefix trains the rotation, then IVF and PQ run on the rotated vectors. OPQ is a candidate to benchmark at the same code size; its recall benefit depends on the embedding distribution and training sample.

Asymmetric distance computation (ADC)

We don't decompress vectors to search them. Instead, we calculate the distance from the uncompressed query to the compressed database vectors using lookup tables.

Mathematically, the squared Euclidean distance between a query vector $q$ and a quantized vector $y$ (approximated by codebook centroids $C(y)$) is:

$d(q, y)^2 \approx d(q, C(y))^2 = \sum_{j=1}^{m} d(q_j, C_j(y_j))^2$

Where $q_j$ is the $j$-th sub-vector of the query, and $C_j(y_j)$ is the centroid for the $j$-th sub-vector of $y$. This is the core of Asymmetric Distance Computation (ADC). Instead of reconstructing an approximate full vector and computing distance against it, we precompute the distance from each query sub-vector to all centroids in each codebook. The query-time distance for any stored vector then becomes a simple table lookup and sum. The implementation below demonstrates this. It takes a query vector and pre-computed PQ codebooks, creates the lookup tables, and returns the top k nearest neighbors by partial distance lookup alone.

Filtered search

Real queries almost never search the whole corpus. A support tool asks for "tickets like this one, but only from the last 30 days and only for the EU region." That metadata predicate is a filter, and where you apply it changes both recall and latency. There are three strategies, and the choice is one of the most common production interview questions.

Filter then exact scan first finds rows matching the predicate, then scores only that subset. If the allowed set is small, this is exact and can be efficient. It gets costly as the allowed set grows.

Post-filtering (search, then filter) runs normal ANN search for some candidate count, then discards anything that fails the predicate. This keeps the graph intact, but it has an overfiltering failure mode: if the predicate is selective (say only 1% of vectors match), the initial ANN candidate buffer may contain zero matches, so you return fewer than k results or none at all. Some engines address this by expanding the scan iteratively until enough matching results appear or a budget is exhausted.^[1]

Allow-list graph traversal is another useful option. The graph walk only counts allowed nodes toward the result set while it can still traverse disallowed nodes for connectivity. Weaviate documents this pre-filtered HNSW behavior, a sweeping strategy, and an ACORN-inspired option; its documentation recommends ACORN particularly when restrictive filters correlate poorly with the vector neighborhood.^[6][7] This isn't a universal winner: a tiny allowed set can make a flat scan cheaper, while broader or poorly correlated filters can benefit from graph traversal.

How products package these ideas

Vendor defaults drift faster than the underlying concepts, so skip memorizing a leaderboard table. In interviews and production reviews, ask four concrete questions instead:

1. Which ANN families are exposed: HNSW, IVF, PQ, disk-backed graphs, or a managed black box?
2. How does filtered search work: before search, after search, or during traversal?
3. Where does the index body live: RAM, SSD, or object storage?
4. Which compression knobs are available, and what recall do they cost?

That framing travels better than product trivia:

• Postgres-style extensions usually expose a small set of explicit index types such as HNSW or IVFFlat inside SQL workflows.
• General-purpose vector databases often center HNSW for RAM-resident search, then layer in quantization and filter-aware traversal.
• Faiss and Faiss-derived stacks expose broad ANN menus, which is powerful but shifts more tuning responsibility onto the engineer.
• Storage-first systems move more bytes out of RAM and onto SSD or object storage, which improves cost efficiency but makes IO behavior part of your latency budget.

The pattern that stays stable is conceptual, not vendor-specific: HNSW is a candidate when you want strong in-memory recall without centroid training, while IVF and PQ are candidates when scan fraction or bytes per vector become central constraints. Choose from measured recall, tail latency, build/update cost, and memory on your workload.

Scaling to billions

When data exceeds standard RAM limits, you usually need one of two moves: compress the vectors more aggressively, or move most of the index body out of RAM. A global logistics platform tracking billions of shipment embeddings faces this exact choice: either compress each route vector with PQ or keep a sparse graph in memory and store the full index on fast SSD.

1. Hybrid approaches (IVF-PQ)

Combining IVF (to reduce search scope) and PQ (to compress vectors) is a common billion-scale recipe.

• Index: IndexIVFPQ in Faiss.
• Memory math: In Faiss, IndexIVFPQ stores about ceil(m_pq * nbits / 8) + 8 bytes per vector for the PQ code plus the vector id, where m_pq is the number of PQ sub-vectors/codebooks. A 32-byte code therefore lands near 40 bytes per vector, so 1B vectors is roughly 40 GB before centroids and other overhead.
• Trade-off: Much lower memory than raw float32 vectors, but more recall loss and more tuning knobs than HNSW.

2. Disk-based indexes (DiskANN)

Microsoft's DiskANN^[8] shows that you can serve a billion-point graph index from a single node by keeping a compact in-memory structure and placing the large index body on SSD.

• Mechanism: The system is graph-based, but optimized around SSD access patterns rather than assuming every edge traversal hits RAM.
• IO-aware design: Search quality now depends on storage layout and read amplification, not just graph degree and beam width.
• Performance: The Microsoft Research page for the NeurIPS 2019 paper reports >5000 queries per second, <3 ms mean latency, and 95%+ 1-recall@1 on SIFT1B on a 16-core machine with 64 GB RAM plus SSD. Treat those numbers as benchmark-specific, not a universal promise for every embedding workload.

3. Distributed sharding

If single-node vertical scaling fails, we shard horizontally using a Scatter-Gather approach.

• Strategy: "Scatter-Gather" architecture. Split 1B vectors into $S$ shards (e.g., 10 shards of 100M each).
• Query: The gateway node broadcasts the query to all $S$ nodes (Scatter).
• Merge: Each node returns its top-$k$. The gateway merges these lists to find the global top-$k$ (Gather).
• Bottlenecks: Under full fan-out, throughput doesn't scale linearly due to coordination overhead, and tail latency (P99) is exposed to the slowest shard.

Mastery check

Common pitfalls

These are the symptoms, causes, and fixes we see most often in production vector search.

Symptom: recall drops after a data shift Cause: You trained an IVF index on English product descriptions, then started adding Spanish descriptions. The old centroids no longer represent the new data distribution, so queries land in the wrong Voronoi cells. Fix: Retrain centroids on a representative sample that includes the new data. Monitor recall@k on a held-out validation set and trigger retraining when it drifts below a threshold.

Symptom: HNSW index causes OOM crashes Cause: An uncompressed HNSW index stores graph adjacency data on top of raw vectors. Edge representation, layer distribution, ids, allocator overhead, and implementation choices all affect the real total. Fix: Measure bytes per indexed vector in the chosen engine at production-like M and dimension settings, then reserve headroom for builds, queries, operating-system buffers, and metadata. If RAM is tight, evaluate compression or an IVF-PQ design against recall requirements.

Symptom: search is fast but returns poor matches Cause: The ANN budget is too small for the index family you chose. For IVF that often means nprobe is too low, so you inspect too few lists. For HNSW it often means ef_search is barely above k, so the beam never explores enough candidates. Fix: Diagnose by index family, not with one generic knob story. Measure recall@k on a labeled set, then raise nprobe for IVF or ef_search for HNSW until recall meets the product target.

Symptom: switching from L2 to cosine breaks IVF results Cause: You changed the distance metric at search time but didn't retrain the coarse quantizer on normalized vectors. The centroids were learned in L2 geometry, so they misplace vectors after normalization. Fix: Normalize training vectors before calling index.train(), and normalize both database and query vectors before index.add() and index.search().

Follow-up questions

Your corpus updates constantly and you need online inserts. What HNSW maintenance caveat matters most?

HNSW handles inserts naturally because a new node can be attached incrementally. Deletes are harder because removing nodes can damage graph connectivity. Many systems therefore use tombstones and periodic rebuilds or compaction instead of pretending deletion is free.

You have 10M vectors and only 16 GB RAM. Why might IVF-PQ beat HNSW even if HNSW usually has stronger recall-latency behavior in RAM?

Because memory is the hard constraint. IVF-PQ compresses vectors aggressively enough to stay resident where HNSW may spend too much RAM on raw vectors plus graph edges. HNSW is often better when the working set already fits; IVF-PQ becomes the practical choice when bytes per vector decide feasibility.

A teammate wants to reconstruct every PQ vector before scoring it because it “sounds simpler.” Why is that the wrong instinct?

Because ADC is the whole trick that keeps PQ search efficient. Query-time work should be lookup-table additions, not full-vector reconstruction for every candidate. Reconstructing every vector throws away much of the compute benefit of compressed search.

Distributed search added more shards, but p99 got worse. What probably happened?

You shrank local indexes but increased fan-out and made the request wait on more shard responses. Scatter-gather throughput can rise while p99 still gets worse if one slow shard or merge overhead dominates.

Evaluation rubric

By the end, you should be able to defend these points without relying on metadata or hidden notes:

1. HNSW search starts at sparse upper layers, uses greedy routing there, then uses a bounded best-first search at layer 0.
2. M, ef_construction, and ef_search move recall, latency, build time, and memory in different directions.
3. IVF reduces search work by partitioning vectors into nlist inverted lists and probing only nprobe of them.
4. Product Quantization reduces memory by splitting vectors into subspaces and storing centroid IDs instead of float32 values.
5. IVF-PQ trades memory for quantization error, while HNSW trades memory and build time for strong in-RAM recall and latency.

What you can do now

By this point in the article, you should be able to:

1. Estimate flat-search work. Given $N$ vectors and $d$ dimensions, calculate raw memory and scored components per query, then state what must be benchmarked before making a latency claim.
2. Trace HNSW search. Explain why the algorithm starts at the top layer, how greedy descent works, and why ef_search controls the recall-latency trade-off.
3. Count IVF comparisons. Given nlist and nprobe, estimate the fraction of the database that gets scanned.
4. Choose an index family. State whether HNSW or IVF-PQ is a better fit when the constraint is "16 GB RAM for 10M vectors" versus "sub-50 ms latency at 99% recall."
5. Spot common misconfigurations. Recognize stale centroids, underestimating graph memory, and metric mismatches from their symptoms.

Key takeaways

Evaluate HNSW when you can afford RAM and need low-latency high-recall retrieval. Evaluate IVF-PQ when raw vector storage becomes the bottleneck. Consider DiskANN-style systems when a graph index remains attractive but the index body no longer fits in memory. In each case, release from a recall-and-latency curve measured on representative queries.