RAG 08 — Two-Step Retrieval: Architecture & Cost-Quality Mathematics

00

Topics We'll Cover

Why Two Steps? — The Operational Picture
Bi-Encoder vs Cross-Encoder — The Fundamental Asymmetry
Indexability — Why MIPS Scales and Cross-Attention Doesn't
ANN Mathematics — HNSW, IVF, PQ, Recall–Latency Trade-offs
Recall, Precision, and the Recall-Ceiling Theorem
Fusion Mathematics — RRF Derivation, CombSUM, Z-Score
Latency Composition — Means, Percentiles, Parallelism
Cascade Depth — The (k, Quality, Latency) Pareto Frontier
Score Calibration — Platt, Isotonic, Temperature
Worked Example — 10 M Documents, 200 ms Budget
What to Take Away

Companion deck

This deck covers the architecture and cost-quality mathematics of the two-stage cascade. Its sibling, RAG 09 — Reranker Mathematics, takes the second stage and derives the actual scoring functions and training losses: cross-encoder attention, ColBERT MaxSim, RankNet / LambdaRank / LambdaMART, InfoNCE, MarginMSE distillation, and the metric mathematics (DCG / NDCG / MRR / MAP).

01

Why Two Steps? — The Operational Picture

Every serious RAG system in production is a cascade: a cheap, high-recall stage that scans the entire corpus, followed by an expensive, high-precision stage that re-scores a short-list of survivors. The structure is not an implementation detail — it is the only architecture that makes the cost arithmetic work.

The arithmetic that forces a cascade

A modern cross-encoder reranker scores one (query, document) pair in 1–5 ms on a single GPU. A modest production corpus has 10⁷ documents. Scoring every pair: 10⁷ × 2 ms = 5.5 hours per query. Per query. With one user. The cascade exists because we cannot run the precise model on the whole corpus.

Stage 1
cheap, indexed, recall−oriented

→

Optional fusion
BM25 ∪ dense

→

Stage 2
expensive, exact, precision−oriented

→

Top-k to LLM

The cascade is justified by two empirical observations that hold across almost every retrieval benchmark:

Cheap models have high recall at large k. A bi-encoder or BM25 with k=100 typically captures >95% of relevant documents on BEIR-style corpora — even if their ranking inside the top-100 is mediocre.
Expensive models have high precision at small k. A cross-encoder reranker applied to a 100-item short-list typically lifts NDCG@10 by 5–15 points over the bi-encoder's own top-10 — because cross-attention lets every query token see every document token.

The cascade composes the strengths: cheap recall × expensive precision = both. Everything in this deck is a quantitative consequence of that composition.

02

Bi-Encoder vs Cross-Encoder — The Fundamental Asymmetry

The two stages exist because there are two structurally different ways to score a (query, document) pair. They differ in where the query and document interact.

Bi-encoder — late, scalar interaction

s(q,d) = ⟨ f_θ(q), g_φ(d) ⟩

Query and document are encoded independently into a single vector each: f(q), g(d) ∈ ℝ^D. Score is a single inner product. Time per pair: O(D). Document vectors can be precomputed once and stored in an index.

Cross-encoder — early, full-token interaction

s(q,d) = h_ψ([CLS] q₁…q_|q| [SEP] d₁…d_|d|)

Concatenate query and document into one transformer input. Every query token attends to every document token in every layer. Time per pair: O((|q|+|d|)²) in the attention layers. Document representations depend on the query and cannot be cached.

Why the cross-encoder wins on precision

In a bi-encoder, the only path from query token q_i to document token d_j is through two pooled scalars. Token-level evidence (a single matching named entity, a specific operator, a date) has to fight its way into a global pooled vector. In a cross-encoder, query token q_i can attend directly to document token d_j in layer 1 and refine that attention in every subsequent layer. The fine-grained signal is preserved end-to-end. The cost of preserving it: you must re-run the model on every (q,d) pair you want to score.

