Similarity search answers one question: given a query vector, which stored vectors are closest to it? It is the retrieval step of RAG, semantic search, recommendations and de-duplication, and interviewers probe it because the honest answer is a trade-off, not a lookup. Exact nearest-neighbour search has to compare the query against every stored vector, so at scale every real system uses an approximate index that gives up some recall to buy latency. A Backend / AI engineer is expected to explain what a distance metric means, how HNSW and IVFFlat find neighbours without scanning everything, and how to prove that the approximation is not silently hurting answer quality.
Query q = [1, 0]
doc A = [10, 0] same direction as q, long
doc B = [0.7, 0.7] 45 degrees off, short
doc C = [-1, 0] opposite direction
L2 (Euclidean) : straight-line distance between the points
cosine distance : 1 - cos(angle between vectors) (ignores length)
inner product : q . d (rewards both alignment AND length)
pgvector operators (PostgreSQL, ORDER BY ... ASC = nearest first):
<-> L2 distance
<=> cosine distance
<#> NEGATIVE inner product (negated so ASC still means "best first")# Python 3 (stdlib only) - real output from running the script
query = [1.0, 0.0]
doc L2 cosine_dist neg_inner
A (same direction, long) 9.000 0.000 -10.000
B (45 deg, short) 0.762 0.293 -0.700
C (opposite) 2.000 2.000 1.000
nearest by L2 : B (45 deg, short)
nearest by cosine : A (same direction, long)
nearest by inner product: A (same direction, long)
normalised, L2 : ['A (same direction, long)', 'B (45 deg, short)', 'C (opposite)']
normalised, cosine : ['A (same direction, long)', 'B (45 deg, short)', 'C (opposite)']
normalised, inner product: ['A (same direction, long)', 'B (45 deg, short)', 'C (opposite)']The metric defines what "similar" means, so it changes the answer. L2 punishes doc A for being far away in absolute terms; cosine only looks at direction, so A is a perfect match; inner product rewards both direction and magnitude. Once every vector is scaled to unit length, all three give the same ranking, because L2 distance squared equals 2 - 2 * cosine similarity and the inner product equals the cosine. That is why many embedding providers return normalised vectors: you can then use the cheapest operator (inner product) without changing results. The rule of thumb is to use the metric the embedding model was trained with, and do not mix metrics between the index and the query.
Exact (brute force) nearest neighbour:
cost per query = N vectors x D dimensions (no index can skip anything
without risking a miss)
20,000 vectors x 64 dims = 1,280,000 multiply-adds per query (real, from the script)
At 10M vectors x 1536 dims that is ~15 billion multiply-adds per query.
Approximate (ANN) search:
look at a SMALL, well-chosen candidate set, rank only that
result = top-k of the candidates -> may miss a true neighbour
recall@k = |ANN top-k intersect exact top-k| / k# Python 3 toy IVF (k-means lists) - real output
# 4000 vectors, 16 dims, 20 lists, recall@10 averaged over 200 queries
probes recall@10 vectors scanned/query fraction of corpus
1 0.941 265 6.63%
2 0.978 555 13.87%
4 0.997 1089 27.23%
8 1.000 2044 51.11%
20 1.000 4000 100.00%Every ANN index is a knob between recall and work. Probing one list scans about 7% of the corpus and finds 94% of the true top-10; probing all lists degenerates into exact search with perfect recall and no saving. The table counts vectors scanned rather than seconds, because that count is what latency tracks, and the numbers come from a small synthetic, well-clustered dataset: real embeddings are generally less cleanly clustered, so expect lower recall at the same fraction of the corpus scanned. The general lesson is that recall is a measured property of a specific index, dataset and parameter setting, never a constant.
IVFFlat (inverted file, "flat" = full vectors stored)
BUILD : k-means over a sample -> `lists` centroids
each vector goes into the list of its nearest centroid
QUERY : find the `probes` closest centroids, scan ONLY those lists
centroid 1 [ v v v v ] <- scanned
centroid 2 [ v v v ]
centroid 3 [ v v v v v ] <- scanned (2nd closest)
A true neighbour sitting in an unprobed list is missed.
HNSW (hierarchical navigable small world graph)
layer 2: o-----------------o few nodes, long hops
layer 1: o-----o-----o-----o-----o more nodes, medium hops
layer 0: o-o-o-o-o-o-o-o-o-o-o-o-o-o-o ALL nodes, short hops
QUERY : enter at the top, greedily hop to the neighbour closest to the
query, drop a layer when no neighbour is closer, repeat;
at layer 0 keep a candidate list of size ef_search.-- PostgreSQL + pgvector (not run locally; behaviour described in prose below)
CREATE EXTENSION IF NOT EXISTS vector;
CREATE TABLE chunks (
id bigserial PRIMARY KEY,
doc_id bigint NOT NULL,
content text NOT NULL,
embedding vector(1536) NOT NULL
);
-- HNSW: graph index. m = links per node, ef_construction = build-time candidate list
CREATE INDEX chunks_hnsw ON chunks
USING hnsw (embedding vector_cosine_ops) WITH (m = 16, ef_construction = 64);
SET hnsw.ef_search = 40; -- query-time candidate list: bigger = better recall, slower
-- IVFFlat: cluster index. Build it AFTER the table has representative data.
CREATE INDEX chunks_ivf ON chunks
USING ivfflat (embedding vector_cosine_ops) WITH (lists = 100);
SET ivfflat.probes = 10; -- lists scanned per query
-- The query shape the index can serve: ORDER BY distance, LIMIT k
SELECT id, content, embedding <=> $1 AS cosine_distance
FROM chunks
ORDER BY embedding <=> $1
LIMIT 5;IVFFlat is cheap to build and small, but its centroids are learned from the data present at build time; if the data drifts or the table was empty when you built it, the partitions are poor and recall suffers until you rebuild. HNSW builds slower and uses more memory, but it absorbs inserts without retraining and generally gives a better recall-versus-latency curve, which is why it is the common default in pgvector. In both, the query only uses the index for the pattern ORDER BY embedding <op> query LIMIT k with the operator matching the index's operator class; a mismatched operator, or no LIMIT, falls back to a sequential scan that is exact but slow.
Question 1: Is the ANN index faithful to exact search? (index quality)
ground truth = exact top-k by brute force on a sample of real queries
metric = recall@k = |ANN top-k intersect exact top-k| / k
knobs = ef_search / probes / m / lists
Question 2: Does the exact top-k contain what the user needed? (retrieval quality)
ground truth = labelled (query -> relevant chunk ids) pairs
hit rate@k = fraction of queries with >= 1 relevant chunk in top-k
MRR = mean of 1 / (rank of first relevant chunk)
nDCG@k = rank-aware, supports graded relevance
Worked MRR example (3 queries): first relevant chunk at rank 1, 3, 2
MRR = (1/1 + 1/3 + 1/2) / 3 = 0.611These are separate failure modes and mixing them up is the classic mistake. If recall@10 against exact search is 0.99 but hit rate against human labels is low, the index is fine and the problem is upstream: chunking, the embedding model, missing metadata filters, or a query that needs keyword matching. Conversely, a great embedding model behind a badly tuned index loses good answers silently, with no error to alert you. Tune the index against exact search first, then evaluate the whole pipeline (including any reranker and the generated answer) against labelled queries.
<-> L2 distance, <=> cosine distance, <#> negative inner product. Use the metric the embedding model was trained for, and make the index operator class match the query operator.probes lists: small and fast to build, recall depends on the data present at build time. HNSW = layered graph with ef_search: slower build, more memory, generally better recall per unit of latency and tolerant of inserts.ef_search or probes buys recall at the price of latency; there is no free setting, and the right point depends on the product's tolerance for a missed result.ORDER BY distance LIMIT k shape. With filters (WHERE) the planner may apply the filter after the ANN scan, returning fewer than k rows; check the pgvector version's filtering and iterative-scan options.probes clusters, HNSW by greedy graph traversal across layers.ef_search, probes, m or lists until the recall-latency point meets the requirement; a data-distribution change may require a rebuild (IVFFlat especially).# metrics.py - save and run: python3 metrics.py (stdlib only; output is in the blocks above)
import math, random
def l2(a, b): return math.sqrt(sum((x - y) ** 2 for x, y in zip(a, b)))
def dot(a, b): return sum(x * y for x, y in zip(a, b))
def norm(a): return math.sqrt(dot(a, a))
def cosine_dist(a, b): return 1 - dot(a, b) / (norm(a) * norm(b))
def neg_ip(a, b): return -dot(a, b) # what pgvector's <#> returns
q = [1.0, 0.0]
docs = {"A (same direction, long)": [10.0, 0.0],
"B (45 deg, short)": [0.7, 0.7],
"C (opposite)": [-1.0, 0.0]}
print(f"query = {q}")
print(f"{'doc':26} {'L2':>7} {'cosine_dist':>12} {'neg_inner':>10}")
for name, d in docs.items():
print(f"{name:26} {l2(q,d):7.3f} {cosine_dist(q,d):12.3f} {neg_ip(q,d):10.3f}")
for label, key in (("L2", l2), ("cosine", cosine_dist), ("inner product", neg_ip)):
order = sorted(docs, key=lambda n: key(q, docs[n]))
print(f"nearest by {label:13}: {order[0]}")
# unit-normalised vectors: the three metrics agree on the ranking
def unit(v): n = norm(v); return [x / n for x in v]
u = {n: unit(v) for n, v in docs.items()}
uq = unit(q)
for label, key in (("L2", l2), ("cosine", cosine_dist), ("inner product", neg_ip)):
print(f"normalised, {label:13}:", sorted(u, key=lambda n: key(uq, u[n])))
# brute-force cost: exact search touches every vector
random.seed(7)
N, D = 20000, 64
data = [[random.gauss(0, 1) for _ in range(D)] for _ in range(N)]
qv = [random.gauss(0, 1) for _ in range(D)]
ops = N * D
print(f"exact scan: {N} vectors x {D} dims = {ops} multiply-adds per query")
best = min(range(N), key=lambda i: l2(qv, data[i]))
print("exact nearest neighbour id:", best)
# ivf.py - save and run: python3 ivf.py (toy IVF; try changing LISTS or the 1.5 noise term
# and watch recall at probes=1 fall as the clusters overlap more)
import math, random
random.seed(42)
D, CLUSTERS, PER, LISTS, K = 16, 40, 100, 20, 10
def l2sq(a, b): return sum((x - y) ** 2 for x, y in zip(a, b))
def mean(vs): return [sum(c) / len(vs) for c in zip(*vs)]
# synthetic corpus: 40 loose blobs of 100 points -> 4000 vectors
centers = [[random.gauss(0, 3) for _ in range(D)] for _ in range(CLUSTERS)]
data = [[c + random.gauss(0, 1.5) for c in ctr] for ctr in centers for _ in range(PER)]
queries = [[c + random.gauss(0, 1.5) for c in random.choice(centers)] for _ in range(200)]
# IVF build = k-means (a few Lloyd iterations), then assign every vector to its nearest centroid
cents = random.sample(data, LISTS)
for _ in range(8):
buckets = [[] for _ in range(LISTS)]
for v in data:
buckets[min(range(LISTS), key=lambda i: l2sq(v, cents[i]))].append(v)
cents = [mean(b) if b else cents[i] for i, b in enumerate(buckets)]
lists = [[] for _ in range(LISTS)]
for idx, v in enumerate(data):
lists[min(range(LISTS), key=lambda i: l2sq(v, cents[i]))].append(idx)
def exact(q): return set(sorted(range(len(data)), key=lambda i: l2sq(q, data[i]))[:K])
def ivf(q, probes):
order = sorted(range(LISTS), key=lambda i: l2sq(q, cents[i]))[:probes]
cand = [i for l in order for i in lists[l]]
return set(sorted(cand, key=lambda i: l2sq(q, data[i]))[:K]), len(cand)
truth = [exact(q) for q in queries]
print(f"{len(data)} vectors, {LISTS} lists, recall@{K} averaged over {len(queries)} queries")
print(f"{'probes':>6} {'recall@10':>10} {'vectors scanned/query':>22} {'fraction of corpus':>19}")
for probes in (1, 2, 4, 8, 20):
rec, scanned = 0.0, 0
for q, t in zip(queries, truth):
got, n = ivf(q, probes)
rec += len(got & t) / K
scanned += n
rec /= len(queries); scanned /= len(queries)
print(f"{probes:>6} {rec:>10.3f} {scanned:>22.0f} {scanned/len(data):>19.2%}")
-- PostgreSQL + pgvector: an experiment to run on your own instance
-- (no output is shown here because none was produced locally)
CREATE EXTENSION IF NOT EXISTS vector;
CREATE TABLE items (id serial PRIMARY KEY, label text, embedding vector(3));
INSERT INTO items (label, embedding) VALUES
('A long, same direction', '[10,0,0]'),
('B short, 45 degrees', '[0.7,0.7,0]'),
('C opposite', '[-1,0,0]');
-- Compare the three operators against the query [1,0,0]:
SELECT label,
embedding <-> '[1,0,0]' AS l2,
embedding <=> '[1,0,0]' AS cosine_distance,
(embedding <#> '[1,0,0]') * -1 AS inner_product
FROM items;
-- Expected: the same relationships as the Python demo (L2 prefers B, cosine and
-- inner product prefer A); exact numeric formatting depends on the pgvector version.
-- Check whether the planner uses an index (only meaningful with many rows):
EXPLAIN SELECT id FROM items ORDER BY embedding <=> '[1,0,0]' LIMIT 2;
-- With 3 rows the planner will generally choose a sequential scan even if an
-- index exists; try again with 100k+ rows to see an index scan.
-- Measure recall yourself: run the query with the index, then with the index
-- disabled for that session (SET enable_indexscan = off;) and compare id sets.Q: How does vector similarity search work?
A: Text, images or other items are converted by an embedding model into fixed-length vectors, and semantically similar items land near each other in that space. A query is embedded the same way, and the database returns the stored vectors with the smallest distance to it under a metric such as cosine, L2 or inner product. Exact search scores every vector, so at scale you use an approximate index (HNSW or IVFFlat) that inspects a small candidate set, trading a little recall for large latency savings.
Q: How would you evaluate retrieval quality?
A: In two layers. First measure how faithful the index is: recall@k of the ANN result against brute-force exact results on a sample of real queries, and tune ef_search / probes until that is acceptable. Then measure whether the exact top-k actually contains the right content using a labelled set of query-to-relevant-chunk pairs with hit rate@k, MRR or nDCG, and, for RAG, check the final answer quality separately. The trade-off is labelling cost: a small, curated, regularly refreshed set is far more useful than none, and it lets you compare chunking, embedding models and hybrid search changes objectively.
Q: What is the difference between exact and approximate nearest neighbour search, and when would you use each?
A: Exact search compares against every vector, so it is always correct and needs no index or tuning, but the cost is linear in N times D per query. Approximate search uses a structure (graph or clusters) to look at a fraction of the data and may miss a true neighbour. Exact is the right choice for small tables (tens of thousands of rows), for building the ground truth used to measure recall, and where a miss is unacceptable; ANN is the right choice once brute-force latency or CPU cost breaks the budget.
Q: How do you reason about the recall versus latency trade-off?
A: Each index exposes a knob (ef_search for HNSW, probes for IVFFlat) that widens the search: more candidates examined means higher recall and higher latency, with diminishing returns as recall approaches 1.0. You pick the smallest setting that meets a recall target measured on your data, because the curve depends on the dataset, dimensionality and index build parameters. Missing a low-ranked neighbour barely matters for a "related articles" widget, while a compliance search may justify a much higher setting or exact search.
Follow-up: Cosine similarity and inner product give different results on my data. Why?
A: Cosine ignores vector length, inner product does not, so they only agree when vectors are normalised. If some vectors have larger norms (for example from a model that encodes confidence or document length in magnitude), inner product will favour them. Check whether the model's vectors are normalised, and use the metric the model was trained with; storing normalised vectors and using inner product is a common performance optimisation that keeps cosine semantics.
Follow-up: I added a WHERE clause and the query now returns fewer than k rows. Why?
A: In pgvector the ANN index typically returns a bounded candidate set (governed by ef_search for HNSW) and the WHERE filter is applied to those candidates afterwards, so a selective filter can leave fewer than k rows, or none. Options are raising ef_search, using iterative index scans where the installed pgvector version supports them, partial or partitioned indexes for common filters, or filtering first with a regular index when the filter is highly selective. Each has a cost: a bigger candidate set is slower, partitioning multiplies indexes to maintain.
Follow-up: HNSW recall dropped after months of updates and deletes. What would you check?
A: Compare current ANN results with exact search on a query sample to confirm the drop is real and not a data or embedding-model change. Then check for heavy deletes and updates leaving dead tuples (run VACUUM, and consider REINDEX to rebuild the graph), whether ef_search was reset to the default in a new connection or pool, and whether the query distribution changed. The trade-off is that a rebuild costs time and memory, so schedule it, and monitor recall on an ongoing sample rather than discovering degradation from user complaints.
In a RAG system the vector index sits on the latency-critical path of every user question, so its parameters become part of the service's SLO: a target recall@k on a fixed evaluation set, and a p95 latency budget for the retrieval hop. pgvector inside PostgreSQL keeps vectors next to relational metadata (tenant, document version, ACLs), which makes filtered queries and transactional updates simple, while a dedicated vector store may scale further and offer richer filtering at the price of a second system to keep consistent. Memory is the practical limit for HNSW: the graph and vectors should generally fit in RAM for good latency, so capacity planning is dimension times row count times bytes per component, plus graph overhead, and options such as lower-dimension embeddings, half-precision or quantised vectors, and partitioning by tenant reduce it. Any design should also include the evaluation harness described above, run whenever the embedding model, chunking strategy or index parameters change, because those changes all move recall without producing errors.
The decision is to accept approximate answers in exchange for sub-linear query time, and the cost is that recall becomes a tunable, data-dependent property you must measure instead of assume. HNSW spends build time and RAM for good recall and insert tolerance; IVFFlat spends less memory but needs representative data at build time and a probes setting tuned per workload; higher ef_search or probes spends latency for recall. An ANN index is the wrong choice for small tables where a sequential scan is fast and exact, for workloads where a missed result has serious consequences and exact search is affordable, and for queries dominated by a highly selective filter where a normal B-tree index followed by an exact distance sort on the few matching rows is both faster and perfectly accurate.