acceptodds
Under review as a conference paper at ICLR 2027

Ranking is Not Scoring: From A Permutation Space Perspective

Abstract

Learning-to-rank (LTR) typically learns item scores and sorts items accordingly. However, evaluation metrics assess item permutations rather than score magnitudes. This creates a structural mismatch between optimization and decision spaces: although scores can represent any permutation, producing an optimal ranking depends on whether the information obtained through optimization captures the requirements of the evaluation metric. To characterize this mismatch, we develop a permutation-space framework that represents ranking metrics as linear utilities over permutation distributions and uses utility differences between permutations to connect convex calibration requirements with score-based optimization. Under arbitrary joint distributions on the complete binary relevance space, we establish exact convex calibration dimensions that grow linearly for normalized AUC and binary NDCG with nonconstant discounts, quadratically for average precision (AP), and exponentially for reciprocal rank (RR) and homogeneous cascades with positive parameters. Using the Plackett–Luce (PL) model to connect scores with permutation probabilities, we prove that exact expected gradients recover all AUC/NDCG utility differences at every finite score point, while exact expected gradients and Hessians recover all AP utility differences at uniform and generic points. For RR, the fraction of utility directions observable through derivatives up to any fixed order at a single point tends to zero as the candidate set grows. Nevertheless, incomplete utility information can still support approximately optimal decisions: for RR truncated at a fixed depth , there exist convex reports whose dimension grows polynomially with candidate set size, with full-RR regret bounded by truncated regret plus . Computational examples and simulation experiments support these results, clarifying how evaluation metrics and candidate set size jointly shape representation requirements for exact ranking, information available to local optimization, and opportunities to reduce representation costs through approximation.

Primary area:
learning theory
Keywords:
Learning to Rank, Convex Calibration Dimension, Plackett–Luce Model, Local Identifiability, Ranking Approximation

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 2 reviews, above 85% of the others.
Reviewer_w6zqOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies learning to rank from a permutation-space rather than the traditional score-space perspective. The authors represent ranking metrics as linear utilities over permutation distributions, and use the space spanned by utility differences between permutations to connect Bayes-optimal decisions, convex calibration dimension, and the local derivative information of the Plackett–Luce (PL) expected utility. Under arbitrary joint distributions over the full binary relevance space, the paper gives exact convex calibration dimensions for several metrics: n−1 for normalized AUC and binary NDCG with non-constant discounting, n(n+1)/2−2 for AP, and 2^n−n−1 for RR and homogeneous cascade metrics with positive parameters. For the PL parameterization, the paper proves that exact gradients of AUC/NDCG recover all utility differences at any finite score point; for AP, gradients and Hessians recover all utility differences at uniform points as well as at generic points outside an appropriate algebraic exceptional set; whereas for RR/homogeneous cascades, when derivatives of any fixed order are used at a single point, the proportion of observable utility directions vanishes as the candidate set grows. The paper further constructs distributions whose local observations coincide but whose sets of optimal permutations are disjoint, analyzes the finite stationary points and higher-order flat saddles of the PL objective, and, via truncated RR, gives polynomial-dimensional reports with a guarantee that full-RR regret is bounded by the truncated regret plus 1/(K+1). Enumeration and simulation experiments are used to verify the dimension, recovery, truncation, and local-optimization dynamics conclusions.

Critical strengths
  • The theoretical problem is clearly defined: the paper distinguishes between representing a given permutation by scores and identifying the metric-optimal permutation from data, and provides a unified formalization through the utility-difference space.
  • The exact convex calibration dimensions are a substantial contribution. In particular, the exact quadratic dimension for AP and the exponential dimensions for RR/homogeneous cascades are more complete than mere order-of-magnitude bounds or specific score-and-sort impossibilities.
  • Connecting the utility directions required for convex calibration with the local derivative observation matrix of the PL expected utility is original, and yields a clear stratification across metrics: first order for AUC/NDCG, second order for AP, and no fixed order suffices for RR.
  • Rather than merely stating dimension differences, the paper also provides non-identifiable distribution pairs, decision costs, finite stationary-point structure, flat saddles, and escape-time results, establishing a fairly concrete link between information deficiency and decision/optimization behavior.
  • The RR truncation results provide a constructive approximation path: at a fixed depth, the report dimension and decoding complexity are polynomial in the number of candidates, with a distribution-free regret transfer bound.
  • Assumptions are generally stated clearly — e.g., the full binary outcome space, arbitrary joint distributions, the NDCG discount condition, the parameter range for homogeneous cascades, and exact expected derivatives.
  • The appendix is fairly complete, including proofs of the main theorems, finite-field rank checks, explicit counterexample constructions, derivative formulas, and additional experiments.
