Learning-to-rank losses over candidate sets

Overview

In this wiki, "learning-to-rank" names ranking-style training losses over a set of candidate outputs. In decision-focused learning the set is a cache of feasible solutions. In abstractive summarization it is a set of summaries the model has generated.

In decision-focused learning, a model predicts a cost vector ĉ from features. The loss does not differentiate through the solver. It ranks a cache of feasible solutions instead, and asks that the true optimum look cheapest under the predicted costs, by a margin or in probability 2307.13565 §3.1.4. The cache starts from known optima and grows on a fraction of training steps that call the solver 2307.13565 §5.2.

In summarization, BRIO adds a pairwise margin loss to ordinary cross-entropy. The loss orders the model's own candidate summaries by their ROUGE to the reference, and asks that the model's scores follow the same order 2203.16804 §3. See Liu et al., 2022.

Scope: the decision-focused claims come from one survey and benchmark of decision-focused learning 2307.13565. The summarization claims come from one paper 2203.16804. Search-ranking learning-to-rank (click models, retrieval rankers) is not covered, because no card supports it yet.

Not this concept either: LLM-Blender's PairRanker also ranks by pairwise comparisons, but it ranks candidate text answers from an LLM ensemble, and its loss is not computed over feasible solutions 2306.02561 §3.3. See Jiang et al., 2023.

Variants

The first four variants are the decision-focused losses. They are benchmarked in 2307.13565 §5.2. Results are author-reported, and the text gives qualitative rankings only; the regret values are in box plots fig. 5–fig. 11. Card: Mandi et al., 2023.

Listwise

A tempered softmax over the cache gives one distribution from the true costs and another from the predicted costs. The loss is the cross-entropy between them, with temperature τ 2307.13565 §3.1.4. The grid is τ ∈ {0.05, 0.1, 0.5, 1, 2, 5} 2307.13565 tab. 3. The paper reports high variance 2307.13565 §5.2.3.

Pairwise

A hinge on the predicted gap between the optimum and each rival. The loss is zero once the optimum is cheaper by at least a margin Θ [arxiv:2307.13565 §3.1.4]. The grid is Θ ∈ {0.01, 0.05, 0.1, 1, 10, 50} 2307.13565 tab. 3. The paper reports high variance 2307.13565 §5.2.3. On portfolio at degree 16, Pairwise beats SPO 2307.13565 §5.2.1.

Pairwise (diff)

For each rival, the squared difference between the predicted gap and the true gap 2307.13565 §3.1.4. The paper reports lower variance than Pairwise and Listwise 2307.13565 §5.2.3. On energy scheduling it is among the best methods, with FY, SPO, I-MLE and MAP 2307.13565 §5.2.1.

MAP

The largest gap to any rival, weighted by the cost error ĉ − c 2307.13565 §3.1.4. The paper suggests it for large problems: it is cheap, and its regret is close to SPO's 2307.13565 §5.2.3. It is poor at high knapsack capacities 2307.13565 §5.2.1.

Shared cost

The four decision-focused losses are much cheaper to train than SPO, DBB, I-MLE and FY. On energy scheduling those four take about 100 times as long per epoch as the prediction-focused baseline, while the cache losses, run with a 5% solve probability, are much faster 2307.13565 §5.2.2.

Candidate ordering for generation (BRIO)

This is not a solution-set loss. The candidates are summaries the model writes itself. Each training document gets 16 candidates from diverse beam search, generated once before training 2203.16804 §3 app. B. Each candidate is scored by its summed token log-probability, divided by its length raised to a penalty alpha 2203.16804 eq. 9. A pairwise hinge then asks the higher-ROUGE candidate to score above each lower one by a margin that grows with the rank gap 2203.16804 eq. 8. The total loss is cross-entropy on the reference plus gamma times this term 2203.16804 eq. 10. The paper trains two models:

• BRIO-Mul (cross-entropy plus ranking) generates summaries. Author-reported ROUGE-1 on CNN/DailyMail is 47.78, against 44.29 for BART, the model it starts from 2203.16804 tab. 2.
• BRIO-Ctr (ranking term only) is a scorer that picks among candidates. It cannot generate 2203.16804 §3. Its ROUGE-1 on CNN/DailyMail is 47.28 2203.16804 tab. 2.

