Retrieving Under a Drifting Kernel Preference Without Rebuilding the Index

Personalized systems face two problems that are usually solved separately. A user's taste changes over time, sometimes abruptly, and the model of that taste has to keep up. The system also has to find the few items the user will like among millions, fast. Kernel methods, which score an item by its smooth similarity to things the user has engaged with, are good at the first problem when they are made cheap with random features: each item is mapped to a few thousand random cosine coordinates, and the user becomes a single weight vector that can be updated in constant memory. They are bad at the second problem. A nearest-neighbor index built in that thousand-dimensional feature space runs into the curse of dimensionality, where search trees and graphs lose their ability to prune. Rebuilding an index every time the user's taste moves is not an option either.

This note proposes to learn in the random-feature space and to retrieve in the original item space. The item index is built once over the raw, comparatively low-dimensional item vectors and is never touched again. When the user's preference function drifts, only the query changes. At serving time we climb the learned preference function from a few recent positive items to its current peaks in item space, query the static index at those peaks, and rerank the candidates exactly with the kernel model. Drift becomes a change in where we look, not a change in the data structure.

Core Claim

Let $z(x) \in \mathbb{R}^m$ be a random Fourier feature map, the cosine features $\sqrt{2/m}\cos(\omega_j^T x + b_j)$ with $\omega_j$ drawn from the kernel's spectral density. The user's preference at time $t$ is the linear score $f_t(x) = w_t^T z(x)$, where $w_t$ is a weight vector updated online. Because this score is differentiable in the raw item coordinates $x \in \mathbb{R}^d$,

$$\nabla_x f_t(x) = -\sqrt{2/m}\sum_{j=1}^{m} w_{t,j}\,\sin(\omega_j^T x + b_j)\,\omega_j ,$$

we can run a few steps of gradient ascent in $d$ dimensions, starting from recently liked items. Each local maximum then serves as an ordinary nearest-neighbor query against a fixed graph index over the raw item vectors. The claim is that this approach, which we call ascend-then-retrieve, recovers the exact top-$k$ items under the current $f_t$ with high recall. It should need far fewer distance computations than searching an index over the $m$-dimensional features $z(x)$, and it should never need a rebuild when $f_t$ changes. Recovery should hold whenever the high-scoring region of $f_t$ is concentrated around a small number of modes.

That condition is what the experiments must test. Smooth kernels in high dimension can produce broad, flat score landscapes, and ascent would then add nothing over a scan.

Relation to Prior Work

Four papers motivate the gap. Kernel Expansion for Online Preference Tracking shows that a fixed-size primal model built on an explicit degree-2 polynomial expansion with Passive-Aggressive updates survives preference flips better than an online dual kernel machine: 68.9% versus 61.1% for LASVM when half of the uspop2002 preferences flip. It retrieves by scanning every candidate, however, and its expansion grows as $O(d^p)$ with input dimension. We reuse its primal-tracking logic but swap in random features, whose size does not depend on $d$, and we add sublinear retrieval.

Accelerating High-Dimensional Nearest Neighbor Search with Dynamic Query Preference (the Dual-Index Query Framework, DQF) keeps a small "hot" index of frequently queried items beside the full index. It reports a 2.0–5.7x speedup over HNSW and NSG at 95% recall under a Zipf query distribution. DQF treats drift as a change in item popularity under a fixed Euclidean metric. Our setting is different: the scoring function itself is nonlinear and changes, while popularity may stay flat.

Locality-sensitive binary codes from shift-invariant kernels turns random Fourier features into hash codes whose Hamming distance tracks a fixed kernel. It reaches about 0.8 precision at 0.2 recall with 128 bits on LabelMe and is weak below 32 bits. Its codes answer "which items are kernel-close to this one point," not "which items maximize a learned weighted sum of features."

Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation expires old data in sliding windows but only maintains bucket counts, not a learned preference function.

One paper supplies a method. DEANN shows that a raw-space ANN index can carry most of the cost of a kernel sum, because kernel mass sits near the query. Our approach depends on the same locality, applied to a learned and drifting function rather than a static density.

Other papers constrain the design. Which Spatial Partition Trees are Adaptive to Intrinsic Dimension? and Contrast Plots and P-Sphere Trees document why indexing the $m$-dimensional feature space is a poor idea: cells stop shrinking and distance contrast vanishes. They also warn that our raw space can be high-dimensional too (GIST is 960-d), which is why we use graph indices rather than trees.

Scalable Random Wavelet Features reports step-function RMSE of 0.071 against 0.246 for Fourier features. Its localized wavelet atoms should yield sharper, more mode-concentrated score landscapes, so we test them as an alternative feature map. They were developed for static regression; we use them in the online setting.

Research Program

We will build three components and study how they interact. The first is the online learner: Passive-Aggressive or decayed least-squares updates of $w_t$ over Fourier features, with wavelet features as a variant. The second is the ascent routine: from the $s$ most recent positive items, take a fixed number of gradient steps, merge nearby endpoints, and treat the surviving modes as queries. The third is the retrieval layer: a static HNSW index over raw item vectors, queried with $k'$ neighbors per mode, followed by exact reranking with $w_t^T z(x)$.

