Stale Bridges: Comparison Graph Topology Under Preference Drift

When people compare things two at a time, which of two responses is better or which of two teams won, we can recover a hidden score for every item only if the comparisons link all items together. How precisely we recover those scores depends on how well they are linked. When preferences also change over time, the usual remedy is to down-weight old comparisons. That remedy has a hidden cost. Old comparisons are often the only links between groups of items that are rarely compared directly: two sports conferences, two topic clusters of prompts. Discounting them by age alone quietly cuts the graph apart, and the scores across groups become noise. This note proposes to measure that cost exactly, predict it per pair of items from the graph, and spend a limited budget of fresh comparisons on the links whose staleness hurts most.

The central object is simple. Picture each past comparison as an electrical resistor whose resistance grows with its age. The error in comparing any two items today is then roughly the effective resistance between them in this age-inflated network. Effective resistance means how hard it is to push current from one node to the other through all available paths. This single quantity explains when recency weighting helps, when it fails, and which new comparison to ask for next.

Core Claim

We claim that under drift, the precision of a current score difference $w_i(T)-w_j(T)$ is governed by the effective resistance of a time-discounted comparison graph. In that graph, each comparison $k$ on edge $e$, made at age $a_k$, contributes conductance

$$c_e(T) = \sum_{k \in e} \frac{1}{v_k + \sigma^2 a_k},$$

where $v_k$ is that comparison's outcome noise (for the Bradley-Terry model, the inverse of $p(1-p)$ at the current scores) and $\sigma^2$ is the drift variance per unit time. This is a first-order approximation. It treats each old comparison as a noisy measurement of today's difference and ignores the correlation between drift increments shared across comparisons. We will test it rather than assume it.

The approximation makes three falsifiable predictions. First, on well-mixed comparison graphs, any reasonable age discount is close to optimal. Second, on clustered graphs joined by a few bridges, age-only discounting inflates cross-cluster error by a factor tied to the bridges' resistance, while within-cluster error stays fine. Third, a bridge refreshed at rate $r$ settles at a tracking variance of about $\sqrt{\sigma^2 v / r}$. That form comes from the steady state of the scalar Kalman filter recursion for a random walk observed sparsely. So the comparison budget a bridge needs grows linearly with drift speed and with the inverse square of the error we will tolerate.

These predictions turn the "topological blindspot" of Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift into something measurable. That paper (NS-DPO) weights preference losses by $\gamma^{T-t}$ regardless of graph structure.

Relation to Prior Work

Static theory motivates the resistance view. Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence ties error to the spectral gap of the comparison graph's Laplacian, the matrix summarizing which items are compared and how often. Graph Resistance and Learning from Pairwise Comparisons tightens this with effective resistance, which matters precisely in bridge-like graphs where a single bottleneck makes the spectral gap pessimistic. $\ell_{\infty}$-Bounds of the MLE in the BTL Model under General Comparison Graphs localizes error to each item's neighborhood. All three assume fixed scores. We keep their resistance machinery and add age as a resistance term.

Three papers already cross into time, and each leaves a specific gap. Detecting Abrupt Changes in Sequential Pairwise Comparison Data shows that detectable jump size depends on the spectral gap. It works only offline, assumes step changes, and treats the comparison schedule as given. Nonparametric Estimation in the Dynamic Bradley-Terry Model kernel-smooths comparisons and requires the smoothed graph to be connected at every time. That requirement is an assumption on the data, with one bandwidth shared by all pairs and a non-causal window. NS-DPO is causal and scalable but ignores topology entirely. Our proposal differs from all three in two ways: it predicts per-pair error under gradual drift from the discounted graph, and it chooses which comparisons to collect.

On the active side, three methods supply techniques we reuse. Enhanced statistical rankings via targeted data collection adds edges across the most separated parts of the graph to raise the spectral gap. Hybrid-MST guarantees connected batches using a spanning tree. Experimental Design under the Bradley-Terry Model gives greedy submodular selection. All three assume stationary scores, and the greedy spectral and D-optimal variants cost cubic time per step. Active Reward Learning from Online Preferences queries online but chooses each query in isolation, with no regard for the graph. At language-model scale, What Does Preference Learning Recover from Pairwise Comparison Data? defines a neural "connectivity degree" generalizing the spectral gap. We borrow it to define clusters among prompts.

Research Program

The work has three parts.

The first is analysis. We will derive the age-inflated resistance bound for Bradley-Terry scores following a Gaussian random walk, quantify its gap to the exact Kalman posterior variance, and prove the bridge-refresh rate result for barbell and clustered graphs. We will also connect the bound to the unknown-variation-budget problem NS-DPO raises. Because $\sigma^2$ enters the conductances directly, it can be estimated online from prediction residuals on frequently compared within-cluster edges. Those residuals then set the effective discount for sparse bridges, which removes the need to tune a single global $\gamma$.

