BM25, bi-encoders and recall@k

Comparing two retrievers requires three things you can state precisely: what each one scores, and what the number that compares them counts. This chapter gives working definitions of all three. Later topics go deeper on each family and on the metric; what is here is enough to implement both rankers, run them against a labelled set, and read the result without arguing about what it means.

The labelled set is the one from chapter 2, on diagnosing annotator disagreement — a hundred queries or so, each with the documents an annotator judged relevant under a stated rubric. Everything below turns that into a figure.

Scoring a document by the words it actually contains#

Lexical retrieval starts from a question with a mechanical answer: which of the query's terms appear in this document, and how surprising is each appearance. An inverted index maps each term to the list of documents containing it, so answering "which documents contain page_size" is a dictionary lookup rather than a scan. The scoring function that has been the default for three decades is BM25, which came out of the probabilistic retrieval work Stephen Robertson and Karen Spärck Jones began in the 1970s and was hardened over successive evaluations at TREC, the Text REtrieval Conference, through the 1990s. It is what Lucene, and therefore Elasticsearch and OpenSearch, computes unless told otherwise.

import math
from collections import Counter


def bm25_score(query_terms, doc_terms, df, n_docs, avgdl, k1=1.2, b=0.75):
    """Score one document. df maps term -> number of docs containing it."""
    tf = Counter(doc_terms)
    dl = len(doc_terms)
    score = 0.0
    for term in query_terms:
        if tf[term] == 0:
            continue
        idf = math.log(1 + (n_docs - df[term] + 0.5) / (df[term] + 0.5))
        norm = tf[term] + k1 * (1 - b + b * dl / avgdl)
        score += idf * (tf[term] * (k1 + 1)) / norm
    return score

Three behaviours in that expression are worth holding onto, because they explain most of what lexical retrieval gets right and wrong. The idf factor — inverse document frequency, a term's rarity across the corpus — rewards rare terms steeply: in a 12,000-document corpus where page_size appears in 3 documents, its IDF is ln(1 + (12000 - 3 + 0.5) / 3.5) ≈ 8.15, while the word pagination, appearing in 410 documents, scores ln(1 + 11590.5 / 410.5) ≈ 3.38. A single hit on the rare identifier contributes more than two hits on the common topic word, which is exactly the behaviour you want when a developer pastes an error code or a function name. Term frequency saturates through the (tf * (k1 + 1)) / (tf + ...) form, so a document mentioning page_size twelve times scores about 1.9 times a document mentioning it once rather than twelve times — keyword stuffing buys little. And b = 0.75 normalises by length against the corpus average, so a 200-word focused page beats a 4,000-word page that mentions the term in passing.

Both of those IDF figures repay being computed rather than accepted, because the shape of the expression is what produces the behaviour. The quantity inside the logarithm is close to the number of documents that do not contain the term, divided by the number that do. For page_size in 3 documents out of 12,000 that ratio is nearly three and a half thousand to one. For pagination in 410 documents it is a little over twenty-eight to one. Taking the logarithm compresses those two ratios into 8.15 and 3.38, and the compression is the point of the logarithm rather than an incidental detail. Without it, a term appearing in a single document would outweigh every other term in the query by three orders of magnitude and the score would collapse into a lookup on the rarest word present. With it, roughly a hundredfold difference in rarity becomes a difference of a bit under five in weight — large enough to dominate, small enough that a second term can still matter.

The saturation figure deserves the same treatment, because it has a ceiling that is easy to read past. Take a document of average length, so the length factor 1 - b + b * dl / avgdl collapses to one and norm is just tf + k1. One mention scores (k1 + 1) / (1 + k1), which cancels to exactly one. Twelve mentions score 12 * (k1 + 1) / (12 + k1), and since k1 is small beside twelve the denominator is barely more than twelve, so the twelves very nearly cancel too and what survives is close to k1 + 1 on its own. That is the ceiling. No term frequency, however large, lifts the factor above k1 + 1, which at the default is a little over two, and twelve mentions have already claimed almost all of it. The second mention is worth a good deal and the twelfth is worth almost nothing. This also makes the comparison in the paragraph above stronger than it reads: a single hit on page_size at 8.15 beats two hits on pagination, and it beats them by more than doubling 3.38 would suggest, because the second hit does not double anything.

