Learning to rank

The three paradigms are: Pointwise (treat each document independently, regress or classify its relevance score), Pairwise (train on document pairs, minimize the number of rank inversions — e.g., RankNet), and Listwise (optimize over the entire ranked list jointly — e.g., ListNet, LambdaRank). Each paradigm makes different assumptions about how to encode the ranking objective into a tractable loss.

DCG@k = sum_{i=1}^{k} (2^rel_i - 1) / log2(i+1); NDCG@k = DCG@k / IDCG@k where IDCG@k is the DCG of the ideal (perfect) ranking. The exponential gain term 2^rel_i - 1 makes it sensitive to graded relevance levels (e.g., 0–4), rewarding highly relevant documents much more than marginally relevant ones, unlike binary-relevance metrics such as MAP.

import numpy as np

def dcg_at_k(rels, k):
    rels = np.array(rels[:k], dtype=float)
    gains = (2**rels - 1) / np.log2(np.arange(2, len(rels)+2))
    return gains.sum()

def ndcg_at_k(rels, ideal_rels, k):
    return dcg_at_k(rels, k) / (dcg_at_k(sorted(ideal_rels, reverse=True), k) + 1e-9)

RankNet models the probability that document i should rank above document j as P(i>j) = σ(s_i − s_j) and minimizes cross-entropy against the target probability P̄(i>j) ∈ {0, 0.5, 1} derived from relevance labels. This converts the ranking problem into binary classification over all ordered document pairs within a query, allowing standard gradient descent to be applied.

import torch, torch.nn.functional as F

def ranknet_loss(s_i, s_j, target):
    # target = 1 if doc_i more relevant, 0.5 if equal, 0 otherwise
    p_pred = torch.sigmoid(s_i - s_j)
    return F.binary_cross_entropy(p_pred, target)

Instead of computing an explicit loss, LambdaRank directly defines the gradient (lambda) for each document pair as the RankNet gradient scaled by |ΔNDCG_{ij}| — the absolute change in NDCG from swapping documents i and j. This implicitly drives the model toward improving NDCG (a non-differentiable metric) without needing a closed-form NDCG loss. The key innovation is incorporating the metric change as a multiplicative weight on pairwise gradients.

# Lambda gradient for doc i (simplified)
# lambda_i = sum_{j: rel_j < rel_i} |delta_NDCG_ij| * d/ds_i log(sigma(s_i - s_j))
# = sum_j |delta_NDCG_ij| * sigma(s_j - s_i)

LambdaMART applies MART (Multiple Additive Regression Trees / gradient boosted trees) using LambdaRank's lambdas as pseudo-residuals. At each iteration, a regression tree is fit to the lambda values; leaf outputs are computed via a Newton step using sum(lambda) / sum(|d_lambda/d_score|) per leaf. This ensemble of trees achieves state-of-the-art LtR performance (e.g., on LETOR/MS-MARCO) by combining the expressive power of GBDT with NDCG-oriented gradient signals.

# In LightGBM (equivalent to LambdaMART)
import lightgbm as lgb

train_data = lgb.Dataset(X_train, label=y_train, group=query_groups_train)
params = {
    'objective': 'lambdarank',
    'metric': 'ndcg',
    'ndcg_eval_at': [1, 3, 5, 10],
    'num_leaves': 64,
    'learning_rate': 0.05,
}
model = lgb.train(params, train_data, num_boost_round=500)

MAP (Mean Average Precision) assumes binary relevance and averages precision at each relevant document's rank. NDCG supports graded relevance via exponential gain (2^rel − 1) and a logarithmic position discount. NDCG is preferred for multi-level relevance (e.g., 0–4 star ratings in web search), while MAP is natural for binary relevance scenarios such as classic IR benchmarks. Both are normalized to [0,1] and averaged over queries.

MRR = (1/|Q|) * Σ_q 1/rank_q, where rank_q is the position of the first relevant document for query q. It is most appropriate for navigational or question-answering tasks where the user needs exactly one correct answer (e.g., 'Capital of France?'), because it rewards only the first hit and completely ignores subsequent relevant documents.

