Warmup Guide — Semantic Retrieval & Search

Zero-to-expert primer for Phase 04: retrieval as an engineered system — BM25's mechanics derived term by term, dense retrieval operated honestly, hybrid fusion, index structures, and the evaluation harness that makes any of it improvable.

Table of Contents

• Chapter 1: Retrieval's Place in Every ML System
• Chapter 2: The Inverted Index
• Chapter 3: BM25, Derived Term by Term
• Chapter 4: Analyzers — Where Lexical Search Is Won
• Chapter 5: Dense Retrieval, Operated
• Chapter 6: Hybrid Fusion
• Chapter 7: Index Structures and Their Trades
• Chapter 8: Evaluating Retrieval
• Lab Walkthrough Guidance
• Success Criteria
• Interview Q&A
• References

Chapter 1: Retrieval's Place in Every ML System

Retrieval answers: given a query, find the small set of candidates worth scoring carefully. It is the first stage of a universal two-stage architecture:

millions of items → [RETRIEVAL: cheap, recall-oriented] → hundreds
                  → [RANKING: expensive, precision-oriented] → ten

Search engines, recommenders (Phase 06's candidate generation), ads systems, and RAG (Phase 10) are all instances. Two consequences define the engineering:

1. Recall@k of the first stage upper-bounds the whole system — the ranker cannot rank what retrieval didn't return. Measuring first-stage recall separately (Ch. 8) is therefore non-negotiable; end-to-end metrics can't localize the loss.
2. Retrieval must be cheap per item (it touches everything) — which is why its models are constrained (bag-of-words scoring; bi-encoders with offline-computable document vectors) and its data structures matter (Ch. 2, 7).

Chapter 2: The Inverted Index

From zero: scoring every document per query is O(N). The inverted index makes lexical retrieval sublinear: a map from each term to its postings list — the documents containing it (plus term frequencies/positions):

"watermark" → [(doc3, tf=2), (doc17, tf=1), ...]

Query time: union/intersect the postings of the query's terms; only documents sharing at least one term are touched — for selective terms, thousands instead of millions. Everything Lucene/Elasticsearch does is elaboration: compressed postings, skip lists for fast intersection, segment files with merges (an LSM structure — append new segments, merge in background — the same write-pattern logic as Kafka's logs and LSM databases). You build the dict-of-lists version in the lab; the production versions differ in constants, not concept.

Chapter 3: BM25, Derived Term by Term

The scoring function (per query term t, summed):

$$\text{score}(q, d) = \sum_{t \in q} \underbrace{\ln!\left(\frac{N - df_t + 0.5}{df_t + 0.5} + 1\right)}{\text{IDF}} \cdot \underbrace{\frac{tf{t,d} ,(k_1 + 1)}{tf_{t,d} + k_1\left(1 - b + b,\frac{|d|}{\text{avgdl}}\right)}}_{\text{saturating TF, length-normalized}}$$

Each piece, justified from a failure of the simpler thing:

• Why IDF: raw term counts let "the" dominate. Rarity ≈ informativeness; the log damps (a term in 1 doc vs 10 is a big deal; 100K vs 1M is not); the +0.5s smooth zero/all-docs cases. (Probabilistic-relevance derivation exists — Robertson/Spärck Jones; for engineering, "log-damped rarity weight" is the load-bearing intuition.)
• Why TF saturates (the $k_1$ term): the 2nd occurrence of "watermark" is strong evidence; the 20th adds little — relevance isn't linear in count. The hyperbola $tf(k_1{+}1)/(tf{+}k_1)$ rises to an asymptote; $k_1 \approx 1.2$ sets how fast. ($k_1 = 0$ → pure presence/absence; large $k_1$ → near-linear TF.)
• Why length normalization (the $b$ term): long documents match more terms by bulk, not by aboutness. Dividing TF's denominator by the doc's relative length ($|d|/\text{avgdl}$) penalizes proportionally; $b \in [0,1]$ interpolates between no normalization ($b{=}0$) and full ($b{=}1$); 0.75 is the folklore default. Corpora of uniform length (tweets) want low b; mixed corpora want it high.

