Curriculum Roadmap
A planned map of content areas. Published topics are linked; everything else is on the roadmap.
Explore the full dependency graph, or browse by track below.
Foundations
Retrieval Foundations
Track completeRetrieval as ranking by a relevance functional; the metric and inner-product structure of similarity; and the complexity-theoretic limits of exact search. The root of the dependency graph.
The Retrieval Problem: Relevance, Similarity, and the Geometry of Scores
Retrieval as ranking by a relevance functional — and the three similarity scores that agree on the sphere and diverge off it
Retrieval is ranking: given a query, score every document by a relevance functional rel(q, d) and return the top k, a set-valued operator on the resulting order. Because only the order matters, relevance is ordinal even though scores are cardinal — the ranking is invariant under any strictly monotone transform of the score, a fact we will lean on repeatedly. We then study the three similarity functions retrieval actually uses — Euclidean distance, the dot product, and cosine similarity — through the single identity ||a-b||^2 = ||a||^2 + ||b||^2 - 2<a,b>. On the unit sphere this identity collapses the three into one: ranking by Euclidean distance, by dot product, and by cosine all induce the same order. Off the sphere they diverge, because magnitude matters for the dot product but is quotiented away by cosine — the divergence that motivates normalization throughout the rest of the curriculum. We separate which of these are true metrics (Euclidean is; cosine distance violates the triangle inequality; the dot product is not a metric at all) because the triangle inequality is exactly the structure that tree- and graph-based approximate-nearest-neighbor indexes later exploit. The level sets make the picture geometric: equal-score loci are hyperplanes for the dot product, spheres for Euclidean distance, and cones for cosine. An interactive similarity playground and a tested, deterministic implementation accompany the derivation, with a finance example showing the same query ranking documents differently under dot product and cosine when document norms vary.
MIPS Hardness and the Limits of Exact Nearest-Neighbor Search
Why maximum inner-product search is not a metric problem, why exact high-dimensional search has no truly-sublinear algorithm, and why we approximate
Retrieval ranks documents by maximum inner product: return the document maximizing <q, d>. We first show why this is not the metric nearest-neighbor problem it is often mistaken for — the inner product has no triangle inequality, and a vector need not be its own best match — so the space-partitioning intuition that organizes metric search does not transfer. We then give the asymmetric lifting transforms (Bachrach et al.; Shrivastava-Li; Neyshabur-Srebro) that turn MIPS into Euclidean nearest-neighbor search on a lifted sphere, prove the transform preserves the argmax exactly, and flag honestly that it does not preserve approximation ratios. With the problems reduced to one another, we reach the hardness: exact high-dimensional nearest-neighbor and closest-pair search have no known algorithm that is simultaneously exact, truly sublinear per query, and near-linear in space. We present the Orthogonal Vectors problem and its reduction to closest/farthest pair, state the Strong Exponential Time Hypothesis precisely, and derive the conditional n^(2-o(1)) lower bound — emphasizing that this is conditional hardness, not a proven impossibility. The payoff is the trade-off triangle that motivates the rest of the curriculum: in high ambient dimension you cannot have exactness, sublinear time, and near-linear space at once, so you relax one — give up exactness for approximate indexes, or exploit the low intrinsic dimension that the concentration topic showed real embeddings actually have. An interactive laboratory and a tested notebook accompany the derivation, with a finance example on why exact MIPS over a multimodal corpus is hopeless at query time.
Embedding-Space Geometry
Track completeWhere embeddings live and what ANN must contend with: concentration of measure, hypersphere and von Mises–Fisher geometry, PCA and random projections, Johnson–Lindenstrauss, and chunking as segmentation.
Need the ML foundations? formalml.com →
Chunking as a Segmentation and Optimization Problem
Where to cut a document, posed as a coherence-maximizing segmentation with an exact dynamic-programming optimum — and the proxy it secretly optimizes
Chunking is the first thing a retrieval pipeline does to a document and the least mathematized — the default is to split every few hundred tokens and move on. Posed properly it is a one-dimensional segmentation problem: choose boundaries that maximize within-chunk coherence. We show that coherence has a clean closed form — for L2-normalized sentence embeddings the within-segment cost is the segment length minus the norm of the sum of its embeddings, which is the length times one minus the mean resultant length, the von Mises-Fisher concentration statistic from the prerequisite topic — so minimizing total cost carves the document into tight clusters on the sphere. Because the cost is additive across segments, the globally optimal segmentation is computed exactly by an O(n squared) dynamic program, which we prove optimal and verify against brute force; TextTiling's greedy depth scores and fixed-size chunking are heuristics that cannot beat it. We then confront the honest catch that makes this more than an algorithms exercise: coherence is a proxy for downstream retrieval quality, and the harness shows boundary-recovery F1 peaking at the true section count while the coherence cost keeps falling under over-segmentation. An interactive Chunking Laboratory and a tested implementation accompany the derivation, with a synthetic 10-K filing on which the optimal segmentation recovers the section structure that fixed-size chunking misses.
High-Dimensional Geometry and the Concentration of Distances
Why nearly every pair of points looks equidistant in high dimensions — and why retrieval works anyway
Retrieval-augmented generation searches for nearest neighbors in an embedding space of several hundred to a few thousand dimensions, but our intuition for distance comes from two and three. We establish the three concentration phenomena that make high-dimensional space behave unlike anything that intuition expects: the norm of a random vector concentrates on a thin shell of radius √d; two random vectors are almost surely nearly orthogonal, with inner product of variance 1/d; and, for data with i.i.d. coordinates, every pairwise distance concentrates at a common value, so the nearest and farthest neighbors of a query become indistinguishable — the curse of dimensionality. We prove the load-bearing direction (the relative variance of squared distance vanishes, hence contrast collapses for any fixed number of points) and cite Beyer et al. for the general statement, verifying it numerically. We then resolve the apparent paradox that retrieval works at all: real embeddings escape the curse because their intrinsic dimension is far below the ambient one, the property that approximate nearest-neighbor indexes exploit. An interactive Concentration Laboratory and a tested implementation accompany the derivation, with a finance example asking whether cosine similarity is meaningful for 1536-dimensional document embeddings.
Normalization, the Hypersphere, and von Mises–Fisher Geometry
Why retrieval lives on the unit sphere, and the distribution that models a topical cluster on it
Dense retrievers L2-normalize their embeddings, so the space they actually search is not all of R^d but the unit hypersphere S^{d-1}, where cosine similarity is the inner product and ranking by cosine is ranking by Euclidean distance. We start from that identity, then ask what 'no information' looks like on the sphere — the uniform distribution, whose projection onto any axis has density proportional to (1 − t^2)^((d−3)/2) and variance exactly 1/d, the same 1/d that made random vectors near-orthogonal one topic ago, now read as a law that crowds all the mass onto the equator. A topical cluster of embeddings is not uniform; it concentrates around a mean direction, and the distribution that models it is the von Mises–Fisher law f(x) = C_d(kappa) exp(kappa mu·x). We derive its normalizing constant, showing it is a modified Bessel function precisely because the surface integral reduces to the equatorial slice; prove it is the maximum-entropy distribution on the sphere with a given mean direction; and derive the maximum-likelihood estimates of the mean direction mu and the concentration kappa, the parameter that measures how tight a cluster is. An interactive Hypersphere Laboratory and a tested implementation accompany the derivation, with a finance example modeling two topical clusters of 1536-dimensional document embeddings and showing that cluster tightness is a measurable quantity.
Random Projections and the Johnson–Lindenstrauss Lemma
Reducing embedding dimension with a matrix that never saw the data — and the dimension-independent price of preserving every distance
PCA reduces an embedding's dimension by reading the cloud's own covariance: data-dependent, variance-optimal, and it must see every vector first. Johnson-Lindenstrauss reduces it the opposite way — multiply by a random matrix that has never seen the data — and still preserves every pairwise distance to within a factor of one plus or minus epsilon. We prove the chain that makes this work: a random Gaussian map is unbiased on squared norm, the normalized squared norm follows a chi-squared law that concentrates at rate exp(-c k epsilon squared), and a union bound over the difference vectors of n points shows that a target dimension k on the order of epsilon-to-the-minus-two times log n suffices for all pairwise distances at once — a dimension that depends on log n and epsilon but not on the ambient d. We establish the database-friendly Rademacher and sparse variants and cite the Larsen-Nelson result that the bound is optimal — no data-oblivious map does better. The honest catch is one of applicability, not failure: the constant is worst-case (the typical pair distorts far less than the worst), and the lemma preserves distances rather than rankings, so a random projection is a distance-preserving sketch and approximate-search front end, not a standalone exact retriever — which is why data-dependent PCA keeps far more exact-ranking recall on a structured cloud. An interactive Random Projection Laboratory and a tested, scikit-learn-cross-checked implementation accompany the derivation, with a finance example projecting 1536-dimensional document embeddings and measuring what distortion and recall survive.
Matryoshka Representations: Jointly Trained Nested Subspaces
One embedding whose every prefix is itself a usable representation — and the exact sense in which the linear version is just PCA
A retriever that stores one embedding per document would like to spend few dimensions when latency matters and many when accuracy does — without re-encoding the corpus. Matryoshka Representation Learning trains a single embedding so that every prefix of it is itself a usable representation: the first 96 coordinates retrieve almost as well as all 1536. We make the geometry precise. In the linear, squared-reconstruction setting we prove that the jointly optimal nested basis is exactly PCA's eigenvalue-ordered basis — because PCA's top-k subspaces are nested and each is the Eckart-Young rank-k optimum, one ordered basis is simultaneously optimal at every granularity, hence optimal for any positive weighting of the granularities. Matryoshka generalizes PCA's nested-subspace optimality from variance to an arbitrary task loss. We then confront the honest catch: the nesting that makes a prefix usable is a property of the training, not a free consequence of having an embedding — a random rotation preserves every full-width distance yet destroys the prefixes — and the nonlinear, contrastively trained version's advantages are empirical regularities, not theorems. We close with adaptive funnel retrieval, shortlisting on a cheap short prefix and reranking at full width for near-exhaustive recall at a fraction of the cost, an interactive Matryoshka Laboratory, and a tested, scikit-learn-cross-checked implementation on a 1536-dimensional finance cloud.
PCA as Optimal Linear Dimensionality Reduction for Embeddings
The variance-optimal projection of an embedding cloud — what truncating 1536 dimensions to k keeps, and the honest reason it can still hurt retrieval
A retriever stores millions of embeddings, and both memory and nearest-neighbor latency scale with the dimension, which runs from several hundred to a few thousand. High-dimensional geometry told us those embeddings have low effective rank — most coordinates carry little variance — so the natural question is how much retrieval quality survives projecting them down. Principal component analysis is the variance-optimal linear answer: the projection onto the directions the embedding cloud actually spreads along, which are the top eigenvectors of the centered covariance, equivalently the right singular vectors of the centered data matrix. We prove the three equivalent faces of PCA — maximizing retained variance, minimizing reconstruction error, and decorrelating the coordinates — establish the Eckart-Young-Mirsky theorem that the truncated SVD is the best low-rank approximation with squared error equal to the tail of the spectrum, and prove a projection-distortion identity: the fraction of squared distance the top-k projection retains is exactly the explained-variance ratio. We then confront the honest catch that variance-optimal is not retrieval-optimal — the top components often encode nuisance structure, so removing them can help cosine retrieval. An interactive Spectrum Laboratory and a tested, scikit-learn-cross-checked implementation accompany the derivation, with a finance example projecting 1536-dimensional document embeddings and measuring the recall that survives, against a random projection of the same width.
Retrieval Mechanics
Probabilistic IR
Track completeThe classical algebraic and probabilistic retrieval models that form the lexical half of hybrid retrieval: the vector space model, the Probability Ranking Principle, BM25, query-likelihood models, and the inverted index.
The Vector Space Model and TF-IDF
Documents and queries as weighted term vectors — where inverse document frequency is the self-information of a term, and cosine normalization quotients document length away
The vector space model is the first concrete relevance functional: documents and queries become sparse vectors over the vocabulary, weighted by term frequency and inverse document frequency, and ranked by cosine similarity. We scale term frequency sublinearly so repetition has diminishing returns — a strictly increasing, concave transform — and then give inverse document frequency its rigorous reading: IDF is exactly the self-information, the pointwise Shannon surprise, of a term's presence under a uniform-document model, so a term in every document carries zero bits and a rare one carries log N. Assembling tf-scaling with IDF gives the TF-IDF weight, and cosine normalization quotients away the document-length magnitude that the off-sphere divergence of the retrieval problem warned about. We then locate exactly where TF-IDF falls short — sublinear tf is unbounded and cosine length normalization is untunable and document-global — which is precisely the gap BM25 closes with a saturating tf transform and a tunable length term. An interactive vector space laboratory and a tested NumPy implementation, cross-checked against scikit-learn and sharing the BM25 interest-rate-exposure corpus, accompany the derivation.
BM25 and the Binary Independence Model
How probability theory turns term counts into a ranking function — and why saturation and length normalization are the two ideas that matter
BM25 is the strongest lexical retrieval baseline in information retrieval, and it is not an arbitrary formula: its inverse-document-frequency factor falls out of the Binary Independence Model with a Jeffreys prior, and its term-frequency saturation is motivated by the 2-Poisson eliteness model. We derive the Robertson–Spärck-Jones weight from the Probability Ranking Principle, show how smoothed IDF emerges, motivate the saturating tf transform and the document-length normalization, assemble the BM25 scoring function, and prove its limit behavior (k₁→0 recovers the binary model, k₁→∞ recovers length-normalized raw term frequency, b interpolates length normalization). An interactive scoring laboratory and a from-scratch NumPy implementation whose tests verify these limits accompany the derivation, with a worked finance example over earnings-call transcripts and 10-K filings.
The Inverted Index and Safe Dynamic Pruning (WAND, BlockMax-WAND)
How BM25 is actually computed at scale — and the provably exact pruning that skips the documents that cannot enter the top-k
BM25 assigns a score to a document, but a retrieval system must return the top-k documents from a collection of millions without scoring all of them. The inverted index is the data structure that makes this possible, and dynamic pruning is the algorithm. We define the inverted index — postings lists, document frequencies, length array — and document-at-a-time scoring, then derive WAND: per-term maximum-score upper bounds, a running threshold equal to the k-th best score so far, and a pivot rule that skips any document whose cumulative upper bound cannot reach the threshold. We prove the safety theorem — WAND returns the exact top-k — and show how BlockMax-WAND tightens the bound with per-block maxima for deeper skipping. The honest counterweight: pruning is exact but has no asymptotic guarantee, and an adversarial query reduces it to the exhaustive scan. An interactive pruning visualizer and a from-scratch implementation whose tests assert exactness and measure the pruning accompany the derivation, with a finance case study over filings and transcripts at scale.
The Probability Ranking Principle
The exchange-argument proof that ranking by decreasing probability of relevance is decision-theoretically optimal — the root probabilistic IR builds on
Retrieval ranks documents by a relevance functional; the Probability Ranking Principle says the right functional is the probability of relevance itself, P(R=1 | d, q), and that ranking by it is not a heuristic but provably optimal. We set up the decision-theoretic frame — a Bernoulli relevance variable per document, a linear cost for retrieving a non-relevant document or missing a relevant one, and the additive expected cost of an ordering — and prove the PRP by an exchange argument: swapping any out-of-order adjacent pair can only lower expected cost, so the order sorted by decreasing P(R) is optimal at every cutoff at once, reached by nothing but bubble-sort swaps. We specialize to the 1/0 cost model, where the principle maximizes expected precision and recall at every k, and to the log-odds form the next topic inherits: because ranking is invariant under strictly monotone transforms, ranking by P(R) is ranking by the log-odds of relevance, which is exactly where the Binary Independence Model and BM25 begin. We separate the clean theorem from its load-bearing assumption — additivity of cost — and show, with an executable counterexample, where interdependent relevance breaks it. An interactive exchange-argument laboratory and a tested NumPy notebook that brute-forces the optimum over all permutations accompany the derivation.
Relevance Feedback and Query Expansion: Rocchio and RM3
Closing the loop — using the documents you just retrieved to repair the query, and why doing too much of it drifts off topic
A query and its relevant documents often use different words — a filing's risk disclosure says 'outlook' and 'forecast' where the analyst typed 'guidance' — and lexical retrieval cannot match what is not there. Relevance feedback repairs the query using the documents already retrieved. We derive Rocchio, the vector-space update that moves the query toward the centroid of the relevant documents, and the language-model relevance models RM1 and RM3, which estimate an expanded query distribution from the top documents weighted by their query likelihood and re-score by the KL/cross-entropy view. We prove Rocchio's centroid-optimality and RM3's interpolation limits, and we make the central honest point executable: pseudo-relevance feedback assumes the top documents are relevant, so a little feedback bridges the vocabulary gap and lifts recall, but too much pulls in off-topic terms and the query drifts. An interactive feedback laboratory and a from-scratch implementation whose tests assert both the gain and the drift accompany the derivation, with a finance case study over filings and transcripts.
Query-Likelihood Language Models and Smoothing
Ranking by the probability a document's language model generates the query — and why smoothing is not optional but the whole game
The query-likelihood model ranks documents by the probability that each document's language model generated the query. The maximum-likelihood estimate P(t|d) = tf/|d| already divides by document length, so query likelihood sidesteps the length hijack that captures the raw tf-idf dot product — but it pays with the zero-frequency catastrophe, where a single unseen query term sends the score to negative infinity. Smoothing repairs this, and it is the entire substance of the model: we derive Jelinek-Mercer interpolation and Dirichlet smoothing, prove that Dirichlet smoothing is exactly the Bayesian posterior mean under a conjugate Dirichlet prior, show that ranking by negative KL divergence between the query and document models is rank-equivalent to query likelihood, and expose via the Zhai-Lafferty decomposition the IDF-like role smoothing plays. An interactive smoothing laboratory and a from-scratch NumPy implementation whose tests verify every claim accompany the derivation, with a worked finance example over earnings-call transcripts and 10-K filings.
Vector Quantization
Track completeLossy compression of embedding vectors for memory-bounded search — rate-distortion and estimation theory: Lloyd–Max optimality, product quantization, and score-aware anisotropic quantization.
Need the ML foundations? formalml.com →
Optimized Product Quantization and Score-Aware Quantization
Two ways to make a product quantizer optimal: rotate the space so its subspaces carry balanced information, and reshape the loss so it protects the inner products a query actually sees
The previous topic ended on a wall the product quantizer could not climb alone: it assumes the subspaces are independent, and cross-subspace correlation with unequal per-subspace variance under equal bit allocation is the loss it pays. A variance-balancing rotation cut the distortion several-fold on a deliberately imbalanced cloud — but only as a heuristic. This topic formalizes that rotation, then changes the loss the quantizer optimizes. Optimized product quantization inserts an orthogonal matrix R before the split and optimizes it jointly with the codebooks. Because R is an isometry, it leaves every distance and inner product unchanged, so it cannot hurt retrieval — but it adds the freedom to choose the axes along which the vector is cut. We derive the parametric solution: under a Gaussian high-rate bound, the optimal R decorrelates the data and balances the PRODUCT of eigenvalues across subspaces, not the SUM the previous topic's heuristic balanced — a distinction that is provable and matters. We then derive the non-parametric algorithm, alternating optimization in which the rotation step is a closed-form Orthogonal Procrustes problem solved by a single SVD, giving a monotone descent to a local optimum. The second half changes the objective. For maximum-inner-product search, reconstruction error is the wrong loss: what matters is the inner product seen by queries that actually retrieve the vector. Score-aware quantization, the idea behind ScaNN, splits the quantization residual into a component parallel to the datapoint and an orthogonal one, and weights the parallel part — which dominates the inner-product error for aligned queries — more heavily. An interactive laboratory and a tested implementation that imports and extends the product-quantization code accompany the derivation.
Product Quantization and Asymmetric Distance Computation
Quantizing each subspace independently turns one intractable codebook into a product of small ones — the additive distortion that makes it work, and the lookup table that keeps search fast
The previous topic ended on a wall: a single flat codebook of 256 codewords compresses a 256-dimensional embedding to one byte but retains only about half of the nearest-neighbor recall, and a flat codebook cannot do better cheaply — it needs 2^B centroids for B bits, capped at the number of training points and intractable past a couple dozen bits. Product quantization breaks the wall by giving up on a single codebook. Split each vector into m disjoint subvectors, quantize each subspace independently with its own small codebook of k* centroids — which is exactly Lloyd's k-means run m times — and store the tuple of m sub-centroid indices, m*log2(k*) bits. We prove the identity that makes this work: squared Euclidean distance separates over disjoint coordinate blocks, so the total distortion is the sum of the per-subspace distortions and each subspace is trained independently. The effective codebook is the product of the sub-codebooks, (k*)^m codewords, stored as only m*k* centroids: eight bytes encode an effective 2^64 codewords from 2048 stored vectors. For retrieval, asymmetric distance computation keeps the query exact and precomputes an m-by-k* table of squared sub-distances, so each database distance is m table lookups, turning an O(d) distance into O(m). We confront the honest accounting — at equal trainable bits a flat codebook matches or beats PQ; PQ wins only by reaching budgets a flat codebook cannot — and connect the residual loss to subspace correlation, the gap that optimized product quantization closes with a learned rotation. An interactive Quantization Laboratory and a tested implementation that imports and extends the previous topic's Lloyd code accompany the derivation.
Vector Quantization and the Lloyd–Max Optimality Conditions
The two conditions an optimal quantizer must satisfy — nearest-neighbor encoding and centroid decoding — and the alternating algorithm that drives distortion down to a local optimum
A retriever that stores ten million high-dimensional float32 embeddings spends tens of gigabytes before any structure is added, and every dimension is paid for again at query time. Vector quantization attacks the memory directly: replace each embedding by the index of the nearest entry in a small learned codebook, so a vector costs log2(k) bits instead of thousands of floats. We formalize what makes such a quantizer optimal. A quantizer factors as a decoder composed with an encoder, Q = beta . alpha, and its quality is the expected squared distortion D = E||X - Q(X)||^2. We prove the two conditions an optimal quantizer must satisfy: given the codebook, the optimal encoder assigns each point to its nearest codeword, carving space into Voronoi cells (the nearest-neighbor condition); and given that partition, the optimal codeword is the conditional mean of its cell, c_i = E[X | X in R_i] (the centroid condition). Alternating the two is Lloyd's algorithm, which we show drives distortion down monotonically to a fixed point — a local, not global, optimum. We identify k-means as exactly this procedure under the empirical measure, confront the non-convexity and initialization dependence honestly, and connect the asymptotic law D ~ C(d) k^(-2/d) to the curse of dimensionality: the same d that concentrates distances forces codebook size to grow exponentially for a fixed distortion. An interactive Quantization Laboratory and a tested, scipy-cross-checked implementation accompany the derivation, quantizing a finance embedding cloud and measuring the rate-distortion tradeoff that the next topics — product quantization and the IVF index — are built to exploit.
ANN Index Structures
Track completeThe data structures behind sublinear vector retrieval, at the level of their actual mathematics: IVF Voronoi partitioning, LSH sensitivity theory, navigable small-world graphs and HNSW, multi-vector and filtered ANN.
Filtered and Incremental ANN: Predicate Search, Deletion, and Graph Connectivity
Deletion and predicate filtering are the same operation — removing nodes from a navigable graph — so they obey one exact over-fetch law, with percolation as the honest floor beneath it
HNSW gave us a graph that is natively incremental on insert and a beam that walks it, but it ignores the two things production indexes actually face: vectors are deleted over time, and queries carry a predicate the index must respect. This topic formalizes both, and its organizing idea is that they are the same operation — removing nodes from a navigable graph. The mathematics has three movements. The first is the exact spine: a tombstoned node stays in the graph as a routing waypoint but is dropped from results, so to return k live results when a fraction delta are dead the number of candidates scanned is negative-binomial with mean k over one minus delta; hard deletion plus a neighbor-repair heuristic recovers the recall that tombstone bloat costs. The second movement is the honest floor: connectivity under random churn is a percolation threshold, p_c equal to one over M minus one for a regular graph, verified on a configuration-model graph and then measured on HNSW's real layer-zero graph, with the load-bearing caveat that connectivity is necessary but not sufficient for navigability — recall fails far inside the connected regime. The third movement is the unification: a filter soft-deletes every failing node for this query, so post-filtering obeys the same law, mean fetch k over s, with a sharp binomial recall cliff; pre-, post-, and in-filtering trade off in a crossover set by selectivity, and the induced subgraph on a random passing set fragments by site percolation while a spatially coherent predicate stays connected far below the same selectivity. An interactive laboratory shows the single over-fetch hyperbola that both deletion and filtering ride, the percolation thresholds, and the filter-strategy crossover.
HNSW: Hierarchical Navigable Small-World Construction and Search
How one randomized idea — a hierarchy of nested graphs — turns the navigable small-world graph's arbitrary entry into a provably logarithmic descent, and the heuristic that keeps each layer navigable
The navigable small-world graph gave us a searchable graph and a beam that walks it, but its search starts at an arbitrary entry and its small-world property is empirical. HNSW adds one structural idea — a randomized hierarchy of nested graphs, the continuous analogue of a skip list — that turns the arbitrary entry into a provably logarithmic descent. The mathematics has three movements. The first is the level-assignment law: each node draws a maximum level as the floor of minus the logarithm of a uniform variable scaled by one over the logarithm of M, which makes the probability of reaching level ell exactly M to the minus ell. From that exact law follow geometric layer occupancy, an order-one top layer, and an expected maximum level — the entry-descent depth — that grows like the logarithm base M of n. This is the provable spine, the analogue of the prerequisite's Kleinberg theorem. The second movement is the heuristic that distinguishes HNSW from linking to the nearest M: admit a candidate only if no already-kept neighbor is closer to it than it is to the base, a diversity rule that preserves the long-range links that keep each layer navigable, with no optimality proof. The third movement builds and searches the hierarchy, reusing the prerequisite's beam restricted to a per-layer adjacency — a fresh per-layer search that, forced to a single layer, is the prerequisite's greedy search exactly — and closes the approximate-nearest-neighbor arc with a head-to-head against the inverted file on one shared cloud. An interactive laboratory steps through the layer pyramid and a query's descent, contrasts the naive and heuristic neighbor sets, and traces the recall-versus-cost frontiers of the graph and partition indexes side by side.
Voronoi Partitioning and the Inverted-File Index
A coarse quantizer cuts the database into Voronoi cells so a query scans only the few nearest — and product-quantizing the residual after the partition turns the same bit budget into higher recall
The quantization track learned to compress a vector so a distance is cheap to estimate, but every method so far still scans the whole database. The inverted-file index is the non-exhaustive half. A coarse quantizer — Lloyd's k-means with nlist centroids — partitions the space into Voronoi cells; each database vector is filed under its nearest centroid into that cell's inverted list; and a query is compared only against the vectors in the nprobe cells nearest to it. We prove the candidate-set reduction (probing nprobe of nlist balanced cells scans about nprobe/nlist of the database, a sqrt(n)-scale speedup at nlist ~ sqrt(n)) and confront the honest catch: the boundary effect, where a query's true nearest neighbor sits across a Voronoi boundary in a cell the query does not probe, so recall at nprobe = 1 is strictly below 1 and is recovered monotonically by probing more cells. The second movement composes the index with product quantization. By the law of total variance the coarse quantizer removes the between-cell variance, so the residual of each vector relative to its cell centroid has strictly smaller variance than the vector itself; product-quantizing that residual — IVFADC, the IndexIVFPQ of production systems — spends the same bit budget on a smaller signal and reaches higher recall than flat product quantization at equal bits. An interactive laboratory traces the recall-versus-scan frontier and the boundary effect, and a tested implementation that imports the k-means and product-quantization code accompanies the derivation.
Locality-Sensitive Hashing: Collision Probability and the ρ Exponent
Hash so that near points collide more often than far ones, and the collision probability — not a heuristic — becomes the index: an exact angular law, the AND/OR S-curve that sharpens it, and a sublinear exponent that holds for any data
IVF cut the space into Voronoi cells you probe and the graph topics walked a graph; locality-sensitive hashing is the third approximate-nearest-neighbor family and the only one with a sharp, distribution-free theory of its own. The idea is to hash so that near points collide more often than far ones, and to build the index on the collision probability itself. The centerpiece is random-hyperplane SimHash, which is signed random projection — so this topic imports the Johnson-Lindenstrauss machinery rather than reinventing it — and the mathematics has three movements. The first is the exact collision law: two vectors at angle theta collide with probability exactly one minus theta over pi, verified to the third decimal against a Monte Carlo of random hyperplanes. The second is amplification: concatenating k bits is an AND that needs all of them, unioning L independent tables is an OR that needs any of them, and the composite collision probability one minus one-minus-p-to-the-k all to the L is the S-curve whose threshold k and L place and sharpen, trading recall against candidate-set size — and which collapses to the bare hash at k equals L equals one. The third is the headline exponent: rho equals log of one over p-one over log of one over p-two is below one whenever the near collision beats the far one, so query time order n to the rho is sublinear by a family that never looks at the data, and rho falls as the approximation factor widens the near-far gap. A laboratory shows the angular law on the unit circle, the S-curve under amplification, and a cross-index head-to-head where, honestly, the data-aware indexes dominate the oblivious hash on a low-rank cloud.
Multi-Vector ANN: Indexing and Pruning MaxSim at Scale (PLAID)
Late interaction kept one vector per token and paid for it in storage and scan; PLAID serves it by reusing the two ANN prerequisites — cluster every token into shared centroids (IVF), compress each residual (PQ), approximate MaxSim by the centroid it landed in and prune with a Cauchy–Schwarz bound — a heuristic cascade whose one exact statement is that probing everything and pruning nothing recovers brute-force MaxSim
Late interaction lifted the single-vector rank ceiling by keeping one contextual vector per token, and the previous topic flagged the bill: an index roughly thirty-two times the size of a single-vector index, and a candidate-generation step that is now a multi-vector nearest-neighbor problem. This topic is how that bill is paid. PLAID, the optimized engine behind ColBERTv2, serves MaxSim at scale by reusing the two ANN prerequisites verbatim. First, representation: cluster every token embedding in the corpus into a single shared set of centroids — the inverted-file coarse quantizer — and store each token as its nearest centroid identifier plus a product-quantized residual, exactly IVFADC applied at the token level. Second, the centroid-MaxSim approximation: because tokens share centroids, the inner product of a query token with a document token can be approximated by its inner product with that token's centroid, computed once per centroid and reused across the whole corpus; the approximation error is exactly Cauchy–Schwarz, the inner product of the query token with the residual, bounded by the product of their norms. Third, the cascade: generate candidates by probing token inverted lists, prune them by the cheap centroid-MaxSim score, then decompress residuals and compute full MaxSim only on the survivors. The one exact statement is the collapse anchor — probe everything, prune nothing, rerank fully, and the cascade is brute-force MaxSim to floating point — and everything above it is a heuristic speed-for-recall trade we measure honestly on a frontier. A laboratory shows the token-to-centroid-plus-residual geometry, the centroid-MaxSim grid with its per-cell error bound, the recall-versus-cost frontier, and the storage collapse; a tested notebook that imports the IVF, PQ, and late-interaction code owns every number.
Navigable Small-World Graphs and the Mathematics of Greedy Routing
Why a graph is searchable by greedy hops only when its long-range links are scale-free and matched to the dimension — Kleinberg's navigability theorem — and how that idea becomes a practical approximate-nearest-neighbor index
The inverted file partitioned the space into Voronoi cells; this topic replaces the flat partition with a graph, and search becomes a walk. The mathematics has two movements. The first is Kleinberg's navigability theorem, the deepest idea in graph-based search: on a lattice augmented with one long-range link per node, drawn with probability proportional to the lattice distance to the power minus alpha, decentralized greedy routing — always step to the neighbor nearest the target — is polylogarithmic in the number of nodes if and only if alpha equals the lattice dimension. The long-range links must be scale-free, distributed equally across distance scales, so that greedy routing can always halve the remaining distance; too uniform or too local a link law, and routing degrades to a polynomial number of hops. We simulate the U-shaped delivery-time curve on a ring and confirm its trough at the dimension. The second movement turns the idea into an index. The navigable small-world graph is built by incremental insertion: each point, as it arrives, links to its approximate nearest neighbors found by greedy search in the graph so far, and early insertions become the long-range hubs that make the graph a small world. Search is greedy beam descent from an entry node, and the honest catch is that pure greedy hill-climbing stops at a local minimum — a node with no closer neighbor — so recall is below one until the beam widens. An interactive laboratory traces the navigability curve and the greedy walk that gets stuck, and a tested implementation that imports the prerequisite's synthetic cloud accompanies the derivation. The hierarchy that layers this graph for logarithmic entry is the next topic.
Learned Retrieval & Ranking
Neural & Learned Retrieval
Track completeLearned representations for retrieval, defined by training objectives and expressivity claims: InfoNCE contrastive training, dense dual encoders, late interaction and learned sparse, cross-encoders, distillation, and cross-modal alignment.
Need the ML foundations? formalml.com →
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.
Dense Retrieval and Dual Encoders: Architecture, Expressivity, and the Cost of Negatives
Why a query tower and a document tower trained to a separable score let you precompute every document, collapse retrieval to a single maximum-inner-product lookup, and represent exactly the relevance patterns of rank at most d by Eckart–Young — and why one batch of 2B encodings secretly buys B² training comparisons
InfoNCE told us how a dual encoder is trained; this topic asks what that architecture can represent and what it costs. A dual encoder is two towers, a query encoder and a document encoder, whose relevance score is the separable inner product of their outputs. We show that separability is the whole game: because the score factorizes, every document vector can be precomputed and stored once, and a query at serving time reduces to a single argmax over inner products — maximum-inner-product search, the problem the MIPS-hardness topic analyzes. We then ask the expressivity question. Stacking the scores into a query-by-document relevance matrix, a d-dimensional dual encoder can realize exactly the matrices of rank at most d; the Eckart-Young-Mirsky theorem makes the truncated SVD the optimal rank-d approximation to any target, so d is a clean upper bound on what the architecture can express, and retrieval accuracy collapses when d falls below the relevance pattern's intrinsic rank. We flag honestly that rank is an upper bound, not the tight sign-rank measure of how many dimensions relevance needs. Finally we account for training cost: a batch of B query-document pairs costs 2B encoder forward passes but produces a B-by-B Gram matrix of similarities, yielding B-squared-minus-B in-batch negatives at no extra encoding cost — the quadratic-utility-from-linear-cost law that makes in-batch-negative training the default. A laboratory reuses the InfoNCE finance encoder to show the precompute-then-MIPS path, the rank-d reconstruction of a relevance matrix, and the in-batch Gram trick; a tested notebook owns every number.
How Many Dimensions Does Relevance Need? Sign-Rank and Margin Complexity
Rank says how many dimensions suffice to fit the scores; sign-rank says how many dimensions relevance actually needs to get the order right — far fewer for benign patterns, unboundedly many for combinatorial qrels, and the reason a single-vector embedding has a ceiling no amount of training removes
DPR proved an upper bound: a d-dimensional dual encoder realizes exactly the relevance matrices of rank at most d. But rank is the wrong complexity for a relevance pattern, which is a sign pattern — relevant or not, the row-wise order, not the scores. This topic asks the tight question DPR deferred: how many dimensions does relevance actually need? The answer is the sign-rank, the smallest dimension in which the pattern is linearly realizable irrespective of magnitudes, and its robust cousin the margin complexity. We show rank and sign-rank are genuinely different — the signed identity has full rank n but sign-rank 3 — proving the gap both directions, and we prove a closed-form lower bound: Forster's spectral bound makes a Hadamard relevance pattern need at least sqrt(N) dimensions. We then connect to retrieval through the LIMIT theorem, which pins the minimum embedding dimension of a qrel matrix to the sign-rank of its signed form, and show by free, perfectly optimized embeddings that the largest realizable all-pairs corpus grows only polynomially in d — so at any fixed dimension some combinatorial relevance pattern is unrepresentable. A laboratory makes the rank/sign-rank gap, the Forster wall, and the free-embedding wall visible; a tested notebook owns every number; and the finance flip shows the embedding dimension that perfectly solves single-company retrieval failing combinatorial multi-company queries.
Contrastive Learning for Retrieval: InfoNCE, Temperature, and Negative Sampling
How a dual encoder is taught to place a query near its answer and far from everything else — one loss read three ways: a mutual-information lower bound, a tug-of-war between alignment and uniformity on the hypersphere, and a temperature-sharpened gradient that the hardest negative dominates
The hypersphere topic told us where dense embeddings live; this one tells us how they are taught. Contrastive learning trains a dual encoder to place a query near its relevant document and far from everything else, and the loss that does it — InfoNCE — is the foundation of the neural-retrieval track. We read one loss three ways. First, InfoNCE is an (N+1)-way cross-entropy whose minimization is a lower bound on the mutual information between query and positive, the Contrastive Predictive Coding result of van den Oord, Li, and Vinyals (2018) — a bound ceilinged at log(N+1), which is the formal reason more negatives help and the honest reason the information story saturates. Second, as the number of negatives grows the loss splits, on the unit hypersphere of the previous topic, into alignment — positives pulled together — and uniformity — every embedding pushed toward the exact uniform distribution we already characterized, with temperature playing the role of an inverse von Mises-Fisher concentration (Wang & Isola, 2020). Third, the gradient is a softmax-weighted repulsion over the negatives: the hardest negative, the one nearest the query, dominates, and temperature controls how sharply — small temperature focuses almost all the push on a single negative, a hardness-awareness that is powerful and, past a point, brittle (Wang & Liu, 2021). A laboratory draws the query, positive, and negatives on the sphere with the gradient weights live, the mutual-information bound against its log(N+1) ceiling, and the alignment-uniformity decomposition as the temperature varies; a tested, deterministic notebook owns every number it shows.
Late Interaction and Learned Sparse Retrieval: ColBERT and SPLADE
A single pooled vector hits a sign-rank ceiling; keep one vector per token and score by MaxSim, or expand into a high-dimensional sparse lexical space, and the ceiling lifts — two different escapes from the bottleneck the previous topic proved, one provable reduction and one honestly empirical gain
The previous topic proved a single pooled embedding has a sign-rank ceiling: relevance patterns it cannot represent below a critical dimension. This topic covers the two architectures that escape it. Late interaction (ColBERT) keeps one vector per token and scores a query against a document by MaxSim, the sum over query tokens of the best-matching document token. Because MaxSim is a max of inner products rather than a single bilinear form, the rank ceiling does not apply; we prove the one clean boundary fact — with one vector per item MaxSim is exactly the dual-encoder dot product — and then demonstrate, honestly flagged as empirical, that a model with two vectors per document realizes the all-pairs relevance pattern a single vector provably cannot. Learned sparse retrieval (SPLADE) takes the other route: it expands each text into a high-dimensional sparse vector over the vocabulary, living in BM25's inverted index, with a FLOPS regularizer controlling sparsity. It fixes the vocabulary mismatch BM25 cannot, retrieving a relevant document whose terms the query never mentions. A laboratory shows the MaxSim grid, the single-vector wall and its multi-vector escape, and SPLADE's expansion and its sparsity trade-off; a tested notebook owns every number; and the two escapes map onto the two failure modes a single-vector financial retriever hits.
Hard-Negative Mining and Debiased Contrastive Training (ANCE)
InfoNCE's gradient weights each negative by its similarity, so random negatives are near-orthogonal noise and the learning signal lives in the same-sector hard negatives — but mining near the anchor is mining where true positives hide, so the mined negatives are contaminated at a false-negative rate τ⁺. The debiased estimator of Chuang et al. solves p = τ⁺p⁺ + τ⁻p⁻ to recover the true-negative expectation from unlabeled samples, and Robinson's β-reweighting concentrates it on the hardest negatives; ANCE then mines globally from an ANN index that goes stale as the encoder drifts, trading a refresh interval against staleness against cost
InfoNCE told us the contrastive gradient weights each negative by its softmax similarity, so the hardest negative dominates; this topic spends that fact and pays its hidden cost. First the geometry: a random negative is near-orthogonal to the query and contributes a vanishing gradient, while the same-sector hard negatives a miner surfaces carry a share of the gradient far above their count fraction — which is why hard-negative mining works. But mining samples near the anchor, and near the anchor is exactly where unlabeled true positives live, so the mined negatives are contaminated at a false-negative rate τ⁺ and the loss pushes accidental positives apart. The rigorous spine is the debiased contrastive estimator of Chuang, Robinson, Lin, Torralba, and Jegelka: writing the unlabeled sampling law as p = τ⁺p⁺ + τ⁻p⁻ recovers the true-negative expectation from unlabeled samples, an asymptotically unbiased correction, and Robinson, Chuang, Sra, and Jegelka's β-reweighting concentrates it toward harder negatives without re-importing the false negatives it removed. The systems counterpart is ANCE: to mine global hard negatives rather than in-batch ones, Xiong et al. retrieve them from an approximate-nearest-neighbor index — which goes stale as the encoder drifts during training, so an asynchronous inferencer rebuilds the index on an interval, and the refresh-interval ↔ staleness ↔ cost tradeoff is the systems-math object, an empirical curve with no convergence bound. A laboratory shows the gradient share under a temperature slider, the false-negative rate rising as the mining radius tightens, the biased, true, and debiased estimators under a τ⁺ slider, and the ANCE staleness-versus-refresh curve with its cost knee; a tested notebook owns every number; and the finance thread is a production document encoder fine-tuned on the same-sector hard negatives a single embedding confuses, debiased against the same-sector filings that are accidentally relevant.
Knowledge Distillation for Retrieval: Teacher–Student Transfer (MarginMSE)
A cross-encoder is the most accurate scorer and the least deployable — a joint forward pass per query–document pair forbids precomputation. Distillation spends that accuracy cheaply: train a precomputable dual-encoder student to match the teacher's per-query score MARGIN, not its absolute level. The all-pairs MarginMSE reduces to a centered Frobenius distance 2·n_d·‖SC − TC‖², so margins are blind to the teacher's per-query miscalibration (translation-invariance), and the margin-optimal rank-d student is best_rank_d of the per-query-centered teacher — Eckart–Young again. Distillation approaches the teacher's recall at dual-encoder inference cost, but the embedding-dimension rank ceiling still binds it
The cross-encoder topic built the most expressive relevance scorer and proved it could never be a first stage: a joint forward pass per query–document pair forbids precomputation. This topic spends that accuracy where it is affordable — it distills the expensive teacher into a cheap, precomputable dual-encoder student. The transfer loss is MarginMSE (Hofstätter et al., 2020): rather than match the teacher's absolute scores, match its per-query score MARGIN between a positive and a hard negative. The first result is why margins are the right target. The all-pairs MarginMSE between a student S and teacher T reduces, by a variance identity, to a centered Frobenius distance 2 n_d ||SC − TC||² where C row-centers each query's document scores — so adding a per-query offset T ↦ T + b·1ᵀ leaves the loss unchanged. That translation-invariance is the rigorous hinge: cross-encoder scores are per-query miscalibrated, and margins are blind to that miscalibration. The closed-form optima follow from Eckart–Young–Mirsky with no SGD: the pointwise-MSE-optimal rank-d student is best_rank_d(T), and the margin-optimal one is best_rank_d(TC), the per-query-centered teacher. Because the teacher's scores carry a large constant level — its top singular direction — the pointwise student wastes a dimension reproducing it, while the margin student spends every dimension on ranking; at a restricted rank the margin student's recall@1 leads the pointwise student's, and the embedding-dimension rank ceiling binds both below the teacher, which they approach but never exceed. The payoff is the reranking sub-track's whole point: the distilled student gives cross-encoder-quality ranking at dual-encoder inference cost — precompute the documents once, answer by MIPS, never run a per-pair forward pass. A laboratory shows the translation-invariance of the loss under a miscalibration slider, the margin-over-pointwise recall gap across the rank budget with the two spectra that explain it, and the teacher's graded dark-knowledge margins beside the cost speedup; a tested notebook owns every number; and the finance thread is the production dense retriever that inherits a cross-encoder's same-sector discrimination at no extra query-time cost.
Ranking, Fusion & Reranking
Track completeThe mathematics of producing, combining, and reordering ranked lists: learning-to-rank, reciprocal rank fusion and its social-choice grounding, cross-encoder cascades, and LLM listwise rerankers.
LambdaRank, LambdaMART, and Listwise Objectives
RankNet gave each document a gradient force but is position-blind — a swap at the top of the list costs the same as a swap in the tail. This topic makes the objective position-aware three ways: LambdaRank weights each pairwise force by the ΔNDCG a swap would cause, LambdaMART boosts those forces into trees, and listwise objectives replace the heuristic with a proper Plackett–Luce loss — anchored by the honest theorem that LambdaRank's field is the gradient of no scalar loss, while the listwise loss genuinely is one
RankNet reduced ranking to a pairwise logistic surrogate whose gradient factorizes into a per-document lambda force — the net pull on each document from its preference pairs. That force is position-blind: it weights a swap at ranks 1–2 exactly like a swap at ranks 99–100. This topic removes that blindness three ways. LambdaRank multiplies each pairwise force by the absolute change in NDCG that swapping the pair would cause; because the change in NDCG factorizes into a change in gain times a change in discount, and the discount marginal is steep at the head and flat in the tail, the gradient mass concentrates where ranking quality is decided. But this weighting has a price, and the price is the honest core of the topic: the lambda field now depends on the current ranking, so it is the gradient of no scalar loss — locally, within a ranking cell, it is a weighted-RankNet gradient with a symmetric Jacobian, but globally it is discontinuous across swaps and a closed loop integrates to a nonzero value, the classical signature of a non-conservative field. LambdaMART feeds those lambdas as pseudo-residuals to gradient-boosted regression trees, buying a nonlinear scorer demonstrated to escape a rank ceiling no linear model can on a constructed interaction instance. Listwise objectives restore a proper loss: ListMLE is the negative log-likelihood of the Plackett–Luce model over the ideal permutation, convex in the scores, and ListNet its top-one cross-entropy. The arc is pairwise (a loss, position-blind) to LambdaRank (position-aware, not a loss) to listwise (a convex loss). A tested notebook owns every number; the headline NDCG deltas among the methods sit within the confidence interval, so the reported wins are structural.
Learning to Rank: Pointwise, Pairwise, and RankNet
The evaluation layer measured rankings with NDCG and MAP; this topic learns one. Ranking reduces to supervised learning three ways — pointwise regression of scores onto grades, pairwise classification of preferences (RankNet), and a listwise preview — anchored by the theorem that makes the field necessary: NDCG and MAP are piecewise-constant in the scores, with zero gradient almost everywhere, so they cannot be optimized directly, and the smooth pairwise logistic stands in as a surrogate
The evaluation layer learned to score a ranking; this topic learns to produce one. Learning to rank reduces ranking to supervised learning, and there are three reductions. The pointwise approach regresses each document's score onto its relevance grade by least squares — the global mean-squared-error minimizer, but it optimizes calibration, not order. The pairwise approach, RankNet, models each preference as a Bernoulli trial: the probability that document i outranks document j is the logistic of their score difference, and the loss is the pairwise cross-entropy, exactly the negative log-likelihood of the observed preferences. For a linear scorer this loss is convex in the weights, so it has a single global optimum reachable by Newton's method — no stochastic gradient descent, no learning-rate schedule. The listwise approach, which scores a whole permutation at once, we preview. The rigorous core is the theorem that makes the field necessary: NDCG and MAP are piecewise-constant in the scores, with zero gradient almost everywhere and jump discontinuities exactly at the score ties where the ranking swaps, so they cannot be optimized by gradient descent at all; the smooth pairwise logistic is a surrogate standing in for them. RankNet's gradient factorizes into a per-document lambda force — the net pull on each document from its preference pairs — which is the bridge to LambdaRank. The headline is that ranking is not regression: a model optimal in pointwise mean-squared error can lose on NDCG to a pairwise model with worse error, because order beats calibration. The finance climax learns a RankNet over the three complementary retrieval legs and, on held-out queries, beats every single leg and reciprocal-rank fusion. A tested notebook owns every number the page reports.
LLM Rerankers: Listwise Permutation Objectives and RankGPT
Classical learning-to-rank scored each document from a fixed feature vector, blind to the rest of the list except through the loss. The LLM reranker drops that — feed the whole candidate list into one model and it emits a permutation, scoring documents in each other's context. But context fits only a window of candidates, so RankGPT slides a window and locally re-sorts (a bubble sort), the order is position-biased (lost in the middle), windows must be aggregated (social choice), and the costly teacher is distilled into a cheap student — anchored by the honest caveat that an autoregressive permutation model, like LambdaRank, descends no scalar loss at inference.
The predecessor scored each document from a fixed feature vector. An LLM reranker drops that assumption: feed the whole candidate list into one model and it emits a permutation directly, scoring documents in each other's context — the most listwise objective there is. We model the LLM as a Plackett–Luce sampler at temperature τ (the ListMLE bridge made operational): as τ→0 it emits the ideal order byte-for-byte; as τ→∞ it is uniform. But an LLM context fits only a window of w ≪ n candidates, so RankGPT slides a window back-to-front and locally re-sorts — a bubble sort whose call count is O(n/s) per pass against the O(n²) of all-pairs comparison, with one perfect pass guaranteeing the global best in the top window and recall climbing toward a plateau under noise. The in-window order is position-biased (lost in the middle); presenting each window in several random orders and aggregating flattens it. Multiple windows produce multiple noisy permutations, reconciled by Borda, RRF, the NP-hard Kemeny median, or the Dwork et al. Markov-chain consensus — a comparison random walk's stationary distribution — with the consensus error falling at the 1/√K central-limit rate. Finally the expensive teacher is distilled into a cheap linear listwise student: a perfect teacher's student is exactly the predecessor's own fit, and it answers at zero inference LLM calls. The cost–quality frontier is the systems story. A tested notebook owns every number; the LLM is a simulated noisy oracle, so the provable wins are algorithmic, and the aggregate quality deltas sit inside the confidence interval.
Rank Fusion: Reciprocal Rank Fusion and the Geometry of Rank Aggregation
Why combining ranked lists by position beats combining them by score — and how close a cheap heuristic gets to the optimal consensus
Hybrid retrieval runs two retrievers — a lexical one like BM25 and a dense one — and must combine their rankings. The two live on incompatible score scales, so adding scores (CombSUM) lets one swamp the other; Reciprocal Rank Fusion (RRF) instead combines by position, reading only each document's rank in each list. We show that this makes RRF invariant to any strictly monotone rescaling of either retriever's scores, that as its constant k grows the RRF order converges to the Borda count, and that rank fusion opens onto the real mathematics of rank aggregation: permutations as points in a metric space under the Kendall-τ distance, the Spearman footrule, the Diaconis–Graham inequality relating them, the Kemeny consensus as the median permutation, and the footrule-optimal aggregate as a polynomial-time 2-approximation of the NP-hard Kemeny optimum. An interactive Fusion Laboratory and a from-scratch implementation whose tests verify every claim accompany the derivation, with a worked finance example fusing a BM25 ranking over 10-K text with a dense ranking over earnings-call passages.
Retrieval & RAG Evaluation
Track completeEvaluation treated as statistics: ranking metrics as estimators, significance testing, calibration, drift detection, LLM-as-judge reliability, and distribution-free conformal factuality guarantees.
Need the ML foundations? formalml.com →
NDCG: Graded Relevance and Discount Geometry
Set metrics treat relevance as a yes-or-no flag; NDCG keeps the degree of a match and the position it lands. We build the discounted cumulative gain over the same three retrieval legs, prove the ideal ranking is optimal by the rearrangement inequality, read the geometry of the logarithmic discount against the rank-biased alternative, and carry the estimator framing straight over — a reported NDCG gap is not a real one until it clears sampling noise, and the gain and discount you chose are conventions that can flip the verdict
Binary relevance throws away how relevant a document is: a perfect 10-K disclosure and a tangential transcript snippet both count as one hit. NDCG keeps the difference. A document carries a graded relevance, its gain is a function of that grade, and a hit deep in the ranking is discounted by its position — so discounted cumulative gain rewards putting the most relevant documents highest. Normalizing by the ideal cumulative gain gives NDCG in [0,1]. We build the metric over the same three legs and exact-MaxSim oracle the rest of the evaluation layer uses, grading relevance by global tertiles of the oracle score so the graded set nests the binary one exactly. The rigorous core is the rearrangement inequality: writing DCG as an inner product of the gains in ranked order with a decreasing discount vector, the ideal ranking — gains sorted descending — maximizes it, which is why the normalizer is the ideal and NDCG lands in [0,1]; under linear gain and the log discount the construction reduces exactly to the NDCG the BM25 notebook already computed. The discount is a geometry on rank positions, and its shape matters: the logarithmic discount keeps weight deep down where the geometric rank-biased discount, with its clean user model, concentrates it in the head. Both the gain and the discount are conventions, and built-and-run examples show each one reversing the verdict between two systems. Finally NDCG is an estimator, with the same standard error and the same overlapping-interval caveat as MAP: a tested notebook owns every number the page reports.
Set Metrics: Precision, Recall, MAP, and MRR as Estimators
The published stack measured recall@k everywhere and never defined it; here the whole set-metric family is defined over real rankings — precision and recall at a cutoff, the precision–recall curve and Average Precision as the area beneath it, MAP and MRR — and then reframed as what they actually are: sample means with standard error, so a reported gap is not a real one until it clears sampling noise
Retrieval returns a ranking; this topic defines what it means to score one. A metric is a functional from a ranking and a set of relevance judgments to a number, and the set-metric family is built up over three real retrieval legs — BM25, a dense dual encoder, and late interaction — scored against the same neutral exact-MaxSim ground truth the rest of the curriculum uses, so every number is a measurement, not a toy. Precision and recall at a cutoff k give the purity and coverage of the top-k; sweeping k traces the precision–recall curve, whose area is exactly Average Precision (the mean of precision at the relevant ranks), with the interpolated envelope flagged as a convention that inflates it. Averaging AP over queries gives MAP; the reciprocal rank of the first relevant document gives MRR, and the two coincide exactly in the known-item regime where each query has one answer. The load-bearing move is the last: every one of these numbers is a sample mean, hence an estimator with a standard error that shrinks like one over the square root of the query count — so two systems whose confidence intervals overlap cannot yet be told apart, which is the question the significance-testing topic resolves. A tested notebook that imports the three legs owns every number the page reports.
Conformal Factuality: Distribution-Free Correctness Guarantees for Generation
The evaluation layer produced numbers with error bars; the judge produced a calibrated confidence that a generated claim is supported. This topic turns that confidence into a guarantee — conformal prediction converts any nonconformity score into finite-sample coverage under exchangeability alone. We back off unsupported claims with a split-conformal threshold, control the false-claim rate with conformal risk control, and watch the guarantee break under drift and be repaired by reweighting. The finance thread: a retrieval-augmented system over filings that abstains rather than hallucinate a figure, at an error rate an auditor could sign off on.
The evaluation layer treated every retrieval number as an estimator and the LLM judge as a noisy instrument whose verdicts we debias and whose confidence we calibrate. That leaves a sharper question for generation: not how good a number is, but whether we can sign a guarantee on the answer we emit. Conformal prediction answers it. Given any nonconformity score — here the calibrated judge confidence that a claim is supported — split conformal sets a threshold from a held-out calibration set so that a genuinely faithful claim survives with probability at least one minus alpha, a finite-sample coverage guarantee that assumes only exchangeability, no model of when the language model hallucinates. We build the score, the per-claim back-off that removes the least-confident claims, and the recall guarantee that follows verbatim from the marginal-coverage theorem. But recall is not precision: a lenient judge endorses unsupported claims at high confidence, so the recall guarantee lets the false-claim rate run uncontrolled — on this corpus nearly a quarter of retained claims are hallucinations at the strictest level. Controlling the false-claim rate needs a guarantee on a monotone loss, which is conformal risk control: the per-slot false-claim rate, with its fixed denominator, is non-increasing in the back-off threshold, and the risk-control threshold holds its expectation at or below alpha. The fraction-of-retained loss, by contrast, is not monotone and silently voids the guarantee — a trap we exhibit numerically. A perfect judge collapses the whole construction onto precision at k, the metric the evaluation layer was built on. Finally the guarantee is marginal and rests on exchangeability, which covariate shift breaks: the threshold calibrated on yesterday's query mix under-covers a shifted deployment, and weighted conformal with the known likelihood ratio restores coverage. The finance thread is a retrieval-augmented system over filings that backs off unsupported claims and abstains rather than hallucinate a figure, at a guaranteed error rate. A tested notebook owns every number.
LLM-as-Judge and Faithfulness: RAGAS as a Family of Estimators
The evaluation track measured retrieval against fixed relevance labels. Generation has no label, so we hire an LLM to judge — and the judge is a noisy instrument with its own sensitivity, specificity, bias, and variance. We rebuild every RAGAS metric as an estimator you must correct for the instrument: debias the verdict with known error rates, agree on the protocol with chance-corrected reliability, calibrate the confidence, price the irreducible judge-variance floor, and recover the error rates with no gold labels at all.
Retrieval evaluation rested on fixed relevance labels; generation has none. The standard workaround hires a large language model as a judge, and RAGAS turns its verdicts into metrics — faithfulness, answer relevance, context precision. This topic treats the judge as what it is: a noisy measurement instrument, and every RAGAS metric as an estimator built from its verdicts. Faithfulness is the sample mean of the judge's per-claim support verdicts, and because the judge has imperfect sensitivity and specificity, that mean is a biased estimator of the latent grounding prevalence. The Rogan–Gladen correction inverts the error model to recover an unbiased estimate, but its variance is inflated by the inverse square of the judge's Youden index, so a near-useless judge cannot be debiased — only amplified. Trusting a judge first means agreeing with it: Cohen's kappa chance-corrects raw agreement, but the kappa paradox shows high agreement collapsing to near-zero kappa under the skewed marginals typical of 'most claims are supported', so we read Gwet's AC1 and Krippendorff's alpha alongside it, and decompose the variance to expose an intraclass-correlation reliability and a judge-variance floor that more queries cannot lower. We calibrate the judge's stated confidence with the prerequisite's reliability-diagram machinery, detect position bias with a paired swap test, and recover each judge's error rates with no gold set through Dawid–Skene latent-class EM — closing the loop with the correction that opened the topic. A tested notebook owns every number.
Score Calibration, Drift Detection, and Significance Testing for Retrieval
The prerequisites measured a metric as an estimator and left one question open: is an observed gap real? We close it with the right instrument — a paired significance test — and then generalize the same two-distribution comparison to two more production questions: is a retrieval score calibrated as a probability, and has the distribution drifted since we last looked? One idea runs through all three: difference two distributions of per-query quantities and ask whether the difference is zero.
Set metrics and NDCG framed every retrieval number as a sample mean with a standard error, and both left the same question hanging: when two systems' confidence intervals overlap, is the gap real or sampling noise? The crude overlapping-intervals read is conservative because it ignores that the two systems are measured on the SAME queries. The paired significance test exploits that pairing — differencing query-by-query cancels the shared per-query difficulty, so the variance of the difference is far below the sum of the two variances, and the test resolves a gap at a fraction of the queries. We build the paired t-test, cross-check it against the permutation and bootstrap tests that make no normality assumption, correct for the three simultaneous leg comparisons, and replace the prerequisites' crude query-count with a power calculation — closing the NDCG cliffhanger exactly: the closest pair needs 116 queries for 80% power, not the 185 the overlapping intervals suggested. The same two-distribution comparison then answers two more questions. Calibration asks whether a retrieval score behaves like a probability: the reliability diagram plots empirical relevance against confidence, the expected calibration error is the area off the diagonal, and raw cosine and MaxSim scores are wildly over-confident — which is exactly why rank fusion discards scores and fuses ranks. Platt scaling and isotonic regression pull the scores onto the diagonal while leaving the ranking untouched, so calibration is orthogonal to the ranking metrics. Drift asks whether the distribution has moved since a reference window: the Kolmogorov–Smirnov statistic is the sup-gap between two empirical CDFs and the population stability index is a symmetrized KL divergence, the credit-risk standard. A silent quality decay the aggregate mean cannot distinguish is caught by the paired test; a pure covariate shift fires the input drift alarm with no quality loss at all, so input monitoring alone cannot diagnose decay. A tested notebook owns every number.
Generation & Reasoning
Generation & Grounding
Track completeThe mathematics of what happens once context is retrieved: the retrieval-vs-long-context tradeoff, query transformation as distribution-shift correction, faithfulness as a measurable quantity, and selective generation.
Need the ML foundations? formalml.com →
Faithfulness and Groundedness as Measurable Quantities
HyDE modeled the quality of a generated answer with a single hallucination rate p. Here we stop modeling it with a knob and measure it on the text itself — as two numbers, not one. Faithfulness is the precision of an answer's atomic claims against the retrieved context (what fraction of what you said is supported); groundedness is the recall (what fraction of the supportable facts you used). They diverge, a noisy judge measures both with a bias we debias and a confidence we calibrate, and trading coverage for guaranteed faithfulness is the abstention frontier.
HyDE modeled the quality of its generated hypothetical with one hallucination rate p and showed no amount of averaging could remove it. This topic stops modeling generation quality with a knob and measures it on the generated text — as two numbers, not one. We decompose an answer into atomic claims and define faithfulness as the precision of those claims against the retrieved context and groundedness as the recall of the supportable facts; together they are the precision–recall curve of generation, the evaluation layer's pair of metrics read over claims instead of documents. The two diverge: a terse answer is faithful but thin, a verbose one covers everything but invents figures, and a single factuality score hides the trade. Because the measurement is an LLM judge — a noisy Bernoulli instrument — the raw faithfulness number is biased, so we debias it with Rogan–Gladen and calibrate the judge's confidence with ECE, Platt, and isotonic recalibration before that confidence can drive a cut. Raising the cut drops low-confidence claims, lifting precision and lowering recall along the frontier, and trading coverage for a guaranteed faithfulness under a distribution-free conformal back-off is exactly the abstention frontier the next topic studies. Finally we read grounding in bits: a supported claim is one whose pointwise mutual information with the context is positive, a hallucination one whose PMI is non-positive. A tested notebook owns every number.
Query Transformation and HyDE: Correcting Distribution Shift in Embedding Space
A query is question-shaped and a document is answer-shaped, so a bare query sits off the document manifold and its nearest documents are mediocre. HyDE writes a hypothetical answer, embeds that, and retrieves real documents near it — landing back inside the manifold. It is pseudo-relevance feedback with a generated rather than a retrieved centroid, and it trades query-document mismatch for one honest new cost: generation bias, which no amount of Monte-Carlo averaging removes.
In a dual encoder the query and document encoders share an embedding space, but the two distributions do not coincide on the sphere: a query is question-shaped, an answer is answer-shaped, so a bare query lands off the document manifold and retrieves mediocre neighbors. HyDE (Gao et al., 2023) corrects this distribution shift without any relevance labels — it asks a language model for a hypothetical answer document, embeds that, and retrieves real documents near it. We formalize HyDE on the dense-retrieval finance geometry as two things at once: a distribution-shift correction (the generated proxy lands inside the document manifold, so retrieval recovers the answer at any shift) and the neural generalization of pseudo-relevance feedback (Rocchio/RM3 expand a query toward the centroid of retrieved documents; HyDE expands it toward the centroid of generated ones). Averaging k hypotheticals is a Monte-Carlo estimate of the answer centroid whose variance falls toward the 1/k rate; but if the generator hallucinates on a fraction p of queries, the estimate is consistent for the wrong center and recall plateaus at a ceiling near 1 − p. That irreducible generation bias is the honest price HyDE pays for closing the gap.
Retrieval versus Long Context: Attention Complexity and Positional Bias
If the context window is large enough to hold everything, why retrieve at all? Because attention costs (kL)² — quadratic in the tokens read — and because more context is not better: once the answer is in hand, extra passages are redundant at best and same-sector distractors at worst, so answer quality peaks at the smallest covering context and declines as you stuff the window, while a relevant passage buried in the middle is read at attenuated attention — a soft erasure. The right move is not a bigger window but a better-chosen one.
Modern context windows are large enough to hold a whole filing, which invites a tempting shortcut: skip retrieval and stuff everything in. This topic gives the mathematics of why that loses. The first reason is the rate: full self-attention over a context of k passages of L tokens forms a (kL)×(kL) score matrix, so the arithmetic cost is Θ((kL)²) — doubling the context quadruples the compute, and FlashAttention lowers the memory to O(n) but leaves the FLOPs untouched. The second reason is the distortion. We read the top-k retrieved passages under a finite attention budget — softmax weights w_j that sum to one — and combine their evidence additively, generalizing the von Mises–Fisher answer model the PMI and noisy-channel topics built: p(a|q,C_k) = softmax((⟨q,μ_a⟩ + Σ_j w_j⟨d_j,μ_a⟩)/τ). On a finance corpus of sectors of confusable companies, each answer carries several relevant passages plus a shell of same-sector distractors. Even with the answer reliably retrieved (recall@1 ≈ 1), answer quality Q(k) = E[p(a*|q,C_k)] is highest at the smallest covering context and declines monotonically: while the top-k is all-relevant the extra passages are redundant — a second filing of the same company moves belief almost not at all, the diminishing-returns result imported from the PMI topic — and once same-sector distractors enter, they steal attention budget and inject wrong-company evidence, so precision falls and the answer entropy H(A|context) rises toward the prior. Recall climbs while precision falls, and answer quality tracks precision, not recall: chasing recall@k by enlarging the window degrades the answer. Read against cost, the focused-retrieval point Pareto-dominates stuffing — quadratically more compute for strictly worse answers. The third pillar is positional: a relevant passage buried in the middle of a long context is read at attenuated attention (lost-in-the-middle), a soft erasure that drops quality even though the passage was retrieved. The answer model is the same synthetic softmax stand-in the previous topics used, so every quality number is exact for the model and illustrative of a real generator; a tested notebook owns every number, and the quadratic cost, the diminishing returns, and the monotone decline are asserted, not asserted-about.
Selective Generation: When a RAG System Should Abstain
The faithfulness topic ended at a back-off frontier — coverage traded for a conformally guaranteed faithfulness — and left a question: what should the system do when the certified-faithful answer is too thin to be worth emitting? It should abstain. The two prior topics decided which claims to keep inside an answer; this one decides whether to answer at all. That answer-level decision has its own mathematics: Chow's cost-optimal reject rule, the risk–coverage curve and its area, the gap a real confidence signal pays against the oracle, a distribution-free guarantee on the wrong-emission rate, and a cost model for abstaining versus erring.
The faithfulness topic measured a generated answer as two numbers and traded coverage for a conformally guaranteed faithfulness along a back-off frontier — deciding which claims to keep. This topic takes the next step the frontier set up: the per-query decision of whether to answer at all. We define the answer-level selective risk (the error rate among the answers emitted) and coverage (the fraction of queries answered), and derive Chow's rule — the cost-optimal reject threshold, abstain iff the probability of being wrong exceeds the cost ratio of abstaining to erring. Sweeping the threshold traces the risk–coverage curve, whose area, the AURC, is the answer-level mirror of average precision; the achievable curve, ordered by a noisy judge's confidence, sits above the oracle curve ordered by truth, and the excess closes only as the signal's discrimination approaches perfect. We then lift conformal risk control from the claim level to the answer level: a monotone wrong-emission loss whose distribution-free threshold controls the rate of confident wrong answers at a chosen level. The whole construction composes with the prior topic's back-off into a two-stage gate — certify the faithful claims, then abstain if the answer is too risky or too thin — and a cost model picks the operating point where a finance RAG defers to a human analyst rather than guess. A tested notebook owns every number, and the build-and-run discipline catches the trap: a too-weak signal makes abstention no better than refusing to answer at all.
Information Theory of RAG
Track completeThe "why retrieval works" layer: mutual information between query, context, and answer; the retriever as a noisy channel; submodular and DPP context selection; multi-hop retrieval; GraphRAG; and the multimodal financial capstone.
Need the ML foundations? formalml.com →
Capstone: The Mathematics of a Production Multimodal Financial RAG System
The retrieval stack arrived as a dozen separate topics — lexical scoring, dense MIPS, IVF and PQ and HNSW, late interaction served by PLAID, reciprocal-rank fusion; this capstone composes the published stack into one finance pipeline and proves the three laws that govern it end to end — cascade recall multiplies across stages, hybrid fusion gains exactly when its legs de-correlate, and a fixed compute budget is allocated across heterogeneous per-modality legs by water-filling — with the single exact statement that a full-budget pipeline recovers brute-force retrieval, and everything above it a heuristic speed-for-recall trade measured honestly on a finance frontier
The retrieval half of a production RAG system arrived as a dozen topics; this capstone composes the published stack — lexical scoring, dense MIPS, IVF/PQ/HNSW candidate generation, PLAID-served late interaction, reciprocal-rank fusion — into one finance pipeline and proves the three laws that govern it end to end. Cascade recall multiplies across independent stages, a conservative lower bound the correlated real legs sit above; hybrid fusion beats its best leg by a margin that grows as the legs de-correlate, and fails when a false positive is co-endorsed by two legs; and a fixed compute budget is allocated across heterogeneous per-modality legs by water-filling, equalizing the marginal recall-per-cost. The one exact statement is the collapse anchor — a full-budget pipeline is brute-force retrieval — and a tested notebook that imports the fusion, PLAID, IVF, and over-fetch code owns every number on the finance frontier. The generation and grounding layer above retrieval is named as future work, not derived.
Context Selection: Submodular Coverage, MMR, and Determinantal Point Processes
Once retrieval returns more candidate passages than the window can hold, which subset do you keep? Ranking by relevance packs the context with near-duplicates that each add almost nothing — the diminishing returns PMI measured in bits — so the right objective is monotone submodular coverage, for which greedy is provably within 1−1/e of the optimum (Nemhauser–Wolsey–Fisher), while MMR trades relevance against redundancy as a popular heuristic with no such guarantee, and a determinantal point process makes diversity a probability P(S) ∝ det(L_S), the squared volume of the selected feature vectors, so two near-duplicates span a flat parallelepiped and are almost never drawn together — and at a fixed budget every one of these diversity-aware rules beats plain top-k on the answer it ultimately produces.
Retrieval returns a ranked list; the generator's window holds a budget of k passages. Filling that budget with the top-k by relevance is the obvious move and the wrong one: the highest-scoring passages of a confusable company are near-duplicates, and the previous topics showed each duplicate adds almost no information — PMI measured it in bits, the long-context topic watched answer quality go flat over the redundant set. This topic gives the mathematics of choosing the subset that maximizes coverage of the query rather than per-item relevance. The natural objective is monotone submodular: facility-location coverage f(S) = Σ_i w_i max_{j∈S} sim(i,j) rewards a selection for standing in for every candidate the query cares about, and submodularity — the marginal value of adding a passage to a larger set is no greater than adding it to a smaller one — is exactly the diminishing-returns property the saturation curve exhibits. Maximizing a monotone submodular function under a cardinality constraint is NP-hard, but the greedy algorithm that adds the highest-marginal-gain passage at each step returns a set worth at least (1−1/e) ≈ 0.632 of the optimum, the Nemhauser–Wolsey–Fisher bound, proved here in full; Minoux's lazy-greedy speeds it up by exploiting submodularity itself. Maximal Marginal Relevance, λ·rel(d,q) − (1−λ)·max_{d'∈S} sim(d,d'), is the field's workhorse diversity heuristic, but — the rigor flag — it carries no submodular guarantee: its penalty is taken against the evolving chosen set, and the closest fixed objective is submodular but non-monotone, exactly the hypothesis the theorem needs. The determinantal point process gives a probabilistic answer: P(S) ∝ det(L_S), where the determinant is the squared volume of the parallelepiped the selected feature vectors span, so near-duplicates span a near-flat solid of near-zero volume and are almost never sampled together; the quality–diversity factorization L = diag(q) S diag(q) separates per-item relevance from a similarity kernel, exact MAP is NP-hard, and the certified object is greedy on the monotone surrogate log det(I + L_S), which inherits the same 1−1/e. We close on the payoff and the honest hinge. The objective we actually want is the answer-information gain I(A;D_S|Q), but mutual information of a set with a target is not submodular in general — not even on this corpus, and provably not for a synergistic pair whose marginal gain increases with conditioning — so coverage, not info gain, is the backbone that earns the theorem. On a finance pool where the most query-relevant passages are sector-generic near-duplicates that support the gold company and its peer equally, while the disambiguating passage is less query-similar, top-k spends its budget on the redundant cluster and leaves the answer split; coverage- and diversity-aware selection reach the disambiguator and sharpen the answer. We read every method through the imported answer_posterior_topk, so the numbers chain with the rest of the arc, and the headline — diversity beats top-k at a fixed budget — is a comparison across methods, pinned to the observed run. A tested notebook owns every number; the lab recomputes only the closed forms.
GraphRAG: Community Detection and the Modularity of Knowledge
Multi-hop retrieval found a path; the relation 'retrievable-from' it traced has by now drawn a graph over the whole corpus, and a global, sensemaking question — what are the dominant themes across all of these filings? — has an answer that is a property of that graph's partition, not of any document or path. This is the mathematics of the partition: modularity scores it against a degree-preserving null and the modularity matrix's leading eigenvector relaxes the optimal split; the resolution limit caps the scale modularity can see; the stochastic block model's detectability threshold says when a thematic decomposition exists to be found at all; and Louvain and Leiden are the NP-hard-forced heuristics, with Leiden's refinement guaranteeing the connected communities Louvain cannot.
Multi-hop retrieval answered a local question — a path from a query to a specific answer document. A global, sensemaking question — what are the dominant themes across the whole corpus? — has no such answer: it is a property of the corpus's partition into communities, and no single chunk and no single path can carry it. GraphRAG builds an entity graph from the corpus and partitions it; this topic is the mathematics of that partition. Newman–Girvan modularity scores a partition against the degree-preserving configuration-model null, the excess of within-community edge weight over chance; on the finance entity graph the planted sectors score 0.778 against a random partition's −0.04. For a bipartition the modularity matrix B = A − kkᵀ/2m has rows summing to zero, so Q = (1/4m)sᵀBs, and the relaxed optimum is B's leading (largest-algebraic) eigenvector, rounded by sign — Newman's spectral method, which matches a brute-force argmax exactly on a small graph and reports a clique indivisible when that eigenvalue is non-positive. The integer optimum is out of reach: modularity maximization is NP-hard, so spectral rounding, Louvain, and Leiden are all heuristics. Modularity also has a resolution limit (Fortunato–Barthélemy): on a ring of thirty cliques the optimal partition merges adjacent cliques even though each is a genuine community, because the global √(2m) normalization makes a small clique invisible; the resolution parameter γ only moves the scale, it does not remove the limit. The deep result is the stochastic block model's detectability transition: for the symmetric two-block sparse SBM, a partition correlated with the planted one is recoverable if and only if (c_in − c_out)² > 2(c_in + c_out), the Kesten–Stigum threshold — below it, no algorithm beats a coin flip, an information-theoretic converse and the community-detection analogue of the channel capacity the noisy-channel topic priced. We demonstrate it numerically: above the line spectral recovery overlaps the truth at 0.93, below it at 0.01. Louvain (local-moving plus aggregation, with a closed-form ΔQ) and Leiden (adding a refinement phase that guarantees internally-connected communities) are the workhorses; a disconnected community can be a Louvain local optimum its local moving cannot repair, and Leiden's refinement is exactly what forbids it. The modularity of knowledge is literal: a corpus decomposes into themes worth summarizing precisely when modularity is high, the resolvable scale is coarse enough, and the block signal clears Kesten–Stigum — below threshold there is no decomposition to summarize, and GraphRAG degrades to flat retrieval. The entity graph is a synthetic planted partition on the finance vMF geometry, exact for that model and illustrative of a real knowledge graph; a tested notebook owns every number and the lab recomputes only the closed forms.
Multi-Hop and Iterative Retrieval as Search over an Evidence Space
A compositional question — the revenue of the company that acquired Company A's primary supplier — hides its answer in a document the query cannot reach in one retrieval: near-orthogonal to the query on the embedding sphere, yet a short reformulation away through a bridge filing that names the supplier. Retrieval becomes a search over an evolving evidence space, where each hop is the previous topic's retrieve-and-select step, end-to-end recall is the product of per-hop recalls, an information-theoretic stopping rule decides when the marginal evidence no longer pays its cost, and — the climax — single-shot selection provably cannot shortcut the path because the bridge and answer form a supermodular synergy.
Single-hop retrieval answers a question by finding documents near the query on the embedding sphere. A compositional question — the revenue of the company that acquired Company A's primary supplier — defeats it: the answer document is near-orthogonal to the query (their cosine is below the edge threshold) and reachable only through a bridge document that names the supplier. On the retrieval graph, whose nodes are documents and whose edges are the relation 'retrievable-from', the answer sits at graph distance two, so single-hop recall is essentially zero while multi-hop recall is essentially one — the compositional gap. This topic frames multi-hop and iterative retrieval as search over an evidence space: a state is a belief over answers, an action is a reformulated query, a trajectory is a path through the graph, and each hop is exactly the retrieve-and-select operator the previous topic certified. The reformulation operator q' = normalize(d − ⟨d,q⟩q) extracts the new entity a read filing names, the part orthogonal to the current query — and that is what turns a bridge into the next query. The greedy hop maximizes expected marginal information; the optimal policy satisfies a Bellman recursion we name but do not solve, because it is intractable over the belief simplex. We then pay the bill of chaining: end-to-end recall is the product of per-hop recalls, so it decays geometrically, and to hold an end-to-end target ρ each of k hops must over-retrieve to ρ^(1/k) — though positive dependence between hops, by the same FKG argument the capstone used for cascades, makes the independent product a conservative lower bound, the safe direction to provision. We close on stopping and the climax. A hop's marginal information is the new direction its filing opens; the rule is to stop when that residual collapses — when the read filing names no one new — which makes the realized hop count equal the chain depth. Greedy hopping earns no 1−1/e guarantee, and the reason is the heart of the topic: information gain is not submodular, and the compositional question is its supermodular, synergistic case — the bridge alone says nothing about the answer, the answer document alone cannot be recognized as relevant, yet together they resolve it, the exact XOR witness the context-selection topic used. So single-shot selection provably cannot reach the answer — it is never in the one-hop pool — and a myopic stopping rule that watches the belief would halt at the worthless-looking bridge; only reformulating from the bridge's content harvests the synergy. The synthetic von Mises–Fisher answer model is exact for the model and illustrative of a real retriever, and the compositional-gap headline is one constructed corpus, not a universal law; a tested notebook owns every number and the lab recomputes only the closed forms.
Pointwise Mutual Information: What Retrieval Adds to Generation, in Bits
Generation begins with an answer prior p(a|q) and a retrieved document sharpens it to a posterior p(a|q,d); the log-ratio of the two is the pointwise mutual information of that document for that answer — positive for a relevant filing, negative for a distractor that costs bits — and its average is the conditional mutual information I(A;D|Q), the entropy retrieval removes, the same quantity the dense encoder's InfoNCE objective maximized a lower bound on
Retrieval is usually scored by whether the right documents came back — recall, average precision, the set-metric family. This topic scores it by a different, information-theoretic question: how many bits does a retrieved document add to the generator's answer? Generation begins with a prior over answers conditioned on the query alone, p(a|q), which is uncertain, with entropy H(A|Q). A retrieved document d sharpens it to a posterior p(a|q,d). The pointwise mutual information pmi(a;d|q) = log p(a|q,d)/p(a|q) is, for a particular answer a, the log-factor by which the document moved the odds — the literal log of a Radon–Nikodym density ratio. Its expectation over the posterior is the per-document information gain, the KL divergence KL(p(·|q,d) ‖ p(·|q)) ≥ 0, and averaging over documents and queries gives the conditional mutual information I(A;D|Q) = H(A|Q) − H(A|Q,D): the entropy retrieval removes, the bits it adds, verified three ways. We then make four points the set-metric layer could not see. A relevant filing has positive pmi on the true answer; a plausible distractor has negative pmi — it costs bits, dragging the posterior toward a wrong answer. A second document that merely repeats the first adds almost nothing — diminishing returns are the chain rule of mutual information, not a heuristic. The dense encoder we trained was, all along, maximizing an InfoNCE lower bound on this very I(Q;D), so retrieval value and contrastive training measure the same quantity from two directions. And bits-added is orthogonal to recall: on an easy corpus where every gold filing is retrieved, recall reads 'perfect' for every query while the bits actually delivered vary widely. The answer model is a synthetic von Mises–Fisher exponential-family stand-in, not a transformer, so every bit is exact for the model and illustrative of a real generator; a tested notebook owns every number.
The Retriever as a Noisy Channel: Recall, Precision, and Information Limits
Read the retriever as a communication channel: a query enters, a context comes back, a generator decodes an answer. A recall failure ERASES the relevant filing, so the bits delivered fall exactly as recall × I(A;D|Q) — the capacity of a binary erasure channel — and Fano's inequality turns the residual entropy H(A|Q,D) into a floor on the answer error that no generator beats. A precision failure SUBSTITUTES a plausible distractor, and the generator answers confidently wrong while that same entropy floor sees nothing. Recall sets the floor; precision governs whether you hit it.
The pointwise-mutual-information topic measured how many bits a retrieved document adds to the generator's answer: the conditional mutual information I(A;D|Q) = H(A|Q) − H(A|Q,D). This topic reads the same machinery as a communication channel — a query enters, the retriever emits a context, a generator decodes an answer — and asks what the channel's recall and precision do to the bits, and what the bits do to the answer error. The two words of the subtitle are the channel's two failure modes, and they are co-equal headlines. A recall failure is an ERASURE: the relevant filing is dropped and the generator falls back to a non-informative belief, so the bits delivered fall exactly as recall × I(A;D|Q) — the capacity of a binary erasure channel is its surviving fraction, here the recall. What is lost reappears as residual entropy H(A|Q,D), which climbs toward log₂K, and Fano's inequality converts that residual into a floor on the generator's Bayes error, P_e ≥ (H(A|Q,D) − 1)/log₂K — a hard limit no generator beats. Recall sets the floor. A precision failure is a SUBSTITUTION: a plausible same-sector distractor is returned, the generator reads it and answers confidently wrong, the realized error climbs to 1 — yet H(A|Q,D) stays low, so the Fano floor never moves. An entropy bound cannot see confident contamination; the gap between realized error and the Bayes floor is exactly what the faithfulness and calibration layer must close. Precision governs whether you hit the floor. We close by reading the recall–precision operating point as a rate–distortion choice: the retriever spends bits read to buy down answer error. The answer model is the same synthetic von Mises–Fisher exponential-family stand-in the prior topic built, so every bit is exact for the model and illustrative of a real generator; a tested notebook owns every number, and the capacity identities and Fano's inequality are asserted, not asserted-about.
Building your foundations?
Many topics here build directly on machine-learning theory — representation learning, information theory, conformal prediction — covered on formalml.com . The deeper foundations live on formalcalculus.com (linear algebra, optimization, analysis) and formalstatistics.com (estimation, testing, calibration) — all with the same geometric-first approach.