Mathematical and systems primer for RAG

This appendix makes the assumptions behind common RAG components explicit. The equations are families, not claims that every implementation uses the same normalization or loss.

1. Sparse retrieval

Let $f(t,d)$ be term frequency, $n_t$ document frequency, $N$ corpus size, $|d|$ document length, and $\overline{|d|}$ average length. A common positive BM25 IDF and score are

\operatorname{IDF}(t)=\log\left(1+\frac{N-n_t+0.5}{n_t+0.5}\right),

s(q,d)=\sum_{t\in q}\operatorname{IDF}(t) \frac{(k_1+1)f(t,d)} {f(t,d)+k_1(1-b+b|d|/\overline{|d|})}.

The inverted index stores postings only for nonzero terms, making exact search efficient and incremental updates natural. Fields can have separate weights; filters can enforce tenant, time, document type, and authority before scoring.

Learned sparse models such as SPLADE replace observed term counts with sparse vocabulary weights predicted by a transformer. A FLOPS-like regularizer penalizes expected activation across the collection so postings remain usable. This gives semantic expansion without abandoning inverted-index infrastructure, but index size and latency are learned hyperparameters rather than fixed facts.

2. Dense dual-encoder retrieval

A dual encoder maps a query and passage independently:

u=E_Q(q),\quad v=E_D(d),\quad s(q,d)=u^\top v

or cosine similarity after normalization. Given a positive passage $d^+$ and negatives $\mathcal N$ , an InfoNCE-style loss is

\mathcal L_q=-\log \frac{\exp(s(q,d^+)/\tau)} {\exp(s(q,d^+)/\tau)+\sum_{d^-\in\mathcal N}\exp(s(q,d^-)/\tau)}.

In-batch positives from other questions provide many cheap negatives. Hard negatives from BM25, a previous dense model, or a cross-encoder teach distinctions near the decision boundary. False negatives are dangerous: a passage may be unlabeled but valid, so the loss pushes useful evidence away.

At serving time, maximum-inner-product or cosine search uses an approximate nearest-neighbor index. Important parameters include vector dimension, quantization, graph/list construction depth, search probes, rerank candidate count, and exact-verification stage. Approximation error must be measured by comparing ANN with exact search on a representative subset. The embedding revision is part of the index schema; changing it normally requires re-encoding.

Single-vector retrieval compresses an entire passage into one point. It handles paraphrase but can discard rare terms, fine-grained relations, and multiple topics. Domain length, language, instruction prefix, normalization, and training negatives can change ranking substantially.

3. Cross-encoders and late interaction

A cross-encoder jointly processes $[q;d]$ and returns a relevance or utility score:

s(q,d)=w^\top h_{\text{CLS}}([q;d]).

It models every query-document interaction but cannot precompute a document score independent of the query. It therefore reranks tens or hundreds of candidates rather than millions.

Late-interaction systems occupy the middle. ColBERT retains contextual token vectors and uses

s(q,d)=\sum_{i=1}^{|q|}\max_{1\le j\le |d|} E_Q(q_i)^\top E_D(d_j).

Document token vectors are precomputable; query-token maxima preserve detailed alignment. The cost is a multi-vector index. ColPali applies the same operation between query tokens and page-image patches.

A reranker for RAG should ideally predict downstream evidence utility, not only topical relevance. A passage can be relevant yet redundant, stale, contradictory, or too ambiguous to improve the answer. Utility labels can be defined by claim support or by the causal change in a fixed reader when a passage is included, but reader-specific labels may not transfer.

4. Latent-document generation

Let $z$ be a retrieved document and $y$ an answer. The ideal marginal is

p(y\mid x)=\sum_{z\in\mathcal C}p_\eta(z\mid x)p_\theta(y\mid x,z).

The corpus is too large, so RAG truncates to top $k$ . RAG-Sequence assumes one latent document for the full sequence:

p(y\mid x)\approx\sum_{z\in\operatorname{TopK}(x)}p_\eta(z\mid x) \prod_t p_\theta(y_t\mid x,z,y_{<t}).

RAG-Token moves the document sum inside the token product:

p(y\mid x)\approx\prod_t\sum_{z\in\operatorname{TopK}(x)}p_\eta(z\mid x) p_\theta(y_t\mid x,z,y_{<t}).

Negative log likelihood sends learning signal to the query encoder when a retrieved document makes the target likely. It does not establish that the document is factually supporting: spurious correlation or parametric memory can produce the answer. The top- $k$ operator is discrete; documents outside it receive no gradient. A stale fixed document index means the updated query encoder scores vectors produced by an older document encoder.

