Vector Database Interview Questions: From HNSW to Billion-Scale Serving

Vector search used to be a specialist topic. It is now a standard part of system design loops at FAANG (Facebook/Meta, Apple, Amazon, Netflix, Google) and at AI-first companies like Anthropic, OpenAI and Nvidia, because almost every retrieval-augmented feature shipped in the last two years sits on top of one.

The questions are rarely "what is a vector database". They are closer to: you have 500 million embeddings, 50ms of latency budget, and results have to respect per-user permissions — design it. This guide covers what interviewers are actually testing, the specific tradeoffs they push on, and where candidates most often lose the round.

Why vector database questions entered interview loops

Three things happened at once. Embedding models got cheap enough to run over entire corpora. Retrieval-augmented generation became the default architecture for grounding a language model in private data. And the resulting indexes got big enough that naive approaches stopped working.

That last point is what makes it an interview question. Searching a million vectors by brute force is a for-loop. Searching a billion of them, under a latency budget, with filters, while the corpus is being updated, is a system design problem with real tradeoffs — which is exactly what an interviewer wants to watch you navigate.

If you have not worked with one in production, the fastest way in is to build the naive version first: our brute-force vector similarity search question is the baseline every index is an optimisation over, and cosine similarity is the primitive underneath it.

What interviewers are actually testing

Across reported loops, the probes cluster into five areas:

Notice what is absent: nobody is asking you to recall the HNSW paper's pseudocode. The signal is whether you can pick a configuration and defend it against a stated requirement.

The index is the interview: flat, IVF, and HNSW

Every vector index answers the same question — find the k nearest vectors to this query — and they differ in what they give up to go faster.

Flat (exhaustive) compares the query against every vector. Recall is exactly 100% because it is not an approximation; it is the ground truth other indexes are measured against. Latency scales linearly with corpus size. For a few hundred thousand vectors this is genuinely fine, and saying so is a good signal: it shows you size the solution to the problem.

IVF (inverted file) clusters vectors into a few thousand buckets, keeps a centroid per bucket, and at query time searches only the nprobe buckets whose centroids are closest. Build is cheap, memory is modest, and nprobe is the accuracy dial. Its weakness is the cluster boundary: a genuine nearest neighbour sitting just outside the probed buckets is invisible, and no amount of scanning within those buckets recovers it.

HNSW (hierarchical navigable small world) builds a layered proximity graph and greedily walks it from a sparse top layer down to a dense bottom one. It is usually the strongest latency-versus-recall tradeoff at high recall, which is why it is the default in most vector databases. The costs are real: the graph holds roughly M neighbour links per vector per layer, so memory is substantially higher than IVF, and build time is longer.

Recall is a dial, not a property

This is the concept that separates candidates who have run a vector index from those who have read about one.

Recall@k is the fraction of the true k nearest neighbours that your approximate search actually returned, measured against a flat index over the same data. It is not fixed by your choice of index — it is set by the parameters you choose, and every point of recall costs latency.

The dials worth knowing by name:

• HNSW efSearch — how many candidates the graph walk keeps in its frontier. Raising it raises recall and latency, at query time, with no rebuild. This is the runtime dial.
• HNSW M — neighbours per node. Higher means a better-connected graph and higher recall ceiling, at higher memory and build cost. Fixed at build time.
• IVF nprobe — buckets searched per query. Same shape of tradeoff as efSearch.
• nlist — number of IVF clusters. More clusters means finer buckets and cheaper individual probes, but more of them needed for the same recall.

The interview move is to state that you would measure recall rather than assume it: build a ground-truth set with a flat index over a sample, sweep the dial, and pick the lowest setting that clears your recall target at your latency budget. Interviewers ask "how do you know the search is good enough?" precisely to see whether you reach for measurement or for adjectives.

Distance metrics and the normalization trap

Three metrics cover almost everything: cosine similarity, inner product, and Euclidean (L2) distance.

The point interviewers probe is the relationship between them. For L2-normalized vectors, ranking by cosine similarity, inner product, and Euclidean distance all produce the same order. That is why so many systems normalize at write time and then use plain inner product: it is the cheapest operation, and on unit vectors it is equivalent to cosine.

Get this wrong in the other direction and you have a silent bug rather than an error. Indexing un-normalized vectors and querying with inner product ranks by magnitude as well as direction, so long documents drift to the top of every result set — a failure that looks like "the search is a bit off" rather than anything that raises an alarm.

Practise the primitives directly: normalize a vector (L2) and cosine similarity are both short questions that make the equivalence concrete, and the embeddings glossary entry has the definitions in one place.

Filtering: the part nobody prepares for

"Find similar documents that this user is allowed to see" is where most designs fall apart, and it is a favourite follow-up.

Post-filtering searches the index for k results, then discards the ones failing the predicate. It is trivial to implement and it breaks badly under selective filters: if a user can see 1% of the corpus, a top-100 vector search returns roughly one permitted result. You have to over-fetch by a factor you cannot know in advance.

Pre-filtering evaluates the predicate first, then searches only the surviving set. This is exact, but a naive implementation destroys the index — the HNSW graph's connectivity assumes the full vector set, and walking a graph where most nodes are excluded degenerates toward a scan.

Production systems land in between: filtered search that evaluates the predicate during traversal, usually with a bitmap of allowed ids, plus a fallback to exhaustive search over the filtered set when the predicate is selective enough that scanning is simply cheaper. Naming that crossover — "below some selectivity threshold I would brute-force the filtered subset instead" — is a strong signal.

Capacity: sizing an index out loud

Interviewers want to see arithmetic, not a product recommendation. The base calculation is small enough to do in your head.

Raw vectors: count x dimensions x bytes_per_component. For 100 million vectors at 768 dimensions in float32 (4 bytes):

