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

Phase 05 — Core Contributor Notes: Retrieval Foundations

This document reads the lab against the source of the real systems it miniaturizes. The point is to know where the stdlib toy is honest, where it simplifies, and what a committer to Lucene, FAISS, hnswlib, or pgvector actually deals with under the hood. Descriptions are of the pattern in each codebase; no URLs, no invented API surface.

Lucene's BM25Similarity vs the lab's BM25

The lab's idf and score are Lucene's scoring function with the tutorial rounded off. The formula is the same one — IDF · tf(k1+1)/(tf + k1(1 − b + b·|d|/avgdl)), with the smoothed ln(1 + (N − df + 0.5)/(df + 0.5)) IDF and defaults k1=1.2 in Lucene (the lab uses 1.5, Elasticsearch's historical default) and b=0.75. What a Lucene contributor knows that the lab elides:

• norm is quantized to a single byte. Lucene does not store |d| exactly; at index time it encodes the length normalization factor into one byte (SmallFloat), so BM25's length term is lossy and two documents of slightly different length can share a norm. This is a deliberate space tradeoff — one byte per field per doc instead of an int — and it is why re-scoring in Lucene can differ imperceptibly from a textbook computation. The lab keeps doc_len exact.
• IDF is computed from the term dictionary, not a Python dict. df comes from the postings list's document frequency, held in the terms index (an FST — finite state transducer — over the sorted term bytes). The lab's self.df dict is the semantic equivalent at toy scale; Lucene's version is a compressed on-disk structure you can memory-map.
• Postings are the real data structure. The lab scores by iterating documents and looking up tf; Lucene iterates the query terms' postings lists and advances document iterators (DISI), scoring only documents that actually contain a query term. That inversion is the whole performance story of lexical search and the reason BM25 is cheap on huge corpora — you never touch a document that shares no term with the query.
• Similarity is pluggable. BM25Similarity is one implementation of the Similarity SPI; classic TF-IDF, DFR, and LM-Dirichlet are siblings. Elasticsearch and OpenSearch expose this as the index-level similarity setting. The lab hard-codes BM25 because it won thirty years of that bake-off.

FAISS: the index zoo the lab's DenseIndex collapses into one

DenseIndex.search — score every vector, sort — is IndexFlatIP (inner product on normalized vectors = cosine). FAISS's value is everything you reach for when flat stops scaling, and a contributor thinks in the index-factory string:

• IndexHNSWFlat builds the Malkov–Yashunin proximity graph. The construction knobs are M (neighbors per node; higher = better recall, more memory, slower build) and efConstruction (candidate breadth during insertion; higher = better graph, slower build). At query time efSearch trades recall for latency. These are not the lab's concern because brute force has no graph to tune — but they are the interview vocabulary.
• IndexIVFFlat is the coarse quantizer + inverted lists design: k-means into nlist centroids, probe nprobe at query. nprobe=1 is fast and lossy; nprobe=nlist degenerates back to flat. Training is required (IVF must see representative vectors to place centroids), which is a real operational wrinkle the lab has none of.
• IndexIVFPQ adds product quantization: sub-vector codebooks compress each vector to m bytes. The famous gotcha a committer knows — PQ distances are asymmetric (query kept full precision, database compressed) and the recall/​memory tradeoff is set by m and nbits. This is how billion-vector indexes fit in RAM.
• Metric matters. FAISS distinguishes METRIC_INNER_PRODUCT from METRIC_L2; you must normalize vectors for inner product to equal cosine — exactly what the lab's embed does with its L2 divide. Mismatch the metric to the embedder's training objective and recall silently drops. This is the single most common FAISS-user bug.

The design lesson from FAISS's own evolution: it started as a research library for billion-scale similarity and grew the composable index_factory grammar ("IVF4096,PQ64", "HNSW32,Flat") precisely because no single index wins across the memory/recall/latency triangle — you compose one for your point.

hnswlib: the standalone graph, and the params pgvector inherits

hnswlib is the reference HNSW implementation many systems embed. A contributor's mental model of its sharp edges:

• ef_construction and M are set at build and mostly frozen. M in particular changes the graph's memory layout, so you cannot cheaply raise it after the fact — you rebuild.
• ef (search) is per-query and must be ≥ k. Set it below k and you literally cannot return k results. Raising it is the recall knob you tune against an SLO at serve time.
• Deletes are tombstones, not removals. hnswlib marks deleted elements; the graph node stays, so a churny corpus accumulates dead nodes and degrades until you rebuild. This is why "just upsert" is not free at scale and why compaction/rebuild jobs exist.
• Single-writer. Concurrent inserts need external synchronization. Real vector DBs wrap hnswlib (or a reimplementation) with segment-based writes to get around this.

pgvector: ivfflat vs hnsw, and why the default flipped

pgvector is the enterprise default because it puts vectors next to relational rows, transactions, and row-level security — the access-control-at-retrieval story the lab defers to Phase 13 is a plain WHERE clause here. What a pgvector contributor knows:

• Two index types. ivfflat (IVF, needs lists set and a representative sample to build — build after loading data or the centroids are garbage) and hnsw (added later, no training, better recall/latency, higher build cost and memory). The community guidance moved toward HNSW as the safer default precisely because IVF's "build after you have data, pick lists ≈ rows/1000" footgun bit too many people.
• Query-time knobs are session GUCs. hnsw.ef_search and ivfflat.probes are set per session — the same recall/latency lever as FAISS/hnswlib, exposed as SQL settings.
• The operator class picks the metric. vector_cosine_ops, vector_ip_ops, vector_l2_ops — you must match the one your embedder was trained for, and (again) normalize for cosine. Same trap as FAISS, different syntax.
• BM25 is bolted on. Core Postgres full-text (ts_rank, tsvector) is not BM25; getting real BM25 + vector hybrid in Postgres means an extension or fusing pgvector results with an external lexical engine's — the RRF step the lab does in twelve lines is exactly the glue those stacks write.

sentence-transformers and the reranker: bi-encoder vs cross-encoder in the wild

The lab's hashing embed stands in for a bi-encoder (all-MiniLM-L6-v2 at 384 dims, bge-* at up to 1024, Cohere Embed, OpenAI text-embedding-3). The interface the lab preserves is the one that matters: text → vector, compare by cosine, precomputable and indexable. What real bi-encoders add that the lab cannot: learned paraphrase (car ≈ automobile), and often a required prompt prefix (bge wants a "query: " / "passage: " prefix; forget it and recall drops — a classic ops mistake). Matryoshka-trained models let you truncate the vector to trade storage for accuracy.

token_overlap_scorer + rerank is the cross-encoder slot — Cohere Rerank, bge-reranker, or a BERT cross-encoder. The real thing feeds the (query, passage) pair together through the model so attention crosses both, producing a far better relevance score at O(candidates) model calls. The lab's stable sort keeping fusion order on ties is the honest detail: a real reranker also needs a deterministic tie-break, and "keep upstream order" is the sane default.

What the miniature deliberately simplifies

• Exact instead of approximate. No graph, no quantization, no efSearch — the lab is the oracle those approximate, on purpose, so the semantics are visible before the speed tricks.
• Forward tf dicts, not inverted postings. Correct scores, wrong data structure for scale; Lucene's postings + FST is the real shape.
• Global corpus stats trivially available. avgdl and df are one pass over twelve docs; sharded systems fight to keep IDF globally consistent.
• No metadata, filtering, deletes, or tenancy. The three production concerns every real engine spends most of its code on. The lab is the algorithm; the systems above are the algorithm plus everything that makes it survive a corpus that changes and a caller who is not trusted.