Retrieval Augmented Generation

retrieval-augmented generation bolts a search engine onto a language model: fetch relevant documents at query time and paste them into the prompt, so the model answers from evidence rather than from its frozen weights (lewis et al. 2020, retrieval-augmented generation for knowledge-intensive nlp). 𐃏 it is the pragmatic alternative to baking every fact into an llm’s weights.

why retrieve at all#

three problems that no amount of scaling fixes cleanly, and retrieval fixes cheaply:

• knowledge cutoff. a model’s parameters freeze at training time; retrieval injects information that did not exist then — today’s prices, this week’s tickets, your private wiki.
• grounding. parametric knowledge is lossy and confabulates confidently. conditioning generation on retrieved text sharply reduces hallucination on factual queries, because the answer is copied from context rather than reconstructed from weights.
• provenance. retrieved chunks carry source ids, so the system can cite — the user can check the claim against the document. a bare llm cannot tell you where its answer came from.

updating a rag system is editing a document store; updating a model’s parametric knowledge is fine-tuning (tune) or full retraining. that asymmetry is the whole value proposition.

dense retrieval#

classical search (bm25) matches words. dense retrieval matches meaning: a bi-encoder maps query and document independently to vectors in a shared space, and relevance is their similarity (karpukhin et al. 2020, dense passage retrieval).

• bi-encoder. two transformer encoders (often tied), \(q \mapsto E_Q(q)\) and \(d \mapsto E_D(d)\). crucially the document vectors are computed once, offline, so query time is a single query encode plus a vector search — this independence is what makes dense retrieval fast enough to scale.

• similarity. cosine similarity, or inner product when vectors are normalised:

  \begin{equation} \operatorname{sim}(q, d) = \frac{E_Q(q) \cdot E_D(d)}{\lVert E_Q(q) \rVert\, \lVert E_D(d) \rVert}. \end{equation}

• contrastive training. the encoders are trained to pull a query toward its true passage and push it from irrelevant ones, via the infonce loss over a batch with one positive \(d^+\) and negatives \(d^-_j\):

  \begin{equation} \mathcal{L} = -\log \frac{\exp(\operatorname{sim}(q, d^+)/\tau)}{\exp(\operatorname{sim}(q, d^+)/\tau) + \sum_j \exp(\operatorname{sim}(q, d^-_j)/\tau)}. \end{equation}

  the trick that makes it work is in-batch negatives: every other document in the batch serves as a negative for free, so a batch of \(B\) pairs gives \(B-1\) negatives per query at no extra encoding cost. hard negatives (bm25’s top wrong answers) sharpen it further.

approximate nearest-neighbour indexes#

exact nearest-neighbour over millions of vectors means a full scan — \(O(nd)\) per query, too slow at scale. ann indexes trade a little recall for large speedups:

• hnsw (hierarchical navigable small world): a multi-layer proximity graph; search greedily walks toward the query, descending layers. roughly \(O(\log n)\) query time, excellent recall, high memory (the graph) and slow to build. the default for quality.
• ivf (inverted file): k-means-cluster the vectors, search only the few clusters nearest the query. tunable via how many clusters you probe — fewer is faster and lower recall. often paired with product quantisation to compress vectors ~10–50x, at some accuracy cost.

honest complexity note: “approximate” is load-bearing — these structures do not guarantee the true top-\(k\), they return it with high probability, and the recall/latency/memory trade is a knob you tune per workload, not a solved problem.

chunking#

documents must be split before embedding, because one vector cannot faithfully summarise a whole pdf. the trade:

• too large — the chunk’s embedding averages many topics into mush, and retrieval precision drops.
• too small — chunks lose the surrounding context needed to be interpretable (“it increased 12%” — what did?).

typical practice: 200–500 token chunks with ~10–20% overlap so a fact straddling a boundary survives in at least one chunk. structure-aware splitting (on headings, paragraphs, code blocks) beats blind fixed-size cutting.

reranking#

the bi-encoder is fast but crude — it compressed each document to one vector before ever seeing the query. a cross-encoder reranker fixes this for the shortlist: it feeds the query and a candidate together through a transformer, so every query token attends to every document token, and outputs a single relevance score.

\begin{equation} \text{score}(q, d) = \operatorname{CrossEncoder}([q\,;\,d]) \in \mathbb{R}. \end{equation}

