Information Retrieval and Retrieval-Augmented Generation

Information needs that can be met with facts expressed in short texts, e.g. “Where is the Louvre Museum located?”.

By conditional generation from the question: it has seen the facts in pretraining. Such factual knowledge seems to be stored in the large feedforward layers of the transformer.

A response that is not faithful to the facts of the world: the model makes up a reasonable-sounding answer. LLMs sometimes do this even when the correct facts are stored in their parameters, apparently when the feedforward layers fail to recall them.

Its confidence in an answer correlates highly with the probability that the answer is correct. A calibrated system could hedge when likely wrong; LLMs are poorly calibrated and often give wrong answers with complete certainty.

Hallucination (often wrong, hard to detect), no access to proprietary data (personal email, medical records, company documents), and static knowledge (no information after the model was trained).

Using information retrieval to fetch documents likely to contain relevant information, then having an LLM generate an answer conditioned on those documents and the question.

Answers are based on facts from a curated collection, can be shown together with their source passages (so users can check them), and retrieval works over any proprietary data.

A user poses a query to a retrieval system, which returns an ordered set of documents from some collection.

A document is whatever unit of text is indexed and retrieved (web page, paper, passage). A collection is the set of documents used to satisfy requests (possibly the whole web). A term is a word (or phrase) in the collection. A query is a user’s information need expressed as a set of terms.

Sparse retrieval, representing queries and documents as word-count vectors weighted by tf-idf or BM25, and dense retrieval, representing them as embeddings computed by language models.

A document is represented as a vector of counts of the words it contains (Salton, 1971). Bag of words: treat the document as an unordered set of words, ignoring positions and keeping only frequencies.

A matrix with a row per vocabulary word and a column per document; each cell counts how often the word occurs in the document. Each document is a column vector.

Similar documents have similar words, so their column vectors are similar: Shakespeare’s comedies have many fool and wit, few battle, unlike the histories.

Raw counts overweight frequent words and ignore how discriminative a word is; tf-idf and BM25 weight terms by frequency in the document and rarity across the collection.

Log-scaled count: \(\text{tf}_{t,d} = 1 + \log_{10}\text{count}(t, d)\) if the count is positive, else 0. A word occurring 100 times isn’t 100 times more relevant (tf goes 1, 2, 3, 4 for counts 1, 10, 100, 1000).

\(\text{df}_t\) is the number of documents containing term \(t\). \(\text{idf}_t = \log_{10}\frac{N}{\text{df}_t}\) for \(N\) documents: high for terms in few documents, 0 for terms in every document.

Terms that occur in only a few documents discriminate those documents from the rest; terms that occur everywhere (good, sweet in Shakespeare) aren’t helpful.

\(\text{tf-idf}(t, d) = \text{tf}_{t,d} \cdot \text{idf}_t\).

By the cosine between their tf-idf vectors, \(\text{score}(q, d) = \frac{q \cdot d}{|q||d|}\), assuming documents with words similar to the query are more relevant. Only terms in both contribute to the dot product.

The first document contains both query terms (sweet twice), while the second lacks love, which has the higher idf; its tf-idf cosine is much higher (≈ .75 vs ≈ .08).

Dropping the idf term for the document (keeping it only for the query), which sometimes performs better.

A tf-idf variant (Okapi BM25): \(\sum_{t \in q}\log\frac{N}{\text{df}_t}\cdot\frac{\text{tf}_{t,d}}{k\big(1 - b + b\frac{|d|}{|d_{avg}|}\big) + \text{tf}_{t,d}}\). Parameter \(k\) balances term frequency against idf; \(b\) controls document-length normalization.

\(k = 0\): no term frequency, just binary presence (plus idf); large \(k\): raw term frequency. \(b = 1\): full scaling by document length; \(b = 0\): no length scaling. Typical: \(k\) in [1.2, 2], \(b = 0.75\).

A list of high-frequency (mostly function) words removed from queries and documents. It makes phrase search hard (“to be or not to be” → “not”), and idf already downweights such words, so modern IR rarely uses it.

The data structure for finding documents containing query terms: a dictionary of terms (with document frequencies) each pointing to a postings list of document IDs, optionally with counts or positions.

love  {2} → 1 [1] → 3 [1]
nurse {2} → 1 [1] → 4 [1]
sweet {3} → 1 [2] → 2 [1] → 3 [1]

Format: term {document frequency} → doc id [count in doc] → …

Indexing: build an inverted index over the collection. Retrieval: use it to find candidate documents containing query terms, score each by tf-idf or BM25 cosine with the query, sort by score, and return the top N.

Precision = relevant returned / all returned (\(|R|/|T|\)). Recall = relevant returned / all relevant documents in the collection (\(|R|/|U|\)).

They ignore order: we want metrics that prefer systems ranking relevant documents higher.

Precision\(_k\) = relevant documents in top \(k\) / \(k\); Recall\(_k\) = relevant documents in top \(k\) / total relevant documents.

Recall never decreases (it rises at each relevant document); precision jumps up at relevant documents and down otherwise. They are plotted as a precision-recall curve.

