Information retrieval at scale presents a fundamental engineering paradox: the models most capable of understanding deep semantic meaning are too computationally expensive to run across a massive corpus, while the methods fast enough to scan billions of documents lack the nuance to consistently find the best answers.
If you evaluate a complex cross-attention transformer or a large language model (LLM) against a corpus of millions of documents, the system will grind to a halt due to the computational complexity of token-level interactions. Conversely, if you rely solely on fast keyword matching, you miss deep semantic connections and synonyms.
To resolve this tension, modern search and recommendation systems employ a multi-stage cascading architecture. Instead of evaluating every document with a single model, the system acts as a progressive funnel. Early stages prioritize high throughput and recall to prune the search space, while later stages focus on high precision, applying heavy computational power only to the most promising candidates.
The Geometry of the Funnel
The core intuition behind a multi-stage cascade is the progressive optimization of the trade-off between latency and accuracy. As detailed by Jimmy Lin et al. in Learning to efficiently rank on big data, implementing a multi-stage cascade allows search systems to use inexpensive features to eliminate irrelevant documents early. This ensures that high-complexity ranking features are only applied to a tiny fraction of the corpus.
Imagine a system processing millions of potential items. The pipeline is structured into distinct tiers:
- Candidate Generation (Recall Stage): Reduces the corpus from millions to hundreds or thousands of candidates using high-speed, low-cost operations.
- Mid-Tier Filtering (Coarse Ranking): Narrows the pool further using lightweight neural models or vector spaces.
- Final Re-ranking (Precision Stage): Evaluates the top few dozen candidates using computationally intensive architectures like cross-encoders or LLMs.
By filtering out 99.9% of irrelevant documents in the first stage, the system can afford to spend orders of magnitude more compute per document in the final stage without compromising real-time latency requirements. As Qi Guo et al. observe in Talent Search and Recommendation Systems at LinkedIn: Practical Challenges and Lessons Learned, this multi-pass scoring funnel allows large-scale systems to maintain low latency while deploying highly sophisticated models at the tip of the funnel.
Stage 1: Maximizing Recall with Sublinear Search
The first stage must process the entire corpus. To do this efficiently, it must avoid comparing the query to every document text directly. Instead, it relies on pre-computed representations or inverted indexes.
Traditionally, this stage uses lexical matching like BM25 or fast dense retrieval via dual encoders (bi-encoders). In a dual encoder setup, document embeddings are computed offline and stored in a vector database. At query time, only the query is embedded, and a fast approximate nearest neighbor (ANN) search isolates the top candidates.
To optimize this stage even further, Aditya Kusupati et al. introduced Matryoshka Representation Learning, which nests smaller, highly accurate representations within the first few dimensions of a larger embedding. The system can perform the initial broad search using just a small slice of the embedding (e.g., 64 dimensions) to achieve massive wall-clock speedups, before passing the shortlisted items to a higher-dimensional re-ranking step.
Interestingly, the optimal query format changes depending on the stage. As shown by Adian Liusie et al. in University of Cambridge at TREC Cast 2022, a keyword-heavy raw history might maximize recall during initial lexical search, whereas a highly precise, de-contextualized query is required for late-stage re-ranking.
Stage 2: Deep Interaction and Precision Re-ranking
Once the candidate pool is reduced to a manageable size (e.g., 100 to 1,000 documents), the system hands off the candidates to a more powerful model.
The most common transition is from a bi-encoder to a cross-encoder. While a bi-encoder computes query and document embeddings independently, a cross-encoder feeds the query and document together into a transformer model like BERT. This allows full cross-attention: every token in the query can interact directly with every token in the document.
The authors of Scalable Zero-shot Entity Linking with Dense Entity Retrieval demonstrate this synergy clearly: a fast bi-encoder first surfaces potential candidates across millions of entities, and a deep cross-encoder then performs the fine-grained token-level interaction needed for precise disambiguation.
[ Entire Corpus: Millions of Documents ]
│
▼ (Stage 1: Bi-Encoder / Lexical Search)
[ Candidate Pool: ~1,000 Documents ]
│
▼ (Stage 2: Cross-Encoder Re-ranking)
[ Top Candidates: ~100 Documents ]
│
▼ (Stage 3: Listwise LLM / Generative Selection)
[ Final Ranked Results: Top 10 ]
In state-of-the-art systems, this cascade can extend to three or four stages. For instance, Carlos Eduardo Rosar Kos Lassance et al. developed a four-stage pipeline detailed in Naverloo @ TREC Deep Learning and Neuclir 2023: As Easy as Zero, One, Two, Three - Cascading Dual Encoders, Mono, Duo, and Listo for Ad-Hoc Retrieval. Their architecture transitions from fast dual encoders to pointwise re-rankers (Mono), pairwise re-rankers (Duo), and finally to sophisticated listwise generative re-ranking using GPT-4.
Why the Cascade Works
The mathematical justification for multi-stage retrieval lies in the distribution of computational effort. If a single-stage cross-encoder takes $C_{\text{heavy}}$ time to evaluate a single document, evaluating it over a corpus of size $N$ takes $\mathcal{O}(N \cdot C_{\text{heavy}})$. For large $N$, this is completely unfeasible for real-time systems.
In a cascaded pipeline, the total time complexity becomes:
$$\text{Total Time} = \mathcal{O}(N \cdot C_{\text{light}}) + \mathcal{O}(K \cdot C_{\text{heavy}})$$
where $K$ is the small candidate pool size ($K \ll N$) and $C_{\text{light}}$ is the negligible cost of an index lookup or dot product. By decoupling the scale of the corpus ($N$) from the complexity of the final model ($C_{\text{heavy}}$), multi-stage architectures achieve the best of both worlds: sublinear scaling with respect to corpus size, and deep semantic accuracy at the point of delivery.