Item features can sharply cut the number of comparisons needed to rank many items. Product specs, text embeddings or player statistics let a model learn how attributes map to quality and then rank items nobody has compared. The ranking methods that achieve this still have to output a complete order. In the sparse regimes where features help most, many of the pairs they order are guesses: two items that sit close in feature space, or an item never compared directly and scored only by extrapolation. Selective prediction (models that may abstain, and that guarantee a bound on error over the cases they do answer) handles this problem for classifiers. It has not been built for rankers learned from few comparisons.
We propose a feature-based ranker that ranks a pair of items only when it can certify the order, and stays silent otherwise. Its output is a partial order with a guaranteed bound on the pairwise error rate. The core idea is a per-pair confidence score: the estimated utility gap between two items, divided by its estimated standard error. That standard error splits into two parts. One reflects uncertainty about the feature weights in the direction separating the two items. The other reflects uncertainty about each item's idiosyncratic residual, which depends on how often that item was compared. A threshold on this score is then calibrated, with a finite-sample guarantee, on held-out comparisons chosen so that they are statistically independent. We expect this to give much higher coverage at a fixed error budget than abstention rules based on feature distance or raw score gap, precisely when comparisons are scarce. The two-part decomposition also says whether an abstained pair would be resolved by more comparisons or only by better features.
Core Claim
Consider the hybrid utility model of Rank Aggregation and Prediction with Item Features (RABF). It gives item $i$ a score $s_i = w^\top x_i + r_i$, where $x_i \in \mathbb{R}^d$ are the item's features, $w$ is a shared weight vector and $r_i$ is an item-specific residual. Fit it with a penalized logistic pairwise loss and take a Laplace approximation, meaning a Gaussian fitted at the optimum whose covariance $C$ is the inverse Hessian of the penalized loss over $(w, r)$. For a pair $(i,j)$, let $a_{ij} = (x_i - x_j,\; e_i - e_j)$, where $e_i$ is the indicator vector for item $i$. The confidence score is
$$ z_{ij} = \frac{|\hat s_i - \hat s_j|}{\sqrt{a_{ij}^\top C\, a_{ij}}}, $$
and the pair is ranked only if $z_{ij} \ge \theta$. The denominator expands into three terms. The first is a feature term, the uncertainty of $w$ along $x_i - x_j$. The second is a residual term, which is large for rarely compared items. The third is a cross term.
The threshold $\theta$ is chosen with the Selection-with-Guaranteed-Risk procedure of Selective Classification for Deep Neural Networks. That procedure inverts a binomial tail bound on held-out errors so that the selective risk is at most $r^*$ with probability at least $1-\delta$.
The binomial bound needs independent errors, and ranking errors are not independent: pairs that share an item share that item's error. We restore independence by calibrating on a matching over held-out items. In a matching, every calibration pair uses two items that appear in no other calibration pair and in no training comparison. Given the trained model, the errors on those pairs are then independent. The guarantee therefore holds exactly for pairs drawn the same way. How well it carries over to arbitrary test pairs is something we measure, not assume.
Because accepted relations always agree with the order of the point scores, the accepted pairs can never form a cycle. The output is a valid partial order.
The claim has three parts. First, at matched misranking risk, this score achieves higher pairwise coverage than thresholds on feature distance or raw score gap, with the advantage growing as comparisons get sparser. Second, the guarantee holds empirically even on non-matching test pairs. Third, abstentions attributed to the residual term fall when more comparisons are added, while those attributed to the feature term largely do not.
Where This Sits
The work is motivated by three results that each stop short of this question.
Ranking with Abstention proves the need for abstention. For smooth hypothesis classes, items close in feature space get nearly equal scores, so surrogate-loss ranking cannot be consistent unless the model may abstain. Its rule abstains when the feature distance is below a hand-tuned $\gamma$. That rule has no risk guarantee, ignores how much comparison data each item has, and comes with no sample-complexity analysis. We treat its rule as a baseline, not as our method.
Selective Preference Aggregation outputs tiered partial orders that abstain on contested pairs. It is feature-free, and its authors note that under sparse data it collapses nearly everything into one tier. Features are the obvious remedy, and that remedy has not been tried.
Transductive Conformal Inference for Ranking gives distribution-free rank intervals for a fixed trained ranker. It does not turn them into a rank-or-abstain decision, and it does not engage with how training data is acquired.
The theory of sublinear feature-based ranking constrains how ambitious we should be. Inductive Pairwise Ranking proves that $\Omega(\log n)$ comparisons suffice under incoherence assumptions, and recovers good rankings at 10% pair sampling. A Graph Theoretic Approach for Preference Learning with Feature Information gets a minimax $\mathcal{O}(\alpha\log\alpha)$ rate when features lie in the span of an independent set of size $\alpha$. Both rest on structural assumptions that real features break. Our method is meant to degrade gracefully when they fail: when features are poor, the residual term should dominate and the ranker should abstain more, not misrank more.
Bayesian Analysis of Rank Data with Covariates and Heterogeneous Rankers already provides posterior credible intervals with covariates. It is the principled but expensive reference for our Gaussian approximation. It is not a competitor on large datasets, because its Gibbs sampler scales poorly.
Research Program
The first component is the estimator. We fit RABF with logistic loss, choosing the two penalties by marginal likelihood under the Laplace approximation instead of grid search. This addresses the hand-tuning that RABF leaves open. We compute $C$ blockwise. The residual block is sparse, with one entry per item plus comparison-graph couplings, and the feature block is $d \times d$. Exploiting this, $a_{ij}^\top C a_{ij}$ costs about $O(d^2)$ per pair after a one-time factorization. That makes scoring all $\binom{n}{2}$ pairs feasible for thousands of items, and lets us subsample pairs for larger galleries.
The second component is calibration. We hold out a random set of items and collect or simulate one comparison per matched pair among them. We apply the SGR bound at chosen $(r^*, \delta)$ and report the guarantee on matched pairs. Separately, we measure empirical violation on all pairs, both among held-out items and between held-out and training items.
The third component is diagnosis and acquisition. For each abstained pair, we record the share of the variance coming from the residual term. A small extension then requests new comparisons only for abstained pairs dominated by residual variance. We test whether this raises certified coverage faster per comparison than uniform sampling. The IPR analysis suggests uniform sampling over distinct pairs is already efficient, which makes it a fair and strong reference.
A modest theoretical piece accompanies this. Under the linear-Gaussian model, we bound the expected number of comparisons needed for a fixed fraction of pairs, those whose true gap exceeds a margin, to be certified. The bound is in terms of $d$ and the fraction of items left uncompared. This mirrors the abstention-cost analysis that Ranking with Abstention leaves open.
Baselines
The naive reference is RABF forced to rank every pair at full coverage. Its misranking rate is the error that abstention must improve on at any coverage. Comparison-only Bradley–Terry provides a second floor, showing what features buy.
The safety-zone baseline follows Ranking with Abstention. It uses the same fitted RABF but abstains when $\|x_i - x_j\|$ falls below $\gamma$, with $\gamma$ calibrated by the same SGR procedure, so the only difference is the score. On CIFAR-10 label-ordered pairs with ResNet-34, that paper reports total loss of 8.25% at $c=0.1$, $\gamma=0.7$, versus 8.33% at $\gamma=0$. We reproduce this setting so our numbers are directly comparable. Beating it means lower total abstention-cost loss at the same $c$ there, and higher coverage at matched selective risk on the preference datasets.
The strongest competitor is the margin baseline. It thresholds $|\hat s_i - \hat s_j|$ on the same model, with SGR calibration. It differs from our method only in the denominator, so it is the ablation that isolates the key ingredient. We also run feature-term-only and residual-term-only versions of the denominator, which tests whether the decomposition is needed or one term carries the effect. For selective classification, SGR reports 1% error at 78% coverage on CIFAR-10. No reported result was found on Lacuna for a margin-thresholded feature ranker on Sushi, Car, Forbes 2000 or NBA data, so we will establish these numbers ourselves under identical folds, features and tuning budgets.
On data-rich voting benchmarks, SPA is the reference. There it achieved 28.2% label error versus 37.8% for majority vote on DICES. We compare SPA and our method on the coverage of asserted pairs as comparisons are progressively deleted, with tiers derived from our partial order.
BARC posterior order probabilities, thresholded the same way, serve as the gold-standard uncertainty on the small NFL quarterback and Sushi data. Matching BARC's risk–coverage curve at a fraction of the runtime counts as success. Beating BARC is not required.
All methods share the training comparisons, the features and the calibration sets. Each gets the same budget of 20 hyperparameter configurations, selected on a validation split disjoint from calibration.
Why not just…?
Why not just abstain on pairs that are close in feature space? This is the rule from Ranking with Abstention, and its own CIFAR-10 numbers show a small gain (8.33% to 8.25%). Feature distance cannot tell apart two well-compared items whose residuals pin down their order and two items never compared. In sparse data, that difference is the main source of error. The safety-zone baseline under equal calibration tests this directly. If it matches our coverage, our denominator adds nothing.
Why not just threshold the score gap? This is the real threat. When every item has roughly the same number of comparisons, the standard error is nearly constant across pairs, and the margin rule should match ours. Our hypothesis concerns heterogeneous sparsity: items with zero to few comparisons alongside heavily compared ones. We will vary this heterogeneity on synthetic data at fixed total comparisons. If the margin rule ties us even at high heterogeneity, we will report that the simple rule suffices and narrow the contribution to the guarantee and the diagnostic.
Why not just use BARC's posterior? It is more principled, and on small data it may be better calibrated. Its sampler, however, does not scale to the New Yorker Caption Contest data (2.2M captions) or to frequent refitting during acquisition. The comparison on NFL and Sushi quantifies what the approximation costs.
Why not just run SPA, or conformal rank intervals, and abstain where tiers or intervals overlap? SPA cannot place uncompared items at all, and it collapses under sparsity. Conformal intervals come with a coverage guarantee on ranks, not on pairwise decisions, and require Monte Carlo envelopes. We include interval-overlap abstention on Yummly-10k as a further baseline. If it dominates there, that points to pairing our score with transductive calibration.
Proposed Experiments and Decisive Checks
The datasets are the Sushi and Car preference data with item features, Forbes 2000 with financial covariates, NBA matchups with injected feature noise, NFL quarterbacks, and CIFAR-10 label-ordered pairs. For scale, we use the New Yorker Caption Contest data, deriving pairwise outcomes from crowd ratings and using text embeddings as features. We also use synthetic IPR-style and f-BTL-style generators, where we can vary features (informative to uninformative), dimension, and comparison budget from far below $n$ to $n\log n$.
The ground truth is the true utility order in synthetic data, the label order in CIFAR-10, and an order aggregated from the full comparison data in Sushi, Forbes and NYCC, against which subsampled training is scored.
The metrics are coverage of all pairs at selective misranking risk $r^*$, area under the risk–coverage curve, and the violation rate of the $(r^*, \delta)$ guarantee over 100 random splits. Violations are reported separately for matched pairs and for arbitrary test pairs, and for pairs involving never-compared items.
Three checks decide the claim. First, our score must beat the margin ablation on coverage at fixed risk under heterogeneous sparsity. Second, the guarantee's violation rate on arbitrary pairs must stay near $\delta$. If it does not, the matching-based calibration is insufficient and the guarantee has to be restated. Third, as feature noise grows on NBA data, coverage must fall smoothly while risk stays at or below $r^*$. That would show the ranker abstains instead of failing the way Rank-SVM does in the RABF experiments. We also measure certified coverage per added comparison, residual-targeted versus uniform acquisition, as the test of whether the decomposition is useful beyond diagnosis.
References
- Rank Aggregation and Prediction with Item Features
- Selective Classification for Deep Neural Networks
- Ranking with Abstention
- Selective Preference Aggregation
- Transductive Conformal Inference for Full Ranking
- Inductive Pairwise Ranking: Going Beyond the n log(n) Barrier
- A Graph Theoretic Approach for Preference Learning with Feature Information
- Bayesian Analysis of Rank Data with Covariates and Heterogeneous Rankers