Information retrieval

The matching problem

A retrieval system has four parts, and every design decision lives in one of them.

Representation. Documents are reduced to something a machine can compare: index terms, a vector of term weights, an embedding. Whatever is dropped here is unfindable later. The classic data structure is the inverted index, a table from each term to the list of documents containing it, which is why a search over millions of documents answers in milliseconds.

The query. A need, compressed into a few words or a sentence. The compression loses information. Robert Taylor’s 1968 study of reference interviews named the result the compromised question: of the four forms a need passes through, the one that reaches the system is the last and least faithful.

Matching. Deciding which representations correspond to the query. Boolean matching returns the set of documents that satisfy a logical expression. Ranked matching scores every document and sorts.

Relevance. The thing the whole system approximates: whether a document meets the need. Relevance is judged by a person, against the need behind the query, and it changes as the person learns. Every retrieval model is a hypothesis about what correlates with it.

Calvin Mooers, who coined the term “information retrieval” in 1950, stated the law that governs adoption in 1959: an information retrieval system will tend not to be used whenever it is more painful and troublesome for a customer to have information than not to have it. He meant the burden of the information itself. The engineering reading is narrower and holds anyway. A system that returns the right document at rank forty has, as far as its user is concerned, not retrieved it.

Where it came from

Retrieval became a field when technical report collections outgrew subject catalogues. In the early 1950s Mortimer Taube’s Uniterm system kept one card per keyword listing the documents that carried it, and answered a query by comparing cards: Boolean retrieval done by hand. Hans Peter Luhn at IBM showed in 1957 and 1958 that word frequency could stand in for the human indexer: terms that occurred often in a document but not across the collection were good descriptors, and a machine could count them.

The Cranfield experiments tested the assumption under the whole catalogue tradition. Cranfield II (1962 to 1966) compared 33 indexing languages over about 1,400 aeronautics papers and 221 queries with human relevance judgments, and single natural-language terms came out ahead of the controlled vocabularies. The result was contested for years and has held. It also fixed the method every retrieval system has been evaluated with since: a collection, a query set, and judgments.

Gerard Salton’s SMART project at Harvard and then Cornell turned documents and queries into weighted term vectors and ranked by the cosine between them. Karen Spärck Jones showed in 1972 that weighting a term by the inverse of the number of documents containing it, inverse document frequency, improved ranking across collections; multiplied by Luhn’s within-document frequency it became tf-idf. Stephen Robertson and Spärck Jones put term weighting on a probabilistic footing in 1976, and that line of work produced BM25 in Robertson and Walker’s Okapi system for TREC-3 in 1994. Lucene made BM25 its default scoring function in 2016, so it is the ranking inside most keyword search today.

The web changed the scale and the signals. Brin and Page’s PageRank (1998) scored pages by the structure of links between them, evidence from outside the text. In the 2000s ranking became a function learned from human judgments over hundreds of such features; Burges and colleagues’ RankNet (2005) is the usual starting point. From 2018 transformer models made it practical to embed queries and documents as dense vectors, so that a question and a passage with no words in common could still score high. Google reported using BERT in ranking in 2019, and dense passage retrieval (Karpukhin and colleagues, 2020) beat BM25 on open-domain question answering. Retrieval-augmented generation, named in a 2020 paper by Lewis and colleagues, put a generative model at the end of a pipeline the TREC question answering track had been running since 1999, with an extraction model where the generator now sits.

Three models that still run everything

Every production system uses some combination of three retrieval models, and each fails in a characteristic way.

Boolean. A document matches or it does not. Boolean retrieval is exact and explainable, and it is the right tool for filters: documents of this type, from this source, after this date. It has no notion of a better or worse match, so used alone it returns either too much or nothing.

Lexical ranking. Documents and queries as weighted term vectors, scored by tf-idf or BM25. It needs no training and it rewards exact vocabulary, which is why it still wins on names, codes, error strings, and rare technical terms. It fails when the user and the document say the same thing in different words.