Position bias is the empirically observed tendency for users to click on higher-ranked results regardless of true relevance — a document at rank 1 receives far more clicks than an equally relevant document at rank 5 simply because users are more likely to examine it. Training on raw clicks as positive relevance signals creates a self-reinforcing feedback loop: the initial ranker's biases are amplified, causing the model to overfit to the old ranking rather than true relevance.

IPS corrects position bias by reweighting each click by the inverse of its examination propensity p(examined=1 | rank): Loss = Σ_i (c_i / p_i) * loss(f, i). Under the assumption that clicks occur only on examined, relevant documents, IPS provides an unbiased estimator of the true relevance loss. Propensities are estimated via randomization experiments (e.g., result swaps or intervention harvesting). High-variance estimates at low propensity positions are typically clipped for stability.

def ips_weighted_loss(clicks, propensities, scores, labels, clip=10.0):
    weights = torch.clamp(clicks / propensities, max=clip)  # IPS weights
    per_doc_loss = F.binary_cross_entropy_with_logits(
        scores, labels, reduction='none')
    return (weights * per_doc_loss).mean()

ListNet (Cao et al., 2007) defines a probability over all n! permutations using the Plackett-Luce model and minimizes the KL divergence between the predicted and ground-truth permutation distributions. In practice the top-one probability approximation is used: P(d_i is top-1 | s) = exp(s_i) / Σ_j exp(s_j). The corresponding loss is a cross-entropy between this softmax over predicted scores and the softmax over relevance labels, making it fully differentiable.

def listnet_loss(scores, relevances):
    # scores, relevances: [n_docs] tensors for one query
    p_pred = F.softmax(scores, dim=0)
    p_true = F.softmax(relevances.float(), dim=0)
    return -(p_true * torch.log(p_pred + 1e-9)).sum()

LambdaLoss (Wang et al., 2018) defines a family of losses as weighted negative log-likelihoods of permutation probabilities: L = -Σ_{i,j} w_{ij} * log P(d_i ranks above d_j). By choosing metric-specific weight functions w_{ij}, different algorithms emerge — NDCG weights recover LambdaRank; uniform weights recover RankNet. The framework proves LambdaRank implicitly optimizes an upper bound on expected negative NDCG, providing the first rigorous theoretical basis for the empirically successful lambda trick.

LtR features fall into three categories: (1) Query features — query length, query type, search intent; (2) Document features — PageRank, domain authority, document length, freshness; (3) Query-document features — BM25, TF-IDF cosine similarity, field-specific match scores, historical click-through rate for this query-doc pair. Query-document features are most important as they directly capture relevance, while query and document features provide context.

ERR = Σ_{r=1}^{n} (1/r) * Π_{i=1}^{r-1}(1-R_i) * R_r, where R_i = (2^rel_i − 1)/2^max_rel is the probability the user is satisfied by document i. Unlike NDCG which sums all discounted gains independently, ERR models a cascade — high-relevance top results reduce the probability that lower documents are even examined. This makes ERR more sensitive to the placement of highly satisfying documents at top positions.

Counterfactual LtR learns from historical logged data (query, displayed ranking, clicks) using off-policy corrections like IPS to debias click signals, without any live experimentation. Online LtR (e.g., DBGD) actively deploys exploratory rankings in production and uses interleaving or bandit feedback to learn in real time. Counterfactual approaches are safer (no online risk) but require accurate propensity estimates; online methods adapt faster but carry user experience risk.

BM25 is a fast unsupervised term-frequency model used as first-stage retriever: it efficiently reduces millions of documents to O(100–1000) candidates via an inverted index. These candidates are then re-ranked by an expensive LtR model (LambdaMART, cross-encoder BERT, etc.). BM25's retrieval score is also commonly included as a feature in the re-ranker, providing a strong lexical match signal that complements learned semantic features.

