Concept 14: Vector Databases & AI Infrastructure — Embeddings, ANN Indexes & RAG at Scale

System Design Bible — File 14 Difficulty: ★★★★★ Prerequisites: File 02 (Caching — the memory hierarchy is the entire cost model here), File 04 (Sharding & Partitioning — you will shard vectors, and the partition key choice is unusually cruel), File 06 (Consistent Hashing), File 08 (Consensus & Replication), File 09 (Object Storage — where cold vectors live), File 11 (Databases Deep-Dive — B-trees, LSM-trees, segments), File 13 (Distributed Search Engines — HNSW got a first look there; scatter-gather, immutable segments, and hybrid retrieval all carry over), plus the fundamentals unpacked in Section 0.

Table of Contents#

0Prerequisites — What You Must Understand First#

Vector search looks like "search but with AI," and that framing will sink you in an interview. It is a genuinely different problem with a different physics. Five ideas make everything else obvious.

0.1What an embedding actually is (and why a list of 768 numbers means something)#

An embedding is a fixed-length list of floating-point numbers — a vector — produced by a neural network from some input (a sentence, an image, a user's click history, a product). A typical text embedding has 768 or 1536 dimensions; each dimension is just a number like 0.031, -0.44, 0.87.

Individually those numbers mean nothing. No dimension is "how much this text is about dogs." The meaning is entirely geometric and relative: the model was trained so that inputs humans consider similar land close together in this space, and dissimilar inputs land far apart. That's the whole contract. "How do I reset my password?" and "I forgot my login credentials" share zero words — File 13 showed you that BM25 is structurally blind to that pair — but their vectors sit almost on top of each other, because the training process pulled semantically related texts together.

How the model learns this matters less than that it's a learned property, but the intuition is worth having: contrastive training. You show the model millions of pairs — a question and its correct answer (a positive pair), a question and a random unrelated answer (a negative pair) — and you adjust the weights to pull positives together and push negatives apart. Do this at internet scale and the resulting space acquires structure nobody explicitly programmed: paraphrases cluster, translations of the same sentence cluster, and a picture of a golden retriever lands near the text "a happy dog" if the model was trained on image-text pairs (that's CLIP, and it's why multimodal search works at all).

Three consequences you must internalize before anything else in this file:

**The vector is the data now. Once you embed, the original text is irrelevant to the retrieval math. You're not searching text; you're doing geometry**. Every algorithm below is a spatial algorithm.

The embedding space belongs to one model version. Vectors from model-v1 and model-v2 are mutually meaningless — different training runs produce entirely different coordinate systems, so a v1 query vector compared against v2 document vectors returns noise, not "slightly worse results." This is the single most expensive operational fact in this file (§7.4).

Embeddings are lossy summaries. 1536 numbers cannot losslessly represent a 10-page document. The model compresses toward whatever it was trained to preserve — usually topical gist — and discards exactly the things BM25 is great at: rare identifiers, error codes, SKUs, proper nouns it never saw. Hold this: an embedding is a learned, lossy, model-specific coordinate for meaning — powerful precisely because it's geometric, and dangerous precisely because it throws away the literal.

0.2Distance metrics — how "close" gets defined, and why the choice isn't yours#

If similarity is geometry, you need a distance function. Three matter.

Euclidean (L2) distance is the ruler distance you learned in school: sqrt(Σ(aᵢ − bᵢ)²). It cares about absolute position in the space, so both direction and magnitude (length) of the vectors affect it.

Cosine similarity measures the angle between two vectors, ignoring their length: cos(θ) = (a·b) / (|a| · |b|), ranging from 1 (identical direction) through 0 (perpendicular, unrelated) to −1 (opposite). This is the default for text, and there's a real reason: raw embedding magnitude often correlates with junk like document length or token count, not meaning. Two documents about the same topic, one three times longer, may point the same direction while having very different lengths. Cosine says "same topic"; L2 says "far apart." Cosine deliberately throws away magnitude because magnitude is usually noise.

Dot product (inner product) is a·b = Σ aᵢbᵢ — cosine without the normalization, so it rewards both alignment and magnitude. Recommendation systems love it because they can encode a bias into the magnitude: make a popular item's vector longer and it wins more dot products, baking "popularity" into the geometry itself.

The key relationship, and a favorite interview trap: if all vectors are normalized to unit length (|v| = 1), then cosine, dot product, and L2 produce the identical ranking. The algebra: for unit vectors, L2² = 2 − 2·(a·b), so L2 is a monotonically decreasing function of the dot product — ordering by one is ordering by the other. This is why almost every production system normalizes at write time and then uses dot product: you get cosine's semantics at the cost of a single multiply per dimension, and dot product is the operation CPUs and GPUs are most brutally optimized for.

The part people get wrong: you don't choose the metric — the model does. Every embedding model was trained with a specific similarity function in its loss. Use cosine on a model trained for dot product and you silently degrade recall — no error, just worse results, forever. Hold this: read the model card, use the metric it was trained with, normalize at ingest, and never treat the metric as a tuning knob.

0.3The curse of dimensionality (why every classic index dies here)#

This is the prerequisite. Everything in §4 exists because of it.

You already know how to index one dimension: a B-tree (File 11) sorts values and gives O(log n) range lookups. You may know how to index two or three: a k-d tree splits space alternately by each axis, or a quadtree recursively quarters a plane. These structures work by pruning — "the whole left subtree is farther than my current best, skip it." Pruning is what makes them fast.

Now go to 768 dimensions, and space stops behaving.

Everything becomes equidistant. Take 10,000 random points in a high-dimensional cube and measure all pairwise distances. In 2D you get a wide, useful spread: near neighbors and far strangers. In 768D the histogram collapses into a narrow spike — the ratio (max_dist − min_dist) / min_dist tends toward zero as dimensions grow. Why? Distance is a sum over dimensions of per-dimension differences. With 768 independent-ish terms, the law of large numbers kicks in: every pair's sum concentrates tightly around the same expected value. Individual differences average out. When everything is roughly the same distance from everything, "nearest neighbor" becomes a fragile, low-contrast distinction — and pruning ("this subtree is far, skip it") has nothing to prune, because nothing is decisively far.

Volume runs away to the corners. The volume of the unit hypersphere inscribed in the unit hypercube goes to zero as dimensions rise — in 768D, essentially all of the cube's volume is in its corners, and a "ball around my query" contains almost nothing. So a space-partitioning tree needs to check nearly every partition to be sure it hasn't missed a neighbor.

Therefore: k-d trees degenerate to full scans above roughly 10–20 dimensions. This is not a tuning problem or an implementation weakness; it's geometry. In 768D, a k-d tree is slower than brute force, because it does the same work plus tree overhead.

So we're left facing a wall. Exact nearest-neighbor search in high dimensions has no known sub-linear algorithm — you must, in the worst case, look at everything. The only escape is to stop demanding exactness. Hold this: the curse of dimensionality means exact kNN cannot be indexed, so every vector index in existence is an approximation, and the entire field is the study of what to approximate and how gracefully.

0.4The arithmetic of brute force (why RAM is your budget, not your disk)#

Let's price the naive approach, because the numbers explain every design decision downstream.

One distance computation between 768-dimensional float32 vectors is 768 multiplies and 767 adds. A modern CPU core with AVX-512 SIMD does ~16 float multiply-adds per instruction, so call it ~50–100 nanoseconds per comparison.

One query against 10 million vectors = 10M × 768 × 4 bytes = 30.7 GB of data read and ~10 billion floating-point operations. Even at a very optimistic 50 GB/s of memory bandwidth, that's ~600 ms of pure memory streaming, per query, on a fully-saturated core. At 1,000 QPS you'd need ~600 cores just to move the bytes. And note the shape of that bottleneck: you are memory-bandwidth bound, not compute bound — the arithmetic is trivial; getting 30 GB through the memory bus is the problem. That's File 02's memory hierarchy delivering the verdict.

Now do it from disk instead. 30.7 GB of random-ish reads on NVMe at ~2 GB/s is 15+ seconds. On network-attached object storage (File 09), forget it. The vector index must be in RAM to be fast — and RAM costs roughly 10–50× per byte what disk does.

So the RAM bill becomes the design: 10M vectors × 768 dims × 4 bytes = 30 GB of raw vectors alone, before the index structure's overhead (HNSW's graph adds ~30–50% more). 100M vectors ≈ 300 GB + graph — multiple large machines, replicated, for one index. This is why a vector database's pricing page is essentially a RAM pricing page, and why §5's quantization is not an optimization — it's the difference between a viable and an unviable system. Hold this: vectors are big, dense, and incompressible by classical means; RAM is the budget; every ANN and quantization technique is a scheme to buy accuracy back after cutting that bill.

0.5Approximation and the recall/latency/memory triangle#

Because exactness is off the table (§0.3), we accept Approximate Nearest Neighbor (ANN) search: return probably most of the true nearest neighbors, fast.

The quality metric is recall@k: of the true top-k nearest neighbors (computed by brute force on a sample, offline), what fraction did the index actually return? If the true top-10 contains items {A…J} and your index returns 9 of them plus one impostor, that's recall@10 = 0.9.

Everything in this file trades on a three-way tension — you can have any two, and you're always buying one with the others:

                    RECALL (accuracy)
                          ▲
                         ╱ ╲
                        ╱   ╲          pick your point on this surface;
                       ╱     ╲         you cannot have all three maxed
                      ╱       ╲
             LATENCY ◄─────────► MEMORY (cost)

Want higher recall? Search more of the graph or more clusters (more latency) or store less-compressed vectors (more memory). Want lower memory? Quantize harder (lower recall). Want lower latency? Explore less (lower recall).

Here's the reframe that makes this comfortable rather than alarming, and it's the sentence that impresses interviewers: your embedding model is already wrong more often than your index is. If the model's own top-10 only contains the genuinely best answer ~80% of the time, then the difference between 99% recall and 95% recall is invisible to users — you're arguing about the 4% of a ranking that was already noisy. So don't buy recall you can't perceive. Meanwhile, going from 99% to 95% recall might cut your memory bill by 4× and your latency by 3×. Hold this: ANN is a knob, not a compromise; measure recall against your actual product metric, and spend the savings where users can feel them.

1Architectural Definition & "The Why"#

1.1The Plain Definition#

A vector database is a system that stores high-dimensional vectors alongside their metadata, builds an approximate nearest-neighbor index over them, and answers the query "given this vector, return the k most similar stored vectors — optionally restricted to those whose metadata matches a filter" in single-digit milliseconds over billions of vectors, while supporting inserts, updates, and deletes.

The analogy: **a librarian who has read every book and arranged the entire library by meaning rather than by title.** A conventional index (File 13) is the card catalog — you must know a word that appears on the page. This librarian instead placed every book in a room where physical proximity is topical proximity: books about grief sit near books about loss, regardless of shared vocabulary. Walk in holding a book, and the ones you want are within arm's reach. The librarian's trick is that she doesn't search the whole library — she has memorized a network of shortcuts between the shelves (that's HNSW, §4.3), so she hops from a random shelf to the right neighborhood in a handful of steps. She is occasionally wrong: sometimes the very best book was one shelf over and she missed it. She gets you 95% of the way in 5 milliseconds instead of 100% of the way in 5 minutes, and that trade is the entire product.

Be precise about the layers, because interviewers deliberately blur them:

1.2"The Why" — The Limits That Forced This to Exist#

Limit 1 — Lexical search structurally cannot match meaning. File 13's inverted index answers "which documents contain this exact term?" Brilliant, and blind: car and automobile are unrelated strings, so BM25 scores their overlap at zero. Every workaround — synonym lists, stemming, query expansion — is a human hand-maintaining a lookup table of meaning, which does not scale to natural-language questions. Embeddings put the model's learned notion of meaning into the geometry, and vector search retrieves on it. The wall was: lexical matching has a hard ceiling on recall for natural-language intent, and no amount of synonym curation lifts it.

