Retrieval and reranking

BM25 uses exact term matching with TF-IDF-style scoring, making it highly effective when users search with precise technical terms, product IDs, or rare words that may not be well-represented in semantic embedding space. Dense retrieval generalizes better via semantic similarity but can miss exact keyword matches. Hybrid pipelines typically combine both for best results.

Cross-encoders jointly encode the query and document together, enabling full attention between all tokens for highly accurate relevance scoring—but they require O(n) forward passes at query time, making them too slow for million-scale corpora. Bi-encoders encode query and documents independently, enabling pre-computation of document embeddings and fast ANN search, at the cost of some accuracy. The standard production pipeline uses bi-encoder retrieval to produce a top-k candidate set (k=100–500), followed by cross-encoder reranking of those candidates.

HNSW builds a multi-layer proximity graph where higher layers act as 'highway' connections for coarse navigation and lower layers provide fine-grained nearest-neighbor links, giving sub-linear O(log n) query time. It achieves recall above 95% at ef_search=200 and supports online insertions without rebuilding the index—critical for real-time document addition. The main trade-off is high memory usage (e.g., ~3 KB per vector for D=768 float32, plus ~100–200 bytes for graph edges per node).

RRF assigns each document a score of Σ 1/(k + rank_i) across all result lists, where k (typically 60) dampens the influence of top ranks. Documents appearing in multiple lists accumulate higher scores; those in only one list still contribute. RRF is effectively parameter-free beyond k and outperforms linear score combination because it avoids the problem of incomparable score scales between BM25 (unbounded) and cosine similarity ([−1, 1]).

def reciprocal_rank_fusion(
    rankings: list[list[str]], k: int = 60
) -> dict[str, float]:
    scores: dict[str, float] = {}
    for ranking in rankings:
        for rank, doc_id in enumerate(ranking, start=1):
            scores[doc_id] = scores.get(doc_id, 0.0) + 1.0 / (k + rank)
    return dict(sorted(scores.items(), key=lambda x: x[1], reverse=True))

ColBERT encodes query and document into bags of contextualized token embeddings rather than a single pooled vector. The relevance score is Σ_{q_i} max_{d_j}(q_i · d_j): for each query token, find the document token with the highest similarity, then sum across all query tokens. This MaxSim operation preserves token-level interactions, capturing exact term matches and soft alignments that a single [CLS]-pooled vector loses, at the cost of a larger index (one vector per token rather than one per document).

import torch

def maxsim_score(Q: torch.Tensor, D: torch.Tensor) -> torch.Tensor:
    """
    Q: (q_len, dim) — L2-normalized query token embeddings
    D: (d_len, dim) — L2-normalized document token embeddings
    Returns scalar relevance score.
    """
    sim = Q @ D.T                           # (q_len, d_len)
    return sim.max(dim=1).values.sum()      # sum of per-query-token maxima

SPLADE uses a BERT encoder followed by a vocabulary-size projection and log(1 + ReLU(·)) activation to produce sparse vectors in the BERT vocabulary space, where most dimensions are zero. It is trained with FLOPS regularization to enforce sparsity while preserving relevance via contrastive loss. Unlike BM25, SPLADE can activate synonyms and related terms for a concept even when the exact query word is absent—performing implicit query expansion within a sparse framework that remains compatible with inverted indexes.

HyDE addresses the query-document embedding space mismatch: short interrogative queries and long declarative documents occupy different regions of the embedding space. It prompts an LLM to generate a 'hypothetical document' (a plausible answer to the query), embeds that document, and retrieves based on document-space proximity instead of raw query proximity. The primary risk is hallucination propagation: if the LLM generates plausible-but-factually-wrong content, retrieval pivots toward incorrect passages and can mislead the final generation step.

MRL trains a single embedding model such that the first d dimensions of a full D-dim embedding are themselves a high-quality d-dim embedding for any d in a predefined nested set (e.g., 64, 128, 256, 512, 1024). This is achieved by computing the contrastive loss at multiple nested dimensionalities and summing the losses during training. In production, embeddings can be truncated to smaller dimensions for faster ANN search or cheaper storage with graceful quality degradation, reserving full-size embeddings for reranking.

BEIR (Benchmarking IR) evaluates zero-shot generalization of retrieval models across 18 heterogeneous datasets spanning biomedical, legal, financial, news, and QA domains. It revealed that BM25 often outperformed early dense retrieval models (including DPR) on out-of-domain data, demonstrating that learned dense representations did not generalize as well as term-matching methods outside their training distribution. This finding spurred research into more generalizable dense retrievers and hybrid approaches.

