Multi-Stage Ranking Cascades

Re-ranking the top 1,000 BM25 results for one MS MARCO query with BERT-large took 32,900 milliseconds on a Tesla V100 and lifted development-set MRR@10 from 16.7 for the official BM25 run to 36.5. Anserini's BM25 answered in 62 milliseconds (Khattab & Zaharia, 2020, ColBERT, arXiv:2004.12832). Scoring every passage in the collection with the large model would multiply that half-minute by thousands. The best model is unaffordable over the whole corpus and the affordable model is not good enough. Production ranking systems almost all resolve this the same way: cheap functions over many candidates, expensive functions over few.

Anatomy of a cascade

Stage \(i\) receives \(k_{i-1}\) candidates from the stage before, scores each at per-candidate cost \(c_i\), and passes its top \(k_i\) onward. The query's compute is

and every stage sees only what earlier stages kept, so

The first stage over the full index is typically an inverted index scored by BM25, a learned sparse model, or approximate nearest-neighbour search over embeddings. Middle stages are often gradient-boosted trees such as LambdaMART over hundreds of features. The final stage is the expensive model: a cross-encoder, a pairwise or listwise neural ranker, or a large multi-task network in recommendation. The neighbouring concept Reranking and Cross-Encoders covers that last stage; this one is about the pipeline around it.

Recommendation uses the same shape. YouTube's system was explicitly split into candidate generation, which narrows millions of videos to hundreds, and a separate ranking network over those hundreds (Covington, Adams & Sargin, 2016, Deep Neural Networks for YouTube Recommendations, RecSys).

Budgeting a pipeline: a worked example

Nogueira, Yang, Cho and Lin built a three-stage text pipeline: BM25 retrieves \(k_0 = 1000\), monoBERT scores each query-passage pair independently, and duoBERT compares pairs of the top \(k_1\) (Nogueira et al., 2019, Multi-Stage Document Ranking with BERT, arXiv:1910.14424). Because the two BERT stages cost about the same per inference, latency can be counted in inferences.

monoBERT costs 1,000 inferences per query. duoBERT is pairwise, so it scores \(k_1(k_1 - 1)\) ordered pairs: 2,450 inferences at \(k_1 = 50\), more than doubling the total. At \(k_1 = 20\) it needs 380, and the authors found this reached close to the maximum achievable score for roughly a 40 percent increase in latency over monoBERT alone. The quadratic stage is affordable only because the linear stage in front of it cut the list by a factor of fifty.

Now the ceiling. BM25's recall on MS MARCO development queries was 59.2 percent at 50 candidates, 73.8 percent at 200 and 85.7 percent at 1,000 (Khattab & Zaharia, 2020, Table 2). A perfect reranker over the top 1,000 cannot exceed 85.7 percent recall, and one over the top 50 cannot exceed 59.2. Shrinking \(k_0\) to save reranker time moves the ceiling, and no amount of reranker quality recovers it. This is why improvements to the first stage, such as document expansion or learned sparse retrieval, often raise end-to-end quality more than a better final model.

Training each stage for its job

The objectives differ by position. An early stage is judged by whether the relevant items survive into its top \(k_i\), so it should be trained and evaluated on recall at its cut-off, not on nDCG@10. The final stage is judged on the ordering users see. Stages are also deployed on a different distribution than they are often trained on: a reranker trained on random negatives meets only the hard negatives its predecessor let through.

Whether stages should be learned separately is an open disagreement. Wang, Lin and Metzler treated the cascade itself as the object to learn, with a sequence of progressively more expensive ranking functions pruning candidates and efficiency part of the objective (Wang, Lin & Metzler, 2011, A Cascade Ranking Model for Efficient Ranked Retrieval, SIGIR). Gallagher and colleagues argued that the usual practice of training stages independently leaves effectiveness on the table and proposed optimising them jointly (Gallagher, Chen, Blanco & Culpepper, 2019, Joint Optimization of Cascade Ranking Models, WSDM). Most production teams still train stages separately, because separate models can be owned, retrained and rolled back independently.

A second argument is about how many stages there should be. Late-interaction models blur the line: ColBERT re-ranking reached MRR@10 34.9 against 36.0 for a BERT-base cross-encoder while being over 170 times faster, which makes a cheaper, near-final stage viable. LLM listwise rerankers push the other way, adding a new, even more expensive stage on top.

When it breaks

The ceiling is invisible offline. If relevance judgments were collected by pooling the results of the existing pipeline, documents the first stage never retrieves are never judged, and a new retriever that finds them is scored as if they were irrelevant.

Fixed \(k\) ignores query difficulty. A navigational query needs ten candidates and a vague exploratory one needs thousands. Constant cut-offs overspend on the first and starve the second.

Tail latency compounds. Each stage has its own p99. Under load, systems time out the expensive stage and fall back to the previous stage's order, so the quality users receive depends on traffic.

Later stages train on what earlier stages allowed. Logged interactions exist only for items that survived the cascade and were shown. A candidate generator retrained on those logs learns to reproduce the current pipeline's choices, the same feedback loop described in Position Bias and the Examination Hypothesis.

Attribution is hard. When a relevant document is missing from the final page, it could have been dropped at any stage. Without per-stage recall logging, teams tune the reranker for a loss that happened at retrieval.