5. Multi-passage fusion

Naively concatenating $k$ passages of length $L$ into one transformer encoder gives self-attention complexity approximately $O((kL)^2)$ . FiD encodes each passage independently, about $O(kL^2)$ , concatenates encoder states, and lets the decoder cross-attend over all of them. This makes 100 passages feasible but decoder attention and memory still grow with total encoded length.

Reader-to-retriever learning uses a teacher distribution $p_T(d\mid q,a)$ from reader attention or per-document answer likelihood and minimizes

\mathcal L_{\text{distill}}= \operatorname{KL}(p_T(d\mid q,a)\,\|\,p_\eta(d\mid q)).

Attention is easy to extract but not necessarily causal. Per-document answer likelihood is closer to utility but can reward answer leakage. Stop-gradient is often used so the auxiliary retriever signal does not distort the reader.

6. Query transformation and multi-query fusion

Query rewriting seeks a transformation $q'=g(q,h)$ , possibly conditioned on conversation history $h$ , that improves evidence retrieval. HyDE instead generates a hypothetical answer document $\tilde d$ and retrieves with $E_D(\tilde d)$ . Multi-query methods generate $q_1,\ldots,q_m$ , search each, and fuse candidates.

Generated expansions can introduce detail that was never requested. Evaluate intent preservation, source recall, latency, model calls, and sensitivity to sampling. Keep the original query in the fusion so generated text cannot erase rare exact terms. Reciprocal-rank fusion avoids incompatible score scales:

s_{\text{RRF}}(d)=\sum_{r=1}^{m}\frac{w_r}{K+\operatorname{rank}_r(d)}.

The constant $K$ controls how quickly rank contributions decay. RRF is robust but discards score margins; learned calibration may exploit margins at the cost of more labels and drift.

7. Context selection as constrained optimization

Given candidates $D$ , budget $B$ , length $\ell(d)$ , and utility $u(d\mid q,S)$ conditional on already selected evidence $S$ , context construction resembles a knapsack/submodular problem:

\max_{S\subseteq D}\sum_{d\in S}u(d\mid q,S) \quad\text{s.t.}\quad\sum_{d\in S}\ell(d)\le B.

Maximal marginal relevance is a simple greedy surrogate:

d^*=\arg\max_{d\notin S} \lambda\operatorname{rel}(q,d) -(1-\lambda)\max_{s\in S}\operatorname{sim}(d,s).

Real constraints add per-document limits, permissions, temporal validity, modality/token cost, source diversity, conflict groups, and minimum complete evidence chains. The optimal $k$ depends on the reader: a stronger long-context model may tolerate more noise, while another loses relevant evidence in the middle. Report token budget and evidence order with every result.

8. Graph and hierarchical retrieval

Graph retrieval transforms chunks into nodes and relations. With adjacency matrix $P$ , personalization vector $e_q$ , and restart probability $1-\alpha$ , Personalized PageRank solves

\pi=(1-\alpha)e_q+\alpha P^\top\pi.

Query-linked seed entities spread relevance over multi-hop neighbors. Graph quality depends on extraction, canonicalization, edge direction/type, and source/version lineage. A high PageRank score is associative relevance, not a proof that a path constitutes valid reasoning.

Hierarchical indexes cluster leaf chunks and create summaries or community reports. They reduce global-synthesis context but form a lossy derived corpus. Every summary needs lineage to children; inserts, corrections, and deletions must invalidate ancestors. Compare graph/hierarchy against a text-retrieval and map-reduce baseline under equal generation budget.

9. Retrieval policy and reinforcement learning

An agentic retriever treats search as sequential decision making. At state $s_t=(q,h_t,o_{1:t})$ , action $a_t$ can reason, rewrite, choose a source, retrieve, answer, or stop. The trajectory objective is

J(\pi)=\mathbb E_{\tau\sim\pi} \left[R_{\text{answer}}(\tau) +\beta\sum_t R_{\text{process}}(s_t,a_t) -\lambda\sum_t C(a_t)\right].

Answer-only rewards are sparse and allow spurious evidence, fabricated tags, or excessive search. Process rewards for relevance, information gain, redundancy, citation, and correct stopping add supervision but can themselves be gamed. Retrieved observations should be masked from the policy loss so the model is not trained to reproduce environment text as its own action.

