Vector Search Fundamentals: Embeddings, ANN and Recall

A vector database stores fixed length numeric arrays produced by an embedding model and answers the question “which stored vectors are closest to this one”. Everything else in the system exists to make that question fast without making the answer too wrong.

Exact search sets the reference point

Brute force search compares the query against every stored vector. It is exact by definition and its cost grows linearly with the number of vectors and with dimensionality. For small collections this is fine and is often faster than people expect, because the operation is a dense matrix multiply that hardware handles well.

Approximate nearest neighbor indexes exist because linear scan stops being viable as collections grow. Every ANN index accepts a chance of missing some true nearest neighbors in exchange for examining a small fraction of the data. That chance is the central tradeoff, and it is tunable rather than fixed.

Distance metric has to match the model

Cosine similarity, inner product and Euclidean distance are not interchangeable. The right choice is whatever the embedding model was trained against. Using cosine on vectors that were not normalized, or inner product where the model expects cosine, produces results that look plausible and rank badly. Normalization, where required, must be applied consistently at both index time and query time.

Graph based indexes

A navigable small world graph connects each vector to a set of neighbors and searches by walking the graph greedily toward the query, keeping a candidate list along the way. Hierarchical variants add sparse upper layers that let the search jump across the space before descending into a dense bottom layer.

Two knobs dominate. Build time controls how many neighbors each node keeps and how hard the builder works to find good ones, which sets index memory and build cost. Query time controls how large the candidate list is during the walk. Increasing it raises recall and raises latency, and it can be changed per query without rebuilding. That separation is useful in practice: you can serve cheap queries and expensive queries from the same index.

Graph indexes generally live in memory and handle deletions poorly. Removals are usually tombstoned, degrading the graph until a compaction or rebuild happens.

The neighbour count also has a direct memory cost that does not depend on how wide the vectors are, which is why it should be treated as a capacity decision before it is treated as a recall decision. Vector database memory sizing works through the arithmetic, and the HNSW index sizer applies it to a given corpus.

Cluster based indexes

An inverted file index partitions vectors into clusters around learned centroids. A query compares against the centroids, picks some number of nearest clusters and searches only inside those. Probing more clusters raises recall and cost. These indexes train on a sample of the data, so a badly drifted collection needs retraining, and they degrade when the data distribution changes substantially after the centroids were learned.

Choosing between the two families comes down to memory, build cost and how often the corpus changes rather than to a recall ceiling, since both can be tuned to the same recall. HNSW vs IVF: vector index tradeoffs compared sets them side by side.

Quantization trades memory for accuracy

Storing full precision vectors is often the largest cost in the system. Scalar quantization reduces the precision of each dimension. Product quantization splits the vector into subspaces and replaces each with a codebook symbol, which compresses far harder and loses more. Both are lossy, and both are usually paired with a rescoring pass: retrieve a larger candidate set using compressed vectors, then re rank the top candidates against full precision copies.

Measure recall against ground truth

Latency numbers mean nothing without the recall they were achieved at. The only honest measurement is to compute exact nearest neighbors for a query sample with brute force on the same data, then report what fraction of them the index returned. Comparing two configurations at different recall levels is not a comparison.

Filtering is where designs break

Applying a metadata filter after retrieval can return fewer results than requested, because the filter removes candidates the index already committed to. Applying it during the search keeps the result count intact but constrains graph traversal and can slow the query badly when the filter is highly selective. Know which behavior your engine implements before relying on filtered search.

Where to go next

• Sizing an index before building it: vector database memory sizing, plus the HNSW index sizer for a specific corpus.
• Picking between graph and cluster indexes: HNSW vs IVF: vector index tradeoffs compared.
• An index that is already returning the wrong neighbours: low vector search recall: causes and fixes.