Limit 2 — LLMs have a fixed context window and a fixed training cutoff. A large language model knows what was in its training data, up to a date, and can only "see" a bounded number of tokens at inference. Your company's private wiki isn't in there, and you cannot paste 40 GB of documents into a prompt. Two alternatives exist and both are worse for most cases: fine-tuning (retrain the model on your data — expensive, slow, must be redone as data changes, and notoriously bad at reliably injecting facts), or stuffing everything in the context (physically impossible past a few hundred pages, and quality degrades as context grows — the "lost in the middle" effect). Retrieval-Augmented Generation (RAG) is the third way: keep the knowledge in an external index, retrieve the ~5 relevant chunks per question, and paste those into the prompt. RAG exists because the context window is a hard physical limit and fine-tuning is a bad tool for facts — and RAG's retrieval step is a vector search. This one limit created the entire commercial vector-database market.

Limit 3 — The curse of dimensionality broke every existing index. §0.3. You cannot bolt this onto a B-tree. The data structures had to be reinvented, and the reinvention required abandoning exactness.

Limit 4 — RAM is the cost wall. §0.4. 100M vectors is 300 GB of raw floats. The economics force quantization, disk-based indexes, and tiering. Every serious vector-infrastructure paper of the last decade is fundamentally about doing more per byte of RAM.

Limit 5 — Recommendation at scale needed sub-linear retrieval. Before LLMs existed, Spotify, YouTube, and Meta already had this problem: score 100 million candidate items against one user in under 50 ms. The industry's answer — two-tower retrieval — embeds users and items into a shared space so that "recommend" becomes "find nearest neighbors of the user vector." ANN search was load-bearing infrastructure at Meta and Google years before anyone said "RAG." Saying this in an interview instantly separates you from candidates who think vector databases were invented in 2023.

1.3What It Solves — And the Price It Charges#

Every row carries a real cost. The one candidates always miss: "it's approximate" is not a footnote — it means your system has a permanent, invisible error rate that no amount of debugging will drive to zero, and you must design around that rather than be surprised by it.

2The Recursive Sub-Concept Tree#

2.1Sub-Concept: Dimensionality and What It Costs You#

Dimension count (d) is how many numbers per vector: 384 (MiniLM), 768 (BERT-base), 1536 (OpenAI text-embedding-3-small), 3072 (large models). It is fixed by the model.

Why it matters, concretely: memory is exactly linear in d (10M × 1536 × 4 B = 61 GB; halve the dimensions and halve the bill), distance computation time is linear in d, and — more subtly — **higher d makes the curse worse** (§0.3), so ANN indexes need to work harder for the same recall.

The trade-off: more dimensions generally means a richer representation and better retrieval quality, up to a point of severely diminishing returns. Which is why Matryoshka Representation Learning (MRL) matters: newer models are trained so that the first 256 dimensions of a 1536-dim vector are themselves a usable, coherent embedding — the information is packed front-loaded, like nested dolls. Benefit: you can truncate to 256 dims, take a 6× memory cut, and lose only a few points of recall — and even better, use the truncated vector for a fast first pass and the full vector to rescore the top 100. Cost: some quality loss, and only models explicitly trained with MRL support it (truncating a non-MRL model's vector is vandalism — the information is spread across all dimensions and you're deleting a random chunk of it). Mitigation: measure recall at each truncation length on your data; the curve is usually shockingly flat.

2.2Sub-Concept: Recall@k, and Why It's the Only Metric That Matters#

Recall@k = |returned top-k ∩ true top-k| / k. Measuring it requires a ground truth set: take ~1,000 sample queries, brute-force them against the full corpus offline (slow but exact — this is the one time you're allowed to be O(N)), and store the true neighbors. Then every index configuration is scored against that fixed set.

Why this is non-negotiable: ANN failures are completely silent. A wrong result looks identical to a right one — plausible items, no error, no log line. Without a recall harness you have literally no way to know whether your index is at 0.98 or 0.60. Teams discover the difference through a slow, unexplained decline in product metrics, months later.

The distinction to make in an interview: **recall@k measures your index; it does not measure your product. An index at 99% recall over a corpus whose embeddings are wrong for your domain is 99% faithful to garbage. So you need two layers of measurement: recall for the index, and a retrieval-quality metric (NDCG against human judgments, answer correctness for RAG, click-through for recs) for the system. Optimize recall only until it stops being the bottleneck, then stop** (§0.5).

2.3Sub-Concept: The Embedding Model (and versioning as your central operational problem)#

The embedding model is a neural network mapping input → vector. Practically, you choose along four axes: quality (measured on benchmarks like MTEB, but validate on your data — benchmark rankings routinely fail to transfer), dimension (§2.1, this is your RAM bill), max input length (512 tokens vs 8,192 — determines how you chunk, §8.2), and hosted vs self-hosted (an API is trivial to start with but adds ~50–200 ms per call and a per-token bill on every ingest and every query; self-hosting on a GPU costs engineering time but drops the marginal cost to near zero and cuts latency to ~5 ms — the crossover typically arrives fast for high-volume ingest).

The versioning problem, stated as bluntly as it deserves. Vectors from different models are not comparable (§0.1). Therefore upgrading your embedding model requires re-embedding your entire corpus — every document, through a GPU or a paid API — and rebuilding every index. For 100M chunks that's days of compute and potentially tens of thousands of dollars. And you cannot do it incrementally, because a half-migrated index is a corrupted index: v1 and v2 vectors in one space produce nonsense distances, silently.

The mitigation — the pattern to name in an interview: the same blue/green + alias discipline File 13 demanded for mappings. Build index_v2 alongside index_v1 while v1 keeps serving; when v2 is fully built and its recall has been validated against a ground-truth set, atomically flip the alias; keep v1 for a rollback window, then delete. Benefit: zero-downtime model upgrades and instant rollback. Cost: you pay for double storage during the transition, plus the full re-embedding compute. Non-negotiable prerequisite: you must keep the original source content in durable storage (Postgres/S3, File 09), because re-embedding requires re-reading everything. Teams that embed-and-discard their source text have built an index they can never upgrade. Say that sentence in an interview; it is the vector-DB equivalent of File 13's "never make it your source of truth."

2.4Sub-Concept: ANN vs Exact (Flat) Search#

Flat / brute-force search compares the query against every vector. It gives recall = 1.0 by definition and is genuinely the right answer below roughly 10,000–100,000 vectors, where a full scan is a few milliseconds and no index can beat it — the index's overhead exceeds the savings. **The tell of a good candidate: when the interviewer says "we have 50,000 documents," you say "brute force in a numpy array or pgvector without an index; you don't need a vector database yet."** Reaching for Pinecone at 50k vectors is over-engineering, and interviewers are testing for exactly that reflex.

ANN trades exactness for sub-linear search (§0.5). Every index in §4 is one.

2.5Sub-Concept: Metadata, Payloads, and Filters#

Real queries are never pure similarity. They're "similar to this AND tenant_id = 42 AND language = 'en' AND published_at > 2026-01-01 AND the user has permission to see it." The scalar fields attached to a vector are its metadata (or payload). The system must index them separately — typically an inverted index or bitmap per field, exactly like File 13's keyword fields — and combine that with the vector search.

Why this is the hardest problem in the field, previewed here and dissected in §6: an ANN graph is built over geometry only. It has no idea that half its nodes belong to tenant 42. So "search the graph, but only among tenant 42's nodes" asks the graph to do something it was not built to do, and the two obvious strategies both break. This is where naive designs fall over in production, and it's where an interviewer will push you.

2.6Sub-Concept: Segments, Immutability, and the Freshness Problem#

Here's a structure you already know from File 13 (and File 11's LSM-trees), appearing for a third time — which should tell you it's a law, not a coincidence.

HNSW graphs and IVF cluster assignments are expensive to build and awkward to mutate. Inserting into an HNSW graph requires finding the new node's neighbors and rewiring existing links — doable, but it degrades graph quality over time and requires locking. Deleting is far worse: removing a node can disconnect the graph, orphaning regions so that queries can no longer reach them — and the failure is silent, appearing only as declining recall. IVF is worse still: its clusters were computed from a snapshot of the data distribution, so as data drifts, the centroids become wrong and the clusters become unbalanced.

So vector databases converge on the same answer as every other system in this bible: buffer writes in a small mutable structure, periodically seal them into immutable segments, and merge segments in the background. Deletes are tombstones — a bit in a deletion bitmap, filtered out at query time, with the space reclaimed only on merge.

The consequences you must be able to state:

2.7Sub-Concept: Chunking#

An embedding model has a max input length (512–8,192 tokens), and even when it can accept a long document, embedding a 50-page PDF into one vector produces a useless average of everything it discusses — a vector pointing at the centroid of "quarterly finance, HR policy, and office snacks," close to nothing in particular. So documents are chunked into passages, each embedded separately.

Why the chunk size is a real trade-off, not a config default. Small chunks (~200 tokens) give precise, focused vectors that match a specific question sharply — but they lose surrounding context, so a chunk saying "This reduced latency by 40%" is a retrieval landmine: it's semantically confident and doesn't say what "this" is. Large chunks (~2,000 tokens) preserve context and coherence but dilute the embedding (one topic among ten) and waste LLM context window on irrelevant text.