it is far more accurate and far too slow to run over the whole corpus — quadratic attention over \((q, d)\) for every document. so the standard two-stage recipe: bi-encoder retrieves top-100 cheaply, cross-encoder reranks those 100 to a top-5. best of both — the recall of dense retrieval, the precision of full cross-attention, only on a shortlist.

the generation step#

the top chunks are formatted into the prompt with an instruction to answer only from the provided context and to cite sources. good grounding prompts:

• interleave chunk text with explicit source markers ([1], [2]) so the model can attribute claims.
• instruct the model to say “not in the context” rather than fall back on parametric guessing — retrieval’s whole point is undone if the model ignores the evidence.

failure modes#

rag has three characteristic ways to be wrong, and they compound:

• retrieval miss. the right chunk never makes the top-\(k\) (bad embeddings, bad chunking, vocabulary mismatch). the generator then answers from parametric memory, confidently and unsourced — the worst failure because it looks grounded.
• context stuffing. cramming in as many chunks as fit dilutes signal with noise and can push the true answer past the model’s effective attention.
• lost in the middle. models attend most strongly to the start and end of a long context and neglect the middle (liu et al. 2023, lost in the middle) — so a correct chunk buried in position 8 of 15 may be ignored despite being retrieved. reranking to put the best chunk first is a partial fix.

evaluation#

rag is two systems, so evaluate both:

• retrieval: recall@k (did any relevant chunk make the top \(k\)?), plus rank-aware measures like mrr and ndcg. this is the ceiling — the generator cannot cite what was never retrieved.
• generation: faithfulness (is every claim supported by the retrieved context?) and answer relevance (does it address the question?). increasingly scored by an llm-judge against the retrieved chunks, with the usual caveat that the judge is itself fallible.

toy dense retrieval in numpy#

the retrieval core — embed, normalise, cosine top-\(k\) — with a hashing-trick embedding standing in for a trained bi-encoder. real systems swap embed for a transformer; the search logic is identical.

import numpy as np
import re
from zlib import crc32                  # deterministic hash (unlike builtin hash())

# --- toy corpus of "documents"
docs = [
    "the cat sat on the warm mat by the fire",
    "dogs are loyal animals and make great pets",
    "the kitten chased a ball of red wool",
    "python is a popular programming language",
    "neural networks learn features from raw data",
    "a warm fireplace keeps the cottage cosy in winter",
]

def tokenize(s):
    return re.findall(r"[a-z]+", s.lower())

# --- hashing-trick embedding: map each token to a fixed bucket, count = bag of words
DIM = 24
def embed(text):
    v = np.zeros(DIM)
    for tok in tokenize(text):
        v[crc32(tok.encode()) % DIM] += 1.0   # token -> fixed bucket
    n = np.linalg.norm(v)
    return v / n if n else v             # L2-normalise so dot product = cosine

D = np.stack([embed(d) for d in docs])   # (n_docs, DIM) document matrix

def retrieve(query, k=3):
    q = embed(query)
    sims = D @ q                          # cosine similarity (all vectors unit-norm)
    order = np.argsort(sims)[::-1][:k]
    return [(docs[i], sims[i]) for i in order]

for query in ["a warm cosy fireplace", "loyal pet animals", "learn features from data"]:
    print(f"query: {query!r}")
    for doc, sim in retrieve(query):
        print(f"  {sim:.3f}  {doc}")
    print()

query: 'a warm cosy fireplace'
  0.667  a warm fireplace keeps the cottage cosy in winter
  0.408  python is a popular programming language
  0.333  neural networks learn features from raw data

query: 'loyal pet animals'
  0.577  dogs are loyal animals and make great pets
  0.385  a warm fireplace keeps the cottage cosy in winter
  0.236  python is a popular programming language

query: 'learn features from data'
  0.833  neural networks learn features from raw data
  0.333  a warm fireplace keeps the cottage cosy in winter
  0.316  the kitten chased a ball of red wool

each query pulls the right document to rank 1 by cosine alone. the noisy tail (a fireplace matching “loyal pet animals” at \(0.385\)) is exactly the weakness a trained bi-encoder plus a cross-encoder reranker exists to remove — a bag-of-words embedding shares buckets between unrelated words, whereas a learned encoder places meaning, not spelling, near meaning.

see also#

• llms — the generator this pipeline grounds
• transformers — the encoder behind bi- and cross-encoders
• tokenisers — how documents become token sequences before embedding
• fine tuning — the alternative for injecting knowledge into weights