Vector search

1. Intuition

Embeddings as points. An embedding model turns each chunk of text into a vector of a few hundred to a few thousand numbers. Texts with similar meaning land close together. A query is embedded with the same model, and search means "find the $k$ stored vectors closest to this one".

Exact search is simple and linear. Compare the query with every stored vector, keep the best $k$. With a million vectors, that is a million distance computations per query. It is perfectly accurate and fine for tens of thousands of vectors. It gets expensive at hundreds of millions, or at thousands of queries per second.

Approximate nearest neighbor (ANN) search gives up a little accuracy for a lot of speed. Three families dominate:

• IVF (inverted file). Cluster the vectors with k-means into nlist cells. At query time, find the nprobe cells whose centroids are closest to the query, and only scan vectors in those cells. A true neighbor that sits just across a cell boundary is missed unless you probe that cell too.
• HNSW (hierarchical navigable small world). Build a graph where each vector links to a few dozen near neighbors, plus sparse upper layers with long-range links. Search starts at the top, greedily hops toward the query, then explores a candidate list of size efSearch at the bottom layer. Fast and accurate, but the links cost memory and the whole graph usually lives in RAM.
• Product quantization (PQ). Compress each vector by splitting it into chunks and replacing each chunk with the ID of its nearest codebook entry. A 3 KB vector becomes about 100 bytes. Distances become approximate, so PQ is often combined with IVF (IVF-PQ) and followed by re-scoring the top candidates with full vectors.

Hybrid search. Dense vectors match meaning but can miss exact tokens: error codes, product SKUs, rare names. Keyword search (BM25) matches those exactly. Running both and merging the ranked lists with reciprocal rank fusion is a strong default.

2. Visualization

Try it (predict first, then check):

1. Set nprobe to 1 and drag the query onto a boundary between two cells. Predict recall@10. Then raise nprobe one step at a time until recall reaches 1.
2. Set nprobe equal to the number of clusters. Predict recall and the number of distance computations compared with brute force. Why is it slightly more than brute force?
3. Increase the number of clusters from 8 to 32 while keeping nprobe at 2. Predict what happens to cost and to average recall.
4. Raise $k$ from 5 to 20 with everything else fixed. Does recall go up or down, and why?

3. The math

Symbols

Similarity metrics

If every vector has length 1, the three agree on the ranking: $\cos = \text{dot}$, and $\lVert q - x\rVert^2 = 2 - 2\cos(q, x)$. So normalize at write time and at query time, then use dot product (the cheapest).

Worked example. $q = [1, 0]$, $a = [0.8, 0.6]$ (length 1), $b = [3, 4]$ (length 5).

• Dot: $q \cdot a = 0.8$, $q \cdot b = 3$. Dot ranks $b$ first because $b$ is long.
• Cosine: $\cos(q, a) = 0.8/1 = 0.8$, $\cos(q, b) = 3/5 = 0.6$. Cosine ranks $a$ first.
• L2: $\lVert q - a\rVert = \sqrt{0.2^2 + 0.6^2} = \sqrt{0.4} = 0.632$, $\lVert q - b\rVert = \sqrt{2^2 + 4^2} = \sqrt{20} = 4.472$. L2 ranks $a$ first.
• After normalizing, $b \to [0.6, 0.8]$. Now dot $= 0.6$, and $\lVert q - b\rVert^2 = 0.4^2 + 0.8^2 = 0.8 = 2 - 2(0.6)$. All three metrics agree.

Use the metric the embedding model was trained with. Models trained with a dot-product objective may encode useful information (such as confidence or popularity) in the vector length, and normalizing them throws it away.

Exact search cost

Brute force computes $N$ distances of $d$ multiply-adds each: $O(N \cdot d)$ per query, plus selecting the top $k$. With $N = 1{,}000{,}000$ and $d = 768$: $768{,}000{,}000$ multiply-adds per query. The work is a single matrix-vector product, so it runs at full hardware speed, which is why brute force on a GPU is competitive up to surprisingly large $N$.

