Retrieval & Information Extraction

A language model only knows what was in its training data, up to its training date, and it cannot cite where a fact came from. Retrieval-augmented generation (RAG) fixes part of this: before answering, find relevant passages in a document collection and put them in the prompt. The model then answers from what it has just read, and can say where it read it.

This page builds the retrieval side, sparse and dense, with small numeric examples, then the reverse problem: pulling structured fields out of text, reliably enough for a program to use them.

The pipeline

1. Chunk the documents into passages small enough to be specific.
2. Index them: word statistics for sparse retrieval, embedding vectors for dense retrieval.
3. Retrieve the top-$k$ passages for the question (the $k$ best-scoring), possibly from both kinds of index, and fuse the rankings.
4. Generate: put the passages in the prompt, with an instruction to answer from them and to cite them.

Lewis et al. (2020) introduced the name and a model that retrieves and generates jointly; today most RAG systems use a frozen language model and only engineer steps 1 to 3.

Sparse retrieval: BM25

Sparse retrieval looks at the words themselves. BM25 scores a document $d$ for a query $q$ by the query terms it contains (Robertson and Zaragoza, 2009):

with $L_d = |d| / \mathrm{avgdl}$, where:

• $t$ is a query term and the first sum runs over the terms of the query;
• $f_{t,d}$ is how often term $t$ occurs in $d$, $|d|$ the document's length and $\mathrm{avgdl}$ the average document length;
• $k_1$ and $b$ are constants (defaults $k_1 = 1.2$, $b = 0.75$);
• $\mathrm{idf}(t)$ is the inverse document frequency, which makes rare terms count more: the Apache Lucene search library uses $\mathrm{idf}(t) = \ln\!\left(1 + \frac{N - n_t + 0.5}{n_t + 0.5}\right)$, with $N$ documents of which $n_t$ contain $t$.

Two ideas are built in. Saturation: the tenth occurrence of a word adds much less than the first, controlled by $k_1$. Length normalization: a long document matches more words by chance, controlled by $b$. BM25 is fast, needs no training, and is hard to beat on exact names, codes and rare words.

Example. Three documents, tokenized: $d_0$ = "the cat sat" (3 words), $d_1$ = "the dog barked at the cat all day" (8 words), $d_2$ = "a bird sang" (3 words). The average length is $14/3 = 4.67$. Query: "cat".

1. "cat" is in 2 of the 3 documents: $\mathrm{idf} = \ln(1 + (3 - 2 + 0.5)/(2 + 0.5)) = \ln 1.6 = 0.47$.
2. Document $d_0$: $f = 1$, $L = 3/4.67 = 0.64$: $s = \dfrac{1 \cdot 2.2}{1 + 1.2\,(0.25 + 0.75 \cdot 0.64)} = 1.17$. Score $0.47 \cdot 1.17 = 0.55$.
3. Document $d_1$: the same count, but $L = 8/4.67 = 1.71$: $s = 0.77$, score $0.36$. The word "cat" is the same, but it is a smaller part of the long document.
4. Document $d_2$ has no "cat": score 0.

The ranking is $d_0$, $d_1$, $d_2$. For the query "dog" (in one document only, $\mathrm{idf} = 0.98$, higher because it is rarer) only $d_1$ scores: $0.98 \cdot 0.77 = 0.76$.

Saturation: with $L = 1$, a word that occurs $f = 1, 2, 3, 10$ times gets $s = 1.00, 1.38, 1.57, 1.96$: ten occurrences are not worth ten times one.

Dense retrieval: embeddings

Dense retrieval maps every passage and every query to a vector of numbers with a neural encoder, and ranks passages by cosine similarity, the dot product of unit-length vectors (1 if they point the same way, 0 if unrelated, $-1$ if opposite). Encoders are trained contrastively, like CLIP (Contrastive Language-Image Pre-Training, section 13): a query and its relevant passage are pulled together, the other passages in the batch pushed apart (Karpukhin et al., 2020, for question answering; Reimers and Gurevych, 2019, and Wang et al., 2022, for general sentence embeddings). Dense retrieval matches meaning rather than words ("car" finds "automobile"), but can miss exact identifiers. For millions of passages, exact search is replaced by approximate nearest-neighbour indexes such as FAISS, a library for similarity search on dense vectors (Johnson et al., 2021).

Example. Two-dimensional embeddings (real ones have hundreds of numbers). Query $(1, 0)$; passages $(2, 0)$, $(1, 1)$, $(0, 3)$, $(-1, 0.1)$. Cosine similarities: $1.00$, $0.71$, $0.00$, $-0.995$. The best two are passages 0 and 1. The length of the vectors does not matter, only the direction: $(2, 0)$ and $(1, 0)$ have similarity 1.