What the function cannot do follows just as directly. It scores string identity after whatever the analyzer does — lowercasing, stemming, stopword removal — so pagination and paginating collapse together while cursor-based iteration and paging through results share nothing. A misspelled page_szie has a document frequency of zero and contributes no score at all. And because "not" is a stopword in most default analyzer chains, the polarity query from chapter 3, on constraints similarity cannot carry, reaches the scorer with the negation already deleted.

Scoring by proximity in a learned space#

The embedding path replaces string matching with geometry. A bi-encoder maps the query and each passage independently into the same vector space — 768 or 1,536 dimensions is typical — and the score is the cosine of the angle between them, the same arithmetic on a single pair of vectors applied across a whole corpus. Because the passage vectors do not depend on the query, they are computed once at index time and reused, which is what makes the approach practical.

At 12,000 passages and 768 float32 dimensions the whole matrix is about 35 MB, and an exact scan — one matrix-vector product — takes roughly 10 ms on a laptop core, so nothing clever is required. The arithmetic scales linearly, so at 5 million passages the same exact scan is around 4 seconds per query, which is where approximate nearest neighbour indexes such as HNSW, the hierarchical navigable small-world graph, come in: they trade a small amount of recall against the exact result for a sublinear search, typically returning the true top 10 about 95 to 99% of the time at single-digit milliseconds, tunable through the graph's search-breadth parameter. That trade introduces a second, purely mechanical source of missed documents, distinct from anything to do with relevance, and it is worth measuring separately by comparing the ANN result against an exact scan on a sample of queries before concluding that the embedding model is at fault for something.

Each of those figures is one multiplication, and doing them is what turns the four seconds from a quotation into a prediction. Twelve thousand passages at 768 dimensions is a little over nine million numbers. A float32 is four bytes, so the matrix comes to about thirty-seven million bytes, and thirty-seven million bytes counted in the binary megabytes a machine reports is the 35 MB above. The scan follows from the same shape. An exact search multiplies the query vector against every row of that matrix and does nothing else, so the work is proportional to the number of rows. Five million passages over twelve thousand is a factor of about four hundred, and four hundred times 10 ms is a little over four seconds. None of that chain is an estimate — the linear growth is a property of the operation — which is why the size at which an exact scan stops being viable can be worked out in advance rather than discovered in production.

Both families rank whatever unit you decided to index, and that decision sits upstream of everything in this chapter. If an SLA page is indexed whole, both rankers score a single four-thousand-word object in which an exclusions appendix is a small fraction of the signal. If it is split into eight-hundred-character chunks, the appendix becomes its own retrievable unit with its own vector and its own term statistics, and BM25's length normalisation stops penalising it. The same corpus under two chunking schemes produces different scores for both families, which means a comparison between rankers is only meaningful when they are reading identical units. Fixing the chunking first, and recording it next to every number you report, is what keeps a later "the dense retriever got better" from being a chunk-size change nobody logged.

Both halves of that have a mechanism behind them, and they are different mechanisms, which matters because it means chunking moves the two rankers for unrelated reasons. On the lexical side the length normalisation does it: b at its default divides by the ratio of this document's length to the corpus average, so a four-thousand-word page carries a ratio well above one and every term in it is discounted for the company it keeps. On the dense side there is no length term anywhere in the scoring; the appendix is diluted because a passage vector is a pooled average over its tokens, and the appendix's tokens are a small share of four thousand words. Splitting the page removes the lexical discount and removes the dilution by two separate routes, and there is no reason those two routes should move by the same amount. That is why one chunking change can lift BM25 and the bi-encoder by different margins in the same direction, and why a comparison run across a chunking change is not a comparison at all.

