Hybrid Search & Reranking

The Big Picture: Retrieval + Reranking Pipeline

Modern information retrieval splits into two complementary stages:

• Retrieval (Recall-Focused): Fast, approximate algorithms to find top-1000 candidates from billions of documents. Examples: BM25 (keyword-based), dense embeddings (semantic), or hybrid fusion.
• Reranking (Precision-Focused): Accurate, expensive models to refine top candidates. Examples: cross-encoder BERT, listwise learning-to-rank, business logic.

Why This Two-Stage Design?

Single-stage neural reranking (e.g., cross-encoder on all 100M documents) would be prohibitively slow. By retrieving ~1000 candidates first, we get a 100x latency reduction while maintaining high quality.

Why Hybrid Search Works: Complementary Strengths

BM25 and dense embeddings have orthogonal strengths. A concrete example:

Example 1: Exact Term Match

Query: "BERT architecture"

• BM25: Directly matches "BERT" and "architecture" in document text. Scores highly because both keywords are present.
• Dense: May confuse with other transformer models, pooling "BERT" with "GPT," "T5," etc., diluting the signal for this specific architecture question.

Example 2: Semantic Paraphrase

Query: "fast cars"

• BM25: Misses documents with "speedy vehicles" or "rapid automobiles"—no keyword overlap.
• Dense: Finds semantically similar passages through learned embeddings. The query embedding is close to the passage embedding.

Empirical Evidence: BEIR Benchmark

The BEIR benchmark evaluates zero-shot retrieval across 18 diverse datasets (news, scientific papers, legal docs, Q&A). Typical results:

Hybrid consistently beats either method alone by 5-15% on NDCG@10, demonstrating the power of ensemble retrieval.

Why Ensemble Wisdom Works

The principle: diverse retrieval models make independent mistakes. By combining them (via RRF or interpolation), we reduce the chance of missing relevant documents.

Score Fusion: Interpolation & Normalization

When combining multiple retrievers, we need to fuse their scores. Simple interpolation is intuitive but requires careful handling of score scales.

Linear Interpolation Formula

score_hybrid(d) = α × score_BM25(d) + (1 - α) × score_dense(d)

The parameter α controls the balance: α=1.0 gives pure BM25, α=0.0 gives pure dense, α=0.5 weighs them equally.

The Normalization Problem

BM25 scores are unbounded (depend on document length, term frequency), while dense cosine similarity is bounded in [-1, 1]. Direct interpolation favors BM25 because its scores are larger.

Solution: Normalize both scores to a common range before interpolation.

Min-Max Normalization

normalized_score = (score - min_score) / (max_score - min_score)

Scales any score to [0, 1] based on observed min/max in the result set. Simple but sensitive to outliers.

Z-Score Normalization

normalized_score = (score - mean) / std_dev

Centers scores around 0 with unit variance. More robust but can produce negative values after interpolation.

Tuning α

Grid search on a validation set: try α ∈ {0.1, 0.3, 0.5, 0.7, 0.9} and measure NDCG@10. Surprisingly, α=0.5 (equal weighting) works well as a starting point and rarely needs heavy tuning.

Reciprocal Rank Fusion (RRF): Parameter-Free Combination

RRF is an elegant fusion method that requires no score normalization—it works purely on rank positions.

RRF Formula

RRF_score(document) = Σ 1 / (k + rank(document))

Where:

• k: A constant (typically 60) that prevents division by zero and balances the impact of different retrievers.
• rank(document): The position of the document in one retriever's ranked list (1-indexed).
• Σ: Sum over all retrievers.

Worked Example: 5 Documents

Key Properties of RRF

• Parameter-Free: No α tuning needed. Works out-of-the-box.
• Robust to Scale: Only uses ranks, not raw scores. Immune to score distribution differences.
• Competitive: Empirically matches or beats learned fusion methods (like gradient boosting) on many benchmarks.
• k Parameter: Can vary k (often 50-100); k=60 is standard. Larger k = more impact for high-ranked items.

Cross-Encoder Reranking: Bi-Encoder vs Cross-Encoder

Reranking requires a model that can score query-document pairs with fine-grained relevance. Cross-encoders are the standard choice.

Bi-Encoder (Retrieval)

Architecture: Encode query and passage separately, then compare embeddings.

query_embedding = encoder(query)
passage_embedding = encoder(passage)
similarity = cosine(query_embedding, passage_embedding)

