A support engineer types "E1043 X200 paper jam" into the company's new semantic search. The top results are thoughtful articles about printer jams in general. The one page that mentions error E1043 on the X200, the page that actually fixes the problem, is ranked fifteenth. An embedding model has squeezed "E1043" into the same neighborhood as every other error code, because for most of its training data, one error code is much like another.

That's the gap this section fills. Exact word matching, an idea from the 1970s refined into BM25 by the 1990s, is still one of the strongest retrieval methods there is. On BEIR's zero-shot benchmark, BM25 beat many neural retrievers of its day outside their training domain (Thakur et al., 2021). The best systems don't choose. They combine lexical and dense retrieval, then rerank the survivors with a model that reads the query and each candidate together. And to know whether any of it works, you need metrics you can compute correctly in your sleep. We'll build all of it.

The inverted index

Lexical search represents a document as a sparse vector over the vocabulary $\mathcal{V}$, with one coordinate per word that appears in it. Scoring a query is a dot product between two sparse vectors, which only involves the words they share. So instead of storing documents, a search engine stores, for each term $t$, a posting list of the documents containing it and how often. That's the inverted index, and it's why Google could search the web in 1998. A query touches only the posting lists of its own terms, so its cost is the total length of those lists, the number of documents that contain each query term, summed over the terms. For the rare, specific terms that carry most queries, that is a tiny fraction of the collection, and engines skip most of even those lists with dynamic pruning algorithms such as WAND, which stop scoring documents that can no longer reach the top $k$.

Throughout this section, $D$ is a document, $q$ is a query (a set of terms), $n$ is the number of documents in the collection, $\operatorname{tf}(t, D)$ is how many times term $t$ occurs in $D$, $\operatorname{df}(t)$ is the number of documents containing $t$, $|D|$ is the length of $D$ in tokens, and $\overline{|D|}$ is the average length over the collection.

TF-IDF, and what it gets wrong

You met TF-IDF in §1.4 as a weighting for co-occurrence matrices. As a ranking function it scores

In plain words, a document scores well when it uses the query's words often, and rare words count for more than common ones. The idea that rarity signals importance is Karen Spärck Jones's (1972). A query word that appears in every document can't help you choose among them.

Two flaws show up the moment you try it.

1. Term frequency grows without bound. A page that says "jam" 40 times gets 40 times the credit of a page that says it once. But the second mention of a word is strong evidence of aboutness, and the fortieth adds almost nothing. We want a score that saturates.
2. Long documents win for being long. A 5,000-word manual mentions everything more often than a 50-word answer. We need to normalize by length, but not completely, because some long documents really do cover more.

BM25 fixes both, and the way it fixes them is worth understanding, because interviewers ask you to derive it.

BM25 derived from the probabilistic relevance framework

BM25 comes from Stephen Robertson and colleagues' probabilistic model of retrieval, summarized in Robertson and Zaragoza (2009). It's built in three steps.

Step 1, rank by probability of relevance. The probability ranking principle (Robertson, 1977) says that if you rank documents by $\mathbb{P}(\text{relevant} \mid D, q)$, you get the best expected precision at every cutoff. Ranking by that probability is the same as ranking by its log odds.

Step 2, the binary independence model gives IDF. Pretend a document is just the set of terms it contains, and that terms occur independently given relevance. Let $p_t$ be the probability that term $t$ appears in a relevant document and $\bar p_t$ the probability it appears in a non-relevant one. Then the log odds of relevance, up to a constant that doesn't depend on $D$, is a sum over the query terms present in $D$ of the Robertson and Spärck Jones (RSJ) weight

Without any relevance judgments we have to guess $p_t$ and $\bar p_t$. Almost every document is non-relevant, so $\bar p_t \approx \operatorname{df}(t)/n$. For $p_t$, with no information, take $1/2$. Then $p_t/(1 - p_t) = 1$ and

where the 0.5s are the smoothing from the RSJ formula with zero relevance information. In plain words, IDF falls out of a probabilistic model as the log odds that a term marks a document as unusual. One practical wrinkle is that this IDF goes negative for terms in more than half the documents, so Lucene and Elasticsearch use $\log\big(1 + \frac{n - \operatorname{df}(t) + 0.5}{\operatorname{df}(t) + 0.5}\big)$, which is always positive. We'll use that form.

