Core Retrieval Algorithms

In the last chapter, you inspected whether unlabeled embeddings formed meaningful neighborhoods. A support assistant needs a tougher guarantee: given one customer question, can it place the policy page that answers the question near the top? An LLM can't quote a rule that retrieval never places in its context.

We'll build that evidence-selection stage around one query and four help-center passages. You will implement lexical ranking with BM25, dense ranking with cosine similarity, rank fusion, retrieval evaluation, and an approximate-search failure test. By the end, 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

Customer question:

How do I get a refund for an annual plan?

The support assistant may retrieve these passages:

The distinction between d2 and d4 matters. A page may mention refunds and still fail to answer this refund 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. This is why exact policy phrases, order codes, and error identifiers can be found efficiently.

We'll lowercase words, remove punctuation, and discard a short stopword list so the query keeps three discriminating terms: refund, annual, and plan.

d2 is judged relevant, but it doesn't appear in any of these three posting lists. That isn't a bug in lexical retrieval. It is the limitation we will need dense retrieval to cover.

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]

BM25 has implementation variants. The code below 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 is short enough to inspect and precise enough to reproduce each score.

BM25 should put d1 first: it contains all three exact query terms. It should rank d4 above d2 because d4 contains refund, 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

The previous chapter taught you to audit vector geometry. 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]

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 didn't use the literal word refund.

Dense ranking promotes d2, the paraphrase that sparse ranking could not 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:

Do not 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]

The paraphrased answer d2 moves above the refund-status 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.

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]

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

This is why 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]

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.

The lesson isn't that hybrid always wins. It's that an evaluated hard query reveals the weakness 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][7][8]

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 is 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 recall@1: how often an ANN configuration returns the same top passage.

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 refund-heavy distractors to bm25-from-scratch.py. Print each query term's document frequency and explain why annual and plan should carry more lexical evidence than refund.
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 annual_refund.
5. Write a retrieval review record for a small policy 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 policy-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 annual_refund. 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.

Key Concepts

• relevance judgments and evidence selection
• inverted indexes and BM25
• dense retrieval and cosine similarity
• metric contracts for dot product versus cosine
• reciprocal rank fusion (RRF)
• reranking as a second-stage precision pass
• Hit Rate @ K and Mean Reciprocal Rank (MRR)
• ANN recall against exact-search baselines

Evaluation rubric

• Foundational: Explains why d1, d2, and d4 are treated differently for the same refund question, then reproduces BM25 and cosine rankings.
• Intermediate: Builds sparse, dense, and RRF stages and measures a judged retrieval run with Hit Rate and MRR.
• Advanced: Diagnoses whether a missing policy page was lost by retrieval, reranking, or ANN approximation, and proposes an exact-baseline release gate.

Follow-up questions

Common pitfalls