Property	Bi-encoder	Cross-encoder
Score formula	⟨f(q), g(d)⟩	h([CLS] q [SEP] d)
Doc encoding depends on query?	No — precompute once	Yes — recompute every query
Cost of one score (BERT-base)	1 dot product ≈ 1–3 μs	1 full forward pass ≈ 1–5 ms (GPU)
Cost over corpus of N docs	1 query encode + N dot products = O(D·N)	N full forward passes = O(L·N)
Indexable by MIPS / ANN?	Yes (see slide 03)	No — no factorisation exists
BEIR avg NDCG@10 (2024 SOTA)	≈ 48–52 (BGE-M3, E5-mistral)	≈ 55–60 (BGE-Reranker-v2-m3, Cohere)

03

Indexability — Why MIPS Scales and Cross-Attention Doesn't

An index speeds up retrieval by exploiting structure in the scoring function. Whether structure exists is a property of the function, not the data. This is where the bi-encoder / cross-encoder split becomes a hard mathematical wall.

Maximum Inner Product Search (MIPS)

For a bi-encoder, retrieving the top-k documents is the problem:

d^∗ = arg max_{d ∈ D} ⟨ f(q), g(d) ⟩

Crucially, f(q) is fixed once the query is encoded; only g(d) varies as we sweep d. The problem reduces to finding the nearest neighbour of a fixed point in a precomputed point cloud {g(d) : d ∈ D}. This admits sub-linear indexing — tree-, graph-, and quantisation-based structures all work.

The cross-encoder is non-factorisable

For a cross-encoder, the score is h([CLS] q [SEP] d). There is no decomposition

h(q, d) = ⟨ φ(q), ψ(d) ⟩

that holds for general inputs. Self-attention layers contain softmax(QK^T/√d) V where Q, K, V are computed from all tokens jointly. There is no way to precompute a per-document representation that supports cheap query-time scoring under arbitrary cross-attention. This is the indexability barrier.

A formal way to see the barrier

Suppose, for contradiction, that a cross-encoder admits a factorisation h(q,d) ≡ ⟨φ(q), ψ(d)⟩ with φ, ψ mapping to ℝ^D. Then the rank of the matrix M_q,d = h(q, d), over any finite set of queries and documents, is at most D. But the matrix of cross-encoder scores has empirically been shown to be approximately full rank on real corpora — if it were not, a bi-encoder of dimension D would match cross-encoder quality, which is false. Hence no exact factorisation exists.

What ColBERT (partly) buys you

ColBERT keeps token-level embeddings on both sides and replaces full cross-attention with a per-query-token max:

s(q,d) = Σ_{i ∈ q} max_{j ∈ d} ⟨ E_{q_i}, E_{d_j} ⟩