The mitigations, each with its own cost: overlapping windows (each chunk repeats ~15% of the previous chunk's tail) so an idea spanning a boundary survives in at least one chunk — at the cost of storing redundant vectors. Semantic/structural chunking — split on markdown headings, paragraphs, or function boundaries rather than a fixed token count — which respects the author's own structure and is nearly always better than naive splitting, at the cost of format-specific code. Small-to-big retrieval: embed the small precise chunk for matching, but return the larger parent section for context — you get precision in retrieval and completeness in the prompt, at the cost of storing the mapping and more prompt tokens. Contextual retrieval: prepend an LLM-generated one-line summary of the document to each chunk before embedding, so the orphaned "This reduced latency by 40%" becomes "From the 2026 caching migration report: This reduced latency by 40%" — a large, well-documented recall win, paid for with an LLM call per chunk at ingest.

The senior framing: "Chunking is where most RAG systems actually fail, and it's not a vector-database problem — it's a document-processing problem that people skip because it's unglamorous."

2.8Sub-Concept: The Reranker (Bi-Encoder vs Cross-Encoder)#

This is the most important sub-concept people leave out, and it explains the shape of every production system in §11.

Your embedding model is a bi-encoder: it encodes the query and the document separately and independently, and compares the two vectors. That independence is precisely what makes it scale — you embed all documents once, offline, months before the query exists, and at query time you do a single embed plus a geometric lookup. Precomputation is the entire reason ANN works.

But independence is also its ceiling: the document's vector was computed without ever seeing the query. It's a fixed, lossy summary that has to serve every possible future question. Nuance is impossible — the model couldn't know which aspect of the document you'd care about.

A cross-encoder takes the query and the document together as one input ([CLS] query [SEP] document) and runs full transformer attention across both, so every query token can attend to every document token. It directly outputs "how relevant is this document to this query?" It is dramatically more accurate — and it cannot be precomputed at all, because it needs both sides. Scoring 10M documents with a cross-encoder means 10M transformer forward passes per query: minutes to hours. Completely infeasible as a retriever.

So you use both, in two stages — and this is the shape of every serious retrieval system on earth:

  10,000,000 docs ──[bi-encoder + ANN]──► 100 candidates ──[cross-encoder]──► top 5
      (cheap, precomputed, approximate)      (expensive, exact, 100 passes ≈ 50ms)
      ── optimizes RECALL ──                 ── optimizes PRECISION ──

Why it works: the expensive model only touches 100 items, so you can afford 10,000× more computation per item. Stage 1 must not miss things (recall); stage 2 makes the fine distinctions (precision). Benefit: typically a 10–30% jump in retrieval quality — the single highest-ROI addition to a mediocre RAG system, usually beating any amount of chunking or embedding-model fiddling. Cost: +50–200 ms of latency and a GPU (or a reranker API). Mitigation: rerank fewer candidates (50 instead of 200), or use a distilled/smaller cross-encoder. This is exactly File 13's §6.6 learning-to-rank two-stage architecture, and File 13's §6.5 ANN discussion, meeting in the middle. Same shape, third time. Notice the pattern: cheap-and-approximate to narrow, expensive-and-exact to order.

2.9Sub-Concept: The Two-Tower Model (how recommendations became vector search)#

To understand why Meta and Google built this infrastructure before LLMs existed: a two-tower (dual-encoder) model has one tower encoding the user (their history, demographics, context) into a vector, and another encoding each item (a video, a song, a product) into a vector in the same space, trained so that dot(user, item) is high for items that user engaged with.

The payoff is architectural: all item vectors can be computed offline in a nightly batch job (hundreds of millions of them), and at request time you embed only the user and do an ANN lookup. Recommendation retrieval becomes nearest-neighbor search, and the ANN index is the recommender. Benefit: 100M candidates narrowed to 500 in ~10 ms. Cost: the towers never see user-item interaction features (the whole point is that they're separate, which is what allows precomputation) — so the model can't learn "this user likes this video because of this specific pairing." Mitigation: the same two-stage pattern as §2.8 — the two-tower model retrieves 500 candidates, and a heavy interaction-aware ranking model orders them. Retrieval and ranking are always separate models at scale.

3Deep-Dive Mechanics — The Life of a Vector and the Life of a Query#

3.1The Write Path (ingesting a document, end to end)#

  SOURCE OF TRUTH (Postgres / S3 / Kafka)  ◄── you MUST keep this (§2.3)
        │  CDC / event
        ▼
┌──────────────────────────────────────────────────────────────────────────┐
│ INGEST PIPELINE                                                          │
│  1. PARSE      PDF/HTML/code → clean text (this step is 80% of the bugs) │
│  2. CHUNK      split ~500 tokens, ~15% overlap, on semantic boundaries   │
│  3. ENRICH     prepend doc context/title to each chunk (§2.7)            │
│  4. EMBED      batch 64–256 chunks → GPU/API → vectors [d=768]           │
│                ⚠ batching matters enormously: GPUs are throughput        │
│                  machines; 1-at-a-time wastes ~95% of the hardware       │
│  5. NORMALIZE  v / |v|  ⇒ now dot product ≡ cosine (§0.2)                │
│  6. QUANTIZE?  float32 → int8 (§5)                                       │
└──────────────────────────────────────────────────────────────────────────┘
        │  upsert(id, vector, metadata)
        ▼
┌──────────────────────────────────────────────────────────────────────────┐
│ VECTOR DB — COORDINATOR                                                  │
│   shard = hash(id) % N          ← random spread; NOT by similarity! §7.1 │
└──────────────────────────────────────────────────────────────────────────┘
        │
        ▼
┌──────────────────────────────────────────────────────────────────────────┐
│ SHARD (one node)                                                         │
│   a. append to WAL                    ─── durable, sequential (File 11)  │
│   b. insert into MUTABLE BUFFER       ─── searched by BRUTE FORCE        │
│   c. replicate to replicas                                               │
│   d. ── every N vectors / T seconds ──►  SEAL: build an immutable        │
│         segment (HNSW graph or IVF lists) over the buffer                │
│   e. ── background ──► MERGE segments; physically drop tombstones        │
└──────────────────────────────────────────────────────────────────────────┘

Three things to notice. First, the buffer is brute-forced. Fresh vectors get exact search while old vectors get approximate search — the opposite of what you'd guess, and it's how the system offers near-real-time visibility without incrementally mutating an expensive graph (§2.6). Second, embedding dominates ingest cost, not the database. A 10M-chunk backfill is a GPU-hours problem; the DB insert is noise. Budget accordingly. Third, the WAL is here for the same reason as everywhere else in this bible (File 11's write-ahead log, File 13's translog): make the durable record cheap and sequential, and build the expensive structure lazily.

3.2The Read Path (a filtered kNN query, end to end)#

  "How do I reset my password?"  + filter: {tenant: 42, lang: "en"}
        │
        ▼  [1] EMBED the query  (same model, same normalization — non-negotiable)
        │       ~5–50 ms  ← often the LARGEST single latency item! cache it.
        ▼
  q = [0.03, −0.44, …]  (768 floats, unit length)
        │
        ▼  [2] PLAN: how selective is the filter?
        │      ├─ very selective (<1% of corpus) ─► fetch matching IDs, BRUTE FORCE them
        │      ├─ very broad (>50%)              ─► ANN search + post-filter
        │      └─ middling                       ─► FILTERED graph traversal (§6)
        ▼
┌───────────────────────── COORDINATOR ─ scatter to ALL shards ────────────┐
│    (can't route by similarity — neighbors live everywhere, §7.1)         │
└──────────────────────────────────────────────────────────────────────────┘
    │             │              │             │
    ▼             ▼              ▼             ▼
 Shard 0       Shard 1        Shard 2       Shard 3
   for each segment:
     • HNSW: enter at top layer → greedy descend → beam search (ef) at L0
       …evaluating the metadata filter DURING traversal
     • compute distances on QUANTIZED vectors (fast, approximate)
     • keep local top-k' (k' > k, oversampled)
   ┌── RESCORE: re-rank local top-k' using FULL-PRECISION vectors ──┐
   │   (recovers most of the recall the quantization cost you, §5.4)│
   └────────────────────────────────────────────────────────────────┘
   return [(id, score) × k]        ← ids + scores only, no payloads
    │             │              │             │
    └─────────────┴──────┬───────┴─────────────┘
                         ▼
       coordinator merges 4×k, sorts, keeps global top-k
                         ▼
       [3] FETCH payloads/text for the k winners only     ← File 13's
                         ▼                                  query-then-fetch,
       [4] RERANK with a cross-encoder (§2.8) → top 5      exactly
                         ▼
       [5] BUILD PROMPT: system + retrieved chunks + question → LLM (§8)

The latency budget, and the thing that will surprise you:

The lesson, and it's an interview-winning one: in a RAG system, arguing about whether ANN takes 5 ms or 15 ms is arguing about 0.3% of the user's wait. The LLM is 90% of it. Optimize recall and cost, not ANN latency — and if you want perceived speed, stream the LLM's tokens. Candidates who micro-optimize ef_search while ignoring a 3-second generation are optimizing the wrong system.

4ANN Index Algorithms — Exhaustive Breakdown#

Every algorithm gets the full treatment. This is the heart of the file.

4.1Flat (Brute Force) — the baseline you must respect#

What it is. Store vectors in a contiguous array. Compare the query to every one. Keep a top-k heap.

How it works. For each of N vectors, compute the dot product with the query (SIMD-vectorized, 16 floats per instruction), push onto a size-k min-heap if it beats the heap's minimum. One linear pass, perfectly sequential memory access.

Worked example. 100k vectors × 768 dims × 4 B = 307 MB. Streaming that at ~50 GB/s ≈ 6 ms. Fully parallel across cores → ~1 ms on 8 cores. Recall: exactly 1.0.

Why it works. No cleverness — but perfectly sequential access means the hardware prefetcher is at 100% efficiency and there are zero branch mispredictions. It's the only access pattern the memory subsystem truly loves (File 11's sequential-vs-random lesson, holding true at the nanosecond scale).

Pros. Perfect recall, zero build time, zero memory overhead beyond the vectors, trivially supports filters (just skip non-matching vectors mid-scan — no graph to break), instant updates (append to an array), and no tuning knobs to get wrong.

Cons. O(N·d) per query. At 10M vectors that's 600 ms (§0.4) — a wall you hit hard and suddenly.

Complexity. Time O(N·d); memory O(N·d); build O(1).

When to use it. Under ~100k vectors, or when N × QPS is small, or when perfect recall is a requirement (compliance, legal discovery, ground-truth generation). Also: a GPU changes this math dramatically — an A100 brute-forces ~10M vectors in ~10 ms because it has ~2 TB/s of memory bandwidth, so GPU brute force beats CPU ANN up to surprisingly large N. Decision rule: always start here, and only build an index when you've measured that you must.

4.2IVF (Inverted File Index) — clustering#

What it is. Partition the space into buckets by clustering; search only the few buckets nearest the query. The name is a nod to File 13's inverted index: instead of term → docs, it's centroid → vectors.

How it works, step by step.

Sub-Concept: k-means. An algorithm to partition points into k groups. Pick k random points as centroids. Repeat until stable: (a) assign every point to its nearest centroid; (b) move each centroid to the mean of its assigned points. It converges to a local optimum — not the global best, but consistently good. It's the standard tool because it's simple and O(N·k·d·iterations). Its relevant weakness: k-means assumes roughly spherical, similar-sized clusters, and real embedding data is lumpy — so some IVF buckets end up huge and some nearly empty, which directly causes IVF's imbalance problem below.

The buckets form Voronoi cells — a term worth defining because it recurs across spatial computing: given a set of "seed" points (here, the centroids), the Voronoi cell of a seed is the region of space closer to that seed than to any other seed. Assigning every vector to its nearest centroid is exactly carving the space into these cells; the cell boundaries are the perpendicular midlines between neighboring centroids. The picture:

   space partitioned into Voronoi cells by centroids (●)
   ┌──────────┬──────────┬──────────┐
   │    ●     │    ●     │    ●     │      query ★ lands in cell 5
   │  cell 1  │  cell 2  │  cell 3  │      nprobe=3 → search cells 5, 2, 6
   ├──────────┼──────────┼──────────┤      = ~3/9 of the data = 3× speedup
   │    ●     │   ★ ●    │    ●     │
   │  cell 4  │  cell 5  │  cell 6  │      ⚠ the true nearest neighbor might
   ├──────────┼──────────┼──────────┤        sit just across the border in
   │    ●     │    ●     │    ●     │        cell 8 — and you'd never see it.
   │  cell 7  │  cell 8  │  cell 9  │        THAT is where recall is lost.
   └──────────┴──────────┴──────────┘

Worked example. 10M vectors, nlist=4000 → ~2,500 vectors per bucket. nprobe=16 → search 16 × 2,500 = 40,000 vectors instead of 10,000,000 — a 250× speedup, at ~90–95% recall.

Why it works. Near neighbors usually fall in the same or an adjacent Voronoi cell, so a handful of cells contain almost all of the true top-k. nprobe is a direct, honest recall dial: nprobe = nlist degenerates to exact brute force with 100% recall; nprobe = 1 is fastest and leakiest.

Pros. Very low memory overhead — just nlist × d floats for centroids plus one integer per vector for its bucket ID; the graph-free structure means ~4 bytes/vector of overhead versus HNSW's hundreds. Build is fast and parallel. nprobe is tunable at query time, so you can trade recall for latency per request without rebuilding — an underrated operational superpower. And it composes beautifully with filters and with PQ (§5.2).

Cons. The boundary problem: a true neighbor sitting just across a cell border is missed unless nprobe is raised (which costs latency). Clusters become stale: centroids were trained on a snapshot, so as data drifts, buckets become imbalanced — one bucket ends up with 500k vectors and probing it is as slow as brute force. Requires a training step (unlike HNSW), so you need a representative sample before you can index anything. And recall is meaningfully worse than HNSW at the same latency in most benchmarks.

Complexity. Query O(nlist·d + (nprobe/nlist)·N·d); build O(N·nlist·d) for training and assignment; memory overhead ~4 bytes/vector.

When to use it. When memory is your binding constraint and you can accept slightly lower recall — which, at 100M+ vectors, is very often the honest situation. It's the base layer for the billion-scale combination IVF-PQ (§5.2). Prefer it over HNSW when you need per-query recall tuning, when your data is large and mostly static, or when you must fit an index into a budget HNSW can't reach. Avoid when data drifts fast (retraining centroids is a full rebuild) or when you need the last few points of recall.

4.3HNSW (Hierarchical Navigable Small World) — the default#

What it is. A multi-layer graph where you greedily walk toward the query, using sparse long-range links at the top for coarse navigation and dense short-range links at the bottom for precision. A skip list, generalized from a line to a metric space.

The intuition first — "six degrees of separation." A small-world network has the remarkable property that any two nodes are reachable in very few hops, despite most connections being local. Your social network is mostly people in your city (short links), but a handful of long-range friendships (a cousin in Tokyo) collapse the network's diameter to ~6. HNSW builds that structure deliberately: long-range links to cross the space in a few jumps; short-range links to home in.

How it works, step by step.

Build. Insert vectors one at a time. Each new node is assigned a maximum layer l drawn from an exponentially decaying distribution (l = floor(−ln(uniform(0,1)) · mL)), so ~1/2 of nodes exist only at layer 0, ~1/4 reach layer 1, ~1/8 layer 2 — the higher the layer, the sparser and more "express" it is. The node is then inserted into every layer from l down to 0, and at each layer, connected to its M nearest neighbors found by searching that layer.

The crucial subtlety — neighbor selection. HNSW does not simply connect to the M closest nodes. It uses a heuristic that prefers a diverse neighbor set: a candidate is pruned if it's closer to an already-selected neighbor than it is to the new node. Why? If you connected only to the M nearest, in a dense cluster all your links point inward at the same tight blob, and the graph fragments into islands with no way to travel between them — a greedy walk gets trapped in a local minimum and never reaches the right region. The diversity heuristic deliberately keeps some longer links so the graph stays navigable. This is the difference between HNSW and a naive kNN graph, and it's the detail that shows an interviewer you've read the paper.

Search. Enter at the single top-layer node. Greedily move to whichever neighbor is closer to the query; when no neighbor improves, drop to the next layer down and repeat. At layer 0, run a beam search: maintain a candidate list of size ef_search, always expanding the closest unexpanded candidate, and keep the best k found. ef_search is your recall dial — bigger beam, more of the graph explored, higher recall, more latency.

 L2 ●───────────────────────────────────● ← ~1/8 of nodes: express highways
     ╲                                 ╱
 L1   ●────────●──────────●──────────●    ← ~1/4 of nodes: regional roads
       ╲      ╱ ╲        ╱ ╲        ╱
 L0    ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●    ← ALL nodes: local streets, M links each
                    ▲
                 query ★: enter top → 2 hops → drop → 3 hops → drop → beam search
                 total: ~50–200 distance computations out of 10,000,000 vectors

Worked example. 10M vectors, M=16, ef_search=100. A query evaluates roughly 100–200 distance computations — versus 10,000,000 for brute force. That's a ~50,000× reduction in work, at ~98–99% recall, in ~2–5 ms.

Why it works. The layer hierarchy makes the expected number of hops O(log N) (each layer roughly halves the remaining distance in graph terms — the same argument as a skip list), and the diversity heuristic guarantees the greedy walk doesn't get stuck. It's an approximation because greedy descent can settle in a local minimum; the beam width ef_search is exactly your insurance against that.

Pros. The best recall-per-latency of any in-memory index, consistently, across nearly every public benchmark (ann-benchmarks). It needs no training step — insert and go, from the first vector. It supports incremental inserts natively. ef_search is tunable at query time, so recall is a per-request decision. This is why it's the default in Elasticsearch (File 13), Qdrant, Weaviate, Milvus, pgvector, and Lucene.

Cons — be precise, because this is where interviews go.

Complexity. Query O(log N) hops × M·ef distance computations; build O(N·log N·M·d); memory O(N·d + N·M·4 bytes).

When to use it. The default for anything from ~100k to ~100M vectors that fits in RAM, where recall matters and you can pay for memory. Choose IVF instead when RAM is the binding constraint; choose DiskANN when the dataset can't fit in RAM at any acceptable price; choose flat below 100k.

4.4LSH (Locality-Sensitive Hashing) — the theory that lost#

What it is. Hash functions designed so that similar vectors collide on purpose. Look up the query's hash bucket; the neighbors are probably in it.

How it works (random hyperplane LSH, for cosine). Generate b random hyperplanes through the origin. For each vector, record which side of each hyperplane it falls on: hᵢ(v) = sign(v · rᵢ) — one bit per hyperplane. Concatenate the bits into a b-bit signature. Two vectors landing on the same side of every hyperplane must be angularly close, so identical signatures ⇒ similar vectors. Use the signature as a hash-table key; query by hashing the query and scanning its bucket. Repeat with L independent hash tables to catch neighbors that got separated by an unlucky hyperplane.

Worked example. b=16 bits → 65,536 buckets. 10M vectors → ~150 vectors per bucket. Scan the query's bucket in L=10 tables → ~1,500 candidates instead of 10M. Recall: ~70–85% — noticeably worse than HNSW at comparable cost.

Why it works. The probability that two vectors are separated by a random hyperplane is exactly θ/π (their angle over π), so the collision probability is a clean, provable function of similarity. LSH is the only ANN method with rigorous theoretical guarantees on the recall/cost trade-off.

Pros. Provable guarantees; trivially parallel and shardable (a hash is a hash); cheap to build; supports streaming inserts with no rebuild; and the binary signatures are tiny, so LSH-style hashing survives as a deduplication tool (MinHash for near-duplicate documents) even where it lost as a retrieval index.

Cons — and this is why you'll rarely deploy it. It's data-oblivious. The hyperplanes are random; they know nothing about where your data actually lies. Real embeddings occupy a thin, lumpy manifold, not a uniform cloud — so most random hyperplanes slice through empty space and waste their bit. Learned structures (IVF's k-means centroids, HNSW's data-driven graph) adapt to the actual distribution, which is why they beat LSH by a wide margin empirically. To reach HNSW-level recall, LSH needs many tables and thus more memory than HNSW — losing on both axes at once. Bucket sizes are also wildly uneven for skewed data.

Complexity. Query O(L·b·d + candidates·d); memory O(L·N) for the tables plus the vectors.

When to use it. Almost never for kNN retrieval today — it is comprehensively beaten. Know it because (a) interviewers ask it as a theory question, (b) it's the intellectual ancestor of binary quantization (§5.3), which is current best practice, and (c) MinHash-LSH remains the right tool for near-duplicate detection over sets. Decision rule: if a candidate proposes LSH for a modern vector search system, they learned ANN from a 2012 textbook.

4.5DiskANN / Vamana — breaking the RAM wall#

What it is. A graph index engineered so the graph lives on SSD while a compressed copy of the vectors lives in RAM — letting one machine serve a billion vectors that would otherwise need a hundred.

Why it exists. §0.4's arithmetic: a billion 768-dim vectors is 3 TB of RAM. At cloud prices that's an eye-watering monthly bill for one index. But 3 TB of NVMe is cheap and ordinary. The problem is that HNSW on disk means ~100 random reads per query (§4.3 cons). DiskANN's entire contribution is restructuring the graph so that the number of disk round-trips per query drops to single digits.

How it works — three ideas that only work together.

  RAM  (small):  PQ vectors, 32 B each   →  1B vectors = 32 GB  ← navigation
  SSD  (large):  [full vector | neighbor list] per node, page-aligned
                 →  1B × ~3 KB = 3 TB   ← ~5–10 page reads per query
  Result: ONE machine, 1 BILLION vectors, ~5 ms, ~95% recall.
          Same corpus in pure HNSW: ~3 TB RAM ≈ a rack of machines.

Why it works. It exploits the memory hierarchy (File 02) exactly as designed: keep a lossy but sufficient representation in the fast tier for decisions, and touch the slow tier only for the few verifications that matter. The α-pruning is what makes the number of slow-tier touches small enough to matter.

Pros. ~10–50× cheaper per vector than in-RAM HNSW — often the difference between a project being fundable and not. Excellent recall (~95%+). Proven at Bing/Azure scale.

Cons. Latency is a few ms higher than in-RAM HNSW (you're touching an SSD). Build is very expensive (Vamana requires multiple passes; billion-scale builds are a batch job measured in hours on a big machine). Updates are awkward — the graph is disk-resident and page-aligned, so **FreshDiskANN exists specifically to bolt on an in-memory delta index for recent writes, merged periodically (§2.6's pattern, again). And it's sensitive to SSD quality**: on network-attached or throttled storage, the whole premise collapses.

Complexity. Query O(hops × PQ-distance) in RAM + ~5–10 SSD reads; memory O(N · pq_bytes); build very expensive.

When to use it. When your vector count × dimensions exceeds what you'll pay for in RAM — practically, above ~100M vectors — and you can tolerate ~5–10 ms and rare, batched rebuilds. Don't reach for it below that; the operational complexity isn't worth it when HNSW fits.

4.6ScaNN (Google) — quantization that knows it will be ranked#

What it is. Google's index, built on a genuinely clever insight: standard quantization minimizes the wrong error.

The insight, which is worth understanding properly. Every quantizer (§5) approximates a vector v with a codeword ṽ, minimizing reconstruction error |v − ṽ|². That treats all error equally. But **you don't care about reconstructing the vector — you care about the ranking of dot products. Decompose the error into two parts: the component parallel to the query direction, and the component orthogonal** to it. Only the parallel component changes the dot product; the orthogonal component is essentially harmless. Moreover, the errors that actually hurt are those on high-scoring items (a mistake that demotes the true #1 out of your top-10 is catastrophic; a mistake among items ranked 900th vs 901st is invisible). So ScaNN uses anisotropic vector quantization: a loss function that weights parallel error far more heavily than orthogonal error, deliberately accepting more total reconstruction error in exchange for more accurate dot products among the top candidates.

How it works. A three-stage pipeline: partition (tree/k-means, like IVF) → score with anisotropically-quantized vectors using SIMD-friendly 4-bit lookup tables → rescore the top candidates with full-precision vectors.

Worked example. On the standard glove-100 benchmark, ScaNN reaches ~95% recall at roughly 2× the throughput of the best HNSW configuration — a real, reproducible gap that comes purely from the quantizer knowing what it's optimizing for.

Pros. Best-in-class recall-per-QPS for MIPS (maximum inner-product search) workloads; excellent memory efficiency; battle-tested inside Google (it's what serves their own retrieval).

Cons. More complex to tune (partitioning + quantization + rescoring each have knobs). It's optimized for inner product; the anisotropic argument is weaker for pure L2. Historically less ecosystem support outside Google's stack, though it's now in pgvector (as pgvectorscale's cousin) and elsewhere. Requires a training step, so it inherits IVF's drift problem.

Complexity. Similar shape to IVF-PQ, with a better constant factor — which, at Google's scale, is worth a data center.

When to use it. When you're doing large-scale inner-product retrieval (recommendations, two-tower serving) and throughput-per-dollar is the objective, and you're willing to tune. Use HNSW when you want good results with one knob.

4.7Comparison Table & Decision Rule#

The decision rule, in plain English:

Under 100k vectors → brute force. No index, no vector database. Use numpy, or pgvector with no index. Anything else is over-engineering, and an interviewer is watching for exactly this. 100k–10M and it fits in RAM → HNSW. It's the default for a reason: best recall per millisecond, no training, one knob (ef_search). Add int8 scalar quantization + rescoring (§5.1) to cut memory 4× for nearly free. 10M–100M → HNSW with quantization if you can afford the RAM; IVF-PQ if you can't. Here the decision is genuinely a budget conversation, and the right answer is "measure recall against cost on our data." Over 100M → DiskANN (one machine, SSD-backed, ~10–50× cheaper) or IVF-PQ sharded across machines. At this scale, RAM cost dominates every other consideration. Throughput-critical inner-product recommendations → ScaNN. And always: measure recall@k on YOUR data with YOUR model. Public benchmarks use datasets whose geometry may look nothing like yours; a config that's 99% recall on glove-100 can be 85% on your corpus.

5Quantization & Compression — Exhaustive Breakdown#

§0.4 established RAM as the budget. Quantization is how you buy it back. Every technique below is "make the vectors smaller, lose some accuracy, then win the accuracy back with a rescoring pass."

5.1Scalar Quantization (float32 → int8)#

What it is. Replace each 4-byte float with a 1-byte integer. 4× smaller, immediately.

How it works. For each dimension (or globally), find the min and max values across the corpus, then linearly map that range onto the 256 buckets of an int8: q = round((v − min) / (max − min) × 255). Reverse it at read time. That's the entire algorithm.

Worked example. A dimension ranging [−0.5, 0.5]. Value 0.031 → round((0.031 + 0.5)/1.0 × 255) = round(135.4) = 135. Decode: 135/255 − 0.5 = 0.0294. Error: 0.0016 — about 0.2% of the range. Across 768 dimensions, these tiny independent errors largely cancel in the dot product (they're roughly zero-mean and independent, so the sum's error grows as √d, not d), which is exactly why the ranking barely moves.

Why it works. Embedding values cluster tightly around zero in a narrow range, so 256 evenly-spaced levels resolve them finely. And the errors are noise-like, not systematic.

Pros. Recall loss is typically under 1% — this is close to a free 4× memory cut, which is why it should be your first move, before anything more exotic. It's simple, it's fast (int8 SIMD is faster than float32 SIMD — more values per instruction, so you often get a speedup too), and it's easy to reason about.

Cons. Only 4×, which isn't enough at billion scale. It's vulnerable to outliers: one dimension with a rare value of 50.0 stretches the range so that all the normal values crush into a handful of buckets, destroying precision. Mitigation: clip at the 99th percentile before quantizing, accepting large error on rare outliers to protect the common case.

Complexity. O(d) to encode/decode; memory N·d bytes instead of 4·N·d.

When to use it. Always, essentially by default, for any index over ~1M vectors. The recall cost is a rounding error and the memory savings are real. Decision rule: if you're not doing at least int8, you're paying 4× for accuracy nobody can perceive.

5.2Product Quantization (PQ) — the billion-scale workhorse#

What it is. Chop the vector into sub-vectors, replace each sub-vector with the ID of the nearest entry in a small learned codebook. 32–64× smaller.

How it works, step by step.

  v = [ 0.1 … 0.4 | 0.7 … 0.2 | ...  ]   768 floats = 3072 bytes
        └ sub 1 ─┘ └ sub 2 ─┘  … 96 sub-vectors of 8 dims

  sub 1 → nearest of its 256 centroids → id 37  →  1 byte
  sub 2 → nearest of its 256 centroids → id 194 →  1 byte
        …
  encoded v = [37, 194, 12, ...]  = 96 bytes        ← 32× smaller

  QUERY TIME:  build lookup table  LUT[96][256]  once (~24k distance computations)
               dist(q, v) ≈ LUT[0][37] + LUT[1][194] + LUT[2][12] + …
               = 96 cache-friendly lookups + adds — NO decompression, NO float math

Worked example. 1 billion × 768-dim: raw = 3 TB. PQ at 96 bytes = 96 GB. That fits on one large machine. This single technique is what makes billion-scale vector search economically possible, and it's why PQ (from Jégou et al., 2011, at INRIA — the paper that led to FAISS) is one of the most consequential algorithms in this file.

Why it works. Independently quantizing sub-spaces gives an enormous effective codebook: 256 choices per sub-space across 96 sub-spaces is 256^96 distinct representable vectors — astronomically more expressive than any single codebook you could train or store. You get the expressiveness of a colossal codebook with the memory of 96 tiny ones. And the ADC table trick means the compression makes queries faster, not slower — you replaced float arithmetic with table lookups.

Cons — and these are serious. Recall drops meaningfully, typically to 0.80–0.92 — a real, perceptible degradation, not a rounding error. PQ assumes the sub-spaces are independent, which is false for real embeddings (dimensions are correlated), and the resulting error is systematic rather than noise-like. It requires training on a representative sample, so it inherits the drift problem: as your data distribution shifts, the codebooks get worse, silently. And the compressed vectors cannot be reconstructed accurately — you've genuinely destroyed information, so if you ever need the original you must have kept it somewhere.

Mitigations, both standard. (1) OPQ (Optimized PQ): learn a rotation matrix applied before splitting, which redistributes variance evenly across sub-spaces and de-correlates them — recovering a few points of recall for one extra matrix multiply. (2) Rescoring (§5.4) — the big one. Retrieve 10× more candidates using PQ, then re-rank those with full-precision vectors fetched from disk or a second tier.

Complexity. Encode O(m·k·(d/m)); query O(m·k·(d/m)) to build the LUT, then O(m) per vector — independent of d; memory **m bytes per vector**.

When to use it. When memory is the binding constraint and you have a rescoring stage to recover recall. It's the foundation of IVF-PQ and DiskANN. Don't use it below ~10M vectors — you're paying real recall for memory you didn't need to save. Decision rule: int8 first (free 4×); PQ only when 4× isn't enough, and never without rescoring.

5.3Binary Quantization — the 32× sledgehammer#

What it is. Keep one bit per dimension: is this value positive or negative? A 768-dim float vector becomes 96 bytes → 32× smaller — and distance becomes a Hamming distance, computed with XOR and POPCNT.

How it works. bit_i = 1 if v_i > 0 else 0. Similarity between two binary codes = the number of differing bits = popcount(a XOR b). A modern CPU computes this over 768 bits in ~4 instructions. Compare that to 768 float multiply-adds: this is roughly 40× faster, not just smaller.

Worked example. [0.03, −0.44, 0.87, −0.01] → 1011... wait — note the −0.01, a value hovering right at zero, which becomes 0. A tiny perturbation to +0.01 flips the bit entirely. Values near zero are where binary quantization destroys information, and that's precisely its weakness.

Why it works — when it works. It's the sign-based LSH idea (§4.4) with the axes as hyperplanes. For high-dimensional vectors from models trained to spread information across many dimensions, the sign pattern alone carries a startling amount of the semantic signal — the sheer number of dimensions provides redundancy. The critical caveat: this works well for 1024+ dimensional models (Cohere's embeddings famously retain ~95% of quality binarized) and works badly below ~768 dimensions, because there simply aren't enough bits of redundancy to absorb the loss. This is a model-dependent decision, and you must measure it.

