Learning to rank

Problem

A user types a query and a first-stage retriever (BM25, or a vector index) returns a few hundred candidate documents. For each query-document pair we have features (text match scores, embedding similarity, freshness, click history) and, for training, a graded relevance label from human judges or clicks: 0 = irrelevant up to, say, 3 = perfect. We want a function f(features) → score such that sorting by score puts the most relevant documents first.

The obvious move is regression: predict the label, minimize squared error. But the score is only ever used to sort within one query. Its absolute value doesn't matter, scores from different queries are never compared, and an error at position 1 costs far more than the same error at position 80 that nobody scrolls to. A loss that ignores all three can prefer the worse ranker. Take three documents with labels 2, 1, 0:

Squared error prefers A by a factor of 82; any ranking metric prefers B, which is perfect. Learning to rank (LTR) is the family of methods that optimize the ordering directly.

Intuition

There are three ways to turn "get the order right" into a loss, named by how many documents each loss term looks at:

• Pointwise: one document at a time. Regress the label or classify relevant vs not. Simple and often a decent baseline, but it spends capacity on calibrating values the sort throws away.
• Pairwise: two documents from the same query at a time. For each pair with different labels, push the more relevant one's score above the other's. Scores become relative, which is what sorting needs. RankNet is the classic form: a logistic loss on the score difference.
• Listwise: the whole list at once. Either define a probability distribution over the list and match it to the labels' (ListNet), or optimize a list metric like NDCG.

The difficulty is that list metrics are step functions of the scores: nudging a score changes nothing until two documents swap, and then the metric jumps. Their gradient is zero almost everywhere. The trick behind LambdaRank and LambdaMART is to skip the loss and write down the gradient directly: take RankNet's pairwise gradient and multiply it by how much NDCG would change if the two documents swapped places. Pairs whose swap matters near the top get big gradients; pairs shuffling around at the bottom get almost none. Handing those gradients to gradient-boosted trees gives LambdaMART, which is what XGBoost's default ranking objective rank:ndcg implements.

Mechanics

DCG and NDCG

Discounted cumulative gain scores a ranked list of labels y₁, …, y_n (position 1 at the top) by summing each document's gain times a discount for its position:

DCG@k  = Σ_{i=1..k} gain(y_i) · 1 / log2(i + 1)
gain(y) = 2^y − 1      (exponential gain, XGBoost's default)
        = y            (linear gain, scikit-learn's ndcg_score)
NDCG@k = DCG@k / IDCG@k          IDCG = DCG of the labels sorted best-first

The discount falls fast at first (1, 0.63, 0.5, 0.43, …) then slowly, so the top few positions dominate. Exponential gain makes a label-3 document worth 7 label-1 documents, which matches how much more a "perfect" answer is worth than a marginal one. Dividing by IDCG puts every query on a 0 to 1 scale so queries with many relevant documents don't dominate the average. XGBoost computes the gain as a bit shift (CalcDCGGain), which is why labels are capped at 31, and the discount with 0-based ranks as 1/log2(idx + 2) (CalcDCGDiscount). scikit-learn's _dcg_sample_scores uses the label itself as gain, and by default averages the gains of tied scores (_tie_averaged_dcg) so the metric doesn't depend on how a sort breaks ties.

RankNet: a pairwise logistic loss

For a pair where document h has a higher label than l, model the probability that h should rank above l as σ(s_h − s_l) and minimize its negative log: L = log(1 + exp(−(s_h − s_l))). The gradient with respect to s_h is σ(s_h − s_l) − 1, always negative (raise h), and the opposite for l. It shrinks to 0 as the pair becomes confidently ordered. Each document's total gradient is the sum over every pair it is in.

LambdaRank: scale each pair by |ΔNDCG|

RankNet treats every misordered pair alike. LambdaRank multiplies each pair's gradient by |ΔNDCG_hl|, the change in NDCG from swapping the two documents' positions in the current ranking, and does not define the loss at all:

λ_hl   = (σ(s_h − s_l) − 1) · |ΔNDCG_hl|          added to h's gradient, subtracted from l's
hess_hl = 2 · σ(1 − σ) · |ΔNDCG_hl|                added to both
ΔNDCG_hl = (gain_h − gain_l) · (disc[rank_h] − disc[rank_l]) / IDCG

That is XGBoost's LambdaGrad: equal labels give zero, the metric delta comes from DeltaNDCG, and the gradient and hessian are at lines 132-133. Repulse flips the sign for the lower document. No loss function is written down anywhere: the gradients are the definition.

LambdaMART is LambdaRank's gradients plugged into gradient-boosted regression trees (MART = multiple additive regression trees). Each boosting round computes λ and the hessian for every document in every query, then fits a tree with the usual Newton leaf values −Σg/Σh. The trees see per-document targets like any regression problem; all the ranking knowledge is in how the targets were computed.

What XGBoost adds

• Pair selection. With the default lambdarank_pair_method="topk", every document in the top k (default 32) is paired with every document below it (MakePairs); the alternative "mean" samples lambdarank_num_pair_per_sample pairs per document.
• Score normalization (lambdarank_score_normalization, default on): |Δ| is divided by |s_h − s_l| + 0.01 (lines 124-126), so pairs the model already separates widely push less.
• Gradient normalization (lambdarank_normalization, default on): for top-k the query's gradients are scaled by log2(1 + Σλ)/Σλ, for mean by 1/(pairs per sample) (CalcLambdaForGroup), which keeps queries with many pairs from dominating.
• Other objectives. rank:pairwise is plain RankNet (|Δ| = 1) and rank:map uses ΔMAP (DeltaMAP) for binary labels; all three are registered at lines 662-672.
• Position debiasing. lambdarank_unbiased=True learns how much click labels are biased by the position the document was shown at, and divides it out (Unbiased LambdaMART).

ListNet: a listwise cross-entropy

ListNet turns both the scores and the labels into a probability for each document of being ranked first, via softmax, and minimizes the cross-entropy between them: L = −Σ softmax(y)_i · log softmax(s)_i. It is smooth and cheap (linear in the list length, no pairs), and works naturally with neural rankers trained by backprop. It doesn't target a cutoff like NDCG@10 the way lambdas do.

Worked example

One query, five documents. The labels and the current model scores are:

NDCG by hand

Sorting by score gives the order d3, d2, d1, d5, d4:

NDCG = 5.780 / 9.393 = 0.6153. The best document is stuck at rank 3 behind an irrelevant one. With linear gain (scikit-learn's convention) the same ranking scores 0.6612: the label-3 document matters less, so misplacing it costs less. NDCG@3, which ignores ranks 4 and 5, is 0.5741. The same scores give three different numbers, so always say which gain and cutoff a reported NDCG uses.

The lambdas

Nine of the ten pairs have different labels (d3 and d5 are both 0 and are skipped). For each, ΔNDCG of the swap and the resulting λ, then each document's total:

Both sum to zero over the query: pairwise gradients only move documents relative to each other. The lambdas pour almost everything into the top of the list: d1 gets -0.333 and d3, the irrelevant document at rank 1, gets +0.368, mostly from the one swap worth 0.373 NDCG. d5, irrelevant but already at rank 4, gets only +0.052. RankNet's gradients are larger everywhere and spread out: it pushes d5 down with +1.475, about three quarters as hard as d3 (+2.028), because every misordered pair counts the same to it.

A few Newton steps

Treating the five scores as free parameters and applying the update s ← s − 0.5 · g / h per document (what a boosting round does with one leaf per document) gives:

Both fix the top two within two steps. After that the lambdas stop caring: d3 (label 0) stays just above d4 (label 1) at ranks 3 and 4, a swap worth only 0.0074 NDCG, while the effort goes into widening the margin of the top document. RankNet does reach a perfect order here, because it pushes every misordered pair equally. That is the trade: lambdas concentrate on the positions a user sees, which is the point when only the first page is evaluated, at the cost of caring little about the tail. The listwise ListNet loss for the starting scores is 1.725, against 1.057 if the scores equalled the labels.

Implementation

With XGBoost, a ranker is a regressor plus query ids. Rows must be grouped and sorted by qid; the tutorial sorts them first:

import numpy as np
import xgboost as xgb

# X: [n, n_features], y: graded labels 0..4, qid: query id per row
order = np.argsort(qid, kind="stable")
X, y, qid = X[order], y[order], qid[order]

ranker = xgb.XGBRanker(
    objective="rank:ndcg",              # LambdaMART; "rank:pairwise" is RankNet
    lambdarank_pair_method="topk",      # pair each of the top k with everything below
    lambdarank_num_pair_per_sample=10,  # k: match it to the cutoff you care about
    eval_metric="ndcg@10",
    n_estimators=500, learning_rate=0.05, max_depth=6,
    early_stopping_rounds=50,
)
ranker.fit(X, y, qid=qid, eval_set=[(X_val, y_val)], eval_qid=[qid_val])

scores = ranker.predict(X_test)      # only meaningful for ordering within a query

Evaluating with scikit-learn's ndcg_score needs one row per query (pad or loop), and it uses linear gain, so its number will differ from XGBoost's ndcg@10 on the same predictions. The XGBoost tutorial notes that scikit-learn's metrics don't know about query groups. XGBRanker.score does: it takes a DataFrame with a qid column and returns the model's last evaluation metric.

In a neural ranker (a cross-encoder scoring query-document pairs), the same losses are a few lines over a [queries, docs] score tensor: RankNet is softplus(-(s_i - s_j)) over masked pairs, ListNet is a cross-entropy between softmax(labels) and log_softmax(scores), and a LambdaRank weight is a detached |ΔNDCG| tensor multiplying the RankNet term.

Tradeoffs

• Pointwise vs pairwise vs listwise. Pointwise is easiest and lets you reuse classifiers, but optimizes the wrong thing. Pairwise costs up to O(n²) pairs per query; top-k pairing caps it at about k·n. Listwise matches the metric best but needs whole lists per batch.
• The cutoff k. Set the pair k and the eval cutoff to the number of results users actually see. A small k ignores the tail entirely, as the worked example shows.
• Gain. Exponential gain heavily rewards the best labels; linear gain is gentler. Pick one, and report it with the number.
• Labels. Human judgments are expensive; clicks are cheap but biased toward what was already shown at the top. Unbiased LambdaMART or randomized interleaving corrects for that, at the cost of more modeling.
• Trees vs neural rankers. LambdaMART on hand-built features is still a strong, fast, cheap baseline. Cross-encoders read the text directly and win on semantic matching, but cost a transformer pass per query-document pair, so they rerank only the top few dozen from a cheaper stage.
• Grouping leaks. Splits must keep each query wholly in train or test (see data leakage); a query split across both lets the model memorize it.

Connections

References

• Burges et al. Learning to Rank using Gradient Descent. ICML, 2005. (RankNet.)
• Burges, Ragno and Le. Learning to Rank with Nonsmooth Cost Functions. NeurIPS, 2006. (LambdaRank.)
• Cao, Qin, Liu, Tsai and Li. Learning to Rank: From Pairwise Approach to Listwise Approach. ICML, 2007. (ListNet.)
• Burges. From RankNet to LambdaRank to LambdaMART: An Overview. Microsoft Research Technical Report MSR-TR-2010-82, 2010.
• Järvelin and Kekäläinen. Cumulated Gain-Based Evaluation of IR Techniques. ACM TOIS, 2002. (DCG and NDCG.)
• Hu, Wang, Peng and Li. Unbiased LambdaMART: An Unbiased Pairwise Learning-to-Rank Algorithm. WWW, 2019.
• XGBoost v3.4.2: lambdarank_obj.h, CalcLambdaForGroup, ranking_utils.h, learning-to-rank tutorial.
• scikit-learn 1.9.1: dcg_score, ndcg_score.