Estimate vector index memory for 100M × 768-d vectors with HNSW, IVF-PQ, and binary quantisation.
- 1 min — raw size and dtype options
- 3 min — HNSW, IVF-PQ, binary memory each
- 2 min — recall vs memory, rescoring design
- 2 min — tiering, sharding, platform ownership
Raw vectors: N × d × bytes. HNSW adds graph links: roughly 2M neighbour IDs at layer 0 × 4 bytes per vector (M=16 → ~128–160 B). IVF-PQ stores only codes (m bytes per vector at 8 bits per sub-quantiser) plus IDs and centroids. Binary quantisation stores d bits = d/8 bytes per vector and rescores a shortlist with higher-precision vectors held on disk or in a cheaper tier.
An e-commerce catalog search with 100M product and review chunks embedded at 768-d. The team proposes HNSW on a single node because it worked at 5M. You need to show what it costs at 100M and pick the compression tier that keeps recall above the 0.95 target.
Default: HNSW over int8 or binary vectors in RAM with full-precision rescoring from SSD, because it keeps graph search latency and controls memory. Switch to IVF-PQ when memory dominates cost and you can tolerate a reranking stage. The number that matters isn't bytes, it's recall at the latency SLO, measured on your queries — compression error is model-dependent. Ownership: the search platform team publishes tiers (hot HNSW, warm quantised, cold IVF-PQ on disk) with recall/latency/price per million vectors; product teams pick a tier, not index parameters.
Assumptions: N = 100M, d = 768, HNSW M = 16, IVF nlist = 65,536, PQ with 96 sub-quantisers × 8 bits, 8-byte IDs.
- Raw float32: 100M × 768 × 4 B = 307 GB (float16: 154 GB; int8: 77 GB).
- HNSW (float32): 307 GB + ~150 B × 100M ≈ 15 GB links → ~322 GB → 3 × 128 GB nodes (or 2 × 256 GB) before replication.
- HNSW over int8: 77 + 15 ≈ 92 GB — one large node per replica.
- IVF-PQ: codes 96 B × 100M = 9.6 GB + IDs 0.8 GB + centroids 65,536 × 768 × 4 B ≈ 0.2 GB → ~10.6 GB; recall@10 typically 0.6–0.85 without rescoring, so rescore top-200 from float vectors on SSD.
- Binary: 768 bits = 96 B × 100M = 9.6 GB in RAM; rescore top-10×k with int8 (77 GB on NVMe). Many 2024–2026 embedding models keep ~90–96% of float retrieval quality this way; measure on yours.
- Cost: assume $5/GB-month for RAM-heavy instances (illustrative): float32 HNSW ≈ $1,600/month per replica vs binary ≈ $50 RAM + NVMe.
| Index | RAM | Recall@10 (typical) | Notes |
|---|---|---|---|
| HNSW float32 | ~322 GB | 0.97–0.99 | multi-node |
| HNSW int8 | ~92 GB | 0.95–0.98 | one node |
| IVF-PQ 96B | ~11 GB | 0.6–0.85 → 0.95 w/ rescore | rescore from SSD |
| Binary + int8 rescore | ~10 GB | 0.9–0.96 w/ rescore | model-dependent |
What the answer sounds like at each level
Computes 307 GB of raw float32 vectors and knows HNSW adds graph overhead.
Sizes all three options and explains the recall trade-off and rescoring.
Recommends a tiered design with measured recall at the SLO, sharding, and a platform-owned menu of tiers with prices.
Follow-ups the interviewer will push
1Now the corpus grows to 1B vectors.
Float HNSW is 3+ TB — out. Shard IVF-PQ or binary across nodes (~100 GB codes), consider DiskANN-style SSD-resident graphs, and route by tenant or category so most queries hit one shard.
2Now there's a strict tenant filter on every query.
Filtered HNSW degrades when the filter is selective (<1% of vectors); partition by tenant for large tenants and use pre-filtered brute force for tiny ones. Memory per tenant then decides placement.
3How would you pick nlist and nprobe?
nlist ≈ 4–16 × √N (40k–160k at 100M); sweep nprobe on a held-out query set and take the smallest value that hits target recall at the latency SLO — typically 16–64.
Red flags interviewers listen for
- Forgets HNSW graph overhead or replication when sizing RAM.
- Quotes PQ or binary recall without mentioning rescoring.
- Picks an index by benchmark leaderboard rather than recall on their own queries at the SLO.
How it's scored
| Dimension | What strong looks like |
|---|---|
| Arithmetic | 307 GB raw, ~15 GB HNSW links, ~10 GB PQ/binary — correct within 10%. |
| Trade-off | Ties each option to recall at the latency SLO and explains rescoring. |
| Design | Proposes tiered storage and sharding with a measured selection process. |
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
- The Faiss library — Douze et al., 2024paper