Critical weaknesses
  • The strongest exponential-dimension results rely on arbitrary joint distributions over the full binary relevance space. The paper itself notes that under conditionally independent Bernoulli labels, RR and homogeneous cascades can be solved by ranking according to marginal relevance probabilities. A quantitative account of which dependence structures in real data the exponential lower bound actually corresponds to is therefore still missing.
  • The paper juxtaposes convex calibration dimension with the information capacity of finite-order PL derivatives at a single point, but the algorithmic meaning of the two objects is not exactly the same: CCdim allows arbitrary convex surrogates and a fixed decoder, whereas the local recovery results are restricted to the PL map and a single score point. The current narrative can occasionally lead readers to interpret this connection as a more general optimization impossibility.
  • Single-point derivative non-identifiability does not rule out algorithms querying multiple score points or accumulating information along the optimization trajectory. The paper gives no information lower bounds for multi-point or adaptive queries, or for the full iterative process, so the local results for RR cannot be directly generalized to a claim that general training algorithms cannot identify the optimal permutation.
  • The local recovery results assume access to exact expected gradients and Hessians. In practice these quantities come from finite samples or Monte Carlo estimates; in particular, the second-order recovery for AP and the numerical conditioning near the algebraic exceptional set may be poor, yet the paper lacks a singular-value, sample-complexity, or robust-recovery analysis.
Questions for authors
  • Can the logical relationship between CCdim and the rank of single-point PL derivatives be characterized more precisely? Specifically, which results are necessary conditions for general convex calibration methods, and which are merely limitations of the PL parameterization and the single-point local oracle?
  • For RR/homogeneous cascades, if fixed-order derivatives may be observed at multiple distinct score points, what is the minimum number of points needed to recover all utility directions? Could adaptive point selection significantly bypass the gap between the exponential dimension at a single point and polynomial capacity?
  • The paper has shown that under conditionally independent Bernoulli relevance, ranking by marginal probabilities is optimal for RR. Can one characterize the complexity or approximation error as one gradually deviates from the independent model — e.g., under low-order interactions, bounded dependence order, low-rank moment structure, or total-variation neighborhoods?
  • Although the gradient and Hessian of AP at generic points have full column rank, how does the smallest singular value of the corresponding observation matrix scale with n and the score spread? Under finite samples or noisy derivatives, how many samples might be needed for stable recovery?
  • The DK in Theorem 13 is a constructive upper bound. For truncated RR at fixed K, can a matching or non-trivial convex calibration dimension lower bound be given, so as to determine whether the construction is close to optimal?
  • Is the uniform 1/(K+1) regret bound tight? Do there exist distributions that attain or asymptotically attain it? If not, can the tail probability of the first relevant item beyond position K be exploited to obtain a more data-dependent bound?
  • The construction of single-point indistinguishable distributions depends on the observation point and the derivative order. For a fixed distribution, can one prove that information deficiency or significant optimization delay persists along the actual gradient trajectory, rather than merely local non-identifiability at some pre-specified point?
  • Can experiments be added on public LTR datasets or synthetic but scalable relevance-label models, comparing exact/full objectives, different truncation depths, and common PL/listwise surrogates, and reporting candidate sizes, derivative estimation noise, runtime cost, and final metric regret?
  • Please clarify the scope difference between the homogeneous cascade in this paper and the commonly used ERR definition. Can the current exponential-dimension results extend to position- or item-dependent stopping probabilities, graded relevance, and more general cascade models?
Reviewer_Y64POpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies the mismatch between score-based learning and permutation-based evaluation in learning-to-rank. It establishes exact convex calibration dimensions for ranking metrics, showing linear complexity for AUC/NDCG, quadratic for AP, and exponential for RR. It further analyzes how ranking information can be recovered from Plackett–Luce derivatives and proposes truncated RR to reduce representation complexity. The findings are supported by theoretical analysis and small-scale synthetic experiments.

Critical strengths
  • The authors establish exact convex calibration dimensions for several ranking metrics, including AP and RR.
  • The proposed idea characterizes how ranking-relevant information can be recovered from Plackett–Luce gradients and higher-order derivatives.
  • The authors propose the truncated RR with theoretical regret guarantees, reducing representation complexity from exponential to polynomial.
Critical weaknesses
  • The experimental evaluation is restricted to small-scale synthetic settings with at most six items, primarily relying on exact enumeration and numerical analysis. While these experiments support the theoretical claims, they do not establish whether the observed phenomena persist in realistic ranking scenarios. Evaluations on larger candidate sets, real-world learning-to-rank datasets, and comparisons with established ranking methods would strengthen the empirical contribution.
  • Although the theoretical results characterize the information required to optimize different ranking metrics, their implications for practical learning-to-rank algorithms remain unclear. In particular, the Plackett–Luce analysis assumes access to exact expected gradients and higher-order derivatives, whereas practical optimization relies on noisy, finite-sample estimates. The paper does not investigate how these limitations affect optimization or demonstrate whether the proposed insights lead to improved ranking performance.
Questions for authors

Apart from weakness section, here are my further questions.

  • Could the authors extend the empirical evaluation to established learning-to-rank benchmarks, such as MSLR-WEB10K, Yahoo! LTR, or LETOR? Evaluating on realistic datasets with larger candidate sets and comparing against standard LTR baselines would help assess whether the theoretical findings translate into practical ranking performance.

  • How robust are the theoretical findings when gradients and Hessians are estimated from finite samples rather than computed exactly? Could the authors provide empirical evidence or theoretical bounds characterizing the impact of estimation noise on ranking performance?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.