03. Vector Search Engine — Interview Q&A

~15 min read · Part 4 of 4 (Overview → HLD → LLD → Q&A)

These are the questions an interviewer asks once the scatter-gather diagram is on the board. Each answer is the strong version, followed by the wrong answer that quietly sinks candidates.

Q1. Why not just compute the exact nearest neighbors? Because exact k-NN means comparing the query against every stored vector — a billion distance computations per query — and no latency budget survives that at 10k QPS. The entire field is a bargain: give up the guarantee of the exact nearest neighbor and do thousands of times less work by walking an approximate index (HNSW walks ~3,500 vectors instead of 50M per shard, a ~14,000× reduction). The quality of the approximation is captured by recall, which you tune to a floor — 95% here — and monitor, rather than assume. The framing to say out loud: this is not about finding the exact nearest neighbor, it is about bounding how often you miss it. Common wrong answer to avoid: "Index the vectors in a B-tree / normal database index and sort by distance." Tree indexes assume a total order on one dimension; nearest-neighbor in 768 dimensions has no such order, so a B-tree gives you nothing and you fall back to a full scan.

Q2. HNSW or IVF-PQ — how do you choose? It is a memory-versus-recall decision. HNSW gives higher recall at a given latency and supports live incremental inserts, but costs ~3.3 KB/vector (~3.3 TB for a billion), which forces ~20 shards purely to fit RAM. IVF-PQ compresses each 768-dim vector to ~96 bytes (a 32× cut to ~96 GB total), fitting far fewer machines, but its distances are approximate so you must re-rank the top candidates against full-precision vectors, and its centroids drift as data changes, forcing periodic retrains. Choose HNSW when recall and freshness dominate and RAM is available; choose IVF-PQ when RAM is the binding constraint and a re-rank pass can recover the lost recall. Common wrong answer to avoid: "HNSW is strictly better, always use it." HNSW's RAM footprint is often the thing that doesn't fit; ignoring the memory ceiling is exactly the mistake the scenario is built to expose.

Q3. Walk me through serving 1 billion vectors at 10k QPS with 95% recall. Shard for RAM, replicate for QPS. A billion HNSW vectors at ~3.3 KB each is ~3.3 TB, so split into 20 shards of 50M (~165 GB each, fits a 256 GB box). Every query fans out to all 20 shards because a query's neighbors can be on any shard, so internal load is 10,000 × 20 = 200,000 shard-queries/second. Tune ef_search=100, which clears 95% recall and runs ~4 ms/shard; at that setting a replica sustains ~2,000 shard-queries/second, so you need 200,000 / 2,000 = 100 replicas — 5 per shard. Those replicas also give the coordinator a hedge target for slow tails. End-to-end latency is roughly the slowest un-hedged shard plus a small merge, comfortably under the 50 ms p99 budget. Common wrong answer to avoid: "Route each query to the shard that holds its neighbors." You can't — you don't know where a query's neighbors are until you search, which is why the read path is scatter-gather to all shards, not partition-by-key like a sharded database.

Q4. What actually happens to latency when one shard replica goes slow? It poisons the tail of every query, not just some. Because each query waits for all 20 shards, the end-to-end latency is the max over shards, so one replica that drifts from 4 ms to 80 ms drags p99 on every query that touches it — while the mean barely moves because the other 19 shards are fine. That's why mean latency is the misleading metric here and the tail is what you watch. The fix is request hedging: when a replica misses a soft deadline (say the fleet p95), the coordinator fires the same sub-query at a second replica and takes whichever returns first, and it ejects a replica whose p99 crosses a threshold. Common wrong answer to avoid: "Average latency is fine, so we're healthy." Scatter-gather makes the average lie — a single slow replica hides in the mean and lives entirely in the tail that users actually feel.

