1Vector Search & HNSW 2Chunking & Reranking for RAG 3Model Calibration 4Data Drift & Model Monitoring

Lensa ML

Vector Search & HNSW

Step 1 of 6: Nearest Neighbours

Brute force compares the query with every vector

Vectors in the index (N)120

Neighbours returned (k)5

Distances computed

120

Multiply-adds at d = 768

92.2K

Distance to neighbour 5

0.097

Doubling N doubles the work: 120 vectors means 120 distance computations per query, each costing d multiply-adds. The 5 green points are the exact answer.

Drag Vectors in the index (N) from 20 to 200 and Neighbours returned (k) from 1 to 10, or tap the plot to move the query. This is the same k-nearest-neighbours search a kNN classifier runs, applied to embeddings. Exact search costs O(N · d) per query, and a full sort is unnecessary: a heap of size k keeps the running best in O(N log k). On a GPU, brute force over a few million vectors is often fast enough, and exact search stays the baseline every approximate index is measured against.

Step 2 of 6: Cosine, Dot, L2

Three scores, and when they disagree

Query direction60°

Query length1.0

Document vectors

Top by cosine

B

Top by dot

C

Top by L2

B

Ranks that differ

6

Cosine picks B on angle alone. Dot product rewards length and picks C, while L2 agrees with cosine. 6 rank slots differ from cosine.

Drag Query direction and Query length, then switch Document vectors between Raw lengths and Normalized. Cosine similarity is a · b / (‖a‖ ‖b‖), so it ignores length. On unit vectors, ‖a − b‖² = 2 − 2 · cos, which is why many systems normalize once at indexing time and then run a fast inner-product search. Match the metric to the embedding model: a model trained with a cosine objective expects cosine, while dot-product retrievers such as DPR can store useful signal in vector length.

Step 3 of 6: Approximate Search

Trading a little recall for a lot of speed

Search width (ef)32

Recall@10

0.706

Latency

0.53 ms

Faster than brute force

56×

ef = 32 finds 7 of the 10 exact neighbours in 0.53 ms, about 56 times faster than scanning all 1M vectors. The curve is illustrative, but its shape is typical.

Drag Search width (ef) from 1 to 512 and follow the dot along the curve. An approximate index gives up the guarantee of the exact answer in exchange for speed. Public benchmarks such as ann-benchmarks plot this same curve, queries per second against recall, for each library and parameter setting. Production systems often target recall@10 between 0.9 and 0.99, because a retriever that feeds a reranker or an LLM rarely needs the perfect top 10. The 30 ms brute-force figure and the curve are illustrative, not measured.

Step 4 of 6: The HNSW Graph

Sparse long links on top, dense local links below

Links per node (M)3

Layer

Nodes on this layer

80

Links on this layer

163

Average links per node

4.1

Layers

5

Layer 0 holds all 80 points, each linked to up to 6 close neighbours. These short links make the final, local part of a search accurate.

Drag Links per node (M) from 2 to 8 and click through the Layer buttons. Each node draws its top layer once, as floor(−ln(u) · m_L) with u uniform and m_L = 1/ln M, so it reaches layer l with probability M^−l. Links are chosen with the paper's heuristic: a candidate is kept only if it is closer to the new node than to any neighbour already kept, which preserves links between clusters. The layered design generalizes the skip list to proximity graphs, and the paper suggests M between 5 and 48.

Step 5 of 6: Greedy Search

From the entry point down to layer 0

Query

Search width (ef)5

Layer

4

Distances computed

1

Brute force

80

Recall@5 (final)

2/5

On layer 4 the search moves to whichever neighbour is closer to the query and stops when none is. That node becomes the starting point one layer down.

Pick Query A, B, or C, set Search width (ef) between 5 and 40, then press Play or Step. Query A at ef = 5 shows the failure mode: the beam settles among points near the entry path, and three true neighbours are never reached. Search cost grows roughly with log N, because each upper layer cuts the remaining distance to the target. Insertion runs the same search with a construction width, efConstruction (16 here), so building the index costs far more than a single query.

Step 6 of 6: At Scale

IVF lists, product quantization, memory

IVF lists probed (nprobe)1 of 8

Vectors stored (N)100M