The analysis focuses on when this succeeds. The score landscape has a characteristic width set by the kernel bandwidth. When that width is small relative to the spread of the items, $f_t$ is a sum of local bumps and its top items sit near a few modes. When it is large, the top set spreads out and the number of candidates needed grows. We will measure recall of the exact top-$k$ as a function of bandwidth, $m$, number of seeds, and candidate budget, and we will try to bound the candidate budget in terms of the number of significant modes. Because we have no theory for this yet, we state it as a hypothesis to measure rather than a result.

Baselines

The naive reference point is a brute-force scan: score every item with $w_t^T z(x)$ at cost $O(Nm)$ per query. It defines exact ground truth for recall and the latency ceiling. It runs on the same hardware with the same learner, so recall is 100% by construction, and our method must beat it on latency or distance computations at recall@10 of at least 95%.

The strongest direct competitor is maximum-inner-product search with HNSW built over the $m$-dimensional features $z(x)$. It is exact in the space where the model lives and also needs no rebuild under drift, since only the query $w_t$ moves. This makes it the real threat. We give it the same memory budget and tune its graph degree and search breadth with the same number of trials as our method, and we compare distance-computation cost (each of its distance evaluations costs $m$ operations, ours cost $d$) at matched recall. No reported result was found on Lacuna for HNSW over random-feature vectors, so this number has to be produced by us.

The strongest published dynamic-index method is DQF, which reports 2.0–5.7x over HNSW/NSG at 95% recall under Zipf $\beta=1.2$ (Accelerating High-Dimensional Nearest Neighbor Search with Dynamic Query Preference). We run it on raw vectors with a linear user vector as its query, on the same SIFT1M and GIST1M catalogs. It counts as beaten if our method retrieves more of the true nonlinear top-$k$ at equal cost. Under a pure-popularity Zipf workload we expect it to win, and we will say so.

For preference tracking, the reference is PA-L-EX with degree-2 polynomials, whose 68.9% under 50% flips on uspop2002 we first reproduce, alongside Fourier features with exponential time decay.

The key ablation is seeds-without-ascent: query the raw index at the recent positive items themselves, with no gradient steps. This isolates whether climbing the learned function contributes anything beyond item-to-item neighbor lookup.

Why not just…?

Why not just index the random features directly with an inner-product graph? It is correct and drift-proof, so it may well be competitive. Its weakness is cost: every hop evaluates an $m$-dimensional product, with $m$ typically thousands against $d$ of 128 or 960. The distance-concentration results of Goldstein et al. also suggest its routing degrades as $m$ grows. If the matched-recall comparison shows it within a small factor of our cost, the honest conclusion is that ascent is unnecessary, and we will report that.

Why not just use a linear user vector in raw item space with time decay and DQF or HNSW? If preferences on these catalogs are close to linear in the raw embedding, kernels add nothing. The uspop2002 evidence (Kernel Expansion for Online Preference Tracking) shows nonlinear expansions matching RBF accuracy, but it does not show them beating linear models. Our KuaiRand experiment compares linear and kernel trackers directly on randomly exposed items. If linear matches the kernel tracker there, the proposal reduces to retrieval on synthetic preferences and we will say so.

Why not just retrieve neighbors of recently liked items? This is the seeds-without-ascent ablation. After a preference flip, recent positives sit in regions the model has just learned to dislike. Ascent should move queries toward the new high-score region, whereas raw neighbors should lag. If the two give equal recall after flips, the gradient step is not earning its place.

Why not just scan, given that catalogs are small? For KuaiRand-Pure's 7,582 videos, scanning is the right answer, and we do not claim otherwise. Indexing only matters at the million-item scale, which is why the retrieval experiments use SIFT1M and GIST1M.

Proposed Experiments

The first experiment tests tracking quality on real drift. On KuaiRand (KuaiRand), we train each tracker on organic interactions in temporal order and evaluate AUC on the randomly exposed videos in later windows, which separates preference change from exposure bias. The trackers are linear, polynomial PA-L-EX, Fourier with decay, and wavelet features. The KuaiSim simulator (KuaiSim) reports an AUC of 0.7234 for multi-behavior prediction. That result comes from a different model and task, so we use it only as orientation, not as a target. We also reproduce the uspop2002 flip experiment.

The second experiment tests retrieval under planted drift at scale. SIFT1M (128-d) and GIST1M (960-d) serve as item catalogs. For each simulated user, we draw a ground-truth preference as a random-feature function with several modes and stream noisy feedback. At set times we flip the user to new modes. We then measure recall@10 against the exact top-10 under the learner's current $f_t$, along with distance computations and wall-clock latency per query, and recovery time after a flip. All methods are swept over the same tuning grid.

The decisive checks come in three parts. First, we plot recall against candidate budget across kernel bandwidths to locate the regime where ascend-then-retrieve beats feature-space search. The hypothesis fails if no bandwidth that also gives good KuaiRand tracking falls inside that regime. Second, the post-flip recall gap between ascent and seeds-without-ascent tests the mechanism itself. Third, comparing Fourier and wavelet features tests whether localized features make the landscape more retrievable, as the step-function results of Scalable Random Wavelet Features suggest.