LLM & VLM courseBlog
152Track 6: LLM applications · session 10 of 20

RAG, part 1: the basic pipeline

A language model only knows what was in its training data, and it cannot tell you where a fact came from. Retrieval-augmented generation (RAG) fixes this: find the right pieces of your own documents, put them in the prompt, and ask the model to answer from them with citations. This session builds the basic pipeline step by step (chunking, embedding, indexing, hybrid search, reranking, context assembly and citations) and ends with an honest comparison of RAG, long context and fine-tuning.

Time: 3 to 4 hours (reading 2 hours, exercises 1 to 2 hours)Level: IntermediateBefore this: Sessions 143, 150 and 151

What you will learn

  • Why RAG exists: knowledge that is fresh, private and citable, and the original RAG formula of Lewis et al.
  • The two halves of a RAG system: the offline indexing pipeline and the online query pipeline
  • How to chunk documents: chunk size, overlap, sentence boundaries, and the exact overlap that keeps a fact whole
  • Sparse search with BM25 (with the meaning of k1 and b) and dense search with embeddings, and why each one fails on different queries
  • Hybrid search: reciprocal rank fusion and weighted score fusion
  • Two-stage retrieval: why a cross-encoder reranker over 50 to 100 candidates beats either stage alone, and what it costs
  • Context assembly and citations, and when to use RAG, long context or fine-tuning, with FLOPs and KV-cache numbers for an 8B model

Why this matters

A language model knows only what was in its training data. It does not know what happened after its training cutoff, it has never seen your company’s documents, and it cannot tell you where a fact came from. Retrieval-augmented generation (RAG) fixes all three problems with one simple idea: before the model answers, search your documents for the most useful pieces and put them in the prompt.

The three needs have names. Knowledge must be fresh (a new price list, yesterday’s incident report), private (contracts, code, medical notes that were never on the public web) and citable (the user, a lawyer or an auditor must be able to click on the source). Retraining a model every day for new facts is too slow and too expensive. Putting all your documents into every prompt is usually too long. Searching first, then reading only the best few pieces, is cheap, fast and easy to update: you add a document to the index, and the next question can use it.

The name comes from Lewis et al. (2020). Their system used a dense retriever (DPR) over the December 2018 Wikipedia dump, split into 21 million chunks of 100 words, stored in a FAISS index, and a BART-large generator with 400M parameters. [Certain] Today almost every “chat with your documents” product, every enterprise search assistant and every coding assistant that reads your repository is a RAG system. This session builds the basic pipeline. Session 153 adds advanced methods and, most important, evaluation. It builds on session 150 (how text becomes vectors) and session 151 (how to search millions of vectors fast).

The idea and the pipeline

Let \(x\) be the user’s question and \(y\) the answer. A plain LLM models \(p_\theta(y \mid x)\): the answer depends only on the question and on the weights \(\theta\). RAG adds a hidden variable \(z\), a piece of text retrieved from a large collection. Lewis et al. wrote the model as a sum over the top \(k\) retrieved pieces:

\[ p(y \mid x) \;\approx \sum_{z \,\in\, \text{top-}k(x)} p_\eta(z \mid x)\; p_\theta(y \mid x, z) \tag{152.1} \]
Read the symbols
\(z\)
one retrieved chunk of text (a passage)
\(p_\eta(z \mid x)\)
the retriever: how relevant chunk \(z\) is to question \(x\), turned into a probability; \(\eta\) are the retriever’s weights
\(p_\theta(y \mid x, z)\)
the generator (the LLM): the probability of answer \(y\) when it reads both the question and the chunk
top-\(k(x)\)
the \(k\) chunks with the highest retriever score; Lewis et al. trained with 5 or 10

Formula (152.1) says: the answer is a mixture of “answers given chunk 1”, “answers given chunk 2”, and so on, weighted by how relevant each chunk is. In the original paper both the retriever’s query encoder and the generator were trained together. Most RAG systems today are simpler: a frozen retriever, a frozen LLM, and all top-\(k\) chunks pasted into one prompt. The LLM itself then decides which chunk to use. This “retrieve, then read” system is what we build here. (For methods that train the retriever with the LLM’s feedback, see session 90.)

A RAG system has two halves that run at different times:

  • Offline (indexing), once per document and again when it changes: load and clean the documents, cut them into chunks, compute an embedding vector for each chunk, and store the chunks in two indexes: a vector index for dense search and an inverted index for keyword search.
  • Online (query), for every question: search both indexes, fuse the two result lists, rerank the best candidates with a more accurate model, assemble the prompt with numbered sources, and let the LLM answer with citations.

Step through the whole pipeline in Figure 1. The example uses a tiny manual for a made-up router, the X200, which we use for the rest of the session.

offline: indexingonline: the querythe active step
Figure 1. The basic RAG pipeline. The top row runs offline when documents arrive. The bottom row runs for every question. The two meet at the indexes.
How to read Figure 1

Press Next to move one step. The readout shows what happens to the question “what does error E-4012 mean” at that step, with the real numbers from the toy example of Figures 3 and 4. Notice that only the last two boxes involve the big LLM. Everything before them is search, and search quality decides most of the final answer quality: the LLM cannot cite a chunk it never sees.

Chunking: cutting documents into pieces

Why not embed each document as one vector? Three reasons. First, embedding models have a maximum input length; BERT-based encoders, which many embedding models are, stop at 512 tokens. [Certain] Second, one vector for a 40-page PDF is an average of 40 pages of meaning, so it matches nothing well. Third, the prompt has a budget: we want to paste the one paragraph that answers the question, not the whole PDF. So we cut each document into chunks, and the chunk becomes the unit of search, of the prompt and of the citation.

Chunk size is a trade-off. Too small, and a chunk loses its context: “It needs wall power” does not say what “it” is. Too large, and the chunk’s embedding is diluted by unrelated text, and each chunk eats more of the prompt. Common starting points are 200 to 800 tokens with 10 to 20% overlap; the right value depends on the documents and must be tuned on your own questions. [Likely]

Fixed-size chunks with overlap

The simplest method slides a window of \(C\) tokens over a document of \(N\) tokens, moving \(C - O\) tokens each time, so neighbouring chunks share \(O\) tokens of overlap. The number of chunks is

\[ n_{\text{chunks}} = \left\lceil \frac{N - O}{C - O} \right\rceil \quad (N \gt C), \qquad \text{storage factor} \approx \frac{C}{C - O} \tag{152.2} \]
Read the symbols
\(N\)
length of the document in tokens
\(C\)
chunk size in tokens
\(O\)
overlap: how many tokens each chunk shares with the next one (\(O \lt C\))
\(\lceil \cdot \rceil\)
round up to the next whole number

