Reranking Math

Two stages, two objectives

Retrieval and reranking are separated because their cost structures are opposite. Stage one runs against the entire corpus — possibly hundreds of millions of chunks — so it must be sublinear and precomputable. Stage two runs against only the handful of candidates stage one returned, so it can afford to be expensive per item. Formally, if retrieval returns a candidate set C of size N (typically 50 to 200), the reranker computes a fresh score s(q, d) for every d ∈ C and re-sorts, then keeps the top k (say 3 to 10) to hand to the LLM.

That division of labor is what makes it tractable. Retrieval alone caps out on precision, because the very thing that makes it fast is what limits its accuracy; reranking buys that precision back on a small, already-narrowed set.

Dense retrieval: the bi-encoder first stage

The first stage is almost always a bi-encoder (dense retrieval). A single encoder maps the query and each document independently to vectors: u = E(q) and v = E(d), each in R^d. Relevance is then a cheap vector similarity, usually cosine or dot product: sim(q, d) = u · v / (‖u‖ ‖v‖).

The decisive property is that v = E(d) does not depend on the query, so every document vector is computed once, offline, and stored in an index. At query time you embed only q and run an approximate nearest-neighbor (ANN) search, sublinear in corpus size, which is why retrieval scales to hundreds of millions of chunks. The price is that query and document never see each other during encoding: their interaction is compressed into one dot product of two vectors built in mutual ignorance. Fine detail — a negation, a specific entity, a qualifying clause — often washes out, and that lost signal is precisely what reranking recovers.

The cross-encoder: joint encoding, full cross-attention

A cross-encoder throws out the independence assumption. Instead of encoding q and d separately, it concatenates them into one sequence and feeds the pair through the transformer together:

input  = [CLS] q_1 ... q_m [SEP] d_1 ... d_n [SEP]
H      = Transformer(input)          # H: [1 + m + n + 2, d_model]
h_cls  = H[0]                         # pooled pair representation
s(q,d) = w · h_cls + b               # scalar relevance score

Because self-attention runs over the whole concatenated sequence, every query token attends to every document token, and vice versa, at every layer. That is the ‘cross-attention’ the name refers to — not a separate encoder-decoder block, but query and document tokens sharing one attention matrix. The [CLS] vector absorbs that joint interaction and a tiny linear head projects it to a single number. Note what the output is not: not a similarity between two vectors, because there are no two vectors — there is one fused representation of the pair and one learned scalar read off it.

Why the cross-encoder is more accurate

The accuracy gap traces to where the interaction happens. In a bi-encoder, all cross-talk between query and document is deferred to a single dot product after both have been squeezed into fixed vectors, so any nuance that did not survive that bottleneck is gone. In a cross-encoder the interaction happens inside the network, token by token, across every layer: the model can represent ‘the query asks about X but not Y, and this document is about Y,’ a soft, term-level matching a single dot product cannot express.

Concretely, cross-encoders routinely lift ranking quality by several points of nDCG over strong dense retrievers on the same candidate set, and they handle hard negatives (documents topically close but actually wrong) far better, because those are exactly the cases where fine token interaction matters. The catch is inseparable from the benefit: the score depends jointly on q and d, so nothing can be precomputed — every new query forces a fresh forward pass for every candidate.

The cost: O(candidates) forward passes

This is the central budget line. A bi-encoder does one encoder pass per query (embed q) plus a cheap ANN lookup; document passes were amortized offline. A cross-encoder does N full transformer forward passes per query — one per candidate in C — and none can be cached, because each pass sees a different (q, d) pair.

That O(N) factor is the whole reason reranking lives only at the top of the funnel. With N = 100 candidates and each cross-encoder pass over a ~512-token pair taking a few milliseconds on GPU (much more on CPU), the reranker adds tens to a couple hundred milliseconds; the same model over a million documents would take minutes per query. So the arithmetic dictates the architecture: retrieve wide and cheap to cut the corpus to N, then rerank narrow and expensive over just those N. The reranker never sees the corpus, only the shortlist.

Training: pairwise and listwise ranking losses

Rerankers are trained to order, not to predict absolute scores, so the loss operates on relative preferences. Given a query with a relevant document d+ and an irrelevant one d-, we want s(q, d+) > s(q, d-). A logistic (RankNet-style) pairwise loss reads:

L_pair = -log σ( s(q,d+) - s(q,d-) )
       where σ(x) = 1 / (1 + e^(-x))