100,000,000 x 768 x 4 bytes = 307 GB

Then add the index overhead. HNSW graph links are roughly M x 2 x 4 bytes per vector per layer, which in practice lands somewhere around 20–40% on top of the raw vectors for typical M. So the honest number is closer to 400 GB — comfortably past a single machine's memory, which is what makes the next question ("so how do you shard it?") inevitable.

Two levers come up immediately:

• Quantization. Scalar quantization to int8 cuts the vector bytes by 4x for a small, measurable recall cost. Product quantization goes much further and costs more accuracy. The framing interviewers want: quantization trades recall for memory, and it should be measured like any other recall decision. The quantization glossary entry has the definition.
• Dimensionality. A 768-dimension model and a 1536-dimension model differ by 2x in every storage and bandwidth number above, forever. Choosing the smaller model that clears your quality bar is the highest-leverage decision available, and it is made before any of this infrastructure exists.

If back-of-the-envelope work is the part you find hardest, the estimation guide and the latency numbers reference are the two things worth having automatic before an interview.

Freshness: updates, deletes, and the rebuild problem

A question that reliably catches people: a document is deleted — what happens?

HNSW graphs do not support true deletion cleanly. The standard approach is a tombstone: mark the id as deleted, filter it from results at query time, and leave the node in the graph as a routing waypoint. That works, and it degrades — as tombstones accumulate, you are traversing and paying for nodes that can never be returned, so recall per unit of work falls.

Hence periodic rebuilds, and hence the real design question: how do you rebuild a 400 GB index without downtime? The expected answer is the same shape as any blue/green migration — build the new index alongside the old from the source of truth, replay writes accumulated during the build, verify recall against a ground-truth sample, then switch reads over. Notice that this requires the embeddings to be durably stored outside the index, which is a design decision you should state early rather than discover here.

Re-embedding is the harder cousin. Changing the embedding model invalidates every vector you have, and old and new vectors are not comparable, so there is no incremental path — it is a full rebuild plus a dual-serving window. That is why "which embedding model?" is a more consequential choice than it first looks.

Scaling out: sharding and replication

Once the index exceeds one machine, two axes appear.

Sharding splits vectors across machines. The default is random or hash-based assignment, because a query has to fan out to every shard regardless — there is no partition key that tells you which shard holds the nearest neighbours. Each shard returns its local top-k and a coordinator merges them, which is correct as long as all shards use the same metric.

Semantic sharding (clustering related vectors together) sounds appealing and usually is not worth it: it makes the fan-out skewed and load-imbalanced, and it couples your placement to a clustering that drifts as the corpus grows.

Replication handles read throughput and availability. Because most vector indexes are read-heavy and rebuilt in bulk rather than mutated in place, replicas are unusually easy — they are near-immutable artifacts that can be copied and served independently.

The latency consequence worth naming: a fan-out query is as slow as its slowest shard, so p99 latency is governed by tail behaviour across the whole fleet. Hedged requests and a tail-tolerant coordinator matter more here than in a sharded key-value store, where a single partition serves the read. The tail latency glossary entry covers the general case.

How to practise this

Reading about vector search is a poor proxy for being asked about it under time pressure. A practical sequence:

1. Build the naive version. Brute-force vector similarity search and cosine similarity — these make the approximation everything else performs concrete.
2. Work the full design. Design a Vector Database is the four-phase interactive walkthrough for exactly this question, including the capacity calculations and the tradeoff discussion.
3. Do the retrieval system around it. Design a RAG System puts the index in context: chunking, hybrid retrieval, reranking, and the permission trap above. The companion RAG interview guide covers the same ground in prose.
4. Practise the adjacent pieces. Text chunking with overlap for RAG, RAG context retrieval pipeline, and a semantic cache for LLM responses.
5. Check the vocabulary. The LLM and AI engineering quiz is a fast way to find the gaps, and Interview Concepts covers vector database, embeddings, chunking and retrieval-augmented generation.

If you are targeting a specific company, the OpenAI, Anthropic and Nvidia pages collect the relevant questions in one place.

Frequently asked questions

Do I need to know HNSW's internals for a system design interview? You need to know that it is a layered proximity graph, that efSearch trades latency for recall at query time, that M sets memory and the recall ceiling at build time, and that deletes are tombstoned. Reproducing the insertion algorithm is not expected outside a specialist retrieval role.

IVF or HNSW? HNSW when you need high recall under a tight latency budget and can afford the memory. IVF when memory is the binding constraint or the corpus is written far more often than it is read. Under a few hundred thousand vectors, a flat index is often the right answer and saying so is a point in your favour.

How is a vector database different from a search engine? A search engine matches terms; a vector index matches positions in embedding space, so it retrieves on meaning rather than wording. In practice strong systems use both — hybrid retrieval fuses lexical and vector results, because each fails in ways the other covers. Exact identifiers and rare proper nouns are where lexical search wins outright.

Is a dedicated vector database required, or is a Postgres extension enough? For most workloads a general database with vector support is sufficient and removes a system from your architecture. The case for a dedicated store starts when the index no longer fits in memory on one machine, when you need independent scaling of retrieval, or when filtered search at high selectivity is a core path. Interviewers respond well to that framing because it names a threshold instead of a preference.

What does "recall" mean here, exactly? The fraction of the true k nearest neighbours that the approximate search returned, measured against exhaustive search over the same data. It is a property of your parameter settings, not of the index type, which is why the strongest answers treat it as something to measure and tune rather than assume.

How many dimensions should embeddings have? Whatever the smallest model that clears your quality bar produces. Dimensions multiply through every storage, memory and bandwidth number in the system, and that cost is permanent. Evaluate retrieval quality on your own data before committing, because the ranking of embedding models is task-dependent.