Skip to main content
ZICQ

Wiki Concepts

Reranking

Concepts
Aliases: rerank cross-encoder re-ranking ·2026-10-10

Reranking

Reranking (or Rerank) re-evaluates and re-orders an initial candidate list retrieved by an upstream coarse-stage search, employing models with deeper semantic interaction. In modern search and Retrieval-Augmented Generation (RAG) pipelines, it serves as the critical second stage, establishing a Pareto-optimal boundary between latency budgets and top-k precision.


The Information Bottleneck in Coarse Retrieval

In large-scale search architectures, the first stage must rapidly evaluate candidates across millions to billions of documents. Consequently, systems rely on Bi-Encoders (dense vector search) or inverted lexical indexes (BM25):

  • Bi-Encoder Compression Bottleneck: A bi-encoder compresses an entire passage offline into a single, fixed-size dense vector $\mathbf{v} \in \mathbb{R}^d$. During query processing, query and document vectors are compared via simple dot products or cosine metrics. Because the two towers are completely decoupled until the scalar product, they lack token-level cross-attention, masking fine-grained lexical and logical relationships.
  • Classic Failure Modes: Bi-encoders frequently exhibit semantic drift in:
    • Negation and conditional constraints (e.g., distinguishing "how to enable passwordless auth" from "how to disable passwordless auth");
    • Exact versioning and parameter names (e.g., distinguishing v1.2 from v2.1);
    • Long-tail entities and tight relational bindings.

The reranking stage does not expand search scope; instead, it sifts through the dozens of coarse candidates, leveraging deep cross-attention to isolate genuine answers and eliminate superficially relevant false positives.


Architectural Comparison: Bi-Encoder vs. Cross-Encoder

[Bi-Encoder Architecture]
Query ──► [Transformer Encoder Q] ──► Vector u ─┐
                                                 ├─► Dot Product / Cosine (Lightweight, O(d))
Doc   ──► [Transformer Encoder D] ──► Vector v ─┘
(Documents encoded independently offline; no token-level cross-attention)

[Cross-Encoder Architecture]
[CLS] + Query + [SEP] + Document + [SEP]
                   │
                   ▼
     ┌───────────────────────────┐
     │  Full Transformer Encoder │ ◄── Every Query Token attends to every Doc Token
     │  (Dense Cross-Attention)  │     across all layers via full self-attention
     └───────────────────────────┘
                   │
                   ▼
            [CLS] Classification Head ──► Scalar Relevance Score (Complexity O((Lq + Ld)^2))

1. Computational Complexity and Interaction Depth

  • Bi-Encoder: Inputs are processed separately. Document vectors are precomputed offline. Search scales at $O(N \cdot d)$ (or $O(\log N)$ via ANN graphs), but suffers from semantic compression loss.
  • Cross-Encoder: Query and passage are concatenated into a unified sequence $[CLS] \circ q \circ [SEP] \circ d \circ [SEP]$ and passed through a Transformer encoder. Full self-attention computes dense pairwise interactions across all tokens:

$$\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V$$

Every token in the query attends directly to every token in the document across every layer. This comprehensive cross-attention delivers exceptional semantic discernment, but scales quadratically with sequence length $O((|q| + |d|)^2)$. Scores cannot be precomputed; pairs must be processed dynamically online.

2. Comparative Feature Matrix

Dimension Bi-Encoder Cross-Encoder (Reranker)
Scoring Mechanism Dot product of isolated vectors $\langle E(q), E(d) \rangle$ Joint sequence encoding via classification head
Token-level Interaction None (pooled global vector only) Dense, multi-layer pairwise cross-attention
Evaluation Scope Entire corpus (millions/billions) Initial coarse candidate set ($50 \sim 200$)
Compute Latency Sub-millisecond to low millisecond Milliseconds per pair (GPU accelerated)
Ranking Accuracy (nDCG@10) Baseline $10% \sim 35%$ boost over bi-encoders

Two-Stage Cascading Pipeline

In enterprise RAG architectures, a two-stage cascade balances tail latency and retrieval precision:

User Query
    │
    ▼
[Stage 1: Retrieval / Recall] ──► Hybrid Search (BM25 + Dense Vectors)
    │                             Retrieves K1 = 50~100 candidates in <20ms from 1M+ docs
    ▼
