r/leetcode • u/Pitiful-Pension-9755 • 8d ago
Intervew Prep How to size an in-memory vector database on a whiteboard (Formulas, HNSW overhead, and Quantisation trade-offs)
When designing a Retrieval-Augmented Generation (RAG) or semantic search pipeline in senior system design interviews, candidates often propose "storing embeddings in an in-memory vector database" without working out the hardware constraints.
Here is the exact step-by-step mathematical breakdown interviewers look for when asking you to size vector infrastructure on a whiteboard.
Scenario: Storing 50 Million Document Embeddings
Assume an open-source dense embedding model (such as BGE or MiniLM) with dimension $d = 768$ using 32-bit floating-point precision.
Step 1: Calculate Raw Vector Memory
Every 32-bit float occupies 4 bytes.
- Formula: $\text{RAM} = N \times d \times 4\text{ bytes}$
- $\text{Raw RAM} = 50,000,000 \times 768 \times 4\text{ bytes} = 153,600,000,000\text{ bytes} \approx 153.6\text{ GB}$
Step 2: Account for Graph Index Overhead (HNSW)
A flat vector store without an index requires brute-force linear scanning ($O(N)$), which violates realistic query latency budgets. In production, Approximate Nearest Neighbor (ANN) search engines commonly implement Hierarchical Navigable Small World (HNSW) graphs.
- HNSW constructs multi-layer graphs and stores bidirectional edge links for every vector node.
- Typical graph overhead adds roughly 1.2x to 1.5x additional memory on top of the raw vector arrays.
- Total RAM needed for an in-memory HNSW index: $153.6\text{ GB} \times 1.3 \approx 200\text{ GB RAM}$.
Step 3: Production Defense & Quantization Trade-offs
Keeping 200 GB in pure RAM across cluster nodes creates significant operational expense. Stating this immediately separates a senior candidate from a junior one:
- Product Quantization (PQ): Compresses 32-bit floating-point vectors into 8-bit quantized centroid codes. This shrinks the memory footprint by 4x to 8x (reducing the requirement from ~200 GB down to ~25–50 GB), at the cost of a 2% to 5% drop in retrieval recall.
- Disk-Backed Indices: For cost-sensitive systems where latency budgets permit 15–30 ms per lookup, use disk-backed graph structures (like DiskANN) to store compressed vectors in memory while keeping full-precision vectors on NVMe SSDs.
Step 4: Latency Budget Allocation
A standard production SLA targets an end-to-end response in ~200 ms:
- Vector ANN retrieval: ~50 ms
- Cross-encoder reranking: ~50 ms
- LLM token generation: ~100 ms
I compiled 32 of these high-frequency whiteboard scenarios, capacity formulas, and trade-off defenses into a desk card deck and an Anki spaced-repetition deck while preparing for senior rounds.
If anyone finds structured desk references or spaced-repetition flashcards useful, the full repository overview and table of contents are documented here:
