Cranfield query 185 asks for experimental studies on panel flutter, and nine abstracts are relevant to it. BM25 places six of them in its top ten and all nine in its top 20. Hand BM25's top ten to the cross-encoder of the previous article and its re-ordered list scores 0.815 in nDCG@10, above BM25's 0.807. Hand it the top 20, which contains every relevant abstract, and it scores 0.759. More candidates gave the re-ranker more to find and more to get wrong, and on this query it got more wrong. How deep should the first stage's list be, what limits does a first stage set, and what does each further stage cost?
A multi-stage ranking system answers a query in a pipeline. A first stage retrieves a list of candidates from the whole collection with a cheap function over an index, and each later stage re-orders the list it receives, usually passing on a shorter one, until the last stage's order is shown. The idea is old and the course has met it twice: How web search answers a query follows one query through a funnel of stages with illustrative counts, and Search at scale places the cascade among the techniques that make a large engine affordable. This article treats the pipeline as an object with properties that can be proved and costs that can be measured.
Here is the route. First we fix the vocabulary, following the formulation of Nogueira, Yang, Cho and Lin (2019), and prove the two ceilings a first stage imposes: one on recall and one on any graded measure such as nDCG. Then we measure, on Cranfield, how close the cross-encoder of the previous article comes to those ceilings at each depth, what the depth costs, and whether a middle stage or the first stage's own score helps. Then we do the same on this site, inside the part of it the judgments cover. Finally we describe the stages that come after a pointwise re-ranker in published systems: pairwise, sequence-to-sequence and listwise, the last with a proof about the sliding window it uses. The article assumes Cross-Encoder Re-ranking and the measures of ranked retrieval evaluation and nDCG. The numbers are computed by tools/experiments/neural-ranking/multi-stage-ranking.py.
Stages, candidates and depth
Nogueira and colleagues give the standard formulation. A pipeline has stages $H_0, \dots, H_N$. Stage $H_0$ retrieves $k_0$ candidates from the collection's inverted index; each later stage $H_i$ receives the ranked list of $k_{i-1}$ candidates from the stage before and passes on a ranked list of $k_i \le k_{i-1}$ candidates, and the list from $H_N$ is shown. In their words, each stage "is unconstrained in its implementation other than the input–output specifications": a stage may ignore the scores it receives, treating its input as a set, or combine them with its own. In this unit the depth of the list a re-ranker receives is written $n$, and the length of the list that is evaluated is $k$, as in nDCG@$k$.
The first stage's job is different from the others'. They put it plainly: "it is critical in $H_0$ to optimize for recall to provide subsequent stages a diverse set of documents to work with. On the other hand, precision is less of a concern because non-relevant documents can be discarded by later stages." The two ceilings below make that precise.
Lin, Nogueira and Yates (2021, §3.2) date the retrieve-and-re-rank design "back to at least the 1960s" and call it the simplest instance of a multi-stage architecture. Wang, Lin and Metzler (2011) treated the whole cascade as something to learn, with a boosting algorithm that chooses a sequence of "increasingly complex ranking functions that progressively prunes and refines the set of candidate documents" so as to trade effectiveness against efficiency directly (their abstract). Asadi and Lin (2013) studied the first stage's part in such a trade: with the features and learned model fixed, they found no significant difference in end-to-end nDCG between conjunctive and disjunctive candidate generation with WAND, the conjunctive form being substantially faster, while plain postings intersection was fast and substantially worse (their abstract). Dynamic pruning with MaxScore and WAND covers that algorithm.
The ceilings a first stage sets
A re-ranker can only re-order what it is given. Two consequences can be stated exactly.
Fix a query, its set $\mathrm{Rel}$ of relevant documents, and the candidate set $C_n$: the first $n$ documents of the first stage. A re-ranking of $C_n$ is any list whose first $n$ positions hold the documents of $C_n$ in some order; documents below rank $n$ keep the first stage's order (as in every run of this article) or are dropped, and either way they cannot enter the top $n$.
Proposition 1 (the recall ceiling). For every re-ranking $L$ of $C_n$ and every $k \le n$,
$$\mathrm{recall@}k(L) \;\le\; \min\Big( \mathrm{recall@}n(\text{first stage}),\; \frac{k}{\lvert \mathrm{Rel} \rvert} \Big).$$
Proof. The top $k$ of $L$ is a subset of $C_n$, so it contains at most $\lvert \mathrm{Rel} \cap C_n \rvert$ relevant documents, and recall@$n$ of the first stage is $\lvert \mathrm{Rel} \cap C_n \rvert / \lvert \mathrm{Rel} \rvert$. It also contains at most $k$ documents. $\square$
In a cascade the same argument applies at every stage, since each stage's output is a subset of its input: the recall at $k$ of the final list is at most the smallest of the recalls that the earlier stages' cut lists have. A relevant document dropped at any stage is lost to all later ones.
Recall counts relevant documents and ignores their grades and positions. For a graded measure the question is what the best possible re-ordering of $C_n$ scores.
Proposition 2 (the oracle ceiling). Let $k \le n$, let documents carry gains $g(d) \ge 0$, and let positions carry discounts $w_1 \ge w_2 \ge \dots \ge w_k > 0 = w_{k+1} = w_{k+2} = \cdots$, as in DCG@$k$ with $w_r = 1/\log_2(1 + r)$ for $r \le k$. Among all orderings of $C_n$, the one that sorts the documents by decreasing gain has the largest DCG@$k$. Hence every re-ranking of $C_n$ has
$$\mathrm{nDCG@}k \;\le\; \frac{\mathrm{DCG@}k(C_n \text{ sorted by gain})}{\mathrm{IDCG@}k},$$
where the ideal $\mathrm{IDCG@}k$ is computed, as always, from all the query's judged documents.
Here is the idea: if a less useful document stands above a more useful one, swapping them moves the larger gain to the larger discount, which cannot lower the sum.
Proof. Take any ordering of $C_n$ that is not sorted by decreasing gain. Then some two neighbors are out of order: positions $i$ and $i + 1$ with $g(d_i) < g(d_{i+1})$. Swapping them changes DCG by
$$\big(g(d_{i+1}) w_i + g(d_i) w_{i+1}\big) - \big(g(d_i) w_i + g(d_{i+1}) w_{i+1}\big) = \big(g(d_{i+1}) - g(d_i)\big)\big(w_i - w_{i+1}\big) \ge 0,$$
since both factors are at least 0: the gains are out of order, and the discounts do not increase with position (a position beyond $k$ has discount 0). The swap reduces by exactly one the number of pairs of positions whose gains are out of order, and leaves every other pair's order as it was. Repeating it, as bubble sort does, therefore reaches a sorted ordering after finitely many swaps, and no swap lowers DCG. Orderings sorted by gain differ only among documents of equal gain and have the same DCG. So the sorted order's DCG is at least that of the ordering we started from. The denominator of nDCG does not depend on the ordering, so the same holds for nDCG. $\square$
The script checks Proposition 2 on every query: no run of this article exceeds its oracle at the same depth.
Proposition 3 (both ceilings rise with depth; what is reached need not). If $n < n'$, then $C_n \subseteq C_{n'}$, so $\lvert \mathrm{Rel} \cap C_n \rvert \le \lvert \mathrm{Rel} \cap C_{n'} \rvert$ and the recall ceiling cannot fall. For the oracle: the $r$-th largest gain in a set is at least the $r$-th largest gain in any subset of it, so the sorted gains of $C_{n'}$ are, position by position, at least those of $C_n$, and the oracle DCG cannot fall either. Nothing similar holds for a re-ranker that makes mistakes. Deepening the list adds candidates the re-ranker may wrongly place above relevant ones, and on a single query its nDCG can fall; the experiment counts how often it does. $\square$
The two ceilings bound different things. The recall ceiling says which relevant documents can appear at all. The oracle says how good the top $k$ could be if the re-ranker were perfect. The distance between the oracle and what a real re-ranker reaches is the re-ranker's own loss, and the distance between the oracle and 1 is the first stage's.
Depth and its cost, measured on Cranfield
The first stage is the BM25 of the course ($k_1 = 1.2$, $b = 0.75$), or the unit 1 bi-encoder searching all 1,400 abstracts; the re-ranker is the pinned cross-encoder, cross-encoder/ms-marco-MiniLM-L6-v2 at revision 233902d25c440f23af6f7d6e94d2946bac0bee0a. The measures are nDCG@10 with Cranfield's gain $5 - \text{grade}$ and recall, over all 225 queries. Each row re-ranks the first $n$ candidates and leaves the rest in the first stage's order. Cost is counted in cross-encoder passes, one per candidate, which is $n$ per query.
BM25 first, then the cross-encoder:
| Depth $n$ | Passes per query | Recall@$n$ (ceiling) | Oracle nDCG@10 (ceiling) | Cross-encoder nDCG@10 |
|---|---|---|---|---|
| 10 | 10 | 0.397 | 0.522 | 0.378 |
| 20 | 20 | 0.503 | 0.630 | 0.384 |
| 30 | 30 | 0.564 | 0.688 | 0.384 |
| 50 | 50 | 0.642 | 0.756 | 0.383 |
| 100 | 100 | 0.737 | 0.832 | 0.384 |
BM25 alone has nDCG@10 0.368. The bi-encoder first, then the cross-encoder:
| Depth $n$ | Recall@$n$ (ceiling) | Oracle nDCG@10 (ceiling) | Cross-encoder nDCG@10 |
|---|---|---|---|
| 10 | 0.416 | 0.541 | 0.390 |
| 20 | 0.530 | 0.648 | 0.399 |
| 30 | 0.604 | 0.716 | 0.396 |
| 50 | 0.686 | 0.788 | 0.396 |
| 100 | 0.772 | 0.847 | 0.391 |
The bi-encoder alone has 0.382.
Four things can be read from the two tables.
- The ceilings rise steeply and what is reached does not. From depth 10 to depth 100 behind BM25, the oracle rises from 0.522 to 0.832, and the cross-encoder's nDCG@10 moves between 0.378 and 0.384. On this collection the first stage is not what limits the pipeline beyond depth 20: the re-ranker is. At depth 100 a perfect re-ranker of BM25's candidates would score 0.832, more than twice what this one reaches.
- Depth beyond 20 bought nothing measurable. Behind BM25, the difference between depth 50 and depth 20 is $-0.001$ ($t = -0.17$, $p = 0.87$), and between depth 100 and depth 50 it is $+0.001$ ($p = 0.77$). Even depth 50 against depth 10 is $+0.005$ ($p = 0.43$). The cost, meanwhile, is proportional to $n$: depth 100 takes five times the passes of depth 20.
- Deeper lists hurt single queries, as Proposition 3 allows. Going from depth 10 to depth 20 behind BM25, the cross-encoder's nDCG@10 fell on 85 queries and rose on 54; from 50 to 100 it fell on 20 and rose on 7. The candidates added at depth are mostly non-relevant, and each is a chance for the re-ranker to put a wrong abstract into the top ten. Query 185 is one of them: at depth 10 its re-ranked nDCG@10 is 0.815, and from depth 20 on it is 0.759, although its oracle reaches 1 at depth 20, where all nine relevant abstracts are among the candidates.
- A better first stage helped at every depth, detectably from depth 20 on. At equal depth, the bi-encoder's candidates have higher recall than BM25's, and the cross-encoder re-ranked them to a higher nDCG@10 at every depth, by 0.007 to 0.015. A paired test on the 225 queries ($t$ distribution) separates the difference from chance at every depth from 20 to 100 ($p$ between 0.009 and 0.037) but not at depth 10 ($p = 0.24$), where the gain is as large; that is each test taken alone, and corrected for testing five depths (Holm), only depth 50 stays below 0.05. Seven queries have no relevant abstract in BM25's top 100, and no re-ranker can help them.
Lin, Nogueira and Yates (2021, §3.2.2) report the same experiment for monoBERT-large on MS MARCO's development queries with a different outcome: effectiveness rises with depth with "clearly diminishing returns", from an MRR@10 of 0.372 at 1,000 candidates to 0.377 at 10,000, with no change at 50,000. They read this as evidence that BERT "is not 'confused'" by poor candidates and advise selecting "the largest $k$ practical given their available hardware budget". A re-ranker trained on the collection's own kind of data is in a different position from this one, which the depth table shows being confused by the additional candidates on single queries and gaining nothing on average. The advice therefore depends on the re-ranker, and on Cranfield it does not hold for this model.
Three stages. The bi-encoder's cosines cost one dot product per candidate once the vectors are stored, so it can sit between BM25 and the cross-encoder at almost no cost. Take BM25's top 1,000, re-order them by cosine, and pass the top $n$ to the cross-encoder. At $n = 20$ this scores 0.400 against 0.384 for passing BM25's top 20 directly, a difference of 0.016 ($t = 2.31$, $p = 0.022$; randomization $p = 0.020$), for the same 20 cross-encoder passes per query. The middle stage raised the recall of the 20 candidates from 0.503 to 0.532. At $n = 50$ the three-stage pipeline scores 0.395 against 0.383 ($p = 0.011$), with the candidates' recall raised from 0.642 to 0.681. On this collection a cheap stage that raises the candidates' recall was worth more than raising the expensive stage's depth from 20 to 100, which gained nothing measurable.
Keeping the first stage's score. A re-ranker may combine its score with the score it received. Lin, Nogueira and Yates (2021, §3.2.2, Figure 10) interpolate monoBERT's probability with BM25's score scaled to $[0, 1]$ over each list, as $\alpha \hat{s}_{\mathrm{BM25}} + (1 - \alpha) s_{\mathrm{BERT}}$, and find on MS MARCO that MRR@10 "monotonically decreases as we increase the weight placed on BM25 scores". The same interpolation of $\sigma(s)$ with BM25's min-max scaled score, over BM25's top 50 on Cranfield, gives:
| $\alpha$ | 0 | 0.1 | 0.2 | 0.3 | 0.5 | 0.7 | 0.9 | 1 |
|---|---|---|---|---|---|---|---|---|
| nDCG@10 | 0.383 | 0.392 | 0.392 | 0.390 | 0.388 | 0.386 | 0.374 | 0.368 |
The best weight, 0.2, is 0.009 above the cross-encoder alone ($t = 1.64$, $p = 0.10$). Chosen on the 112 development queries of the unit's split and measured on the other 113, the weight is again 0.2 and the gain 0.008 ($p = 0.26$). So here the opposite of the MS MARCO finding holds in direction, a little of BM25's score helps, but the data cannot show that it is more than chance. Hybrid Retrieval studies interpolation between two first stages in detail.
This site: depth and passages per page
On this site the first stage is BM25F over whole pages, and the cross-encoder scores passages, so a pipeline has two depths: how many pages to re-rank, and how many passages of each page to read. The experiment of Cross-Encoder Re-ranking read every passage of BM25F's top 20 pages. Here both depths are varied. Passages are chosen within a page by the unit 1 bi-encoder, nearest to the query first, which adds a cheap stage between the two; a page is scored by the best cross-encoder score among the passages read.
The site's judgments limit what can be compared. The pool behind them holds one ranker's results: on 13 November 2026, BM25F's top 20 pages for each query, 1,200 pairs of which 1,199 were judged, by a model judge (Claude Sonnet 5.5) whose agreement with the owner on 150 calibration pairs was a quadratic-weighted kappa of 0.85, with the owner's and a second model's grades averaged in on those 150. The judgments are used as they stood at commit c057efe (the pool was later re-drawn and extended to other rankers, and all its pairs are now judged; the numbers here use the judgments of that commit, and Hybrid Retrieval reports the judged comparison across rankers). Cross-Encoder Re-ranking describes them in full. Of the 1,200 query-page pairs re-ranked at depth 20, 1,151 have a judgment at that commit and 49 do not, and those count as not relevant: 48 entered BM25F's top 20 after the pooling, as pages changed, and one was in the pool but never judged. For the same reason the oracle ceiling of Proposition 2 is nearly trivial at depth 20: the pages known to be relevant are, by the way the judgments were made, nearly all in BM25F's top 20, so a perfect re-ordering of that list scores 0.994. At depth 10 it scores 0.862.
nDCG@10 over the 60 topical queries, with the number of cross-encoder passes for all 60 queries:
| Pages re-ranked | Passages read per page | nDCG@10 | Passes |
|---|---|---|---|
| 10 | 1 | 0.729 | 600 |
| 10 | 3 | 0.752 | 1,800 |
| 10 | all | 0.755 | 11,835 |
| 20 | 1 | 0.735 | 1,200 |
| 20 | 2 | 0.772 | 2,400 |
| 20 | 3 | 0.778 | 3,600 |
| 20 | 5 | 0.778 | 5,994 |
| 20 | all | 0.783 | 23,851 |
BM25F alone scores 0.753.
- Here depth paid. Re-ranking 20 pages beats re-ranking 10 by 0.027 when every passage is read ($t = 2.09$, $p = 0.041$; ahead on 39 queries, behind on 18). At depth 10 the re-ranked list scores 0.755, level with BM25F's 0.753, so nearly all of the re-ranker's gain came from pages that BM25F placed 11th to 20th. On Cranfield, depth beyond 20 bought nothing measurable; on the site, depth 20 is where the gain is. The site's relevant pages are, by the way the judgments were made, nearly all inside BM25F's top 20, so the recall ceiling rises from depth 10 to 20 and then stops being measurable.
- Three passages per page were nearly enough. Reading the three passages nearest the query by the bi-encoder, 15 percent of the passes, scores 0.778 against 0.783 for reading everything, a difference of 0.005 ($p = 0.49$). Reading one passage costs 0.048 ($t = 3.29$, $p = 0.002$). The bi-encoder, which lost clearly to BM25F as a retriever of pages on the site's known-item queries (Dense Passage Retrieval), served here as an inexpensive filter of passages within a page.
- Read with the pool's limit in mind. All of these numbers concern re-orderings of BM25F's own top 20. None says whether a different first stage would serve the site better, which would need its own top 20 judged.
Stages after a pointwise re-ranker
The cross-encoder of the previous article is pointwise: it scores each candidate alone. Three later designs change what a stage looks at. They are described here with their published results; none was run.
Pairwise: duoBERT
Nogueira, Yang, Cho and Lin (2019) added a stage after monoBERT, their name for the pointwise BERT re-ranker of Nogueira and Cho (2019). duoBERT reads the query and two candidates, $d_i$ and $d_j$, as one input, "[CLS] query [SEP] $d_i$ [SEP] $d_j$ [SEP]" with a separate segment embedding for each of the three texts and truncation to 62, 223 and 223 tokens, and estimates the probability $p_{i,j}$ that $d_i$ is more relevant than $d_j$. It is trained with a cross-entropy loss over pairs of one relevant and one non-relevant candidate. At inference it scores all ordered pairs of the top $k_1$ candidates from monoBERT, $k_1(k_1 - 1)$ inferences, and aggregates each candidate's probabilities into one score. Of the five aggregations they tried, two did best: SUM, $s_i = \sum_{j \ne i} p_{i,j}$, and BINARY, which counts the $j$ with $p_{i,j} > 0.5$ and is "inspired by the Condorcet method", the majority vote that rank fusion describes. BINARY was slightly ahead on MS MARCO; on TREC CAR the two were very close, with SUM slightly better at the smaller depths $k_1$ (their Figure 3) and both at 36.9 at $k_1 = 50$ (their Table 2).
Their measurements show both the gain and its price. On MS MARCO's development queries, re-ranking 1,000 BM25 candidates with monoBERT gave MRR@10 of 37.2, and adding duoBERT with SUM over the top 50 gave 38.2, with BINARY 38.3 (their Table 1). On TREC CAR the stage added 2.1 points of MAP, from 34.8 to 36.9 (their Table 2). The 50 candidates cost $50 \times 49 = 2{,}450$ inferences on top of monoBERT's 1,000, more than tripling the work. They found that inferences of the two models take about the same time, so inferences per query serve as a unit of cost, and they called $k_1 = 20$ a good operating point, close to the best score they reached, for a latency about 40 percent above monoBERT's alone. In inferences that is $20 \times 19 = 380$ more than 1,000, an increase of 38 percent. They also tried scoring a random sample of each candidate's pairs among more candidates, and found that it "has a lower effectiveness than BINARY and SUM for any fixed number of inferences per query".
Sequence-to-sequence: monoT5
Nogueira, Jiang, Pradeep and Lin (2020) used an encoder-decoder model, T5, as the pointwise stage. The input is the text "Query: $q$ Document: $d$ Relevant:", and the model is fine-tuned to produce the word "true" or "false". At inference "we apply a softmax only on the logits of the 'true' and 'false' tokens", and the probability of "true" is the score. Lin, Nogueira and Yates (2021, §3.5.3) call the model monoT5. On the MS MARCO passage task, re-ranking BM25's candidates, their Table 1 gives MRR@10 on the development queries of 0.372 for BERT-large (340 million parameters), 0.381 for T5-base (220 million), 0.393 for T5-large (770 million) and 0.398 for T5-3B. They also report that when few training examples are available, the T5 model learns far more effectively than BERT. On news collections with full-length documents (the TREC 2004 Robust track and two others), the model trained only on MS MARCO was applied to each document by scoring passages of ten sentences with a stride of five and keeping the highest probability, which they identify as the MaxP technique of Dai and Callan (2019).
Listwise re-ranking by language models (as of November 2026)
A large language model can be asked to re-order a list directly. This part of the field is recent and changing; the three methods below are named, published ones, and the statements about them are those of their papers as of November 2026.
Sun and colleagues (2023), in the paper whose method was released as RankGPT (the name of its code), gave a chat model the query and a numbered list of passages and instructed it to output the identifiers in order of relevance, "in a format such as [2] > [3] > [1]", so that the model "ranks passages directly without producing an intermediate relevance score". A model reads only so much text at once, so they re-ranked BM25's top 100 with a sliding window: rank the last $w$ passages, move the window up by $s$ positions, rank again, and so on to the top of the list, with $w = 20$ and $s = 10$. Their Table 1 reports nDCG@10 of 75.59 for GPT-4 on the TREC 2019 Deep Learning passages against 71.83 for monoT5 with three billion parameters and 50.58 for BM25, and an average over eight BEIR datasets of 53.68 against 51.36 and 43.42. To limit cost on BEIR, GPT-4 re-ranked only the top 30 of a list already re-ranked by GPT-3.5: a cascade of language models. The same paper distilled the model's permutations into a small cross-encoder. Pradeep, Sharifymoghaddam and Lin then trained open models for the same task. RankVicuna, with 7 billion parameters, reached effectiveness "comparable to zero-shot reranking with GPT3.5" and "slightly behind reranking with GPT4" on the TREC 2019 and 2020 Deep Learning tracks (Pradeep et al., 2023a, abstract), and RankZephyr was reported to close the gap with GPT-4 and "in some cases" surpass it (Pradeep et al., 2023b, abstract).
The paper's reason for the choice $s = w/2$ is cost: in an appendix of its arXiv version (Appendix G) it explains that with this step most of the text is read by the model only twice. The sliding window also has a property that can be proved, and it gives a second reason.
Proposition 4 (what one pass guarantees). Suppose the window ranker is perfect: it sorts the passages in each window by their true order. Then after one back-to-front pass with window $w$ and step $s < w$, over any initial list of at least $t = w - s$ passages, the first $t$ positions hold the true top $t$ passages, in their true order.
Here is the idea: a passage of the true top $t$ always lands in the top $t$ places of any window that contains it, and the next window, moved up by $s$, still covers those $t$ places, so it is carried to the top.
Proof. Number positions from 0. Let $T$ be the set of the true top $t$ passages. A window covers positions $a$ to $a + w - 1$; the first starts at $a = \max(M - w, 0)$ for a list of $M$ passages, and each next one starts at $a' = \max(a - s, 0)$, the last at 0. We show by induction over the windows that after the window starting at $a$ is sorted, every passage of $T$ that lies at a position $\ge a$ lies in positions $a$ to $a + t - 1$.
The first window covers every position from $a$ to the end of the list. The passages of $T$ in it rank above all others, and there are at most $t$ of them, so after sorting they occupy its first places, positions $a$ to at most $a + t - 1$.
Now suppose the claim holds after the window at $a$, and let the next window start at $a'$. If $a' = a - s$, it ends at $a' + w - 1 = a + t - 1$. If $a' = 0$, then $a \le s$ and it ends at $w - 1 \ge a + t - 1$. Either way it covers every position from $a'$ to $a + t - 1$, so by the claim for $a$ it contains every passage of $T$ that lies at a position $\ge a'$. Sorting puts those passages in its first places, positions $a'$ to at most $a' + t - 1$. That is the claim for $a'$.
The last window starts at 0, so after it every passage of $T$ lies in positions 0 to $t - 1$, and since there are $t$ of them and the window was sorted, they are there in their true order. $\square$
With RankGPT's $w = 20$ and $s = 10$, one pass therefore delivers the true top 10, exactly the depth that nDCG@10 measures. The windows overlap so that each position is covered at most twice, but passages move: the pass makes 180 passage readings for 100 passages, 1.8 per passage on average, and a passage carried upward is read once in every window it passes through. Nothing is guaranteed below position $t$: the script finds, among random orderings of 12 passages with $w = 4$ and $s = 2$, cases where the passage that should be third is not third after the pass. The proposition is about the window arithmetic only; a real model is not a perfect window ranker, and its errors inside a window are not covered by it. A pass over $M = 100$ passages with $w = 20$ and $s = 10$ uses windows starting at positions 80, 70, …, 0, which is $\lceil (M - w)/s \rceil + 1 = 9$ windows and 180 passage readings.
What is proved here, what is cited, and what the experiments show
Proved on the page. The recall ceiling of a re-ranker and of a cascade (Proposition 1); that sorting by gain maximizes DCG@$k$ over the orderings of a candidate set, so the oracle bounds every re-ranker (Proposition 2); that both ceilings are nondecreasing in depth (Proposition 3); that one back-to-front pass of a sliding window with a perfect window ranker returns the true top $w - s$ in order (Proposition 4); the inference counts of a pairwise stage and of a sliding window.
Cited. The formulation of the pipeline and everything about duoBERT, with its results (Nogueira, Yang, Cho and Lin, 2019); monoT5 and its results (Nogueira, Jiang, Pradeep and Lin, 2020); the history and the depth experiments on MS MARCO reported in Lin, Nogueira and Yates (2021); learned cascades (Wang, Lin and Metzler, 2011) and candidate generation (Asadi and Lin, 2013), from their abstracts; RankGPT, RankVicuna and RankZephyr and their results (Sun et al., 2023; Pradeep et al., 2023a, 2023b).
Shown by the experiments. On Cranfield, with BM25 or the unit 1 bi-encoder as first stage and the pinned cross-encoder as re-ranker: the recall and oracle ceilings rose steeply with depth, from 0.522 to 0.832 in oracle nDCG@10 between depths 10 and 100 behind BM25, while the re-ranker's nDCG@10 stayed between 0.378 and 0.384; depth beyond 20 bought nothing measurable and lowered single queries' scores more often than it raised them; a bi-encoder stage between BM25 and the cross-encoder raised nDCG@10 by 0.016 at equal cross-encoder cost; and keeping a fifth of BM25's score in the final score gave a small gain that the data cannot separate from chance. On this site, inside the judged pool: re-ranking BM25F's top 20 pages beat re-ranking its top 10, and reading three passages per page, chosen by the bi-encoder, came within 0.005 of reading all of them. These are observations with one small cross-encoder and two collections.
Worked problems
These problems are posed on Cranfield query 185, on the depth tables above and on small exact cases; the unit has no course assignments. The script recomputes every number.
Problem 1 (the recall ceiling for query 185). BM25's top ten for query 185 contains six of its nine relevant abstracts. What is the largest recall@10, and the largest recall@5, that any re-ranking of that list can have? What changes at depth 20?
Solution. By Proposition 1, recall@$k$ of any re-ranking of $C_{10}$ is at most $\min(\text{recall@}10, k/9)$. Recall@10 of BM25 is $6/9 = 0.667$, so recall@10 after re-ranking is at most 0.667, and BM25 already reaches it. Recall@5 is at most $\min(0.667, 5/9) = 0.556$, reached by any ordering that puts five of the six relevant abstracts first. At depth 20 all nine relevant abstracts are candidates, so the recall ceiling at 10 rises to $\min(1, 10/9) = 1$, and the ceiling at 5 stays at $5/9$, which is now set by the cutoff and not by the first stage.
Problem 2 (the oracle for query 185 at depth 10). The gains ($5 - \text{grade}$, 0 if not relevant) of BM25's top ten for query 185 are, in order, $2, 3, 3, 0, 3, 2, 0, 0, 3, 0$, and the query's nine relevant abstracts have gains $3, 3, 3, 3, 2, 2, 1, 1, 1$. Compute the oracle nDCG@10 of this candidate list and compare it with BM25's 0.807 and the cross-encoder's 0.815.
Solution. By Proposition 2 the best ordering sorts the candidates by gain: $3, 3, 3, 3, 2, 2, 0, 0, 0, 0$. Its DCG@10 is
$$\frac{3}{\log_2 2} + \frac{3}{\log_2 3} + \frac{3}{\log_2 4} + \frac{3}{\log_2 5} + \frac{2}{\log_2 6} + \frac{2}{\log_2 7} = 3 + 1.893 + 1.5 + 1.292 + 0.774 + 0.712 = 9.171 .$$
The ideal DCG@10 uses all nine relevant abstracts, sorted, with the tenth position empty: the first six terms as above plus $1/\log_2 8 + 1/\log_2 9 + 1/\log_2 10 = 0.333 + 0.315 + 0.301$, which is 10.121. The oracle is $9.171/10.121 = 0.906$. BM25 reaches 0.807 of it and the cross-encoder 0.815. The remaining distance to 0.906 is the re-ranker's; the distance from 0.906 to 1 is the first stage's, the three relevant abstracts of gain 1 that lie below rank 10.
Problem 3 (the cost of a pairwise stage). In the pipeline of Nogueira, Yang, Cho and Lin, monoBERT re-ranks $k_0 = 1{,}000$ candidates and duoBERT then compares all ordered pairs of the top $k_1$. Count the inferences per query for $k_1 = 10, 20, 30, 40, 50$, and the increase over monoBERT alone at $k_1 = 20$ and $k_1 = 50$.
Solution. monoBERT costs $k_0 = 1{,}000$ inferences and duoBERT $k_1(k_1 - 1)$: 90, 380, 870, 1,560 and 2,450. The totals are 1,090, 1,380, 1,870, 2,560 and 3,450. The paper's Figure 3 plots effectiveness against duoBERT's inferences alone, $k_1(k_1 - 1)$, from 0 (monoBERT alone) to 2,450; adding monoBERT's 1,000 gives the totals, and the largest, 3,450, is the most expensive point of its Figure 4. At $k_1 = 20$ the increase is $380/1{,}000 = 38$ percent, the paper's latency increase of about 40 percent for its suggested operating point; at $k_1 = 50$ it is 245 percent, more than tripling the work. The pairwise stage's cost grows with the square of its depth, so it is affordable only on a list that the pointwise stage has already cut short.
Problem 4 (the sliding window). Six passages, labelled $A$ to $F$ in their true order ($A$ best), stand in the order $D, E, A, B, C, F$. Run one back-to-front pass with window $w = 4$ and step $s = 2$ and a perfect window ranker, numbering positions from 1 (the proof numbers them from 0). Which positions are guaranteed to be right, and which are? Then count the windows and passage readings for 100 passages with $w = 20$ and $s = 10$, $s = 5$ and $s = 15$.
Solution. The first window covers positions 3 to 6, holding $A, B, C, F$, already in order. The next window starts two positions up and covers positions 1 to 4, holding $D, E, A, B$; sorted, they become $A, B, D, E$. The final order is $A, B, D, E, C, F$. Proposition 4 guarantees the first $w - s = 2$ positions, and they are right: $A, B$. Position 3 is wrong: $C$ is fifth, because the second window did not reach it. For 100 passages and $w = 20$ the windows start at $100 - 20 = 80$ and step up by $s$, so their number is $\lceil 80/s \rceil + 1$: with $s = 10$, 9 windows and 180 readings, top 10 guaranteed; with $s = 5$, 17 windows and 340 readings, top 15 guaranteed; with $s = 15$, 7 windows and 140 readings, top 5 guaranteed. A smaller step buys a deeper guarantee at the price of more readings.
Problem 5 (spending a fixed budget). On Cranfield, a budget allows 20 cross-encoder passes per query. Using the measurements of this article, which pipeline should be chosen, and what would raising the budget to 100 passes buy?
Solution. Three pipelines fit the budget: BM25's top 20 re-ranked (nDCG@10 0.384), the bi-encoder's top 20 re-ranked (0.399), and BM25's top 1,000 re-ordered by the bi-encoder with the top 20 re-ranked (0.400). The last two need stored passage vectors; the third keeps BM25's candidate set and costs nothing in cross-encoder passes beyond the 20. The three-stage pipeline beats BM25's top 20 by 0.016 ($p = 0.022$). Raising the budget to 100 passes behind BM25 gives 0.384, no measurable gain over 20, although the oracle rises from 0.630 to 0.832. With this re-ranker on this collection, the budget is better spent on a better candidate list than on a longer one.
What we have learned
A multi-stage pipeline is limited in two ways that can be stated exactly. Its first stage fixes which relevant documents can ever be shown, the recall ceiling, and how good the best re-ordering of its candidates could be, the oracle ceiling; both can only rise as the list gets deeper. Its re-ranker decides how much of that ceiling is reached, and a re-ranker that makes mistakes can do worse on a deeper list. On Cranfield the pinned cross-encoder reached about half of the oracle at depth 100 and gained nothing beyond depth 20, while a cheap bi-encoder stage in the middle helped; on this site the second ten pages were where re-ranking paid, and three passages per page were enough. Stages after a pointwise re-ranker compare pairs of candidates (duoBERT), generate relevance as a word (monoT5) or re-order whole lists with a language model, and each costs more per query than the stage before; one pass of a sliding window with step $s = w/2$ is exactly enough to guarantee the top $w/2$ when the window ranker is perfect.
The cross-encoder reads the query and passage together at a price of one pass per pair; the bi-encoder of unit 1 reads them apart at the price of one vector per passage. Between the two lies a design that keeps one vector for every token of the passage and lets each query token find its best match among them. That is Late Interaction and ColBERT.
References
- Asadi, N., and Lin, J. (2013). Effectiveness/efficiency tradeoffs for candidate generation in multi-stage retrieval architectures. In Proceedings of SIGIR 2013, 997–1000. record
- Dai, Z., and Callan, J. (2019). Deeper text understanding for IR with contextual neural language modeling. In Proceedings of SIGIR 2019, 985–988. arXiv:1905.09217. record · 3 pages
- Lin, J., Nogueira, R., and Yates, A. (2021). Pretrained Transformers for Text Ranking: BERT and Beyond. Morgan & Claypool. arXiv:2010.06467 (version 3). record · 5 pages
- Nogueira, R., and Cho, K. (2019). Passage re-ranking with BERT. arXiv:1901.04085. record · 7 pages
- Nogueira, R., Jiang, Z., Pradeep, R., and Lin, J. (2020). Document ranking with a pretrained sequence-to-sequence model. In Findings of the Association for Computational Linguistics: EMNLP 2020, 708–718. record
- Nogueira, R., Yang, W., Cho, K., and Lin, J. (2019). Multi-stage document ranking with BERT. arXiv:1910.14424. record · 3 pages
- Pradeep, R., Sharifymoghaddam, S., and Lin, J. (2023a). RankVicuna: Zero-shot listwise document reranking with open-source large language models. arXiv:2309.15088. record
- Pradeep, R., Sharifymoghaddam, S., and Lin, J. (2023b). RankZephyr: Effective and robust zero-shot listwise reranking is a breeze! arXiv:2312.02724. record
- Sun, W., Yan, L., Ma, X., Wang, S., Ren, P., Chen, Z., Yin, D., and Ren, Z. (2023). Is ChatGPT good at search? Investigating large language models as re-ranking agents. In Proceedings of EMNLP 2023, 14918–14937. arXiv:2304.09542. record
- Wang, L., Lin, J., and Metzler, D. (2011). A cascade ranking model for efficient ranked retrieval. In Proceedings of SIGIR 2011, 105–114. record · 3 pages