Vector DB Internals: HNSW & IVF

Exact vector scoring and production RAG established how retrieval feeds grounded generation. Now open the index itself: before an agent or RAG pipeline can reason over documents, the system has to find relevant candidate chunks quickly enough for an interactive product.

Finding one incident runbook in an archive with millions of traces, alerts, and postmortems is hard when you have only a vague description of the failure. Embeddings turn the query and documents into vectors so the system can compare meaning, but checking every stored vector is expensive. You'll see how Hierarchical Navigable Small World (HNSW) graphs and inverted file (IVF) partitions avoid most of that scan, what Product Quantization (PQ) compresses, and how to choose a recall-latency-memory operating point.

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 $<span data-glossary="big-o-notation">O(N \cdot d)</span>$ complexity. That notation means the work grows in direct proportion to both the number of vectors and the number of dimensions.

Make that concrete with 100 million trace-summary 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]Reference 1pgvectorhttps://github.com/pgvector/pgvector}

Why is unfiltered exact vector search difficult at 100 million vectors?

Answer

The system stores hundreds of GB of raw vectors and scores every vector for each unfiltered query. Both storage and query work grow with corpus size, so teams commonly evaluate ANN indexes while retaining exact search as their recall baseline.

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 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.

Recall gate: 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]Reference 2Efficient and Robust Approximate Nearest Neighbor Using Hierarchical Navigable Small World Graphs.https://arxiv.org/abs/1603.09320} 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 narrow a search. Map zoom is a useful analogy: 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 the Layer 0 adjacency cap (often 2M) control the recall-latency trade-off.

A worked example: tracing one insertion

To see how the layers work in practice, imagine you're 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 again select up to M neighbors for the new node. Because connections are bidirectional, an existing Layer 0 node can commonly retain up to 2M total connections before pruning. That larger adjacency cap makes the base layer denser.
5. Update entry point. If vector 8 had been assigned above the graph's current maximum level, it would become the new entry point. Landing on an existing top layer isn't enough.

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

This example 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 keeps up to ef_search best result candidates while the walk may visit more nodes, which is why raising ef_search often 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 parameters that matter most control the number of edges and the beam width used during 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 centroid shard map

The easiest way to think about IVF is a centroid shard map. Instead of checking every vector in the collection, you find the shard whose centroid is closest to the query and only search that list. If a neighbor might sit across a boundary, you probe a few extra lists 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 score candidates only inside those selected lists. IVF-Flat calculates exact distances there; IVF-PQ can score compressed codes with ADC lookup tables.

A worked example: counting comparisons

Suppose you have 1 million embeddings with 128 dimensions. Compare brute force against IVF with nlist = 1,024 and nprobe = 5:

• Brute force: $1{,}000{,}000$ distance computations per query.
• IVF centroid scoring: $1{,}024$ distance computations.
• IVF list scans: average list size $1{,}000{,}000 / 1{,}024 = 976.5625$, so $5 \times 976.5625 \approx 4{,}883$ vector scores inside probed lists.
• IVF total: roughly $5{,}907$ distance computations.

That's about a 169x 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]Reference 3Billion-scale similarity search with GPUs.https://arxiv.org/abs/1702.08734} 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 direction still holds: more probes mean higher recall and more work.

Why does increasing nprobe usually improve IVF recall while increasing query work?

Answer

IVF scores vectors only inside selected lists. Probing more lists gives the search more chances to inspect a true neighbor that landed outside the closest centroid's cell, but each added list contributes more candidate vectors to score.

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 dot-product ranking. 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}$

One billion vectors at 768 float32 dimensions need about 3 TB of raw vector storage alone. Add index overhead, operating-system buffers, and application memory on top of that.

You have 1B vectors, raw float32 storage needs terabytes of RAM, and one node only has 128 GB. What must product quantization buy you first before anything else matters?

Answer

It must buy memory reduction. By replacing sub-vectors with compact centroid IDs, PQ lets far more vectors stay resident, which is what makes any fast single-node search plan feasible in the first place.

Product Quantization (PQ) compresses vectors by breaking them into smaller chunks and quantizing those chunks independently.^{[4]Reference 4Product Quantization for Nearest Neighbor Search.https://dblp.org/rec/journals/pami/JegouDS11} 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 divides the high-dimensional space into several lower-dimensional subspaces and quantizes each subspace independently. A single full-vector codebook would need an impractically large number of centroids to represent many combinations of values. PQ factorizes that codebook into smaller pieces that are cheaper to train and store.

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]Reference 3Billion-scale similarity search with GPUs.https://arxiv.org/abs/1702.08734} 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's 32x compression for the vector code before ids, codebooks, centroids, and other index overhead.

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]Reference 5Optimized Product Quantizationhttps://openaccess.thecvf.com/content_cvpr_2013/html/Ge_Optimized_Product_Quantization_2013_CVPR_paper.html} 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, you 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 table lookup and sum. The lab below builds those tables once per query, then ranks stored codes by summed partial distances only.

Why does ADC stay practical at large N while reconstructing every approximate vector doesn't?

Answer

ADC computes query-to-centroid distances once, then scores each database vector with cheap table lookups and additions. Reconstructing every approximate vector would reintroduce much more per-vector work at query time.

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. Three strategies are useful to understand.

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]Reference 1pgvectorhttps://github.com/pgvector/pgvector}

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]Reference 6ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Datahttps://arxiv.org/abs/2403.04871[7]Reference 7Filteringhttps://docs.weaviate.io/weaviate/concepts/filtering} 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.

Filter placement is a security boundary as well as a recall knob. Trusted filter-then-exact or in-traversal allow-lists keep unauthorized vectors out of the application path; app-side post-filtering after unrestricted ANN can leak privileged text through logs, traces, caches, or partial failures even when the final answer list is scrubbed. RAG Security & Access Control treats that trusted-plane contract in depth.

Why can a selective filter make post-filtering return fewer than k results?

Answer

Post-filtering ranks the top candidates first, then drops non-matches. If only a tiny fraction of vectors satisfy the predicate, the ANN candidate buffer may contain few or no matches, so the final list comes up short. Over-fetching or in-traversal filtering avoids this.

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 index whose internals aren't exposed?
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 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 large incident-search platform tracking billions of trace-summary embeddings faces this exact choice: either compress each incident 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]Reference 8DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node.https://proceedings.neurips.cc/paper/2019/hash/09853c7fb1d3f8ee67a61b6bf4a7f8e6-Abstract.html} 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 graph degree and beam width alone.
• Performance: The NeurIPS 2019 paper abstract 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, you can shard horizontally with scatter-gather.

• Strategy: 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.

When vector indexes break

Index family trade-offs

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.

Release from a measured index frontier

Freeze the embedding model, distance normalization, representative query set, filters, and exact top-$k$ baseline. Sweep each candidate's search budget, then plot recall against p95 latency and bytes per vector under target concurrency. Include build time, update/delete behavior, and filtered-search completeness in a release scorecard; choose the cheapest point that clears every constraint, not the index with the best isolated benchmark.