Dimension (d)768

PQ code bytes (m)

Vectors scanned (toy IVF)

18 of 120

Recall@5 (toy IVF)

3/5

float32 memory

307.2 GB

PQ memory

6.4 GB

Probing 1 of 8 lists scans 18 points but misses 2 true neighbours that sit just across a list boundary. Raw vectors at d = 768 take 307.2 GB; 64-byte PQ codes shrink that 48× to 6.4 GB, at some cost in distance accuracy.

Drag IVF lists probed, then set Vectors stored, Dimension, and PQ code bytes. IVF, the inverted file index, runs k-means once and assigns every vector to its nearest centroid, and a query scans only the nprobe closest lists. Product quantization (Jégou et al., 2011) splits each vector into m sub-vectors and replaces each with the index of one of 256 learned centroids, one byte per sub-vector. The codebooks add only 256 × d × 4 bytes. FAISS combines both as IVF-PQ, and vector databases add storage, filtering, and updates around indexes like these.

What is vector search and how does HNSW work?

Vector search finds the stored vectors closest to a query vector under a similarity measure such as cosine similarity, dot product, or Euclidean (L2) distance. The vectors are usually embeddings, so "closest" means "most similar in meaning". Exact search compares the query with every stored vector, which is too slow for millions of items, so practical systems use approximate nearest neighbour (ANN) indexes such as HNSW, IVF, and product quantization.

Vector search is the retrieval step in retrieval-augmented generation (RAG): a question is embedded, the nearest document chunks are fetched, and an LLM answers from them. The same operation powers semantic search, recommendation, image search, deduplication, and anomaly detection. Libraries such as FAISS and hnswlib, and vector databases built on them, return the top results from hundreds of millions of vectors in milliseconds by searching only a tiny fraction of the data.

Key ideas

Vector search returns the k stored vectors most similar to a query, usually embeddings compared by cosine, dot product, or L2 distance.
Exact search costs one distance per stored vector, so its cost grows linearly with the size of the collection.
On normalized vectors, cosine similarity, dot product, and L2 distance produce the same ranking.
Approximate indexes trade a small loss in recall@k for search that is tens to thousands of times faster.
HNSW builds a layered proximity graph and searches it greedily from a sparse top layer down to a dense bottom layer, with ef controlling the beam width.
IVF limits the search to a few k-means clusters, and product quantization compresses each vector to a few bytes so billions of vectors fit in memory.

Short takes on this topic

The recommendation funnel in 1 picture

Common questions

What is a vector database?

A vector database stores embeddings alongside their source records and serves nearest-neighbour queries through an ANN index, usually HNSW or IVF. It adds the features of a database around the index: inserts and deletes, metadata filters, persistence, replication, and access control. Many relational and search engines, such as PostgreSQL with pgvector and Elasticsearch, now offer vector indexes too.

Is HNSW better than IVF?

HNSW usually gives higher recall at a given latency and needs no training step, but it keeps the full vectors and graph links in memory. IVF needs a k-means training pass and is often combined with product quantization, which makes it far more memory-efficient at billion scale. The right choice depends on collection size, memory budget, and how often the data changes.

How do you choose ef and M for HNSW?

M sets how many links each node keeps, so a larger M raises recall and memory use together. efConstruction controls build quality, and ef at query time controls the recall and latency trade-off. A common approach is to fix M and efConstruction, then raise ef until recall@k on a held-out set of queries with exact answers reaches the target.

Can you filter vector search results by metadata?

Yes, but filtering interacts with the index. Post-filtering searches first and then drops non-matching results, which can return fewer than k items when the filter is strict. Pre-filtering or filter-aware graph traversal restricts the search to matching items, and most vector databases implement one of these strategies.

Related explainers

Embeddings — Turning words and categories into vectors
Norms & Distance Metrics — L1, L2, cosine similarity — measuring closeness in vector spaces
K-Nearest Neighbors — Classification by proximity and distance metrics
K-Means Clustering — Unsupervised grouping by centroid distance
Retrieval-Augmented Generation — Ground language model outputs in retrieved documents to reduce hallucination
Quantization — Shrinking model weights to 8 and 4 bits

References

Last updated October 25, 2026