Q5. How do you tune and defend the 95% recall number? Recall is a measured quantity, not a hope. Hold a fixed ground-truth probe set — say 1,000 queries whose true top-10 you computed offline by brute force — and continuously run them at the current ef_search, measuring recall@10. A recall governor raises ef_search if measured recall drifts below 95% and can lower it under overload to shed load deliberately. The knob has a known curve: ef_search 40 → ~90% recall at ~2 ms, 100 → ~95% at ~4 ms, 200 → ~98% at ~8 ms. You pick 100 because it clears the floor with margin, and you keep measuring because recall silently decays as the corpus grows or the distribution drifts. Common wrong answer to avoid: "Set ef_search to a good value once and leave it." Recall rots — more data, distribution drift, and tombstone buildup all erode it — so an unmeasured recall setting is a silent regression waiting to happen.

Q6. A traffic surge pushes you past capacity — do you drop queries? No — shed recall before you shed requests. Dropping ef_search from 100 to 60 cuts per-shard work ~40% (recall dips from ~95% to ~92%), which lets the same 100 replicas absorb roughly a 1.6× QPS surge while a warning fires. A user getting 92%-recall results in 4 ms is a far better outcome than a user getting a timeout, and the degradation is graceful and reversible: as the surge passes, the governor walks ef_search back up to 100. Autoscaling replicas is the durable fix, but it's minutes slow; recall-shedding is instant. Common wrong answer to avoid: "Add more replicas / autoscale." Correct as the long-term answer, but too slow for the surge itself — a candidate who has no instant lever for overload hasn't run one of these systems under load.

Q7. How does hybrid search work, and why not just add the scores? Retrieve two ranked lists — dense vector similarity and sparse BM25 keyword relevance — and fuse them by rank, not by raw score. Cosine similarities sit around 0–1 while BM25 scores are unbounded and corpus-dependent, so adding them directly compares incomparable scales and lets one signal swamp the other. Reciprocal Rank Fusion uses only rank position: an item's fused score is the sum over each list of 1/(K + rank) with K≈60, so items both lists rank highly float to the top. Hybrid matters because dense vectors miss exact-term matches (part numbers, rare proper nouns) that BM25 nails, and BM25 misses paraphrase that vectors catch — the lists cover each other's blind spots. Common wrong answer to avoid: "Normalize both scores to 0–1 and take a weighted sum." Score normalization is fragile — BM25's range shifts with the corpus and query, so the weights that work today break tomorrow; rank fusion sidesteps this because ranks carry no scale to drift.

Q8. Do you rebuild the whole index on every change, or update incrementally? Both, for different jobs. Incremental inserts handle freshness: an upserted vector is written to the durable store, then inserted live into the shard's HNSW graph and searchable within seconds. Full rebuilds handle correctness and compaction: they run offline on a separate build tier over hours, reclaim tombstoned deletes, and — for IVF — retrain centroids that have drifted from the current data distribution, then ship immutable segments that shards hot-swap. HNSW can coast longer on incremental inserts; IVF needs rebuilds sooner because centroid drift silently decays its recall. The rule: incremental for freshness, full rebuild for correctness, and never let a rebuild contend with serving. Common wrong answer to avoid: "Rebuild the index whenever data changes." Rebuilding a billion-vector index takes hours; doing it per change is impossible, and doing it on the serving fleet would tank query latency.

Q9. How do you delete a vector from an HNSW graph? You tombstone it rather than surgically removing the node, because cleanly excising a node means finding every inbound edge and re-wiring the neighbors it connected — expensive and disruptive to graph connectivity. So you flip a bit in a tombstone bitset (O(1)), and searches traverse through the dead node but filter it out of results. The cost is that inbound edges still point at it, so navigation slowly degrades as tombstones accumulate; when the tombstone ratio passes ~10%, trigger a compaction rebuild for that shard to reclaim the space and restore connectivity. Common wrong answer to avoid: "Remove the node and its edges from the graph in place." Live node removal from an HNSW graph is costly and can disconnect regions of the graph, silently dropping recall for unrelated queries.