NDCG@10 = DCG@10 / IDCG@10, where DCG@10 = Σ_{i=1}^{10} rel_i / log₂(i+1) and IDCG is the DCG of the ideal (perfect) ranking. The log discount penalizes placing relevant documents at lower ranks, reflecting the user assumption that examination probability decreases with rank. Graded relevance labels (0/1/2/3) are supported, making NDCG more nuanced than binary-relevance metrics like MAP or P@k.

import numpy as np

def dcg(rels: list[float]) -> float:
    return sum(r / np.log2(i + 2) for i, r in enumerate(rels))

def ndcg_at_k(retrieved_rels: list[float], k: int = 10) -> float:
    """retrieved_rels: relevance grades in retrieved order."""
    dcg_k  = dcg(retrieved_rels[:k])
    ideal  = dcg(sorted(retrieved_rels, reverse=True)[:k])
    return dcg_k / ideal if ideal > 0 else 0.0

Random negatives (arbitrary documents from the corpus) are easily distinguishable from relevant ones, providing weak gradient signal that leads to poorly discriminative embeddings. Hard negatives—documents topically similar to the query but not actually relevant—force the model to learn fine-grained semantic distinctions, dramatically improving recall on difficult queries. False negative contamination occurs when a mined hard negative is actually a relevant document (just unlabeled), incorrectly penalizing the model; mitigation strategies include cross-encoder filtering (remove candidates scoring above a threshold) and deduplication against known positives.

PQ splits each D-dimensional vector into M subvectors of D/M dimensions, quantizing each subspace independently to one of K centroids (typically K=256). A D=768 float32 vector compressed with M=96 subspaces uses only 96 bytes instead of 3072 bytes—a 32× reduction. Distances are approximated as sums of precomputed subspace distances (asymmetric distance computation), introducing quantization error that lowers recall at fixed nprobe; IVFPQ (inverted file index + PQ) is the standard FAISS configuration for billion-scale search.

MMR addresses result redundancy: when top-k retrieved documents are semantically near-identical, they waste context window space and increase LLM hallucination risk by providing no new information. MMR iteratively selects documents by maximizing λ·sim(q, d_i) − (1−λ)·max_{d_j∈S} sim(d_i, d_j), balancing query relevance against similarity to the already-selected set S. λ=1 is pure relevance; λ=0 is pure diversity; λ∈[0.5, 0.7] is typical for RAG applications.

RAG-Fusion generates 3–5 query reformulations from the original query using an LLM, performs retrieval for each variant, and merges all result lists using Reciprocal Rank Fusion. Documents that rank consistently across multiple phrasings receive higher fused scores, making the final top-k more robust to query ambiguity and vocabulary mismatch. RRF handles score-scale incompatibility across retrieval runs, making it the natural fusion operator without requiring calibration of raw retrieval scores.

Pointwise reranking scores each document independently (O(n) calls, uncalibrated across documents). Pairwise reranking compares document pairs per call—O(n²) or O(n log n) in tournament style—yielding better calibration but high cost. Listwise reranking (e.g., RankGPT) presents k documents in a single LLM call and asks for a re-ordered list; this is most token-efficient at large k because prompt context is shared across all documents. Sliding window implementations (window=20, stride=10) scale listwise reranking to long candidate lists while maintaining coherence.

Standard chunking loses surrounding context (e.g., 'The defendant was found liable' without knowing which case). Contextual Retrieval prepends a short LLM-generated context summary to each chunk before embedding and BM25 indexing, providing chunk-level provenance and disambiguation. Anthropic reported approximately a 49% reduction in retrieval failures when combining contextual embeddings with contextual BM25 (versus standard chunking), rising to approximately 67% when a reranking step is also added—with the main cost being LLM inference over every chunk at index time.

Standard chunking splits text into fixed windows before embedding, losing cross-chunk context. Late chunking embeds the entire document (or a large window) with a long-context model (e.g., jina-embeddings-v2 with 8192-token context), then derives chunk-level embeddings by mean-pooling the token-level outputs for each chunk's token span. This preserves cross-chunk contextual information in the chunk embeddings, improving retrieval for passages that are only interpretable with surrounding text.

