formalRAG
The mathematics of retrieval-augmented generation
Theorem-bearing explainers on retrieval geometry, approximate nearest-neighbor algorithms, probabilistic IR, ranking, and the information theory of RAG — each with rigorous mathematics, interactive visualizations, and working code.
Latest Topics
Adaptive Retrieval Routing: Choosing a Strategy per Query
The published gate decided whether to answer; this one decides how hard to try — a router over retrieval strategies whose optimum is Chow's rule with more than two actions, whose achievable region is a convex hull, and whose entire possible gain is a Jensen gap that vanishes exactly when the strategies never change places
Selective generation ended with a binary gate: emit the answer or abstain, cut at Chow's threshold. This topic is that gate with more than two actions. A router chooses among retrieval strategies — answer from the query alone, retrieve once, or iterate — using only features available before any retrieval fires, and the pointwise optimum is the same argmax Chow's rule was a special case of, reducing to it exactly when the actions are emit and abstain. Sweeping the cost weight traces a family of policies whose convex hull is the achievable cost–quality region, and the most any router can win over the best single strategy is a Jensen gap between the expected maximum and the maximum expectation — strictly positive if and only if the strategies actually change places across queries. The honest half is what a realizable router collects: on a corpus where the oracle gap is positive at every operating point, a fitted router captures 58% of it at one, 3.5% at another, and less than nothing at a third, where it loses to always-retrieving-once. Only one of four gains is distinguishable from zero. A gap that exists is not a gap you can collect.
Cross-Encoders and the Reranking Cascade
A dual encoder's separable score has a rank-d ceiling, and a learned bilinear q⊤Wd does not escape it — S = QWG⊤ is still rank at most d. Only a nonlinear joint encoder h([q;d]) breaks the wall, at a cost that forbids it from ever being the first stage. So the cross-encoder becomes a reranker: retrieve K cheaply, rescore K expensively. An oracle rerank is recall-monotone and pinches recall@1 to the candidate pool's recall@K, but a lossy cross-encoder can dip below the first stage by being confidently wrong
The dual-encoder topic kept invoking the cross-encoder as the rank-free, un-precomputable counterpoint; this topic spends that power. A cross-encoder scores a fused pair h([q;d]), letting query and document attend at every layer, and the first result is why the nonlinearity is the whole point: a learned bilinear form q-transpose-W-d does NOT escape the rank ceiling, because S = QWG-transpose = (QW)G-transpose is still a product through a d-dimensional bottleneck and has rank at most d. Only a nonlinear joint encoder has no such ceiling, so it escapes the sign-rank wall the embedding-dimension topic proved — and pays for it with a joint forward pass per pair, which forbids precomputation and makes it unusable as a first stage. The architecture is therefore a retrieve-then-rerank cascade: a cheap dual encoder retrieves a candidate pool of size K, the cross-encoder rescores only those K. We prove the cascade's two governing facts. First the recall pinch: an oracle rerank of the top-K makes recall@1 equal the candidate pool's recall@K, so the reranker can never recover a true neighbor the first stage dropped — the cost model c_ret + K times c_ce against the brute corpus-size times c_ce sets the Pareto knee. Second, oracle rerank is recall-monotone in K because a larger pool is a superset, but a lossy cross-encoder can dip below the first stage by being confidently wrong, demoting a true top-1. We close on expressivity versus generalization: the cross-encoder's extra capacity overfits small training sets where the dual encoder's inner-product inductive bias wins, the up-link to VC dimension. A laboratory shows the rank-ceiling split, the cascade frontier and its cost knee, and the per-query rerank buckets with their hard-negative fixes and confident-wrong dips; a tested notebook owns every number; and the finance thread is the production reranker that separates same-sector hard negatives a single embedding confuses.
Cross-Modal Contrastive Alignment and the Modality Gap
Train a text tower and a chart tower with the same symmetric CLIP loss and the two modalities settle into disjoint cones on the sphere — a modality gap between the centroids that contrastive training shrinks but never quite closes. We prove the gap is the coherent, rank-one part of cross-modal misalignment (an orthogonal split L_align = gap² + dispersion) and that it is INVISIBLE to maximum-inner-product ranking: a shared offset is a per-query constant, so recall is exactly gap-invariant. The gap is a calibration artifact — it shifts absolute similarities, never the order — and lower training temperature preserves a larger residual gap.
A multimodal retrieval system trains two encoders — a text tower and a chart tower — with the same symmetric contrastive (CLIP) loss, so a text query can retrieve a chart of the same company. Even after training, the two modalities occupy disjoint cones on the sphere: a measurable modality gap between the text and chart centroids. This topic reads the gap three ways. First, an orthogonal decomposition: the cross-modal alignment loss splits exactly as L_align = gap² + dispersion, a Frobenius-Pythagoras decomposition of the per-pair difference matrix into its coherent rank-one part (the gap) and its incoherent complement, so the gap is bounded by the alignment loss and contrastive training can shrink the loss while a coherent gap survives. Second, the headline: the gap is invisible to maximum-inner-product ranking. Shifting one modality by the shared gap vector changes every cross-modal score by a per-query constant, leaving the argsort — and recall@k — exactly invariant, so the gap is a calibration artifact on absolute similarities, not a ranking defect. Cosine retrieval, which renormalizes, is the honest exception. Third, the cone effect: a deterministic full-batch descent on the symmetric loss closes the gap at moderate temperature, and lower temperature preserves a larger residual gap. The finance thread runs throughout: a desk embedding 10-K text and price charts of the same companies retrieves correctly through the gap but miscalibrates a fixed relevance threshold across it.