Why overlap at all? Because a fact that crosses a chunk boundary is cut in half, and neither half matches the question well. How much overlap do we need? Take a fact that is \(L\) tokens long. Windows start every \(C - O\) tokens, so the last window that starts at or before the fact starts at most \(C - O - 1\) tokens before it. That window holds the whole fact if \((C - O - 1) + L \le C\). So:

\[ \text{every fact of length } L \text{ lies whole inside some chunk} \iff O \ge L - 1 \tag{152.3} \]

(The “only if” part holds for the worst-placed fact.) So overlap is a promise: “facts up to \(O + 1\) tokens long are never cut”. Longer facts may be cut, depending on luck. Overlap costs storage: by (152.2), \(O = 64\) with \(C = 512\) stores \(512/448 = 1.14\) times the text.

Structure-aware chunks

Better splitters cut at natural boundaries: sections, then paragraphs, then sentences, and only then in the middle of a sentence. (This is the “recursive” splitter in common RAG libraries.) Each chunk also carries metadata: the document title, the section heading, the page number, the date, and who is allowed to read it. Many systems put the title and heading in front of the chunk text before embedding, so that “It needs wall power” becomes “X200 manual › Power: It needs wall power”. Tables, code and slides need their own splitters: never cut a table row or a function in half. Try both methods on a 100-word document in Figure 2.

the answer (2 sentences, 20 words)chunk that holds the whole answeroverlap text (dotted)
Figure 2. Chunking a 100-word document. The question is “why does my router show E-4012?”. The answer needs two sentences (the cause and the code), 20 words in total, so it is only useful if one chunk holds both.
How to read Figure 2

Start with fixed windows, \(C = 30\), \(O = 0\): the answer is cut between two chunks. Raise the overlap: with \(O \ge 19\) the answer is always whole (formula 152.3 with \(L = 20\)), but the stored text grows by \(C/(C - O)\). Now switch to whole sentences with \(C = 30\) and \(O = 0\): the splitter keeps sentences together and the answer fits into one chunk with no extra storage. With whole sentences, overlap repeats the last sentences of a chunk at the start of the next one, and this can move the boundaries in a bad way (try \(O = 10\)). There is no setting that is best for every fact; this is why chunking is tuned on real questions.

Worked example: how many chunks, and how big is the index?

A company has 10,000 documents of 2,000 tokens each (20 million tokens). With \(C = 512\) and \(O = 64\), each document gives \(\lceil (2000 - 64)/448 \rceil = \lceil 4.32 \rceil = 5\) chunks, so 50,000 chunks. With a 1,024-dimensional embedding in FP32, the vectors need \(50{,}000 \times 1024 \times 4 = 204.8\) MB (102.4 MB in FP16). That fits in the memory of a laptop; exact search over it is fine.

The DPR Wikipedia index is a different size: 21,015,324 passages of 100 words, with 768-dimensional vectors, is \(21{,}015{,}324 \times 768 \times 4 \approx 64.6\) GB in FP32. That is when the compressed indexes of session 151 (IVF, PQ, HNSW) become necessary.

Dense retrieval: embeddings and the vector index

Dense retrieval uses a bi-encoder: one encoder turns the question into a vector \(\mathbf{q}\), and the same (or a twin) encoder turns each chunk into a vector \(\mathbf{d}\). Chunks are embedded once, offline; only the question is embedded at query time. The score is the cosine similarity:

\[ s_{\text{dense}}(q, d) = \cos(\mathbf{q}, \mathbf{d}) = \frac{\mathbf{q}^\top \mathbf{d}}{\lVert \mathbf{q} \rVert\, \lVert \mathbf{d} \rVert} \tag{152.4} \]

If all vectors are normalized to length 1 when they are stored, the cosine is just a dot product, which is what fast vector indexes compute. Dense retrieval is good at meaning: “how do I restart my router” matches “to reboot the X200, hold the power button” even though the two share no important word. It was trained to do this (see session 60). On Natural Questions, DPR found the answer in its top 20 passages for 78.4% of questions, against 59.1% for BM25. [Certain]

Two practical rules. First, the question and the chunks must be embedded by the same model version; if you change the embedding model, you must re-embed the whole collection. Second, many embedding models expect an instruction or prefix. The E5 models, for example, expect "query: " in front of questions and "passage: " in front of chunks. [Certain] Forgetting the prefix quietly lowers quality.

Figure 3 runs this dense half of the pipeline for real, from raw text to an answer, on the 8 paragraphs of the X200 help pages. To keep every number checkable by hand it uses a toy embedding: each dimension is a concept, the value is a count, stop words are dropped, and synonyms share one dimension (“reboot” and “restart” both count as restart; every error code counts as CODE). With counts, formula (152.4) becomes small integer arithmetic. For the question “what does error E-4012 mean”, \(\mathbf{q} = (\text{error } 1, \text{CODE } 1, \text{mean } 1)\) and \(\lVert \mathbf{q} \rVert = \sqrt{3} = 1.732\). Chunk 2 has the counts error 2, CODE 1, mean 1 plus five concepts the question does not use, so \(\lVert \mathbf{d} \rVert = \sqrt{22} = 4.690\) and

\[ \cos(\mathbf{q}, \mathbf{d}_2) = \frac{1\cdot 2 + 1\cdot 1 + 1\cdot 1}{1.732 \times 4.690} = \frac{4}{8.124} = 0.492 \]

Chunk 3 (“Fault E-4021 means the fan is blocked. Clean the air vent.”) shares 3 counts with the question but is shorter, \(\lVert \mathbf{d} \rVert = \sqrt{10}\), so it scores \(3/(1.732 \times 3.162) = 0.548\) and wins. The long chunk 2 is pushed down by its own length: its five extra concepts sit in the denominator. The last stage is a stand-in reader, not a real LLM: it picks the source sentence that shares the most concept counts with the question and cites its number. It is enough to show the rule that matters: the generator can only use what retrieval put into the prompt.

  1. for each paragraph \(p\): if \(\text{words}(p) \le C\) keep \(p\), else split at sentence ends (then every \(C\) words) chunk
  2. for each chunk \(z_i\): \(\mathbf{d}_i \leftarrow\) concept counts of \(z_i\); store \(\lVert \mathbf{d}_i \rVert\) embed, offline
  3. \(\mathbf{q} \leftarrow\) concept counts of the question; \(\lVert \mathbf{q} \rVert\) online
  4. for each chunk: \(s_i \leftarrow \mathbf{q} \cdot \mathbf{d}_i \,/\, (\lVert \mathbf{q} \rVert\, \lVert \mathbf{d}_i \rVert)\) (152.4)
  5. \(\text{top-}k \leftarrow\) the \(k\) chunks with the largest \(s_i\) \(\text{top-}k(x)\) of (152.1)
  6. for \(j = 1, \dots, k\): \(\text{prompt} \leftarrow \text{prompt} + \text{“}[j]\text{ ”} + z_{(j)}\)
  7. \(s^{*} \leftarrow \argmax_{s}\ \mathbf{q} \cdot \text{count}(s)\) over source sentences \(s\) stand-in reader
  8. \(\text{answer} \leftarrow s^{*} + \text{“ }[j]\text{”}\)
