Core Retrieval Algorithms

Meaningful embedding neighborhoods are useful, but a technical-docs assistant needs a tougher guarantee: given one developer question, can it place the guide that answers the question near the top? An LLM can't quote a procedure that retrieval never places in its context.

Build that evidence-selection stage around one query and four documentation passages. You'll implement lexical ranking with BM25, dense ranking with cosine similarity, rank fusion, retrieval evaluation, and an approximate-search failure test. Afterward, a fluent wrong answer won't look like a mysterious model failure. You'll know how to inspect the evidence gate first.

One Question, Four Possible Sources

Developer question:

How do I rotate an API key?

The documentation assistant may retrieve these passages:

The distinction between d2 and d4 matters. A page may mention API keys and still fail to answer this rotation question. Retrieval evaluation needs judgments tied to a question, not a general document category.

Sparse Retrieval Starts With an Inverted Index

Sparse retrieval treats documents as words and counts. It first builds an inverted index, a map from a term to documents containing that term. Exact API names, error codes, and configuration identifiers can be found efficiently.

Lowercase words, remove punctuation, and discard a short stopword list so the query keeps three discriminating terms: rotate, api, and key.

d2 is judged relevant, but it doesn't appear in the API-key posting lists. That isn't a bug in lexical retrieval. It's the limitation that dense retrieval covers.

BM25 scores lexical evidence

BM25 ranks passages from term counts while preventing two easy distortions: repeating one word forever and rewarding long documents merely for having more chances to contain a word. For each query term, its score contribution is:

$$\mathrm{IDF}(t) \cdot \frac{f(t,d)(k_1+1)} {f(t,d) + k_1(1-b+b|d|/\mathrm{avgdl})}$$

