Nearest neighbour search

Finding the k closest vectors to a query, exactly or approximately, and why approximate is usually the right call.

Also called kNN, brute force, flat search

What: Compare the query with every stored vector and keep the k closest. The result is exact, and the cost grows linearly with the number of vectors.
Why: Perfect recall and no index to build or tune, which is ideal for small collections, filtered subsets and ground truth when evaluating.

SQL

SELECT id, title
FROM docs
ORDER BY embedding <=> $1
LIMIT 5;

Watch out

Assuming this query stays exact once an ANN index exists: Postgres then uses the index, so disable index scans in the session to get ground truth.

Also called ANN

What: Search with an index that visits only a small part of the data and returns most, but not always all, of the true nearest neighbours.
Why: It turns seconds into milliseconds at millions or billions of vectors, and most applications barely notice a missing neighbour or two.

Watch out

Assuming an ANN index returns the same results as exact search; measure how often it does.

Also called k, limit, score threshold

What: k is how many neighbours a query returns. A threshold instead keeps only results closer than a chosen distance.
Why: k controls how much context reaches a reranker or LLM; a threshold stops weak matches from being shown as answers.

Watch out

Setting a fixed threshold once and forgetting it: score ranges differ between models, so it must be re-tuned when the model changes.

What: In high dimensions, distances between random points bunch together and classic space-partitioning structures such as k-d trees stop pruning much.
Why: It explains why vector search needed its own index families such as graphs, clustering and quantisation, instead of reusing B-trees or k-d trees.

Also called recall@k, accuracy

What: The share of the true top k neighbours, found by exact search, that the ANN search also returned. 0.95 means 95 of every 100 true neighbours were found.
Why: It is the one number that tells you what speed is costing in quality, so every tuning decision is made against it.

Watch out

Tuning for latency with no recall measurement at all, then blaming the LLM for poor answers.

What: Below roughly tens of thousands of vectors, or after a filter narrows the candidates to a few thousand, a full scan is often fast enough.
Why: Skipping the index removes build time, memory and recall loss, and keeps the system simpler.
Example: Searching one customer's 3,000 support tickets: filter by customer id with a B-tree index, then compute exact distances on those rows.

Go deeper