Rank-Calibrated Streaming Preference Gaussian Processes

Recommenders and interactive decision tools often learn what a person wants from comparisons such as "I prefer A over B" or "from these five, I pick this one." A Gaussian process (GP) is a Bayesian model that places a prior over functions and returns calibrated uncertainty along with each prediction. GPs are the standard tool when such comparisons are scarce and the system must choose which options to show next. They have three problems in deployment. Exact inference costs grow cubically with the number of comparisons. The person's tastes drift over time. And the system is ultimately judged on whether the top few items it shows are right, while the model is fit to classify pairs correctly. Prior work treats these problems one at a time. This note argues that they meet at a single point: the approximation that makes the GP scale.

A scalable GP compresses everything it has seen into a small, fixed budget of summary variables. Nothing in the standard approximation tells that budget to describe the current top of the ranking accurately rather than the long tail. Drift makes this worse, because the true top-K keeps moving away from the region the compressed model learned well. We propose a streaming preference GP with three parts. Forgetting comes from a learned temporal kernel. Fitting uses a listwise choice likelihood. The variational approximation, together with its placement of summary points, is calibrated against expected top-K ranking quality under the current posterior. The claim is narrow and testable: when the budget is tight and preferences drift, approximation error concentrated at the top of the list is the main cause of the gap between pairwise fit and NDCG@K. A rank-calibrated approximation closes much of that gap at the same compute.

Core Claim

Three lines of evidence point to the same mechanism. On objectives, LambdaFM shows that pairwise objectives can improve global ordering while getting positions 1 and 2 wrong. Its lambda surrogates raised MRR by over 35% on Yahoo Music while AUC stayed flat or fell. Rejuvenating Cross-Entropy Loss in Knowledge Distillation proves that a classification loss bounds NDCG only under "closure": the evaluated candidate set must contain the items the model currently ranks highly. On scalable GPs, Approximation-Aware Bayesian Optimization shows that sparse approximations smooth over sharp, narrow optima. It fixes this by calibrating the variational approximation to the downstream decision. On drift, Right Now, Wrong Then shows that stationary pairwise preference learning falls to near-chance reward accuracy (about 50–55%) when preferences flip. Exponential time decay recovers 60–70%.

Put together, these suggest that a sparse, drifting preference GP fails at the top of the list in a predictable way. Its summary variables sit where data was dense in the past. Its pairwise likelihood spends evidence on the tail. And its comparisons rarely include the items it currently believes are best, so closure fails. Our claim is that calibrating the approximation to the posterior's own top-K decision, and choosing slates that keep that top-K inside the evaluated set, should improve NDCG@K under drift at fixed budget. We expect the gain to shrink to zero as the budget grows. If the gain does not vanish with a larger budget, or never appears at a small one, the claim is wrong.

Research Program

The model places a GP prior on a latent utility $f(x, t)$ over item features $x$ and time $t$. Its covariance is a product of an item kernel and a temporal kernel. The temporal kernel is a Markovian Matérn kernel, so the posterior can be propagated forward in time by a Kalman-style recursion. Per-step cost then depends on the number of item summary variables $m$, not on the length of history.

This choice handles drift differently from the alternatives. Forgetting becomes part of the prior: stale evidence loses influence at a rate set by a temporal lengthscale, and that lengthscale is learned by maximizing the variational objective online. By contrast, NS-DPO's decay factor $\gamma$ must be fixed in advance from a guess at how much drift there will be. OHSVGP compresses history with polynomial projections that are built not to forget, and it freezes kernel hyperparameters. DAO-GP detects drift by monitoring regression error and then refits or swaps kernels. It handles only scalar targets.

Each observation is a slate $S$ of $K$ items shown at time $t$, together with the user's choice or partial ordering over it. We model this with a Plackett–Luce likelihood, which treats a ranking as repeated choices of the most preferred remaining item. Pairwise duels, as in Preferential Bayesian Optimization and POP-BO, are the special case $K=2$.

The fitting objective adds a decision term to the usual sparse variational objective, following the logic of approximation-aware BO:

$$ \mathcal{L}(q, Z) = \mathrm{ELBO}(q, Z) + \lambda \log \mathbb{E}_{f \sim q}\big[\mathrm{NDCG@K}(\hat\pi_T, f(\cdot, T))\big]. $$

The symbols are as follows. $q$ is the variational posterior over the $m$ summary variables placed at item locations $Z$. $\hat\pi_T$ is the ranking the system would currently display at time $T$, namely items sorted by posterior mean. The expectation scores that ranking with posterior samples of the utility used as gains. $\lambda \ge 0$ sets the strength of the calibration, and $\lambda = 0$ recovers the standard approximation. The second term rewards approximations under which the system's own top-K decision looks reliable. This pushes accuracy toward the head of the list. We estimate its gradient with a SoftSort relaxation of the kind RewardRank uses to backpropagate list utility. Here the relaxation acts on posterior samples inside the approximation, not on a learned neural reward model, so the reward-hacking failure that paper reports has no learned critic to exploit.

Two further rules carry the closure insight into the GP. First, summary-point locations $Z$ are re-seeded at each step from the current posterior top-K and its nearest high-variance competitors. Second, each displayed slate contains the posterior top items plus Thompson-sampled challengers. Together these keep the items the model ranks highly inside the evaluated set.

The analysis component asks one question: where does NDCG@K loss come from as $m$ shrinks? We will decompose the total loss into three parts: error from the likelihood (pairwise vs. listwise), error from forgetting (decay vs. temporal kernel), and error from the approximation (uniform vs. rank-calibrated budget). We will then plot how each part changes with $m$ and with drift speed.

