Approximate nearest neighbour (ANN) search is how vector databases answer "find the k closest vectors" without comparing the query to every stored vector. Exact search costs work proportional to the corpus size for every query, which is fine for thousands of vectors and painful for hundreds of millions; ANN indexes give up a controlled amount of accuracy (recall) for orders of magnitude less work. Interviewers probe it because the whole topic is a three-way trade-off between recall, latency and memory, and a good answer names the knob that moves each corner, explains how you would measure recall, and knows why high dimensions make the problem intrinsically hard. For a Backend or AI engineer this is the reasoning behind "why is our RAG missing the right chunk", "why did p99 latency triple after the index grew", and "why does this instance need 200 GiB of RAM". The storage and operations side is in Vector Databases; the SQL-level view is in Similarity Search.
Approximate Nearest Neighbor (ANN) search is a fast way to find the items in a huge collection that are most similar to something you are looking for — like finding the ten songs that sound most like a song you just played — without comparing your query against every single item one by one. It trades a small, controlled amount of accuracy (it might miss the single best match once in a while) for a massive speed-up, which is the only way to search collections with millions or billions of items in a fraction of a second.
Imagine trying to find your car in a massive, unsorted parking lot by checking every single row from the entrance — that is exact search, and it works but it is painfully slow once the lot gets big. Now imagine the lot is organized into numbered sections by color and size, so you can walk straight to "red sedans, section 12" and only check the dozen cars there instead of the whole lot. You might occasionally miss the exact closest car if it happens to be parked one section over, but you will find a car that is close enough almost instantly — that is the trade-off approximate nearest neighbor search makes.
Exact (brute-force) k-NN: score = dot(query, v_i) for every stored vector, keep the top k.
work per query = N x d multiply-adds
data read/query = N x d x bytes (memory-bandwidth bound: every byte is touched once)
ILLUSTRATIVE arithmetic, N = 10M, d = 768, float32:
multiply-adds = 10,000,000 x 768 ~ 7.7 billion per query
bytes scanned = 10M x 768 x 4 B ~ 28.6 GiB per query
at an assumed 100 GB/s of usable memory bandwidth -> roughly a quarter of a second per query, per machine
1,000 queries/s would need ~1,000x that bandwidth -> not feasible with a single copy of the data
ANN idea: examine a small, well-chosen candidate set (say 0.1%-5% of N), then score only those exactly.Brute force is not a strawman: it is exact, needs no index, handles filters trivially and is often the right answer below roughly a few hundred thousand vectors, or on a GPU where batching many queries amortises the scan. It stops working because the cost is linear in N and dominated by memory bandwidth, so latency and cost grow with the corpus and throughput requires copying the whole dataset onto more machines. ANN structures cut the number of vectors touched per query to a small fraction of N, at the price of building and storing the structure and occasionally missing a true neighbour. Note the assumptions above are stated, not measured: real throughput depends on hardware, SIMD, batching and quantization.
HNSW (graph) IVF (clusters) PQ (compression) LSH (hashing)
layered proximity graph k-means partitions split vector in m parts, random hyperplanes
code each part by nearest -> bit signature
L2: o-----o centroids * of 256 sub-centroids similar vectors
\ lists: [*: v v v v] (1 byte per part) collide in buckets
L1: o--o--o [*: v v v] 768 floats (3072 B)
| \ | [*: v v v v v] -> e.g. 96 bytes query: hash, look up
L0: o-o-o-o-o-o (all points) query: nearest nprobe distances via lookup buckets, re-score
greedy walk from top layer centroids, scan their tables (approximate) candidates
down; beam width = ef_search lists only usually with re-scoring
memory: vectors + links memory: vectors + centroids memory: small codes only memory: hash tables
recall/latency: usually best cheap to build, easy to combine: IVF-PQ, theory-friendly, less
in RAM; costly to build shard/update; needs HNSW + PQ common as the main
and to update deletes retraining as data drifts index at scale todayThe four families attack different costs. Graph indexes (HNSW) connect each vector to nearby ones across several layers; a query enters at the sparse top layer, greedily moves toward the query, and drops down, finishing with a beam search on the dense bottom layer. They generally deliver the best recall at a given latency when the data fits in RAM, but the graph and the raw vectors both live in memory and construction is slow. Cluster indexes (IVF) run k-means to make nlist partitions and store each vector in its nearest partition's inverted list; a query scans only the nprobe lists whose centroids are closest. They are cheap to build, easy to shard and update, but recall depends entirely on the query's neighbours falling in the probed lists. Quantization (PQ and relatives) does not reduce the number of candidates but shrinks each vector, so the same RAM holds far more of them and distance computation is faster; it is usually combined with IVF or a graph and finished with an exact re-score of the shortlist. LSH hashes vectors so that similar ones collide with high probability; it has strong theory and is simple, but at high recall it typically needs many hash tables, and graph or IVF-based indexes have generally dominated practical vector search.
Knob (engine-specific names) Raises recall by... Costs
-----------------------------------------------------------------------------------------------
HNSW ef_search wider beam at query time latency (more distance evals)
HNSW M (links per node) denser graph, better connectivity memory, build time
HNSW ef_construction better graph quality at build build time only
IVF nprobe scan more lists per query latency (scans more vectors)
IVF nlist (more lists = finer partitions) more centroid compares; needs
more nprobe for same recall
PQ code size / bits / m more bytes per vector = less error memory
Re-score (refine) factor exact-score a longer shortlist latency, needs full vectors
Typical shape of the curve: recall rises steeply at first, then flattens; each extra
0.01 of recall near 1.0 costs disproportionately more work. Pick the point that meets the
product's recall target at the latency SLO, then re-check as data grows.Every ANN index exposes a build-time choice (structure and memory) and a query-time knob (effort). Query-time knobs are the operationally valuable ones because they can be changed per request or per tier without rebuilding: a background batch job can afford ef_search or nprobe high enough to be near-exact, while an interactive path runs lower. The trap is that recall degrades as the index grows if the knob stays fixed, because a larger graph or more lists means the same effort covers a smaller share of the space; capacity planning should re-run the recall measurement whenever the corpus grows by a large factor, and tie it to SLOs (see Capacity Planning & SLOs). Also note that memory and recall interact with cost: quantization shrinks the RAM bill (see Cost Optimization for AI Systems) but a lower recall ceiling has to be recovered with re-scoring.
recall@k = | ANN_top_k INTERSECT exact_top_k | / k (averaged over many queries)
Method:
1. Sample Q representative queries (real traffic if possible, not random vectors).
2. Compute exact top-k by brute force (offline, once; a GPU or a big batch job is fine).
3. Run the ANN index at each setting of the knob; record recall@k, p50/p95/p99 latency, RAM.
4. Plot recall vs latency; choose the knee. Repeat WITH your metadata filters on.
5. Re-run when the corpus, model or dimension changes.
Caveat: ANN recall is NOT end-to-end quality.
recall@10 = 0.95 means 9.5 of the 10 true neighbours are found - the missing ones are the
10th-best-ish ones. For RAG, what matters is whether the chunk that answers the question
is retrieved, so also measure task-level recall@k/MRR/nDCG against labelled questions.The ground truth for ANN is the exact k-NN result under the same distance metric, not human relevance labels: you are measuring how faithfully the index approximates brute force. That separation is useful: first verify the index reproduces exact search (ANN recall), then separately verify that exact search over your embeddings finds the right documents (retrieval quality, which is bounded by the embedding model and the chunking, see Chunking & Embedding Strategies). If the exact search already misses the relevant chunk, no tuning of ef_search helps, and if ANN recall is 0.99 but retrieval quality is poor, tuning the index is wasted effort. Use enough queries for a stable estimate, stratify by filter and query type, and remember that averages hide tails: some queries, especially those near cluster boundaries, can have far lower recall than the mean.
As dimension d grows, for random points the nearest and farthest neighbours become nearly the
same distance away ("distance concentration"):
contrast = (farthest - nearest) / nearest (measured in the demo below)
d=2 : huge contrast -> a space-partitioning tree prunes most of the data
d=32: about 1 -> pruning gets weak
d=1024: about 0.14 -> nearest is barely closer than typical -> partitions cannot exclude much
Why ANN still works on real embeddings: they do not fill the space. Real data lies near a
low-dimensional manifold and has cluster structure ("topics"), so neighbours ARE much closer than
typical points, and partitions/graphs can exploit that. On structureless data ANN needs to scan much more.Classic exact-search structures such as k-d trees prune by splitting on one coordinate at a time, which stops helping somewhere around a few tens of dimensions because the query's distance to the nearest point is comparable to its distance to a partition boundary in many directions at once. Distance concentration explains why ANN methods are approximate by design rather than a temporary compromise: for high-dimensional unstructured data there is no sub-linear exact algorithm that avoids touching most of the data. What rescues practical systems is structure in real embeddings, which the demo below reproduces by comparing structureless random vectors (hard) against vectors scattered around topic centres (easy). It is also why the same index parameters can give very different recall on two datasets, and why you must tune on your own embeddings rather than copy numbers from a benchmark blog.
nprobe nearest lists; cheap to build and shard, but recall depends on where neighbours fall and centroids drift as data changes.ef_search, nprobe) trade latency for recall without rebuilding; build-time knobs (M, ef_construction, nlist, PQ size) trade memory and build time.ef_search, nprobe) set how wide the search is: wider means higher recall and higher latency.A toy IVF index built from scratch: a few rounds of spherical k-means produce 32 centroids over 10,000 seeded 32-dimension unit vectors, each vector goes into its nearest centroid's list, and a query scans only the nprobe closest lists. Recall@10 is measured against brute-force ground truth for 100 queries on two datasets: structureless random vectors and vectors clustered around topic centres. A last block measures distance contrast versus dimension. Standard library only; it runs in roughly 20 seconds. The numbers describe this toy on this synthetic data, not any production engine.
import random, math
random.seed(11)
N, DIM, NLIST, K, NQ = 10000, 32, 32, 10, 100
def unit(v):
n = math.sqrt(sum(x * x for x in v)) or 1.0
return [x / n for x in v]
def gauss_vec(d):
return [random.gauss(0, 1) for _ in range(d)]
def dot(a, b):
return sum(x * y for x, y in zip(a, b))
def make_uniform():
"""Structureless data: unit vectors spread over the sphere."""
data = [unit(gauss_vec(DIM)) for _ in range(N)]
queries = [unit(gauss_vec(DIM)) for _ in range(NQ)]
return data, queries
def make_clustered(n_topics=40, noise=1.0):
"""Structured data: points scatter around topic centres (like real embeddings)."""
centres = [unit(gauss_vec(DIM)) for _ in range(n_topics)]
def sample():
c = random.choice(centres)
return unit([x + noise * random.gauss(0, 1) / math.sqrt(DIM) for x in c])
return [sample() for _ in range(N)], [sample() for _ in range(NQ)]
# ---------- toy IVF: spherical k-means (few iterations) + inverted lists ----------
def kmeans(data, k, iters=5):
cents = [list(v) for v in random.sample(data, k)]
for _ in range(iters):
sums = [[0.0] * DIM for _ in range(k)]
for v in data:
j = max(range(k), key=lambda c: dot(v, cents[c]))
s = sums[j]
for i in range(DIM):
s[i] += v[i]
cents = [unit(s) if any(s) else cents[j] for j, s in enumerate(sums)]
return cents
def build_ivf(data, nlist):
cents = kmeans(data, nlist)
lists = [[] for _ in range(nlist)]
for idx, v in enumerate(data):
lists[max(range(nlist), key=lambda c: dot(v, cents[c]))].append(idx)
return cents, lists
def ivf_search(q, data, cents, lists, k, nprobe):
order = sorted(range(len(cents)), key=lambda c: -dot(q, cents[c]))[:nprobe] # closest clusters
cand = [i for c in order for i in lists[c]] # only scan these
return sorted(cand, key=lambda i: -dot(q, data[i]))[:k], len(cand)
def brute(q, data, k):
return sorted(range(len(data)), key=lambda i: -dot(q, data[i]))[:k]
def evaluate(name, data, queries):
cents, lists = build_ivf(data, NLIST)
sizes = sorted(len(l) for l in lists)
truth = [set(brute(q, data, K)) for q in queries] # exact ground truth
print(f"\n{name}: N={N}, dim={DIM}, nlist={NLIST}, list sizes min/median/max = "
f"{sizes[0]}/{sizes[len(sizes)//2]}/{sizes[-1]}")
print(" nprobe scanned% recall@10")
for nprobe in (1, 2, 4, 8, 16, 32):
rec, scanned = 0.0, 0
for q, t in zip(queries, truth):
got, n_scanned = ivf_search(q, data, cents, lists, K, nprobe)
rec += len(t & set(got)) / K
scanned += n_scanned
print(f" {nprobe:6d} {100*scanned/(NQ*N):7.1f}% {rec/NQ:9.3f}")
evaluate("Structureless (uniform on sphere)", *make_uniform())
evaluate("Clustered (topic-like) data", *make_clustered())
# ---------- curse of dimensionality: distance contrast for random points ----------
print("\nDistance contrast (max-min)/min from a random query to 2000 random points:")
for d in (2, 8, 32, 128, 512, 1024):
pts = [gauss_vec(d) for _ in range(2000)]
q = gauss_vec(d)
ds = [math.dist(q, p) for p in pts]
print(f" dim {d:5d}: contrast = {(max(ds)-min(ds))/min(ds):.3f}")
# Output:
#
# Structureless (uniform on sphere): N=10000, dim=32, nlist=32, list sizes min/median/max = 280/314/350
# nprobe scanned% recall@10
# 1 3.1% 0.191
# 2 6.3% 0.319
# 4 12.5% 0.503
# 8 25.1% 0.738
# 16 50.1% 0.935
# 32 100.0% 1.000
#
# Clustered (topic-like) data: N=10000, dim=32, nlist=32, list sizes min/median/max = 89/264/655
# nprobe scanned% recall@10
# 1 3.5% 0.915
# 2 6.7% 0.982
# 4 12.7% 0.991
# 8 25.6% 0.998
# 16 50.5% 1.000
# 32 100.0% 1.000
#
# Distance contrast (max-min)/min from a random query to 2000 random points:
# dim 2: contrast = 97.339
# dim 8: contrast = 5.781
# dim 32: contrast = 1.067
# dim 128: contrast = 0.404
# dim 512: contrast = 0.227
# dim 1024: contrast = 0.139Reading the output: on structureless data IVF behaves like sampling, with recall about equal to the fraction of the corpus scanned (0.503 recall at 12.5% scanned, 0.935 at 50%), which is the curse of dimensionality in action. On clustered data, one probe scanning 3.5% of the vectors already reaches 0.915 recall and four probes reach 0.991, because neighbours mostly share a list; the residual misses are queries near a list boundary. In production the same experiment runs against a real engine's parameters, for example (labelled configuration, not run here):
# pgvector (PostgreSQL), query-time knob for HNSW; check current docs for defaults and ranges
SET hnsw.ef_search = 100; -- wider beam: higher recall, higher latency
# IVFFlat: SET ivfflat.probes = 10; -- this is nprobe
# Build-time: CREATE INDEX ... USING hnsw (embedding vector_cosine_ops) WITH (m = 16, ef_construction = 64);
# Then measure recall@10 against an exact scan of the same queries (disable the index or use a plain sequential scan)
# at each setting, and keep the cheapest setting that meets your target. No output is invented here.Q: Why can't we just use exact nearest-neighbour search at scale?
A: Exact search compares the query to every vector, so per-query work and memory traffic grow linearly with the corpus: about 28.6 GiB scanned per query for 10M x 768 float32 (ILLUSTRATIVE). Serving many queries per second then needs many full copies of the data. It is still right for small collections, for ground truth, and for very selective filters where the matching set is small.
Q: Explain HNSW in an interview-sized answer.
A: HNSW is a stack of proximity graphs: sparse upper layers act like express lanes and the bottom layer contains every vector. A query starts at the top, greedily moves to the neighbour closest to the query, drops a layer, and at the bottom runs a best-first search with a candidate list of size ef_search. Higher ef_search or M improves recall at the cost of latency or memory; it also has slow builds and awkward deletes.
Q: How does IVF work and when does it lose recall?
A: K-means splits the space into nlist cells and each vector is filed under its nearest centroid; a query scans only the nprobe nearest cells. It loses recall when the query's true neighbours sit in a cell that was not probed, typically near boundaries or when the data is unstructured, and when data drift makes the centroids stale so lists become unbalanced. Fixes: raise nprobe, retrain centroids periodically, or use more, smaller cells with more probes.
Q: What does product quantization buy you, and what does it cost?
A: It splits each vector into subvectors and stores each as a one-byte code pointing into a small codebook, so a 3072-byte float32 vector can shrink to on the order of 100 bytes (about 30x, depending on configuration). That lets far more vectors fit in RAM and makes distance evaluation fast via lookup tables. The cost is quantization error, so ordering near the top-k is noisy; systems recover accuracy by re-scoring a shortlist with full-precision vectors.
Q: How do you measure recall for an ANN index?
A: Compute exact top-k with brute force for a representative sample of queries, run the index, and average |ANN top-k intersect exact top-k| / k. Report it next to p95 and p99 latency for each setting of the effort knob, do it with your production filters, and repeat when the corpus grows or the embedding model changes. Separately measure retrieval quality against labelled relevance, since ANN recall only says the index matches brute force.
Q: Recall at k=10 is 0.95. Is that good enough for RAG?
A: It depends on what is missed. Losing the 8th-best neighbour barely matters when you send the top 5 chunks to a reranker or model, but if the single answer-bearing chunk is often the one missed, the end-to-end result suffers. Measure task-level retrieval (recall@k, MRR) on labelled questions and consider retrieving more candidates (top 50) and reranking, which tolerates a lower ANN recall.
Follow-up: Recall dropped after the index doubled in size. Why, and what do you do?
A: Fixed search effort covers a smaller share of a larger space: a fixed nprobe scans the same number of lists while each holds more vectors and neighbours spread over more of them, and a fixed ef_search explores the same beam in a bigger graph. Re-measure against ground truth, raise the effort knob (paying latency), rebuild with better parameters, or shard so each index stays small. Alert on recall from a canary query set.
Follow-up: Why not always use HNSW?
A: It is memory-hungry (vectors plus links live in RAM for best speed), slow to build, and awkward for heavy deletes and updates; with billions of vectors the RAM bill can dominate. IVF-PQ or disk-based graph indexes trade some recall or latency for much lower memory. Choose by corpus size, update rate, RAM budget and recall target, and benchmark on your embeddings.
Follow-up: Does higher embedding dimension always improve retrieval?
A: No. More dimensions can capture more nuance but cost linear memory and compute, make distances more concentrated, and may not help a given task; some embedding models allow reduced-dimension outputs that keep most quality at a fraction of the cost. Evaluate retrieval quality at several dimensions and pick the smallest that meets the target.
ANN choices drive the sizing slide in any RAG, semantic-search or recommendation design (see Retrieval-Augmented Generation and Design a RAG-Based Support Chatbot). State your assumptions and reason aloud: for 20M chunks at 768 dimensions float32 the raw vectors are about 57 GiB (ILLUSTRATIVE), an HNSW index holds those in RAM plus links, and replicas for availability multiply it; if the budget is tighter, quantize to int8 or PQ and add a re-score stage. Pick a recall target (for example recall@10 of at least 0.95 at a p99 retrieval budget of a few tens of milliseconds, both assumptions to be validated), then tune the effort knob on a labelled query set. Retrieve wide and rerank narrow (top 50 to 100 candidates ANN, top 5 to 10 after a reranker) so that imperfect ANN recall is absorbed by the reranker. Note the operational hooks: canary queries that track recall over time, rebuild or compaction schedules, embedding-model version tracked per index, and the cost line from RAM and re-embedding.
The decision is how much accuracy to trade for latency and memory, and on which knob. Higher recall costs superlinearly near the top of the curve, so the wrong choice is chasing 0.99 recall for a pipeline whose reranker and LLM will not notice the last few percent, and equally wrong is tuning latency with a fixed setting and never re-measuring recall as data, filters and models change. Graph indexes buy speed with RAM and build time; cluster indexes buy cheap builds and easy sharding with recall sensitivity and centroid maintenance; quantization buys capacity with error you must repair by re-scoring. Approximate search is also the wrong tool when exactness is a requirement (small corpora, legal or dedup checks, ground-truth evaluation) or when filters are so selective that scanning the matching rows exactly is cheaper than navigating an index. Finally, benchmarks on public datasets say little about your embeddings, dimensions and filters, so the durable practice is to keep a labelled query set, an exact-baseline job, and dashboards for recall and tail latency.