Pros. 32× memory reduction, and a ~40× distance-computation speedup from POPCNT. It makes RAM-resident billion-scale search plausible on modest hardware.

Cons. Standalone recall is poor (0.70–0.85) — unusable without rescoring. Dimensions near zero are effectively randomized. It's highly sensitive to the model.

Complexity. O(d/64) machine words per comparison; memory d/8 bytes per vector.

When to use it. **As the first stage of a two-stage retrieval, essentially always paired with rescoring (§5.4): binary-scan a huge candidate pool absurdly fast, then rescore the top few hundred with int8 or full-precision vectors. The combination — binary for the funnel, full precision for the finish — is close to a free lunch and is now standard practice at Cohere, Qdrant, and Elasticsearch.** Never use it alone.

5.4Rescoring / Oversampling — the technique that makes all the others viable#

What it is. Retrieve more candidates than you need using the cheap compressed representation, then re-rank those candidates using the accurate representation. It's the same two-stage idea as §2.8 and File 13's LTR, applied at the byte level.

How it works. Want top-10 with binary quantization? Retrieve the top 100–400 by Hamming distance (blindingly fast over a compressed index), fetch the full-precision vectors for just those 100–400 (from RAM's cold tier, or from SSD, or from an object store), compute exact distances on that tiny set, and return the true top-10 of them.

Worked example, with numbers that make the point. 100M vectors, 1024-dim. Binary index: 12.8 GB — fits comfortably in RAM. Full float32 vectors: 400 GB — lives on SSD. Query: Hamming-scan the binary index (~2 ms), take the top 200, read 200 × 4 KB from SSD (~200 random reads ≈ 2 ms, or from a page cache ≈ 0), rescore exactly (~0.02 ms). Recall jumps from 0.80 back to ~0.97. Total: ~5 ms, on a machine with 16 GB of RAM instead of 400 GB.

Why it works. The compressed representation is bad at fine ranking but good at coarse filtering — it reliably gets the true top-10 somewhere into its top-200, even though it scrambles their order. So you use it for what it's good at (throwing away 99.9998% of the corpus) and use the expensive representation for what it's good at (ordering a tiny set). The information the quantizer destroyed only mattered for the last step, and you didn't do the last step with the quantizer.

Pros. Recovers nearly all the lost recall for a small, bounded, predictable cost. It decouples memory from accuracy, which is the whole game.

Cons. Requires storing the full-precision vectors somewhere (SSD or a cold tier) — so you haven't eliminated the storage, you've moved it to a cheap tier. Adds a fetch step, and if that fetch is 200 random reads on a slow disk, your latency budget evaporates. Oversampling too aggressively (retrieving 10,000 to return 10) erases the speedup entirely.

Complexity. +O(oversample × d) for the exact pass, plus oversample random reads.

When to use it. Whenever you quantize below int8. It is not optional with PQ or binary — it is the other half of the technique. Decision rule: quantize to fit your RAM budget, then oversample by 10–40× and rescore to buy the recall back. That combination — not the quantizer alone — is what the state of the art actually looks like.

5.5Comparison Table & Decision Rule#

Decision rule: "Start at float32. Move to int8 immediately — it's 4× for under 1% recall, and it's faster. If you're still over budget, go to binary or PQ with 10–40× oversampling and full-precision rescoring, which gets you 32× compression at ~97% recall. Above 100M vectors, combine: PQ or binary in RAM for navigation, full precision on SSD for the final rescore — which is precisely DiskANN. And measure recall at every step on your own data, because every one of these numbers is model-dependent."

6The Filtered-Search Problem (the hardest thing in vector search)#

This is where interviews are won, because it's where the naive mental model shatters. Query: *"documents similar to this, **where tenant_id = 42**"* — tenant 42 owns 0.1% of a 100M-vector index.

Why this is hard, stated precisely. The HNSW graph was built purely from geometry. Its edges encode "these two vectors are close," not "these two vectors belong to the same tenant." Tenant 42's 100,000 vectors are scattered uniformly through the graph like dust. There is no region of the graph that is "tenant 42's neighborhood," and no edge that means "stay in tenant 42." The index simply does not know the filter exists.

6.1Strategy A: Post-Filtering (search then filter)#

How it works. Run a normal ANN search for the top-k, then discard results failing the filter.

Why it catastrophically fails. With tenant 42 at 0.1% of the corpus, a top-100 ANN search returns ~0.1 matching results. You asked for 10 and got zero. So you oversample: fetch top-10,000 and hope 10 survive. Now you've done 100× the work — and you still have no guarantee, because if tenant 42 has no vectors in the query's geometric neighborhood, you can fetch the top-100,000 and get nothing while a perfectly good tenant-42 match sits 3% further away, never examined.

Pros. Trivial to implement over any index; zero changes to the graph; works fine when the filter is broad. Cons. Silently returns fewer than k results, or none at all — and the failure is worst exactly when the filter is most selective, which is the common case for multi-tenancy. When to use it. Only when the filter matches >50% of the corpus (e.g., language = 'en' on an English-dominant corpus), where the oversampling factor is ~2× and harmless.

6.2Strategy B: Pre-Filtering (filter then brute force)#

How it works. Use the metadata index (a bitmap or inverted index over tenant_id, exactly like File 13's keyword field) to get the set of matching IDs, then brute-force the query against only those vectors.

Why it works. Perfect recall, guaranteed — you looked at every candidate that qualified. And when the filter is tight, the candidate set is small enough that brute force is genuinely fast: 100,000 vectors × 768 dims = 300 MB ≈ 6 ms (§0.4). Note that the filter did the ANN index's job for it, cutting the corpus by 1000×.

Pros. Recall = 1.0. Simple. Fast when selective. And it degrades gracefully — a tighter filter makes it faster, the exact opposite of post-filtering. Cons. Cost is linear in the filter's result-set size. A filter matching 10M vectors means brute-forcing 10M vectors — 600 ms, unusable. And it needs an efficient way to materialize the ID set (a bitmap index, which costs memory). When to use it. When the filter matches under ~1% of the corpus, or under ~50k–100k vectors absolute. This is the right answer for tight multi-tenant filters, and saying so demonstrates that you know brute force is a legitimate tool, not a failure.

6.3Strategy C: Filtered Graph Traversal (single-stage / in-place filtering)#

How it works. Walk the HNSW graph normally, but evaluate the filter at each node during traversal and only admit passing nodes into the result heap — while still **traversing through failing nodes** to reach other regions.

That distinction is the crux. If you refused to traverse through non-matching nodes, the graph would fragment: tenant 42's vectors are scattered dust, and the paths between them run through other tenants' nodes. Cut those paths and the greedy walk gets marooned in a dead end — recall collapses. So you walk through everything and only collect what matches.

Why it works — and where it breaks. It preserves the graph's connectivity, so navigation still works. But you're now paying for hops through nodes you'll never return. As the filter gets more selective, the ratio of useful-to-wasted hops collapses, and at some point you're traversing most of the graph — slower than the pre-filter brute force would have been. The graph's O(log N) navigation guarantee quietly evaporates when most nodes are filtered out, because that guarantee assumed all nodes were valid destinations.

Pros. Good recall across the middle of the selectivity range (1%–50%), where both A and B are bad. No oversampling guesswork. Cons. Slower per hop (a filter check per node — which must be a cheap bitmap lookup, or it dominates). Recall still degrades at high selectivity. Implementation complexity is real. Qdrant's refinement is worth naming: it estimates the filter's cardinality first and, when a filter is very selective, additionally builds extra graph links among the matching subset so that dense filtered subsets stay navigable on their own.

When to use it. The middle band, 1%–50% selectivity. It's the reason modern vector databases (Qdrant, Weaviate, Milvus) advertise "filterable HNSW" — they're solving exactly this band.

6.4Strategy D: Partitioning by the Filter (make the problem disappear)#

How it works. If the filter is nearly always the same field — tenant_id, in the classic SaaS case — don't filter at all. Give each tenant its own index (a "namespace," "collection," or "partition"). The query hits only that tenant's small HNSW graph, which contains only qualifying vectors. Filtering becomes routing.

Why it works. The filter has been promoted from a query-time predicate to a data-layout decision — the same move File 13 made with time-based indices for logs (a time filter becomes "skip whole indices") and Uber Eats made with geo-cells. Strong systems delete problems with layout rather than solving them with cleverness.

Pros. Perfect recall, tiny per-tenant graphs (fast!), clean tenant isolation (a genuine security and compliance win — one tenant's data physically cannot leak into another's results), and trivial per-tenant deletion for GDPR. Cons. It only works for one filter dimension — you can partition by tenant or by language, not both, without a combinatorial explosion of partitions. Thousands of tiny indexes carry real per-index overhead (each HNSW graph has fixed costs, and 10,000 tenants × a small graph each wastes a lot of memory) — this is File 13's oversharding lesson in a new costume. And it can't handle cross-partition queries at all. Mitigation: hybrid approaches — a dedicated namespace per large tenant, and one shared, filtered index for the long tail of small tenants. This mirrors File 13's "whales get their own index" advice exactly. When to use it. Whenever a single, high-cardinality, always-present filter dominates your workload — which describes essentially every B2B SaaS product. If an interviewer describes multi-tenancy, this should be your first sentence.

6.5Comparison Table & Decision Rule#

Decision rule: "First ask whether one filter dominates — if it's tenant_id, partition and stop thinking about it; layout beats cleverness. Otherwise, estimate the filter's cardinality at query time and pick the strategy from it: under ~1% → pre-filter and brute force (perfect recall, and it's fast because* the filter is tight); over ~50% → ANN with post-filtering and light oversampling; in between → filtered graph traversal. A vector database that doesn't estimate cardinality and choose is going to be wrong for half your queries — and 'my query planner picks the strategy from the filter's selectivity' is exactly what a good answer sounds like."*

7Distributed Architecture — Sharding, Freshness, Tiering & Rebuilds#

7.1Sharding: Why You Cannot Shard by Similarity#

The tempting idea: cluster the vectors, put each cluster on its own shard, and route each query to the one shard holding its neighborhood. One shard answers instead of all of them — File 13's scatter-gather tax, eliminated. It's the first thing everyone proposes, and it's wrong. Three reasons:

It's IVF's boundary problem, promoted to a network partition. A query landing near a cluster border has its true neighbors on another machine, and now missing them isn't a few extra distance computations — it's a network hop you didn't make. To be safe you'd query several shards anyway, and you're back to scatter-gather with worse balance.

It creates permanent, unfixable hotspots. Semantic clusters are wildly unequal in both size and popularity. If 30% of your queries are about "password reset," the shard owning that region melts while others idle. And you cannot rebalance, because the shard's identity is its region of space — you can't move half of "password reset" elsewhere without destroying the routing premise.

It's fragile under drift. The clustering was computed from a snapshot. As your corpus evolves, the boundaries become wrong, and fixing them means re-clustering and physically moving vectors between machines.

**So production systems shard *randomly*** — hash(id) % N, exactly like File 13 — and accept scatter-gather: every query goes to every shard, each returns its local top-k, the coordinator merges. Benefit: perfect load balance, trivial rebalancing, and every shard's local index sees a representative sample of the distribution (so its k-means centroids and graph are well-formed). Cost: File 13's tail-latency amplification — p99 is the slowest shard, and with 20 shards the odds that one is mid-GC or cold are uncomfortably high. Mitigation: fewer, bigger shards; replicas plus adaptive replica selection so you route to the fastest copy; per-shard timeouts so one sick node can't hold the response hostage.

The one legitimate exception is §6.4's partitioning by tenant — which is not sharding by similarity, it's sharding by an access-pattern boundary that happens to be perfectly aligned with the queries. That's why it works.

┌───────────────────────── VECTOR DB CLUSTER ─────────────────────────┐
│  COORDINATOR / ROUTER  ── embeds nothing; scatters, merges top-k     │
│         │         │            │            │                       │
│         ▼         ▼            ▼            ▼                       │
│    ┌────────┐┌────────┐  ┌────────┐   ┌────────┐                    │
│    │Shard 0 ││Shard 1 │  │Shard 2 │   │Shard 3 │  ← hash(id) % 4    │
│    │ HNSW   ││ HNSW   │  │ HNSW   │   │ HNSW   │    (RANDOM spread) │
│    │ +buffer││ +buffer│  │ +buffer│   │ +buffer│                    │
│    └────────┘└────────┘  └────────┘   └────────┘                    │
│      replicas ×2 each (read throughput + failover, File 08)         │
│                                                                     │
│  METADATA / CONTROL PLANE: shard map, collection config             │
│    (Raft/etcd — consensus for METADATA only, never for vectors —    │
│     exactly File 13's split: control plane consistent, data plane   │
│     fast)                                                           │
│                                                                     │
│  OBJECT STORAGE (File 09): raw vectors + built segments             │
│    ⇒ nodes are stateless-ish; a new replica downloads a prebuilt    │
│      index rather than rebuilding the graph from scratch            │
└─────────────────────────────────────────────────────────────────────┘

That last box deserves emphasis: modern vector databases separate storage from compute. Segments are built once and stored in S3; query nodes download and memory-map them. Benefit: adding a replica is a download, not an hours-long graph build; you can scale reads in minutes; and a node loss doesn't mean rebuilding an index. Cost: an added dependency and cold-start latency when a node warms up. Mitigation: prefetching and keeping a warm pool.

7.2Consistency and Freshness#

Vector databases are eventually consistent, and you must know exactly which parts are and why. The write is durable when the WAL says so (§3.1), but the vector isn't in the ANN index until a segment is built. Systems bridge the gap by brute-forcing the small unsealed buffer alongside the ANN search of the sealed segments (§2.6) — so freshness is typically seconds, not minutes.

The deeper issue is that "consistent" is oddly meaningless here. Even a perfectly consistent read returns approximate results (§0.5). Asking whether your vector DB is strongly consistent is asking the wrong question — the answer that matters is "is my recall stable over time?", and that's threatened by tombstone accumulation and graph degradation (§2.6), not by replication lag. This reframing is a strong interview move: the CAP conversation barely applies to a system whose reads are approximate by construction; the real reliability question is recall drift.

7.3Tiering — hot RAM, warm SSD, cold S3#

The cost pyramid, straight from File 02's memory hierarchy:

The pattern to state: navigate in the hot tier with compressed vectors; verify in the warm tier with exact ones; archive everything in the cold tier so you can always rebuild. That's DiskANN as a system architecture, not just an index — and it's the same hot/warm/cold ILM discipline File 13 used for logs, driven by the same economics.

7.4The Rebuild Problem — plan for it before you need it#

Three separate events force a full rebuild, and none of them are exotic:

The mitigation is architectural and must be built up front: keep the source of truth external (Postgres/S3/Kafka — File 09), make the ingest pipeline idempotent and replayable (so you can re-run it from scratch), and build every index behind an alias so blue/green swaps are atomic. Benefit: rebuilds become routine rather than an outage. Cost: double infrastructure during the swap, and real ingest-pipeline engineering that feels like overkill until the day it saves you. The senior sentence: "I design vector infrastructure assuming I will rebuild the entire index at least twice a year — because the model will improve, and if I can't take that upgrade, my product is frozen at last year's quality."

8RAG & AI Infrastructure — The System Around the Index#

The vector database is one box in a larger diagram. In an "design a RAG system" interview, the box is table stakes; the system around it is the actual question.

8.1The Full RAG Pipeline#

 ┌── INGEST (offline, batch) ────────────────────────────────────────────┐
 │  Source (S3/Confluence/DB) → parse → chunk → enrich → EMBED → upsert  │
 │  ⚠ must be idempotent + replayable — you WILL re-run it (§7.4)        │
 └───────────────────────────────────────────────────────────────────────┘

 ┌── SERVE (online, per request) ────────────────────────────────────────┐
 │  user question                                                        │
 │      ├─► [rewrite]  resolve pronouns from chat history, expand acronyms│
 │      │             ("what about its pricing?" → "Pinecone pricing")   │
 │      ├─► EMBED query ──► ANN search (top 50) ─┐                       │
 │      └─► BM25 search (top 50) ────────────────┤ ← File 13's index!    │
 │                                               ▼                       │
 │                                    FUSE (RRF: Σ 1/(60+rank))          │
 │                                               ▼                       │
 │                                    RERANK (cross-encoder) → top 5     │
 │                                               ▼                       │
 │                                    ASSEMBLE PROMPT                    │
 │                                      system + chunks + question       │
 │                                               ▼                       │
 │                                    LLM → stream tokens + citations    │
 └───────────────────────────────────────────────────────────────────────┘

8.2Hybrid Search Is Not Optional#

Why: §0.1 said embeddings are lossy summaries that discard the literal. So a user searching ERR_CONN_4021 or SKU-99213 or a coworker's surname gets garbage from a pure vector search — the embedding has no idea what that token is and returns things that are "vaguely about errors." BM25 nails it instantly. Conversely, "why does my app feel sluggish after the update?" is invisible to BM25 and trivial for vectors.

They fail on disjoint inputs, which is exactly what makes fusing them a genuine win rather than an average. Run both and combine with Reciprocal Rank Fusion: score(d) = Σ_lists 1/(60 + rank_of_d_in_that_list). RRF's beauty is that it uses only ranks, never scores — sidestepping the fact that a BM25 score of 14.2 and a cosine of 0.83 are incomparable quantities with no principled normalization between them (File 13 made the same point). The constant 60 damps the influence of top-1 positions so a single list can't dominate.

Benefit: robust across query types, with typically 10–20% better retrieval than either alone. Cost: two indexes to maintain, two searches per query, and RRF ignores score margins (a runaway-best BM25 hit is treated the same as a marginal one). Mitigation: weighted RRF, or a learned fusion — but plain RRF is a strong default. Decision rule: if your users type identifiers, names, codes, or jargon — and they do — hybrid is mandatory, not an enhancement.

8.3Where RAG Actually Fails (say these in an interview)#

Retrieval failures become hallucinations, not errors. If the right chunk isn't retrieved, the LLM doesn't say "I don't know" — it confabulates from whatever you did give it, fluently and confidently. The vector search's recall failure surfaces as an LLM lying to your user. This coupling is why recall matters more here than in classic search: in File 13, a bad result was a bad link the user could ignore; in RAG, a bad result becomes an authoritative-sounding false statement. Mitigation: always return citations so the user can verify; instruct the model to answer only from the provided context and to say when it can't; and consider a groundedness check (a second model asking "is this answer supported by these chunks?").

Chunking failures (§2.7) — the orphaned pronoun, the table split across two chunks, the answer that spans three sections. This is the most common root cause of a bad RAG system and it lives entirely in the ingest pipeline, not the database.

The "lost in the middle" effect. LLMs attend most strongly to the beginning and end of their context; facts buried in the middle of a long context get measurably ignored. So don't dump 50 chunks in — put the 5 best there, with the single best either first or last. More context is not better context; this is why the reranker (§2.8) earns its keep twice over — it improves what you retrieve and lets you send less.

Stale index. The source updated, the index didn't, and the LLM confidently cites last quarter's policy. Mitigation: CDC-driven ingest (File 07's log-based sync, File 13's advice repeated), plus a freshness timestamp shown in citations.

No evaluation. The killer. Without an eval set — questions with known correct answers, scored for retrieval hit-rate and answer correctness — you are tuning by vibes and every change is a coin flip. Mitigation: build a 100-question golden set on day one, before any tuning. Saying "I'd build the eval harness before I tune anything" is one of the strongest things you can say in an AI-infrastructure interview, because it's what actually separates teams that improve from teams that thrash.

8.4The Cost Model of AI Infrastructure#

Naming these numbers demonstrates you've operated this, not just read about it:

9Pros, Cons & Trade-offs#

Benefits (with the WHY for each)#

Semantic retrieval that lexical search structurally cannot do. Because meaning is encoded as geometry (§0.1), paraphrases, synonyms, translations, and cross-modal matches all become proximity — no synonym list, no hand-curation, no per-language rules.

Sub-linear search in a space where sub-linear was proven hard. ANN indexes (§4) cut work by 4–5 orders of magnitude by giving up a few percent of recall — a trade that's invisible next to the embedding model's own error rate (§0.5).

It unlocks LLMs over private and current data. RAG (§8) is the only economical way to give a model knowledge it wasn't trained on, because the context window is a hard limit and fine-tuning is a poor tool for facts.

One index, many modalities. Text, images, audio, and user behavior all become vectors, so "find similar" is a single primitive across your whole product — the same infrastructure serves search, recommendations, dedup, clustering, and anomaly detection.

Recommendation retrieval at scale. Two-tower + ANN (§2.9) turns "score 100M items" into "one kNN lookup," which is why this infrastructure predates the LLM boom by years.

Costs & Trade-offs (be rigorous)#

It is approximate, permanently and silently. You have a nonzero, invisible error rate. There is no exception log. Mitigation: a recall harness against brute-force ground truth (§2.2), monitored like any other SLI — because without it you cannot distinguish a healthy index from a degraded one.

Memory is the bill, and it's steep. 100M × 768-dim ≈ 300 GB + graph (§0.4). Mitigation: int8 always, then binary/PQ with rescoring, then DiskANN. But note the honest framing: you're moving the cost down the memory hierarchy, not eliminating it.

Model versioning is your recurring existential tax. Vectors are meaningless across models (§2.3), so every upgrade is a full re-embed and rebuild. Mitigation: keep source content durable, make ingest replayable, use aliases and blue/green. This is the constraint that most surprises teams, and it's completely predictable.

It's blind to the literal. SKUs, error codes, names, and rare tokens are exactly what embeddings discard. Mitigation: hybrid search (§8.2). A pure-vector product search is a broken product search.

Filtering is genuinely hard (§6) and is where most naive designs collapse. Mitigation: cardinality-based strategy selection; partition by the dominant filter.

RAG's failure mode is confident lies, not errors (§8.3). Mitigation: citations, groundedness checks, "answer only from context" instructions, and an eval set.

You may not need a new database at all. A dedicated vector DB is another system to run, secure, back up, monitor, and upgrade — and **pgvector in the Postgres you already operate handles tens of millions of vectors with HNSW perfectly well, while giving you real transactions, real joins, real SQL filters (which sidesteps most of §6 — the planner already knows how to combine predicates), and one backup story. Benefit of pgvector: enormous operational simplification, and your filters and your vectors live in the same query. Cost: lower peak QPS, more manual tuning, and Postgres's memory model isn't built for this. Mitigation:** start with pgvector; graduate to a dedicated system when you've measured that you must. Reaching for Pinecone at 200k vectors is exactly the over-engineering interviewers are probing for.

Everything here is model-dependent. Every recall number, every quantization result, every dimension trade-off shifts with the embedding model. Mitigation: benchmark on your data. Public benchmarks are directional, not predictive.

The senior rule: Start with brute force. Graduate to pgvector. Only adopt a dedicated vector database when a measurement — not an intuition — forces it. And from day one, design as if you'll re-embed the entire corpus twice a year: keep the source durable, the pipeline replayable, and the index behind an alias. The vector index is a derived, disposable artifact — the moment you treat it as a source of truth, you've built something you can never upgrade.

10Interview Diagnostic Framework (Symptom → Solution)#

11Real-World Engineering Scenarios#

11.1Spotify — Annoy, and why they chose a "worse" index on purpose#

Spotify built and open-sourced Annoy (Approximate Nearest Neighbors Oh Yeah) to power music and podcast recommendations across ~100M tracks. Annoy consistently loses to HNSW on ann-benchmarks. They used it anyway, for reasons that are a masterclass in engineering judgment.

Takeaway: the "best" index on a benchmark is not the best index for your system. Spotify optimized for static, memory-mappable, shareable, instantly-loading artifacts because their architecture was batch-rebuild-and-ship — and that constraint dominated recall. In an interview, when you're asked to choose an index, ask about the write pattern and the deployment model first. That question is the answer.

11.2Microsoft Bing — DiskANN and SPANN at web scale#

Microsoft runs vector search over billions of web documents for Bing. §0.4's math says a billion 768-dim vectors is ~3 TB of RAM — a rack of machines per index copy, replicated globally. That bill is what produced DiskANN (§4.5) and its successor line.

Takeaway: at billion scale, the memory hierarchy is the architecture (File 02). DiskANN is what you get when you take "RAM for decisions, SSD for verification" seriously and redesign the graph around minimizing slow-tier round-trips. And note point 5: even at the frontier, vector search augments lexical search rather than replacing it.

11.3Meta — FAISS and the two-tower retrieval that predates the hype#

Meta built FAISS (Facebook AI Similarity Search) to serve retrieval across Instagram, Facebook, and Reels — billions of items, ~1B+ users, and the requirement that a feed be assembled in tens of milliseconds. FAISS is the library that made PQ (§5.2) and GPU brute force mainstream, and it's the ancestor of most of the field.

Takeaway: vector search is retrieval, and retrieval is only the first stage of a funnel. Meta's architecture is the canonical shape: cheap approximate retrieval to narrow, expensive exact ranking to order (§2.8) — the same shape as File 13's query-then-fetch, the same shape as LTR, the same shape as binary-quantize-then-rescore. When an interviewer asks you to design a recommendation or search system, draw the funnel first. The funnel is the answer; the index is a detail inside stage one.

12Interview Gotchas & Failure Modes#

Classic Questions (and the crisp answers)#

"Why can't you use a B-tree for vector search?" The curse of dimensionality. B-trees and k-d trees work by pruning — "this subtree is too far, skip it." In 768 dimensions, all pairwise distances concentrate around the same value, so nothing is decisively far and nothing can be pruned; the tree checks nearly every partition and ends up slower than brute force. Space-partitioning indexes degenerate above ~10–20 dimensions. It's geometry, not implementation.

"Why is vector search approximate? Can't you just make it exact?" Exact kNN in high dimensions has no known sub-linear algorithm — you must examine everything, which is 30 GB of reads per query at 10M vectors. ANN gives up a few percent of recall for a 10,000× speedup. And the honest framing: your embedding model's own top-10 is wrong more often than your index is, so buying recall past ~95–98% is buying precision you can't perceive.

"HNSW vs IVF — pick one and defend it." HNSW: best recall per millisecond, no training, incremental inserts, query-time ef tuning — but ~130 bytes/vector of graph overhead, must be in RAM, and deletes degrade it. IVF: ~4 bytes/vector overhead, fast build, nprobe tunable per query — but needs training, suffers cluster drift and boundary misses, and gets lower recall. Default to HNSW under ~100M when RAM allows; use IVF-PQ when memory is the binding constraint; DiskANN above ~100M.

"How would you cut a $30k/month vector RAM bill?" In order: int8 scalar quantization (4× for <1% recall — do this first, and it's faster too). Then binary or PQ with 10–40× oversampling and full-precision rescoring (32× at ~97% recall). Then DiskANN (PQ in RAM, full vectors on SSD, ~10–50× cheaper). Then Matryoshka truncation if the model supports it. And check whether you need all those vectors resident at all — tier the cold ones to S3.

"You have 50,000 documents and need semantic search. Design it." Brute force. 50k × 768 × 4 B = 150 MB; a full scan is ~3 ms and gives perfect recall with zero index, zero tuning, and zero new infrastructure. numpy, or pgvector without an index. The interviewer is testing whether you reach for Pinecone reflexively. Don't.

**"Similarity search with tenant_id = 42 where tenant 42 is 0.1% of the data — what happens?" Post-filtering returns zero results, because the top-100 of a 100M-vector ANN search contains ~0.1 of tenant 42's vectors. The fixes: partition by tenant (a namespace per tenant — the filter becomes routing, recall is perfect, graphs are small); or pre-filter + brute force** (100k vectors ≈ 6 ms, recall 1.0 — and it's fast because the filter is tight). Choose by cardinality at query time.

"How do you upgrade your embedding model?" You can't do it incrementally — v1 and v2 vectors are mutually meaningless, so a half-migrated index is silently corrupt. Re-embed the entire corpus from the durable source into index_v2, validate recall against a ground-truth set, atomically flip an alias, keep v1 for rollback. This is why you never discard your source content and why the ingest pipeline must be replayable.

"Why does hybrid search beat pure vector search?" Because embeddings are lossy summaries that discard exactly what BM25 is best at: rare literal tokens — SKUs, error codes, names, jargon. And BM25 is blind to exactly what embeddings are best at: paraphrase and intent. They fail on disjoint inputs, so fusing them (RRF: Σ 1/(60 + rank), which uses ranks so you never have to normalize incomparable scores) is a real gain, not an average.

"Your RAG system gives confident wrong answers. Debug it." Isolate the stage. Measure retrieval separately from generation: does the correct chunk appear in the top-k at all? If no, it's retrieval — check chunking first (orphaned pronouns, split tables), then hybrid search, then the embedding model's fit for your domain. If yes but the answer is still wrong, it's generation — check for "lost in the middle" (too many chunks; rerank to 5 and put the best first), then prompt instructions ("answer only from context; say when you can't"), then add citations and a groundedness check. Without an eval set separating these two, you're guessing.

"Do you actually need a vector database?" Usually not, at first. pgvector in your existing Postgres handles tens of millions of vectors with HNSW, and it gives you transactions, joins, and — critically — a query planner that already knows how to combine a vector search with SQL predicates, which sidesteps most of §6's filtering pain. Adopt a dedicated system when a measurement forces it, not a blog post.

Failure Modes & Mitigations#

Silent recall decay. Nothing changed, but retrieval quality has been drifting down for months as HNSW accumulates tombstones and rewiring scars from churn (§2.6), or as IVF centroids drift from the data. No error is ever logged. → Mitigation: a recall harness as a monitored SLI (an SLI — Service Level Indicator — is any measured signal you treat as a first-class health metric with a dashboard, a target, and an alert — latency and error rate are the classic ones; the point here is to promote recall into that same category) — 1,000 fixed queries, brute-force ground truth, recall@10 tracked on a dashboard with an alert. Schedule merges and periodic full rebuilds. This is the single most important operational practice in this file, and almost nobody does it.

The half-migrated index. Someone re-embeds "incrementally" with a new model. Now v1 and v2 vectors share a space; distances between them are noise. Results get subtly worse; nothing errors; the cause is invisible for weeks. → Mitigation: models are pinned per index; new model = new index + alias flip. Store the model ID in the index metadata and refuse queries whose query-embedding model doesn't match. Make the corruption impossible rather than detectable.

Post-filter returning empty. Ships fine in dev (where the test tenant has most of the data), then returns zero results in production for every small tenant. → Mitigation: cardinality-aware strategy selection (§6.5); partition by tenant; test with a realistic tenant-size distribution, including the smallest.

OOM from an unquantized index. 100M × 1536 dims × 4 B = 614 GB. The node OOMs mid-build after six hours. → Mitigation: do the arithmetic before you build — N × d × 4 × 1.5 for HNSW is a napkin calculation, and doing it out loud in an interview is worth real points. int8 from the start.

The embedding API as a hidden SPOF. Your hosted embedding provider has an incident. Both your ingest and your query path are down, because a query cannot be embedded — and your vector database, which is perfectly healthy, is now useless. → Mitigation: cache query embeddings aggressively (head queries repeat); have a self-hosted fallback model even if it's slightly worse; degrade to BM25-only when embedding fails — a hybrid architecture (§8.2) means you have a working search engine to fall back to. This is a strong systems answer, and it only exists because you built hybrid.

Chunk-boundary blindness. The answer spans two chunks; neither retrieves; the LLM confabulates. → Mitigation: overlap, semantic/structural splitting, small-to-big retrieval, contextual prefixes (§2.7). And measure retrieval hit-rate on an eval set so you can see the failure.

GC / cold-page tail latency in scatter-gather. p99 = the slowest of N shards (§7.1). One node's page cache goes cold after a deploy and p99 goes to 900 ms. → Mitigation: fewer, bigger shards; replicas with adaptive selection; per-shard timeouts; index warming on startup — and first check whether the tail is actually the embedding API or the LLM (§3.2), because it usually is.

Over-engineering. A team runs a 3-node Milvus cluster for 80,000 vectors. It costs more than the product earns, and brute force would be 2 ms. → Mitigation: §4.1's decision rule. The most valuable engineering judgment in this entire file is knowing when not to build any of it.

13Whiteboard Cheat Sheet#

╔══════════════════════════════════════════════════════════════════════════════╗
║  VECTOR DATABASES & AI INFRA — BOARD DUMP                                    ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ WHY: BM25 = exact terms only, blind to meaning (File 13). Embedding = model  ║
║      maps text→R^768 s.t. SIMILAR = CLOSE. Retrieval becomes GEOMETRY.       ║
║ WALL: curse of dimensionality — in 768D all distances concentrate ⇒ nothing  ║
║       to prune ⇒ k-d trees DIE >10–20 dims ⇒ exact kNN has NO sublinear alg  ║
║       ⇒ EVERY vector index is APPROXIMATE. That's the whole field.           ║
║ MATH: 10M × 768 × 4B = 30 GB per query scan ≈ 600 ms ⇒ RAM IS THE BUDGET     ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ METRICS: cosine=angle (ignores magnitude=noise) | dot=angle+magnitude        ║
║          L2=ruler. NORMALIZE ⇒ all three rank IDENTICALLY. Use the model's!  ║
║ RECALL@k = |returned ∩ true| / k.  ANN failures are SILENT ⇒ MEASURE IT.     ║
║   ★ your MODEL is wrong more often than your INDEX ⇒ don't buy recall >98%   ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ INDEXES                     mem/vec    recall   notes                        ║
║   FLAT (brute force)        3 KB       1.00     <100k. GPU→10M in 10ms       ║
║   IVF (k-means, nprobe)     +4 B       .90-.95  cheap mem, boundary misses   ║
║   IVF-PQ                    ~64 B      .80-.92  BILLION-scale on a budget    ║
║   HNSW (layers+beam ef)     +130 B     .98-.99  ★DEFAULT★ RAM-only, del=bad  ║
║   LSH (random hyperplanes)  big        .70-.85  data-OBLIVIOUS ⇒ lost. dedup ║
║   DiskANN/Vamana(α-prune)   32B RAM    .94-.97  1B vectors, 1 machine, SSD   ║
║   ScaNN (anisotropic PQ)    ~150 B     .95-.98  weights PARALLEL error more  ║
║ HNSW: top layer=express hops → drop layers → beam(ef) at L0. O(log N) hops.  ║
║       diversity heuristic keeps LONG links ⇒ graph stays navigable           ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ QUANTIZATION (= how you pay the RAM bill)                                    ║
║   int8 scalar   4×   .98-.99  ★DO THIS FIRST★ and it's FASTER (SIMD)         ║
║   PQ (96 subs)  32×  .80-.92  → LUT[96][256], dist = 96 lookups + adds!      ║
║   binary(sign)  32×  .70-.85  XOR+POPCNT ~40× faster; needs 1024+ dims       ║
║   ★ RESCORE: retrieve 10–40× oversampled on compressed → re-rank top few     ║
║     hundred with FULL precision ⇒ recall .80 → .97. THIS is what makes       ║
║     quantization viable. Never quantize below int8 without it.               ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ FILTERING (the hard part — graph knows geometry, NOT your filter)            ║
║   post-filter   → search then drop   → 0.1% filter ⇒ ZERO RESULTS  (>50% ok) ║
║   pre-filter    → IDs then BRUTE     → recall 1.0, fast when TIGHT (<1%)     ║
║   filtered walk → check during hops  → traverse THROUGH fails, collect passes║
║                                        (else graph fragments)     (1–50%)    ║
║   PARTITION     → namespace/tenant   → filter becomes ROUTING. ★BEST if one  ║
║                                        filter dominates (all B2B SaaS)       ║
║   ⇒ ESTIMATE CARDINALITY AT QUERY TIME, PICK STRATEGY                        ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ ARCHITECTURE                                                                 ║
║   shard by hash(id) — ★NEVER by similarity★ (border=network hop, hotspots    ║
║      you can't rebalance, drift) ⇒ scatter-gather ⇒ p99 = slowest shard      ║
║   buffer(brute-forced!) → seal → immutable SEGMENT → merge. deletes=tombstone║
║   TIER: RAM=compressed(navigate) | SSD=full(verify) | S3=source(rebuild)     ║
║   consensus for METADATA only, never for vectors (same as File 13)           ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ RAG:  parse→CHUNK(~500tok,15% overlap,semantic)→enrich→EMBED→upsert          ║
║       q → rewrite → [ANN top50 ‖ BM25 top50] → RRF Σ1/(60+rank) →            ║
║           CROSS-ENCODER rerank → top 5 → prompt → LLM (stream + CITE)        ║
║   bi-encoder = separate ⇒ PRECOMPUTABLE ⇒ scales | cross-encoder = together  ║
║      ⇒ accurate, can't precompute ⇒ 2 STAGES: cheap narrow → costly order    ║
║      (same shape: File13 query-then-fetch, LTR, two-tower, PQ+rescore)       ║
║   LATENCY: embed 5–200ms ‖ ANN 2–20ms ‖ rerank 50–200ms ‖ LLM 500–5000ms     ║
║      ⇒ ANN IS NOT YOUR BOTTLENECK. optimize recall+cost, stream tokens.      ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ DANGER                                                                       ║
║   ★ v1 and v2 model vectors are MUTUALLY MEANINGLESS ⇒ upgrade = FULL        ║
║     re-embed + rebuild ⇒ KEEP SOURCE DURABLE, pipeline REPLAYABLE, alias flip║
║   ★ approximate = SILENT error ⇒ recall harness vs brute force AS AN SLI     ║
║   ★ embeddings are blind to SKUs/error codes/names ⇒ HYBRID IS MANDATORY     ║
║   ★ RAG retrieval miss ⇒ confident HALLUCINATION, not an error ⇒ citations   ║
║   ★ <100k vectors? BRUTE FORCE. <10M? pgvector. Don't add a DB you don't need║
║   ★ napkin BEFORE building: N × d × 4 B × 1.5 = your RAM bill                ║
╚══════════════════════════════════════════════════════════════════════════════╝

14One-Sentence Summary for an Interviewer#

"A vector database exists because lexical search is structurally blind to meaning (File 13) while an embedding model turns meaning into geometry — so retrieval becomes nearest-neighbor search — except the curse of dimensionality kills every pruning index above ~20 dimensions and exact kNN has no sub-linear algorithm, which means every vector index on earth is an approximation and the whole discipline is choosing what to approximate: HNSW (a skip-list generalized to metric space — express links up top, beam search at the bottom, O(log N) hops, best recall-per-ms, but ~130 bytes/vector of graph, RAM-only, and deletes silently rot it), IVF-PQ (k-means buckets plus 96-byte codes scored by lookup table — 32× smaller, the only way billion-scale is affordable), or DiskANN (PQ vectors in RAM to navigate, full vectors on SSD to verify — one machine, a billion vectors, because the memory hierarchy IS the architecture); you always int8-quantize first (4× for under 1% recall, and it's faster), then oversample 10–40× on compressed vectors and rescore with full precision to buy the recall back; filtering is the genuinely hard part because the graph knows geometry and nothing about your tenant_id, so you estimate cardinality per query — under 1% pre-filter and brute force, over 50% post-filter, in between traverse-and-check, and if one filter dominates just partition and delete the problem; you shard by hash, never by similarity, and eat the scatter-gather tail; and the senior move is to say that the index is a derived, disposable artifact — because vectors from two model versions are mutually meaningless, so every upgrade is a full re-embed behind an alias flip, which is only survivable if you kept the source durable and the pipeline replayable — that hybrid BM25+vector fused with RRF is mandatory since embeddings discard the exact SKUs and error codes users actually type, that a cross-encoder reranker over the top 100 is the highest-ROI thing you can add, that ANN latency is ~1% of a RAG request while the LLM is 90%, that an ANN failure surfaces as a confident hallucination rather than an error so recall against brute-force ground truth must be a monitored SLI, and that under 100k vectors the correct answer is brute force in numpy and no vector database at all."

End of File 14. Next → File 15: Idempotency & Payment Gateways (idempotency keys, the payment lifecycle, outbox, sagas, reconciliation) — how to move money exactly once over a network that can only promise "at least once." Prompt me to continue.