Retrieval is evaluated before generation, with recall@k: the fraction of the relevant passages that appear in the top $k$. If the right passage is not retrieved, no model can use it.

Example. Two queries, top 2 retrieved. Query 1 has relevant passages $\{0, 1\}$ and the top 2 are $[0, 1]$: recall $1$. Query 2 has relevant passages $\{2, 3\}$ and the top 2 are $[2, 1]$: it found one of two, recall $0.5$. Mean recall@2: $0.75$.

Fusing rankings

Hybrid retrieval runs both and merges the results. The scores of BM25 and of cosine similarity are on different scales, so adding them does not work. RRF (reciprocal rank fusion; Cormack et al., 2009) only needs ranks:

where ranks start at 1 and a document missing from a ranking contributes nothing. Elasticsearch uses $k = 60$ by default. A document ranked well by both retrievers rises to the top.

Example. BM25 ranks A, B, C; the dense retriever ranks B, D, A. With $k = 60$:

document	from BM25	from dense	RRF
B	$1/62$	$1/61$	$0.03252$
A	$1/61$	$1/63$	$0.03227$
D	none	$1/62$	$0.01613$
C	$1/63$	none	$0.01587$

The final ranking is B, A, D, C: B, which both found near the top, beats A, which BM25 put first but the dense retriever put last.

Chunking and context

Passages that are too long dilute the match and waste the context window; too short, and they lose the context that makes them understandable. A common compromise is fixed-size windows with overlap, so that a sentence cut at one boundary appears whole in the next chunk. The position of the passages in the prompt matters too: Liu et al. (2023) found that models use information at the beginning or end of a long context better than in the middle.

Example. A text of 10 tokens, chunks of size 4 with overlap 1: each chunk starts $4 - 1 = 3$ tokens after the previous. Chunks: tokens 0–3, 3–6 and 6–9. The tokens 3 and 6 each appear in two chunks, so a sentence cut at a boundary survives whole in at least one.

Information extraction

The reverse task turns text into data: names, dates, amounts, fields of a form. Classic systems trained a tagger per entity type; today an LLM (large language model) is prompted with a schema (the list of fields and their types) and asked to answer in JSON (JavaScript Object Notation, a text format for structured data). Two things make that reliable:

• Validation: parse the output, check that every required field is present and has the right type, and retry or reject otherwise. Models often wrap JSON in markdown fences or add a sentence before it, so parsing must be tolerant and checking strict.
• Constrained decoding: at every step, allow only the tokens that keep the output valid with respect to a grammar or a JSON schema, so that invalid output cannot be generated at all (Willard and Louf, 2023).

Example. The model answers: "Sure! Here it is:" followed by a code fence containing {"vendor": "ACME", "total": 42, "paid": true}. A tolerant parser finds the first { that starts a valid JSON object and returns it. The schema asks for a required text vendor, a required number total and an optional text date. Validation reports extra: paid (a field that is not in the schema). For {"total": "42"} it would report missing: vendor and type: total (a text where a number is expected).

References

• P. Lewis et al., Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks, NeurIPS, 2020.
• S. Robertson, H. Zaragoza, The Probabilistic Relevance Framework: BM25 and Beyond, Foundations and Trends in Information Retrieval, 2009.
• Apache Lucene, BM25Similarity: the idf formula and the defaults $k_1 = 1.2$, $b = 0.75$.
• V. Karpukhin et al., Dense Passage Retrieval for Open-Domain Question Answering, EMNLP, 2020.
• N. Reimers, I. Gurevych, Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks, EMNLP, 2019.
• L. Wang et al., Text Embeddings by Weakly-Supervised Contrastive Pre-training, arXiv, 2022. E5.
• J. Johnson, M. Douze, H. Jégou, Billion-Scale Similarity Search with GPUs, IEEE Transactions on Big Data 7, 2021. FAISS.
• G. V. Cormack, C. L. A. Clarke, S. Buettcher, Reciprocal rank fusion outperforms Condorcet and individual rank learning methods, SIGIR, 758–759, 2009.
• Elasticsearch documentation, Reciprocal rank fusion: rank_constant defaults to 60.
• N. F. Liu et al., Lost in the Middle: How Language Models Use Long Contexts, TACL, 2023.
• B. T. Willard, R. Louf, Efficient Guided Generation for Large Language Models, arXiv, 2023.