Keeping a Ranking Fresh: Active Comparison Under Drifting Preferences

Many systems keep a ranked list of items by asking people to compare two at a time. Examples include ranking model outputs for preference alignment, tiering players, and ordering thousands of images by an attribute. These systems usually assume the true order never changes, so they sort once and stop. In practice, tastes, norms and item quality drift, and a ranking built last month is partly wrong today. Existing methods for drifting comparisons either work offline on logged data or only track the single best item. None tells you which pair to ask about next when the whole list must stay accurate on a fixed comparison budget per time step.

We propose to treat ranking under drift as maintenance rather than repeated sorting. The algorithm keeps a current estimated order. It spends most of its comparisons on adjacent items whose relative order is both uncertain and stale. It spends a small fixed fraction on random long-range probes that catch items that have jumped far. Each item gets its own forgetting rate, set by how surprising its recent outcomes have been, so stable items keep their history and only moving items shed old evidence. The bet is that real drift is uneven, with a few items moving while most stay put. Under that kind of drift, local repair with per-item forgetting should track the true order at a fraction of the cost of re-sorting, and more accurately than any single global discount.

Core Claim

Assume pairwise outcomes follow a time-varying Bradley–Terry model, in which item $i$ beats item $j$ at time $t$ with probability $\sigma(\theta_i(t)-\theta_j(t))$. Here $\sigma$ is the logistic function and $\theta_i(t)$ is item $i$'s latent score. We measure tracking quality as the time-averaged normalized Kendall distance between the maintained order $\hat\pi_t$ and the true order $\pi_t$:

$$ \mathcal{E}_T=\frac{1}{T}\sum_{t=1}^{T} d_K(\hat\pi_t,\pi_t), $$

where $d_K$ is the fraction of item pairs ordered differently and $T$ is the horizon. Each step allows a budget of $B$ comparisons with $B \ll n$, where $n$ is the number of items.

The claim has two parts. First, when only a fraction of items drift, item-local forgetting plus neighbor-focused sampling achieves lower $\mathcal{E}_T$ at equal budget than three alternatives: periodic re-sorting, globally discounted win counting, and Elo-style online updates. Second, the cost of detecting drift stays linear in $B$ rather than quadratic in $n$, because detection rides on the random probes instead of monitoring every pair.

Relation to Prior Work

Two results from stationary active ranking supply the method. Just Sort It! runs Quicksort directly on noisy comparisons. It shows that inconsistent outcomes cause only local displacements, and on GIFGIF it reduces displacement by 14–23% over random sampling. We reuse the locality insight: if errors stay local, repairs can be local too. Maximum Selection and Ranking under Noisy Comparisons supplies noisy binary-search insertion, which we use to re-place an item once a probe flags it as misplaced. Simple, Robust and Optimal Ranking from Pairwise Comparisons proves that plain win counting is minimax-optimal for top-$k$ under random designs and is far faster than spectral estimation. It is our strongest stationary reference. Its guarantee assumes random comparison designs and fixed scores, and we violate both on purpose.

Three lines of work motivate the drift side and mark the gap. Right Now, Wrong Then (NS-DPO) down-weights old preference pairs by a global factor $\gamma^{T-t-1}$. It concedes two limits: tuning $\gamma$ requires knowing the drift budget in advance, and one discount treats stable and drifting preferences alike. Per-item forgetting is our direct answer to that second limit. However, NS-DPO is passive and trains a policy, not a ranking. Preference-Based Dynamic Ranking Structure Recognition estimates time-varying Bradley–Terry scores with kernel spectral methods and finds tier change points by dynamic programming. It shows that drift is often structured, with tiers that are stable inside and moving at the boundaries. It works offline on fixed data and never chooses queries. Non-Stationary Dueling Bandits does choose queries under piecewise-stationary drift, and its reset rule (BtWR) and change monitors (MDB, DETECT) are the closest active designs. Each targets a single winner, and MDB watches all $O(n^2)$ pairs, which defeats the purpose of a quasi-linear budget. The Borda-criterion extensions (Weighted Borda, Generalized Borda) still select arms rather than maintain a full order. Our setting is full-list tracking with active queries, which none of these address.

Research Program

The algorithm, which we call Repair-and-Probe, maintains three things for each item: a score estimate from a weighted Bradley–Terry fit over its past comparisons, a forgetting rate $\lambda_i$, and the time it was last compared with each current neighbor.

At each step, a fraction $1-\rho$ of the budget goes to adjacent pairs in $\hat\pi_t$. Pairs are chosen with probability proportional to estimated uncertainty times staleness. Uncertainty is the posterior variance of the score gap, and staleness is the time since that pair's order was last checked. The remaining fraction $\rho$ goes to uniformly random pairs. A probe whose outcome strongly contradicts the current order (low predicted probability) raises the surprise statistic of both items involved. Each item's $\lambda_i$ is a monotone function of its recent surprise, so surprised items forget faster. When an item's surprise crosses a threshold, it is removed and re-inserted by noisy binary search, which costs $O(\log n)$ comparisons.

The probe fraction does real work. Adjacent comparisons alone cannot detect an item that has jumped 500 positions; it would bubble only slowly toward its new place. Random probes find such items at rate roughly $\rho B$ times the fraction of pairs they misorder.

The analysis will bound $\mathcal{E}_T$ in two regimes. In smooth drift, each $\theta_i$ moves by at most $v$ per step, so neighbor sampling must outpace the rate at which neighboring orders cross. In jump drift, $m$ items relocate at unknown times, and the binding costs are the probe detection delay and the binary-search repair cost. We also expect a lower bound by reduction to the $\Omega(\sqrt{KMT})$ dueling-bandit result. Whether tracking is possible at $B=O(\log n)$ per step, and how this depends on the fraction of drifting items, is the main theoretical question. We state it as a target, not a result.