Precision at recall level \(r\) is set to the maximum precision at any recall ≥ \(r\): \(\text{IntPrecision}(r) = \max_{i \ge r}\text{Precision}(i)\). It allows averaging over queries at 11 standard recall levels (0, .1, …, 1) and smooths the curve, giving systems the benefit of the doubt.

Higher precision at all recall levels is better; systems high on the left favor precision, those high on the right favor recall.

AP: average of the precision values measured at the ranks where relevant documents occur, \(\frac{1}{|R_r|}\sum_{d \in R_r}\text{Precision}_r(d)\). MAP: the mean of AP over a set of queries.

Precisions at those ranks: 1/1, 2/3, 3/4. AP = (1 + .667 + .75)/3 ≈ .81.

Sparse methods like tf-idf and BM25 only work when query and document share exact words, so the user must guess the words the answer’s writer used. Dense embeddings handle synonymy and solve this.

Feed both to one encoder, “query [SEP] document”, so self-attention sees all tokens of both, then a linear layer on the [CLS] output predicts a relevance score. Documents are usually split into passages (e.g. ~100-token chunks) to fit the window.

Every new query would require running every document in the collection through the encoder jointly with it, which is far too expensive; it is used only for reranking.

Separate encoders for queries and documents: each document is encoded once in advance (e.g. its [CLS] vector) and stored; a new query is encoded and scored against all documents by dot product, \(\text{score} = z_q \cdot z_d\).

Its relevance decision can’t exploit interactions between query tokens and document tokens; each side is compressed into a vector independently.

Rank with a cheap first pass (e.g. BM25), then rerank only the top N documents with an expensive model like a full cross-encoder.

Encode query and document separately into one contextual vector per token (document vectors can be precomputed); for each query token find the most similar document token (MaxSim) and sum: \(\text{score}(q, d) = \sum_{i=1}^{N}\max_{j} E_{q_i}\cdot E_{d_j}\).

End-to-end with a cross-entropy loss on triples (query, positive document, negative document). Positives from datasets with gold relevant passages (e.g. MS MARCO), negatives sampled from an existing system’s top results; without labels, relevance-guided supervision iteratively harvests passages that do or don’t contain short answer strings.

Finding the document vectors with the highest dot product with the query is a nearest neighbor search problem, solved with approximate nearest neighbor libraries like Faiss. (Sparse retrieval uses the inverted index.)

The retriever, which finds relevant passages in a document collection, and the generator (historically the “reader”), an LLM that answers conditioned on the retrieved passages and the user prompt.

(1) Retrieve the top-k passages \(R(q) = d_1 \ldots d_k\) for query \(q\); (2) build a prompt with the passages and the question (“Based on these texts, answer this question: …”); (3) call the LLM, which generates \(p(x_i \mid R(q); \text{instruction}; q; x_{<i})\).

The system decides when to call retrieval and from which collection (web, private data…), instead of always retrieving for every turn.

Add a reranker to reorder passages after retrieval, or use multi-hop retrieval: append the first-stage documents to the query and retrieve again.

Instruction-tune the LLM on questions annotated with retrieved passages and correct answers; or use test-time compute to have it reflect on which passages were useful; or train the retriever and LLM end-to-end on question–answer data, since the IR engine wasn’t optimized for feeding an LLM.

Evidence for factual statements, like numbered references to URLs or literature. Simplest: instruct the model in the prompt to answer only from the provided search results and cite them for every factual claim.

The questions’ origin (natural information-seeking vs probing/testing), answer format (multiple choice vs free form), whether passages are provided (open vs closed book), and prompting setup (zero-shot vs few-shot).

Natural Questions (Google queries with long paragraph and short span answers from Wikipedia), MS MARCO (Bing queries with human answers and passages, for retrieval ranking and QA), DuReader (Chinese), TyDi QA (typologically diverse languages).

Given a question and a Wikipedia article’s passages in one of several typologically diverse languages, (a) select the passage containing the answer (or NULL) and (b) mark the minimal answer span (or NULL).

Its questions come from exams for humans (GRE, medical licensing, AP…), designed to test knowledge, not to reflect people’s information needs.

Reading comprehension: extract the answer from a given document. Open-book QA: answer given one or more documents (e.g. via RAG). Closed-book QA: answer directly from the LM with no retrieval.

Multiple-choice (e.g. MMLU): exact match, the % of predictions matching the gold answer exactly. Free-text answers (e.g. Natural Questions): token F1, treating prediction and gold as bags of tokens, computing F1 per question and averaging.

It parsed the question (with a cascade of finite-state transducers), mapped words to meaning fragments (“Where” → Place = ?), and matched the resulting attribute-value query against a structured database of games.

It retrieved candidate sentences by frequency-weighted term overlap with the question, then dependency-parsed them and picked the one whose structure best matched the question (“What do worms eat?” matches “worms eat grass”, not “birds eat worms”).

Predicate calculus / logical forms, as natural language interfaces to databases (LUNAR: lunar geology samples).

The US Text REtrieval Conference evaluations (since 1992) provided testbeds for IR; its QA track (1999) drove many factoid and non-factoid QA systems.

Retrieval augmentation was first introduced to improve language-model word prediction (Khandelwal et al., 2019), then quickly applied to question answering.