Dense retrieval. Documents and queries as embeddings from a trained model, scored by similarity. It finds paraphrases and related concepts that share no words. It fails on exact identifiers, on vocabulary the model has not seen, and on identity: two documents about different entities with the same shape sit close together, which is the authority-control problem the Knowledge organization page describes.

The field’s answer to these failure modes predates dense retrieval: combine the evidence. Fox and Shaw showed at TREC-2 in 1994 that summing the scores of several retrieval runs beat the best single run, and Cormack, Clarke, and Büttcher’s reciprocal rank fusion (2009) is the version most pipelines use. A production system filters with Boolean conditions, fuses lexical and dense scores, and reranks the top candidates with a cross-encoder, which Nogueira and Cho demonstrated with BERT in 2019. Hybrid retrieval is a thirty-year-old design with better parts.

Principles that have survived

Indexing is a decision, and chunking is indexing. What you choose to represent determines what you can retrieve. Splitting documents into passages is an indexing policy with a literature: Salton, Allan, and Buckley tested passage retrieval in 1993, and Kaszkiel and Zobel’s 1997 study found fixed-length overlapping windows of a few hundred words performed as well as or better than splitting on the author’s own paragraphs and sections. The right unit depends on the questions the system is asked, not on a token limit.

Rare terms carry the signal. Spärck Jones’s 1972 observation is the simplest idea in the field that still works: a term that appears everywhere tells you nothing about which document to return. Every weighting scheme since encodes some form of it.

Relevance belongs to the need. Two users typing the same words can want different documents. The field has distinguished since the 1970s between system relevance, what the ranking function computes, and user relevance, what the person judges; Tefko Saracevic’s 1975 review in JASIS is the standard statement. A system that learns nothing about the need beyond the query string is working from the compromised question.

Ranking beats matching. A set of matches has no order, and the user reads in order. Joachims and colleagues’ 2005 eye-tracking studies of web search found attention concentrated on the first two results and falling off fast below them. Whatever sits at rank twenty might as well have been dropped at indexing.

Feedback improves retrieval. Rocchio’s 1965 method moved the query vector toward the documents a user judged relevant. It is the ancestor of query expansion, of pseudo-relevance feedback, and of the “fan-out” that AI search systems perform when they rewrite one question into several.

Why it matters for AI

Retrieval-augmented generation is a retrieval system with a reader on the end. The reader is a language model, and it is very good at producing a fluent answer from whatever it is handed. That is the problem. If retrieval returns the wrong passages, the answer will be fluent and wrong, and nothing in the output will say so.

Most quality problems in these systems are therefore retrieval problems, and the field has a method for each. A system that misses documents using different vocabulary needs lexical and dense retrieval fused. A system that confuses entities needs Boolean filters on metadata, which needs the metadata to exist. A system that returns the right document and the wrong passage has a chunking policy problem. A system whose answers degrade as the collection grows has a ranking problem. A system that nobody can say is getting better or worse has no test collection, which the next page covers.

The field also explains what a model cannot fix. A model cannot retrieve a document that was never indexed, cannot recover a field that was dropped at representation, and cannot tell that the passage it was given is about the wrong customer. Those are decided before the model runs, by people, in the design of the index.

Common questions

Is vector search information retrieval? Yes. Dense retrieval is one retrieval model among several, evaluated with the same test collections and measures. Teams that take it for the whole field tend to rediscover BM25 in their second quarter.

Do I still need keyword search if I have embeddings? Almost always. Exact identifiers, product codes, error messages, and names are where lexical ranking wins, and on the BEIR benchmark (2021), eighteen collections the retrievers had not been trained on, BM25 beat most of the dense models tested. Fusing the two beats either.

What is the difference between search and retrieval? None in the technical sense. “Search” is what users do; “retrieval” is what the system does, and the name of the discipline.

Where to go next

The AI Architecture topic places retrieval in the stack and covers the pipeline around it. Evaluation and relevance, the next Foundations page, covers how to tell whether a retrieval system is working.

• AI Architecture
• Knowledge Graphs