Step 3, term frequency with saturation and length normalization. The binary model ignores how often a term appears. Robertson's group modeled term counts with a mixture of two Poisson distributions, one for documents that are really about the term ("elite" documents) and one for documents that mention it in passing. The exact formula is unwieldy, but its shape is simple. It's zero at $\operatorname{tf} = 0$, increases, and levels off. BM25 replaces it with the simplest function of that shape,

where $k_1 \ge 0$ sets how quickly it saturates. For length, the "verbosity" view says that a document twice as long says the same things with twice as many words, so its counts should be divided by its relative length. The "scope" view says it covers more topics and its counts are honest. BM25 interpolates between the two with $b \in [0, 1]$, dividing the count by

Substituting $\operatorname{tf}/\nu(D)$ into the saturation function and multiplying by $(k_1 + 1)$, which makes a single occurrence in an average-length document worth exactly 1, gives the full formula,

In plain words, each shared term contributes its rarity times a saturating count, where the count is discounted for documents longer than average.

The two knobs have clean extremes. With $k_1 = 0$ the count term is 1 whenever the term is present, so BM25 becomes a binary model that ignores repetition. As $k_1 \to \infty$ it approaches raw tf with length normalization. With $b = 0$ there's no length normalization, and with $b = 1$ there's full normalization. The model itself says nothing about how to set them. Robertson and Zaragoza (2009) report that many retrieval experiments found values around $1.2 \lt k_1 \lt 2$ and $0.5 \lt b \lt 0.8$ to work reasonably well, while noting that the best values depend on the documents and queries. Lucene and Elasticsearch default to $k_1 = 1.2$ and $b = 0.75$. Treat these as starting points and retune them on your data.

Let's score a tiny collection by hand. Four documents, the query "cat mat", $k_1 = 1.2$, $b = 0.75$.

Check the first document. "cat" appears in 3 of the 4 documents, so $\operatorname{IDF} = \ln(1 + 1.5/3.5) = 0.357$. The document has 6 tokens against an average of 5.75, so $\nu(D) = 0.25 + 0.75 \times 6/5.75 = 1.033$, and the count part is $1 \times 2.2/(1 + 1.2 \times 1.033) = 0.982$. That's $0.357 \times 0.982 = 0.350$ for "cat", and "mat" adds $0.681$ the same way, for a total of $1.031$. Now look at the fourth document. It says "cat" four times and is short, yet it scores only 1.8 times what a single mention earns. That's saturation doing its job, and the document that matches both terms wins.

import numpy as np
from collections import Counter

def bm25(query, docs, k1=1.2, b=0.75):
    raise NotImplementedError

SPLADE, sparse vectors learned by a Transformer

BM25's weakness is the flip side of its strength. It matches only the words you typed. A query for "car" misses a document that says "automobile", the vocabulary mismatch problem. Could a model learn sparse vectors, with the efficiency and exact-match behavior of an inverted index, but with term weights and expansions that understand language?

SPLADE (Formal et al., 2021) does exactly that with BERT's MLM head from §7.1. Run the text through BERT, and at every position $i$ the MLM head produces logits $w_{ij}$ over the whole vocabulary, scores for "which word could be here". SPLADE turns them into one non-negative weight per vocabulary word,

using max pooling over positions as in SPLADE v2 (the first version summed). In plain words, each word in the vocabulary gets the strongest evidence any position in the text provides that it belongs, and the log damps large values the way BM25's saturation does.

The score of a query and a document is the dot product of their vectors, $\mathbf{s}_q^\top \mathbf{s}_D$, which an inverted index computes efficiently as long as the vectors are sparse. A document about cars now has weight on "vehicle" and "automobile" even if it never uses those words. That's document expansion, learned end to end with the InfoNCE loss of §7.2.

What keeps the vectors sparse? A regularizer. The obvious choice, the $\ell_1$ norm of each vector, makes every vector sparse but ignores which terms are active. An inverted index is slow when a few terms are active in a huge share of documents, because their posting lists are long. The cost of a sparse dot product is proportional to $\sum_j \mathbb{P}(\text{term } j \text{ active in } q)\,\mathbb{P}(\text{term } j \text{ active in } D)$, so SPLADE uses the FLOPS regularizer of Paria et al. (2020), a smooth version of that cost estimated on a batch of $N_b$ documents,

