Why Exact Nearest Neighbour Search Does Not Scale

A vector database exists to answer one question quickly: given a query vector, which of my stored vectors are closest to it?

That operation, k-nearest-neighbour search, is the retrieval step underneath semantic search, retrieval-augmented generation, recommendation, deduplication and image similarity. Everything else a vector database does, filtering, metadata, persistence, is scaffolding around it.

The reason it needs a specialised system is that the naive implementation is expensive in a specific way. To find the closest vector exactly, you compute the distance from the query to every stored vector and keep the smallest. For N vectors of dimension d, that is N times d multiply-accumulate operations per query.

Put numbers on it. Ten million vectors at 768 dimensions is roughly 7.7 billion operations per query. That is achievable on modern hardware in a fraction of a second, and it is entirely unachievable at a thousand queries per second without a fleet of machines.

So the field is built around a bargain: give up the guarantee of finding the exact nearest neighbours, in exchange for finding almost all of them almost always, orders of magnitude faster. Everything in this cursus is about the shape of that bargain and how to control it.

Closest requires a definition of distance, and choosing the wrong one silently degrades everything downstream.

Euclidean distance, or L2, is the straight-line distance between two points. It accounts for magnitude as well as direction, so two vectors pointing the same way but with different lengths are far apart.

Cosine similarity measures the angle between two vectors and ignores magnitude entirely. Two vectors pointing in the same direction are maximally similar regardless of length. This is usually what you want for text embeddings, because the direction carries the semantic content while magnitude often reflects incidental properties such as document length.

Inner product, or dot product, is the unnormalised version: it rewards both alignment and magnitude. It matters in recommendation, where a larger magnitude can legitimately encode popularity or confidence.

The critical relationship: for vectors normalised to unit length, cosine similarity and inner product rank identically, and Euclidean distance produces the same ordering too. So if your embeddings are normalised, the choice does not affect which neighbours you get.

The practical rule that follows: use the metric the embedding model was trained with. A model trained with a cosine objective produces a space where cosine is meaningful, and querying it with inner product on unnormalised vectors will return results skewed by length. Check the model card, and normalise if in doubt.

The obvious response to slow search is to build an index, and the classical spatial indexes do not work here. Understanding why is what motivates every structure in the next lesson.

A k-d tree partitions space by splitting on one dimension at a time, and in two or three dimensions it works beautifully: search prunes most of the tree and runs in logarithmic time.

In high dimensions it degrades until it is slower than brute force, because of a cluster of counterintuitive geometric facts.

Volume concentrates at the edges. In high dimensions almost all of a hypercube's volume lies near its surface, so partitioning the interior separates very little.

Distances concentrate. As dimension rises, the distance between the nearest and farthest points in a random set converges: everything becomes roughly equidistant from everything else. The contrast that makes nearest neighbour meaningful erodes.

And neighbourhoods span partitions. A query point near any boundary must search the adjacent cell, and in high dimensions a point is near almost every boundary, so pruning fails and the search visits most of the tree anyway.

The practical threshold is around ten to twenty dimensions for tree structures. Text embeddings run from 384 to 3072 dimensions, which is far past the point where exact indexing helps.

So exactness has to go. What replaces it is the subject of the next lesson.

Approximate nearest neighbour search trades three quantities against each other, and no index escapes the triangle.

Recall is the proportion of the true nearest neighbours the index actually returns. Recall at 10 of 0.95 means that across queries, 95 percent of the true top-10 appear in the returned top-10.

Latency is time per query. Memory is bytes per vector plus index overhead.

Every tuning knob in the next lesson moves along one edge of this triangle. Searching more of the graph raises recall and latency together. Compressing vectors cuts memory and lowers recall. Building a denser index raises recall and memory and build time.

The consequence for practice is that there is no best index, only an index tuned to a stated requirement. A team that has not decided what recall it needs cannot tune anything, because every configuration is defensible against an unstated target.

And recall is measurable, which many teams do not realise: compute brute-force ground truth on a sample of queries, then compare.

Before reaching for an approximate index, it is worth knowing that flat search is frequently correct, and reaching past it is a common source of unnecessary complexity.

