Vector DB Internals: HNSW & IVF

A support assistant has to find one rollback runbook in a corpus of 100 million trace summaries. Checking every stored representation can blow tail latency; skipping most candidates can miss the runbook an operator needs. The production question isn't "which index is fastest?" It's "how much work can we skip while still recovering the right neighbors?"

Use that query to make the trade-off visible. An embedding turns the query and each runbook into a vector, so related meaning appears as nearby geometry. Exact search checks every vector; Hierarchical Navigable Small World (HNSW) walks graph links; inverted file (IVF) opens selected partitions; and product quantization (PQ) compresses stored vectors. The release decision comes from recovered neighbors, latency, memory, and update behavior measured together.

The brute-force problem

Start with exact search, also called flat search. Given a query vector $q$, it computes a distance to every stored vector and returns the $k$ nearest neighbors; k-NN is shorthand for $k$-nearest-neighbor search.

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.

Use the corpus as a concrete baseline: 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 a service-level agreement (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). That budget leaves little room for index and application state on many single-node deployments. Approximate nearest-neighbor (ANN) search reduces 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.

Recall@k answers one question: of the exact top-k nearest neighbors, how many did the 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)

With exact search held as ground truth, start with HNSW when the working set can stay in memory. 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.

Layers skip, then search locally

Suppose the rollback query enters at a node that is far from its best match. A useful next hop should move closer to the query, but scanning every neighbor at every node would erase the speedup. HNSW makes that local decision on a sparse upper graph first, then repeats it on a denser neighborhood.