In this equation, $f(t,d)$ is the count of term $t$ in passage $d$; $|d|$ is the passage length; $\mathrm{avgdl}$ is the average passage length; and inverse document frequency (IDF) gives more weight to rarer terms. $k_1$ controls term-frequency saturation and $b$ controls length normalization. This is the BM25 family presented by Robertson and Zaragoza.^{[1]Reference 1The Probabilistic Relevance Framework: BM25 and Beyond.https://doi.org/10.1561/1500000019}

BM25 has implementation variants. This version uses the always-positive IDF term $\log(1 + (N - \mathrm{df} + 0.5) / (\mathrm{df} + 0.5))$, where $N$ is the number of passages and $\mathrm{df}$ is the number containing the term. A query term still contributes a non-negative weight when it appears in most passages.

The first full ranker uses only Python data structures. It's short enough to inspect and precise enough to reproduce each score.

BM25 should put d1 first: it contains exact API-key terms and repeats key. This tiny tokenizer doesn't stem rotation into rotate, which is why lexical matching still needs careful preprocessing and judged queries. It should rank d4 above d2 because d4 contains api and key, although a human judgment says d2 is the better answer. This is a retrieval failure mode worth keeping visible.

Repetition Saturates Instead of Winning Automatically

Copying a query word repeatedly shouldn't make a weak page unbeatable. In BM25, term frequency raises the contribution but with diminishing returns. The next lab isolates that factor by holding IDF and length normalization fixed.

The weight grows toward the limit $k_1 + 1 = 2.2$, but the remaining gap shrinks. BM25 still requires good tokenization and good documents; it just stops keyword stuffing from behaving like relevance.

Dense retrieval recovers paraphrases

Vector-geometry audits tell you whether neighborhoods are meaningful. Dense retrieval applies that geometry to a query: embed the query and each passage independently, then rank passages by similarity. Dense Passage Retrieval demonstrated this bi-encoder pattern for passage ranking, using query and passage representations scored by inner product.^{[2]Reference 2Dense Passage Retrieval for Open-Domain Question Answering.https://arxiv.org/abs/2004.04906}

To see the mechanics, use three interpretable coordinates rather than a real embedding model:

Cosine similarity compares direction:

$$\cos(q,d) = \frac{q \cdot d}{\lVert q \rVert_2 \lVert d \rVert_2}$$

For d2, the numerator is $1.0(0.9) + 0.8(0.9)=1.62$. Dividing by the two lengths gives approximately 0.994, even though d2 says credential instead of the literal phrase API key.

Dense ranking promotes d2, the paraphrase that sparse ranking couldn't see. It also retains d4 as partially similar, so dense retrieval doesn't remove the need for judgments or reranking.

Similarity Must Match the Embedding Contract

Raw dot product and cosine similarity produce the same order only when vector norms are controlled. A larger vector can win dot product despite pointing in a worse direction.

This doesn't mean cosine is always right and dot product is always wrong. It means index construction, offline evaluation, and online queries must agree on the metric the embedding model is intended to use.

Fuse independent retrieval lanes

For this question, sparse and dense rankings contain complementary evidence:

Don't average a BM25 number such as 3.128 with a cosine number such as 0.994. They have unrelated units. Reciprocal rank fusion (RRF) uses rank positions instead:

$$\mathrm{RRF}(d) = \sum_{\ell \in L} \frac{1}{k + r_{\ell}(d)}$$

Here, $L$ is the set of ranked lists and $r_{\ell}(d)$ is document $d$'s position in list $\ell$. If one lane doesn't return $d$, that lane contributes nothing for $d$. Cormack, Clarke, and Buettcher proposed RRF and used k=60 as a fixed constant in their reported experiments.^{[3]Reference 3Reciprocal Rank Fusion Outperforms Condorcet and Individual Rank Learning Methods.https://dl.acm.org/doi/10.1145/1571941.1572114}

The paraphrased answer d2 moves above the quota distractor d4. The loop accumulates scores across the union of returned documents, so a dense-only candidate isn't silently discarded. RRF didn't decide that d2 was relevant; your judgment table did. RRF only gave both retrieval lanes a fair way to contribute candidates. With only four documents and k=60, reciprocal ranks nearly flatten (0.0325 vs 0.0313); a smaller k would accentuate rank gaps. Production systems often still use k=60 on larger candidate lists, matching Cormack et al.'s reported constant.

Reranking Spends Compute on the Shortlist

A dense retriever encodes a query separately from its passages so passage vectors can be stored and searched cheaply. A cross-encoder reranker instead reads a query-passage pair together and predicts relevance for that pair. Nogueira and Cho showed this second-stage BERT reranking pattern on retrieved passages.^{[4]Reference 4Passage Re-ranking with BERT.https://arxiv.org/abs/1901.04085}

Reranking improves ordering only if the correct passage survived candidate retrieval. For a paraphrased request such as q2 replace credential, the next check makes that boundary explicit with assumed reranker scores where d2 is the best answer.

A retrieval cascade has two separate metrics: candidate recall for the first stage and final ordering quality after reranking.

Measure ranking before evaluating answers

To evaluate retrieval, create queries with relevance judgments. Two useful metrics are:

• Hit Rate @ K: fraction of questions with at least one relevant passage in the first $K$ results.
• Mean Reciprocal Rank (MRR): average of $1/r$, where $r$ is the rank of the first relevant passage.

For multi-relevance or graded judgments, normalized Discounted Cumulative Gain (nDCG) is also common; BEIR reports nDCG@10 across diverse information-retrieval datasets.^{[5]Reference 5BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models.https://arxiv.org/abs/2104.08663}

The mini evaluation below compares a sparse-only run with a hybrid run. q2 uses paraphrased wording, so the dense lane must preserve d2 near the top.

Hybrid retrieval doesn't always win on every corpus. A judged hard query reveals weaknesses that an easy query hides.

Approximate Search Is a Recall Decision

Exact dense retrieval compares a query vector against every stored passage. Once a corpus grows large, an approximate nearest neighbor (ANN) index searches fewer candidates or uses compressed vectors to lower latency and memory cost.

Three building blocks appear often:

IVF and PQ are described in Faiss's similarity-search work and PQ's original nearest-neighbor paper; HNSW uses a hierarchical navigable proximity graph for approximate search.^{[6]Reference 6Billion-scale similarity search with GPUs.https://arxiv.org/abs/1702.08734[7]Reference 7Product Quantization for Nearest Neighbor Search.https://dblp.org/rec/journals/pami/JegouDS11[8]Reference 8Efficient and Robust Approximate Nearest Neighbor Using Hierarchical Navigable Small World Graphs.https://arxiv.org/abs/1603.09320}

Watch an IVF Probe Miss the Nearest Passage

An IVF index assigns documents to coarse partitions. At query time it searches the nearest partition, or several nearby partitions controlled by a probe budget. Near a partition boundary, the closest document may live in the next partition.

The miss isn't a defect in vector meaning. It's an approximation decision. If exact search finds the correct evidence and ANN doesn't, tune or replace the index before changing embeddings.

Put an Exact-Search Gate Around ANN Settings

One anecdote isn't an evaluation. Use a held-out query slice, compute exact nearest results, and report top-1 agreement with exact search (often labeled recall@1 in ANN tuning): how often an ANN configuration returns the same top passage as exact search. That is not multi-neighbor Recall@k over a multi-relevant IR judgment set.

Latency gains aren't free evidence. A production retriever needs both an accuracy report and a latency report for the index setting it serves.

A retrieval review checklist

Before letting an LLM answer from retrieved passages, inspect the stages separately:

This is the first production habit of retrieval-augmented generation (RAG): evaluate the documents entering the prompt before blaming the generator for an unsupported answer.

Practice tasks

1. Add five API-key-heavy distractors to bm25-from-scratch.py. Print each query term's document frequency and explain why rotate should carry more lexical evidence than api.
2. Add a dense-only document d5 to reciprocal-rank-fusion.py. Confirm that the fused output includes it even though BM25 never returned it.
3. Add a fourth judged query to measure-hit-rate-and-mrr.py where the first relevant passage appears at rank 3. Predict how Hit Rate @ 2 and MRR change before running the script.
4. Move the IVF fixture query from [4.9, 0.0] to [5.2, 0.0]. Explain why nprobe=1 now recovers key_rotation.
5. Write a retrieval review record for a small documentation corpus: judged queries, sparse top-k, dense top-k, fused candidates, reranked order, ANN recall against exact search, and latency.

Practice guidance

1. Common terms should have larger document frequency and smaller IDF. The rare task-specific terms should contribute more evidence when they match.
2. Build fusion scores from the union of documents returned by every lane. A lane that omits d5 contributes no reciprocal-rank term for it.
3. A relevant passage at rank 3 misses Hit Rate @ 2 but contributes 1 / 3 to MRR. The metrics answer different questions.
4. At [5.2, 0.0], centroid 1 is closer than centroid 0, so the first probed list contains key_rotation. Probe failures depend on both partition assignment and query location.
5. Keep stage-level artifacts separate. A final answer score can't tell you whether evidence vanished in sparse retrieval, dense retrieval, fusion, reranking, or ANN search.