In plain words, square each term's average weight over the batch, so a term active everywhere is punished much more than one active in a single document. SPLADE v2 reported more than 9 percent gains in nDCG@10 on TREC DL 2019 over the first version and state-of-the-art BEIR results at the time (Formal et al., 2021).

import numpy as np

def splade_vectors(logits, mask):
    raise NotImplementedError

def flops_reg(S):
    raise NotImplementedError

Hybrid search with reciprocal rank fusion

Lexical and dense retrievers fail on different queries. BM25 misses paraphrases, dense models miss rare identifiers and exact phrases. So run both and combine their rankings. The question is how.

Adding raw scores doesn't work. BM25 scores are unbounded and depend on query length and the collection, while cosines live in $[-1, 1]$ and cluster in a narrow band. You can normalize each list (for example min-max to $[0, 1]$) and take a weighted sum, but then the weight needs tuning per collection, and normalization is sensitive to outliers at the top of a list.

Reciprocal rank fusion (RRF, Cormack, Clarke & Büttcher, 2009) ignores scores and uses only ranks. For a set $\mathcal{F}$ of ranked lists to fuse, where $r(D)$ is the rank of document $D$ in list $r$ (starting at 1),

and a document missing from a list contributes nothing from it. In plain words, each list votes for each document with a weight that falls off with rank, and the constant $k_{\text{rrf}}$ keeps the top few positions from dominating. With $k_{\text{rrf}} = 60$, rank 1 is worth $1/61$ and rank 10 is worth $1/70$, so a document that's fifth in both lists ($2/65 = 0.0308$) beats one that's first in one list and absent from the other ($1/61 = 0.0164$). That's the behavior you want from a fusion method, rewarding agreement. The constant 60 came from the original paper's experiments, where RRF beat the individual systems it combined and the standard fusion methods of the time. It's robust enough that many search engines and vector databases ship it as their standard way to fuse hybrid results.

def rrf(rankings, k=60, top=None):
    raise NotImplementedError

Reranking with cross-encoders

A bi-encoder, dense or sparse, never lets the query and the document look at each other. A cross-encoder does. Feed [CLS] query [SEP] document [SEP] into an encoder, exactly the pair format that outlived NSP in §7.1, and put a linear layer on the [CLS] state to output a relevance score. Every query token can attend to every document token in every layer, so the model can check negation, word order, and which entity does what.

monoBERT (Nogueira & Cho, 2019) did this with BERT on MS MARCO and beat the previous state of the art by 27 percent relative in MRR@10. Cross-encoders are trained either pointwise, with binary cross-entropy on relevant and non-relevant pairs, or listwise, with a softmax over one positive and several hard negatives per query, which is InfoNCE again with a cross-encoder as the critic. Modern rerankers are often distilled from larger ones or from LLM judgments, and instruction-tuned LLMs (the kind Chapter 14 builds) can rerank listwise, given a numbered list of passages and asked to output an ordering (RankGPT, Sun et al., 2023).

The catch is cost. A cross-encoder needs one forward pass per query and document pair, so it can never score a whole collection. It reranks a shortlist.

Reranking 100 candidates costs about 11 TFLOP, tens of milliseconds on a modern GPU, which is affordable. Scoring the whole collection is not. That gives the standard retrieval stack, often called retrieve and rerank.

1. Candidate generation. BM25 and a dense retriever each fetch a few hundred candidates, cheaply, with high recall.
2. Fusion. RRF merges the lists.
3. Reranking. A cross-encoder scores the top 50 to 200 fused candidates and the top 5 to 20 go to the user, or to an LLM in §7.6.

The reranker's knowledge can also flow backward, into the cheap first stage. Score each query's candidates with the cross-encoder, turn the scores into a teacher distribution $\mathbf{t} = \operatorname{softmax}(\text{teacher scores}/T)$ over the candidates, and train the bi-encoder to match it, minimizing $\operatorname{KL}(\mathbf{t} \,\Vert\, \operatorname{softmax}(\text{student scores}))$ instead of, or alongside, InfoNCE's one-hot target. The teacher's soft labels say how relevant each hard negative is, which a binary label cannot, and they quietly fix false negatives, since an unlabeled relevant passage gets a high teacher score. RocketQA, E5's fine-tuning stage, and ColBERTv2 all distill this way, and Margin-MSE (Hofstätter et al., 2020) is a popular variant that matches the teacher's score gap between a positive and a negative.