Evaluate action accuracy, over-search, under-search, mean/tail calls, final answer, evidence chain recall, citation entailment, and policy transfer after changing corpus, retriever, or generator. Enforce hard tool, token, time, cost, and source limits outside the learned policy.

10. Calibration, abstention, and risk

Suppose a system emits confidence $c(x)$ and answers only if $c(x)\ge\tau$ . Coverage is the fraction answered; selective risk is error among answered examples. Plot risk against coverage rather than selecting one threshold on the test set.

RAG needs at least two confidences:

answer confidence: is the candidate answer likely correct?
context sufficiency: can the permitted current evidence support it?

A model can know a fact parametrically while evidence is insufficient for a required citation; or evidence can be sufficient while the model is uncertain. Conflicts add source authority and temporal validity. Calibrate by slice, especially unanswerable, long-tail, dynamic, and adversarial cases.

Conformal risk control can bound an aggregate bounded loss at a chosen confidence under exchangeability or explicitly modeled shift. Such a bound is only as broad as its loss and assumptions; it does not authenticate sources or prevent prompt injection.

11. Claim-level attribution

Let generated atomic claims be $A$ , reference claims $Y$ , and citations $C(a)$ for claim $a$ . Distinct measurements are

\operatorname{CitationCompleteness} =\frac{|\{a\in A:C(a)\ne\varnothing\}|}{|A|},

\operatorname{CitationEntailment} =\frac{\sum_{a\in A}\sum_{c\in C(a)}\mathbf 1[c\Rightarrow a]} {\sum_{a\in A}|C(a)|}.

Completeness can be high while entailment is low; entailment can be high while the source is malicious or outdated. Also record source authority, version, valid time, exact span/page/region, and viewer permission. Automatic NLI or LLM judges need calibration against human labels and adversarial citation cases.

12. End-to-end error accounting

A useful failure tree is

P(\text{success})\approx P(\text{evidence exists and is allowed}) P(\text{retrieved}\mid\text{exists}) P(\text{selected}\mid\text{retrieved}) P(\text{used correctly}\mid\text{selected}) P(\text{attributed}\mid\text{used}).

The terms are not independent, so this is diagnostic rather than a literal factorization. It prevents one answer metric from hiding the causal stage. Run the generator on oracle evidence, the reranker on oracle candidates, and the retriever with exact search. These counterfactuals estimate headroom and locate the next useful investment.

The final deployment choice is a Pareto frontier across claim quality, retrieval/citation coverage, abstention, source/permission/freshness validity, security, p95 latency, memory, update time, energy, and cost per correct supported answer.

13. Query likelihood and pseudo-relevance feedback

With Dirichlet smoothing, a document language model scores

\log p(q\mid d)=\sum_{t\in q}f(t,q) \log\frac{f(t,d)+\mu p(t\mid\mathcal C)}{|d|+\mu}.

Large $\mu$ moves short-document estimates toward the collection language model. In relevance-model feedback, top documents $F$ define an expansion distribution

p(w\mid R)\propto\sum_{d\in F}p(d)p(w\mid d) \prod_{t\in q}p(t\mid d),

which is truncated to useful terms and interpolated with the original query. Feedback estimates corpus vocabulary but can drift when initial top documents are wrong. The correct experiment retains an original-query run and measures per-query relevant evidence gained and lost.

14. Learned sparse representation and execution cost

SPLADE-style vocabulary weight for dimension $j$ is often

w_j(x)=\max_i\log(1+\operatorname{ReLU}(z_{ij})).

Ranking is a sparse dot product. A batch FLOPS proxy is

R_{FLOPS}=\sum_j\left(\frac{1}{B} \sum_{i=1}^{B}w_j(x_i)\right)^2.

This penalizes vocabulary terms activated for many examples and thereby long posting lists. Query and document regularization have different consequences: query nonzeros determine how many lists are opened; document nonzeros determine index postings/bytes. The execution objective is not fully captured by vector L0/L1 alone because posting distribution, WAND upper bounds, and term correlation also affect latency.

15. Ranking and distillation losses

For scores $s^+,s^-$ , pairwise logistic loss is

L_{pair}=\log(1+e^{-(s^+-s^-)}),

and margin hinge is $\max(0,m-s^++s^-)$ . A listwise softmax with graded target distribution $p_T$ minimizes

L_{list}=-\sum_{d\in C}p_T(d\mid q) \log\frac{e^{s(d)/T}}{\sum_{d'}e^{s(d')/T}}.

Margin-MSE distillation matches differences rather than absolute scale:

