Information retrieval: inverted indexes, term weighting and ranking

A query typed into a search box is answered by an inference the engine never shows. The engine decides which documents are more likely to answer the query, orders them and cuts the list, and for a screen reader user that order is the main cue. This lecture argues that the ranking is a probabilistic inference about which document answers a query. It argues that a term's weight estimates how much the term changes the odds of relevance rather than a knob turned by taste. It also argues that the estimate is validated only against a collection for which somebody has judged what counts as relevant.

This seventh unit turns from storing to finding. The inverted index makes the estimate affordable, term weighting supplies its parameters, and the judged collection decides whether they were right.

A scan becomes a lookup

Zobel and Moffat (2006) give the machinery: their tutorial covers index storage, construction and query evaluation across the family of index representations built for text search engines. Because the index records, for each term, the documents containing it, matching a query becomes a dictionary lookup and a merge of postings lists rather than a read of every document. Manning, Raghavan and Schutze (2008) place the same structure at the centre of their textbook, which teaches indexing, weighting, ranking and evaluation as one sequence. The index lets a collection of any size be ranked at interactive speed. It also fixes what a ranker can compute: only what a postings list exposes.

Weighting as an estimate of how much a term changes the odds

Sparck Jones (1972) is the origin of this argument. She proposed that the specificity of an index term be read statistically, as a function of how often the term is used rather than what it means, and she tested it on three collections. Frequent terms are still required for good overall performance, while matches on rarer terms should count for more, which she expressed by weighting terms by collection frequency. The simple procedure improved retrieval considerably, and it is the origin of inverse document frequency.

The mechanism can be worked through with arithmetic. In a collection of a thousand documents, a term appearing in five hundred of them carries a weight of about 0.3 under the usual logarithmic form. A term appearing in one carries about 3. A match on the rare term therefore moves the odds roughly ten times as much as a match on the common one. The postings list for the rare term is a handful of entries while the list for the common term is half the collection. The arithmetic illustrates the weighting rule and is not an effectiveness result. Whether the extra weight helps depends on the judgements of the collection, which the next unit takes up.

Robertson and Jones (1976) moved the idea from heuristic to derivation. They derived a series of relevance weighting functions from a general probabilistic theory of retrieval and illustrated them on test collections. A weight is no longer a score somebody chose but the term's estimated contribution to the odds a document is relevant. Robertson and Zaragoza (2009) present that probabilistic relevance framework and show it accounting for document structure and links in BM25F. The ranking functions search engines implement are one premise worked out, not rival intuitions.

One probabilistic premise, read in two ways

The premise can be read more than one way, and the disagreement is instructive. Ponte and Croft (1998) rank a document by the likelihood that the query would be generated by a language model estimated from that document. Their route differs from that of BM25, yet it makes the same claim: a rank is a probability depending on a model with parameters. Zhai and Lafferty (2004) show what that costs. Studying smoothing, the adjustment of the maximum-likelihood estimator for data sparseness, they establish that how a document's model is smoothed decides the ranking. A ranker is therefore a model, and its choices must be justified rather than felt.

Weighting generalises from terms to learned representations

Deerwester and colleagues (1990) introduced latent semantic analysis, which applies singular value decomposition to a term-by-document matrix to represent documents by about one hundred orthogonal factors. It retrieves them by that inferred structure rather than by literal terms, so the weights now index a learned space rather than a dictionary. Karpukhin and colleagues (2020) take the move to its conclusion with dense passage retrieval. They learn embeddings with a dual encoder so that retrieval can use dense representations instead of term matching. Their retriever outperformed a strong Lucene BM25 system largely by nine to nineteen points of absolute top-20 accuracy. Formal, Piwowarski and Clinchant (2021) show the older structure surviving, since SPLADE learns sparse representations under explicit sparsity regularisation. It retains exact term matching and inverted-index efficiency while adding expansion.

The tie that binds, and the judgement it rests on

