Cross-Encoders and the Reranking Cascade

Overview & motivation

Dense retrieval ended on a debt. Its whole architecture rested on separability — a dual encoder scores $s(q,d) = \langle E_Q(q), E_P(d)\rangle$, query and document meeting in a single inner product — and three times over the topic named the thing separability forbids. It promised that “the cross-encoder that this topic kept invoking as the rank-free, un-precomputable counterpoint becomes the reranker in a retrieve-then-rerank cascade,” and deferred how that extra power is spent to “a later topic.” The embedding-dimension lower bound sharpened the debt into an impossibility — the single-vector wall it proved is one “cross-encoders … pay a quadratic cost to fuse query and document and so are not factorizations at all” route around. And late interaction set the cross-encoder as the far pole of the expressivity axis: where ColBERT keeps matching cheap with a sum of token dot products, “a cross-encoder pays a full joint forward pass for the most expressive score of all.” This is that topic. We pay the debt, and we charge it.

A cross-encoder scores a fused pair, $s(q,d) = h([q;d])$, letting query and document attend to each other at every layer rather than meeting once at the end. The first result is the one that explains why this matters at all, and it is more subtle than “more layers, more power.” A learned bilinear scorer $q^\top W d$ — a dual encoder with a trained similarity metric bolted on — does not escape the rank ceiling, because $S = QWG^\top = (QW)G^\top$ is still a product through a $d$-dimensional bottleneck. The escape is not the interaction matrix. It is the nonlinearity. Only a genuinely nonlinear joint scorer has no rank to bound, and that is exactly what lifts the cross-encoder out of the sign-rank wall.

That expressivity is bought with a forward pass per pair, which forbids precomputation and rules the cross-encoder out as a first stage. So it becomes a reranker: a cheap dual encoder retrieves a candidate pool of $K$ documents, the cross-encoder rescores only those $K$. Two facts govern the cascade. The recall pinch says an oracle rerank of the top-$K$ makes recall@1 equal the pool’s recall@$K$ — it can lift the first stage, but never past what the first stage retrieved. And monotonicity: an oracle reranker only improves as $K$ grows, but a lossy one can dip below the first stage by being confidently wrong, and more over-fetch can make the dip worse.

A · the rank ceilingB · the reranking cascadeC · when reranking hurts

embedding dimension d = 1

rank-1 ceiling error (dual = bilinear)

0.745

cross-encoder error

0.000

cross-encoder matrix rank

6 (full)

ceiling reaches 0 only at

d = 6

The target is the signed-identity relevance pattern — full rank 6, with singular values 4, 2, 2, 2, 2, 2. A dual encoder can only realize a rank-≤d matrix, and a learned bilinear q^⊤Wd does not escape that: S = QWG^⊤ = (QW)G^⊤ is still a product through a d-dimensional bottleneck, so its best is the same truncated-SVD ceiling (the blue line). Only the nonlinear cross-encoder h([q;d]), which scores the fused pair rather than a factorization, reconstructs the target at every d — it has no rank to bound. This is the escape from the sign-rank wall the embedding-dimension topic proved; the cross-encoder is, as that topic put it, not a factorization at all.

The first panel is the rank ceiling: on a full-rank target the dual encoder and the learned bilinear share one descending error curve — both capped at rank $d$ — while the nonlinear cross-encoder sits flat near zero, with no embedding budget at all. The second is the cascade frontier: an oracle rerank tracing the pool’s recall@$K$ against the cost $c_\text{ret} + K c_\text{ce}$, with the brute corpus-scan cost a flat line far above. The third is when reranking hurts: a quality slider that fixes hard negatives at one end and breaks true top-1s at the other.

The cross-encoder and the cascade

Fix a query $q$ and a corpus $\mathcal{C} = \{d_1, \dots, d_n\}$. A dual encoder, as the previous topic established, scores by a separable inner product and so realizes only relevance matrices of bounded rank. We define its expressive opposite and the structure that makes it deployable.

The two stages are not interchangeable. The first stage must be precomputable to run over the whole corpus, so it must be a factorization; the reranker need only run over $K$ documents, so it can afford to fuse. We take $s_1$ to be the dual encoder of the previous topic and ask, in order: how much more can a fused scorer express, what does the cascade buy, and how can it fail.

Movement 1 — joint encoding breaks the rank ceiling, and the nonlinearity is why

The previous topic proved that a dual encoder’s score matrix $S = QG^\top$ has $\operatorname{rank}(S) \le d$, and that a target relevance matrix is realizable exactly if and only if its rank is at most $d$. The natural first guess at escaping this ceiling is to keep the two towers but let them interact through a learned matrix — a bilinear score $q^\top W d$, a trained Mahalanobis similarity. The first result is that this guess fails completely.

This is the pedagogical hinge of the topic. Adding a learned similarity metric to a pair of frozen encoders feels like buying expressivity; it buys none. Whatever escapes the rank ceiling, it is not the interaction term — it is leaving the bilinear family altogether. A fused, nonlinear scorer does exactly that.

