Multi-Stage Retrieval

Multi-stage retrieval operates as a sequential funnel where each stage progressively refines results. The initial stage uses a lightweight retriever (e.g., BM25 or Bi-Encoder) to quickly scan millions of documents and return a candidate set of 100-1000 items. Subsequent stages apply computationally intensive models (e.g., Cross-Encoders) only to this reduced set, making the architecture both scalable and precise.

• Stage 1 (Retrieval): High recall, low precision, sub-10ms latency
• Stage 2 (Re-Ranking): Low recall, high precision, 50-200ms latency
• Trade-off: Balances the speed of sparse retrieval with the accuracy of deep neural scoring

The two-stage paradigm typically pairs a Bi-Encoder for initial retrieval with a Cross-Encoder for re-ranking. Bi-Encoders encode queries and documents independently into dense vectors, enabling pre-computed document embeddings and fast cosine similarity search via Approximate Nearest Neighbor (ANN) indexes.

Cross-Encoders process the query-document pair jointly through full self-attention, allowing rich token-level interactions that capture nuanced relevance signals. This joint processing is 10-100x slower but yields substantially higher precision.

• Bi-Encoder: Independent encoding, O(1) per document at query time
• Cross-Encoder: Joint encoding, O(n) transformer passes per candidate

The first-stage retriever must maximize recall while minimizing latency. Common strategies include:

• Sparse Retrieval (BM25): Inverted index lookup with term frequency-inverse document frequency scoring, excellent for exact keyword matching and rare terms
• Dense Retrieval (DPR): Vector similarity search using dual-encoder embeddings, capturing semantic similarity even without lexical overlap
• Hybrid Retrieval: Combining sparse and dense signals at the candidate generation stage using Reciprocal Rank Fusion (RRF) to merge result lists before re-ranking

The candidate set size is a critical hyperparameter—too small and relevant documents are missed, too large and the re-ranker becomes a bottleneck.

The re-ranking stage applies a Cross-Encoder Transformer (e.g., BERT, MiniLM) to score each query-document pair. Unlike Bi-Encoders, Cross-Encoders concatenate the query and document text with a [SEP] token and process them through full self-attention layers.

The model outputs a single relevance score, typically passed through a sigmoid activation. This joint encoding captures:

• Exact term matching with contextual weighting
• Paraphrase detection and semantic equivalence
• Query-document term interactions that Bi-Encoders miss

Modern implementations use distilled models like MiniLM or TinyBERT to reduce latency while maintaining 95%+ of the full model's accuracy.

ColBERT (Contextualized Late Interaction over BERT) offers a middle ground between Bi-Encoder efficiency and Cross-Encoder precision. It stores token-level embeddings for each document—every token in the document gets its own contextualized vector.

At query time, ColBERT computes relevance via MaxSim: for each query token, it finds the most similar document token embedding and sums these maximum cosine similarities. This preserves fine-grained token interactions without the quadratic cost of full cross-attention.

• Storage: Token embeddings require more index space than single-vector Bi-Encoders
• Latency: Slower than Bi-Encoders but 10-50x faster than Cross-Encoders
• Use Case: Ideal when precision requirements exceed Bi-Encoder capabilities but Cross-Encoder latency is prohibitive

Multi-stage retrieval requires careful latency budgeting across stages. A typical search system targets sub-200ms total response time:

• Candidate Retrieval: 5-20ms (ANN search or inverted index lookup)
• Feature Extraction: 2-5ms (fetching document metadata, recency signals)
• Re-Ranking: 50-150ms (Cross-Encoder scoring of top 50-200 candidates)
• Final Ranking: 1-5ms (applying business rules, diversity adjustments)

Dynamic depth adjustment can vary the number of candidates passed to the re-ranker based on query complexity—simple navigational queries may skip re-ranking entirely, while ambiguous informational queries receive deeper processing.