Exact Ranking Likelihoods by Integrating Along the Score Axis

When a ranker is trained to get a whole list in the right order, it would be natural to maximize the probability that its noisy scores land in exactly the observed order. Existing methods avoid computing that probability. One family breaks it into a top-to-bottom sequence of "pick the next best item" choices, as in ListMLE, Seq2Slate and ListGR. That choice of direction is arbitrary, and reversing the list changes the loss. A recent alternative bounds the probability from below using auxiliary cut points that must be optimized in an inner loop. This note argues that neither workaround is needed. If each item's score is an independent one-dimensional random variable, the probability of a full order factorizes as a chain of one-dimensional integrals swept along the score axis, not along the list. This is the same trick autoregressive density estimators use to avoid a global normalizer. On a grid the chain costs time linear in list length, and the result is exact up to quadrature error.

The same sweep handles the case that matters most in web search, where many documents share a relevance grade. It gives the exact probability that every grade-0 document scores below every grade-1 document, and so on up the grades, while leaving the order inside each grade free. The current best full-order method loses its optimization guarantee in exactly this tied setting. The proposal is a loss, not a new architecture. It is order-reversal invariant by construction, needs no inner loop, and handles graded labels without heuristics. The experiments ask whether exactness buys anything measurable over the bound it replaces.

Core Claim

Let item $i$ have a latent score $z_i$ with density $p_i$ and cumulative distribution function (CDF, the probability the score is below a value) $F_i$. Both are predicted by a network from the query and the document. Index items in ground-truth order from worst to best. Define $G_1(t)=F_1(t)$ and

$$G_k(t)=\int_{-\infty}^{t} p_k(z)\,G_{k-1}(z)\,dz ,$$

so that $G_k(t)$ is the probability that the first $k$ items are correctly ordered and the $k$-th lies below $t$. The exact full-order probability is then $G_n(\infty)$. Each step is a one-dimensional cumulative integral, computed on an $m$-point grid in log space, for a total cost of $O(nm)$.

For graded labels, partition items into grade groups $S_1,\dots,S_L$ from lowest to highest. Let $H_g(t)$ be the probability that groups $1..g$ are correctly separated and the maximum score in group $g$ is at most $t$. Then

$$H_g(t)=\int_{-\infty}^{t}\prod_{i\in S_g}\big[F_i(t)-F_i(s)\big]\,dH_{g-1}(s),\qquad H_1(t)=\prod_{i\in S_1}F_i(t).$$

The quantity $H_L(\infty)$ is the exact probability of the observed weak order. It costs $O(nm^2)$ per query, which is a few tens of millions of operations even for Istella's roughly 319 documents per query.

Two properties follow directly. First, the objective is the probability of a set of score vectors, so negating every score and reversing the labels leaves it unchanged. Second, the set of correctly ordered score vectors is a convex polyhedral cone, both with and without ties. A convolution of log-concave functions is log-concave, so with Gaussian or logistic noise the log-likelihood is concave in the item means. This holds even under ties, which is precisely where the bound-based method loses its guarantee.

Relation to Prior Work

The closest work, and the one this proposal directly revises, is Learning to Rank by Directly Optimizing Full-Order Probabilities. It targets the same quantity, $\mathbb{P}(z_1\le\dots\le z_n)$ with heteroscedastic Gaussian scores. It replaces that quantity with a product of interval probabilities between cut points, which gives the Full-Order Bound (FOB). The cut points are fitted by an inner gradient-ascent loop called Safe-Region Gradient Ascent (SRGA). For tied grades the paper falls back to an aggregated surrogate that is no longer concave. Its critique of sequential losses supplies this proposal's motivation. The difference is that this proposal integrates out the cut points exactly instead of optimizing over them, so the bilevel loop disappears and ties are handled without aggregation.

The paper also flags that it never models dependent scores $p(z_i\mid z_{<i})$. This proposal deliberately keeps that limitation. An item-indexed autoregressive chain needs an item order, and an item order reintroduces the directional asymmetry the FOB paper criticizes. Here the chain runs over the score axis and over grade groups, and both have a canonical order.

The sequential models play a constraining role: Seq2Slate uses a pointer-network decoder, ListGR generates documents in sequence with position-discounted terms, and ListMLE's Plackett-Luce factorization (surveyed in Learning to Rank) is the original form. All three are autoregressive over list positions, and that is exactly the asymmetry the score-axis sweep avoids.

The method's ingredients come from the density estimation literature. Expressive one-dimensional conditionals are cheap to normalize, as RNADE and the energy-based conditionals of Durkan et al. show. The Neural Inverse Transform Sampler shows that a monotone neural CDF gives exact interval masses $F(t)-F(s)$, which is the only primitive the recursion needs. This proposal reuses that parameterization to test whether non-Gaussian, for example skewed or multimodal, score uncertainty helps ranking.

SoftRank, also from the survey, used Gaussian scores to approximate rank distributions for expected NDCG. The same grid machinery here computes the probability that item $i$ lands at rank $r$ exactly, which gives an exact expected-NDCG term as a secondary objective. This proposal does not claim that idea as new.

Research Program