The lab's property tests pin each behavior independently — rarity ordering, saturation curvature, length penalty — which is how you know your implementation rather than believe it.

Chapter 4: Analyzers — Where Lexical Search Is Won

The unglamorous truth: production lexical search quality is mostly analysis — the pipeline that turns text into terms:

• Tokenization (Phase 01 of the LLM track at the word level: unicode, punctuation, CJK segmentation), lowercasing, stemming/lemmatization (matching "watermarks" to "watermark" — recall vs precision knob), stopwords (mostly obsolete with BM25's IDF — removing them saves index size, costs phrase queries), synonyms (domain dictionaries: "k8s" = "kubernetes" — the highest-ROI relevance work in enterprise search), and exact fields for IDs/codes (never stem a SKU).
• The cardinal rule (same as the feature store's parity rule): index-time and query-time analysis must match — a stemmed index queried unstemmed silently returns nothing. Same disease as training-serving skew; same cure (one definition, two call sites, a parity test).

Chapter 5: Dense Retrieval, Operated

The LLM track's Phase 02 and Phase 07 cover how embedding models are trained; here is the operator's checklist:

• Normalization: L2-normalize at index AND query time; dot product then equals cosine and rankings coincide — the lab asserts this property.
• The asymmetry trap: retrieval embedders use different prefixes/instructions for queries vs passages; omitting them at one side silently costs recall (the #1 production retrieval bug — worth repeating across tracks).
• What dense buys: paraphrase robustness ("how do I reset my password" matches "credential recovery"); what it loses: exact identifiers, rare entities, negations — precisely lexical's strengths (the complementarity that motivates Ch. 6).
• Version discipline: an index built with embedder v1 queried with v2 is silent garbage — embedder version is part of the index's schema; reindex-on-upgrade is a planned migration (Phase 11 of the PMC track's skew matrix, once again).

Chapter 6: Hybrid Fusion

Run lexical and dense in parallel; merge. The fusion question: BM25 scores (unbounded, corpus-dependent) and cosines ([−1,1]) are incommensurable — score arithmetic is meaningless without calibration. Reciprocal Rank Fusion sidesteps scores entirely:

$$\text{RRF}(d) = \sum_{r \in \text{retrievers}} \frac{1}{k + \text{rank}_r(d)} \qquad (k = 60 \text{ by convention})$$

Rank-based → scale-free, robust, zero tuning; $k$ damps the top-rank dominance. Items found by both retrievers get two contributions — agreement is evidence. RRF is embarrassingly simple and embarrassingly hard to beat; weighted score fusion with per-retriever normalization can edge it with tuning data, and learning-to-rank over both scores (Phase 05) is the principled ceiling. Engineering note: over-retrieve from each parent (k=50–100 each) before fusing — fusion can only promote what was retrieved.

Chapter 7: Index Structures and Their Trades

The operator's map (build intuition here; the LLM track details HNSW/IVF mechanics):

Two operational facts that bite: metadata filtering interacts badly with ANN (filter-during-graph-traversal degrades recall unpredictably — engines differ; ask the question of any vector DB), and the brute-force comparison on a sample is the only honest measure of your ANN recall — run it routinely (the lab's pattern, and the Extension A benchmark's whole point).

Chapter 8: Evaluating Retrieval

The harness (the lab's second half) — small, labeled, decisive:

• qrels: (query → set of relevant doc ids). Even 30–50 labeled queries transform development from vibes to measurement (the recurring curriculum claim; here it's literal — Extension B has you build one).
• Metrics, chosen by stage: recall@k for first-stage retrieval (did the answer make it into the candidate set? — the bound from Ch. 1); MRR (mean reciprocal rank of the first relevant — right when one answer suffices); precision@k (density of good stuff — right for browse). NDCG (graded relevance, position-discounted) belongs to the ranking stage — Phase 05 implements it from scratch.
• Methodology (Phase 02-of-CV's ethics, applied): fixed query set, paired comparisons between systems, never tune on the test queries, slice by query class (the lab's lexical-gap vs paraphrase-gap cases are exactly such slices — aggregate recall hides which retriever fails where; the slice tells you).

Lab Walkthrough Guidance

Lab 01 — Hybrid Retrieval Engine, suggested order:

1. Tokenizer (lowercase, alphanumeric split — keep it simple and identical for index and query: Ch. 4's rule) and the inverted index.
2. BM25 scoring; then the three property tests (rarity, saturation, length) — write them to fail first if you want the full lesson.
3. Dense index: normalized matrix + argpartition top-k; the cosine==dot assertion.
4. RRF; then the two constructed query classes: an ID-lookup query (dense fails, BM25 wins) and a paraphrase query with hand-set vectors (BM25 fails, dense wins) — hybrid must survive both. This pair of tests is the phase's thesis in executable form.
5. The eval harness: recall@k and MRR against qrels, verified on a hand-computable miniature.

Success Criteria

You are ready for Phase 05 when you can, from memory:

1. Draw the two-stage architecture and state what first-stage recall bounds.
2. Write BM25 and explain k1 and b from the failures they fix; predict the effect of b=0 on a mixed-length corpus.
3. State the analyzer parity rule and its skew analogy.
4. List dense retrieval's three operator traps (normalization, prefixes, version).
5. Justify RRF's rank-based design and the over-retrieve-then-fuse rule.
6. Pick metrics per stage (recall@k vs MRR vs NDCG) with reasons.

Interview Q&A

Q: Search works for product IDs but fails for "cheap red running shoes". Or the reverse. Diagnose each. IDs work / natural language fails: pure lexical system — no semantic matching; add a dense retriever and fuse (RRF), and check the analyzer isn't stemming IDs into collisions. Natural language works / IDs fail: pure dense system — embeddings blur exact identifiers; add lexical with exact-match fields (never stemmed), fuse. Both diagnoses end the same way: hybrid is the default for heterogeneous query traffic, and query-class slicing in the eval harness is how you saw it.

Q: Your ANN index reports great latency but product metrics sagged after the migration from brute force. What happened? Recall loss: ANN is approximate, and recall@k vs brute force on a labeled sample is the only honest measure — measure it (likely culprits: efSearch/nprobe tuned for the benchmark not the workload; metadata filtering degrading graph traversal; deletes accumulating as tombstones). The senior lesson: latency is visible by default, recall is invisible by default — instrument the invisible one before migrating.

Q: Why is RRF so hard to beat, and what eventually beats it? It's scale-free (no score calibration across incommensurable retrievers), robust to a bad parent (a garbage retriever adds noise but rank-damping limits damage), and parameter-light (k=60 works broadly). What beats it: learned fusion — a ranker (Phase 05) trained on (query, doc, both-scores, features) with real labels, which can learn query-dependent weighting (lexical matters more for ID-shaped queries). That is, the thing that beats heuristic fusion is the next stage of the architecture doing its job — with labels and an eval harness, which RRF never needed and LTR does.

References

• Robertson & Zaragoza, The Probabilistic Relevance Framework: BM25 and Beyond (2009) — the derivation behind Ch. 3
• Manning, Raghavan, Schütze, Introduction to Information Retrieval — ch. 1–2 (indexes), 6 (scoring), 8 (evaluation); free online
• Cormack, Clarke, Buettcher, Reciprocal Rank Fusion outperforms… (SIGIR 2009)
• Elasticsearch: analysis docs — Ch. 4 industrialized
• BEIR benchmark — heterogeneous retrieval evaluation, the public version of Ch. 8
• LLM track Phase 07 WARMUP — DPR training, HNSW/IVF mechanics, RAG assembly
• hnswlib and FAISS wiki — Extension A's tools