Multi-stage & semantic reranking

The cascade exists because cost-per-document rises 100–1000× at each stage. You can only afford the most accurate model on a handful of documents — so reranking is where you spend a latency budget to buy accuracy, and the whole craft is spending it wisely.

This lesson depends on two predecessors. From 43 (dense & hybrid retrieval) you have the bi-encoder: query and document encoded into separate vectors, scored by dot product, precomputed and indexed in an ANN structure — that's how retrieval pulls a thousand candidates out of millions cheaply. From 44 (learning to rank) you have the mid-stage GBDT/LTR ranker that scores those thousand on hundreds of features. This lesson adds the final, most expensive stage — the neural reranker that runs on the top few dozen — and explains the model architectures (cross-encoder, late interaction) that make accuracy buyable. It sets up 48 (relevance evaluation) — how you prove the rerank actually helped — and 49 (system design), where the whole cascade gets a latency budget.

The cascade exists because cost rises faster than accuracy

A search pipeline is a cascade (also called a multi-stage retrieval-and-ranking funnel; lesson 1 introduced the recsys version). Each stage takes the survivors of the previous one, applies a more expensive and more accurate model, and passes a smaller set forward. The reason this shape is forced — not a convenience but a necessity — is a single inequality:

cost-per-document × number-of-documents ≤ stage latency budget

The left side is what you spend; the right is what you have. Retrieval scores millions of documents, so its per-doc cost must be near-zero (a dot product, or a posting-list increment). The reranker is a transformer that does full attention over a query and a document — milliseconds per pair — so it can only touch a handful. If cost-per-doc rises 100–1000× from one stage to the next, the candidate count must fall by a similar factor to keep the product under budget. That is the whole logic of the funnel.

Worked numbers — the budget at each stage. Suppose retrieval has 10 ms. At 0.0005 ms/doc that is 10 / 0.0005 = 20,000 dot products of headroom — but ANN (lesson 3) lets it touch millions without scoring them all, so the real constraint there is the index, not the per-doc cost. The mid-ranker gets 20 ms at 0.05 ms/doc → it can score 20 / 0.05 = 400 docs comfortably, ~1,000 if you push it. The reranker gets, say, 50 ms at 8 ms/doc → 50 / 8 ≈ 6 docs sequentially. That is far too few — which is exactly why reranking lives and dies on batching and parallelism, the subject of the widget below. Without them, the expensive stage can rerank single digits; with them, dozens.

Bi-encoder vs cross-encoder — the central distinction

Everything about why retrieval and reranking use different neural models comes down to when the query meets the document. There are two architectures, and the difference is whether they interact early (inside the transformer) or late (only at the dot product).

Bi-encoder. The query and each document are encoded independently into fixed vectors, and the relevance score is their dot product (or cosine). Because the document vector doesn't depend on the query, you can compute it once at index time and store it. At query time you encode only the query and do a vector search — that's dense retrieval (43). The architecture's defining property is precisely that the document side is precomputable and indexable. The cost: query and document never see each other inside the model, so the score can only capture coarse, query-independent notions of what the document is "about." A passage that answers the query through subtle term overlap or negation often scores no differently than a topically-similar passage that doesn't actually answer it.

Cross-encoder. The query and a document are concatenated into a single input — [CLS] query [SEP] document [SEP] — and fed jointly into one transformer. Now every query token can attend to every document token through full self-attention. The model can directly represent "does this specific phrase in the document answer this specific part of the query?" This is dramatically more accurate — typically several NDCG points over a bi-encoder on the same data. The cost is the mirror image of the bi-encoder's benefit: the score depends on the (query, document) pair, so nothing can be precomputed. You must run the full transformer forward pass for every candidate, at query time. That is why a cross-encoder is a reranking model and never a retrieval model — you cannot index a function that hasn't yet seen the query.

The reranking latency math, done explicitly

Reranking N candidates with a cross-encoder costing c ms per pair has a naive cost of N × c if you run them one at a time. The whole engineering problem is that this number is enormous unless you control both N and the effective per-doc cost. Three regimes:

The crucial subtlety the table makes concrete: a cross-encoder forward pass is not linear in N on real hardware. A GPU processing a batch of 50 (query, doc) pairs does it in roughly one forward pass of wall-clock time — the 8 ms/pair figure is the amortized cost, and batching collapses it. So the real latency knob is "how big a batch fits, and across how many replicas," not "8 ms times N." The widget below lets you turn those knobs. But batching has a ceiling — sequence length, GPU memory, and tail latency from the slowest doc in the batch — so you cannot make N arbitrarily large for free. The two levers remain: keep N small (let the mid-ranker do the culling), and batch hard.

Late interaction (ColBERT) — the middle ground

