« Phase 05 README · Warmup · Hitchhiker's · Principal Deep Dive · Core Contributor · Staff Notes

Phase 05 — Deep Dive: Retrieval Foundations

This is the mechanism document. It assumes you have read the warmup and want the data structures, the score arithmetic, the invariants, and a query traced end to end with real numbers. Everything here maps to a named function in lab-01-hybrid-retriever/solution.py.

The two indexes are two different data structures

A hybrid retriever is not one index with a knob; it is two indexes over the same chunks, built from two incompatible representations, queried in parallel, and reconciled by rank.

Dense side — a matrix of unit vectors. embed(text, dim=64) maps a chunk to a point on the surface of the unit hypersphere: hash each token with md5 into one of dim buckets, count occurrences (a bag-of-words vector), then divide by the L2 norm. Normalization is not cosmetic — it is what collapses cosine similarity into a plain dot product, because for unit vectors cos(q,d) = q·d / (1·1) = q·d. DenseIndex stores these as a flat list of (id, vector) and search scores the query against every one: O(N·dim) per query, sorted by (-score, id). That is brute force by design — the exact answer the approximate indexes (§below) chase.

Lexical side — an inverted structure. BM25.__init__ precomputes three things over the tokenized corpus: df[t] (how many docs contain term t), tf[i][t] (term counts per doc), and doc_len[i] plus avgdl. This is the seed of a real inverted index — a term → postings map. The lab keeps forward tf dicts for clarity, but the shape is identical: to score a query you only touch the terms in the query, never the whole vocabulary.

The invariant that makes this work: a chunk id is a stable join key across both indexes. chunk_text emits Chunk(f"{doc_id}#{idx}", ...) and the same id is what DenseIndex.add and BM25 store, what rrf fuses on, and what recall_at_k checks membership against. Break id stability (for example by using a per-process hash() in the embedder — the lab uses hashlib precisely to avoid this) and the two rankings can no longer be fused.

BM25 scoring, factor by factor, with arithmetic

$$\operatorname{score}(q,d)=\sum_{t\in q}\operatorname{IDF}(t)\cdot\frac{tf(t,d),(k_1+1)}{tf(t,d)+k_1!\left(1-b+b,\frac{|d|}{\text{avgdl}}\right)}$$

with the smoothed Lucene IDF IDF(t) = ln(1 + (N − df + 0.5)/(df + 0.5)), k1 = 1.5, b = 0.75.

Take the demo corpus: N = 12 docs, avgdl ≈ 22 tokens. The rare identifier tx4096 has df = 1:

IDF(tx4096) = ln(1 + (12 − 1 + 0.5)/(1 + 0.5)) = ln(1 + 7.667) = ln(8.667) ≈ 2.159.

The common token network appears in roughly 10 of 12 docs, df = 10:

IDF(network) = ln(1 + (12 − 10 + 0.5)/(10 + 0.5)) = ln(1 + 0.238) = ln(1.238) ≈ 0.213.

That is a 10× weight gap, and it is the entire reason BM25 catches rare tokens: the score of a document is dominated by the query's most discriminating terms. Now the length/saturation factor for tx4096 in dB (tf = 1, |d| ≈ avgdl so the length ratio is ≈ 1):

norm = 1.5·(1 − 0.75 + 0.75·1) = 1.5, then tf·(k1+1)/(tf+norm) = 1·2.5/(1+1.5) = 1.0.

So tx4096 contributes IDF·1.0 ≈ 2.159 to dB's BM25 score — one rare term single-handedly carries the document to rank 1. The TF saturation is why 50 repeats of a word do not run away: as tf → ∞, the factor tf(k1+1)/(tf+norm) → k1+1 = 2.5, a hard ceiling. The length term penalizes long docs (|d| > avgdl shrinks the factor) so a rambling document cannot farm matches.

Why the same rare token is invisible to the dense index

embed puts tx4096 in exactly one of 64 buckets. dB has ~22 tokens; after L2 normalization its per-token weight is ≈ 1/√22 ≈ 0.213. The query "error code tx4096 connection troubleshooting" has 5 tokens; tx4096's weight is 1/√5 ≈ 0.447. Their contribution to the cosine is 0.213 · 0.447 ≈ 0.095 — a whisper. Meanwhile the distractor xB repeats the query's common words (error, code, connection) several times each, so those buckets carry more mass and xB's cosine with the query exceeds dB's. Dense retrieval loses the rare token in the averaging. This is not a bug in the hashing embedder; a trained bi-encoder has the same failure shape — a rare identifier is one thin direction in a smooth 384- or 1024-dim space, and the model was never trained to preserve exact-string signal.