The evidence the two families use has almost no overlap, which is why their failures do not coincide. Reading the table needs one more term: an encoder does not work on whole words but on subword tokens, because its tokenizer breaks any unfamiliar string into familiar fragments, which is why a typo keeps most of its meaning while a rare identifier is scattered into pieces that mean little on their own.

The first row is a useful check on the IDF discussion above rather than a new claim. ERR_4021 appears in fewer documents than page_size did, and IDF rises as document frequency falls, so its weight has to come out above page_size's 8.15 — which it does. That is the property to trust in a table like this one: the ordering of the weights follows the ordering of the rarities, and a row whose weight moved the wrong way against its document frequency would be a sign that the corpus statistics behind the table came from somewhere else. The fourth row is the one to read twice, because it is the only one where the outcome column says both. Every other row has a winner, and having a winner is what makes running the two families together worth considering. A row where both fail is a row no amount of combining rescues, since the union of two result lists contains nothing neither list contained.

Turning per-query labels into one number#

Recall@k is the fraction of labelled queries for which at least one relevant document appears anywhere in the top k results. The definition is short and each clause carries weight.

def recall_at_k(runs: dict[str, list[str]], qrels: dict[str, set[str]], k: int) -> float:
    """runs: query_id -> ranked doc_ids. qrels: query_id -> set of relevant doc_ids."""
    scored = [q for q in qrels if qrels[q]]        # skip queries with no relevant docs
    hits = sum(1 for q in scored if set(runs[q][:k]) & qrels[q])
    return hits / len(scored)

It counts queries rather than positions. A query whose relevant document sits at rank 1 and a query whose relevant document sits at rank 10 contribute identically, and a query with four relevant documents of which three were found contributes exactly the same as one where a single relevant document was found. The metric is binary per query and then averaged, so it answers one question only: for what fraction of user questions was the evidence in front of the model at all.

Four hits over five scored queries is recall@10 = 0.80, and q4 shows the coarseness plainly: two of three relevant documents found scores the same as three of three. That is a real limitation when the task requires coverage, and it is why an assistant answering multi-part questions needs a coverage-sensitive metric alongside this one. Row q5 shows a second trap. If d61 and d62 contain the same text as d60 but were never labelled, the run is punished for finding the right content under the wrong identifier, which is an artefact of the label set rather than a retrieval failure. Deduplicating the corpus before labelling, or labelling by content hash, avoids weeks of chasing a phantom.

The qrels argument in that function — the name is standard in retrieval evaluation and is short for query relevance judgments — is the labelled set, reshaped: the pairs marked relevant become the set of relevant document identifiers for their query, and everything marked irrelevant simply does not appear. Pairs marked partial need a decision that should be made once and written down, since counting them as relevant raises every recall figure by several points and counting them as irrelevant lowers it, and a team that changes the convention mid-project will spend a day chasing a regression it created in a spreadsheet. The conservative convention is to exclude partial from the relevant set for recall and report the count separately, so the headline number always means "the answer was there", never "something adjacent was there".

The direction of that shift is guaranteed while its size is not, and the guarantee holds under one condition worth stating out loud. For a query that already has at least one document marked relevant, promoting its partial pairs only adds members to the set the metric is looking for. A query that was a hit stays a hit, a query that was a miss may become one, and recall for that query cannot fall. The condition is the queries whose only positive pairs were partials. Under the conservative convention those queries carry no relevant documents at all and are excluded from the denominator, and promoting their partials pulls them into it, where they may be hits or misses. So the aggregate usually rises and is not obliged to. That is the second reason to fix the convention before any number is produced: a figure that can move in either direction because of a labelling choice is not something anybody will successfully debug afterwards.

The first line of the function skips queries with no relevant documents. That is not defensive coding against a malformed file; those queries exist deliberately in a good eval set, and dividing by them would make the metric meaningless. Chapter 7, on questions no ranking can answer, returns to what they are for.

