Ranking is Not Scoring: From A Permutation Space Perspective

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 $K$, there exist convex reports whose dimension grows polynomially with candidate set size, with full-RR regret bounded by truncated regret plus $1/(K+1)$. 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.