Information Retrieval (IR)

Definition

Information retrieval (IR) is the problem of turning a short, ambiguous request — two or three words typed into a box — into a ranked list of documents drawn from a collection nobody could read. The ranking is the entire discipline. Finding the documents that contain your words is easy and almost never useful: on a collection of a million documents where six pages genuinely answer the question, a system that returns everything has achieved perfect recall and a precision of 6 in 1,000,000, which is 0.0006%. Deciding which six of the ten thousand matching documents belong at the top is the part that is hard, and it is what every technique below exists to do.

IR is older than machine learning as a practical field, and its two durable inventions are still running underneath everything: the inverted index, which is why a search over ten million documents does not read ten million documents, and a scoring function — today almost always BM25 — that turns word counts into an ordering. Layered on top of those is a third contribution that outlasted both: a way of measuring whether a ranking is any good, using precision, recall, mean average precision, mean reciprocal rank and nDCG. Those five metrics are the shared vocabulary of the field. A retrieval system you cannot score is a system you cannot improve, and the arithmetic below is the whole of it.

Everything newer sits inside this frame rather than replacing it. Vector search is a different way to generate candidates; semantic search is a different way to interpret the query; retrieval-augmented generation bolts a language model onto the end. All three are evaluated with nDCG and recall on test collections built the way Cyril Cleverdon's team built one at the College of Aeronautics at Cranfield in the 1960s.

How It Works

Never scan the collection

A naive search reads every document and checks whether it contains the query terms. Put numbers on that. Ten million documents averaging 500 words each is 5 billion word occurrences; at roughly 6 bytes per word that is about 30 GB of text. Streaming 30 GB from disk at 1 GB/s takes 30 seconds per query, and that is before any scoring.

An inverted index turns the collection inside out. Instead of a map from document to words, it stores a map from word to the list of documents containing it — the posting list. Looking up espresso is a dictionary lookup followed by a sequential read of one list. If espresso appears in 2,000 of the ten million documents, that list is 2,000 document IDs, about 8 KB at 4 bytes each. You have touched 0.02% of the collection, and the number of items read fell from 5,000,000,000 to 2,000 — a factor of 2,500,000.

The complexity statement is the durable version of that arithmetic: a linear scan is O(N · L̄) in the number of documents times their average length, while an index lookup is O(df) in the number of documents containing the term. A two-word query intersects two sorted posting lists in O(df₁ + df₂), because both are stored in document-ID order and a merge walks them once. This is why the index size matters far less than people expect — in the BEIR study below, a BM25 index over roughly 15 million BioASQ documents took 18 GB, while a late-interaction ColBERT index over the same corpus took about 900 GB, a 50× difference driven by storing one vector per token instead of one entry per term.

The cost of the index is that it commits you to a fixed vocabulary decided at indexing time. Whatever the tokenizer does — case folding, stemming, splitting wi-fi — is what the index can find, and a query for a word the index never recorded returns nothing at all. That brittleness is precisely the gap dense retrieval was invented to close.

Decide how much a word is worth

Once you have candidates you have to rank them, and the first idea everyone has is to count. Take a five-document collection and the query espresso machine:

Raw term frequency scores D3 highest with 50, because it says espresso fifty times. That is the first failure: a document repeating a word fifty times is not fifty times more relevant than one saying it twice.

The second idea fixes a different problem. machine appears in three of the five documents and espresso in four, so machine is the more discriminating word — inverse document frequency turns that into a weight. Under the textbook form log₁₀(N / df), espresso is worth 0.0969 and machine 0.2218. Under the form BM25 actually uses, ln((N − df + 0.5)/(df + 0.5) + 1), they are 0.2877 and 0.5390. The idea, from Karen Spärck Jones's 1972 paper in the Journal of Documentation, is that a term's value is a function of how rarely it is used, not of what it means. Multiply the two and you get TF-IDF:

The spam page is still first. IDF fixed which words matter and did nothing about repetition, because the term frequency going into the product is still raw.

BM25, and the two things it fixes

BM25 — Okapi BM25, from Stephen Robertson and Steve Walker's work at City University London, presented at TREC-3 in 1994 and built on the probabilistic weighting model Robertson and Spärck Jones published in 1976 — replaces the raw count with a saturating function of it:

score(q, d) = Σ over terms t: idf(t) · (tf · (k₁ + 1)) / (tf + k₁ · (1 − b + b · dl / avgdl))

Two constants do the work, and both ship with the same defaults in Lucene and Elasticsearch: k₁ = 1.2 and b = 0.75.