The paper sets gamma = 100 for CNN/DailyMail, XSum and NYT [arxiv:2203.16804 tab. 13]. ROUGE-1 rises as gamma grows to 100 and falls at 1000 [arxiv:2203.16804 tab. 3]. The offline candidate pass takes about 20 hours per epoch on four RTX 3090 GPUs 2203.16804 app. B. The released code's XSum weighting does not match the paper's table; see the card's Paper vs code section before reproducing XSum.

When to use which

Implementation sketch

The four decision-focused losses share the cache and the cost vectors. Only the final comparison differs. The sketch is in our own words, with one branch per variant.

# Cache-based ranking losses, one branch per variant  [arxiv:2307.13565 §3.1.4]
# cache: (|S|, n) feasible solutions, one per row, including the optimum
# x_star: row index of the true optimum under the true costs c

def cache_loss(c_hat, c, cache, x_star, variant, tau, margin):
    # Cost of every cached solution under predicted and true costs  [§3.1.4]
    cost_hat = cache @ c_hat
    cost_true = cache @ c
    # Gap between the optimum and each rival  [§3.1.4]
    gap_hat = cost_hat[x_star] - cost_hat
    gap_true = cost_true[x_star] - cost_true

    if variant == "listwise":
        # Cross-entropy between softmaxes of true and predicted costs  [§3.1.4]
        p_true = softmax(-cost_true / tau)
        return -mean(p_true * log_softmax(-cost_hat / tau))

    if variant == "pairwise":
        # Hinge: zero once the optimum beats each rival by the margin  [§3.1.4]
        return sum(max(0, margin + gap_hat))

    if variant == "pairwise_diff":
        # Squared difference between predicted and true gaps  [§3.1.4]
        return sum((gap_hat - gap_true) ** 2)

    # MAP: largest rival gap, weighted by the cost error  [§3.1.4]
    return max((cache[x_star] - cache) @ (c_hat - c))

Notes on the released code, which differs from the paper in several places §3.1.4. The pairwise losses compare one representative per distinct true cost rather than every cached solution. The cache-growth coin is tossed per mini-batch, not per instance. Both points, and the loss scale, are in the card's Paper vs code section. Check them before you reproduce the numbers.

The BRIO term scores whole sequences, so it gets its own sketch. It is in our own words, from the paper's equations.

# BRIO multi-task loss for one document  [arxiv:2203.16804 eq. 8] [eq. 10]
# f: scores of the candidates, best-ROUGE first  [eq. 9]
# ref_nll: summed token NLL of the reference summary  [eq. 3]

def brio_loss(ref_nll, f, lam, gamma):
    rank_term = 0
    for i in range(len(f)):
        for j in range(i + 1, len(f)):
            # Higher-ranked candidate i must beat j by a margin that grows
            # with the rank gap j - i  [eq. 8]
            rank_term += max(0, f[j] - f[i] + (j - i) * lam)
    # Cross-entropy keeps the model usable as a generator  [eq. 10]
    return ref_nll + gamma * rank_term

Contradictions

• Warcraft (image-based shortest path). The same paragraph says Listwise is best at sizes 12, 18 and 30, and also that SPO is best at size 30 2307.13565 §5.2.1. Read the figure before citing a winner fig. 7.
• Variants on the same problem. On energy scheduling, Pairwise (diff) and MAP are among the best methods, while Listwise and Pairwise are worse than the prediction-focused baseline 2307.13565 §5.2.1. The paper does not reconcile these; they are reported as they stand.
• Which methods the paper calls "LTR losses". The paper's table lists an "LTR losses" row 2307.13565 tab. 1, and its text refers to "the LTR losses" without listing the members. The benchmark names the four cache losses above. This page treats those four as the family. Verify before citing a result for "the LTR losses".

Papers

• Mandi et al., 2023: survey and benchmark that defines Listwise, Pairwise, Pairwise (diff) and MAP and reports their regret across seven problem sets.
• Liu et al., 2022: BRIO. Pairwise margin loss over 16 generated summaries ordered by ROUGE, added to cross-entropy for abstractive summarization. Two trained variants: a generator and a scorer.
• Jiang et al., 2023: LLM-Blender. Pairwise ranking of LLM answers. Named here only to mark the scope boundary; it is not a solution-set loss.