Baselines

The naive reference is a static sort: run Multisort-plus-MLE from Just Sort It! once at the start, then keep spending the per-step budget on uniformly random pairs while updating an undiscounted Bradley–Terry fit. It shows how much drift costs a method that ignores it. Its counterpart is an oracle that is told the true change points and restarts there, which bounds what is achievable.

The periodic re-sort baseline restarts Quicksort-based Multisort every $W$ steps using only comparisons from the current window. It is the natural "just retrain" competitor. We tune $W$ by grid search on held-out drift scenarios, using the same number of tuning runs we give our own $\rho$ and threshold.

Discounted Copeland applies the NS-DPO weighting $\gamma^{T-t-1}$ (Right Now, Wrong Then) to win counts from Simple, Robust and Optimal Ranking. We run it with both random and adjacent-pair sampling and tune $\gamma$ on the same grid budget. It is the strongest simple competitor because it combines a minimax-optimal stationary estimator with the field's standard drift fix.

Elo with neighbor matchmaking is an online rating update with a fixed learning rate that pairs items of similar rating. It is not in the file but is the obvious practitioner baseline. It is effectively our method without per-item forgetting and without probes, so it doubles as an ablation.

MDB wrapped around a dueling-bandit learner (Non-Stationary Dueling Bandits) represents principled active change detection. We expect it to be competitive on top-1 accuracy and to pay heavily in comparisons on full-list error.

As an offline reference, we run the kernel spectral estimator of Preference-Based Dynamic Ranking Structure Recognition on the comparisons our method collected, to test whether our estimator is the weak link. That paper reports Kendall $\tau=1.0000$ and perfect grouping in specific offline synthetic settings with $n\le 50$. For active full-list tracking under drift, no reported result was found on Lacuna for any of these baselines.

Two ablations isolate the key ingredients. The first replaces per-item $\lambda_i$ with one tuned global $\gamma$. The second sets $\rho=0$. Our method beats a baseline if it lowers $\mathcal{E}_T$ by a margin larger than the seed-to-seed spread at equal $B$, and if this holds across drift scenarios rather than in one.

Why not just…?

Why not just re-sort on a sliding window? This is the most serious threat in abrupt-change regimes with long quiet stretches, where restarting is nearly free. Online Ranking Prediction in Non-stationary Environments found that periodic batch retraining lags reactive online updates between retraining cycles. Preference-Based Dynamic Ranking Structure Recognition notes the variance-versus-lag trade-off of any fixed window. Re-sorting also throws away the evidence about stable items, which is exactly what per-item forgetting keeps. The partial-drift sweep described below decides this. If re-sorting matches us whenever more than half the items drift, we will report that boundary rather than hide it.

Why not just use a well-tuned global discount, as NS-DPO does? When all items drift at a similar rate, a single $\gamma$ should be near-optimal, and we expect to tie it there. The case for per-item rates rests on uneven drift. The global-$\gamma$ ablation, given the same tuning budget, directly measures whether that unevenness is worth modeling. We also test robustness by tuning $\gamma$ on one drift rate and evaluating on others, since NS-DPO itself notes that the right $\gamma$ depends on an unknown drift budget.

Why not just run Elo with similar-rating matchmaking? Elo already does local, recency-weighted updates, and in smooth drift it may be hard to beat. Its weak points are large jumps, which an item escapes only by small rating steps, and its single learning rate. If the jump-drift experiments show Elo recovering as fast as probe-triggered reinsertion, then the probes add nothing and the contribution narrows to per-item forgetting.

Why not just wrap a change detector like MDB around the sorter? Monitoring all pairs costs $O(n^2)$ comparisons per detection window, according to Non-Stationary Dueling Bandits. At $n=6{,}120$ items that is about 18.7 million pairs, far beyond any per-step budget. DETECT is cheaper but watches only the presumed winner. We will report MDB at small $n$, where it is feasible, to show where the crossover happens.

Proposed Experiments

Because no public dataset offers actively queryable comparisons with known, time-varying ground truth, the core benchmarks are semi-synthetic but anchored in real data. We fit Bradley–Terry scores to the Sushi (100 items) and GIFGIF (6,120 items) comparison data used by Just Sort It! and treat the fitted scores as the starting truth. We then inject three drift types. In smooth drift, a fraction $f$ of items follows Brownian score motion. In jump drift, $m$ items relocate abruptly, mimicking the TV-HH-style mid-stream flips of Right Now, Wrong Then. In tier-boundary drift, whole tiers swap, mimicking the structure found by Preference-Based Dynamic Ranking Structure Recognition. The NBA 2014–2019 data supplies a realistic drift trajectory: we fit dynamic scores with the kernel spectral estimator and use them as a simulator that every method queries actively.

We report time-averaged Kendall distance, top-$k$ recovery at every step, comparisons consumed by detection, and wall-clock time. For the stationary sanity check at $f=0$, our method must not fall below static Multisort's stationary performance. The paper reports a 14–23% displacement gain over random sampling, and we must preserve that ordering.

The decisive checks are three. The first sweeps $f$ from 0.05 to 1 at fixed budget. The claim survives only if Repair-and-Probe beats tuned discounted Copeland and Elo at small $f$, with the advantage shrinking toward a tie as $f$ approaches 1. A flat advantage would suggest a confound; no advantage refutes the idea. The second compares detection delay after jumps across $\rho\in\{0, 0.05, 0.2\}$ to confirm that the probes, not the forgetting, catch large moves. The third scales $n$ from 100 to 6,120 at $B=O(\log n)$ per step to test whether tracking error stays bounded, which is the practical form of the open theoretical question.