Nearest-neighbour search

Now that we can score similarity, searching sounds easy: compare the query with every stored vector and keep the best ones. That is k-nearest-neighbour (kNN) search — find the k closest vectors — and the straightforward way to do it is called brute-force or flat search.

Brute force, step by step

1. Turn the query into a vector.
2. Compute its similarity to every stored vector.
3. Keep the top k (say, 5) scores.
4. Return those items.

type Item = { id: string; vector: number[] };

const dot = (a: number[], b: number[]) => a.reduce((s, x, i) => s + x * b[i], 0);

function searchFlat(items: Item[], query: number[], k: number) {
  return items
    .map((item) => ({ id: item.id, score: dot(item.vector, query) })) // vectors normalised → dot = cosine
    .sort((a, b) => b.score - a.score)
    .slice(0, k);
}

This is exact: it always returns the true nearest neighbours. For small collections it is also perfectly fast — which is why brute force is a legitimate choice, not just a teaching example.

Why it stops scaling

Each comparison costs one multiplication and one addition per dimension. The cost of one query is:

work per query ≈ number of vectors × dimensions

Modern CPUs are fast, so a few million operations take well under a millisecond. Hundreds of millions per query — multiplied by many queries per second — is a different story. The cost also grows linearly: ten times more data means ten times slower search.

The trade-off: exact vs approximate

Vector databases escape the linear cost with approximate nearest-neighbour (ANN) search. Instead of checking everything, an index guides the search to the region where the best matches probably are, and checks only a small fraction of vectors.

The price is that ANN might occasionally miss one of the true nearest neighbours. We measure this with recall:

recall@k = (how many of the true top-k the search returned) ÷ k

If the true top 10 contains items 1–10 and your search returns nine of them plus one slightly worse item, recall@10 is 0.9.

Is "approximate" good enough?

Usually, yes. Embeddings are themselves an approximation of meaning, so the "true" 10th-nearest neighbour isn't meaningfully better than the 11th. For RAG and semantic search, a recall of 0.95 is typically indistinguishable to users from 1.0 — while being many times faster.

When exactness does matter (small collections, legal or compliance search, or as a ground truth for testing), use flat search.

When to use which

The next section explains how ANN indexes work, starting with the general idea in Approximate search.

Written by Bipin Singh

Senior Full-Stack Engineer · AI & AWS. I build production search, RAG and AI systems on AWS and Postgres.

Work with me