None of this decides whether a ranking is any good, which is where the argument turns back on itself. Manning, Raghavan and Schutze (2008) define the measures the field uses. Recall is the fraction of relevant items retrieved. Precision is the fraction of retrieved items that are relevant. The F measure combines them, and mean average precision summarises a ranked list. They also describe how those judgements are obtained, through pooling, where assessors judge only the documents the systems under test already returned, so something unpooled cannot be credited. Relevance, on that account, is a judgement a person makes about a document at a moment, not a property it carries. Thakur and colleagues (2021) turn the problem into a benchmark: eighteen public datasets and ten lexical, sparse, dense, late-interaction and re-ranking systems. Their result is uncomfortable for any single-family claim. BM25 is a robust baseline, re-ranking and late-interaction models lead the zero-shot average at high cost, and dense and sparse models, though cheaper, often underperform. A ranking that does not generalise beyond the collection it was fitted to is not a ranking that works.

Contested question: does the model decide, or the collection?

The literature disagrees about what determines a ranking.

The first position holds that within a family the model choice barely matters. Kamphuis and colleagues (2020) ran a large-scale reproducibility study of eight BM25 variants, including the Lucene implementation practitioners usually mean, on three newswire collections. They found no significant effectiveness differences between them. If the details a reader is taught to tune do not decide the outcome, the weight is not finely calibrated but coarse.

The second position holds that the model matters greatly once the family changes. Karpukhin and colleagues (2020) report a dense retriever beating a strong BM25 system by nine to nineteen points of top-20 accuracy. Thakur and colleagues (2021) find systematic differences across the four families on the same benchmark. The ranking is then a property of the modelling assumptions, not a broad plateau of equivalent weights.

The third position, which this lecture defends, holds that both findings are about the collection. The model families separate because they make different assumptions about how a term changes the odds. The BM25 variants fail to separate because they share one assumption, differing only in how it is approximated. What varies is not taste but the estimand, measured against judgements made on a particular collection. Kamphuis and colleagues found no difference on three newswire collections, a statement about those collections as much as about the variants. The zero-shot design of Thakur and colleagues exists because a result on one collection does not transfer.

What would settle it is an evaluation that varies the model family and the collection independently. It would report effectiveness alongside the judgements and pooling depth behind it. It would also show whether an advantage survives on collections never used to fit it. Thakur and colleagues (2021) come closest, and their benchmark still inherits whatever its eighteen datasets' pooled judgements omit.

Rate each side by its evidence. Kamphuis and colleagues (2020) report one family measured on three collections, a result that holds inside that family. Karpukhin and colleagues (2020) and Thakur and colleagues (2021) measure across families, on benchmarks whose judgements are pooled. The strongest objection is that the model families were built on the collections, so a benchmark cannot be the neutral instrument an independent design needs. While the dispute is open, a designer reports which judgements a score was computed against before comparing two rankers.

Where the argument is heading

Formal and colleagues (2021) show the inverted index being kept rather than abandoned, and Karpukhin and colleagues (2020) show what is gained when term matching is not relied on alone. Lin, Nogueira and Yates (2022) give a monograph account of the pretrained transformer models that now rank text, and Li and colleagues (2025) survey the step beyond matching, in which a model generates the document identifier or the answer instead of scoring a candidate list. The open question is the one the contested section raises: whether a judged collection can stand for the queries a deployed system will receive. Thakur and colleagues (2021) try to widen that collection, and the pooling problem Manning, Raghavan and Schutze (2008) describe is why it remains hard.

The sources this unit rests on