cosine score (bar)the current itemin the top \(k\): goes into the promptbadge colour: source paragraph
Figure 3. Dense RAG computed step by step in the browser: chunk the 8 paragraphs, embed each chunk, embed the question, score every chunk with the cosine (152.4), sort, paste the top \(k\) into the prompt, and answer. The embedding is the toy concept-count embedding described above (the same one as in Figure 4), and the generator is a stand-in reader, not an LLM. Every number in the panel on the right is computed live.
How to read Figure 3

Press Play, or Step through it. The highlighted line of the algorithm is the one running; the panel under it shows the formula with the real numbers. Each chunk is a row; its bar grows to its cosine, and at the “rank” step the rows slide into order. With the defaults (\(C = 20\), \(k = 3\)) dense search ranks the wrong error code first (c3, 0.548, ahead of c2, 0.492), but c2 is still in the prompt as [2], and the answer comes from it. Now set \(k = 1\): only c3 reaches the prompt and the answer is wrong. Keep \(k = 1\) and lower \(C\) to 8: the sentence “Error E-4012 means the firmware update failed.” becomes its own chunk, nothing dilutes it, and it ranks first with 0.816. Smaller is not always better: with \(C = 8\), “keeps switching off” and “restart my router” lose the second half of their answer (“too hot”, “ten seconds”) to a separate chunk that shares no concept with the question.

Sparse retrieval: BM25

The older family of methods is sparse or lexical search: a chunk matches if it contains the words of the question. An inverted index maps each word to the list of chunks that contain it, so search touches only the chunks that share a word with the question. The standard scoring function is BM25 (Robertson and Zaragoza):

\[ s_{\text{BM25}}(q, d) = \sum_{t \in q} \operatorname{IDF}(t)\cdot \frac{f(t, d)\,(k_1 + 1)}{f(t, d) + k_1\left(1 - b + b\,\dfrac{|d|}{\text{avgdl}}\right)} \tag{152.5} \]
\[ \operatorname{IDF}(t) = \ln\!\left(1 + \frac{N - n_t + 0.5}{n_t + 0.5}\right) \tag{152.6} \]
Read the symbols
\(t \in q\)
each distinct word (term) of the question
\(f(t, d)\)
how many times term \(t\) appears in chunk \(d\) (term frequency)
\(|d|\), avgdl
the length of chunk \(d\), and the average chunk length in the collection
\(N\), \(n_t\)
the number of chunks, and the number of chunks that contain \(t\)
\(k_1\)
saturation: how fast extra repeats of a word stop helping; typical 1.2 to 2.0
\(b\)
length normalization: \(b = 1\) fully penalizes long chunks, \(b = 0\) ignores length; typical 0.75

Read it in three parts. IDF (inverse document frequency) rewards rare words: a word in every chunk tells you nothing, a word in one chunk tells you a lot. The fraction grows with the term count but saturates: the tenth “firmware” adds much less than the first, and the fraction can never exceed \(k_1 + 1\). The length term lowers the score of long chunks, which contain many words just by being long. Lucene and Elasticsearch use \(k_1 = 1.2\), \(b = 0.75\) by default. [Certain] The IDF in (152.6) is the Lucene form; the “1 +” inside the log keeps it positive even for a word that is in every chunk.

Worked example: BM25 by hand

Our toy collection (listed under Figure 4) has \(N = 8\) chunks with an average length of 8.75 words after removing stop words. The question “what does error E-4012 mean” keeps three terms: error, e-4012, mean.

e-4012 appears in one chunk, so \(\operatorname{IDF} = \ln(1 + 7.5/1.5) = \ln 6 = 1.792\). The same holds for error (the other error chunk says “fault”). mean appears nowhere (the chunks say “means”; we do no stemming), so it adds 0.

Chunk 2 has 12 words, so the length term is \(k_1(1 - b + b \cdot 12/8.75) = 1.2 \times 1.279 = 1.534\). Each of the two terms appears once: \(1.792 \times 2.2/(1 + 1.534) = 1.555\). The total is \(2 \times 1.555 = 3.111\), and chunk 2 is the only chunk with a score above 0. Figure 4 prints the same 3.111.

BM25 needs no training, no GPU, and works the same on any language with a tokenizer. It is very strong on exact matches: codes, names, rare technical words. The BEIR benchmark found BM25 to be a robust baseline across 18 datasets when the retriever has not been trained on the target domain (zero-shot), where many dense retrievers did worse than expected. [Certain] Its weakness is the vocabulary gap: “restart” does not match “reboot”.

Hybrid search: use both

Dense search fails on rare exact strings; BM25 fails on paraphrases. The failures are different, so we run both and fuse the two ranked lists. This is hybrid search. The problem: the two scores live on different scales (a BM25 score of 3.1 and a cosine of 0.49 cannot be added). There are two common answers.

Reciprocal rank fusion (RRF) ignores the scores and uses only the ranks:

\[ s_{\text{RRF}}(d) = \sum_{r \in \text{lists}} \frac{1}{k + \operatorname{rank}_r(d)} \tag{152.7} \]
Read the symbols
\(\operatorname{rank}_r(d)\)
the position of chunk \(d\) in result list \(r\) (1 = best); a chunk missing from a list gets nothing from that list
\(k\)
a constant that flattens the curve; Cormack et al. used \(k = 60\) and found the exact value not critical

A chunk near the top of both lists wins. With \(k = 60\), rank 1 gives \(1/61 = 0.0164\) and rank 2 gives \(1/62 = 0.0161\): small rank differences matter little, and being in both lists matters a lot. RRF needs no tuning and no score calibration, which is why it is the default hybrid method in several search engines. [Likely]

Weighted score fusion first rescales each list to \([0, 1]\) (min-max normalization), then mixes them with a weight \(\alpha\):

\[ s_{\text{hyb}}(d) = \alpha\, \tilde{s}_{\text{dense}}(d) + (1 - \alpha)\, \tilde{s}_{\text{BM25}}(d), \qquad \tilde{s} = \frac{s - s_{\min}}{s_{\max} - s_{\min}} \tag{152.8} \]

