Every day, billions of searches are answered by information retrieval (IR) systems. Inside organisations, good search over policies, reports and FAQs saves staff hours and helps people find accurate information. And retrieval is the foundation of retrieval-augmented generation (RAG): an LLM can only answer from documents that retrieval finds. This lecture covers modern retrieval end to end.
The retrieval problem#
Given a query $q$ and a collection of documents (or passages) $\mathcal{D}$, rank documents by relevance. Because collections may contain millions of items, systems use a two-stage design:
- First-stage retrieval — fast, recall-oriented: retrieve the top 100–1,000 candidates.
- Re-ranking — slower, precise: reorder the candidates with a more expensive model.
Lexical retrieval: the inverted index and BM25#
An inverted index maps each term to the list of documents containing it, enabling fast lookup of candidate documents for query terms. Documents are scored with BM25 (see the TF-IDF lecture). Lexical retrieval excels at exact matches: names, codes, rare technical terms, ID numbers. It fails on vocabulary mismatch — "newborn paperwork" vs "birth registration".
Dense retrieval with bi-encoders#
A bi-encoder embeds queries and documents independently into the same vector space; relevance is the dot product or cosine similarity:
Document embeddings are computed once offline; at query time only the query is encoded, followed by nearest-neighbour search. Bi-encoders (DPR, sentence-transformers, E5, BGE, GTE and multilingual variants) are trained contrastively with in-batch and hard negatives, and capture meaning beyond exact words.
from sentence_transformers import SentenceTransformer, CrossEncoder
import numpy as np
docs = ["Birth registration is free at the civil registry office.",
"Vaccinations for children under five are given every Tuesday at the health post.",
"To renew a passport, submit the old passport and two photographs.",
"Cash assistance eligibility depends on household size and income.",
"Lost birth certificates can be replaced by applying with a parent's ID."]
bi = SentenceTransformer("sentence-transformers/paraphrase-multilingual-MiniLM-L12-v2")
D = bi.encode(docs, normalize_embeddings=True)
query = "my baby's birth paper got lost"
q = bi.encode([query], normalize_embeddings=True)[0]
cand = np.argsort(-(D @ q))[:3] # first stage: dense retrieval
print([docs[i] for i in cand])
ce = CrossEncoder("cross-encoder/ms-marco-MiniLM-L-6-v2") # second stage: re-ranking
scores = ce.predict([(query, docs[i]) for i in cand])
print(docs[cand[int(np.argmax(scores))]])Cross-encoder re-ranking#
A cross-encoder feeds query and document together into a transformer, letting every query token attend to every document token, and outputs a relevance score. It is far more accurate than a bi-encoder but too slow to run over the whole collection — perfect for re-ranking the top candidates. Late-interaction models such as ColBERT keep per-token embeddings and compute fine-grained similarity efficiently, a middle ground.
Hybrid search#
Lexical and dense retrieval make different errors. Hybrid search combines them, for example with Reciprocal Rank Fusion (RRF):
Hybrid retrieval is a robust default for real-world search and RAG, especially when queries contain names or codes.
Approximate nearest neighbour (ANN) search#
Exact search over millions of vectors is slow. ANN indexes trade a little recall for large speed-ups:
- HNSW (Hierarchical Navigable Small World graphs): navigate a multi-layer proximity graph; excellent recall/speed trade-off.
- IVF (inverted file): cluster vectors and search only the nearest clusters.
- Product quantisation (PQ): compress vectors into short codes for memory efficiency.
Libraries (FAISS, hnswlib) and vector databases (e.g. pgvector, Qdrant, Weaviate, Milvus, Elasticsearch/OpenSearch vector fields) implement these.
Chunking documents#
Long documents are split into passages (e.g. 200–500 tokens, with overlap) before embedding. Chunk boundaries matter: splitting mid-table or mid-procedure harms retrieval. Keep metadata (title, section, date, language, source URL) with each chunk for filtering and citation.
Evaluation#
With relevance judgements for a set of test queries:
- Recall@k: fraction of relevant documents in the top $k$ — key for first-stage retrieval and RAG.
- MRR (mean reciprocal rank): $\frac{1}{|Q|}\sum_q\frac{1}{\text{rank of first relevant}}$.
- nDCG@k: rewards relevant results near the top, supports graded relevance:
Public benchmarks include MS MARCO, BEIR (zero-shot across domains) and MTEB for embeddings. Always also evaluate on your own queries — log real user queries (with privacy safeguards) and label relevance.