• Deerwester, S., Dumais, S. T., Furnas, G. W. et al. (1990). Indexing by latent semantic analysis. Journal of the American Society for Information Science. The authors use singular value decomposition of a term-by-document matrix to represent documents by about one hundred orthogonal factors and retrieve them by that structure rather than by literal terms.
• Formal, T., Piwowarski, B. and Clinchant, S. (2021). SPLADE: sparse lexical and expansion model for first stage ranking. Proceedings of the 44th International ACM SIGIR Conference. The authors present a first-stage ranker that learns sparse representations under explicit sparsity regularisation, keeping exact term matching and inverted-index efficiency.
• Kamphuis, C., de Vries, A. P., Boytsov, L. et al. (2020). Which BM25 do you mean? A large-scale reproducibility study of scoring variants. Lecture Notes in Computer Science. The authors compare eight BM25 variants, including the Lucene implementation practitioners usually mean, on three newswire collections, and find no significant effectiveness differences. It carries the unit's strongest counter-evidence: what a reader is taught to tune may not decide the outcome.
• Karpukhin, V., Oguz, B., Min, S. et al. (2020). Dense passage retrieval for open-domain question answering. Proceedings of EMNLP 2020. Dense passage embeddings are learned with a dual encoder so retrieval can use dense representations instead of term matching, and the retriever outperforms a strong Lucene BM25 system largely by nine to nineteen points of top-20 accuracy. It marks the point where matching stops being a lookup on terms.
• Li, X., Jin, J., Zhou, Y. et al. (2025). From matching to generation: a survey on generative information retrieval. ACM Transactions on Information Systems. Surveys retrieval in which a model generates a document identifier or an answer rather than scoring a candidate list. It names the paradigm that follows the learned-representation line rather than replacing it, and collects reported results rather than running its own comparison.
• Lin, J., Nogueira, R. and Yates, A. (2022). Pretrained transformers for text ranking: BERT and beyond. Synthesis Lectures on Human Language Technologies. This monograph covers pretrained transformer models for text ranking, grouped into reranking inside multi-stage architectures and dense retrieval that ranks directly; the publisher's description was read, and the chapters sit behind a subscription. It consolidates the neural ranking literature.
• Manning, C. D., Raghavan, P. and Schutze, H. (2008). Introduction to Information Retrieval. Cambridge University Press. The standard textbook teaches indexing, weighting, ranking and evaluation as one sequence, and defines precision, recall, the F measure and mean average precision. It supplies the argument's definitions and describes pooling, so a relevance score is only as good as the judgements behind it.
• Ponte, J. M. and Croft, W. B. (1998). A language modelling approach to information retrieval. Proceedings of SIGIR '98 (the original title spells the term in the American form; it is rendered here in the house British spelling). Ponte and Croft rank documents by the likelihood that the query would be generated by a language model estimated from each document. The ranking comes by a second theoretical route, so it supports reading the ranker as a probability statement.
• Robertson, S. E. and Jones, K. S. (1976). Relevance weighting of search terms. Journal of the American Society for Information Science. The authors derive a series of relevance weighting functions from a general probabilistic theory of retrieval and illustrate them on test collections. It recasts weighting as inference about relevance, the premise BM25 formalises.
• Robertson, S. and Zaragoza, H. (2009). The probabilistic relevance framework: BM25 and beyond. Foundations and Trends in Information Retrieval. The authors present the probabilistic relevance framework that led to BM25 and show it accounting for structure and link information in BM25F. It shows the ranking functions search engines implement are one premise worked out.
• Sparck Jones, K. (1972). A statistical interpretation of term specificity and its application in retrieval. Journal of Documentation. Sparck Jones argues that the specificity of an index term should be read statistically, as a function of how often it is used rather than what it means, and reports experiments on three test collections. Her finding, that frequent terms are still needed overall while rarer ones count for more, is the origin of inverse document frequency.
• Thakur, N., Reimers, N., Ruckle, A. et al. (2021). BEIR: a heterogeneous benchmark for zero-shot evaluation of information retrieval models. Proceedings of the NeurIPS Track on Datasets and Benchmarks. The authors evaluate ten lexical, sparse, dense, late-interaction and re-ranking systems on eighteen datasets; BM25 is a robust baseline, re-ranking and late-interaction models lead at high cost, and dense and sparse models often underperform. It carries the generalisation question into the neural era.
• Zhai, C. and Lafferty, J. (2004). A study of smoothing methods for language models applied to information retrieval. ACM Transactions on Information Systems. The authors study smoothing, the adjustment of the maximum-likelihood estimator for data sparseness, and examine how sensitive retrieval performance is to the smoothing parameters. It establishes that how a document's model is smoothed decides the ranking.
• Zobel, J. and Moffat, A. (2006). Inverted files for text search engines. ACM Computing Surveys. Zobel and Moffat give a tutorial on the inverted index and the index representations built for text search engines, covering index storage, construction and query evaluation.