[Deduplication & Fusion]      ──► Reciprocal Rank Fusion (RRF) merges candidate lists
    │
    ▼
[Stage 2: Reranking / Scorer] ──► Cross-Encoder (e.g., BGE-Reranker, Cohere Rerank)
    │                             Batched parallel inference re-scores all candidates
    ▼
[Top-K Truncation & Context]  ──► Selects Top K2 = 3~5 highest-scoring passages
    │
    ▼
[Generator LLM]               ──► Ingests curated context and synthesizes final answer
  • Sizing Heuristics:
    • Initial Candidates ($K_1$): Typically $50 \sim 100$. If $K_1$ is too low, the target answer may never enter the candidate set (recall bottleneck). If $K_1 > 200$, batch inference latency breaches interactive SLO limits.
    • Final Evidence ($K_2$): Typically $3 \sim 8$. Dictated by the generator's context window budget and vulnerability to lost-in-the-middle degradation.

Scoring Mechanisms and Calibration Traps

Cross-Encoder heads typically output an unnormalized logit score, convertible to a $(0, 1)$ range via the standard Sigmoid function:

$$P(\text{Relevant} \mid q, d) = \sigma(\text{logit}) = \frac{1}{1 + e^{-\text{logit}}}$$

The Hard Cutoff Trap in Production

In production environments, hard-coding an absolute score threshold (e.g., filtering out scores $< 0.7$) is a dangerous anti-pattern:

  1. Domain and Distribution Shift: A general-domain reranker might produce scores of $0.85$ on Wikipedia passages, but yield scores around $0.35$ on proprietary engineering code or internal logs, even for perfectly relevant evidence.
  2. Length Bias and Attention Pooling: Passage lengths introduce systematic variance in logit magnitudes. Absolute score values across different queries are not directly comparable.

Robust Post-Processing Strategies

  1. Relative Dropoff Thresholding: $$\text{Filter condition: } \text{Score}(d_i) \ge \alpha \cdot \text{Score}(d_1) \quad (\alpha \in [0.6, 0.8])$$ Truncate candidates when their scores plunge sharply relative to the top candidate, signaling a drop in relevance confidence.
  2. Top-P Cumulative Mass Filtering: Normalize candidate scores via Softmax and retain documents in descending order until their cumulative probability exceeds a target threshold (e.g., $P=0.85$).

Modern Frontiers: Late Interaction and LLM Reranking

Beyond traditional BERT/RoBERTa cross-encoders, two modern paradigms have emerged:

1. Late Interaction (ColBERT)

ColBERT provides a compromise between bi-encoders and cross-encoders. During offline indexing, it preserves all individual token embeddings rather than pooling into a single vector. At search time, it computes relevance using the MaxSim operator—summing the maximum dot products of query tokens against document tokens:

$$\text{Score}{\text{MaxSim}}(q, d) = \sum{i=1}^{|q|} \max_{j=1}^{|d|} \left( \mathbf{q}_i \cdot \mathbf{d}_j \right)$$

Combined with vector quantization (ColBERTv2), late interaction maintains token-level expressive power while enabling vector matrix searches across thousands of candidates in milliseconds.

2. LLM-as-a-Reranker (Listwise Prompting)

Long-context reasoning models enable Listwise Reranking (such as RankGPT). Instead of evaluating pairs in isolation (pointwise scoring), listwise prompting passes multiple candidates simultaneously into an LLM, prompting it to output an ordered ranking. The model identifies redundant passages, complementary claims, and mutual contradictions across evidence, albeit at higher token cost and inference latency.


Production Deployment and Evaluation

  1. Evaluation Metrics:
    • MRR@10 (Mean Reciprocal Rank): The reciprocal rank of the first relevant document, measuring how effectively top evidence surfaces.
    • nDCG@10 (Normalized Discounted Cumulative Gain): Measures multi-grade relevance with logarithmic positional discounting.
    • HitRate@K: Proportion of queries where at least one correct passage is retrieved within the top K.
  2. Inference Optimization:
    • Smart Batching: Group candidate sequences by token length prior to model execution, eliminating redundant zero-padding tokens in GPU memory.
    • Export computational graphs using ONNX Runtime or TensorRT with FP16/BF16 precision, keeping inference for 50 candidates within $15 \sim 30\text{ ms}$.

Sources and Key Literature