The work has three parts. The first is building the loss. This means log-space cumulative integration, a clipped and adaptive grid placed around the predicted score range, and a group recursion vectorized over $(s,t)$ grid pairs. The quadrature error should be measured against Monte Carlo ground truth at small $n$ and against analytic cases such as $n=2$ with Gaussians.

The second is plugging the loss into standard scorers. Two scorers are used: a feed-forward per-document network, and a SetRank-style self-attention encoder (SetRank) that predicts each item's distribution from the whole candidate set. Inside each scorer the latent family is varied over Gaussian, logistic, and a NITS-style monotone CDF.

The third is an analysis of when exactness matters. On trained models, the gap between $\log H_L(\infty)$ and FOB's best bound is measured as a function of list length, number of grades, and score variance. That gap predicts where the two losses should diverge.

At inference, documents are ranked by expected rank under the predicted distributions. Ranking by the mean is reported for comparability with FOB.

Baselines

The naive reference is LambdaMART, the standard boosted-tree ranker, tuned with the same budget as the neural models. It anchors the tabular-feature benchmarks. The file reports that it reaches NDCG@5 of 0.46 against Seq2Slate's 0.53 on the synthetic diverse-click Web30K (Seq2Slate), and Kendall's $\tau$ of 0.0071 on NASDAQ (TSPRank). Softmax cross-entropy (ListNet) as implemented in TF-Ranking is the cheap listwise reference, since it consumes graded labels natively. ListMLE with random tie-breaking represents the sequential family.

The strongest competitor is FOB together with its metric-aligned variant LambdaFOB. It optimizes the same target, uses the same heteroscedastic Gaussian scores, and reports the highest Kendall's $\tau$ on MSLR-WEB30K and Istella. However, no reported numeric result was found on Lacuna for FOB's Kendall's $\tau$ or NDCG on MSLR-WEB30K, Istella, or MNIST sorting. FOB will therefore be re-run from its description, with identical scorer networks, features, epochs and hyperparameter-search budget for both losses. Its extra SRGA hyperparameters get their own share of that budget, not an additional one. Beating it means three things: higher Kendall's $\tau$ on Istella and Web30K across five seeds with non-overlapping confidence intervals, matched or better NDCG@10, and higher exact-permutation accuracy on MNIST at $n=32$. A matched result at lower wall-clock and tuning cost would be a weaker but real outcome.

On MQ2008-list, the reference is TSPRank-Global's reported NDCG@10 of 0.8884 (TSPRank).

Two ablations isolate the key ingredient. The first swaps the exact grouped likelihood for FOB's aggregated tie surrogate, holding everything else fixed, to isolate tie handling. The second swaps it for the strict-order likelihood under random tie-breaking, to test whether modeling the weak order matters at all.

Why not just…?

Why not just use FOB, since the bound may already be tight? This is the main threat. At optimal cut points, FOB may be nearly tight in exactly the regimes where it was evaluated. If so, the exact likelihood only removes an inner loop. The gap analysis in the research program measures this directly. If the gap is small and metrics tie on strict-order tasks, the contribution narrows to the tied-grade setting, where FOB's own authors concede the guarantee is lost. The proposal would be reframed around that setting.

Why not just estimate the order probability by Monte Carlo sampling of scores? The probability that 32 noisy scores fall in one specific order is astronomically small. Almost no samples satisfy the event, so the estimator's gradient is essentially zero or extremely high-variance. The quadrature recursion has no such problem. A small-$n$ experiment will show Monte Carlo gradients degrading as $n$ grows while the recursion's do not.

Why not just use softmax cross-entropy, which already handles grades and wins in industry? The TF-Ranking results make it a serious competitor on top-heavy metrics. The FOB paper, however, shows that top-one surrogates give identical gradients for different full-order distributions, and they underperform on Kendall's $\tau$ and permutation accuracy. Including it on all benchmarks settles whether the exact likelihood trades NDCG for $\tau$. If it does, the expected-NDCG term computed from the same grid is the tested remedy.

Why not just add item interactions with self-attention and keep a simple loss? Interactions and the loss are orthogonal choices. The SetRank-style encoder is therefore crossed with every loss, so any gain attributable to the loss must hold within a fixed encoder.

Proposed Experiments

The decisive check is graded relevance on MSLR-WEB30K, Istella and Yahoo. The exact grouped likelihood should beat FOB's aggregated surrogate on Kendall's $\tau$ and stay within noise of LambdaFOB on NDCG@10. The improvement should also grow with the size of the grade-0 group, since that is where aggregation discards the most structure.

The second check is the MNIST four-digit sorting task at $n\in\{3,5,8,16,32\}$, which has no ties. Here exact-permutation accuracy is compared against FOB. A win would show that the bound's slack matters. A tie would mean the strict-order case is already solved and the proposal reduces to the tied-grade setting.

Three diagnostics accompany these. The first is an order-reversal test: negate the scores, flip the labels, and check that the loss is unchanged. Exact invariance is expected, while ListMLE should fail. The second is quadrature error and runtime versus grid size $m$, run against SRGA's inner loop on Istella-length lists. The third is calibration of the predicted rank distributions, checked by comparing predicted and observed rank frequencies on held-out queries. Calibration is the property that the density estimation view uniquely promises.