How Vector Search Works

A customer types "my card got declined" into your help centre search box. The article that solves their problem exists. It is titled "Resolving payment authorisation failures". Your search returns zero results, the customer opens a ticket, and your support cost goes up by about eight dollars.

Look at why it failed. A classic search engine builds an inverted index — a dictionary from each word to the list of documents containing it. The query has the tokens my, card, got, declined. The article has resolving, payment, authorisation, failures. The intersection is empty. BM25, the scoring function most keyword engines use, can only rank documents that share at least one term with the query. Zero shared terms means zero candidates, and no amount of tuning fixes that.

This is the lexical gap: humans express the same idea with different words. Synonym lists patch a few cases and then rot. What you actually want is a search system where "declined card" and "payment authorisation failure" land close together because they mean the same thing — where closeness is a number you can compute and sort by. That is vector search, and this lesson takes it apart from the geometry up to the index structures that make it fast.

What keyword search is good at, and where it collapses

Keyword search is not obsolete. It is unbeatable at exactly the things vector search is bad at, and knowing the split stops you from replacing a working system with a worse one.

Keyword search matches strings; vector search matches meaning. Production systems that serve real users almost always run both and fuse the results, because real query logs contain both kinds of query.

An embedding is a learned coordinate system for meaning

An embedding is a list of numbers — a vector — produced by a neural network from a piece of text, an image, or audio. A typical text embedding has 384, 768, 1024 or 1536 numbers in it. Each number on its own means nothing you can name. What matters is the arrangement: the model has been trained so that inputs with similar meaning get vectors pointing in similar directions.

Work through a toy version with three dimensions so you can do the arithmetic by hand. Suppose the model gives:

cat    = [2, 1, 0]kitten = [3, 1, 0]car    = [0, 1, 3]

Similarity here is the cosine of the angle between two vectors: the dot product divided by the two lengths.

For cat and kitten: the dot product is 2×3 + 1×1 + 0×0 = 7. The lengths are $\sqrt{2^2+1^2+0^2}=\sqrt5=2.2361$ and $\sqrt{3^2+1^2+0^2}=\sqrt{10}=3.1623$. So the cosine is 7 / (2.2361 × 3.1623) = 7 / 7.0711 = 0.990.

For cat and car: the dot product is 2×0 + 1×1 + 0×3 = 1. The lengths are 2.2361 and 3.1623 again, so the cosine is 1 / 7.0711 = 0.141.

Nothing about the strings "cat" and "kitten" is similar — they share two letters. The similarity lives entirely in where the model chose to put them. Now scale that from 3 dimensions to 768 and from 3 words to every sentence in your knowledge base, and you have semantic search.

Where those numbers actually come from

Modern text embedding models are trained contrastively. You take a large collection of paired texts that should be close — a question and its accepted answer, a title and its article body, a sentence and its translation. For each pair, the training objective pushes the two vectors together and simultaneously pushes each of them away from every other text in the same training batch. Those other texts are called in-batch negatives, and they are free: a batch of 1,024 pairs gives you 1,023 negatives per example at no extra cost. This is why embedding models are usually trained with enormous batch sizes.

Two consequences follow, and both bite people in production:

• The geometry is only meaningful within one model. A vector from text-embedding-3-small and a vector from bge-base-en-v1.5 live in unrelated coordinate systems even if both have 768 dimensions. Mixing them produces confident nonsense, not an error message.
• Some models are asymmetric. The E5 family was trained with distinct prefixes for the two sides of the pair — you must embed searches as "query: how do I reset my password" and documents as "passage: To reset your password…". BGE uses a longer instruction on queries only (optional but helpful in v1.5), and Nomic uses "search_query: " / "search_document: ". Leave out a prefix the model expects and recall drops, with no warning of any kind.

An embedding is only interpretable relative to the exact model, version, and input formatting that produced it. Re-embedding your whole corpus is the price of changing any of the three.

Choosing an embedding model

The model decides your ceiling. No index, reranker or prompt recovers meaning the embedding never captured. Here is the shape of the landscape rather than a leaderboard, because leaderboards move:

The two OpenAI rows replaced the older text-embedding-ada-002 (1536 dimensions, not truncatable), which you will still see in older tutorials.

Note "truncatable". The OpenAI v3 models are trained with Matryoshka representation learning: the most important information is packed into the leading dimensions, so you can keep the first 512 of 1536 numbers, renormalise, and lose only a little quality while cutting storage by two thirds. Not every model supports this. Truncating a model that was not trained for it destroys it.

How to actually choose

Public benchmarks tell you which models are plausible. They cannot tell you which is best for your domain, because your domain is not in them. The procedure that works:

1. Collect 50 to 100 real queries from your logs, support tickets or user interviews. Real ones, with typos and half-sentences.
2. For each query, have a human mark which documents in your corpus genuinely answer it. This is your gold set. It takes an afternoon and it is the single highest-leverage artefact in the project.
3. Embed the corpus with each candidate model, run exact search, and measure recall@10 and mean reciprocal rank against the gold set.
4. Only then weigh cost, latency, dimension and licence.

