Learning to Rank by Directly Optimizing Full-Order Probabilities

Learning to rank can be cast as a probabilistic modeling problem over permutations, where the goal is to estimate the likelihood of an observed total ordering of items. This formulation naturally involves full-order probabilities of the form $\mathbb{P}(z_1 \leq \cdots \leq z_n)$, whose exact computation and optimization are intractable due to the factorial growth of the permutation space with respect to the list size. In this work, we introduce the *Full-Order Bound* (FOB), a tractable lower bound on the probability of an observed ordering, constructed from a subset of ordering constraints that factorizes across items while preserving full-order structure and order-reversal invariance. Under log-concave latent densities, the bound induces a convex inner tightening problem over latent cut points, which we solve efficiently during training using a *safe-region gradient ascent* (SRGA) procedure. Experiments on synthetic ranking tasks and large-scale learning-to-rank benchmarks show that FOB improves full-list ordering metrics and remains competitive on NDCG, while an optional metric-aligned variant recovers NDCG gains. Our code is available at https://github.com/tyxaaron/FOB.

Many everyday systems must put things in a sensible order: search engines rank web pages, online stores arrange products, and apps line up videos or songs by how well they match your interests. Teaching a computer to produce a good ordering is hard, in part because the number of ways to order even a short list is astronomically large, so the most natural way to score "how good is this ordering" cannot be computed directly. To cope, existing methods usually optimize simpler stand-in goals, such as only comparing items two at a time. These shortcuts are fast but can pull the system away from the ordering we actually care about. We propose a method that stays much closer to the true goal while remaining fast enough for practical use. It provides a reliable, easy-to-optimize estimate of how good a complete ordering is, treats forward and backward orderings consistently, and comes with an efficient training procedure. Across controlled tests and large real-world ranking benchmarks, it produces consistently better orderings than widely used alternatives, with the advantage growing as the lists get longer.