The second part is the estimator. We will not invent a new one. For item-level problems we use a dynamic Bradley-Terry state-space filter: a Kalman filter with a Laplace approximation. Its posterior precision is exactly the discounted Laplacian above plus the drift term. This choice is deliberate, as the skeptic section explains.

The third part, and the core contribution, is the query policy. At each round it asks for the comparison that most reduces a chosen loss. For top-$K$ selection the loss is the maximum resistance among pairs near the selection boundary. For global ranking it is the sum of resistances. The policy uses cheap estimates: random-projection sketches of effective resistance and warm-started Laplacian solves. These cost roughly linear time in the number of edges, rather than the cubic per-candidate cost of exact D-optimal or spectral-gap greedy selection.

Baselines

The naive reference is uniform random pair sampling with a static Bradley-Terry fit on all data. We also run its causal recency version: a sliding window, and NS-DPO-style exponential discounting with $\gamma$ tuned on held-out future comparisons, giving each method the same tuning budget. Beating this reference means lower current-time error on cross-cluster pairs at equal comparison counts.

The strongest passive competitor is the dynamic Bradley-Terry Kalman filter with random queries. It is the right Bayesian tracker under Gaussian drift and already encodes topology implicitly. We give it the same drift estimate as our method. Kernel smoothing as in Bong et al. is run causally, using one-sided kernels with bandwidth tuned to the same budget.

The strongest active competitor is the same filter paired with greedy D-optimal selection from Experimental Design under the Bradley-Terry Model, computed exactly. It also competes with the Fiedler-vector heuristic of Enhanced statistical rankings via targeted data collection and with Hybrid-MST batches. All active methods get identical query budgets and the same filter. Only the selection rule differs.

For reference on static designs, Osting et al. report a factor of 2.2 gain in Fisher informativeness from adding 0.01% targeted edges on Yahoo! Movies. Hybrid-MST reports reaching full-comparison precision with 75% to 84% fewer comparisons on video and image quality data. Neither has a reported result under drift on Lacuna, so we must establish those numbers ourselves.

Two ablations isolate the key ingredient. The first replaces age-inflated resistance with static resistance, removing the $\sigma^2 a$ term. The second keeps age inflation but drops topology, refreshing whichever edges are stalest.

Why not just…?

Why not just use a Kalman filter for dynamic Bradley-Terry and stop? For passive estimation, we agree, and we adopt it. Its posterior already treats a stale bridge as uncertain. Our theory explains its behavior rather than replacing it. The open question is query choice, which a filter alone does not answer. Our ablation "filter plus random queries" quantifies how much active choice adds.

Why not just run greedy D-optimal selection on the filter's posterior? This is the real threat. Under Gaussian drift it may be near-optimal. If it matches our policy in error, our contribution narrows to three things: speed, since the resistance sketch avoids cubic updates and matters at tens of thousands of items; per-pair error prediction; and the drift-rate theory. We will report error against wall-clock time on the scale sweep and state plainly if there is no accuracy advantage.

Why not just tune NS-DPO's discount per cluster? Per-cluster discounting needs known clusters and still discounts cross-cluster edges by age, which is exactly what destroys bridges. The clustered-schedule experiments below test whether any single or per-cluster $\gamma$ can match resistance-aware handling on cross-cluster pairs.

Proposed Experiments

We begin with synthetic Bradley-Terry data in which scores follow Gaussian-process drift and piecewise jumps, on expander, barbell, and stochastic-block comparison graphs with 10 to 10,000 items. We measure current-time $\ell_2$ and $\ell_\infty$ error, split into within-cluster and cross-cluster pairs, plus top-$K$ recovery. The decisive check is whether age-inflated resistance predicts per-pair squared error, with a target rank correlation above 0.8. It should beat static resistance and plain age as predictors, and the predicted $\sqrt{\sigma^2 v / r}$ scaling should appear on bridges.

Real schedules give natural clustering. NFL 2011–2015 and NBA 1980–2016 schedules are divided into conferences and divisions, with sparse games across them. In the passive analysis we test whether recency-discounted fits degrade specifically on cross-conference pairs, by predicting held-out next-week outcomes. For context, the dynamic BT model's top-10 ranking matched 60–100% of the FiveThirtyEight ELO top 10 in Nonparametric Estimation in the Dynamic Bradley-Terry Model. For NBA, no reported number was found on Lacuna. For active querying, we replay with injected drift on the Yahoo! Movie graph and with simulated queries.

At language-model scale, we use the non-stationary UltraFeedback variants from NS-DPO. NS-DPO reports a length-controlled AlpacaEval 2 win rate of 8.93 against DPO's 7.29, and reward accuracy above 60–70% under preference flips against roughly 50–55% for DPO. This is not a horse race on those headline numbers. We cluster prompts by embedding, using the connectivity degree as the linking measure. We then ask two questions. Do NS-DPO's residual reward-model errors concentrate on response pairs whose prompts lie in weakly bridged clusters? And does reserving part of the relabeling budget for those bridges recover accuracy at a fixed annotation count? If the error is spread evenly across clusters, the topological story does not carry over to neural preferences, and we will say so.