Baselines

The naive reference point is a static sparse pairwise GP that never forgets. Concretely, this is the probit model of Gaussian Process Preference Elicitation, run with standard sparse variational inference and the same $m$. It shows how much drift and top-of-list error cost when nothing is done about them. The file has no reported numeric loss for GPPE on Sushi. It reports only that GPPE reached in 4–6 queries an accuracy other methods needed 10+ queries to reach, so we will reproduce it ourselves.

The strongest existing preference-GP competitor is POP-BO with Thompson-style slate selection, given recency through exponential weights on its likelihood. This is the most principled preferential method in the file, and adding decay grants it the simplest drift fix. No reported result found on Lacuna for POP-BO numeric regret. The paper reports only that it was more than 10 times faster than Thompson-sampling methods. For the pairwise-GP lineage, the one quantitative anchor in the file is PBO finding a near-optimal Six-Hump Camel solution in about 200 duels, against thousands for Sparring. We will check that our reimplementations reproduce this order of magnitude before running drift experiments.

The strongest drift competitor is a sparse preference GP with NS-DPO-style decay $\gamma^{T-t_i-1}$ on per-observation log-likelihoods, with $\gamma$ tuned on a validation stream. For contrast, NS-DPO itself reports reward accuracy above 60–70% versus 50–55% for DPO under flips, and a length-controlled win rate of 8.93 versus 7.29. Those numbers come from language-model alignment and do not transfer to our tasks.

The strongest non-Bayesian competitor is a neural listwise ranker trained with LambdaRank-style lambdas and a recency window, refit each step. It tests whether uncertainty matters at all.

The ablations isolate the key ingredient. We set $\lambda=0$ with top-K re-seeding kept, and $\lambda>0$ with uniform re-seeding. We also run an exact (non-sparse) GP at small scale, which serves as an oracle for approximation error.

For fairness, all methods see identical streams and slate sizes. Each gets the same wall-clock budget per update and the same hyperparameter-search budget on a held-out stream. All GP variants share the same $m$. Beating the strongest baseline means a statistically significant improvement in time-averaged NDCG@5 and NDCG@10 across random seeds at small $m$. Pairwise accuracy may stay equal or fall, which is the AUC paradox again. The gap should also shrink toward the exact-GP oracle as $m$ grows.

Why not just…?

Why not just add exponential time decay to an existing sparse preference GP? This is the most serious threat on the drift axis. DAO-GP and NS-DPO both show that decay helps a lot. It is included as a baseline with $\gamma$ tuned using information that would not be available online, which favors it. Our temporal kernel should match it under gradual drift and win under unknown or changing drift rates, where a single $\gamma$ is wrong for part of the stream. We test this by varying drift speed within a stream. If tuned decay matches the temporal kernel everywhere, we will adopt decay and keep only the rank-calibration contribution. That contribution is orthogonal to how forgetting is done.

Why not just use more summary points, or an exact GP? If the approximation stops being the bottleneck at practical budgets, calibration is pointless. The file suggests it often is the bottleneck: Maus et al. find sparse GPs miss narrow optima, and OHSVGP's runtime figure (0.4 s versus 140 s for online sparse GP regression on Solar) shows how quickly cost matters in streaming. Our $m$-sweep against the exact GP on Sushi settles the question directly. A gain that disappears only at $m$ close to the number of items would count against the proposal at small scale but support it at New Yorker scale.

Why not just fit pairwise comparisons and rank by posterior mean? This is what GPPE and PBO effectively do. LambdaFM's results show pairwise fitting misallocating effort away from the top. The pairwise-vs-Plackett–Luce ablation, holding everything else fixed, measures how much of the gain comes from the likelihood alone.

Why not just use a neural ranker with recency weighting? With thousands of comparisons per user this may be competitive, and we report it. Our bet is on the few-query regime GPPE targets. There, choosing which slate to show depends on uncertainty. We test this by plotting NDCG@K against queries per user and expect the neural model to lag early.

Proposed Experiments

The first testbed is the Sushi dataset used by GPPE: 5,000 users ranking 10 items, with 15-dimensional item and 85-dimensional user features. Because each user gives a full ordering, we can simulate any slate response. We introduce controlled drift by moving each user's target ordering, abrupt or gradual, toward that of a different demographic group. This mirrors the opinion-shift construction NS-DPO used on GlobalOpinionsQA.

The second testbed is the synthetic PBO functions (Forrester, Six-Hump Camel, Branin), discretized into candidate sets of 10³ to 10⁵ points with a moving optimum. Here we sweep $m$ and drift speed and measure top-K regret.

The scale test uses the New Yorker caption ranking data: 250M ratings on 2.2M captions over eight years. Captions are embedded with a text encoder, contest date serves as time, and slates are formed from within-contest rating orderings. Because these ratings are pointwise, we treat this testbed as a check of cost and stability and of whether learned temporal lengthscales track real taste change. It is not the main evidence on the likelihood question.

Metrics are time-averaged NDCG@5/10 and MRR, pairwise accuracy (to expose the paradox), and per-update latency and memory.

The decisive checks are three. First, at small $m$ under drift, the rank-calibrated model beats tuned-decay POP-BO and the $\lambda=0$ ablation on NDCG@K. Second, that gain shrinks toward the exact-GP oracle as $m$ grows. Third, removing top-K re-seeding from the slate rule reduces the gain, which would confirm that closure is part of the mechanism. If the gain persists at large $m$, it is not an approximation effect. If it is absent at small $m$, the core claim fails.