Reranking: Cross-Encoders for Precise Information Retrieval › Latency Considerations and Optimization

You need not rerank all retrieved documents. Confidence-based filtering uses the bi-encoder scores to identify high-confidence candidates. If the top bi-encoder result has a score significantly higher than the rest, you might return it directly without reranking, applying the cross-encoder only to ambiguous cases where scores are close. This approach recognizes that for many queries, the bi-encoder is sufficiently confident in its top prediction that the expensive reranking provides minimal benefit.

By measuring the gap between the top score and the mean or second-highest score, you can estimate the uncertainty of the initial retrieval and allocate computational resources only where ambiguity exists. A large gap between the first and second retrieved document suggests that the bi-encoder is very confident in its top result, and the cross-encoder is unlikely to change the ranking. A small gap suggests that the relative ordering is uncertain, and the cross-encoder's fine-grained discrimination is most likely to add value.

This strategy requires careful calibration to ensure that high-confidence predictions are indeed accurate; otherwise, you risk bypassing the reranker precisely when it would have caught a retrieval error. Empirical validation on a held-out test set is needed: measure how often the bi-encoder's top result is also the cross-encoder's top result as a function of the score gap, and use this relationship to set the threshold for when to skip reranking.

Cross-encoder complexity grows quadratically with sequence length. For long documents, you typically truncate to the first $L_{\max}$ tokens (often 512 or 1024 tokens). However, relevant information might appear at the end of a document, a phenomenon known as the "lost in the middle" problem. Early portions of documents often contain boilerplate, introductions, or general context, while specific answers may appear later.

Sliding window approaches split long documents into overlapping chunks, rerank each chunk independently, and aggregate scores. For a document $d$ chunked into overlapping segments $\{c_1, c_2, \ldots, c_m\}$, the final document score is:

$$s(q, d) = \max_{c \in \text{chunks}(d)} s(q, c)$$

where:

• $d$: the full document being scored
• $c$: a specific chunk (text segment) of the document
• $\text{chunks}(d)$: set of overlapping text segments extracted from document $d$
• $s(q, c)$: relevance score between query $q$ and chunk $c$
• $s(q, d)$: final document score, computed as the maximum score across all chunks

Taking the maximum over chunks is motivated by the intuition that a document is relevant if any part of it answers the query. Alternative aggregation strategies include taking the average of the top few chunk scores, which is more reliable to chunks with spuriously high scores, or using a learned aggregation function that weights chunks based on their position or content. The choice of chunk size and overlap involves tradeoffs: smaller chunks reduce the quadratic cost per chunk but may lose context that spans chunk boundaries, while larger chunks preserve more context but increase computational cost.

The key insight here is that chunking shifts the granularity of the retrieval unit from the document to the passage. This is often a fundamentally better alignment with how queries are answered: most questions are answered in a specific paragraph or section, not by a document in its entirety. Many production systems chunk documents at indexing time rather than reranking time, treating chunks as first-class retrieval units and only reassembling them when necessary.

Researchers have developed architectures that balance the efficiency of bi-encoders with the accuracy of cross-encoders. Late interaction models, exemplified by ColBERT (Contextualized Late Interaction over BERT), encode query and document separately but allow token-level interactions at scoring time. The core idea is to preserve one dense vector per token rather than collapsing the entire document into a single vector. This dramatically increases storage requirements compared to single-vector bi-encoders, but enables much richer matching at query time.

The ColBERT scoring function captures the degree to which each query token is "satisfied" by the best-matching document token:

$$s(q, d) = \sum_{i=1}^{L_q} \max_{j=1}^{L_d} \mathbf{q}_i^T \mathbf{d}_j$$

where:

• $L_q$: number of tokens in the query
• $L_d$: number of tokens in the document
• $\mathbf{q}_i \in \mathbb{R}^d$: contextualized embedding of the $i$-th query token
• $\mathbf{d}_j \in \mathbb{R}^d$: contextualized embedding of the $j$-th document token
• $\mathbf{q}_i^T \mathbf{d}_j$: dot product similarity between query token $i$ and document token $j$
• $s(q, d)$: final relevance score (sum of maximum similarities for each query token)

This operation is known as the MaxSim (maximum similarity) operator. For each query token, it finds the document token that most closely matches it, then sums these maximum similarities across all query tokens. The intuition is that a document is relevant when it contains a good match for every important concept in the query, not just when some average representation is similar.

The query and document are encoded independently (fast, precomputable), but the scoring involves a maximum similarity computation between all query-document token pairs, costing $O(L_q L_d)$. This is more expensive than a dot product but vastly cheaper than full cross-attention per layer. Because documents can be pre-encoded and indexed, ColBERT achieves latency much closer to bi-encoders while retaining much of the cross-encoder's ability to model fine-grained interactions. Recent improvements in ColBERTv2 introduce residual compression and denoised supervision, further reducing storage requirements and improving retrieval accuracy. These models represent a promising middle ground for applications where full cross-encoders are too slow but bi-encoders are insufficiently accurate.

For extremely large candidate sets, you can apply vector quantization techniques from Product Quantization to cross-encoder representations, or use knowledge distillation to train a smaller student model to mimic the large cross-encoder's scores. Distillation involves training a compact student model (perhaps a smaller transformer or even a bi-encoder) to reproduce the ranking decisions of the large cross-encoder teacher. The student learns to approximate the teacher's score function, achieving much faster inference while preserving much of the accuracy.

This approach is particularly effective when combined with the cascade architecture: the student model filters the bulk of candidates, and the teacher model verifies only the most promising ones. Distillation also allows you to compress a large cross-encoder into a faster bi-encoder that has been "taught" to produce embeddings that approximate cross-encoder scores, effectively transferring some of the cross-encoder's discriminative ability into a precomputable representation. Models like TAS-B and Augmented SBERT use variants of this distillation approach to produce bi-encoders that significantly outperform bi-encoders trained without a cross-encoder teacher.