The bi-encoder collapses a whole document into one vector before the query is known; the cross-encoder refuses to collapse anything and pays for it at query time. Late interaction (ColBERT, Khattab & Zaharia 2020) sits between them with a clever trick: precompute a vector per token of the document, not one per document. The query is also encoded per token at query time. The relevance score is MaxSim: for each query token, find its best-matching document token (max dot product over the document's token vectors), then sum those maxima over query tokens.

score(q, d) = Σ_{i ∈ q-tokens} max_{j ∈ d-tokens} ⟨ q_i, d_j ⟩

This recovers much of the cross-encoder's token-level matching ("does some doc token strongly match this query token?") while keeping the document side precomputable — the per-token doc vectors don't depend on the query, so they can be computed at index time and stored. The query-time work is just the MaxSim aggregation: cheap dot products and maxes, no transformer forward pass per candidate. ColBERT can even drive retrieval directly (via a token-level ANN index), but its most common use is exactly the role of this lesson: a cheap, accurate reranker over the mid-stage candidates.

Worked numbers — the storage cost. A bi-encoder stores one vector per doc: at d = 768 fp16, that's 768 × 2 = 1,536 bytes ≈ 1.5 KB/doc. ColBERT stores one vector per token; a 200-token document at the same dim is 200 × 1,536 = 307,200 bytes ≈ 300 KB/doc — ~200× the storage. In practice you compress aggressively: project to d = 128 and quantize to ~2 bits/dim (ColBERTv2's residual compression), bringing it down to roughly 200 × 128 × 0.25 ≈ 6.4 KB/doc — still several× a bi-encoder, but workable. The trade is explicit: ColBERT buys cross-encoder-adjacent accuracy and bi-encoder-adjacent query latency by paying in index storage.

The frame to carry away: each architecture trades along precompute-vs-accuracy by choosing the granularity at which it commits to a representation before seeing the query. Bi-encoder commits one vector per doc (most precompute, least accuracy). Cross-encoder commits nothing (no precompute, most accuracy). ColBERT commits per-token vectors (precompute the representation, defer the interaction) — buying accuracy with storage rather than query-time compute.

Pushing accuracy upstream: distillation

If the cross-encoder is the most accurate model but too expensive to run on many docs, the natural question is: can we transfer its judgment into a cheaper model that can run earlier and on more docs? Yes — that's distillation (the teacher→student idea from lesson 26). Run the expensive cross-encoder offline as a teacher over a large set of (query, doc) pairs, producing soft relevance scores. Train a bi-encoder or ColBERT student to match those scores (typically a margin or KL/MSE loss on the teacher's score distribution, not just the binary labels). The student inherits much of the teacher's relevance ordering while keeping the cheap, indexable architecture.

Why this works and why it matters: the binary click/judgment labels are sparse and noisy, but the teacher's soft scores carry a rich, dense signal — relative ordering among negatives, degrees of relevance — that a bi-encoder could never learn from labels alone. Distillation is how modern dense retrievers (and ColBERTv2) got good: the accuracy of cross-attention is baked into the retrieval/rerank model at train time, so you pay the cross-encoder cost once, offline, instead of per-query forever. The senior framing: distillation moves accuracy upstream in the cascade, where it's cheap to apply, by paying for it once at training time instead of every query at serving time.

LLM rerankers — the newest, most expensive tier

Large language models can rerank, and they're increasingly used as either the top tier of the cascade or as offline judges/teachers. Three prompting styles, each with a different latency/cost profile:

• Pointwise (relevance prompting). Ask the LLM, per document, "Is this document relevant to this query? Rate 0–3" or "yes/no with a probability." Score each candidate independently, sort by the score. Simplest, parallelizable across docs, but N separate LLM calls — expensive, and the model never sees documents side by side so it can't calibrate relative judgments well.
• Listwise (RankGPT-style). Put many documents in one prompt and ask the LLM to output a permutation: "Rank these passages by relevance, output the order." One (or a few) calls instead of N, and the model sees documents together so it judges relatively — usually the most accurate LLM approach. Limits: context window caps how many docs fit, so long candidate lists need a sliding-window pass (rank a window, slide, merge); and the output is a permutation, not calibrated scores, which complicates blending with other signals.
• Pairwise. Ask "is A more relevant than B?" for pairs, aggregate into an order. Most accurate per-comparison but O(N²) calls in the worst case — usually only viable with sorting-network tricks to cut the comparison count.

Interactive · rerank budget explorer

This widget makes the rerank arithmetic concrete. Pick how many docs you rerank (N), the per-doc cross-encoder cost, and how much parallelism/batching you have. It reports the total added latency, whether it fits a chosen latency budget, and an approximate (saturating) NDCG-gain curve, then renders a verdict: worth it, over budget, or past the saturation point. The cost and NDCG models are toy approximations — they get the shape and order of magnitude right so the trade-off feels real, not the precise numbers for your stack.

The blend layer — relevance is not the last word

After the reranker produces a relevance-ordered list, one more stage runs: the blend (or "rerank-for-business") stage. Its job is everything relevance scoring deliberately ignores, and — critically — this is the last place in the pipeline where you can enforce these constraints, because nothing downstream sees the full candidate set anymore. Four concerns:

• Diversity & dedup. The top-10 by pure relevance can be 10 near-identical results (the same product from 10 sellers, 10 paraphrases of one article). The user wants coverage. The standard tool is MMR (Maximal Marginal Relevance): greedily build the result list, at each step picking the candidate that maximizes λ · relevance − (1 − λ) · max-similarity-to-already-selected. The λ knob trades relevance against novelty. Exact-duplicate removal (same canonical URL, same product ID) is a hard dedup that runs even before MMR. See lesson 20 for the full diversity/fairness treatment.
• Freshness boosts. For news, social, or trending queries, recency is part of relevance but the reranker (trained on older judgments) under-weights it. A freshness boost — e.g. multiply score by a time-decay factor, or reserve slots for recent docs — corrects this at blend time without retraining.
• Business rules. Sponsored slots, pinned results, editorial overrides, supply/inventory constraints, contractual placements. These are policy, not relevance, and they belong here — out of the model, in an auditable rule layer. See lesson 47 for business blending in e-commerce and marketplace search.
• Per-entity caps. "No more than 2 results from one domain/seller/creator in the top 10." A listwise constraint the per-item reranker structurally cannot see, because it scores documents independently.

Interview prompts you should be ready for