Prefix-Anchored Smoothing for Learning Diverse Rankings from Noisy List-Level Feedback

Many ranking systems are judged on whole lists, not single items. A results page is good when it covers the different things users might have meant, and a playlist is good when it does not repeat itself. These list-level values usually have diminishing returns: a fifth article on the same subtopic adds less than the first. Functions with this property are called submodular. Increasingly, the only supervision available is a noisy score for an entire list, such as a simulated or logged user-satisfaction estimate, or an automated judge. That noise is often persistent: asking again about the same list returns the same wrong number, so repeating the query does nothing. This note proposes a way to learn a ranking model from such feedback. Before any list score is used as a training target, it is denoised by averaging the scores of lists that keep its top items fixed and shuffle or replace only the lower positions.

The idea rests on a structural fact that neither field has used. Take a ranking objective that is submodular and discounted by position. Changes below rank $j$ can move its value by at most a known, shrinking amount. Lists that share a top-$j$ prefix therefore have nearly the same true value, but because they are distinct lists, their persistent noise is independent. Averaging over them removes noise at a bias we can bound and control by choosing $j$. The resulting smoothed values become targets for a listwise loss over a pool of candidate rankings. At inference, rankings come from swap-based local search rather than a one-shot greedy pass.

Core Claim

Let $f: 2^U \to [0,1]$ be a monotone submodular coverage function over candidate items $U$. Let $\pi$ be a ranking, $S_k$ its top-$k$ prefix, and $w_1 \ge w_2 \ge \dots \ge 0$ position weights. The list value is

$$F(\pi) = \sum_{k} w_k \big(f(S_k) - f(S_{k-1})\big).$$

We observe only $\hat F(\pi) = F(\pi) + \epsilon_\pi$, where $\epsilon_\pi$ is fixed per list. Build $m$ neighbors by keeping $\pi$'s top-$j$ prefix and resampling the tail. Then average their observed values to get $\tilde F_j(\pi)$. Two facts follow. The marginal gains after rank $j$ sum to at most $1 - f(S_j)$, and the weights are non-increasing. So the error of the smoothed estimate satisfies

$$\big|\mathbb{E}\,\tilde F_j(\pi) - F(\pi)\big| \le w_{j+1}\,(1 - f(S_j)), \qquad \mathrm{Var}\,\tilde F_j(\pi) \approx \sigma^2 / m,$$

with the variance holding when noise is independent across distinct lists. The bias shrinks as the prefix grows or saturates coverage. The variance shrinks with the number of neighbors.

The claim is that listwise training on these prefix-anchored targets recovers the true ordering of candidate rankings far better than training on raw noisy values. It also does better than smoothing that ignores order, and better than simply flattening the loss. The gain should be largest exactly where Horel and Singer's analysis predicts greedy collapses, at noise levels near or above $1/k$.

Where This Sits in Prior Work

What supplies the method. The denoising step adapts spatial smoothing from noisy submodular maximization. Optimization for Approximate Submodularity averages noisy values over a ball of sets that differ by one element. A Unified Approach to Submodular Maximization Under Noise averages over unions with subsets of a random smoothing set. Both perturb unordered sets. Neither says which perturbations of an ordered list leave its value nearly unchanged. The prefix-anchored neighborhood and the bias bound above are that missing piece.

The inference step borrows from Efficient Submodular Optimization under Noise: Local Search is Robust. That paper shows local search can eject elements chosen because of noise, since it compares whole-set values instead of noisy marginal differences. We apply swap moves to rankings rather than sets.

The training step reuses the pool-based listwise loss of Decision-Focused Learning: Through the Lens of Learning to Rank. That paper trains a predictor so that a downstream solver ranks good solutions above bad ones over a maintained pool, re-solving only 10% of the time.

What motivates the proposal. Mandi et al. evaluate only linear objectives with clean evaluations. Robust Losses for Decision-Focused Learning shows that noisy targets in this setting cause overfitting. Its remedies are averaging over the top-$k$ decisions and over feature-space nearest neighbors, and they are also developed for linear programs. We move to submodular list objectives, and we smooth in solution space using structure those remedies lack.

The combinatorial ranking literature assumes exact evaluations. Ranking with Submodular Valuations gives an optimal greedy for multi-user cover time under exact oracles. Ranking with submodular functions on the fly studies greedy and exchange algorithms in streams, also under exact oracles. Cascading Linear Submodular Bandits learns linear weights on a fixed submodular family online and builds each list greedily, with no way to undo a noisy early pick. All three build lists by irrevocable greedy steps.

What constrains the design. Maximization of Approximately Submodular Functions proves greedy keeps a constant factor only when relative error is below roughly $1/k$. It also proves that under adversarial noise above $n^{-1/2}$, no efficient algorithm keeps a constant factor. So we make no promises under adversarial noise. The bound above requires noise that is independent across distinct lists, and one experiment deliberately breaks that assumption.

On the listwise side, Learning to Rank by Directly Optimizing Full-Order Probabilities and TSPRank model uncertainty and global order. However, they score items as if each item's value does not depend on what else is in the list, and TSPRank's exact solver limits lists to about 50 items. Both are reasons to use a submodular model with local-search inference rather than exact permutation solvers.

Research Program

The model. A neural encoder maps each item's features to non-negative weights over $T$ learned latent topics. The predicted list value $F_\theta(\pi)$ plugs these weights into a probabilistic-coverage submodular function, weighted by position. This generalizes the fixed topic family in CascadeLSB, because the topics are learned rather than given. Rankings are produced by greedy selection under $F_\theta$ followed by first-improvement adjacent and non-adjacent swaps until no swap raises $F_\theta$.