Each stage is tuned for what it's good at. First stages for recall at large $k$, the reranker for precision at small $k$. That means you must measure them with different metrics, which is the last topic of this section.

Retrieval metrics, done right

Here's a question that sounds easy. Two retrievers answer the same 200 queries. System A puts a relevant document first more often. System B finds more of the relevant documents somewhere in its top 20. Which is better? It depends on who consumes the ranking. A person who reads the first result, a reranker that rescores the top 100, and a language model that reads the top 5 want different things, and each metric below encodes one of those wants. Getting them right, and computing them correctly, is a standard interview topic and a common source of silent bugs.

Fix one query with a set of relevant documents $\mathcal{R}$ (possibly with graded relevance labels), and a ranked list of retrieved documents $D_1, D_2, \dots$. Precision and recall for a classifier, with their trade-off and their confidence intervals, are the subject of §0.11. Ranking adds one ingredient, the cutoff $k$, since the system returns a list and the reader stops somewhere.

Precision@k and recall@k. Precision@k is the fraction of the top $k$ that are relevant, $|\{D_1, \dots, D_k\} \cap \mathcal{R}|/k$. Recall@k is the fraction of the relevant documents that made the top $k$, $|\{D_1, \dots, D_k\} \cap \mathcal{R}|/|\mathcal{R}|$. Recall answers "did we find them?", which is what a first stage feeding a reranker should maximize, at a large $k$ such as 100 or 1,000. Precision answers "how much of what we show is useful?", which matters when every slot costs something, such as prompt tokens. Don't confuse this recall with the recall of §7.4, which compares an approximate index with exact search and needs no relevance labels at all. A perfect index can have poor retrieval recall, because the embedding model ranked the wrong documents first. RAG pipelines often report a third variant, hit rate@k (also called success@k), which is 1 if any relevant document is in the top $k$ and 0 otherwise.

Reciprocal rank is $1/\text{rank of the first relevant document}$ (0 if none is retrieved). Averaged over queries, it's the mean reciprocal rank (MRR). It fits tasks with one right answer, such as known-item search or question answering, and it is harsh, since the first result is worth 1 and the second only 0.5. MS MARCO reports MRR@10, which counts only the top 10.

Average precision rewards every relevant document, not just the first. Take the precision at each rank where a relevant document appears, add them up, and divide by the number of relevant documents,

so relevant documents that were never retrieved contribute zero. In plain words, AP is the average, over the relevant documents, of how clean the list was down to each of them. Averaged over queries it is the mean average precision (MAP), the metric MTEB uses for reranking (§7.3). For a ranking with relevant documents at ranks 1 and 3 out of two relevant in total, AP is $(1/1 + 2/3)/2 = 0.833$. If a third relevant document existed and was never retrieved, AP would drop to $(1 + 2/3)/3 = 0.556$. That denominator is the most common bug, dividing by the number of relevant documents retrieved instead of all of them, which rewards a system for retrieving less.

nDCG@k handles graded relevance (say 0 to 3) and rewards putting the best documents first. The discounted cumulative gain adds each result's gain, discounted by the log of its position,

where $\operatorname{rel}_i$ is the relevance label of the document at rank $i$, and the ideal DCG, $\operatorname{IDCG}@k$, is the DCG of the best possible ranking, all judged documents sorted by label (Järvelin & Kekäläinen, 2002). In plain words, nDCG asks how much of the best achievable gain your top $k$ captured, with each position counting a bit less than the one above it. The position-1 document gets full weight, position 3 half ($1/\log_2 4$), and position 7 a third ($1/\log_2 8$).

Two conventions for the gain are in use. TREC's tools and BEIR (and so MTEB) use the label itself, as above. Learning-to-rank papers often use $2^{\operatorname{rel}_i} - 1$ (Burges et al., 2005), which rewards highly relevant documents more strongly. Results computed with different conventions aren't comparable, so say which one you use.

Let's compute all of them for one ranking by hand. The query has four judged relevant documents, with labels 3, 2, 1, and 1, and the system returns five documents with labels $[3, 2, 0, 1, 0]$. The fourth relevant document wasn't retrieved.