That structure is a multi-layer proximity graph. Upper layers hold long-range links; layer 0 contains every vector and does the local search.^{[2]Reference 2Efficient and Robust Approximate Nearest Neighbor Using Hierarchical Navigable Small World Graphs.https://arxiv.org/abs/1603.09320} M sets how many neighbors a new node keeps, ef_search sets the query beam, and the layer-0 adjacency cap (often 2M) keeps the base layer better connected. The mechanism is graph hops, not a partition map: an upper-layer hop gets search near the right region, and layer 0 spends the larger candidate budget there.

A worked example: tracing one insertion

To see the layers work, insert one new runbook vector into a graph that already has a few nodes.

First, a random process samples the new node's top layer. Most nodes live only on layer 0; a few appear higher, which keeps upper layers sparse.

Next, start at the current entry point and greedily walk each layer above the new node's top layer. Stop when no neighbor is closer, then drop down. Those upper layers locate a useful neighborhood without wiring the new node into distant parts of the graph.

On each layer the new node actually occupies, run a beam search with ef_construction candidates. Keep up to M neighbors, add bidirectional edges, and prune an existing neighbor if its degree is now too large. The layer-0 cap is commonly 2M, so the base layer can offer more local routes than upper layers.

Finally, update the entry point only when the sampled level is above the graph's current maximum. Landing on an existing top layer changes local wiring, not the global starting point.

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

Build a tiny graph, then search it

Insert follows the paper's two phases: greedy descent through layers above the new node's top layer, then a wider ef_construction search while wiring bidirectional edges on the layers the node actually occupies.^{[2]Reference 2Efficient and Robust Approximate Nearest Neighbor Using Hierarchical Navigable Small World Graphs.https://arxiv.org/abs/1603.09320} Neighbor selection here is "keep the nearest M candidates." Production HNSW usually adds a diversity heuristic so the graph doesn't collapse into a clique of near-duplicates.

Level sampling is exponential. sample_level is the random process a real builder uses. The lab then inserts with explicit levels so the wiring stays reproducible. Before running it, predict the distinction: the returned neighbors should match the exact top-2 in this tiny graph, but that result doesn't establish large-scale recall.

The toy returns the exact top-2 because its graph and beam are generous for six vectors. That is a correctness check for the implementation, not a production recall result.

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

M, ef_construction, and ef_search are the knobs that actually move recall, RAM, build time, and latency. Use the table as a starting map, then measure on your queries before copying a default.

M0 (often $2M$) is why layer 0 is denser than the upper layers.^{[2]Reference 2Efficient and Robust Approximate Nearest Neighbor Using Hierarchical Navigable Small World Graphs.https://arxiv.org/abs/1603.09320} At 4 bytes per packed neighbor id, $M=16$ adds 128 bytes of layer-0 ids on top of a 1,536-d float32 vector (6,144 bytes). The embedding still dominates; the memory cliff at LLM sizes is uncompressed vectors, not the graph overlay. Compression (PQ, disk-backed graphs) is what changes the budget.

ef_search is the query-time knob: raise it to spend latency for recall, without rebuilding. The lab below picks the cheapest measured point that clears a recall floor and a p95 budget.

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

Ask the same question as before: where can we avoid work without losing the rollback runbook? If a true neighbor sits just across a partition boundary, opening only the closest partition will miss it. IVF protects against that miss by choosing a few coarse regions rather than one.

Training happens before serving. Run K-means clustering on a representative sample to learn $C$ cluster centers, or centroids. In Faiss terminology, $C$ is usually nlist; those centroids become the coarse map.

Indexing assigns each incoming vector to its nearest centroid and stores its ID in that centroid's inverted list. At query time, score all centroids, keep the closest nprobe lists, then score only their candidates. IVF-Flat uses exact distances inside those lists; IVF-PQ can score compressed codes with asymmetric distance computation (ADC) lookup tables.^{[3]Reference 3Billion-scale similarity search with GPUs.https://arxiv.org/abs/1702.08734}

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 performs $1{,}000{,}000$ distance computations per query.

IVF first scores its $1{,}024$ centroids. With balanced lists, each list averages $1{,}000{,}000 / 1{,}024 = 976.5625$ vectors, so five probes add about $5 \times 976.5625 \approx 4{,}883$ vector scores.

Together, centroid scoring and list scans cost roughly $5{,}907$ distance computations. That's about a 169× reduction in distance computations. Real systems are slower than this model because lists are uneven and each comparison has overhead, but the principle holds: IVF refuses to scan most of the database. nlist = 1,024 is a round teaching number here, not a universal default.

A boundary miss: nprobe = 1 drops a true neighbor

Before running the lab, predict what nprobe = 1 keeps. Query (4.9, 0) is closer to centroid 0, so only list 0 opens. Vector 3 at (5.4, 0) is the true second neighbor, but it lives in list 1 and stays invisible until both lists are probed.

The example uses two hand-set centroids: payments-like vectors near the origin and GPU-like vectors near (10, 0). It isolates the failure mode without hiding it behind clustering noise.

Faiss's IndexIVFFlat is the production form of this loop: train centroids, assign inverted lists, then search with nprobe.^{[3]Reference 3Billion-scale similarity search with GPUs.https://arxiv.org/abs/1702.08734}

nprobe is the main query-time knob. If lists were perfectly balanced, the scanned fraction would be about nprobe / nlist. Real lists 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

Before comparing index families, fix the ranking rule. The same stored vectors can produce a different neighbor order when magnitude matters, so changing the metric changes both search and any IVF centroids trained for it. 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.^{[3]Reference 3Billion-scale similarity search with GPUs.https://arxiv.org/abs/1702.08734}

L2 distance is the standard Euclidean objective. Use it when vector magnitude carries signal or when the model was trained with an L2-style loss.

Inner product (IP) ranks by maximum dot-product. Query norm doesn't affect ranking, but database vector norms do, so large-norm items can dominate if that's how the embeddings behave.

Cosine similarity ignores magnitude and keeps only direction. Normalize both database 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, stale coarse centroids can unbalance lists or lower recall. HNSW doesn't have that centroid-training dependency. At typical LLM embedding sizes the extra graph ids are a small add-on to the same raw vectors IVF-Flat already stores; HNSW's usual extra costs are build time and delete behavior, not a second copy of the corpus.

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 lower-dimensional subspaces and quantizes each one 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.

First split the original $d$-dimensional vector into $m$ sub-vectors of dimension $d^* = d/m$. A 768-dimension vector split into 96 sub-vectors yields chunks of dimension 8.

Then cluster each subspace separately. Run K-means on training data to find a codebook for each chunk, often with $k=256$ centroids. Finally, encode each sub-vector as the ID of its nearest centroid. The full vector becomes $m$ small IDs instead of $d$ floats.

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 32× 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. Their codebooks spend centroids on uninformative directions.

Optimized Product Quantization (OPQ) learns an orthogonal rotation matrix $R$ and applies it before the split, distributing 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 a factory string such as OPQ96,IVF4096,PQ96 (keeps the original dimension) or OPQ96_384,IVF4096,PQ96 (rotates and reduces to 384-d, so each of the 96 chunks is 4-d). 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. For each query sub-vector, calculate its distance to every centroid once and keep those values in a lookup table. A stored code then needs only one lookup per chunk and a sum.

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): the query stays uncompressed while the database uses codes. Instead of reconstructing an approximate full vector and computing distance against it, the query-time distance for any stored vector becomes a table lookup and sum.

In IVF-PQ, Faiss's default is to encode the residual after subtracting the coarse centroid.^{[3]Reference 3Billion-scale similarity search with GPUs.https://arxiv.org/abs/1702.08734} ADC then compares the query residual $(q - c_{\text{list}})$ to those residual codes, so the lookup tables are rebuilt (or selected) per probed list rather than once globally. The lab below shows the simpler non-residual case: one table per subspace, then a sum of lookups.

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

The index can behave well for an unfiltered query and still fail once access rules narrow the candidate set. A support tool asks for "runbooks like this one, but only from the last 30 days and only for the EU region." Before choosing a filter strategy, predict the failure: will the filter shrink work, empty the candidate buffer, or block graph routes needed to reach allowed neighbors? Three strategies make that trade-off concrete.

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. pgvector applies filters after an approximate index scan and can expand with iterative index scans (hnsw.iterative_scan / ivfflat.iterative_scan) until enough matches appear or a budget is exhausted.^{[1]Reference 1pgvectorhttps://github.com/pgvector/pgvector}

Allow-list graph traversal: the walk can still traverse disallowed nodes for connectivity, but only allowed nodes count toward the result set. Weaviate's pre-filtered HNSW does this. Since v1.34, ACORN is the default filter strategy; a sweeping walk remains available. ACORN is most useful when a restrictive filter correlates poorly with the vector neighborhood, so the graph region nearest the query is mostly disallowed.^{[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} A tiny allowed set can still make a flat scan cheaper.

Those three placements:

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.

Four questions a vendor page can't answer

When you evaluate a vector database, ask four questions that survive vendor churn. Each one connects an index choice to an operating constraint:

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. As a working heuristic, Postgres-style extensions 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. That makes filtered-search behavior part of the index evaluation, not a later integration detail.

Faiss and Faiss-derived stacks expose broad ANN menus, which shifts more tuning responsibility onto the engineer. The freedom is useful when you can own benchmarking and deployment decisions.

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.

These questions lead to a workload decision, not a vendor slogan: 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 the rollback corpus grows past RAM, two budgets compete: compress the vectors, or move most of the index body to storage. A billion-vector incident-search platform might compress each trace-summary vector with PQ, keep a sparse graph in memory, or compare both against a sharded design. The right branch depends on bytes, recall, and tail latency together.

1. Hybrid approaches (IVF-PQ)

Combining IVF (to reduce search scope) and PQ (to compress vectors) targets both budgets. 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. The savings buy capacity, but quantization error and extra knobs can cost recall compared with 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} keeps a compact in-memory structure and places the large graph body on SSD. The graph is still navigational, but its layout is optimized for storage access rather than assuming every edge traversal hits RAM. Search quality therefore depends on read amplification and layout as well as graph degree and beam width.

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. Those are benchmark-specific measurements, not a universal promise for every embedding workload.

3. Distributed sharding

If neither compression nor storage fits the single-node budget, shard horizontally with scatter-gather.

Split 1B vectors into $S$ shards, such as 10 shards of 100M each. A gateway broadcasts the query to all $S$ nodes (scatter); each node returns its local top-$k$; then the gateway merges those packets into the global top-$k$ (gather).

Full fan-out cuts local work but exposes the request to coordination overhead and the slowest shard. Throughput doesn't scale linearly, and tail latency (P99) is a property of the whole scatter-gather path, not any one shard.

When vector indexes break

Most failures announce themselves as one of three symptoms: recall drops after the data or metric changes, results underfill after filtering or deletes, or p99 rises while local work looks healthy. Use the table to connect each symptom to the budget that moved and the evidence needed before changing a knob.

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. That fixes what "correct" means while you compare candidates.

Then sweep each candidate's search budget and plot recall against p95 latency and bytes per vector under target concurrency. Add build time, update/delete behavior, and filtered-search completeness to the release scorecard. Choose the cheapest point that clears every constraint, not the index with the best isolated benchmark.