A concrete storage consequence of step 4: one million chunks at 1536 dimensions in float32 is 1,000,000 × 1536 × 4 = 6.14 GB. The same corpus at 768 dimensions is 3.07 GB, and at 384 dimensions 1.54 GB. If the 768-dimension model scores within one point of the 1536-dimension model on your gold set, you have just halved your RAM bill for nothing.

Turning geometry into a ranking

Once every document is a vector, search is mechanical: embed the query with the same model, compute a similarity against every candidate, sort, return the top k. Three similarity functions dominate.

There is an identity worth committing to memory. If both vectors are normalised to unit length, then

Squared Euclidean distance is a strictly decreasing function of cosine similarity, so on normalised vectors the two produce identical rankings. Check it with numbers: cosine 0.99 gives squared distance 2 − 1.98 = 0.02; cosine 0.14 gives 2 − 0.28 = 1.72. The order is preserved, reversed in sign as expected.

That identity is the reason most teams normalise every vector once at ingestion time. After normalising, cosine similarity is the dot product — no square roots, no divisions per comparison — and you can use an L2 index and a dot-product index interchangeably.

Exact search: the flat index

The simplest possible vector index stores the vectors in one contiguous array and compares the query against all of them. It is called a flat index, or brute-force search. Here it is in full:

1import numpy as np23class FlatIndex:4    def __init__(self, dim):5        self.dim = dim6        self.vectors = np.zeros((0, dim), dtype=np.float32)7        self.ids = []89    def add(self, ids, vectors):10        v = np.asarray(vectors, dtype=np.float32)11        # normalise once, so cosine similarity becomes a plain dot product12        v /= np.linalg.norm(v, axis=1, keepdims=True) + 1e-1213        self.vectors = np.vstack([self.vectors, v])14        self.ids.extend(ids)1516    def search(self, query, k=10):17        q = np.asarray(query, dtype=np.float32)18        q /= np.linalg.norm(q) + 1e-1219        scores = self.vectors @ q            # one matrix-vector product20        top = np.argpartition(-scores, k)[:k]   # O(n), not a full sort21        top = top[np.argsort(-scores[top])]     # sort only the k winners22        return [(self.ids[i], float(scores[i])) for i in top]

Two details in that code matter more than they look. np.argpartition finds the k largest scores in linear time instead of sorting all n — for n = 1,000,000 and k = 10 that alone is roughly a 5× saving on the ranking step. And normalising at insert rather than at query time moves work out of the hot path permanently.

This index is perfect. Its recall is 1.0 by definition, because it is the definition. It has no parameters to tune, no build step, and it handles deletions by removing a row. For under about 100,000 vectors it is often the correct production answer, and reaching for anything cleverer is premature.

Why it stops working

Do the arithmetic for 10 million chunks at 768 dimensions in float32.

The binding constraint is memory bandwidth, not floating-point throughput — the CPU can multiply faster than it can be fed. And 150 ms is the floor on a whole dedicated server. At 100 queries per second you would need roughly fifteen such machines doing nothing but scanning. That is the wall.

Brute-force vector search costs a full memory sweep per query. Every approximate index in existence is a scheme for reading a small fraction of the data instead.

What "approximate" actually costs you

Approximate nearest neighbour (ANN) search gives up the guarantee of finding the true top k in exchange for touching far less data. The quality measure is recall@k: of the k results exact search would have returned, what fraction did the approximate index return?

Concretely, suppose exact search on a query returns document ids

exact top-10 : [412, 88, 7301, 55, 9902, 143, 2210, 671, 3, 8845]ANN top-10   : [412, 88, 7301, 55, 9902, 143, 2210, 671, 3, 5127]

Nine of the ten match, so recall@10 = 9/10 = 0.90. Note which one was missed: the tenth-ranked result. ANN indexes almost never miss the top result; they lose marginal items at the bottom of the list, and the substitute (5127) is usually a document a human would rate as equally relevant.

This is why 0.95 recall is usually indistinguishable from 1.0 in a live product. Your embedding model already introduces far more ranking error than the index does. Chasing recall from 0.95 to 0.99 typically costs 3× the latency and buys nothing a user can perceive — unless you are in compliance, e-discovery or deduplication, where a genuine miss is a defect.

The four index families

Every vector index in production is built from four ideas, alone or combined.

1. Flat — scan everything

No structure. Perfect recall, linear cost. The baseline everything else is measured against, and the thing you must build first so you have ground truth.

2. IVF — partition the space, scan a few partitions

Inverted file indexes run k-means over a sample of your vectors to find nlist centroids, then assign every vector to its nearest centroid, forming nlist buckets. At query time you compare the query against the centroids only, pick the nprobe closest buckets, and scan those.

With 10M vectors, nlist = 4096 and nprobe = 16, you compare against 4,096 centroids plus roughly 16 × (10,000,000 / 4,096) = 39,062 vectors — about 43,000 comparisons instead of 10,000,000, a 230× reduction. nprobe is a pure runtime dial: raise it for recall, lower it for speed, no rebuild required. The failure mode is the boundary problem — a true nearest neighbour sitting just across a cell border in a bucket you did not probe.