L_{margin}=\left[(s_S^+-s_S^-)-(s_T^+-s_T^-)\right]^2.

LambdaRank-style methods weight pair gradients by the change in the target ranking metric such as $|\Delta\mathrm{nDCG}|$ . All depend on the candidate and judgment pool; incomplete qrels can make an unjudged relevant passage a strong negative.

16. Score fusion and calibration

After calibration or normalization, linear fusion is

s(d\mid q)=\sum_{r=1}^{m}w_r(q)\widetilde s_r(q,d).

CombSUM uses this with unit weights; CombMNZ multiplies the sum by the number of runs that retrieved $d$ . Per-run min-max normalization

\widetilde s=(s-s_{min})/(s_{max}-s_{min})

is sensitive to outliers and candidate depth. Z-score assumes a stable score distribution. Logistic/isotonic calibration estimates relevance probability on labeled data but must be refreshed after corpus/retriever changes. RRF avoids score calibration but discards score margins.

17. Product quantization and IVF

Product quantization partitions $x\in\mathbb R^d$ into $M$ subvectors and stores a codebook index $k_m(x)$ for each:

\hat x=[c_{1,k_1(x)},\ldots,c_{M,k_M(x)}].

Asymmetric query distance uses lookup tables:

\|q-\hat x\|^2=\sum_{m=1}^{M} \|q^{(m)}-c_{m,k_m(x)}\|^2.

An IVF index first assigns vectors to coarse centroid $a(x)$ . Query time selects nprobe centroids and searches only their posting lists, often with PQ codes and exact rescoring of finalists. Recall/latency/memory are controlled by centroid count, assignment multiplicity, nprobe, code size, and rerank depth.

18. HNSW and graph ANN complexity

HNSW samples a maximum layer for each point from an exponential distribution, connects approximate neighbors per layer, greedily descends sparse upper layers, then runs a bounded best-first search at layer zero. Important controls are

$M$ : maximum neighbor degree;
efConstruction: candidate width during insertion;
efSearch: candidate width during query.

Larger values generally improve empirical recall while increasing memory, build, and query work. Complexity is distribution/implementation dependent; common graph ANN methods have constructed linear-time worst cases. Report exact neighbor recall and qrel/answer effect under deployed filters rather than claiming a fixed asymptotic latency.

19. Set coverage and knapsack selection

Let information needs be $H$ , item $i$ cover need $j$ by $a_{ij}\in[0,1]$ , and cost $c_i$ . A budgeted coverage objective is

\max_{x_i\in\{0,1\}} \sum_j w_j\min\left(1,\sum_i a_{ij}x_i\right) -\rho\sum_{i<l}r_{il}x_ix_l \quad\text{s.t.}\quad \sum_i c_ix_i\le B.

This makes comparison/multi-hop retrieval explicit: several high-scoring items covering the same need are worse than a complementary set. Greedy marginal gain per cost is a practical approximation when the utility is monotone submodular; authority, conflict, and minimum-chain constraints can break those assumptions.

20. Temporal ranking and bitemporal validity

For query as-of time $t_q$ , document valid interval $[v_s,v_e)$ , observed time $o$ , and publication time $p$ , temporal compatibility may be

s_{valid}(t_q,d)=\mathbf 1[v_s\le t_q<v_e].

A composite score is

s(q,d)=s_{rel}(q,d)+\alpha s_{authority}(d) +\beta s_{valid}(t_q,d)-\gamma s_{stale}(q,d).

The stale term must be query-specific: recency is useful for current prices but wrong for historical law or evergreen definitions. Bitemporal storage retains both valid time and system/observed time so replay can reconstruct what the system could have known.

21. Cost, latency, and reliability models

Per-request cost decomposes

C=C_{embed}+C_{sparse}+C_{ANN}+C_{rerank} +C_{prompt}+C_{decode}+C_{tools}+C_{verify}.

End-to-end latency with concurrent retrieval branches is approximately

L=L_{pre}+\max_r L_{retrieve,r}+L_{fusion}+L_{rerank} +L_{context}+L_{generation}+L_{verify},

while iterative actions add sequential latencies. Queueing makes tail latency nonlinear near saturation, so component microbenchmarks do not sum to production p95/p99.

If stage conditional success probabilities are $p_i$ , a naive diagnostic upper bound is $\prod_i p_i$ , but errors are dependent. Use counterfactual oracles—gold corpus unit, exact search, oracle candidate ranking, gold context— to estimate each ceiling rather than assuming independence.