What dividing by them would actually do is worth spelling out, because the line reads like a guard clause and is a definition. A query with no relevant document in the labelled set cannot produce a hit under any ranker, at any k, ever. Including it therefore contributes a guaranteed zero to the numerator and a one to the denominator, so the reported recall falls by an amount fixed entirely by how many such queries the set happens to contain. Two teams measuring the identical retriever on sets differing only in their share of unanswerable queries would report different figures and both be right, which makes the number a description of the set rather than of the system.

The choice of k is the decision people make carelessly. Report recall at the k you actually put into the prompt. Measuring recall@50 for a system whose prompt template accepts five passages describes a system nobody runs, and it will read as excellent while the deployed pipeline drops most of what it measured. The reason extending k always flatters the figure is mechanical rather than statistical: recall@k never decreases as k grows, because any document inside the top five is also inside the top fifty, so a larger k can add hits and can never remove one. A metric that cannot fall when one free parameter is turned up is a metric that will be quoted at whichever setting of that parameter somebody tried first, and the only defence is to pin it to the number the prompt template accepts and write it next to the score.

Recall@k is the right first metric for a retrieval-augmented system because it measures the ceiling. No prompt, no reranker and no stronger model can recover a fact that never entered the context window, which is the bounded span of text the model reads in a single request, so the recall figure bounds everything downstream. It bounds and does not predict: recall@10 of 1.0 is entirely compatible with an answer rate of 60%, since the evidence being present says nothing about it being used.

The word ceiling there is meant literally, and the argument for it is one step long. A fact that never entered the context window cannot be quoted out of it, so a query whose evidence retrieval missed cannot be answered correctly from retrieved evidence. The share of queries answered correctly is therefore at most the share whose evidence was retrieved, and that second share is recall@k at whichever k the prompt uses. This is an inequality rather than a correlation, which is what makes it useful: recall@10 of 1.0 sitting above an answer rate of 60% is precisely what the inequality permits, and the forty points between them are a generation problem that no amount of retrieval work will move. Run it the other way and it is just as informative. An answer rate that exceeds recall means the model is answering from something other than the retrieved passages, which is worth finding out about before it is presented as a retrieval result.

Two systems, one average#

Two systems with the same recall@k are not thereby the same system, and this is where the metric's coarseness stops being a convenience and becomes a hazard. Because it collapses each query to a bit and then averages, two runs can agree on the average while disagreeing on which queries produced the bits — the average is invariant to which queries fail, and the identity of the failing queries is usually the entire content of the comparison.

The arithmetic under that observation is what makes it worth acting on rather than merely worrying about. Take the top k from each of two runs, merge the two lists, and ask again whether any relevant document is present. Recall over that union is at least the larger of the two individual figures, because every query that hit under either ranker still hits. It is strictly larger whenever some query hits under one and misses under the other. So a tie at the same average says nothing at all about whether combining the two is worth anything, and the measurement that does say something is the count of queries where the two disagree. A tie with no disagreement means both rankers are finding the same evidence and one of them is redundant. A tie with substantial disagreement means they are finding different evidence at the same rate, and their union is strictly better than either — the same average, two entirely different conclusions, separated by a number nobody computed.

Three definitions, then, and they carry most of the weight in this topic. BM25 scores rare-term overlap with saturation and length normalisation, and cannot see meaning. A bi-encoder scores proximity in a learned space, and cannot see exact strings, negation or entity identity. Recall@k reports, per query, whether the evidence was anywhere in the top k, then averages — which makes it the ceiling on everything downstream and a poor instrument for telling two systems apart.

That last property is not hypothetical. Running BM25 and a dense retriever — the embedding path described above, called dense because each vector is a full array of numbers rather than a sparse list of term counts — against the same three hundred labelled queries produced 0.74 for both, and the meeting that followed nearly ended with a decision to keep the simpler system on the grounds that the numbers were identical.