3. Graph — walk a network of neighbours

HNSW (Hierarchical Navigable Small World) builds a graph where each vector links to roughly M close neighbours, stacked in layers like a skip list: sparse long-range links on top for coarse navigation, dense links at the bottom for precision. A search enters at the top, greedily walks towards the query, drops a layer, repeats, and finally explores the bottom layer keeping a candidate list of size ef.

A typical query at ef = 64 computes 1,000 to 3,000 distances out of 10 million. At 768 dimensions that is roughly 2,000 × 768 × 4 ≈ 6 MB touched instead of 30.7 GB — a five-thousand-fold cut. HNSW is the default in most engines because it delivers the best recall-per-millisecond. Its costs are memory (the graph itself) and build time.

4. Quantisation — make each vector smaller

Orthogonal to the other three: instead of scanning fewer vectors, shrink each one.

• Scalar quantisation maps each float32 component to an int8 using a per-dimension min/max. 4× smaller, typically 1–2 points of recall lost, and int8 arithmetic is faster.
• Product quantisation (PQ) splits a 768-dimension vector into, say, 96 sub-vectors of 8 dimensions each, runs k-means with 256 centroids on each sub-space, and stores 96 single-byte centroid ids. That is 96 bytes per vector instead of 3,072 — 32× compression. Distances are then computed by table lookup rather than arithmetic.
• Binary quantisation keeps one bit per dimension (usually the sign). 32× smaller, and distance becomes XOR plus popcount, which is astonishingly fast.

Quantised indexes are almost always paired with reranking: retrieve 10× more candidates cheaply from the compressed index, then rescore just those with the full-precision vectors. This recovers most of the lost recall for a small fixed cost.

The trade-offs side by side

Figures below are for one million 768-dimension float32 vectors on a modern server core. Treat them as orders of magnitude and measure your own.

The HNSW memory figure is worth unpacking, because people are surprised by it. The graph stores about 2M neighbour ids per vector at the bottom layer. With M = 16 and 4-byte ids that is 16 × 2 × 4 = 128 bytes per vector, plus roughly 8% for the upper layers — about 138 bytes, or 138 MB for a million vectors on top of the 3.07 GB of raw vectors. Doubling M to 32 doubles the graph to 276 MB.

Reading the table as a decision:

Where people get this wrong

"More dimensions means better search." Dimensions cost storage and bandwidth linearly and improve quality with sharp diminishing returns. A 3072-dimension model that beats a 768-dimension model by 0.8 recall points costs you four times the RAM forever. Measure the gain on your gold set before paying for it.

Benchmarking on 5,000 vectors, deploying on 10 million. At 5,000 vectors every index looks fast and every recall looks like 1.0, because nprobe = 8 out of nlist = 16 is scanning half your data. Index behaviour only becomes meaningful when the number of vectors is far larger than the number of partitions. Benchmark at production scale or do not benchmark.

Measuring recall against the wrong ground truth. Recall@10 must be computed against exact flat search on the same vectors with the same metric. Comparing against human relevance labels measures your embedding model, not your index, and the two failures need entirely different fixes.

Forgetting to normalise on one side. Normalising documents at ingestion and forgetting the query — or the reverse — silently turns cosine into a length-weighted score. Results stay plausible, which is what makes it dangerous. It usually shows up as long documents inexplicably dominating every result list.

Silently mixing model versions. Re-embedding half a corpus with a new model version and leaving the rest produces two clouds of points that never retrieve each other. There is no exception thrown. Stamp the model name and version into every record's metadata and refuse queries whose stamp does not match.

Treating chunking as an afterthought. The unit you embed is the unit you retrieve. A 4,000-word page embedded as one vector averages away everything specific in it; 40-word fragments retrieve precise sentences with no context to answer from. Chunks of roughly 200–500 tokens with 10–20% overlap are a reasonable starting point, and this parameter usually moves retrieval quality more than the choice of index does.

Building this for real

The sequence that consistently works, in order:

1. Write the gold set first. 50 queries with human-marked correct answers. Without it every later decision is a guess dressed up as an opinion.
2. Chunk, embed, and build a flat index. Measure recall and MRR. This is your quality ceiling and your correctness oracle — keep it forever, even after you move to ANN, because you need it to compute recall.
3. Fix retrieval quality before touching speed. If the flat index cannot find the right document, no ANN index will. Chunk size, the embedding model, and query preprocessing are the dials here.
4. Set an explicit recall budget. Something like "recall@10 ≥ 0.95 at p95 latency ≤ 50 ms". Now index selection is an engineering problem with an answer instead of a preference.
5. Introduce ANN only when flat search misses the latency budget, and re-measure recall against the flat index you kept.
6. Add keyword search back in. Run BM25 alongside vector search and fuse the two ranked lists. This recovers exactly the identifier and error-code queries that embeddings handle badly, and it typically costs less engineering than any further index tuning.

The teams that ship good search are not the ones with the cleverest index. They are the ones who can answer "what is your recall@10, measured how, on which queries?" without pausing.