“How does vector search work, and how would you choose an index?” appears in almost every AI engineering loop, usually right after “how would you build a RAG system”. Interviewers want three things: that you know what an embedding represents and what it does not, that you can explain why exact nearest neighbour search does not scale and what approximate indexes give up, and that you know when semantic similarity is the wrong tool. The last part separates people who have shipped search from people who have only read about it.
Before you start
You should be comfortable with Python lists and functions and with the idea of a vector as a list of numbers. High-school geometry (the angle between two arrows) is enough for cosine similarity. The examples use Python 3.12+ and the standard library; they build a tiny inverted-file (IVF) index from scratch so you can see the recall trade-off instead of taking it on faith. No embedding API is called: random vectors stand in for real embeddings.
The short answer
An embedding model turns text (or images) into a fixed-length vector, trained so that inputs with similar meaning end up close together. To search, you embed every document chunk once, store the vectors, embed the query with the same model, and return the nearest vectors, usually by cosine similarity. Comparing the query with every vector is exact but linear in the corpus size, so production systems use approximate nearest neighbour (ANN) indexes such as HNSW graphs or IVF clusters, which inspect a small fraction of vectors and occasionally miss a true neighbour. Because embeddings capture meaning rather than exact strings, most systems combine them with keyword search (BM25) and rerank the merged candidates.
How it works
Cosine similarity measures the angle between vectors and ignores their length. If you normalize every vector to length 1, cosine similarity becomes a plain dot product, and the squared Euclidean distance becomes 2 - 2 * cosine, so all three metrics produce the same ranking. That is why many vector stores ask you to pick one metric and normalize up front.
import math, random
def normalize(v):
n = math.sqrt(sum(x * x for x in v))
return [x / n for x in v]
def dot(a, b):
return sum(x * y for x, y in zip(a, b))
def cosine(a, b):
return dot(a, b) / (math.sqrt(dot(a, a)) * math.sqrt(dot(b, b)))
a, b = [3.0, 4.0], [6.0, 8.0]
print(round(cosine(a, b), 4), dot(a, b), round(dot(normalize(a), normalize(b)), 4))
# 1.0 50.0 1.0 -> same direction: cosine 1, raw dot product depends on lengthExact search scores every vector. With a million 1,024-dimensional vectors that is about a billion multiply-adds per query: fine for a batch job, too slow and too costly for interactive traffic at high query rates. ANN indexes avoid most of that work:
- IVF (inverted file) clusters the vectors with k-means. A query is compared with the cluster centroids, and only the
n_probeclosest clusters are scanned. - HNSW (hierarchical navigable small world) builds a layered proximity graph. A search starts at a coarse layer and greedily walks toward the query, keeping a candidate list whose size (
ef_search) controls the recall and latency trade-off. It is fast and accurate but memory-hungry. - Product quantization (PQ) compresses vectors into short codes so more of them fit in memory, at some cost in accuracy. It is often combined with IVF.
Step-by-step walkthrough
Step 1: Build exact search as the ground truth
def exact_top_k(query, vectors, k):
return sorted(range(len(vectors)), key=lambda i: dot(query, vectors[i]), reverse=True)[:k]Every ANN evaluation starts here. Exact search is the reference that tells you what the approximate index missed.
Step 2: Build a small IVF index
class IVFIndex:
"""Cluster the vectors, then search only the clusters closest to the query."""
def __init__(self, vectors, n_lists, rng, iterations=5):
self.vectors = vectors
self.centroids = rng.sample(vectors, n_lists)
for _ in range(iterations):
lists = self._assign()
self.centroids = [
normalize([sum(col) / len(ids) for col in zip(*(vectors[i] for i in ids))]) if ids else c
for ids, c in zip(lists, self.centroids)
]
self.lists = self._assign()
def _assign(self):
lists = [[] for _ in self.centroids]
for i, v in enumerate(self.vectors):
best = max(range(len(self.centroids)), key=lambda c: dot(v, self.centroids[c]))
lists[best].append(i)
return lists
def search(self, query, k, n_probe):
nearest = sorted(range(len(self.centroids)),
key=lambda c: dot(query, self.centroids[c]), reverse=True)[:n_probe]
candidates = [i for c in nearest for i in self.lists[c]]
best = sorted(candidates, key=lambda i: dot(query, self.vectors[i]), reverse=True)[:k]
return best, len(candidates)Building the index costs a few passes over the data; each query then scores 30 centroids plus the members of the probed clusters instead of all 3,000 vectors.
Step 3: Measure recall@10 against exact search
def measure(vectors, queries, index):
for n_probe in (1, 3, 10, 30):
hits, scanned = 0, 0
for q in queries:
truth = set(exact_top_k(q, vectors, 10))
found, n = index.search(q, 10, n_probe)
hits += len(truth & set(found)); scanned += n
print(f"n_probe={n_probe:2d} recall@10={hits / (10 * len(queries)):.2f} scanned={scanned // len(queries)}")
rng = random.Random(42)
dim, n = 32, 3000
# Case A: vectors spread uniformly on the sphere (no topic structure)
vectors = [normalize([rng.gauss(0, 1) for _ in range(dim)]) for _ in range(n)]
queries = [normalize([rng.gauss(0, 1) for _ in range(dim)]) for _ in range(50)]
measure(vectors, queries, IVFIndex(vectors, n_lists=30, rng=rng))
# n_probe= 1 recall@10=0.22 scanned=101
# n_probe= 3 recall@10=0.46 scanned=299
# n_probe=10 recall@10=0.81 scanned=999
# n_probe=30 recall@10=1.00 scanned=3000Step 4: Repeat with clustered data, like real embeddings
Real text embeddings are not uniform; documents about the same topic form clusters. Generating vectors around 40 topic centres changes the picture completely:
rng = random.Random(42)
topics = [[rng.gauss(0, 1) for _ in range(dim)] for _ in range(40)]
vectors = [normalize([c + rng.gauss(0, 0.6) for c in rng.choice(topics)]) for _ in range(n)]
queries = [normalize([c + rng.gauss(0, 0.6) for c in rng.choice(topics)]) for _ in range(50)]
measure(vectors, queries, IVFIndex(vectors, n_lists=30, rng=rng))
# n_probe= 1 recall@10=0.98 scanned=129
# n_probe= 3 recall@10=1.00 scanned=327Same index, same settings, completely different recall. The lesson for an interview: index parameters cannot be chosen from a blog post. You sample real queries, compute exact neighbours offline, and tune n_probe or ef_search until recall meets your target at acceptable latency.
Worked scenario
An electronics retailer launches semantic search for its support site. Questions like “my headphones keep disconnecting” work well. Then the support team reports that searching for the part number “XR-2041” returns the XR-2040 manual first and buries the XR-2041 recall notice. The embedding model sees “XR-2040” and “XR-2041” as nearly identical strings in an almost identical context, which is exactly what it was trained to do. Exact identifiers, error codes, version numbers and rare names are where pure vector search is weakest.
The fix is hybrid retrieval: run BM25 (or another keyword index) alongside the vector index and merge the two rankings. Reciprocal rank fusion is the usual first choice because it needs no score calibration between the two systems:
def reciprocal_rank_fusion(rankings, k=60):
scores = {}
for ranking in rankings:
for rank, doc_id in enumerate(ranking, start=1):
scores[doc_id] = scores.get(doc_id, 0.0) + 1 / (k + rank)
return sorted(scores, key=scores.get, reverse=True)
vector_hits = ["XR-2040 manual", "XR series overview", "XR-2041 manual", "Charger guide"]
keyword_hits = ["XR-2041 manual", "XR-2041 recall notice"]
print(reciprocal_rank_fusion([vector_hits, keyword_hits]))
# ['XR-2041 manual', 'XR-2040 manual', 'XR series overview', 'XR-2041 recall notice', 'Charger guide']The exact manual now ranks first because both systems found it. A cross-encoder reranker on the top 20 to 50 fused candidates would typically lift the recall notice further, since it reads the query and each document together instead of comparing two independent vectors.
Common mistake
- Mixing embedding models or versions. Query and document vectors must come from the same model; upgrading the model means re-embedding the corpus, usually into a new index you switch to atomically.
- Ignoring model-specific input conventions. Some models expect different prefixes or task types for queries and passages. Read the model card.
- Post-filtering after top-k. Retrieving 10 neighbours and then filtering by tenant or date can leave zero results. Use the store’s filtered search or over-fetch.
- Treating similarity scores as probabilities. A cosine of 0.8 is not “80 percent relevant”; score scales differ by model, so calibrate thresholds on labelled data.
- Assuming ANN is exact. Every approximate index has a recall number, and you should know yours.
Verify the behavior
Put recall in a regression test so an index or parameter change cannot silently degrade search:
def test_normalized_metrics_agree():
u, v = normalize([1.0, 2.0, 3.0]), normalize([2.0, 1.0, 0.5])
assert abs(cosine(u, v) - dot(u, v)) < 1e-12
def test_ivf_recall_on_sample_queries():
rng = random.Random(1)
topics = [[rng.gauss(0, 1) for _ in range(32)] for _ in range(40)]
vecs = [normalize([c + rng.gauss(0, 0.6) for c in rng.choice(topics)]) for _ in range(2000)]
qs = [normalize([c + rng.gauss(0, 0.6) for c in rng.choice(topics)]) for _ in range(30)]
index = IVFIndex(vecs, n_lists=20, rng=rng)
hits = sum(len(set(exact_top_k(q, vecs, 10)) & set(index.search(q, 10, 3)[0])) for q in qs)
assert hits / (10 * len(qs)) >= 0.95
test_normalized_metrics_agree(); test_ivf_recall_on_sample_queries(); print("ok")In production, run the same check against a frozen sample of real queries whenever the model, index type or parameters change.
Follow-up questions
HNSW or IVF? HNSW usually gives the best recall at low latency but keeps the full graph and vectors in memory and is slower to build. IVF with PQ uses far less memory and suits very large corpora, at some recall cost. Benchmark both on your data.
Do you need a dedicated vector database? Not always. A relational database with a vector extension, such as pgvector for PostgreSQL, keeps vectors next to the rows they describe and supports filters and transactions. Dedicated stores add scale-out, managed ANN tuning and hybrid search features.
How do you pick an embedding model? Evaluate a few candidates on your own queries with recall@k, considering dimension (storage cost), maximum input length, language coverage and latency. Public leaderboards are a starting shortlist, not a decision.
What does a reranker add? A cross-encoder scores each query and document pair jointly, which is more accurate than comparing separate embeddings but too slow for the whole corpus, so it reorders only the top candidates.
Interview exercise
You index 20 million support documents with HNSW. Recall@10 on your evaluation set is 0.97, but p99 latency is 400 ms against a 100 ms target, and memory use is near the node limit. A teammate proposes doubling the instance size. What else would you try, in what order, and how would you know each change is safe?
Answer and reasoning
First measure where the time goes: query embedding, the ANN search itself, metadata filtering or network. If the search dominates, lower ef_search step by step and plot recall against p99, because the curve is usually flat until a knee. Second, reduce memory: smaller embedding dimensions (some models support truncated dimensions), scalar or product quantization with a rerank of the top candidates using full-precision vectors, or IVF-PQ for the cold part of the corpus. Third, shard by tenant or language so each query searches a smaller index. Each change is validated the same way: the frozen query set with exact neighbours computed offline, plus an end-to-end metric such as answer quality or click-through, and a canary rollout. Doubling the hardware may be the right final step, but only after you know which part of the latency budget it buys.