Below roughly a hundred thousand vectors, brute force on modern hardware is fast enough for most interactive applications. A hundred thousand vectors at 768 dimensions is about 77 million operations, which a vectorised implementation handles in a few milliseconds.

At that scale, flat search has properties an approximate index cannot match. Recall is exactly 1.0 by construction. There is no build step, so writes are immediate and there is no staleness. There are no parameters to tune and therefore none to get wrong. Filtering is trivial because you are scanning anyway. And behaviour is completely predictable.

A useful heuristic: start flat, measure, and move to an approximate index when the measurement says you must. The measurement is query latency at your actual concurrency, not a benchmark.

Two caveats. Memory still binds: a hundred thousand 768-dimension float32 vectors is roughly 300 megabytes, which is fine, while ten million is 30 gigabytes, which is not. And a flat index scales linearly, so a system growing an order of magnitude will need the migration eventually.

But a team running two hundred thousand vectors on a tuned HNSW index they do not understand has usually bought complexity rather than performance.

Dimensionality drives memory, latency and index quality simultaneously, and it is the parameter teams most often accept as given when it is actually a choice.

Memory scales linearly with dimension. A float32 vector at 1536 dimensions costs 6 kilobytes; at 384 dimensions, 1.5 kilobytes. Across ten million vectors that is 60 gigabytes against 15, which is the difference between one machine and several.

Distance computation scales linearly too, so a query against 1536-dimension vectors costs four times what 384 costs, in both flat and approximate search.

And the curse of dimensionality worsens with dimension, so higher-dimensional spaces are intrinsically harder to index well, requiring more graph connections or more probes for the same recall.

The response is that dimension is often reducible at little quality cost. Many current embedding models support Matryoshka representation learning, which trains the model so that truncating the vector to a prefix retains most of its quality. A 1536-dimension embedding truncated to 512 may lose a small amount of retrieval quality while cutting memory and compute by two thirds.

The practical instruction: measure retrieval quality at several truncations on your own evaluation set before accepting the full dimension. The right dimension is a tuning decision with a measurable answer, not a property of the model you must accept.

Recall is the quantity everything else trades against, and most teams never measure it, which means they are tuning blind.

The procedure is simple and cheap.

Take a sample of real queries, a few hundred is usually enough.

Compute exact nearest neighbours by brute force over the full corpus. This is slow and you only do it once, offline.

Run the same queries through your index and compare the returned sets.

Recall at k is the average, over queries, of the proportion of the true top-k that appears in the returned top-k.

Three cautions that determine whether the number means anything.

Use real queries. Synthetic ones are drawn from a different distribution and are usually easier, so they overstate recall.

Recompute after any change to the corpus, the index parameters, or the embedding model. Recall is a property of the combination, not of the index alone.

And distinguish recall from end-to-end quality. Recall measures whether the index found what brute force would have found. It says nothing about whether those were the right documents, which is a question about the embedding model and is measured with the RAG evaluation methods in the Advanced RAG cursus.

A system can have recall of 0.99 and retrieve poorly, because the index faithfully returned the wrong neighbours.

Since everything trades against recall, the requirement has to come from the application rather than from a default.

The question that sets it: what happens when a relevant document is missed?

Where a reranker sits downstream, over-retrieve and let it sort. Fetching 100 candidates at recall 0.90 and reranking to 10 is often better than fetching 10 at recall 0.99, because the reranker recovers ordering and the wider net compensates for index misses. This is the most common production arrangement and it substantially relaxes the recall requirement.

Where the retrieved set goes straight into a model's context with no reranking, misses are invisible and unrecoverable, so recall matters more.

Where retrieval feeds a compliance or discovery process that must not miss items, approximate search may be inappropriate entirely and flat search is the honest answer.

And where the corpus is highly redundant, several documents covering the same fact, effective recall is higher than measured recall, because missing one near-duplicate costs nothing.

The practical target for most retrieval-augmented generation is recall at the retrieval width of around 0.95, with over-retrieval and reranking absorbing the remainder. Chasing 0.99 typically costs latency out of proportion to the benefit, and the last few percent are usually near-duplicates of what you already returned.