The theorem is, by itself, almost trivial: a lookup table realizes any matrix. Its force is the contrast with Proposition 1 and the constructive demonstration the laboratory makes. We take the signed-identity target — full rank $n$, $+1$ on the diagonal and $-1$ off it, the cleanest full-rank pattern that topic studied — and reconstruct it three ways as $d$ grows. The rank-$d$ ceiling (the best dual encoder, which is also the best learned bilinear) has relative reconstruction error that descends from $0.745$ at $d=1$ only to $0$ at $d = n = 6$, plateauing strictly above zero for every $d < n$. A finite nonlinear cross-encoder — a random-ReLU-feature map on the fused pair with a closed-form ridge readout, our deterministic stand-in for $h$ — reconstructs the target to machine precision at every $d$, including $d=1$, and its realized score matrix has full rank $6$. The cross-encoder has no embedding budget to spend; it does not factorize, so there is nothing to bound. (That this finite net realizes the pattern is demonstrated: universal approximation guarantees a realizing network exists only asymptotically, and our scorer is a seeded surrogate, not a trained transformer — the load-bearing caveat below.)

The same expressivity shows on the finance geometry. Fit the cross-encoder on the corpus’s query–document pairs and it realizes the relevance exactly — recall@1 $= 1.0$ — separating the same-sector companies a rank-3 dual encoder ($0.781$ recall@1) confuses. The cross-encoder can resolve hard negatives a single embedding cannot. The catch is that it cannot do so cheaply.

Movement 2 — the retrieve-then-rerank cascade and the recall pinch

A cross-encoder must run a joint forward pass for every pair it scores, and it cannot precompute anything, so scoring the whole corpus costs $|\mathcal{C}|$ forward passes per query — exactly the cost the dual encoder was built to avoid. The cascade resolves the tension by spending that cost only on a small pool: retrieve $K$ candidates cheaply, rescore $K$ expensively.

The cost is exact arithmetic; the question is how large $K$ must be. That is where the cascade’s defining identity lives. Because the reranker only ever sees the pool, its ceiling is set entirely by what the first stage retrieved.

The pinch is the whole logic of over-fetch in one line. The reranker’s reach is the pool’s recall@$K$, so you fetch deep enough that recall@$K$ saturates, then rerank. On the finance toy the rank-3 first stage has recall@1 $= 0.781$ but recall@3 $= 1.0$ — it confuses companies at the very top but keeps the gold within the top three — so reranking a pool of $K = 3$ lifts recall@1 all the way to $1.0$. The laboratory’s second panel draws the oracle curve tracing the pool’s recall@$K$ exactly, with the cost climbing as $c_\text{ret} + K c_\text{ce}$ against the brute corpus-scan line orders of magnitude above: the knee where recall@$K$ saturates is where you stop. One corollary is worth stating, because it is the reason the first stage’s recall is the cascade’s true bottleneck.

Under the known-item qrel the recall pinch is an exact identity; with several relevant documents per query the oracle can surface only one at rank 1, and the identity weakens to the inequality of the corollary. We ship the topic on the known-item qrel, where the equality holds and recall@1 is the natural reranking accuracy.

Movement 3 — monotonicity, and when reranking hurts

The recall pinch is about a perfect reranker. Two facts separate the perfect case from the real one. The first is reassuring.

This is the same superset argument the multi-vector ANN topic used for an exact rerank over a pruned survivor set, and it holds for exactly the same reason — but, exactly as there, only for an exact reranker. A real cross-encoder is not exact, and the second fact is the warning.

The laboratory’s third panel makes this a slider. Model the reranker quality by a corruption level $\sigma$ added to the oracle’s scores; at $\sigma = 0$ it is the oracle and fixes all seven same-sector hard negatives the first stage missed, a net recall@1 lift of $+0.219$. As $\sigma$ grows the buckets shift — fixed falls, broke rises — and the net lift turns negative; a constructed worst-case promoter that always elevates a same-sector distractor breaks every recoverable query. The dip is not a bug in the model. It is the score-versus-ranking gap made operational: a high cross-encoder score on the wrong document is a wrong ranking, and no amount of over-fetch protects against it. This is why a production stack keeps an exact scorer as ground truth and why the monotonicity guarantee is the oracle’s alone.

Honest accounting

Where this sits

The cross-encoder closes the expressivity ladder the dense track climbed — single vector, multi-vector late interaction, fused joint scorer — and opens the reranking sub-track. Its cost is the lever the next topics pull. Knowledge distillation for retrieval uses the cross-encoder as a teacher: its margins supervise a cheap student dual encoder, so the expressive scorer’s judgments are compressed back into a precomputable first stage — the MarginMSE recipe, the practical answer to “the reranker is too slow to run everywhere.” Listwise LLM rerankers push the joint-scoring idea further, scoring a whole candidate list in one context rather than one pair at a time, trading the cross-encoder’s pairwise forward passes for a single sequence model that reasons over the pool. And hard-negative mining is the training-side counterpart of the hard negatives this topic’s reranker exists to resolve: the same same-sector confusions that the cross-encoder fixes at inference are the negatives a first stage should be trained against. Each is named here and developed in its own topic; the cross-encoder is the architecture they all take as given.