A bi-encoder encodes query and document independently into dense vectors, then ranks by dot product or cosine similarity — enabling fast ANN-based retrieval since document vectors are precomputed. A cross-encoder concatenates query and document and attends jointly over both, yielding much higher accuracy but O(n) inference cost since each candidate must be re-encoded per query. In production: bi-encoders for first-stage retrieval, cross-encoders for re-ranking top-k candidates.

ColBERT (Khattab & Zaharia, 2020) encodes query and document independently into sets of contextual token embeddings (like a bi-encoder), then scores via MaxSim: for each query token, find the maximum dot product with any document token, then sum these per-token maxima. Document token embeddings are precomputed and indexed. This achieves accuracy close to cross-encoders (rich token-level matching) while allowing efficient precomputation, bridging the accuracy-efficiency gap.

# ColBERT MaxSim scoring (simplified)
# Q: [q_len, d_model], D: [d_len, d_model]
def colbert_score(Q, D):
    # Q, D already L2-normalized
    sim = Q @ D.T          # [q_len, d_len]
    return sim.max(dim=1).values.sum()  # sum of per-query-token max

At each query, DBGD: (1) samples a perturbation direction in weight space to produce a candidate ranker; (2) interleaves the current and candidate rankers' results using Team Draft Interleaving; (3) infers which ranker was preferred from user clicks on the merged list; (4) updates the current model toward the candidate if it wins. This exploration-based, gradient-free approach converges to a click-optimal ranker without explicit relevance labels.

Interleaved evaluation (Team Draft / Balanced Interleaving) merges results from Ranker A and Ranker B into a single list and infers preference from which ranker's documents receive more clicks. Because both rankers are compared on identical user interactions (same query, same session), query-level variance is eliminated — interleaving requires roughly 100× fewer queries to detect the same effect size as A/B testing. However, it only compares pairs of rankers and cannot measure absolute metric values.

XGBoost supports `rank:pairwise` (RankNet-style pairwise log-loss), `rank:ndcg` and `rank:map` (LambdaRank-style, weighting pairwise gradients by |ΔNDCG| or |ΔMAP|). Training instances must be grouped by query using the `group` parameter (a list of per-query document counts). The model then forms document pairs only within the same query group during gradient computation. LightGBM's `lambdarank` objective is equivalent but typically faster on large datasets.

import xgboost as xgb

dtrain = xgb.DMatrix(X_train, label=y_train)
dtrain.set_group(query_groups_train)  # e.g. [5, 3, 7, ...] docs per query

params = {
    'objective': 'rank:ndcg',
    'eval_metric': 'ndcg@10',
    'max_depth': 6,
    'learning_rate': 0.1,
}
model = xgb.train(params, dtrain, num_boost_round=300)

Query normalization ensures that the loss contribution is averaged per query rather than per document, preventing high-frequency queries with many candidate documents from dominating parameter updates. It is implemented by dividing the loss or gradient by the number of documents in each query group. In NDCG-based metrics, per-query normalization is also implicit in the IDCG denominator, ensuring scores are in [0,1] regardless of how many relevant documents a query has.

SPLADE (Formal et al., 2021) uses a BERT MLM head to produce sparse, vocabulary-sized vectors for queries and documents, where each dimension represents a term's importance via log-saturation + ReLU: w_t = log(1 + ReLU(z_t)). Retrieval uses standard inverted-index dot product (fast like BM25) while the learned representation provides query/document expansion with semantic vocabulary terms. SPLADE overcomes BM25's vocabulary mismatch and dense retrieval's opacity, achieving competitive accuracy with interpretable sparse vectors.

Kendall's tau = (C − D) / [n(n−1)/2], where C is the number of concordant pairs (both orderings agree) and D is discordant pairs among n items. A value of 1 indicates perfect agreement with ground truth, −1 is perfect inversion, 0 is uncorrelated. In LtR, it measures how well a system's ranking correlates with the ground-truth relevance ordering at the list level, complementing position-weighted metrics like NDCG.

