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
The Arm You Did Not Run: Learning an Architecture Under a Switching Cost
Four topics chose an architecture from a table of measured quality and cost — a deployment has no table, only the arm it ran, and once the choice must be learned rather than looked up the benchmark the whole arc optimized turns out to be beatable
Four topics have now chosen a retrieval architecture, and each removed one assumption from the one before it: what six named patterns buy, what the choice depends on, that the workload is estimated rather than known, that it moves. All four share an assumption none of them names — that the table of quality and cost is available to read. It is not. A deployment runs one architecture per query and observes that row only; the other five entries in every column are counterfactual and stay that way, so the table is not an input to the decision but something the decision estimates, one query at a time, paying for every query it spends on a bad arm. Making the table unknown changes three things the arc could not have seen. An exploring policy achieves negative regret against the best fixed architecture in hindsight — not by beating an oracle, but because drift makes that benchmark weak, and the fixed-arm framing the whole arc optimized was leaving value uncollected. The previous topic's instrument, a constant margin a challenger must clear, does not need retuning so much as replacing: across its entire range the differences vanish into noise, because a constant cannot express how well any particular arm is currently known. And a switching cost turns out to be a tax on exploration specifically, levied in proportion to how much a policy explores, with a price past which the rule that knows least wins because it has stopped paying to find out.
When to Switch: Architecture Choice for a Workload That Moves
Three topics chose an architecture for a workload that was allowed to be unknown but not to move — once it moves, the question stops being which architecture and becomes when to change, and the answer is a band rather than a boundary
Three topics have now chosen a retrieval architecture. The first measured what six named patterns buy and where each fails; the second showed the choice depends on a workload mixture, a price ratio and an amortization horizon; the third unfixed the mixture and made it something you estimate. All three left one assumption standing: that the workload sits still. It does not, and once it moves, switching architecture costs something real, so the question becomes when. The answer is a control band — hold the incumbent until a rival beats it by a margin — and the measurement that gives the topic its point is what the band is actually for. Along a path whose genuinely best architecture changes exactly once, a rule that re-decides from each window's traffic changes its mind more than twelve times, and nearly all of that is the estimator rather than the workload. Widening the band suppresses those switches and, at the same time, lowers regret: the discarded switches were not merely expensive, they were wrong. The band that does this best is interior on every deployment simulated, and it is already wide when switching is free — so hysteresis is not principally about amortizing an expensive change, it is about filtering an estimator. The topic closes on the gap between detecting and deciding, where a drift detector and a switching policy are shown failing on the same streams in opposite directions.
The Workload You Do Not Know: Choosing an Architecture from an Estimate
The previous topic read the architecture off a partition of the workload simplex and treated the workload as given — it is estimated, and a partition is exactly the structure that punishes estimation error hardest where it is hardest to avoid
The previous topic ended with a partition: fix the price and the deployment size, look up your workload mixture on the simplex, and read off the architecture. It treated the mixture as known. You do not know it — you estimate it from traffic, and a partition is precisely the structure that turns a small estimation error into a completely different recommendation, because the map from workload to architecture is piecewise constant. Estimation error is therefore free in the interior of a cell and maximally expensive at a boundary. Three decision rules are compared, and one of them turns out not to be a rule at all: because utility is linear in the workload, expected utility over any posterior equals utility at the posterior mean, so the Bayes rule is the plug-in rule applied to a shrunk estimate and nothing more. That leaves the genuine contrast, between committing to the estimate and hedging against what it might be hiding. The hedge is not a safe default — deep inside a cell it is that cell's own arm — and it is not free either: it is a bet that the traffic is more central than the data says, and the bet loses, by more than it wins elsewhere, when the truth sits in a narrow cell just past a boundary.