# 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.