The symmetric failure (Query A) is the mirror: the relevant doc dA shares only common words with "network drive access kerberos", whose IDF BM25 has zeroed to ≈ 0, so BM25 ranks the kerberos-owning distractor first and misses dA, while the dense embedder — which weights all shared tokens regardless of rarity — ranks dA #1. Two queries, two opposite misses. That symmetry is the mechanism-level argument for running both.

ANN indexes: what the brute-force DenseIndex becomes at scale

O(N·dim) per query is fine to ~10⁵ vectors and unacceptable at 10⁷+. Three data structures replace the flat scan, all trading a few points of recall for orders of magnitude of speed:

  • HNSW — a multi-layer proximity graph. Each node links to M near neighbors; upper layers are sparse express lanes. Search is greedy best-first descent from an entry point, keeping a candidate frontier of size efSearch; you reach the query's neighborhood in ≈ O(log N) hops instead of N comparisons. Build cost is O(N·log N·M·efConstruction); memory is the vectors plus M neighbor ids per node.
  • IVF — k-means the corpus into (say) 4096 centroid cells; at query time probe only the nprobe nearest cells. Recall loss comes from a true neighbor sitting just across an unprobed boundary; raising nprobe buys recall back linearly in scan cost.
  • PQ — split each vector into sub-vectors, replace each with the id of the nearest codebook entry. A 1024-dim float vector (4 KB) shrinks to tens of bytes; distances become table lookups. Usually layered as IVF-PQ. Trades precision for a RAM-resident index.

The point of building the exact DenseIndex is that these all approximate its semantics. When someone says "we moved flat → HNSW, recall dropped 1%, p99 dropped 40×," you know precisely what was traded and which knob (efSearch, nprobe) moves it.

RRF fusion: why rank, and the constant's job

Cosine lives in [0,1]; BM25 lives in [0,∞) and drifts with corpus statistics. Adding 0.7 to 2.159 is meaningless, and min-max normalizing BM25 is fragile and needs per-corpus tuning. rrf sidesteps the scales entirely: RRF(d) = Σ_r 1/(k_const + rank_r(d)), k_const = 60. It never reads a raw score. The constant damps the top so a document ranked moderately in both lists beats one ranked #1 in a single list — the consensus behavior you want.

A hybrid query traced end to end (Query B)

retrieve("error code tx4096 connection troubleshooting", k=1, topn=5):

  1. Dense top-5 (misses): [xB#0, d5#0, dB#0, d8#0, d3#0] — xB wins on common-word mass; dB limps in at rank 3.
  2. BM25 top-5 (catches): [dB#0, xB#0, d5#0, d9#0, d6#0] — tx4096's IDF ≈ 2.159 puts dB at rank 1.
  3. RRF fuse, k = 60:
    • dB: dense rank 3, bm25 rank 1 → 1/63 + 1/61 = 0.015873 + 0.016393 = 0.032266
    • xB: dense rank 1, bm25 rank 2 → 1/61 + 1/62 = 0.016393 + 0.016129 = 0.032522 RRF alone still ranks xB a hair above dB (0.032522 vs 0.032266) — fusion narrowed the gap but did not close it.
  4. Rerank by token_overlap_scorer. Query token set = {error, code, tx4096, connection, troubleshooting}. dB contains error, code, tx4096, connection → overlap 4. xB contains error, code, connection (no tx4096) → overlap 3. Stable sort by (-score, fusion_order) lifts dB above xB.
  5. Top-k=1 → dB#0. Hit.

The reranker is the load-bearing final step here: RRF got dB into the top-2, and the precision-oriented reranker put it at #1. Run the same trace for Query A and dense carries dA. Each retriever alone scores recall@1 = 0.5; the fused-and-reranked pipeline scores 1.0. That inequality — hybrid ≥ max(dense, bm25), strict on this set — is a passing test, not a slogan.

Why the naive approaches fail at the mechanism level

  • Pure cosine over one embedding dilutes every rare, high-signal token into one dimension of an averaged vector; exact identifiers, SKUs, and error codes drown. No amount of dimensionality fixes an averaging operator.
  • Lexical-only discards, via IDF, exactly the common-word overlap that carries paraphrase and topical relevance; it cannot see that two texts mean the same thing in different words.
  • Score addition compares [0,1] against [0,∞); whichever scale is larger silently wins, so "hybrid by adding scores" is usually BM25-only with extra steps.

Each failure is structural, not a tuning miss — which is why the fix is architectural: two indexes, rank fusion, a reranked shortlist.