IVF cost

A query computes $n_{\text{list}}$ centroid distances, then scans about $\frac{n_{\text{probe}}}{n_{\text{list}}} N$ vectors (if cells are balanced).

Worked example: $N = 1{,}000{,}000$, $d = 768$, $n_{\text{list}} = 1024$, $n_{\text{probe}} = 8$.

• Scanned vectors: $\frac{8}{1024} \times 1{,}000{,}000 = 7{,}812.5$.
• Distances: $1024 + 7{,}812.5 = 8{,}836.5$.
• Multiply-adds: $8{,}836.5 \times 768 = 6{,}786{,}432$.
• Fraction of brute force: $6{,}786{,}432 / 768{,}000{,}000 = 0.88\%$, about $113\times$ fewer.

A common starting point is $n_{\text{list}} \approx \sqrt{N}$ (here about 1,000) and then tuning $n_{\text{probe}}$ on a recall target. Cells are rarely balanced in practice; a few large cells make some queries much slower than average.

Recall@k for an index

This is recall of the index against brute force, not retrieval recall against human relevance labels. Example: exact top-10 is items 0 to 9. The index returns 0 to 7, plus 42 and 99. Overlap is 8, so recall@10 $= 8/10 = 0.8$. Measure it on a few hundred real queries, not random vectors, because real queries cluster where your data is dense.

HNSW memory and knobs

Each node stores up to $2M$ neighbor IDs at the bottom layer (upper layers add a small fraction more). With $M = 32$ and 4-byte IDs: $64 \times 4 = 256$ bytes per vector, so $256$ MB of links for a million vectors, on top of the vectors themselves. Knobs: $M$ (more links: higher recall, more memory, slower build), efConstruction (build-time search width: better graph, slower build), and efSearch (query-time candidate list, must be at least $k$: higher recall, higher latency). efSearch is the knob you tune per query.

Product quantization memory

Split each $d$-dimensional vector into $m$ subvectors of $d/m$ dimensions. For each position, learn a codebook of 256 centroids with k-means. Store each subvector as one byte (its centroid ID).

Worked example: $N = 1{,}000{,}000$, $d = 768$.

• Raw float32: $1{,}000{,}000 \times 768 \times 4 = 3{,}072{,}000{,}000$ bytes $= 3.072$ GB. In float16: $1.536$ GB.
• PQ with $m = 96$ (subvectors of $768/96 = 8$ dimensions): $96$ bytes per vector, so $96$ MB. Compression: $3072 / 96 = 32\times$.
• Codebooks: $96 \times 256 \times 8$ floats $\times 4$ bytes $= 786{,}432$ bytes, under 1 MB.
• Search: for each query, precompute a $96 \times 256$ table of distances from each query subvector to each centroid. Then each stored vector's approximate distance is the sum of 96 table lookups, with no multiplications.

Reciprocal rank fusion

BM25 scores and cosine similarities live on different scales, so adding them directly is fragile. RRF uses only ranks:

Worked example. Dense ranking: A, B, C, D. BM25 ranking: E, F, A, B.

• A: $\frac{1}{60+1} + \frac{1}{60+3} = 0.016393 + 0.015873 = 0.032266$.
• B: $\frac{1}{62} + \frac{1}{64} = 0.016129 + 0.015625 = 0.031754$.
• E: $\frac{1}{61} = 0.016393$ (BM25 only).
• F: $\frac{1}{62} = 0.016129$.
• C: $\frac{1}{63} = 0.015873$.
• D: $\frac{1}{64} = 0.015625$.

Fused order: A, B, E, F, C, D. Documents both rankers like (A, B) rise to the top. E, BM25's first pick that dense search missed, still beats C and D. The large constant $c$ keeps one ranker's first place from dominating.

Metadata filtering