This drives the score margin between positive and negative to be large and positive. In practice the quality of the negatives matters enormously: training against hard negatives (near-miss documents mined from the retriever) teaches the distinctions that count.

A listwise loss goes further and optimizes the whole ranked list at once. A common form scores the positive against a list of negatives with a softmax cross-entropy — a contrastive InfoNCE objective: L_list = -log[ exp(s+) / (exp(s+) + Σ_j exp(s_j-)) ]. Listwise objectives align more directly with list metrics like nDCG and usually rank better, at the cost of harder batch construction.

Measuring rank quality: MRR

Because the deliverable is an ordering, accuracy is the wrong yardstick — rank-aware metrics are right. The simplest is Mean Reciprocal Rank: for each query, find the rank of the first relevant result and take its reciprocal; average over all queries:

MRR = (1/|Q|) Σ_{q} 1 / rank_of_first_relevant(q)

First relevant document at position 1 contributes 1.0; at position 2, 0.5; at position 5, 0.2. MRR is ideal when there is essentially one right answer and you only care how close to the top it lands: question answering, a ‘find the doc’ lookup, or a RAG stage that forwards only the single best chunk. Its blind spot is that it ignores everything after the first hit — one relevant result at rank 1 scores identically whether or not four more follow. When multiple documents are relevant and their order matters, you want a graded metric: nDCG.

nDCG: graded relevance with position discounting

Normalized Discounted Cumulative Gain is the workhorse ranking metric because it handles two things MRR cannot: graded relevance (perfect, partial, or useless, not just yes/no) and the intuition that a great result buried at rank 8 is worth less than one at rank 1. It builds in three steps.

DCG@k  = Σ_{i=1..k}  rel_i / log2(i + 1)      # discount by position
IDCG@k = DCG@k of the ideal (best-possible) ordering
nDCG@k = DCG@k / IDCG@k                       # in [0, 1]

The gain rel_i is the relevance grade at rank i (an alternative form uses 2^rel_i - 1 to reward highly relevant hits more sharply). The discount log2(i + 1) grows with depth, so the same gain contributes less the further down it appears. Dividing by the ideal DCG — what a perfect ranking of the same documents would score — normalizes to [0, 1], where 1.0 means ‘could not be ordered any better,’ and makes scores comparable across queries with different numbers of relevant results.

A worked nDCG example

Suppose retrieval returns five candidates and the reranker orders them. On a 0–3 relevance scale, the graded labels in the reranker’s order come out as [3, 2, 0, 1, 2]. Compute the discounted gain at each rank:

rank i:   1      2      3      4      5
rel_i:    3      2      0      1      2
log2(i+1):1.000  1.585  2.000  2.322  2.585
term:     3.000  1.262  0.000  0.431  0.774

DCG@5  = 3.000 + 1.262 + 0 + 0.431 + 0.774 = 5.466

Now the ideal ordering: sort the same grades best-first to get [3, 2, 2, 1, 0] and score that.

IDCG@5 = 3/1.000 + 2/1.585 + 2/2.000 + 1/2.322 + 0
       = 3.000 + 1.262 + 1.000 + 0.431 + 0 = 5.693

nDCG@5 = 5.466 / 5.693 = 0.960

An nDCG of 0.96 says the ranking is close to ideal but not perfect: the flaw is the relevant rel = 2 document stranded at rank 5 while a rel = 0 document sits at rank 3. Swapping those would push nDCG toward 1.0. That single number is what you track to know whether a reranker is actually helping.

The latency-quality trade of k

The one knob that ties the whole pipeline together is the candidate count N (often written k for the reranker’s input depth). Reranker latency is essentially linear in it: reranking 200 candidates costs twice reranking 100. Quality, meanwhile, is bounded by recall — the reranker can only promote a great document if retrieval put it in the shortlist. Raise N and you give the reranker more chances to find buried gems (higher recall ceiling), but you pay linearly more compute and add tail latency; lower it and you are fast but risk having already dropped the best answer before reranking even starts.

On CPU or small-model deployments the trade bites hardest, since each cross-encoder pass is far slower than on GPU. Practical tactics: keep N modest (50–100), truncate pair length, distill the cross-encoder into a smaller student, or batch candidates. The healthy mental model is a funnel: retrieval sets the recall ceiling by choosing N, and the reranker spends a fixed per-candidate budget converting recall into precision. Tune N to the latency you can afford, then make every forward pass count.