By hand, $\operatorname{DCG}@5 = 3/1 + 2/1.585 + 0 + 1/2.322 + 0 = 3 + 1.262 + 0.431 = 4.693$. The ideal ranking is $[3, 2, 1, 1]$, so $\operatorname{IDCG}@5 = 3 + 1.262 + 0.5 + 0.431 = 5.193$ and $\operatorname{nDCG}@5 = 0.904$. Recall@5 is 3 of 4, and the reciprocal rank is 1.

import numpy as np

def retrieval_metrics(ranked, qrels, k):
    raise NotImplementedError

def average_precision(ranked, relevant):
    hits, total = 0, 0.0
    for i, d in enumerate(ranked, start=1):
        if d in relevant:
            hits += 1; total += hits / i
    return total / max(hits, 1)

def mean_ap(ranked_by_q, qrels):

Where the labels come from

Every metric above needs relevance labels, and labels are the expensive part. Nobody judges every document in a collection of millions for every query. TREC-style evaluations use pooling. Each participating system submits its top results, the union of everyone's top 100 or so is judged by assessors, and every unjudged document is treated as non-relevant (Manning, Raghavan & Schütze, 2008, chapter 8). That works well for the systems in the pool. A new system that finds relevant documents nobody else found is penalized for them, because they were never judged. So when you evaluate a genuinely new retriever on an old pooled benchmark, report how many of its top 10 were judged at all. A low number means the score is a lower bound.

The two big passage benchmarks show why the metric follows the labels. MS MARCO has about one judged relevant passage per query, labeled sparsely from clicks and annotators, so recall is noisy and MRR@10 is the natural measure. The TREC Deep Learning tracks judged a few dozen queries deeply, with graded labels from 0 to 3, which is what nDCG@10 needs. BEIR mixes both kinds and reports nDCG@10 everywhere (§7.3).

Is the difference real?

Suppose the new model gains two points of nDCG@10. Retrieval metrics are averages over queries, and query difficulty varies far more than systems do. Some queries are easy for everything, some are hopeless for everything. That's why you compare systems per query, with a paired test on the differences, the paired bootstrap or randomization test of §0.11. Here are two simulated systems where B is truly 2 points better, compared on query sets of three sizes.

With 50 queries the true gain is invisible. The measured difference even has the wrong sign, and the interval covers zero comfortably. With 200 the paired test finds it, while an unpaired interval, which ignores that both systems answered the same queries, still straddles zero. The pairing removes the variation in query difficulty, which is most of the variance. So report per-query paired comparisons, and be wary of leaderboard gaps of a point or two on small test sets.

In PyTorch

A cross-encoder is an encoder with a scalar head, trained listwise here with one positive and several negatives per query. With random weights the numbers are meaningless, but the shapes and the loss are exactly what you'd use.

A real pipeline, with BM25 from rank_bm25, a dense retriever, RRF, and a pretrained reranker from sentence-transformers, looks like this. It needs downloads, so it's shown and not run.

Read more

• Robertson & Zaragoza (2009). The Probabilistic Relevance Framework: BM25 and Beyond. The derivation of BM25 from the people who invented it.
• Manning, Raghavan & Schütze (2008). Introduction to Information Retrieval, chapters 6, 8, and 11. Inverted indexes, TF-IDF, evaluation, and the probabilistic model, free online.
• Formal et al. (2021). SPLADE v2: Sparse Lexical and Expansion Model for Information Retrieval. Max pooling, distillation, and the FLOPS regularizer in practice.
• Cormack, Clarke & Büttcher (2009). Reciprocal Rank Fusion outperforms Condorcet and individual Rank Learning Methods. Two pages, one formula, still the default.
• Nogueira & Cho (2019). Passage Re-ranking with BERT. The cross-encoder reranker that changed MS MARCO.
• Järvelin & Kekäläinen (2002). Cumulated Gain-based Evaluation of IR Techniques. Where DCG and nDCG come from.
• Thakur et al. (2021). BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models. Zero-shot retrieval across 18 datasets, and the case for BM25 as a baseline.
• Sun et al. (2023). Is ChatGPT Good at Search? Investigating Large Language Models as Re-Ranking Agents (RankGPT). Listwise reranking with LLMs.

Watch next

▶

▶

▶

▶