Suppose a user may only see 2% of the corpus. Post-filtering (retrieve top 10, then drop disallowed ones) keeps on average $10 \times 0.02 = 0.2$ results: usually none. To expect 10 survivors you would need to fetch $10 / 0.02 = 500$ candidates. Pre-filtering (restrict the search to allowed vectors) returns 10 correct results, but it interacts with the index: an HNSW traversal that must skip 98% of nodes can get stuck, and IVF cells may contain few allowed vectors. Good engines use filter-aware traversal, per-tenant partitions, or fall back to brute force over the allowed subset when it is small. Access-control filters must be enforced in the retrieval query, never left to the LLM.

4. Implementation

The full script is code/16-rag/vector_search_scratch.py (NumPy only, about two seconds on a laptop). It builds each index type from section 3 on its own k-means and measures recall against exact search on synthetic clustered vectors (64 clusters in 32 dimensions; real embeddings cluster too, but less cleanly).

Build it from scratch

Step 1: exact search. Normalize every vector once, at write time, so cosine becomes a dot product. Then the whole search is one matrix-vector product. argpartition finds the top $k$ in $O(N)$ without sorting all $N$ scores; only those $k$ get sorted.

def normalize(X):
    return X / np.linalg.norm(X, axis=-1, keepdims=True)

def exact_topk(X, q, k):                          # X: [N, d] normalized, q: [d] normalized
    s = X @ q                                     # one matrix-vector product: N dot products
    top = np.argpartition(-s, k)[:k]              # top k in O(N), unsorted
    return top[np.argsort(-s[top])]

Predict: you normalize the stored vectors but forget to normalize the query. Does the ranking change?

Step 2: k-means. Both IVF and PQ are built on it. Squared distances come from $\lVert x\rVert^2 - 2x \cdot c + \lVert c\rVert^2$, so every point-to-centroid distance is one matrix product instead of a Python loop.

def kmeans(X, k, rng, iters=10):
    C = X[rng.choice(len(X), k, replace=False)]   # start from k random points
    for _ in range(iters):
        d2 = (X**2).sum(1)[:, None] - 2 * X @ C.T + (C**2).sum(1)   # squared distances [N, k]
        lab = d2.argmin(1)
        for j in range(k):
            if (lab == j).any():
                C[j] = X[lab == j].mean(0)
    return C, lab

Predict: the shapes are [N, 1], [N, k], and [k]. Which broadcasting rule makes the sum [N, k]?

Step 3: IVF. Cluster the data into $n_{\text{list}}$ cells and store each cell's member IDs (the inverted lists). A query compares itself to the centroids, opens the $n_{\text{probe}}$ nearest cells, and runs exact search on only those members.

class IVF:
    def __init__(self, X, nlist, rng):
        self.X = X
        self.C, lab = kmeans(X, nlist, rng)
        self.lists = [np.flatnonzero(lab == c) for c in range(nlist)]   # inverted lists

    def search(self, q, k, nprobe):
        cells = np.argsort(-(self.C @ q))[:nprobe]                     # nearest centroids
        cand = np.concatenate([self.lists[c] for c in cells])
        return cand[np.argsort(-(self.X[cand] @ q))[:k]], len(cand)

Predict: a query's true neighbor sits just across the border of the nearest cell. Which knob fixes the miss, and what does it cost?

Step 4: product quantization. Cut each vector into $m$ subvectors and run k-means with 256 centroids on each position, so a subvector is stored as one byte. At query time, score the query's subvectors against every centroid once (an $[m, 256]$ table); each stored vector's score is then $m$ table lookups added up.

class PQ:
    def __init__(self, X, m, rng):
        self.m, self.ds = m, X.shape[1] // m      # m subvectors of ds dimensions
        self.books, codes = [], []
        for j in range(m):
            sub = X[:, j * self.ds:(j + 1) * self.ds]
            C, lab = kmeans(sub, 256, rng)        # 256 centroids -> a code fits in one byte
            self.books.append(C); codes.append(lab)
        self.codes = np.stack(codes, 1).astype(np.uint8)   # [N, m]: the whole stored index

    def search(self, q, k):
        table = np.stack([self.books[j] @ q[j * self.ds:(j + 1) * self.ds] for j in range(self.m)])  # [m, 256]
        s = table[np.arange(self.m), self.codes].sum(1)    # m lookups per vector, no float math on X
        return np.argsort(-s)[:k]