Q10. How do you handle a filtered query like category = "boots" AND price < 200? Choose the strategy by filter selectivity. For a loose filter that keeps most of the corpus, let each shard run its normal ANN search and drop non-matching results afterward — cheap, and the candidate budget still lands on relevant vectors. For a highly selective filter (say 0.1% of the corpus), post-filtering is a trap: the HNSW walk spends almost its entire ef_search budget on vectors it will discard, so effective recall among matching items craters. There, pre-fetch the matching id set from the metadata store and pass it as an allow-list so the walk only spends its budget on vectors that can survive the filter. The coordinator picks the path based on the filter's estimated selectivity. Common wrong answer to avoid: "Always search first, then filter the results." For a selective filter that returns almost nothing that survives, so you either return too few results or must crank ef_search enormously to compensate — pre-filtering is the correct tool for high selectivity.

Q11. How much memory does this take, and where does the money go? The raw vectors alone are 1e9 × 768 × 4 bytes = 3.072 TB, and HNSW adds ~256 bytes/vector of edges for ~3.3 TB total in RAM — that RAM is the dominant cost, which is exactly why quantization exists. IVF-PQ compressing to 96 bytes/vector cuts the footprint to ~96 GB, a 32× reduction, trading recall for RAM. The durable raw store (object storage) and built segments are cheap by comparison and off the hot path. The scenario is memory-bound, not storage-bound or compute-bound: serving a billion vectors is not a storage problem, it is a memory-residency problem, because the index has to be walked in RAM to hit the latency SLO. Common wrong answer to avoid: "We'll need a big distributed disk-based database." Disk-resident vector search can't hit tens of milliseconds at a billion vectors; the whole design exists to keep the index in RAM, so the interesting scaling is memory, not disk.

Q12. What breaks when the corpus grows from 1B to 2B vectors? Two things move. The index no longer fits the existing 20 shards' RAM — at 100M vectors/shard the ~330 GB footprint spills a 256 GB box and the OS starts paging, which quietly turns 4 ms searches into 400 ms — so you add shards to keep each at ~50M and ~165 GB, going from 20 to ~40. But every added shard adds one sub-query to every query, so internal load jumps to 10,000 × 40 = 400,000 shard-queries/second, requiring more replicas even at the same external QPS. That's the hidden fan-out tax: you shard only as far as RAM forces you to, because each shard makes every query more expensive. Common wrong answer to avoid: "Just let the shards get bigger." A shard whose index exceeds RAM pages to disk and its latency collapses — the RAM-per-shard ceiling is a hard operational limit, monitored and defended, not a soft guideline.

Deeper follow-ups

• How would you support multi-vector documents (a doc with several embeddings, e.g. per-passage) and dedup them so one doc doesn't fill all top-k slots?
• How would you replicate the index across regions for low-latency global reads, and what freshness lag would you accept between regions?
• How would you A/B test a new embedding model that changes every vector, without a flag-day rebuild that breaks live search?
• How would you detect that a shard has become a hotspot (drawing disproportionate query cost) when every query hits every shard equally?
• What changes if the distance metric is inner product (for recommendation) rather than cosine — how does that affect HNSW graph construction and quantization?
• How would you bound the memory of the tombstone/compaction cycle so a high-delete-rate index doesn't degrade between scheduled rebuilds?

How this round is scored

Interviewers use vector search to see whether you treat recall as a measured, defended SLO rather than a vibe. The strong signal is naming the recall-vs-latency-vs-memory triangle early and refusing to move one corner without paying at another — sharding for RAM, replicating for QPS, and tuning ef_search to a floor you monitor. Seniority shows in the scatter-gather insight: recognizing that you can't route to one shard, that tail latency is therefore the slowest shard's latency, and that hedging and recall-shedding are the levers — candidates who model it like a partition-by-key database miss the whole problem. The failure-mode discussion (a slow replica poisoning every query's tail, IVF centroid drift, the fan-out tax as you add shards, a bad build regressing recall) separates people who have operated these systems from those who have only read about them. And doing the memory and QPS arithmetic out loud — 3.3 TB forces 20 shards, 200k internal QPS forces 5 replicas — then using it to justify the topology, is what pushes an answer from "correct" to "senior."