Part IV · Applied concepts · Chapter 25

Vector search internals

Finding the stored vectors closest to a query vector sounds simple: measure the distance to each one and sort. At a few thousand passages that is exactly what you should do. At millions it is too slow, and search engines switch to approximate methods that look at a small fraction of the vectors and usually, not always, find the true nearest ones. This chapter opens up those methods, then adds the two tools that most improve retrieval in practice: keyword scoring and reranking.

Exact search and what it costs

Exact (brute-force) search computes the similarity between the query and every stored vector. Each similarity of two d-dimensional vectors is d multiplications and additions, so one query costs N × d.

• The demo corpus of chapter 24: 68 sections × 384 numbers = 26,112 multiply-adds per question. Nothing.
• One million passages × 384 = 384 million multiply-adds per question. Still feasible on one machine, but it adds up under load, and every stored vector must be read from memory for every query.
• A hundred million passages: no longer practical per query.

Exact search has one great property: it is always right. Use it until it is too slow, and use it as the ground truth when you tune an approximate index.

Approximate search

An approximate nearest-neighbour (ANN) index organises the vectors ahead of time so a query can skip most of them. Its quality is measured by recall@k: of the true k nearest neighbours, what fraction did it return? An index with recall@10 of 0.95 misses, on average, half a true neighbour per query. Two designs dominate.

IVF: search only the nearby cells

An inverted-file index (IVF) clusters the vectors with k-means (lists clusters, each with a centre). Every vector is stored in the list of its nearest centre. A query compares itself with all the centres, picks the probes nearest, and searches only those lists.

Worked with pgvector's suggested starting points: for 1,000,000 rows, lists = rows / 1,000 = 1,000, and probes ≈ √1,000 ≈ 32. A query computes 1,000 distances to centres plus about 32 × 1,000 = 32,000 to vectors in the probed lists: 33,000 in all, about 30 times fewer than exact search. The risk: a true neighbour that sits just across the border of an unprobed cell is never seen. More probes, fewer misses, slower queries. IVF needs data to train its clusters, so it is built after the table is filled, and it drifts as the data changes.

HNSW: walk a graph

A hierarchical navigable small-world graph (HNSW) links each vector to a handful of its near neighbours (up to m per layer). Search starts at an entry point and repeatedly moves to whichever neighbour is closer to the query, like asking for directions. A few upper layers hold only a sample of the points with longer links, like an express line that gets you to the right district before you change to the local stops.

The search keeps a list of the best ef candidates found so far, not just one, so it can step around a dead end. Larger ef finds more true neighbours and costs more distance computations. Building takes longer and uses more memory than IVF, but there is no training step, so the index can be built on an empty table and grows as rows arrive. pgvector's defaults are m = 16, ef_construction = 64 while building, and hnsw.ef_search = 40 at query time.

Averaged over the same 200 random queries in this toy: IVF with 1 probe finds 79% of the true five nearest points while computing 34 distances instead of 300, and with 2 probes 98% for 53. The graph search finds 60% with ef = 5, 91% with 20 and 99% with 40, for 61, 87 and 106 distances. Real indexes show the same shape at much larger scale: each step towards perfect recall costs more work than the last.

Filters and approximate indexes

Real queries often add a condition: only one customer's documents, only policies. An approximate index finds candidates first and the filter runs afterwards, so a narrow filter can leave fewer than k results, or none, even though matching rows exist. pgvector's documentation describes this and offers iterative index scans as a remedy: with hnsw.iterative_scan set, the scan keeps walking the graph until it has k rows that pass the filter. With a small table, exact search with the filter is simpler and always correct.

Keyword search: BM25 by hand

Before embeddings, search engines scored documents by the words they share with the query. The standard formula, BM25, is still hard to beat on queries full of names, codes and rare terms. For each query word it multiplies two things:

• How rare the word is across the collection (inverse document frequency): idf = ln(1 + (N − n + 0.5) / (n + 0.5)), where N is the number of documents and n the number containing the word. Rare words count for more.
• How often it appears in this document, with diminishing returns and a correction for length: f(k₁ + 1) / (f + k₁(1 − b + b · len / avglen)), with the usual k₁ = 1.2 and b = 0.75.

Worked with three tiny documents and the query "fixed deposit":

Each word is in 2 of 3 documents, so idf = ln(1 + 1.5 / 2.5) = ln 1.6 = 0.470. The average length is 16 / 3 = 5.33 words. For d1 (length 6, each word once) the word part is 2.2 / (1 + 1.2 × (0.25 + 0.75 × 6 / 5.33)) = 2.2 / 2.3125 = 0.951, so its score is 2 × 0.470 × 0.951 = 0.894. d2 and d3 match one word each and are slightly shorter than average, scoring 0.470 × 1.026 = 0.482.

BM25 knows nothing about meaning: "FD" and "fixed deposit" share no words. Embeddings know nothing about exact codes: "DGBND" is just a few odd tokens. That is why the two are combined.

Hybrid search and reciprocal rank fusion

Run both searches and merge the two ranked lists. Their scores are on different scales, so the usual merge ignores scores and uses ranks. Reciprocal rank fusion (RRF) gives each document 1 / (60 + rank) from each list it appears in and adds them up; the constant 60 keeps one list's first place from overwhelming everything else.

Worked: passage A is 1st by vectors and 3rd by keywords: 1/61 + 1/63 = 0.03227. Passage B is 2nd by vectors and 1st by keywords: 1/62 + 1/61 = 0.03252. B wins, because it is near the top of both lists.

Fusion is not automatically better. On the ten retrieval questions of the demo corpus in chapter 24 (embedding the section body only), vector search and a BM25 written for this book each put the right section in the top 3 for 5 questions, and their RRF fusion for only 4: when both lists are weak, merging them does not help. With the heading path added to every section, all three reach 10 out of 10, and BM25 ranks the right section first every time, partly because these questions reuse the headings' own words. These counts were measured on the corpus's original wording, before some invented names in it were changed, so treat them as illustrative.

RRF is not the only way to merge. You can also pool the best candidates from several searches, for example the 20 best vector hits plus the sections a table-of-contents search picked, and let a reranker order the whole pool in one pass (next section).

Reranking with a cross-encoder

An embedding model is a bi-encoder: it encodes the query and each passage separately, which is what makes searching millions of stored vectors possible. A cross-encoder reads the query and one passage together, so its attention can compare them word by word, and outputs one relevance score. It is much more accurate and much more expensive, because it runs once per pair and nothing can be precomputed.

The standard pattern is two stages: retrieve generously with cheap methods (say the top 50 by hybrid search), rerank those 50 with a cross-encoder, and keep the best 3 to 5. Fifty cross-encoder runs per question is affordable; fifty thousand is not.