Predict: section 3's example has $d = 768$ and $m = 96$. How big is the lookup table per query, in entries?

Step 5: BM25 and fusion. BM25 is TF-IDF with two fixes: term frequency saturates ($k_1$ caps how much a repeated word helps) and long documents are discounted ($b$ normalizes by length). RRF then merges any number of rankings using ranks only, so BM25 scores and cosine scores never need to share a scale.

def bm25_scores(docs, query, k1=1.5, b=0.75):
    toks = [re.findall(r"\w+", d.lower()) for d in docs]
    avgdl = sum(map(len, toks)) / len(toks)
    df = Counter(t for d in toks for t in set(d))
    scores = []
    for d in toks:
        tf, s = Counter(d), 0.0
        for t in re.findall(r"\w+", query.lower()):
            if t in tf:
                idf = math.log((len(toks) - df[t] + 0.5) / (df[t] + 0.5) + 1)
                s += idf * tf[t] * (k1 + 1) / (tf[t] + k1 * (1 - b + b * len(d) / avgdl))
        scores.append(s)
    return scores

def rrf(rankings, c=60):
    s = {}
    for ranking in rankings:
        for rank, doc in enumerate(ranking, start=1):
            s[doc] = s.get(doc, 0.0) + 1 / (c + rank)
    return sorted(s, key=s.get, reverse=True), s

Predict: with $k_1 = 1.5$ and an average-length document, how much more does a word appearing 10 times add than a word appearing once? (Compute $\frac{tf(k_1+1)}{tf + k_1}$ for both.)

Use the library

FAISS names each idea in an index string, and vector databases expose the same knobs:

import faiss                                         # pip install faiss-cpu
d = X.shape[1]
index = faiss.index_factory(d, "IVF1024,PQ16", faiss.METRIC_INNER_PRODUCT)
index.train(X)                                       # k-means for the cells and the PQ codebooks
index.add(X)
index.nprobe = 8                                     # cells scanned per query
scores, ids = index.search(Q, 10)

hnsw = faiss.IndexHNSWFlat(d, 32, faiss.METRIC_INNER_PRODUCT)   # M = 32
hnsw.hnsw.efSearch = 64                              # query-time candidate list

In Postgres, pgvector offers ivfflat (with ivfflat.probes) and hnsw (with hnsw.ef_search) indexes. What the libraries add: SIMD and GPU kernels, HNSW graphs (not built here: the build is long, and the knobs in section 3 are what you tune), on-disk indexes, filtered search, and incremental inserts.

Run it

uv run code/16-rag/vector_search_scratch.py

Key lines of output (synthetic vectors):

dot a=0.8 b=3.0 | cos a=0.8 b=0.6 | L2 a=0.632 b=4.472
nprobe= 1: recall@10 0.745, vectors scanned 1.1% of N
nprobe= 4: recall@10 0.995, vectors scanned 3.4% of N
nprobe=16: recall@10 1.000, vectors scanned 12.2% of N
memory: float32 128 bytes/vector -> PQ 16 bytes/vector (8x smaller)
recall@10 PQ only 0.379; PQ top-100 + exact rerank 0.947
query 'E1234': [1.23, 0.0, 0.0, 0.0] <- exact IDs are BM25's strength
fused: ['A', 'B', 'E', 'F', 'C', 'D'] {'A': 0.032266, 'B': 0.031754, ...}

The first and last lines reproduce section 3's worked examples. IVF reaches 99.5% recall while scanning 3.4% of the vectors. PQ alone is crude, because neighbors in tight clusters differ by less than the quantization error, but as a shortlist followed by exact rescoring of 100 candidates it recovers most of the recall: the standard production pattern. These recall numbers come from clean synthetic clusters; measure your own index on real queries. The cost arithmetic and the section 2 figure are in code/16-rag/vector_search.py.

5. Engineering