k₁ controls saturation. Ignore length for a moment and the term factor is tf · (k₁ + 1) / (tf + k₁), which rises steeply and then flattens against a hard ceiling of k₁ + 1 = 2.2:

Two mentions already collect 62.5% of everything the term can ever contribute, and the fiftieth mention adds essentially nothing. The raw counts of D3 and D1 differ by 25×; their BM25 term factors differ by 1.5625×. That single curve is why keyword stuffing stopped working.

b controls length normalisation. With average document length 90 in our collection, the denominator picks up k₁ · (1 − b + b · dl/avgdl): 0.4 for the 10-word D1, 2.3 for the 200-word D2. A long document has more chances to contain the query terms by accident, so its counts are discounted in proportion to how much longer than average it is. At b = 0 the normalisation is switched off entirely; at b = 1 it is fully proportional.

Scoring all five documents with k₁ = 1.2 and b = 0.75:

The spam page has fallen from first to fourth. And length normalisation is doing something visible on its own: switching b from 0 to 0.75 lifts the short honest review D1 from 0.9346 to 1.3744, moving it past D5 into second place, because ten words that mention both query terms is a denser signal than eighty words that mention one.

Look at what BM25 still gets wrong, though. D5 — an article about washing machines, containing the word espresso zero times — outscores D3 and D4. BM25 is a bag of words: it has no notion that espresso machine is a phrase, no notion that a machine can be a washing machine, and no way to know that D5 is about laundry. That specific blindness is the reason dense retrieval over embeddings exists, and the reason production systems now run both.

Find out whether any of it worked

Cleverdon's Cranfield experiments established the format still used today: a test collection of documents, a set of queries, and human relevance judgements for query–document pairs. The surviving Cranfield collection holds 1,400 aerodynamics abstracts and 225 queries, and — a detail worth noticing — its judgements were already graded on five levels rather than relevant/not-relevant. NIST's TREC has run the same paradigm at industrial scale since 1992, co-sponsored with the US Department of Defense, and every retrieval benchmark since is a variation on it.

Take one query with 6 relevant documents in the collection, and a system that returns these ten results with these graded relevance judgements:

Precision@k is the fraction of the top k that is relevant. P@5 = 3/5 = 0.6000; P@10 = 4/10 = 0.4000. It says nothing about what you missed.

Recall is the fraction of all relevant documents you found: 4 of 6 = 0.6667. It says nothing about the junk you returned alongside them. This is the trade in its sharpest form — return the whole million-document collection and recall becomes 1.0 while precision becomes 0.000006. You bought a 1.5× improvement in recall by making precision 66,667× worse, which is why nobody reports either number alone.

Reciprocal rank is 1 divided by the position of the first relevant result: the first hit is at rank 2, so RR = 0.5000. Averaged over queries it becomes MRR, and it is the right metric when the user needs one answer and will not scroll — navigational search, question answering, the retrieval step feeding a chatbot.

Average precision rewards getting relevant documents early. Compute precision at each rank where a relevant document appears — 1/2, 2/3, 3/5, 4/8 = 0.5000, 0.6667, 0.6000, 0.5000 — sum them to 2.2667 and divide by the number of relevant documents in the collection, which is 6, not by the 4 you found. AP = 0.3778. Dividing by the number found instead of the number that exists is the single most common error in hand-rolled evaluation code, and it inflates the score by 50% here. Averaged over a query set, AP becomes MAP.

nDCG is the one that handles graded relevance, from Kalervo Järvelin and Jaana Kekäläinen's 2002 paper in ACM TOIS. Each result contributes a gain of 2^grade − 1, divided by a discount of log₂(rank + 1):

• rank 2, grade 3: 7 / log₂(3) = 7 / 1.5850 = 4.4165
• rank 3, grade 2: 3 / log₂(4) = 3 / 2.0000 = 1.5000
• rank 5, grade 3: 7 / log₂(6) = 7 / 2.5850 = 2.7080
• rank 8, grade 1: 1 / log₂(9) = 1 / 3.1699 = 0.3155

DCG@10 = 8.9399. The same six documents perfectly ordered (3, 3, 2, 1, 1, 1) give IDCG@10 = 7.0000 + 4.4165 + 1.5000 + 0.4307 + 0.3869 + 0.3562 = 14.0902, so nDCG@10 = 8.9399 / 14.0902 = 0.6345. The normalisation is what makes nDCG comparable across queries: a query with twenty relevant documents and one with two both land on a 0-to-1 scale.

The five numbers describe the same ranked list and disagree with each other — 0.6000, 0.6667, 0.5000, 0.3778, 0.6345. None is wrong. They answer different questions, and which one you optimise is a product decision, not a technical one.

Types

Four families of retrieval model, in the order the field invented them.