Advantage: Fast at inference time—encode all passages offline, then do cheap cosine similarity at query time.

Disadvantage: Limited interaction between query and passage. Embeddings are fixed-size bottlenecks.

Cross-Encoder (Reranking)

Architecture: Concatenate query and passage into a single input, run through BERT, extract [CLS] token score.

input = [CLS] + query_tokens + [SEP] + passage_tokens + [SEP]
output = transformer(input)
relevance_score = linear_layer(output[CLS])

Advantage: Full interaction between query and passage. Much more expressive and accurate.

Disadvantage: O(N) cost per query—must run forward pass for each candidate. Expensive, so only viable on small candidate sets.

Training Cross-Encoders

Standard approach on MS MARCO dataset:

• Input: (query, passage) pairs with binary relevance label (relevant=1, not-relevant=0).
• Loss: Cross-entropy loss on [CLS] logit.
• Triplet loss variant: order three examples (query, relevant_doc, irrelevant_doc) and optimize ranking.

Listwise & Pairwise Reranking Methods

Beyond simple cross-encoders, learning-to-rank (LTR) offers richer training objectives. See Learning-to-Rank Guide for depth.

Pairwise Learning: RankNet & LambdaRank

Learn to rank: document A > document B given a query.

• RankNet: Neural network trained on pairs; sigmoid cross-entropy loss on (score_A - score_B).
• LambdaRank: Add gradient manipulation by λ-weights to directly optimize ranking metrics (NDCG).

Listwise Learning: LambdaMART & SetRank

Optimize the entire ranking directly, not just pairs.

• LambdaMART: Gradient boosting trees + lambda weighting. Very effective; standard in industry.
• SetRank: Transformer-based listwise learning. More modern approach.

Modern Rerankers: monoT5, duoT5, ColBERT

monoT5

Idea: Treat reranking as a sequence-to-sequence task. Input: "Query: [q] Document: [d]". Output: "true" (relevant) or "false" (not relevant).

T5_score = P(output="true" | input)  # Relevance probability

duoT5

Idea: Pairwise T5 reranker. Compare two documents directly: "Query: [q] Document A: [d1] Document B: [d2]". Output: "A" or "B".

ColBERT

Idea: Late interaction model. Compute query and document embeddings (like bi-encoder), but similarity is computed token-by-token (not pooled). Cache passage embeddings offline.

ColBERT_score = Σ_q max_d (embed_q[q] · embed_d[d])
# For each query token, find max similarity with any document token

Advantage: faster than cross-encoder (parallelizable token comparisons), more accurate than simple cosine.

Two-Stage to Multi-Stage Pipelines

Production search systems often have 3+ stages, each with different latency budgets and objectives.

Classic Two-Stage

Stage 1: Hybrid retrieval (BM25 + dense) → 1000 candidates (10ms)
Stage 2: Cross-encoder reranking → 10 final results (50ms)
Total: 60ms

Extended Three-Stage

Stage 1: ANN search (all vectors) → 1000 candidates (8ms)
Stage 2: Cross-encoder reranking → 100 results (40ms)
Stage 3: Business logic (diversity, freshness, revenue) → 10 final (2ms)
Total: 50ms

Cascaded Retrieval (Alternative)

Instead of fusing results, run retrievers independently and merge:

Stage 1a: BM25 OR dense → top-1000 from each (10ms total)
Stage 1b: Merge (union/intersection) → 1000-2000 candidates
Stage 2: Reranker → top-10 (50ms)
Total: 60ms

Dynamic Candidate Set Sizing

Query difficulty estimation can adjust candidate pool:

• Easy query (high confidence): Retrieve 500 candidates, rerank top-20, return top-5.
• Hard query (low confidence): Retrieve 5000 candidates, rerank top-100, return top-10.

SPLADE & Learned Sparse Retrieval

SPLADE bridges the gap between BM25 (sparse, exact) and dense retrieval (semantic, slow index)

What is SPLADE?

SPLADE: Sparse Lexical and DEnse Embeddings. A learned sparse retrieval method that produces document representations as weighted term vectors.

SPLADE Formula

for each vocabulary term t:
  weight[t] = log(1 + ReLU(MLM_logits[t]))

# MLM_logits come from BERT's masked language model head
# Result: sparse vector (most weights are 0, few are large)

Key Differences from BM25