Training. Each query keeps a pool of candidate rankings. With probability 10% per step, the pool is extended by running local search under the current model, following Mandi et al.'s solve schedule. Each pool member receives a smoothed target $\tilde F_j(\pi)$. The prefix length $j$ is chosen per list to minimize an estimate of bias squared plus variance. The bias estimate uses the model's current guess of $f(S_j)$. The variance estimate uses the spread among the $m$ neighbors.

The loss is the listwise softmax cross-entropy between the pool distribution induced by $F_\theta$ and the distribution induced by the smoothed targets. Neighbor evaluations are the dominant cost. The query budget per list is therefore fixed at $m$ and matched across all methods.

Analysis. We will prove the bias–variance statement for general non-increasing weights. We will then analyze the probability that the smoothed ordering of two pool members is inverted, as a function of their true gap, $\sigma$, $m$, and $j$. This yields a sufficient condition under which pool rankings are correctly ordered with high probability. The analysis also examines how the bound degrades when noise has a shared component across lists that share a prefix. That shared component is the correlated regime flagged as open in the noisy submodular literature.

Baselines

The naive reference is a pointwise model. We fit an additive model regressing raw list scores onto sums of item features, then rank by predicted item score. A second naive variant runs Adaptive Residual Updates–style greedy selection on that model. This is what practitioners do when only list scores exist. Beating it shows that interaction modeling matters at all.

The strongest existing method is Mandi et al.'s pool-based listwise loss trained on raw noisy list values, combined with Schutte et al.'s top-$k$ robust target and, separately, their $k$-nearest-neighbor target. This is the only line of work that trains through a combinatorial solver with ranking losses and also addresses noisy targets. It receives the same encoder, the same submodular head, and the same local-search inference. It also gets the same total number of oracle calls, spent on a larger pool rather than on neighbors. Hyperparameters are tuned with an identical budget of trials for every method.

The file contains no reported result for any of these baselines on noisy submodular ranking, on MovieLens 1M, Sogou, or elsewhere. The only nearby figure is Mandi et al.'s listwise regret of 12.38%, versus 28.50% for two-stage MSE, on Shortest Path. That is a clean-evaluation, linear-objective setting, so it cannot serve as a target here. All baseline numbers will therefore be produced in-house.

The online reference is CascadeLSB, run with its known topic family. It indicates what a well-specified parametric bandit reaches, although it answers a different, online question.

Ablations isolate the key ingredient. The first replaces prefix-anchored neighbors with Bhawalkar-style order-free smoothing at equal $m$, meaning random item-set perturbations anywhere in the list. The second fixes $j$ rather than choosing it adaptively. The third replaces local-search inference with plain greedy.

What counts as winning. The proposal wins if true-$F$ ranking quality at test time exceeds every baseline by more than three seed standard deviations for noise at or above $1/k$. It should also remain within noise of the clean-data oracle's quality as noise falls to zero.

Why not just…?

Why not just raise the softmax temperature or label-smooth the listwise loss? This is the most serious threat, because it is a one-line change. Flattening the target distribution reduces confidence, but it does not change which pool ranking the noisy targets put first. Under persistent noise, the targets' ordering is itself wrong. We will measure directly the Kendall's tau between target and true orderings of each pool. Temperature leaves this unchanged, while smoothing should raise it. We will also give temperature its own tuning budget. If it matches our method on true-$F$ test quality, we will report that the structured smoothing is unnecessary.

Why not just use Schutte et al.'s nearest-neighbor or top-$k$ losses? The nearest-neighbor loss averages outcomes over queries with similar features. That helps only when similar queries recur with shared optimal lists. The top-$k$ loss averages over the best $k$ pool members, which are ranked by the same noisy values. Both are included as baselines at matched budget. The Sogou multi-intent setting, where queries rarely repeat, should show whether query-space averaging is enough.

Why not just re-query and average? Under persistent noise, re-querying returns the same value, as Bhawalkar et al. note. When noise is not persistent, temporal averaging is the obvious correct choice and our method should hold no advantage. We include that regime as a control and expect a tie there. Seeing a tie would confirm that the gains come from the mechanism the proposal claims.

Why not just train a pointwise scorer and apply greedy with a diversity penalty? This is the naive baseline above. Two results suggest it falls short. Mandi et al. find that decision-blind two-stage training triples regret on their benchmark. Hiranandani et al. find that decoupling relevance from submodular diversity under position bias gives linear regret. It is included regardless.

Proposed Experiments

Controlled testbeds with a known true objective. On MovieLens 1M, we use genre coverage as topics, following CascadeLSB. On Sogou Web Pages, we use click-derived intent coverage, following Zhang et al. Persistent noise is injected by hashing each permutation to a fixed Gaussian draw at relative levels spanning $0.1/k$ to $3/k$. A correlated variant adds a noise component shared by all lists with the same top-3 prefix. That variant violates our independence assumption, and the bound predicts gains should shrink in proportion to the shared variance.

Metrics are the true $F$ and intent-aware coverage at cutoff 10 on held-out queries. We also report the pool-ordering Kendall's tau defined earlier. The Million Song Dataset serves as a replication.

Decisive checks. The first check is a crossover plot of each method's true $F$ against noise level. The proposal is supported only if its advantage appears near $1/k$ and grows beyond it. The second check compares prefix-anchored with order-free smoothing at equal $m$. If order-free smoothing matches it, the ordered-neighborhood argument is wrong. The third check verifies that the adaptive $j$ tracks the bias bound: chosen prefixes should lengthen as coverage saturates more slowly.

Sanity check on modular ranking. Finally, we run on MQ2008, where the objective is essentially modular NDCG. There the method should reduce to ordinary listwise training and not degrade it. TSPRank reports an NDCG@10 of 0.8884 on MQ2008-list, and we treat that as the level to stay near rather than to beat.