Boolean retrieval treats the query as a logical expression over the index — espresso AND machine NOT washing — and returns the matching set, unranked. It is exact, auditable and still mandatory in legal e-discovery and patent search, where a lawyer must be able to state precisely which documents were and were not examined. Its failure is that it has no notion of better: a query matching 40,000 documents returns 40,000 documents in no useful order, and tightening it until the set is readable usually throws away the answer.

The vector space model (Gerard Salton's SMART system) represents documents and queries as weighted term vectors and ranks by cosine similarity, which is where TF-IDF lives. It gave the field ranking, and gave it the geometry that embeddings still use — but its weights are heuristic, chosen because they behaved well rather than derived from anything.

Probabilistic retrieval asks a sharper question: what is the probability this document is relevant to this query? Robertson and Spärck Jones's 1976 relevance weighting model answers it, and BM25 is the practical scoring function that fell out of that line of work. It is still the production default.

Learned dense retrieval replaces term matching entirely, encoding query and document into vectors with a trained neural network and retrieving by nearest-neighbour search. It finds paraphrases that share no vocabulary, which BM25 structurally cannot. The trade-off is measured below: it must be trained on data resembling what it will see, it needs an index one to two orders of magnitude larger, and it degrades on out-of-domain collections in a way BM25 does not.

The honest summary is that these are not four generations with the newest winning. Production retrieval today is usually BM25 and dense retrieval, fused, with a reranker on top — a pattern semantic search covers in detail.

Real-World Applications

Every Elasticsearch and OpenSearch deployment on earth. BM25 is Elasticsearch's default similarity, with k₁ = 1.2 and b = 0.75 as shipped defaults — which means the arithmetic worked above is, unmodified, what ranks results in a very large share of the world's site search, log search and internal document search. Relevance tuning in these systems is largely the act of changing those two constants and the per-field boosts around them.

The first stage of most RAG pipelines. A retrieval-augmented generation system that retrieves the wrong passages cannot be rescued by a better language model, and the failure is invisible unless you measure retrieval separately. Teams that instrument recall@k and nDCG@10 on their own labelled query set find the fix; teams that only look at final answer quality debug the wrong component for weeks.

Reranking, as the standard second stage. Retrieve a few hundred candidates cheaply with BM25 or a dense index, then rescore the survivors with a cross-encoder that reads query and document together. The BEIR study measured exactly this configuration as the best-generalising system it tested, at a computational cost that makes it viable only over a shortlist.

Biomedical and legal search. PubMed and Google Scholar are IR systems where recall carries legal or clinical weight — a systematic review that misses a trial is a defective review — so their interfaces still expose Boolean operators and field restrictions rather than hiding everything behind a relevance model.

Benchmarking retrieval itself. BEIR (Thakur et al., NeurIPS 2021 Datasets and Benchmarks) assembled 18 datasets across 9 task types to test how retrievers transfer to domains they were not trained on, and the results are the best available evidence on whether neural retrieval has replaced the classical stack. It has not. Averaged over the 18 zero-shot datasets, relative to BM25 in nDCG@10: DPR scored −47.7%, ANCE −7.4%, TAS-B −2.8%, docT5query +1.6%, ColBERT +2.5%, and BM25 with a cross-encoder reranker +11%. Counted per dataset, ColBERT beat BM25 on 9 of 18 and the reranker on 16 of 18. The paper's own framing is the part worth keeping: "We observe BM25 heavily underperforms neural approaches by 7-18 points on in-domain MS MARCO. However, BEIR reveals it to be a strong baseline for generalization."

That result is routinely overstated in both directions. It does not say BM25 wins — two of the tested neural systems beat it, and the reranked configuration beat it comfortably. It says that a dense retriever's in-domain score predicts almost nothing about its out-of-domain score, and that the classical baseline is where you start rather than what you replace. The numbers are from 2021 and the specific models have been superseded; the structural finding has not been.

Key Concepts

• The candidate set is chosen before the ranking is. A document that never enters the top few hundred cannot be recovered by any reranker, so first-stage recall is the ceiling on everything downstream. This is why hybrid retrieval is standard: two different recall failures are less correlated than one.
• Relevance judgements are the expensive part, not the model. A test collection needs humans to read query–document pairs, and the pool is built from what existing systems returned — so a genuinely novel retriever surfaces documents nobody judged, and gets scored as if they were irrelevant. BEIR measured this directly as a "hole rate": 1.6% of the reranker's top-10 hits were unjudged against 31.8% of TAS-B's.
• Query length changes which technique wins. Two-keyword queries carry almost no signal for a semantic model to work with and reward exact term matching; a full-sentence question rewards a model that can match on meaning. A single retrieval strategy for both traffic types is a compromise, not a design.
• @k is not a detail. Precision@10 and precision@100 on the same system can differ by a factor of five, and nDCG@10 rewards ordering inside the top ten while recall@100 does not care about ordering at all. Any retrieval number without its k is uninterpretable.

Challenges

The vocabulary mismatch is the field's oldest unsolved problem. A user searching "car won't start" needs a document titled "vehicle ignition failure diagnosis", and no amount of term weighting connects them, because they share nothing to weight. Query expansion, synonym dictionaries and dense retrieval are three attempts at the same gap, and each introduces its own error: expansion drags in noise, dictionaries need maintenance, and dense retrieval hallucinates similarity where there is none. The D5 washing-machine result above is this failure running in the other direction — shared vocabulary, unshared meaning.

Evaluation depends on judgements that go stale and were never complete. Nobody labels every document in a collection against every query; TREC-style pooling judges only the top hits of the systems that competed. A retriever that finds something genuinely new gets penalised for it. And relevance is not a property of a document — it is a property of a document, a user, and a moment, which is why offline nDCG improvements so often fail to reproduce in an online A/B test.

The metrics can be optimised apart from the goal. nDCG@10 rewards putting the best documents first, and a system trained hard on it will learn the annotators' habits, including their preference for documents that look like the ones they usually see. Generative engine optimization is the same dynamic on the content side, with publishers now writing for the retriever rather than the reader.

Cost scales with the technique, not with the collection. BM25 over 15 million documents was an 18 GB index in the BEIR measurements; late-interaction retrieval over the same documents was about 900 GB. The choice between them is very often a budget decision dressed as a quality decision, and the honest comparison is nDCG per gigabyte of index rather than nDCG alone.

Future Trends

Retrieval is being pulled into the model's inner loop. Instead of one query producing one ranked list, an agent issues several searches, reads what came back, and searches again with what it learned — which breaks the single-shot evaluation frame entirely, because the thing to measure is now whether the session found the answer, not whether ranking three was well ordered. Nobody has a settled metric for that, and it is the most interesting open problem in IR evaluation.

The other direction is that BM25 keeps getting extended rather than retired: learned sparse retrieval trains a neural network to predict term weights into an inverted index, keeping the index structure, the exact-match guarantees and the interpretability while learning the weighting from data instead of deriving it from document frequency. That line of work describes where the field is heading better than "neural replaces lexical" does — the classical machinery is turning out to be a substrate, not a legacy.

Code Example

The five metrics above, computed on the same ranked list, in twenty lines with no dependencies. The point is how little code the field's entire evaluation vocabulary takes, and how much of it hinges on one detail — dividing average precision by the number of relevant documents that exist, not the number you found.

import math

grades = [0, 3, 2, 0, 3, 0, 0, 1, 0, 0]   # graded relevance of the ranked top 10
ideal  = [3, 3, 2, 1, 1, 1]               # every relevant doc in the collection
rel    = [1 if g else 0 for g in grades]  # binary view, for the set metrics
R      = len(ideal)

p_at = lambda k: sum(rel[:k]) / k
dcg  = lambda gs: sum((2 ** g - 1) / math.log2(i + 2) for i, g in enumerate(gs))

precision5 = p_at(5)
recall10   = sum(rel) / R
rr         = next(1 / (i + 1) for i, r in enumerate(rel) if r)
ap         = sum(p_at(i + 1) for i, r in enumerate(rel) if r) / R
ndcg10     = dcg(grades) / dcg(sorted(ideal, reverse=True))

print(f"precision@5 {precision5:.4f}   3 of the top 5 are relevant")
print(f"recall@10   {recall10:.4f}   4 of the 6 relevant docs were found")
print(f"MRR         {rr:.4f}   first relevant result sits at rank 2")
print(f"AP          {ap:.4f}   4 precision values / 6, not / 4")
print(f"nDCG@10     {ndcg10:.4f}   {dcg(grades):.4f} / {dcg(sorted(ideal, reverse=True)):.4f}")

Output:

precision@5 0.6000   3 of the top 5 are relevant
recall@10   0.6667   4 of the 6 relevant docs were found
MRR         0.5000   first relevant result sits at rank 2
AP          0.3778   4 precision values / 6, not / 4
nDCG@10     0.6345   8.9399 / 14.0902

Change R = len(ideal) to R = sum(rel) and AP jumps from 0.3778 to 0.5667 — a 50% improvement that comes from nowhere and cannot be reproduced by anyone using the standard definition. Before comparing your numbers to a published result, check which convention the published number used.