This is factorisable per document (each document's tokens are independent of the query at encode time) and admits a token-level inverted index. It is a strict relaxation of full cross-attention — each query token chooses its match in isolation, with no joint reasoning across query tokens — but it preserves enough token-level signal to close most of the gap to a cross-encoder. Covered in detail in Deck 09.

04

ANN Mathematics — HNSW, IVF, PQ, Recall–Latency Trade-offs

Bi-encoder retrieval over millions of vectors is fast only because we use an approximate nearest-neighbour structure. The three production-grade families — HNSW, IVF, and PQ — each trade exactness for speed in a different way.

HNSW — Hierarchical Navigable Small World

Multi-layer proximity graph. Top layer is sparse; bottom contains every vector. Search descends greedily, beam width ef_search controls candidate set per layer.

Expected query complexity: O(log N). Recall is monotone in ef_search; bigger ef = more recall, more latency. Memory: ~1.2–1.5× the raw vectors (graph overhead).

IVF — Inverted File / Cluster-Then-Search

K-means into n_list centroids at build time. Query: pick the n_probe nearest centroids, search only those cells.

Cost: O(n_probe · N/n_list) distance evaluations. Typical: n_list = √N, n_probe = 8–32. Recall scales sharply with n_probe; latency scales linearly.

PQ — Product Quantisation

Split each D-dim vector into m sub-vectors of dim D/m. K-means each sub-space to 2^b codes. Store one byte (b=8) per sub-vector.

Memory: m bytes per vector instead of 4D. Distance via lookup table — ~8× faster than float dot product but lossy. Usually layered under HNSW or IVF for compression.

The recall–latency curve, formally

Every ANN structure exposes a knob (ef_search, n_probe, refinement depth) whose monotone increase produces a smooth recall–latency curve:

Recall@k(ξ) = Pr[ true top-k ⊆ ANN(ξ) ], ξ = knob value

Two empirical facts shape all production tuning:

Recall is concave. Going from 90% to 95% costs roughly as much as going from 95% to 97%. Pushing past 99% costs as much as everything below it. Pick a target and stop.
Latency is roughly linear in the knob. Doubling ef_search doubles distance evaluations. Doubling n_probe doubles cell scans. There are no free lunches inside one method — the lunches come from changing methods (IVF→HNSW, fp16→int8, refine-with-fp32).

Binary quantisation with float rescoring

A high-leverage 2024 pattern: index 1-bit-per-dimension binary vectors with Hamming distance (32× memory reduction, 4–10× speed-up), then rescore the top ~200 candidates with the original fp16/fp32 vectors. Recall@10 typically drops by <1% versus float indexing. Supported in Qdrant, Vespa, Weaviate, Milvus, and Postgres pgvector 0.7+.

05

Recall, Precision, and the Recall-Ceiling Theorem

Each stage of the cascade has a different optimisation target. Confusing them is the most common architectural mistake in RAG pipelines.

Stage	Optimise for	Why	Typical k
Stage 1 (retriever)	Recall	Anything missed here is lost forever — no downstream stage can recover it.	100–1000
Stage 2 (reranker)	Precision & rank quality (NDCG, MRR)	The LLM sees only the top-k. Bad ranking here is bad context.	5–20
Stage 3 (LLM)	Faithfulness	Given the top-k, does the generation cite them correctly?	3–10 in prompt

Recall-ceiling theorem (informal)

Let R₁(k) = Recall@k of stage 1 over a query distribution. For any stage-2 reranker 𝒻, including an oracle that ranks the stage-1 short-list perfectly:

Recall@k_final(𝒻) ≤ R₁(k₁) for any k ≤ k₂ ≤ k₁

Stage-1 recall is the global ceiling. If your stage-1 Recall@100 is 92%, then 8% of user queries have no answer reachable from stage 2 — no matter how good your reranker, no matter how big your LLM. The only fix is at stage 1: better embeddings, hybrid retrieval, larger short-list, query rewriting.

Operational consequence

Before tuning anything downstream, measure Recall@k₁ on a labelled set. If it is below ~90% at the short-list size you can afford to rerank, the cascade is fundamentally capped — investing in a better reranker buys nothing. Fix stage 1 first.

06

Fusion Mathematics — RRF Derivation, CombSUM, Z-Score

When stage 1 fans out into multiple retrievers (BM25 + dense, plus perhaps domain-specific lexical or graph retrievers), their result lists must be fused. The fusion methods differ in what they assume about score scales.

The score-scale problem

BM25 returns unbounded positive scores whose magnitudes depend on document length, query term IDF, and corpus statistics. Dense bi-encoder cosine similarity returns values in [-1, 1] with most relevant pairs in [0.3, 0.9]. Adding them directly is meaningless — one retriever's noise floor can be louder than the other's signal.

CombSUM — the original (Fox & Shaw, TREC-3, 1994)

CombSUM(d) = Σ_r norm_r(score_r(d)) over retrievers r

Requires per-retriever score normalisation — usually min-max to [0,1] or Z-score:

z-norm(s) = (s − μ_r) / σ_r μ_r, σ_r over the retrieved short-list

Sensitive to outliers and to query-to-query score distribution drift — one query with a huge top score skews the entire normalisation.

RRF — Reciprocal Rank Fusion (Cormack, Clarke & Büttcher, SIGIR 2009)

RRF(d) = Σ_r 1 / (k + rank_r(d)) rank starts at 1; k = 60 in the original paper

Uses only ranks, never raw scores. Three properties make it the modern default:

Scale-free. BM25 returning 38.7 and cosine returning 0.72 are mapped to ranks 1, 2, 3, … identically. No normalisation step.
Smooth top-end emphasis. The reciprocal function gives most weight to ranks 1–10 but never zero to lower ranks. With k=60: rank 1 → 1/61 ≈ 0.0164, rank 10 → 1/70 ≈ 0.0143, rank 100 → 1/160 ≈ 0.00625. A document ranked 1 by one retriever and 100 by another beats one ranked 50 in both.
The constant k=60 is empirical. Cormack et al.'s ablation showed k=60 outperformed CombSUM and tuned learned fusion on TREC tracks. Larger k flattens the top-end emphasis (closer to a constant); smaller k over-rewards rank 1. Modern systems sometimes use k=20–100 with little measured difference.

CombMNZ — rewarding agreement

A variant: CombMNZ(d) = (number of retrievers that returned d) × CombSUM(d). Documents found by all retrievers are boosted. Rarely used in modern pipelines because RRF achieves a similar agreement-boosting effect implicitly — a document in the top-10 of every retriever accumulates many reciprocals, while a document found only once accumulates one.

Learned fusion — when it pays

If you have labelled query–document pairs (clicks, manual judgments, LLM-as-judge), a small LambdaMART or shallow MLP over per-retriever rank-features (rank_r(d), score_r(d), 1/rank_r(d), retriever indicator) typically beats RRF by 1–3 NDCG@10 on the training distribution. The training cost is rarely worth it for a single-domain RAG system — use RRF until measured otherwise.

07

Latency Composition — Means, Percentiles, Parallelism

Latency budgets are not additive in the obvious way. The mean of a sum is the sum of means, but tail percentiles compose much worse, and parallelism reshapes the budget entirely.

Means add. Percentiles don't.

For independent stages with latencies X, Y:

E[X + Y] = E[X] + E[Y] means add P99(X + Y) ≠ P99(X) + P99(Y) in general

If X and Y are independent and roughly Gaussian, P99(X+Y) ≈ √(P99(X)² + P99(Y)²) — squared addition. But on real systems stage latencies are correlated (GC pauses, GPU contention, network blips), so the worst case is closer to P99(X) + P99(Y). Plan against the worst case until you have measurements.

Sequential vs parallel stages

Sequential: BM25 → dense → rerank

L = L_BM25 + L_dense + L_rerank

Typical 1M-doc corpus: 15 + 8 + 80 = 103 ms mean. P99 closer to 50 + 25 + 130 = 205 ms. Wastes the obvious independence of stage 1.

Parallel stage 1 + sequential rerank

L = max(L_BM25, L_dense) + L_fuse + L_rerank

Same numbers: max(15, 8) + 1 + 80 = 96 ms mean — modest mean win, but a larger tail win because the slow retriever drives the max. Doable with asyncio.gather or any thread pool.

The reranker latency function

A batched cross-encoder reranker scoring k candidates has latency roughly:

L_rerank(k) ≈ t_load + ⌈ k / B ⌉ · t_fwd(B, L_seq)

where B is GPU batch size, L_seq is sequence length, t_fwd is per-batch forward time. Two practical levers:

Batch the candidates. A batch of 64 (q, d) pairs is rarely 64× a single pair; for typical 512-token sequences on A100/H100 it is ≈ 4–8×. Most published reranker latency numbers assume good batching — verify yours does too.
Truncate aggressively at the right place. Halving L_seq usually nearly halves t_fwd (attention is quadratic but FFN is dominant at these sizes — closer to linear in practice). But truncating the document below ~200 tokens can lose information silently — see RAG 03 on chunk-and-max.

08

Cascade Depth — The (k, Quality, Latency) Pareto Frontier

Tuning a cascade is a constrained optimisation. There is one free knob — the short-list size k — that simultaneously trades against quality and latency. Plotting one against the other yields the Pareto frontier and tells you exactly where to operate.

The optimisation, formally

max_k NDCG@10(rerank_top−k(stage1)) subject to L(k) ≤ budget

Three behaviours hold across every cross-encoder reranker on every modern benchmark:

NDCG@10 is monotone non-decreasing in k. A larger short-list contains a superset of the previous one; the reranker can only add information, never remove it (assuming a deterministic reranker).
NDCG@10 saturates by k ≈ 100–200. Beyond a few hundred candidates, almost all the marginal documents are negatives, and the reranker's gain plateaus. Measured on BEIR with BGE-Reranker-v2-m3 the typical curve flattens around k=100.
Latency is linear in k for a batched reranker. Once you exceed one batch, doubling k roughly doubles reranker time.

The shape of the frontier

NDCG@10 vs k typically follows a concave saturating curve; latency follows a near-linear ramp. Their composition is a classic logarithmic-in-quality, linear-in-cost frontier. The Pareto-optimal operating point is the knee — usually k=50–100 on text reranking. Below the knee you leave quality on the table; above it, you pay linear latency for vanishing returns.

How to find your knee in practice

Build a labelled eval set (500–2000 queries with known relevant docs — LLM-generated questions are fine, see RAG 03 slide 08).
Run the cascade with k ∈ {10, 25, 50, 100, 200, 500}. Record NDCG@10 and end-to-end P50/P99 latency.
Plot NDCG@10 vs P99 latency. Pick the smallest k that hits your quality SLO; if every k hits it, pick the smallest. If none hits it, fix stage 1 (recall ceiling) before tuning further.

09

Score Calibration — Platt, Isotonic, Temperature

Reranker scores are not probabilities. They are logits or unnormalised real numbers that have been trained for ranking, not for absolute probability. If you want to use a score as a confidence threshold (“drop any document with relevance < 0.3”) or compare scores across queries, you must calibrate.

Why uncalibrated scores fail

Rank-loss training has no probability target. Pairwise losses (RankNet, see Deck 09) only constrain s(q,d⁺) > s(q,d⁻). A model that outputs (1.0, 0.99) is just as good as one that outputs (100, 0.1).
Cross-query incomparability. One query may have ten near-duplicates in the corpus (high mean score); another may have one genuine match (low absolute score). Raw scores cannot be compared across queries.

Platt scaling — a sigmoid on the logit

Fit a one-parameter (or two-parameter) sigmoid to map reranker score s to a calibrated probability:

P(rel | s) = σ(a · s + b) = 1 / (1 + exp(−(a s + b)))

Fit a, b by maximum-likelihood on a held-out set of (s, binary-rel) labels. Lightweight, monotone, and reversible. Works well when the score-to-probability map is roughly sigmoidal — usually true for cross-encoder logits.

Temperature scaling — even simpler

P(rel | s) = σ(s / T) fit T > 0 on a calibration set

A one-parameter restriction of Platt (a=1/T, b=0). Often used for neural classifiers; rarely the best fit for reranker outputs, but easy and hard to overfit.

Isotonic regression — non-parametric

Fit a monotone step function from s to P(rel | s) by pool-adjacent-violators. No functional form — learns whatever monotone map fits. Pros: handles any shape, including S-curves, hockey-sticks, or plateaus. Cons: needs more calibration data (~1000+ pairs); not differentiable; harder to extrapolate beyond the training range.

Calibration matters most for cascade exits

The two places calibration is load-bearing: (1) early exit — if the top reranker score is above threshold τ_high, skip the LLM and return the document directly; (2) abstention — if every score is below τ_low, return “I don't know” instead of hallucinating from poor context. Both need cross-query-comparable probabilities, not raw scores.

10

Worked Example — 10 M Documents, 200 ms Budget

Concrete numbers ground the abstractions. Consider a typical mid-scale enterprise RAG: 10⁷ chunks, a 200 ms retrieval budget (300 ms left for LLM), single-GPU reranker.

Stage	Choice	Mean	P99	Notes
Query encode (bi-encoder)	BGE-base (110 M), fp16, GPU	4 ms	9 ms	Single query, no batch
BM25 retrieve	OpenSearch, 4 shards, top-200	22 ms	70 ms	Parallel with dense
Dense ANN retrieve	Qdrant HNSW, ef=128, top-200, binary+rescore	12 ms	30 ms	Parallel with BM25
RRF fusion	k=60, in-process Python	<1 ms	<1 ms	Reduces to top-100
Cross-encoder rerank	BGE-reranker-base (278 M), L_seq=384, batch=64, A10	85 ms	140 ms	One batch covers k=100
End-to-end retrieval	Parallel stage 1 + sequential rerank	≈ 110 ms	≈ 220 ms	P99 just over budget

Knobs if P99 misses the 200 ms target

In rough order of leverage: (1) drop k from 100 to 50 — saves ~40 ms reranker P99 for typically 1–2 NDCG@10 points; (2) use a smaller reranker (ms-marco-MiniLM-L-6, ~20 ms for k=100, ~4 NDCG@10 worse); (3) move the reranker to a dedicated GPU and serve via gRPC (cuts variance, not mean); (4) cache rerank scores on (query-hash, doc-id) for repeat queries; (5) use ColBERT-MaxSim instead — comparable quality, lower latency at k>200 (see Deck 09).

Where the 5.5 hours went

Recall slide 01: scoring all 10⁷ docs with the cross-encoder would take 5.5 hours. The cascade compresses that into ~85 ms by:

Cutting 10⁷ → 200 with two indexed bi-encoders (5×10⁴× reduction)
Cutting 200 → 100 with rank fusion (2× reduction)
Running the expensive model only on the surviving 100 candidates (cross-encoder runs ~2×10⁵× less work)

Net speed-up: ~2×10⁵×. That is the entire point of the architecture.

11

What to Take Away

The cascade is not an implementation choice. Cross-encoders are not factorisable, so they cannot be indexed. A two-step architecture is the only one that admits both whole-corpus reach and token-level scoring.
Bi-encoder vs cross-encoder is an asymmetry about where the query and document interact. Late (single dot product) is indexable; early (joint transformer) is not. Everything else follows from that.
The recall-ceiling theorem is unconditional. Stage-1 Recall@k₁ is the global upper bound on final-stage recall. Measure it before tuning anything downstream.
RRF is the default fusion for a reason. Scale-free, zero parameters to tune, within 1–3 NDCG of learned fusion at no training cost. Use k=60 unless you have ground-truth data and an ablation budget.
NDCG@10 saturates near k≈100 on most text rerankers. The Pareto knee is small. Find it empirically; don't over-rerank.
Calibrate before you threshold. Reranker scores are not probabilities. Platt or isotonic mapping is mandatory for early-exit and abstention logic.
Parallelise stage 1. BM25 and dense ANN are independent operations; running them sequentially is unforced.

Where to next

The companion deck, RAG 09 — Reranker Mathematics, dives into stage 2 itself: the cross-encoder architecture, ColBERT's late-interaction MaxSim, the learning-to-rank loss family (pointwise, pairwise RankNet, listwise LambdaRank / LambdaMART), the InfoNCE contrastive loss used to train modern bi-encoders, MarginMSE distillation from teachers to students, and formal derivations of the evaluation metrics (DCG with log₂ discount, NDCG, MRR, MAP) and their relationship to the loss functions.