from scipy.stats import kendalltau

system_ranks  = [1, 2, 3, 4, 5]   # positions assigned by system
relevance_order = [2, 1, 4, 3, 5]  # ground-truth relevance order
tau, p_value = kendalltau(system_ranks, relevance_order)
print(f'Kendall tau = {tau:.3f}')

NDCG depends on document ranks (a sorting step), which has zero gradient almost everywhere. ApproxNDCG (Qin et al., 2010) approximates the rank of document i as rank_i ≈ 1 + Σ_{j≠i} σ(α(s_j − s_i)), where α controls sharpness — as α→∞, it converges to the true rank. Plugging this into the NDCG formula yields a fully differentiable objective that can be optimized via standard gradient descent, achieving direct NDCG maximization.

def soft_rank(scores, alpha=10.0):
    # scores: [n_docs] for one query
    diff = scores.unsqueeze(1) - scores.unsqueeze(0)  # [n, n]
    soft_ranks = 1.0 + torch.sigmoid(alpha * diff).sum(dim=1)  # [n]
    return soft_ranks

def approx_ndcg_loss(scores, relevances, alpha=10.0):
    # negate scores so rank 1 goes to highest-scoring doc
    ranks = soft_rank(-scores, alpha)
    gains = (2**relevances - 1) / torch.log2(ranks + 1)
    ideal = (2**relevances.sort(descending=True).values - 1) \
            / torch.log2(torch.arange(2, len(scores)+2).float())
    return 1.0 - gains.sum() / (ideal.sum() + 1e-9)

A two-tower model uses separate neural encoders for users (or queries) and items (or documents), producing dense embeddings matched by dot product. It enables precomputing item embeddings offline and fast ANN retrieval at query time. The fundamental limitation is the dot-product bottleneck: all user-item interaction must be captured in this single inner product, preventing the model from learning complex feature crosses between user and item attributes that a cross-encoder or feature-crossing model (DCN, DeepFM) can represent.

Plackett-Luce defines P(π | s) = Π_{k=1}^{n} exp(s_{π(k)}) / Σ_{j≥k} exp(s_{π(j)}), modeling the sequential process of choosing the top document proportional to its exponentiated score, then choosing the next from the remaining set, and so on. ListNet minimizes KL divergence between the predicted and ground-truth Plackett-Luce top-one distributions. ListMLE maximizes the log-likelihood of the observed relevance-sorted permutation under the Plackett-Luce model. Both are differentiable and directly optimize over the full ranked list.

Click models are probabilistic models of user behavior that disentangle observed clicks into relevance and examination components. The Position-Based Model (PBM) factorizes click probability as P(click) = P(examined | rank) × P(relevant | doc, query). The Cascade Model assumes users scan top-down and click the first relevant result. By fitting these models to click logs, one obtains estimates of per-document attractiveness or relevance that are corrected for position bias, which then serve as cleaner training labels for LtR.

SoftRank (Taylor et al., 2008) treats document ranks as random variables by adding Gaussian noise to scores, then computes expected NDCG by integrating over the resulting rank distribution (expressed via Gaussian CDF differences). This gives a probabilistic, smooth gradient. ApproxNDCG uses a deterministic sigmoid approximation of rank positions. SoftRank produces smoother gradients theoretically but requires O(n^2) Gaussian CDF evaluations, making it computationally heavier than ApproxNDCG.

Diversity-aware ranking reduces redundancy in the result list while maintaining relevance. Maximal Marginal Relevance (MMR) greedily selects the next document maximizing λ·relevance − (1−λ)·max_similarity_to_selected_docs. Determinantal Point Processes (DPPs) model the probability of a result set S as det(L_S), where L is a kernel matrix encoding both relevance and pairwise similarity — high-probability sets contain diverse, high-quality documents. Exact DPP sampling runs in O(n^3) via eigendecomposition of L; approximate diverse-set selection uses greedy MAP inference on det(L_S).