Traditional RAG over PDFs requires OCR and layout parsing, which fails on charts, tables, figures, and complex multi-column layouts. ColPali (based on PaliGemma) embeds entire document page images using a vision encoder, producing patch-level embeddings for each visual grid region. At query time, query token embeddings are compared against page patch embeddings via ColBERT-style MaxSim, enabling retrieval over visual page representations without any text extraction—making it effective for slide decks, financial reports, and scanned documents.

InfoNCE for a positive pair (q, d⁺) is: L = −log[exp(sim(q,d⁺)/τ) / Σ_j exp(sim(q,d_j)/τ)], where the denominator sums over the positive plus all in-batch negatives d_j, and τ is a temperature (typically 0.02–0.05). Larger batches provide more negatives, making the task harder and improving representation quality—but GPU memory limits batch size. GradCache (gradient accumulation over micro-batches) and explicit hard negative mining compensate for small batch sizes. Domain fine-tuning on triplets typically yields +5–15 NDCG points on in-domain benchmarks.

import torch
import torch.nn.functional as F

def infonce_loss(
    q_emb: torch.Tensor,    # (B, D)
    pos_emb: torch.Tensor,  # (B, D)
    neg_embs: torch.Tensor, # (B, N, D)
    temperature: float = 0.02,
) -> torch.Tensor:
    # L2-normalise so dot product == cosine similarity
    q   = F.normalize(q_emb,   dim=-1)   # (B, D)
    pos = F.normalize(pos_emb, dim=-1)   # (B, D)
    neg = F.normalize(neg_embs, dim=-1)  # (B, N, D)

    pos_sim = (q * pos).sum(dim=-1, keepdim=True)              # (B, 1)
    neg_sim = torch.bmm(neg, q.unsqueeze(-1)).squeeze(-1)      # (B, N)
    logits  = torch.cat([pos_sim, neg_sim], dim=1) / temperature  # (B, 1+N)
    labels  = torch.zeros(q.size(0), dtype=torch.long, device=q.device)
    return F.cross_entropy(logits, labels)

IVF clusters the vector database into nlist clusters using k-means at index time, assigning each vector to its nearest centroid. At query time, the query is compared to all nlist centroids and full exact search runs only within the nprobe closest clusters. Higher nprobe improves recall (approaching exact search at nprobe=nlist) but increases latency linearly; nprobe ≈ nlist/8 to nlist/4 is a common heuristic for ~95% recall on most datasets.

PRF extracts key terms from the top-k retrieved documents (assuming relevance) and re-retrieves with the augmented query—fast, requires no LLM, works well when initial results are high precision. LLM-based expansion generates semantically related terms, synonyms, or sub-questions using a language model—better for ambiguous or underspecified queries and for crossing vocabulary gaps in out-of-domain retrieval. PRF degrades when initial results are poor (garbage-in, garbage-out); LLM expansion can hallucinate terms that mislead retrieval.

The parent document retriever stores small chunks (e.g., 128 tokens) in the vector index for precise semantic matching but, upon retrieval, returns the larger parent document or chunk (e.g., 512–1024 tokens) as LLM context. Small chunks improve retrieval precision—minimizing noise in the similarity comparison—while large parent contexts give the LLM sufficient surrounding information to answer accurately. It is implemented in LangChain via a docstore mapping chunk_id to parent_id.

A self-query retriever uses an LLM to parse the natural language query into a semantic search string plus structured metadata filters (e.g., year >= 2024, category = 'ML'). The metadata filters are applied as pre-filters or post-filters to the vector store, enabling hard constraints alongside semantic ranking. Standard semantic retrieval can only rank by embedding similarity—it cannot enforce hard constraints—making self-query essential for queries like 'find ML papers from 2024 about transformers.'

MTEB (Massive Text Embedding Benchmark) evaluates embedding models across 8 task types—retrieval, clustering, classification, reranking, STS, summarization, pair classification, and bitext mining—over 56+ datasets in 112 languages. Its breadth covers real-world embedding use cases far beyond retrieval alone, making it the authoritative benchmark for model selection. The HuggingFace MTEB leaderboard allows practitioners to filter by task type, language, and model size to find the best model under their constraints.

RSF normalizes each retriever's scores to [0,1] via min-max normalization, then computes a weighted sum: score = α·dense_norm + (1−α)·sparse_norm. Unlike RRF, which uses only rank positions, RSF preserves score magnitude—if a document has an overwhelmingly high dense similarity, RSF reflects that while RRF treats rank 1 identically regardless of score gap. RSF outperforms RRF when score distributions are well-calibrated and unimodal; RRF is more robust when score scales are miscalibrated or distributions differ greatly between retrievers.