• BM25: TF-IDF weights based on term frequency and document length.
• SPLADE: Neural weights learned end-to-end. Can capture semantic importance (e.g., "BERT" gets high weight even with low frequency if it's semantically relevant).

Advantages

• Sparse Index: Uses inverted index like BM25—scalable to billions of documents.
• Semantic: Learns which terms are important for relevance, not just frequency.
• Competitive Accuracy: SPLADE typically beats BM25 by 10-20% on NDCG@10, approaching dense retrieval.
• FLOPS Regularization: Training regularizes L2 norm of weights to keep vectors sparse.

Evaluation Metrics for Reranking

How do we measure reranking effectiveness? Multiple metrics each capture different aspects.

MRR: Mean Reciprocal Rank

Definition: Average of 1 / (rank of first relevant item) across queries.

MRR = (1/|Q|) × Σ 1 / rank_of_first_relevant(q)

Example: Query 1: first relevant at rank 2 → 1/2. Query 2: first relevant at rank 5 → 1/5. MRR = (1/2 + 1/5) / 2 = 0.35

Use Case: When you care about finding *any* relevant item fast (e.g., "Is the answer in top-5?").

NDCG: Normalized Discounted Cumulative Gain

Formula:

DCG@K = rel[1] + Σ_{i=2}^K rel[i] / log2(i)
NDCG@K = DCG@K / Ideal_DCG@K  # Normalize by best possible ranking

Interpretation: rel[i] = relevance score (0=irrelevant, 1=relevant, 2=very relevant, etc.). Positions matter; top-k are weighted more.

Worked Example: NDCG@5

DCG@5 = 1.00 + 0.00 + 0.50 + 0.43 + 0.00 = 1.93

Ideal ranking (if ordered by relevance): 1, 1, 1, 0, 0 → Ideal DCG@5 = 1.00 + 0.63 + 0.50 + 0.00 + 0.00 = 2.13

NDCG@5 = 1.93 / 2.13 = 0.906

Precision@K and Recall@K

• Precision@K: # relevant in top-K / K. What fraction of top-K are relevant?
• Recall@K: # relevant in top-K / total relevant. What fraction of all relevant docs are in top-K?

MAP: Mean Average Precision

Definition: Average precision at each relevant position.

AP = (1 / num_relevant) × Σ_{rank of relevant} P@rank

BEIR Zero-Shot Benchmark

Evaluate retrieval on 18 diverse datasets without task-specific fine-tuning. BEIR is the standard for comparing methods.

A/B Testing vs Offline Evaluation

• Offline: NDCG@10, MRR, etc. on static test set. Fast feedback loop.
• A/B Test: Real users, measure clicks, dwell time, conversions. Gold standard but slow (weeks).

Production Considerations: Latency & Caching

Deploying reranking at scale requires careful engineering.

Latency Breakdown

• Cross-encoder inference: ~0.5-1ms per document on GPU.
• For 1000 candidates: 500-1000ms if processed sequentially.
• Solution: Batch inference on GPU. Process 100 docs in parallel ≈ 50ms.

Caching Strategies

Score Caching

Pre-compute reranker scores for popular queries and cache (Redis, memcached).

cache_key = hash(query)
if cache_key in redis:
  scores = redis.get(cache_key)
else:
  scores = reranker.score(candidates)
  redis.set(cache_key, scores, ttl=3600)

Embedding Caching

For late-interaction models (ColBERT), cache passage embeddings offline and load on-demand.

Knowledge Distillation

Train a faster bi-encoder to mimic a cross-encoder. Use cross-encoder soft labels (probability scores) as training targets.

loss = KL_divergence(biencoder_logits, cross_encoder_soft_targets)

Result: faster retrieval (parallel encoding) with near cross-encoder accuracy.

Late Interaction (ColBERT)

Cache passage embeddings offline. Reranking becomes a fast nearest-neighbor lookup, not a neural forward pass.

Hardware Decisions

Model Serving

• Triton Inference Server: Multi-model serving, batching, dynamic loading.
• TorchServe: PyTorch-native serving, auto-batching, A/B testing.
• vLLM (for seq2seq): Optimized for monoT5, duoT5 inference.

Monitoring & SLOs

• P95 Latency: 95th percentile latency SLO (e.g., <100ms).
• Throughput: Requests per second (e.g., 1000 RPS).
• Score Calibration Drift: Monitor if reranker scores diverge from true relevance over time (retrain if drift > 5%).

Python Implementation: End-to-End Search Pipeline

Build a complete hybrid search + reranking system from scratch.

Complete Implementation

import numpy as np
import pandas as pd
from collections import defaultdict

class BM25Retriever:
    """Simple BM25 using TF-IDF"""
    def __init__(self, corpus, k1=1.5, b=0.75):
        self.corpus = corpus
        self.k1 = k1
        self.b = b
        self.build_index()

    def build_index(self):
        self.idf = {}
        self.doc_lengths = []
        self.term_freqs = []

        for doc_id, doc in enumerate(self.corpus):
            terms = doc.lower().split()
            self.doc_lengths.append(len(terms))

            tf = defaultdict(int)
            for term in terms:
                tf[term] += 1
            self.term_freqs.append(tf)

            for term in set(terms):
                self.idf[term] = self.idf.get(term, 0) + 1

        # Convert to IDF scores
        num_docs = len(self.corpus)
        for term in self.idf:
            self.idf[term] = np.log((num_docs - self.idf[term] + 0.5) /
                                     (self.idf[term] + 0.5) + 1)

        self.avg_doc_length = np.mean(self.doc_lengths)

    def score(self, query, doc_id):
        """Score a single document for the query"""
        query_terms = query.lower().split()
        score = 0.0

        for term in query_terms:
            if term not in self.idf:
                continue

            tf = self.term_freqs[doc_id].get(term, 0)
            idf_score = self.idf[term]
            doc_length = self.doc_lengths[doc_id]

            norm_factor = 1 - self.b + self.b * (doc_length / self.avg_doc_length)
            bm25_term = idf_score * ((self.k1 + 1) * tf) / (self.k1 * norm_factor + tf)
            score += bm25_term

        return score

    def retrieve(self, query, top_k=10):
        """Retrieve top-k documents"""
        scores = {}
        for doc_id in range(len(self.corpus)):
            scores[doc_id] = self.score(query, doc_id)

        ranked = sorted(scores.items(), key=lambda x: x[1], reverse=True)
        return [(doc_id, score) for doc_id, score in ranked[:top_k]]


class DenseRetriever:
    """Simple dense retrieval using TF-IDF vectors"""
    def __init__(self, corpus):
        self.corpus = corpus
        self.build_index()

    def build_index(self):
        from collections import Counter

        # Build vocabulary
        vocab = set()
        for doc in self.corpus:
            vocab.update(doc.lower().split())
        self.vocab = sorted(list(vocab))
        self.word2id = {w: i for i, w in enumerate(self.vocab)}

        # Build TF-IDF vectors
        self.vectors = []
        for doc in self.corpus:
            vec = np.zeros(len(self.vocab))
            terms = doc.lower().split()
            for term in terms:
                vec[self.word2id[term]] += 1
            # Normalize to unit length (proxy for cosine similarity)
            norm = np.linalg.norm(vec)
            if norm > 0:
                vec = vec / norm
            self.vectors.append(vec)
        self.vectors = np.array(self.vectors)

    def retrieve(self, query, top_k=10):
        """Retrieve top-k documents"""
        query_vec = np.zeros(len(self.vocab))
        for term in query.lower().split():
            if term in self.word2id:
                query_vec[self.word2id[term]] += 1

        norm = np.linalg.norm(query_vec)
        if norm > 0:
            query_vec = query_vec / norm

        # Cosine similarity
        scores = {}
        for doc_id in range(len(self.corpus)):
            scores[doc_id] = float(np.dot(query_vec, self.vectors[doc_id]))

        ranked = sorted(scores.items(), key=lambda x: x[1], reverse=True)
        return [(doc_id, score) for doc_id, score in ranked[:top_k]]


class HybridRetriever:
    """RRF fusion of BM25 and dense"""
    def __init__(self, bm25, dense, k=60):
        self.bm25 = bm25
        self.dense = dense
        self.k = k

    def retrieve(self, query, top_k=100):
        """RRF fusion"""
        bm25_results = self.bm25.retrieve(query, top_k=1000)
        dense_results = self.dense.retrieve(query, top_k=1000)

        # Convert to rank dict
        bm25_ranks = {doc_id: rank + 1 for rank, (doc_id, score) in enumerate(bm25_results)}
        dense_ranks = {doc_id: rank + 1 for rank, (doc_id, score) in enumerate(dense_results)}

        # RRF score
        rrf_scores = {}
        all_docs = set(bm25_ranks.keys()) | set(dense_ranks.keys())

        for doc_id in all_docs:
            rrf_score = 0.0
            if doc_id in bm25_ranks:
                rrf_score += 1 / (self.k + bm25_ranks[doc_id])
            if doc_id in dense_ranks:
                rrf_score += 1 / (self.k + dense_ranks[doc_id])
            rrf_scores[doc_id] = rrf_score

        ranked = sorted(rrf_scores.items(), key=lambda x: x[1], reverse=True)
        return [(doc_id, score) for doc_id, score in ranked[:top_k]]


class CrossEncoderReranker:
    """Simple dot-product reranker (proxy for cross-encoder)"""
    def __init__(self, corpus):
        self.corpus = corpus
        # Simple relevance model: more term overlap = higher score

    def score(self, query, doc_id):
        """Score a query-document pair"""
        query_terms = set(query.lower().split())
        doc_terms = set(self.corpus[doc_id].lower().split())

        overlap = len(query_terms & doc_terms)
        # Penalize long docs (prefer concise relevant matches)
        length_factor = 1.0 / np.sqrt(len(doc_terms) + 1)

        return overlap * length_factor


class SearchPipeline:
    """End-to-end search: hybrid retrieve → rerank"""
    def __init__(self, corpus):
        self.bm25 = BM25Retriever(corpus)
        self.dense = DenseRetriever(corpus)
        self.hybrid = HybridRetriever(self.bm25, self.dense, k=60)
        self.reranker = CrossEncoderReranker(corpus)
        self.corpus = corpus

    def search(self, query, top_k=10):
        # Stage 1: Retrieve top 100
        candidates = self.hybrid.retrieve(query, top_k=100)

        # Stage 2: Rerank top candidates
        reranked = []
        for doc_id, _ in candidates:
            score = self.reranker.score(query, doc_id)
            reranked.append((doc_id, score, self.corpus[doc_id]))

        # Sort by reranking score
        reranked.sort(key=lambda x: x[1], reverse=True)

        return reranked[:top_k]


# Example usage
corpus = [
    "BERT is a transformer-based language model for NLP tasks",
    "Transformer architecture uses self-attention mechanisms",
    "GPT models are generative pre-trained transformers",
    "Machine learning models require large labeled datasets",
    "Transfer learning improves model performance with less data",
    "Word embeddings represent words as dense vectors",
    "Attention mechanisms compute weighted combinations of inputs",
    "Neural networks are inspired by biological brains",
    "Deep learning uses multiple layers of abstraction",
    "LSTM and GRU handle sequential data better than vanilla RNNs",
    "Recurrent neural networks process sequences over time",
    "Convolutional networks excel at image classification",
    "Vision transformers apply transformer architecture to images",
    "Natural language processing involves text understanding",
    "Semantic search matches query intent with document meaning",
    "Information retrieval systems rank documents by relevance",
    "Search engines index billions of web pages",
    "Ranking algorithms determine document order in results",
    "Personalization tailors results to individual users",
    "Federated learning trains models without centralizing data"
]

# Run pipeline
pipeline = SearchPipeline(corpus)

# Test query
query = "transformer architecture"
results = pipeline.search(query, top_k=5)

print(f"Query: '{query}'")
print("\nTop 5 Results:")
for rank, (doc_id, score, text) in enumerate(results, 1):
    print(f"{rank}. [Score: {score:.3f}] {text}")

Key Implementation Details

• BM25Retriever: TF-IDF with BM25 weighting formula.
• DenseRetriever: TF-IDF vectors normalized to unit length (cosine similarity proxy).
• HybridRetriever: RRF fusion, k=60, merges rankings from both.
• CrossEncoderReranker: Simple relevance model (term overlap weighted by doc length).
• SearchPipeline: Orchestrates retrieval → reranking in a two-stage design.

Expected Output

Query: 'transformer architecture'

Top 5 Results:
1. [Score: 0.577] Transformer architecture uses self-attention mechanisms
2. [Score: 0.373] BERT is a transformer-based language model for NLP tasks
3. [Score: 0.231] Vision transformers apply transformer architecture to images
4. [Score: 0.162] Attention mechanisms compute weighted combinations of inputs
5. [Score: 0.154] GPT models are generative pre-trained transformers

Extending the Implementation

• Use BERT encodings: Replace TF-IDF with actual BERT embeddings (HuggingFace).
• Add metrics: Compute NDCG@K, MRR, etc. on a labeled test set.
• Batch inference: Rerank 1000 documents in parallel using GPU.
• Production serving: Wrap with FastAPI + Triton for low-latency serving.