Learning to rank

The big idea

Retrieval has handed you 300 candidate documents, products or videos for one request. Now you must put them in order, and only the order matters. If the model's score for the best item is 0.71 or 7.1 makes no difference, as long as it is above the rest. And mistakes are not equal: swapping the results at ranks 1 and 2 is a disaster when the user only reads the first one, while swapping ranks 41 and 42 costs nothing because nobody gets that far.

Think of a librarian handing you books for your question. A good librarian puts the one book you need on top; shuffling the bottom of the pile is harmless. Learning to rankTraining a model whose scores are used only to sort a list of items for a query, with a loss built around the quality of that order. (LTR) trains a scoring function with this in mind. There are three families of loss: score each item on its own (pointwiseLearning-to-rank methods that score each item independently, by regression or classification on its relevance label.), learn which of two items should come first (pairwiseLearning-to-rank methods that train on pairs of items from the same query, penalizing pairs in the wrong order.), or judge the whole list at once (listwiseLearning-to-rank methods whose loss is defined on the whole ranked list for a query, such as ListNet or methods tied to NDCG.). Metrics such as NDCG and MRR reward putting the most relevant items at the top, and the best-known practical method, LambdaMART, is a boosted tree model built to push those metrics up.

How it works

Step 1: The data

Ranking data is grouped by query. For each query $q$ you have a list of candidate items, a feature vector $x$ for every (query, item) pair (text match scores, item popularity, freshness, the user's history with this seller) and a relevance label. In web search the labels come from human judges on a graded scale, for example 0 (bad) to 4 (perfect). In recommenders they usually come from behaviour: a purchase is worth more than a click, and a click more than a skip.

The model is a function $f(x)$ that returns one number per item. At serving time you compute $f$ for every candidate and sort. Nothing else about the score is used, which is what makes ranking different from regression.

Step 2: Metrics that care about the top

DCGDiscounted cumulative gain: the sum over ranked positions of each item's gain divided by a discount that grows with the position, so relevant items count more near the top. adds up a gain for each item, discounted by its position. A common form, the one in the Burges overview cited below, uses gain $2^{\text{rel}}-1$ and a log discount:

NDCGNormalized DCG: DCG divided by the DCG of the best possible order of the same items, so 1.0 means a perfect ranking and queries with different numbers of relevant items can be averaged. divides by the DCG of the perfect order, so every query scores between 0 and 1 and queries can be averaged. A worked example with labels in the order your model ranked them, [3, 2, 3, 0, 1, 2]:

• DCG = 7/1 + 3/1.585 + 7/2 + 0 + 1/2.585 + 3/2.807 = 7 + 1.89 + 3.5 + 0 + 0.39 + 1.07 = 13.85.
• The ideal order [3, 3, 2, 2, 1, 0] gives 14.60, so NDCG = 13.85 / 14.60 = 0.949.

The error that cost the most was the label-3 item sitting at rank 3 instead of rank 2.

MRRMean reciprocal rank: for each query, 1 divided by the rank of the first relevant result (0 if none), averaged over queries. is simpler: for each query, find the first relevant result and take 1 over its rank, then average over queries. If three queries have their first relevant result at ranks 1 and 3, and the third has none, MRR = (1 + 1/3 + 0) / 3 = 0.444. It fits tasks with one right answer, such as a question with one correct passage or a navigational search.

Here is the catch. Both metrics depend on the scores only through the sort. Nudge a score a little and the order usually does not change, so the metric does not change: its gradient is zero almost everywhere, and jumps where two items swap. You cannot run gradient descent on NDCG directly. The three families are three ways around that.

Step 3: Pointwise, pairwise, listwise

Pointwise is a regression or classification you already know ( Linear regression intuition , Logistic regression ). Its weakness shows up in the code below: if some queries simply have higher labels than others, a pointwise model spends effort learning that, even though it can never change the order inside a query.

Pairwise: RankNet. For two items of one query with scores $s_i$ and $s_j$, RankNet models the probability that $i$ should rank above $j$ with a sigmoid of the score difference, and trains with cross-entropy against the label order:

Only differences of scores within a query enter the loss, so anything that shifts all items of a query by the same amount drops out. Burges' overview notes a key speed trick: the gradient factors into one number per item, ${\lambda }_i$, the sum of the pushes from all pairs that item is in, so you accumulate those and do one update per query. That took RankNet's training time from close to quadratic in the number of items per query to close to linear.

Listwise: ListNet. Cao and colleagues turned a list of scores into a probability that each item is ranked first, a softmax over the scores, and used the cross-entropy between that distribution and the one implied by the labels. One training example is a whole query's list, not a pair.

Step 4: LambdaRank and LambdaMART

The idea that made LTR practical is to skip writing a loss and write its gradient instead. Pairwise training already produces a push ${\lambda }_{ij}$ on each pair. LambdaRankA learning-to-rank method that multiplies each pair's RankNet gradient by the change in NDCG that swapping the two items would cause. multiplies it by how much NDCG would change if the two items swapped places:

A misordered pair near the top, where the discount is steep, gets a large push. A pair at ranks 41 and 42 gets almost none. The model now spends its effort where the metric is decided.

LambdaMARTThe boosted-tree version of LambdaRank: gradient boosting (MART) where each new regression tree fits the lambda gradients of every item. plugs these lambdas into gradient-boosted trees ( Boosting: AdaBoost to gradient boosting , where MART is another name for gradient boosting). At each round, compute ${\lambda }_i$ for every item of every query from the current scores, fit a regression tree to them, take a Newton step for each leaf, and add the tree. Because a tree's splits are chosen on all the data, LambdaMART can accept a change that hurts a few queries if it helps the total. An ensemble of LambdaMART rankers won Track 1 of the 2010 Yahoo! Learning to Rank Challenge, and it is the lambdarank objective in LightGBM today.

Try it

• At the start, rank 1 holds doc G with label 0 and NDCG@5 is 0.519. Its biggest swap-cost bars are for the label-4 doc at rank 4 (0.347) and the label-3 doc at rank 6 (0.285): those are the pairs LambdaRank pushes hardest. Press Move down once and NDCG@5 rises to 0.624.
• Press Ideal order, select rank 4 (label 2) and press Move down: one misordered pair, and NDCG@5 falls only to 0.996. Press Ideal order again, select rank 1 and press Move down: still one misordered pair, but NDCG@5 falls to 0.880. A pair count treats those two mistakes the same; NDCG does not.
• With the ideal order, set k to 3 and swap ranks 4 and 5. NDCG@3 stays at 1.000: the metric is blind below its cutoff.

Going deeper

Code: pointwise vs RankNet vs LambdaRank

import numpy as np

# Synthetic search logs: 400 queries x 30 candidate documents, 6 features, graded labels 0 to 4.
rng = np.random.default_rng(0)
Q, D, F = 400, 30, 6
X = rng.normal(0, 1, (Q, D, F))
X[:, :, 5] = rng.normal(0, 1, (Q, 1))                 # a query-level feature: same for every doc of a query
topical = X[:, :, 0] + 0.5 * X[:, :, 1]               # separates 0 from 1 among the many weak docs
quality = X[:, :, 2] - 0.5 * X[:, :, 3]               # separates 2 from 4 among the few strong ones
y = np.where(topical > 1.0, 2 + np.clip(np.round(quality), 0, 2), (topical > -0.5) * 1.0)
y = np.clip(y + 0.5 * X[:, :, 5], 0, 4).round()       # some queries simply have higher labels
disc = 1 / np.log2(np.arange(2, D + 2))               # position discount 1 / log2(rank + 1)

def dcg(rel, k=10): return ((2 ** rel[:k] - 1) * disc[:len(rel[:k])]).sum()
def ndcg(s, rel, k=10): return dcg(rel[np.argsort(-s)], k) / max(dcg(np.sort(rel)[::-1], k), 1e-9)
def rr(s, rel):                                       # reciprocal rank of the first doc with label 3 or more
    hit = np.flatnonzero(rel[np.argsort(-s)] >= 3)
    return 1 / (hit[0] + 1) if len(hit) else 0.0

def pairwise(lambdas, epochs=30, lr=0.05):            # queries 0 to 299 train, 300 to 399 test
    w = np.zeros(F)
    for _ in range(epochs):
        for q in rng.permutation(300):
            x, r = X[q], y[q]
            s = x @ w
            i, j = np.nonzero(r[:, None] > r[None, :])   # every pair where doc i should rank above doc j
            rho = 1 / (1 + np.exp(s[i] - s[j]))          # RankNet: how hard to push this pair apart
            if lambdas:                                  # LambdaRank: times |change in NDCG| if i, j swapped
                pos = np.empty(D, int); pos[np.argsort(-s)] = np.arange(D)
                rho = rho * np.abs((2 ** r[i] - 2 ** r[j]) * (disc[pos[i]] - disc[pos[j]]))
            lam = np.zeros(D); np.add.at(lam, i, rho); np.add.at(lam, j, -rho)
            w += lr * lam @ x / max(rho.sum(), 1e-9)     # move scores along the lambdas (normalized per query)
    return w

A = X[:300].reshape(-1, F)                            # pointwise: least squares from features to labels
w_point = np.linalg.lstsq(np.c_[A, np.ones(len(A))], y[:300].ravel(), rcond=None)[0][:F]
ex, ideal = np.array([3, 2, 3, 0, 1, 2.]), np.array([3, 3, 2, 2, 1, 0.])
print(f"labels [3, 2, 3, 0, 1, 2] in ranked order: DCG {dcg(ex):.2f}, ideal {dcg(ideal):.2f}, NDCG {dcg(ex) / dcg(ideal):.3f}")
print(f"random order        NDCG@10 {np.mean([ndcg(rng.normal(size=D), r) for r in y[300:]]):.3f}")
for name, w in [("pointwise (MSE)", w_point), ("pairwise (RankNet)", pairwise(False)), ("LambdaRank", pairwise(True))]:
    S = X[300:] @ w
    print(f"{name:19s} NDCG@10 {np.mean([ndcg(s, r) for s, r in zip(S, y[300:])]):.3f}  "
          f"MRR {np.mean([rr(s, r) for s, r in zip(S, y[300:])]):.3f}  weights {np.round(w / np.abs(w).max(), 2) + 0.0}")

labels [3, 2, 3, 0, 1, 2] in ranked order: DCG 13.85, ideal 14.60, NDCG 0.949
random order        NDCG@10 0.335
pointwise (MSE)     NDCG@10 0.910  MRR 0.593  weights [ 1.    0.49  0.13 -0.06 -0.01  0.62]
pairwise (RankNet)  NDCG@10 0.907  MRR 0.587  weights [ 1.    0.5   0.09 -0.06  0.01  0.  ]
LambdaRank          NDCG@10 0.919  MRR 0.645  weights [ 1.    0.57  0.26 -0.22  0.04  0.  ]

400 synthetic queries with 30 candidates each, 6 features and labels 0 to 4. Two features decide the many weak labels (0 or 1), two others decide which strong documents get 2 and which get 4, and the sixth is a query-level feature, the same for every document in a query, that raises all of that query's labels. Queries 0 to 299 train three linear scorers, and queries 300 to 399 test them.

• Random order gets NDCG@10 of 0.335. All three models get around 0.91 or more.
• Pointwise least squares reaches 0.910 but puts a weight of 0.62 on the query-level feature, the second-largest weight. That feature is useless for ordering documents inside a query.
• RankNet reaches 0.907 and gives the query-level feature a weight of exactly 0: it adds the same amount to both scores of every pair, so it cancels in $s_i-s_j$.
• LambdaRank reaches NDCG@10 of 0.919 and raises MRR to 0.645, against 0.593 for pointwise and 0.587 for RankNet. Weighting pairs by the NDCG change moves weight onto the two features that separate the best documents (0.26 and -0.22 against 0.09 and -0.06 for RankNet), which is what decides the top of the list.

LambdaMART in practice

You rarely hand-write lambdas. In LightGBM the ranker looks like this (a static listing; the course's Python environment does not include LightGBM):

import lightgbm as lgb  # LightGBM 4.x

# Rows are sorted by query; group lists how many rows each query has, e.g. [27, 18, 67, ...]
ranker = lgb.LGBMRanker(objective="lambdarank", n_estimators=500, learning_rate=0.05)
ranker.fit(X_train, y_train, group=train_sizes,
           eval_set=[(X_val, y_val)], eval_group=[val_sizes], eval_at=[5, 10])
scores = ranker.predict(X_test)  # sort each query's items by score

Details from the LightGBM parameter docs worth knowing:

• Labels must be integers. The default label_gain is 0, 1, 3, 7, 15, ..., that is $2^{\text{rel}}-1$, matching the DCG above.
• lambdarank_truncation_level (default 30) limits training to the top results, and is tied to the $k$ in the NDCG@k you care about.
• eval_at defaults to positions 1 to 5. Set it to the positions your page actually shows.

Not every library uses the same NDCG. scikit-learn's ndcg_score sums the labels themselves (a linear gain) rather than $2^{\text{rel}}-1$, so the two give different numbers for the same ranking. Pick one definition and use it everywhere.

Labels from clicks

With behavioural labels, the top position gets more clicks partly because it is the top position. Train on raw clicks and the model learns to copy the old ranking. Systems either randomize a little to measure that position effect, or model it directly; LightGBM, for example, can take each training row's position and fit position-bias factors alongside the ranker.

Trade-offs

Common mistakes

• Evaluating a ranker with accuracy or RMSE. Report NDCG@k or MRR at the k your page actually shows.
• Shuffling rows across queries when splitting data. Split by query, or the same query leaks into train and test.
• Forgetting the group sizes, or passing rows that are not sorted by query, so LightGBM compares documents from different queries.
• Averaging NDCG over queries that have no relevant items at all. Their ideal DCG is 0; decide explicitly whether to drop them or count them as 0.
• Training on raw clicks without handling position bias, so the new model mostly relearns the old one.

Where you will see this

Every search box with more than a page of results runs a learned ranker: web search, shopping search, app stores, job and travel sites. The Yahoo! Learning to Rank Challenge in 2010 was won by an ensemble of LambdaMART models, and boosted rankers with lambda gradients are built into the common libraries: the lambdarank objective in LightGBM, and rank:ndcg, rank:map and rank:pairwise in XGBoost. In recommenders the same ranker sits after retrieval ( Two-tower retrieval and embedding-based retrieval ), and in RAG pipelines a reranker reorders retrieved passages before they reach the model ( Hybrid search and reranking ).

Check yourself

Recap