It keeps more information (how much better the top hit is), but \(\alpha\) must be tuned, and min-max scaling is sensitive to outliers. Hybrid search is not always better than the better single method: on Natural Questions, DPR’s own BM25 + DPR mix reached 76.6% top-20 accuracy, a little below DPR alone (78.4%). [Certain] Its main value is robustness: it rarely fails badly on any type of query. Try it in Figure 4; its lower half runs the fusion one list entry at a time, with formula (152.7) or (152.8) filled in.

The fusion, one list entry at a time
  1. \(s(d) \leftarrow 0\) for every chunk \(d\)
  2. for each list \(r\) in (BM25, dense):
  3. for \(\text{rank} = 1, 2, \dots\) of list \(r\): \(d \leftarrow\) the chunk at that rank
  4. \(s(d) \leftarrow s(d) + \dfrac{1}{k + \text{rank}}\) (152.7)
  5. sort the chunks by \(s(d)\), best first
share from the BM25 listshare from the dense listcorrect chunk (label)
The 8 chunks of the toy collection
    Figure 4. BM25, dense search and their fusion on 8 chunks from the X200 manual. BM25 is the real formula (152.5) with \(k_1 = 1.2\), \(b = 0.75\). The dense scores come from a toy embedding in which synonyms (restart, reboot) share a direction and all error codes look alike, which copies the typical strengths and weaknesses of real embedding models. The correct chunk for each preset question is shown in green. The lower half replays the fusion: each step takes one entry of one list and adds its share to that chunk’s fused score, so each bar is the sum of its BM25 part and its dense part.
    How to read Figure 4

    “error E-4012”: BM25 finds chunk 2 by the exact code; dense search puts the wrong error (E-4021) first because codes look alike to it. Fusion puts chunk 2 first. “restart my router”: BM25 sees only the word “router” and returns the warranty chunk; dense search understands restart = reboot. With RRF the correct chunk is second; in weighted mode, push \(\alpha\) above about 0.55 and it becomes first. This is the job of the first stage: get the right chunk into the top few, and let the reranker of the next section fix the order. Type your own question too: words that are not in the toy vocabulary only match themselves.

    The fusion player starts at the final result; press Play to rebuild it. The highlighted entry in the lists above is the one being added. In RRF mode watch chunk 2 for “error E-4012”: it gets \(1/61 = 0.01639\) from rank 1 of BM25 and \(1/62 = 0.01613\) from rank 2 of dense search, \(0.03252\) in total, while chunk 3 gets only the dense \(0.01639\). Being in both lists beats being first in one. In weighted mode the same chunk gets \((1 - \alpha) \cdot 1\) from BM25 and \(\alpha \cdot 0.839\) from dense search.

    Reranking: a second, more careful look

    A bi-encoder embeds the question and the chunk separately; the two texts never see each other until the final dot product. That is what makes it fast (chunks are embedded once, offline), and also what limits it. A cross-encoder reads the question and the chunk together, as one input “[CLS] question [SEP] chunk [SEP]”, so every question token can attend to every chunk token, and outputs one relevance score. Nogueira and Cho (2019) fine-tuned BERT this way (“monoBERT”) and improved MRR@10 on MS MARCO by 27% relative to the previous best. [Certain] On BEIR, reranking models gave the best zero-shot results on average, at a high compute cost. [Certain]

    The catch is cost. A cross-encoder must run one full forward pass per (question, chunk) pair at query time, so it can never scan a million chunks. The solution is two-stage retrieval: a cheap first stage (hybrid search) returns \(K\) candidates, say 50 to 100, and the cross-encoder rescores only those and keeps the best \(n\), say 5. The cost per question is

    \[ \text{FLOPs}_{\text{rerank}} \approx K \cdot 2 P_r \cdot (|q| + C) \tag{152.9} \]

    where \(P_r\) is the reranker’s parameter count and \(|q| + C\) the tokens of one pair. For a BERT-base-sized reranker (\(P_r \approx 110\)M), \(K = 100\) and 256 tokens per pair: \(100 \times 2 \times 110 \times 10^6 \times 256 = 5.6 \times 10^{12}\) FLOPs, about 56 ms at an effective 100 TFLOP/s. [Likely: real speed depends on the GPU and batching] Small next to the LLM call, but not free.

    One rule limits what the reranker can do: it can only reorder what the first stage gave it.

    \[ \text{Recall@}n\,(\text{after reranking}) \;\le\; \text{Recall@}K\,(\text{first stage}) \tag{152.10} \]

    Recall@\(K\) is the fraction of questions whose correct chunk is somewhere in the top \(K\). So the first stage is tuned for recall (do not lose the right chunk), and the reranker for precision (put it on top). A larger \(K\) raises the ceiling but costs more, and also gives the reranker more wrong candidates to be fooled by. Figure 5 simulates this trade-off.

    no reranker: first-stage Recall@5first-stage Recall@K (the ceiling, 152.10)rerank K, keep 5: Recall@5
    Figure 5. A simulation of two-stage retrieval: 400 questions, each with one correct chunk among 1,000 wrong ones. A score is “quality + noise” for the correct chunk and pure noise for the others (standard normal noise, seeded). The cross-encoder rescores the top \(K\) with its own, better quality. This is a model, not a benchmark result.
    How to read Figure 5

    The grey line is what you get by sending the first stage’s top 5 straight to the LLM. The blue line is the ceiling: the reranker can never beat it. The orange line is the real system. Move \(K\) from 5 to 100: Recall@5 rises from 0.49 to 0.86 with the default settings, because the reranker rescues correct chunks that the first stage ranked 6th to 100th. Past a point the orange line flattens and falls behind the ceiling: every extra candidate is one more chance to be fooled, while the cost (shown in the readout) grows linearly with \(K\). A weak reranker (\(\Delta_2\) near \(\Delta_1\)) gains little. In this toy model the wrong candidates look random to the reranker; real “hard negatives” are harder, so real gains are smaller. [Likely]

    Context assembly and citations

    After reranking we have, say, 5 chunks. Context assembly turns them into the prompt. It is simple, and easy to get wrong.

    1. Budget. Count tokens. The prompt holds the system instructions, the sources and the question, and must leave room for the answer. The tokens per question are
    \[ n_{\text{prompt}} = n_{\text{sys}} + |q| + \sum_{i=1}^{k} \big(|z_i| + n_{\text{meta}}\big) \tag{152.11} \]

    With 200 instruction tokens, a 50-token question and 5 chunks of 400 tokens plus 20 tokens of labels each: \(200 + 50 + 5 \times 420 = 2{,}350\) tokens.

    1. Deduplicate. Overlapping chunks and copies of the same page waste the budget. Merge neighbouring chunks from the same document into one passage.
    2. Order. LLMs use information at the start and the end of a long context better than information in the middle (“lost in the middle”, Liu et al.). [Certain] So put the best chunk first, and with many chunks put the second best last. [Likely]
    3. Label. Give each chunk a number and its source: [2] (manual.pdf, p. 14, 2025-03) ….
    4. Instruct. Tell the model to answer only from the sources, to cite each claim with the number, and to say “I don’t know” when the sources do not contain the answer.

    The prompt for our running example then looks like this:

    Answer using only the sources below. Cite them like [1].
    If the answer is not in the sources, say you do not know.
    
    Sources:
    [1] (manual.txt) Error E-4012 means the firmware update failed. Download the firmware again and reinstall it.
    [2] (manual.txt) To reboot the X200, hold the power button for ten seconds.
    [3] (manual.txt) Fault E-4021 means the fan is blocked. Clean the air vent.
    
    Question: what does error E-4012 mean
    Answer:

    A citation is the link from a sentence of the answer to the chunk that supports it. Because every chunk keeps its document, page and position, the interface can show the exact passage. Citations are cheap to request but must be checked: models sometimes cite a number that does not exist, or cite a real chunk that does not support the sentence. Two checks are common. (1) A format check: every cited number must be one of the sources. (2) A support check: does the cited chunk entail the sentence? This is a natural language inference task (see session 145), done with a small NLI model or with an LLM judge. Unsupported sentences can be removed, or the answer regenerated. Session 153 measures this as faithfulness.

    The whole pipeline as algorithms

    Algorithm 1: offline indexing
    1. input: documents with metadata (source, date, access list); chunk size \(C\), overlap \(O\); embedding model \(E\)
    2. for each document \(D\): extract clean text (PDF, HTML, tables, code each need their own parser)
    3.   split \(D\) at sections, paragraphs, sentences into chunks of at most \(C\) tokens, overlap \(O\) // (152.2), (152.3)
    4.   for each chunk \(z\): text \(\leftarrow\) title + heading + \(z\); store \(z\) with its metadata and a stable id
    5.     \(\mathbf{d} \leftarrow E(\text{"passage: " + text})\), normalize to length 1 // (152.4)
    6.     add \(\mathbf{d}\) to the vector index (exact, IVF or HNSW); add the words of \(z\) to the inverted index // (152.5)
    7. when a document changes: delete its old chunk ids, re-index it; when \(E\) changes: re-embed everything
    Algorithm 2: answering one question
    1. input: question \(q\), user permissions; \(K\) candidates, \(n\) final chunks, token budget \(B\)
    2. \(L_{\text{dense}} \leftarrow\) top \(K\) of the vector index for \(E(\text{"query: "} + q)\), filtered by permissions
    3. \(L_{\text{BM25}} \leftarrow\) top \(K\) of the inverted index for the words of \(q\), filtered by permissions
    4. \(L \leftarrow\) RRF\((L_{\text{dense}}, L_{\text{BM25}})\), keep the top \(K\) // (152.7)
    5. score every \(z \in L\) with the cross-encoder on (\(q\), \(z\)); keep the top \(n\) // (152.9)
    6. merge neighbours and duplicates; drop chunks until the prompt fits \(B\) // (152.11)
    7. order: best first (and second best last); label \([1] \dots [n]\) with sources
    8. answer \(\leftarrow\) LLM(instructions + sources + \(q\))
    9. check every citation \([i]\): it exists, and chunk \(i\) supports its sentence; otherwise remove the sentence or say “I don’t know”

    The whole pipeline in about 70 lines of PyTorch, deterministic and runnable on a CPU. The embedder is a stand-in (hashed character trigrams with a fixed random projection) so the code needs no download; replace embed with a real embedding model in practice.

    import math, re, torch
    torch.manual_seed(0)
    
    docs = {"manual.txt": "To reboot the X200, hold the power button for ten seconds. "
            "Error E-4012 means the firmware update failed. Download the firmware again and reinstall it. "
            "Fault E-4021 means the fan is blocked. Clean the air vent.",
            "warranty.txt": "The router warranty covers hardware faults for two years from purchase. "
            "The X200 has no battery. It needs wall power to run."}
    
    # 1) chunking: whole sentences, at most C words per chunk
    def chunk(text, C=14):
        sents, out, cur = re.split(r"(?<=\.)\s+", text.strip()), [], []
        for s in sents:
            if cur and len(" ".join(cur + [s]).split()) > C:
                out.append(" ".join(cur)); cur = []
            cur.append(s)
        return out + ([" ".join(cur)] if cur else [])
    chunks = [(src, c) for src, t in docs.items() for c in chunk(t)]
    tok = lambda s: re.findall(r"[a-z0-9]+(?:-[a-z0-9]+)*", s.lower())
    
    # 2) sparse index: BM25, formulas (152.5) and (152.6)
    D = [tok(c) for _, c in chunks]
    vocab = sorted({w for d in D for w in d}); wid = {w: i for i, w in enumerate(vocab)}
    tf = torch.zeros(len(D), len(vocab))
    for i, d in enumerate(D):
        for w in d: tf[i, wid[w]] += 1
    dl = tf.sum(1); avgdl = dl.mean(); N = len(D)
    df = (tf > 0).sum(0).float()
    idf = torch.log(1 + (N - df + 0.5) / (df + 0.5))
    def bm25(q, k1=1.2, b=0.75):
        ids = [wid[w] for w in set(tok(q)) if w in wid]
        f = tf[:, ids]
        return (idf[ids] * f * (k1 + 1) / (f + k1 * (1 - b + b * dl[:, None] / avgdl))).sum(1)
    
    # 3) dense index: a stand-in embedder (hashed character 3-grams, fixed random projection).
    #    In a real system call your embedding model here, the same one for chunks and queries.
    P = torch.randn(4096, 64)
    def embed(texts):
        X = torch.zeros(len(texts), 4096)
        for i, t in enumerate(texts):
            t = f"  {t.lower()} "
            for j in range(len(t) - 2):
                X[i, sum(map(ord, t[j:j + 3])) * 2654435761 % 4096] += 1
        return torch.nn.functional.normalize(X @ P, dim=1)       # unit length: dot = cosine (152.4)
    E_chunks = embed([c for _, c in chunks])
    
    # 4) hybrid retrieval with reciprocal rank fusion, formula (152.7)
    def rrf(*scores, k=60, top=3):
        fused = torch.zeros(N)
        for s in scores:
            order = torch.argsort(s, descending=True, stable=True)
            fused[order] += 1.0 / (k + torch.arange(1, N + 1))
        return torch.argsort(fused, descending=True, stable=True)[:top].tolist()
    
    # 5) context assembly with numbered sources, then the prompt for the LLM
    def build_prompt(q, top=3):
        ids = rrf(bm25(q), (embed([q]) @ E_chunks.T)[0], top=top)
        ctx = "\n".join(f"[{n}] ({chunks[i][0]}) {chunks[i][1]}" for n, i in enumerate(ids, 1))
        return ("Answer using only the sources below. Cite them like [1]. "
                "If the answer is not in the sources, say you do not know.\n\n"
                f"Sources:\n{ctx}\n\nQuestion: {q}\nAnswer:"), ids
    
    print(len(chunks), "chunks")                     # 5 chunks
    prompt, ids = build_prompt("what does error E-4012 mean")
    print(ids)                                       # [1, 0, 2]: the E-4012 chunk first
    print(prompt)                                    # the prompt shown above
    
    # 6) a cheap citation check on the model's answer: every [n] must point to a real source
    answer = "E-4012 means the firmware update failed; reinstall the firmware [1]. See also [7]."
    cited = [int(n) for n in re.findall(r"\[(\d+)\]", answer)]
    print("bad citations:", [n for n in cited if not 1 <= n <= len(ids)])   # [7]

    RAG vs long context vs fine-tuning

    There are three ways to give a model knowledge it does not have. They solve different problems, and good systems often combine them.

    • RAG: search, then put a few chunks in the prompt. Knowledge stays outside the model, can be updated in seconds, can be filtered per user, and can be cited.
    • Long context: put the whole collection (or a whole document) in the prompt, and let attention find the answer. No retriever to tune, nothing can be “not retrieved”. But every question pays for reading all of it, and it only works when the collection fits in the context window.
    • Fine-tuning: train the model on the documents or on question-answer pairs, so the knowledge goes into the weights. Good for behavior: a format, a style, a domain’s language, a skill. Poor for facts that change or must be cited. Ovadia et al. compared unsupervised fine-tuning and RAG for adding knowledge and found that RAG was better, both for facts seen in pretraining and for new facts. [Certain] See session 57 for how fine-tuning is done cheaply.

    To compare RAG and long context we need the cost of reading a prompt (prefill). For a model with \(P\) weights in its layers, \(L\) layers and attention width \(d\), reading \(n\) tokens costs about

    \[ F(n) \approx 2 P n + 2 L d\, n^2 \tag{152.12} \]

    The first term is the weight multiplications (2 FLOPs per weight per token). The second is causal attention: for each layer, \(QK^\top\) and the product with \(V\) cost \(2 n^2 d\) each over all pairs, and causality halves it. The KV cache keeps \(2 L \cdot n_{kv} \cdot d_{\text{head}}\) numbers per token.

    Worked example: Llama 3.1 8B, a 100,000-token collection

    Llama 3.1 8B has 32 layers, \(d = 4096\), 8 KV heads of size 128, and a 131,072-token context window. [Certain] Its 32 layers hold \(P = 6.98 \times 10^9\) weights (the other \(1.05 \times 10^9\) are the input embedding and the output layer).

    Long context, \(n = 100{,}000\): \(F = 2 \times 6.98\times10^9 \times 10^5 + 2 \times 32 \times 4096 \times 10^{10} = 1.40\times10^{15} + 2.62\times10^{15} = 4.0 \times 10^{15}\) FLOPs per question. Attention is already the larger part. The KV cache is \(2 \times 32 \times 8 \times 128 \times 2 = 131{,}072\) bytes per token in BF16, so 13.1 GB for this one prompt, and every generated token must read all 13.1 GB.

    RAG, \(n = 2{,}350\) (from 152.11): \(F = 3.4 \times 10^{13}\) FLOPs, about 117 times less, and a KV cache of 0.31 GB.

    Long context with prefix caching (the collection’s KV cache is computed once and reused, see session 134): a 50-token question then costs only \(2P \cdot 50 + 4 L d \cdot 50 \cdot 10^5 = 3.3\times10^{12}\) FLOPs, but the 13.1 GB cache must stay in GPU memory, and decoding still reads all of it for every token.

    RAGlong context
    Figure 6. Cost per question for Llama 3.1 8B with formula (152.12): prefill compute and KV-cache memory, on a log scale. RAG uses 200 instruction tokens, a 50-token question and \(k\) chunks of \(C\) tokens plus 20 label tokens each. Long context reads the whole collection plus the same instructions and question.
    How to read Figure 6

    Each bar is one cost on a log scale, so one grid step is a factor of 10. Grow the collection: the RAG bars do not move, because RAG cost depends on \(k \cdot C\), not on the collection size. The long-context bars grow, the attention part as the square of the length, and above 131,072 tokens long context is impossible for this model. Turn on prefix caching: long-context compute per question drops below RAG (only the question is new), but the memory bar stays: the cache must live on the GPU for as long as you want to reuse it. Li et al. (2024) found long context better than RAG on average when the model is strong and cost is not a concern, and RAG far cheaper; they route each question to one or the other. [Certain]

    RAGLong contextFine-tuning
    Fresh knowledgeYes: re-index a document in secondsYes: change the promptNo: retrain for every change
    Private, per-user accessYes: filter chunks by permissionsYes, if the prompt is built per userHard: all users share the weights
    CitationsNatural: each chunk has a sourcePossible, less precise in very long promptsNo source to point to
    Collection sizeAny (millions of chunks)Up to the context windowAny, but facts are learned poorly
    Cost per questionLow: a few thousand tokensHigh; lower with prefix caching, but large memoryLowest at query time
    Main failureThe right chunk is not retrievedLost in the middle; distractorsHallucinated or outdated facts
    Best forLarge, changing, private, cited knowledgeOne long document; cross-document reasoning over a small setFormat, style, domain language, skills

    A common practical answer: RAG for the knowledge, a light fine-tune (or just good prompts) for the behavior, and long context when a question really needs a whole document, for example “summarize this contract”. The retrieved context can also be long: retrieving 30 chunks into a 32k-token window is a mix of both ideas. Session 160 puts the pipeline together on real data.

    Where this is used

    ApplicationWhat is retrievedSpecial care
    Enterprise assistants (“chat with our wiki”)Wiki pages, tickets, PDFs, e-mailsAccess rights per chunk; many document formats; stale pages
    Customer support botsManuals, help articles, past solved ticketsProduct codes and error numbers: hybrid search matters (Figure 4)
    Coding assistantsFiles, functions and docs of the repositoryChunk by function or class, not by token count; keep file paths as metadata
    Legal, medical and finance researchContracts, case law, guidelines, filingsCitations must be exact and checked; dates and versions matter
    Search engines with generated answersWeb pages from a live search indexFreshness; untrusted text (prompt injection); many conflicting sources
    Video-RAG and video question answeringClips, keyframes, transcripts (ASR) and captions with timestampsA chunk is a time segment; the citation is a timestamp (key-moment detection); see session 210
    Video retrieval and fingerprintingClip embeddings; near-duplicate fingerprintsThe same two-stage idea: cheap embedding search, then a precise matcher on the top candidates
    Multimodal RAG over documentsPage images, figures, tablesEmbed pages as images or parse them to text first; see session 219

    Common mistakes

    • Debugging the LLM when retrieval is broken. First check whether the right chunk was in the prompt at all. Measure retrieval (Recall@k) and generation separately (session 153).
    • Chunks without context. “It needs wall power” is useless alone. Add the title and section heading to the chunk text, and keep metadata for citations and filters.
    • Cutting tables, lists and code in the middle. Use structure-aware splitters; a half table is worse than no table.
    • Dense search only. Codes, names and rare terms get lost. Add BM25 and fuse with RRF; it costs little.
    • Mixing embedding models or forgetting prefixes. Queries and chunks must be embedded by the same model version, with the prefixes it expects. A model upgrade means re-embedding everything.
    • Too many chunks in the prompt. More context is not always better: distractors and the lost-in-the-middle effect can lower accuracy. Rerank and keep few, good chunks.
    • Trusting citations without checking. Validate that cited sources exist and support the sentence.
    • Filtering permissions after retrieval, or not at all. Filter inside the search, so a forbidden chunk can never reach the prompt or the answer.

    Interview questions

    Why use RAG instead of relying on what the model learned?basic
    The model’s knowledge is frozen at its training cutoff, never included private documents, and has no sources. RAG retrieves relevant chunks at question time and puts them in the prompt, so answers can use fresh and private knowledge and cite it. Updating knowledge means re-indexing a document, not retraining. It also reduces (but does not remove) hallucination, because the model can copy from the source instead of recalling from its weights.
    Walk me through a RAG pipeline end to end.basic
    Offline: parse documents, split into chunks with metadata, embed each chunk, build a vector index and a BM25 inverted index. Online: embed the question, retrieve top K from both indexes (with permission filters), fuse with RRF, rerank the K candidates with a cross-encoder, keep the top 5 or so, deduplicate, order and label them, build a prompt that asks for an answer only from the sources with citations, generate, then validate the citations. Evaluate retrieval and generation separately.
    How do you choose chunk size and overlap?core
    Small chunks give precise embeddings but lose context; large chunks keep context but dilute the embedding and use more prompt budget. Start around 200 to 800 tokens with 10 to 20% overlap, split at structure (sections, paragraphs, sentences), and add title and heading. With fixed windows, overlap \(O \ge L - 1\) guarantees that a fact of \(L\) tokens is never cut, at a storage cost of \(C/(C-O)\). Then tune on a set of real questions by measuring Recall@k, because the best value depends on the documents and the embedding model.
    Explain BM25. What do \(k_1\) and \(b\) do?core
    BM25 sums, over the question’s terms, IDF (rare words count more) times a saturating function of the term frequency, normalized by document length. \(k_1\) controls saturation: small \(k_1\) means a second occurrence adds little; the term part is bounded by \(k_1 + 1\). \(b\) controls length normalization: \(b = 1\) fully divides by relative length, \(b = 0\) ignores length. Common defaults are \(k_1 = 1.2\), \(b = 0.75\). It needs no training and is strong on exact terms.
    Why hybrid search, and why RRF rather than adding scores?core
    Dense search handles paraphrase but misses rare exact strings (codes, names); BM25 is the opposite, so their errors are different and fusion is more robust. BM25 scores and cosines are on different, query-dependent scales, so adding them needs normalization and a tuned weight. RRF uses only ranks, \(\sum 1/(k + \text{rank})\) with \(k = 60\), needs no calibration, and rewards documents that both lists rank highly. Weighted fusion can be better when tuned, but is more fragile.
    Bi-encoder vs cross-encoder: what is the difference and why use both?core
    A bi-encoder embeds question and chunk separately, so chunk vectors are precomputed and search over millions is fast, but the two texts never interact. A cross-encoder reads them together with full attention and gives a more accurate score, but needs a forward pass per pair at query time. So use the bi-encoder (plus BM25) to get K = 50 to 100 candidates, and the cross-encoder to reorder them. The reranker cannot recover what the first stage missed: Recall@n after reranking is at most Recall@K of the first stage.
    How do you make answers citable, and how do you check the citations?core
    Keep a stable id and source metadata (document, page, section, date) for every chunk; number the chunks in the prompt; instruct the model to cite each claim with the number and to say it does not know when the sources do not answer. Then check: every cited number must exist, and the cited chunk must support the sentence, checked with an NLI model or an LLM judge. Remove or regenerate unsupported sentences, and show the exact passage in the interface.
    The index has 50 million chunks with 1,024-dimensional embeddings. How much memory, and how do you reduce it?core
    \(50\times10^6 \times 1024 \times 4\) bytes = 204.8 GB in FP32, 102.4 GB in FP16, 51.2 GB in INT8. Product quantization to 64 bytes per vector gives 3.2 GB, at some loss of recall that a reranker (or re-scoring with full vectors) can recover. Other options: smaller embedding dimensions (some models are trained so the first dimensions can be kept alone), sharding over machines, or HNSW/IVF indexes for speed. See the vector search session.
    RAG, long context or fine-tuning: how do you decide?advanced
    Fine-tuning changes behavior (format, style, skills) and is poor at injecting facts that change or must be cited; Ovadia et al. found RAG better for knowledge injection. Long context is simplest and can reason across a whole document, but every question pays prefill over the full context (about \(2Pn + 2Ldn^2\)), it is limited by the window, and very long contexts lose information in the middle. Prefix caching cuts compute but keeps a large KV cache in memory (13 GB for 100k tokens on Llama 3.1 8B). RAG scales to any collection, is cheap per question and supports permissions and citations, but fails when retrieval fails. Many systems use RAG for knowledge, light tuning for behavior, and long context for single-document tasks, or route between them per question (Li et al., Self-Route).
    Users say the answers are often wrong. How do you debug the RAG system?advanced
    Split the failure. Collect failing questions and label the correct source chunk. (1) Is the answer in the collection at all, and was it parsed correctly? (2) Is the chunk in the first-stage top K (Recall@K)? If not: chunking, embedding model, missing BM25, query wording. (3) Is it in the final top n after reranking? If not: reranker or K. (4) Was it in the prompt but ignored or contradicted? Then it is generation: ordering, too many distractors, the instructions, or the model. Fix the earliest broken stage first, and track each stage’s metric separately over time.
    How do you handle document updates, deletions and access control?advanced
    Give every chunk a stable id tied to its document and version. On update, delete the document’s old chunks from both indexes and insert the new ones; deletions must also remove cached answers that cite them. Store the access list as metadata and filter inside the search (pre-filtering), never only after generation. Record the embedding model version; changing it requires re-embedding the whole collection, often by building a new index in parallel and switching over.

    Exercises

    1. A 3,000-token document is chunked with \(C = 512\) and \(O = 128\). How many chunks, and what is the storage factor?
    2. Answers in your documents are at most 60 tokens long. What is the smallest overlap that guarantees no answer is ever cut by a fixed window? Check the idea with \(L = 20\) in Figure 2.
    3. With RRF and \(k = 60\): chunk A is ranked 3rd by BM25 and 1st by dense search; chunk B is 2nd in both lists. Which wins?
    4. In a collection of \(N = 8\) chunks, compute the Lucene IDF (152.6) of a term that appears in 1, 4 and 8 chunks.
    5. Your collection has 400,000 tokens and the model’s window is 131,072 tokens. Can you use long context? How many prompt tokens does RAG use with \(k = 8\) chunks of 300 tokens (200 instruction tokens, a 50-token question, 20 label tokens per chunk)?
    6. A 110M-parameter cross-encoder reranks \(K = 50\) candidates of 300 tokens each (question included). How many FLOPs per question?
    7. In Figure 5 with the default settings, find the \(K\) where reranked Recall@5 is highest. Explain why it does not keep rising.
    Answerscheck
    1. \(\lceil (3000 - 128)/384 \rceil = \lceil 7.48 \rceil = 8\) chunks; storage factor \(512/384 = 1.33\). 2. \(O \ge L - 1 = 59\) tokens; in Figure 2 (\(L = 20\) words) every fixed-window setting with \(O \ge 19\) keeps the answer whole. 3. A: \(1/63 + 1/61 = 0.032266\); B: \(2/62 = 0.032258\). A wins, by a tiny margin: RRF is nearly indifferent between “very good in one list” and “good in both”. 4. \(n_t = 1\): \(\ln(1 + 7.5/1.5) = \ln 6 = 1.792\); \(n_t = 4\): \(\ln(1 + 4.5/4.5) = \ln 2 = 0.693\); \(n_t = 8\): \(\ln(1 + 0.5/8.5) = 0.057\), small but still positive. 5. No: 400,000 tokens do not fit into 131,072, so you would need RAG (or splitting the work). RAG: \(200 + 50 + 8 \times 320 = 2{,}810\) tokens. 6. \(50 \times 2 \times 110\times10^6 \times 300 = 3.3 \times 10^{12}\) FLOPs. 7. With \(\Delta_1 = 2.5\), \(\Delta_2 = 3.5\), Recall@5 rises up to about \(K = 100\) to 200 (0.86 to 0.90) while the ceiling rises faster (0.90 to 0.955); the gap between the ceiling and the reranked line grows because each extra candidate is one more chance for a wrong chunk to beat the correct one, and the cost grows linearly in \(K\). In practice choose the smallest \(K\) near the flat part.

    Key takeaways

    • RAG gives an LLM knowledge that is fresh, private and citable: retrieve the best chunks, put them in the prompt, answer from them (152.1).
    • The chunk is the unit of search, prompt and citation. Split at structure; overlap \(O \ge L - 1\) keeps facts of length \(L\) whole, at storage cost \(C/(C-O)\) (152.2, 152.3).
    • Dense search (152.4) handles meaning; BM25 (152.5, 152.6) handles exact words. Hybrid search with RRF (152.7) is robust and needs no tuning.
    • Two stages: retrieve \(K\) = 50 to 100 cheaply for recall, rerank with a cross-encoder for precision (152.9); the reranker cannot exceed first-stage Recall@K (152.10).
    • Assemble a short, ordered, labeled context (152.11), ask for citations, and check them.
    • RAG is about 100 times cheaper per question than reading a 100k-token collection (152.12); fine-tuning is for behavior, not facts.

    Key formulas

    \[ p(y\mid x) \approx \sum_{z} p_\eta(z\mid x)\,p_\theta(y\mid x,z), \qquad n_{\text{chunks}} = \left\lceil \tfrac{N-O}{C-O} \right\rceil, \qquad O \ge L - 1 \]
    \[ s_{\text{BM25}} = \sum_{t\in q} \operatorname{IDF}(t)\,\frac{f\,(k_1+1)}{f + k_1(1-b+b\,|d|/\text{avgdl})}, \qquad s_{\text{RRF}}(d) = \sum_r \frac{1}{k + \operatorname{rank}_r(d)} \]
    \[ \text{Recall@}n_{\text{rerank}} \le \text{Recall@}K_{\text{first}}, \qquad F(n) \approx 2Pn + 2Ldn^2 \]

    References for this session

    1. Lewis et al. (2020). Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks
    2. Robertson & Zaragoza (2009). The Probabilistic Relevance Framework: BM25 and Beyond
    3. Gao et al. (2023). Retrieval-Augmented Generation for Large Language Models: A Survey
    4. Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, chapter 11: Information Retrieval and RAG
    5. Karpukhin et al. (2020). Dense Passage Retrieval for Open-Domain Question Answering
    6. Liu et al. (2023). Lost in the Middle: How Language Models Use Long Contexts
    7. Reimers & Gurevych (2019). Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks
    8. Wang et al. (2022). Text Embeddings by Weakly-Supervised Contrastive Pre-training
    9. Malkov & Yashunin (2016). Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
    10. Johnson et al. (2017). Billion-scale similarity search with GPUs
    11. Khattab & Zaharia (2020). ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT
    12. Thakur et al. (2021). BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models
    13. Cormack, Clarke & Buettcher (2009). Reciprocal Rank Fusion outperforms Condorcet and individual Rank Learning Methods
    14. Nogueira & Cho (2019). Passage Re-ranking with BERT
    15. Li et al. (2024). Retrieval Augmented Generation or Long-Context LLMs? A Comprehensive Study and Hybrid Approach
    16. Ovadia et al. (2023). Fine-Tuning or Retrieval? Comparing Knowledge Injection in LLMs
    17. Luo et al. (2024). Video-RAG: Visually-aligned Retrieval-Augmented Long Video Comprehension