def mmr(query_vec, doc_vecs, relevance_scores, lam=0.5, k=10):
    selected, remaining = [], list(range(len(doc_vecs)))
    for _ in range(k):
        mmr_scores = [
            lam * relevance_scores[i] -
            (1-lam) * (max([doc_vecs[i] @ doc_vecs[j]
                           for j in selected], default=0))
            for i in remaining
        ]
        best = remaining[int(np.argmax(mmr_scores))]
        selected.append(best); remaining.remove(best)
    return selected

Offline evaluation uses held-out human-annotated datasets and computes NDCG, MAP, MRR, ERR — it is fast, reproducible, and safe. Online evaluation deploys the model to real users and measures business metrics (CTR, dwell time, conversion rate) via A/B tests or interleaved evaluation — it captures true user utility but is slower, noisier, and subject to novelty and presentation effects. A common finding is that offline NDCG improvements do not always translate to online metric gains, making online evaluation essential for deployment decisions.

LETOR-style LtR feeds handcrafted features (BM25, TF-IDF, PageRank) into GBDTs. MonoBERT (Nogueira & Cho, 2019) fine-tunes BERT on [CLS] query [SEP] doc [SEP] input with a pointwise cross-entropy loss, learning rich contextual query-document representations end-to-end without manual feature engineering. Because cross-encoder inference is O(n) in candidates, transformers are deployed as re-rankers over top-k GBDT or BM25 candidates, not as first-stage retrievers, preserving retrieval efficiency.

# MonoBERT inference (simplified HuggingFace)
from transformers import AutoTokenizer, AutoModelForSequenceClassification
import torch

tokenizer = AutoTokenizer.from_pretrained('cross-encoder/ms-marco-MiniLM-L-6-v2')
model = AutoModelForSequenceClassification.from_pretrained(
    'cross-encoder/ms-marco-MiniLM-L-6-v2')

def rerank(query, docs):
    pairs = [(query, d) for d in docs]
    inputs = tokenizer(pairs, padding=True, truncation=True,
                       max_length=512, return_tensors='pt')
    with torch.no_grad():
        scores = model(**inputs).logits.squeeze(-1)
    return scores.argsort(descending=True).tolist()

Noisy or inconsistent relevance labels from human annotators cause the model to fit incorrect targets, degrading ranking quality especially for borderline documents. Mitigations include: (1) averaging labels from multiple annotators and using soft (probabilistic) labels; (2) confidence-weighted loss that downweights low-agreement labels; (3) robust loss functions (e.g., Huber-based) less sensitive to outlier grades; (4) using click-based signals to complement or audit annotation quality. Label smoothing also regularizes against overconfident fitting to noisy labels.

RRF (Cormack et al., 2009) combines multiple ranked lists as RRF(d) = Σ_{r∈rankers} 1/(k + rank_r(d)) with k=60. It requires no score normalization and is robust to scale differences across systems (e.g., BM25 scores vs. dense cosine similarities). Weighted score fusion is fragile when score distributions differ across rankers and requires careful calibration. RRF is preferred when combining heterogeneous retrieval systems (sparse + dense) and typically matches or exceeds more complex learned fusion approaches.

from collections import defaultdict

def reciprocal_rank_fusion(ranked_lists, k=60):
    scores = defaultdict(float)
    for ranked_list in ranked_lists:
        for rank, doc_id in enumerate(ranked_list, start=1):
            scores[doc_id] += 1.0 / (k + rank)
    return sorted(scores, key=scores.get, reverse=True)

RLHF for ranking trains a reward model from pairwise human preference judgments — conceptually identical to RankNet's P(A>B) = σ(r_A − r_B) pairwise cross-entropy loss. The key difference: in classical LtR the ranker is optimized directly by gradient descent on this pairwise loss, whereas in RLHF (e.g., for LLM response selection) the policy (generative model) is optimized against the frozen reward model using RL (PPO), adding a KL penalty to prevent reward hacking. RLHF is adopted when the 'ranker' must also be a generator.