Choosing the embedding model and dimension. Evaluate candidate models on your queries and documents with a labeled set, not on a public leaderboard alone. Dimension drives memory and latency linearly: 3072 dimensions cost 4 times what 768 cost. Some models are trained so that a prefix of the vector is itself a good embedding (Matryoshka-style), letting you truncate to 256 or 512 dimensions and re-normalize. Quantizing stored vectors to int8 or binary with a full-precision re-score of the top candidates is another common memory lever. Read the model card for input formatting: many retrieval embedding models are asymmetric and expect a different prefix or instruction on queries than on documents (E5 uses query: and passage: ), and skipping it quietly lowers recall.

Reindexing when the model changes. Vectors from two different embedding models are not comparable, even at the same dimension. Changing the model means re-embedding the whole corpus. Do it as a blue-green migration: build the new index alongside the old one, compare recall on your eval set, switch reads, then delete the old index. Store the model name and version with every vector and every request trace.

Updates and deletes. IVF appends new vectors to their nearest cell, but the centroids were trained on old data, so cells drift out of balance as the data changes; retrain periodically. HNSW inserts are incremental but deletes are usually tombstones that the search skips until a rebuild or compaction. Plan for re-index jobs, and track the fraction of deleted entries.

Latency budget. Tune on a recall target, for example "recall@10 at least 0.95 against brute force at p95 latency under 20 ms", and report both. A reranker after retrieval can recover precision, but it cannot recover a document the index never returned.

Which system.

Watch out

Failure modes. Query embedded with a different model or version than the corpus; mixing normalized and unnormalized vectors; post-filtering that returns nothing; nprobe or efSearch left at a tiny default; stale IVF centroids after heavy inserts; deleted documents still returned; measuring recall on random vectors instead of real queries.

Common mistakes

• Using cosine for a model trained with dot product, or the reverse, without checking.
• Tuning the LLM prompt when the index recall against brute force is 0.7.
• Assuming exact search is always too slow. Under a few hundred thousand vectors, brute force is often fast enough and has perfect recall.
• Adding BM25 and cosine scores directly without normalization, instead of RRF or normalized scores.
• Forgetting that HNSW memory includes the graph, not just the vectors.

6. Knowledge check

Practice exercise. You store $N = 10{,}000{,}000$ vectors with $d = 1024$ in float32. (a) How much memory do the raw vectors take? (b) With PQ using $m = 128$ one-byte codes, how much? (c) An IVF index has $n_{\text{list}} = 4096$ and $n_{\text{probe}} = 16$. Approximately how many vectors does one query scan?

Implementation challenge. Extend the script: build an IVF index on the synthetic data, then plot recall@10 against nprobe for $n_{\text{list}} \in \{32, 128, 512\}$ on the same cost axis. Which nlist gives the best recall at 5% of brute-force cost?

Summary

• Normalize embeddings and the three metrics agree; then use dot product. Otherwise use the metric the model was trained with.
• Exact search costs $O(N \cdot d)$ per query and has perfect recall. It is often fine up to a few hundred thousand vectors.
• IVF scans $n_{\text{probe}}/n_{\text{list}}$ of the data; HNSW walks a neighbor graph tuned by $M$ and efSearch; PQ compresses vectors about 32 times at some accuracy cost.
• Measure index recall@k against brute force on real queries, and tune for a recall target at a latency budget.
• Fuse BM25 and dense rankings with RRF, enforce permission filters inside retrieval, and re-embed everything when the embedding model changes.

Next: Evaluating LLM systems

Related: The RAG pipeline · K-nearest neighbors · K-means · Cheat sheet: vector search

Go deeper, code-first (AI Engineering from Scratch): Image Retrieval & Metric Learning

Parts of this lesson are adapted from AI Engineering from Scratch by Rohit Ghumare (MIT license, notice): Information Retrieval and Search, Embedding Models — The 2026 Deep Dive, Embeddings & Vector Representations, Hybrid Retrieval with BM25 and Dense Embeddings.

Interview angle