BGE-Reranker (e.g., BAAI/bge-reranker-large) is a cross-encoder that concatenates query and document as '[CLS] query [SEP] document [SEP]', passes through a BERT-style encoder, and applies a linear layer on the [CLS] token to produce a scalar relevance score. Full query-document token interaction at every layer yields higher accuracy than a bi-encoder but requires one forward pass per candidate—O(k) calls for k candidates. A typical pipeline uses the BGE bi-encoder to retrieve top 100 candidates, then BGE-Reranker to rescore and return the top 5–10.

DPR (Karpukhin et al., 2020) trains two separate BERT encoders (query and passage) using contrastive loss, where positives are Wikipedia passages containing the gold answer and negatives include random documents and BM25-retrieved non-answer passages. The key finding was that DPR outperformed BM25 by 9–19 percentage points in top-20 retrieval accuracy on NaturalQuestions and TriviaQA, demonstrating that learned dense representations can surpass term-matching on knowledge-intensive tasks. However, BM25 remained competitive on low-resource and specialized domains, motivating hybrid approaches.

Sentence window retrieval indexes individual sentences as retrieval units (maximizing precision—matching the exact relevant sentence) but at query time expands each matched sentence to its surrounding window (e.g., ±2 sentences) before feeding to the LLM. This provides precise retrieval with richer context than a potentially off-target 512-token fixed chunk. LlamaIndex benchmarks show ~10–20% improvement in faithfulness and answer relevance on document QA tasks compared to fixed-size chunking.

MRR = (1/|Q|) Σ_q 1/rank_q, where rank_q is the rank of the first relevant document for query q. It directly measures how quickly a user finds the first relevant result, making it ideal for single-answer lookup tasks such as question answering or entity search. Its key limitation is that it ignores all relevant documents beyond the first: NDCG, which handles multiple graded-relevance documents, is more appropriate for comprehensive multi-document retrieval evaluation.

Hosted reranking APIs are ideal when you need enterprise-grade multilingual reranking out of the box, have no GPU infrastructure, have loose latency requirements (~200–500 ms), and prefer usage-based pricing without serving overhead. Self-hosted cross-encoders (BGE-Reranker, ms-marco-MiniLM) are preferred when data privacy prohibits external calls, latency must be sub-50 ms, domain fine-tuning is needed, or query volume makes per-call API costs prohibitive—at >5 M reranks/day, self-hosted typically wins on cost.

Standard RAG fails on global or multi-hop queries (e.g., 'What are the main themes across all company reports?') because no single chunk captures corpus-wide patterns. GraphRAG (Microsoft) builds a knowledge graph from the corpus, applies community detection (Leiden algorithm) to find clusters of related entities, and generates LLM summaries for each community. At query time, local search uses entity-linked subgraphs while global search aggregates community summaries—enabling holistic answers that synthesize information across many documents, at the cost of significant LLM-heavy indexing overhead.

Stage 1 (retrieval) uses a fast bi-encoder or BM25 to retrieve top-k candidates (k=100–500) from the full corpus via ANN search, prioritizing recall to ensure relevant documents are in the candidate set. Stage 2 (reranking) uses a slower but more accurate cross-encoder to rescore only the k candidates, prioritizing precision to surface the most relevant 5–10 results. This design achieves high recall × high precision while keeping total latency acceptable—Stage 1 ~10–50 ms, Stage 2 ~100–300 ms for k=100.

E5 (Microsoft) and Instructor (HKU) prepend a task-specific natural language instruction to queries at inference time—e.g., 'Represent this sentence for searching relevant passages: {query}'—allowing a single model to handle retrieval, classification, clustering, and STS by switching the prefix without fine-tuning. Standard sentence-transformers (e.g., all-MiniLM-L6-v2) embed raw text with no instruction, relying on the model to generalize task-agnostically. E5-mistral-7b achieves strong MTEB performance by combining instruction tuning with a large decoder-based backbone (Mistral 7B).

Cosine similarity scores from bi-encoders are not probability-calibrated—a score of 0.7 vs. 0.8 does not translate to a meaningful probability difference, and score distributions vary significantly across models (some cluster near 1.0, others are more spread). This makes fixed absolute thresholds unreliable for relevance filtering across different models or domains. Calibration approaches include Platt scaling (logistic regression mapping raw scores to probabilities), temperature scaling, and using a cross-encoder to recalibrate thresholds on a validation set; in production, percentile-based thresholds are more robust than fixed absolute cutoffs.