How would you retrieve information from millions of documents efficiently?
- 1 min — requirements: corpus size, QPS, latency, recall target.
- 3 min — funnel: ANN + BM25 → fusion → rerank.
- 3 min — memory sizing, quantisation, partitioning.
- 1 min — ANN recall measurement and routing.
Multi-stage funnel. Cheap, high-recall candidate generation over the full corpus (ANN with HNSW or IVF-PQ, plus BM25), then progressively more expensive stages over shrinking sets, ending in a cross-encoder over tens of candidates. Combine with partitioning: shard by tenant, time, or topic so most queries touch a fraction of the corpus.
Know the index trade-offs concretely. HNSW is fast with high recall but memory-hungry and expensive to rebuild. IVF-PQ compresses heavily, so it fits far more vectors in RAM at some recall cost. Quantisation — scalar or binary — can cut memory 4–32×; binary quantisation with a float rescoring pass over the top candidates is a very strong cost/quality point.
Say the thing most candidates don't: ANN recall is a tunable you're responsible for measuring. Compare against exact search on a sample and know your number. Many teams run at 85% ANN recall without knowing it and spend months tuning rerankers to recover loss that happened in the index. Then: routing — if you can classify the query to a partition, you've cut the problem by an order of magnitude for free.
Org scope: below ~50M vectors, buy — a managed vector store or OpenSearch/pgvector run by the platform team. Building custom index infrastructure is justified only when vector memory cost or latency is a top-three line item.
Assumptions: 5M documents × 10 chunks = 50M chunks; 1024-dim embeddings; HNSW M = 16; target 50ms p99 retrieval at 500 QPS.
- float32: 1024 × 4 B = 4 KB/vector → 205 GB. int8: 51 GB. Binary: 128 B → 6.4 GB.
- HNSW links (level 0, 2M = 32 neighbours × 4 B) ≈ 128 B/vector → 6.4 GB.
- Plan: binary vectors + graph in RAM (~13 GB), float32 on NVMe for rescoring the top 200 (200 × 4 KB = 800 KB read, ~1ms on NVMe).
- CPU: ~1–2ms per query at efSearch 100; 500 QPS × 2ms = 1 core-second/s, so one 8-vCPU node has ~8× headroom.
- Binary plan: 13 GB fits one 64 GB node → 3 replicas (HA + headroom) × ~$0.50/h (illustrative memory-optimised on-demand, Oct 2026) × 730h ≈ $1.1k/month.
- float32 HNSW fully in RAM: ~211 GB × 2 replicas ≈ 422 GB → 8–10 × 64 GB nodes ≈ $2.9–3.7k/month, about 3× the cost for ~1–2 points of recall that float rescoring mostly recovers anyway.
| Encoding | Bytes/vector (1024d) | 50M vectors |
|---|---|---|
| float32 | 4,096 | 205 GB |
| int8 | 1,024 | 51 GB |
| PQ (64 B codes) | 64 | 3.2 GB |
| binary | 128 | 6.4 GB |
What the answer sounds like at each level
Use an ANN index like HNSW plus BM25, then rerank the top results.
Sizes memory per vector, chooses quantisation with rescoring, partitions by tenant or time, and measures ANN recall against exact search.
Designs the funnel against an explicit latency and cost target, decides buy vs build by vector count and cost share, and makes ANN recall a published SLO.
Follow-ups the interviewer will push
1The corpus grows from 5M to 500M documents. What breaks first?
RAM: 5B chunks at even 128 bytes (binary) is 640 GB before graph links, so you shard across nodes and the coordinator fans out. Rebuild time for HNSW becomes days. Move cold partitions to disk-based indexes (DiskANN-style or IVF on SSD), route queries to partitions, and keep only hot data in memory.
2How do you measure ANN recall in production?
Sample ~1,000 real queries daily, run exact brute-force search offline on the same index snapshot, and compute overlap@k with the ANN result. Alert if it drops below the target (e.g. 0.95@10) after compaction or growth; tune efSearch/nprobe to restore it.
Red flags interviewers listen for
- Proposes exact (brute-force) search over tens of millions of vectors per query.
- Never measures ANN recall against exact search.
- No memory arithmetic for the index.
How it's scored
| Dimension | What strong looks like |
|---|---|
| Architecture | Multi-stage funnel with each stage's candidate count stated. |
| Sizing | Computes bytes per vector and total RAM, and picks quantisation accordingly. |
| Quality ownership | Measures ANN recall against exact search and tunes it deliberately. |
Sources
- Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs — Malkov & Yashunin, 2016paper
- Product Quantization for Nearest Neighbor Search — Jégou et al., 2011paper
- Matryoshka Representation Learning — Kusupati et al., 2022paper