Vector Search at Scale

From embeddings to search: where the math suddenly becomes a systems problem

Dr. Lena Hartmann: In L10, we turned text into a vector in d-dimensional space, so similarity became a geometric question.

Dr. Lena Hartmann: Now we have one query vector q, and a huge database of vectors x one through x N.

Kai: If similarity is just a dot product, why not compute it with everything and sort?

Dr. Lena Hartmann: That is exactly our baseline, and it is perfect for learning, but at scale it can be too slow or too expensive per query.

Dr. Lena Hartmann: So our goal today is practical: return the top k neighbors even when N is massive, without losing the meaning of what similarity is.

Why brute force breaks at $10^6$: latency, cost, and user experience

Dr. Lena Hartmann: In retrieval augmented generation, retrieval is on the critical path: you embed the query, search, then generate.

Dr. Lena Hartmann: A common real setting is about one million vectors, each around seven hundred sixty eight numbers long.

Kai: So top k is like the nearest neighbors, but we only need a small list, not a full ranking?

Dr. Lena Hartmann: Exactly. Most applications only need the best few candidates, like k equals five, ten, or fifty.

Kai: When you say one score per vector, are we talking about a million dot products for a single user question?

Dr. Lena Hartmann: The brute force baseline is simple: compute one similarity score per database vector, then take the top k.

Dr. Lena Hartmann: This line is the scale problem: work grows like N times d, so pushing N up by a thousand pushes compute up by a thousand.

Nearest neighbors as geometry: angles on a sphere

Dr. Lena Hartmann: Cosine similarity compares the angle between vectors: one means same direction, zero means perpendicular, negative means opposite directions.

Dr. Lena Hartmann: In practice we often normalize vectors to length one, so we focus on direction, not magnitude.

Kai: So if everything is normalized, vector search is just lots of dot products?

Dr. Lena Hartmann: Yes, and that is why linear algebra is the whole story here: nearest neighbor is the biggest dot product.

Dr. Lena Hartmann: Conceptually, all your embeddings live on a high-dimensional sphere, and you are asking which directions are closest to your query direction.

Let me show you in code: brute-force top-$k$ with cosine similarity

Dr. Lena Hartmann: We are searching with one query vector, like one user question turned into an embedding.

Dr. Lena Hartmann: And the database is a matrix X: N rows, each row one embedding.

Kai: So at scale, the math is still this, but we need a way to not compute that full matrix times vector every time?

Dr. Lena Hartmann: Exactly. The retrieval problem is: keep the same definition of similarity, but avoid scoring all N vectors.

Visual intuition in $2$D: top-$k$ means closest direction

Dr. Lena Hartmann: Notice we did not pick the closest points in Euclidean distance from the tip of the arrow; we picked points pointing the same way.

Kai: So vector search is basically ranking by alignment, and top k is just the shortlist we pass to the next stage.

Dr. Lena Hartmann: In real embeddings, the geometry is the same but in hundreds of dimensions, so we need smarter ways to find those aligned directions fast.

The core math problem: maximize a dot product, return top-$k$

Dr. Lena Hartmann: This equation says: treat the database as a matrix whose rows are vectors, so scores equals X hat times q hat and the result is an N-length score vector. Then argtopk of scores simply means the indices of the k largest entries, which is what we return.

Dr. Lena Hartmann: The time cost grows linearly with the number of vectors and the embedding dimension, because you touch every coordinate of every vector.

Dr. Lena Hartmann: Brute force gives the exact answer. That is why we keep it as our gold standard for checking anything approximate.

Kai: So approximate means we might miss the true best match sometimes, but we get a huge speedup?

Dr. Lena Hartmann: Exactly, and the art is making the miss rate small enough that the application quality does not drop.

Dr. Lena Hartmann: Most scalable methods are the same idea: quickly propose a small candidate set M, then do exact scoring only inside that set.

Scale pain #1: memory is also linear algebra

Dr. Lena Hartmann: Memory is the same multiplication: number of vectors times dimension times bytes per number.

Dr. Lena Hartmann: With float32, you store four bytes per coordinate. One million by seven hundred sixty eight by four is multiple gigabytes.

Dr. Lena Hartmann: Even if your CPU can do dot products fast, pulling gigabytes from memory for every query is a losing game.

Kai: Is this where people use int8 embeddings, like model quantization but for the database?

Dr. Lena Hartmann: Yes. Quantization reduces memory and bandwidth, and it often helps latency more than it hurts accuracy.

Dr. Lena Hartmann: And indexing is the other half: do not even look at most vectors, because most cannot be in the top k anyway.

A worked approximation: cluster first, then search inside a few clusters (IVF idea)

Dr. Lena Hartmann: The offline work is to build a coarse partition of space into C regions, each with a centroid.

Dr. Lena Hartmann: Before we run anything, make a prediction: if we probe 3 out of 50 centroids, what fraction of the dot products do you expect compared to brute force, and what do you expect recall at 1 to do as probes increases?

Kai: So we still do exact dot products, just on a smaller pool that is hopefully where the true neighbor lives.

Dr. Lena Hartmann: And when we reveal the results, the rough mental model is that the candidate work scales like m over C times N dot products, so increasing probes raises recall but also increases compute.

The scaling trick in one line: reduce candidates, then do exact math

Dr. Lena Hartmann: If clusters are roughly balanced, probing m out of C clusters means you only score about m over C of the database.

Dr. Lena Hartmann: Think of it as a funnel: stage one produces a shortlist S, stage two computes exact dot products inside S.

Dr. Lena Hartmann: Different indexes implement the filter differently: clustering like IVF, graph navigation like HNSW, or hashing like LSH.

Kai: Does the index depend on whether we use cosine similarity versus Euclidean distance?

Dr. Lena Hartmann: Yes. Many systems support multiple metrics, and normalization can convert cosine search into a dot-product search on unit vectors.

Dr. Lena Hartmann: In practice you tune an index by measuring three things together: how fast, how accurate, and how big the index is.

Production reality: batch dot products on GPU (PyTorch view)

Dr. Lena Hartmann: Visually, retrieval is just matrix multiplication: rows of Q dotted with rows of X.

Dr. Lena Hartmann: Even with a fast GPU, multiplying by a million rows per query can be too much, so indexing still matters.

Kai: So an index finds candidates, then the GPU does the exact dot products on that smaller set for accuracy.

What you should remember: vector search is linear algebra plus a candidate funnel

Dr. Lena Hartmann: Your vector database is a matrix, and every user query becomes another vector of the same dimension.

Dr. Lena Hartmann: Similarity is usually a dot product, possibly after normalization so it behaves like cosine similarity.

Dr. Lena Hartmann: Brute force is the truth you compare against, and it has linear cost in both N and d.

Kai: So the whole game is making M small without losing the true neighbors too often.

Dr. Lena Hartmann: And you tune the system by measuring recall at k along with end-to-end latency and memory footprint.

Exit ticket: compute one cosine score, then choose an approximation trade-off

Dr. Lena Hartmann: Use the cosine formula: dot product on top, product of lengths on the bottom.

Kai: Let me try: the dot product is two, and the lengths are square root five and two.

Dr. Lena Hartmann: Great. Two divided by two times square root five is one over square root five, which is about zero point four four seven.

Kai: I would accept that trade-off when a slightly imperfect first pass is fine, like when I rerank later, or when latency matters more than one perfect match, like autocomplete or chat retrieval.

Dr. Lena Hartmann: A good answer mentions context: you might accept a small miss rate when you rerank later, or when latency is the top priority, like autocomplete or chat retrieval.

Thank you for watching!

Thanks for watching. Subscribe and share if you found this useful—see you next time!