Two-Speed Random-Feature Memory for Tracking Drifting User Preferences on a Byte Budget

A recommender that adapts to each user as they interact must keep a small model per user and update it after every click or skip. People's tastes do not hold still. Some interests are lasting, some last only a week, and a single recency discount cannot tell the two apart: it either forgets the lasting taste or clings to the passing one. With millions of users, every byte of per-user state also gets multiplied by the user count. This note proposes keeping each user's preference model as two weight vectors over shared random Fourier features. Random Fourier features are a fixed random nonlinear map of item descriptors whose dot products approximate a kernel similarity. One vector is fast and decays quickly; the other is slow, persistent, and stored at 2–4 bits per entry. Updates that keep recurring get moved from the fast vector into the slow one.

The bet is that the precision a model needs depends on how fast its weights change. Recent random-feature work found that for a fixed memory budget, having more features matters more than storing each one precisely. If that holds for slowly changing weights, the bits saved on the slow store can buy a richer feature space. The fast store, which must follow sudden shifts, keeps higher precision. The resulting tracker would follow abrupt preference flips, recover lasting tastes after short detours, and stay within a hard byte budget per user.

Core Claim

Prior work supplies the pieces but not this combination.

Kernel Expansion for Online Preference Tracking is the closest system and our main motivation. It replaces an online kernel SVM, whose stored training examples pile up under drift, with an explicit degree-2 polynomial expansion and a fixed-size linear weight vector. This reaches 68.9% test accuracy against 61.1% for incremental LASVM under 50% preference flips on uspop2002. It uses one timescale, full precision, and a polynomial map that grows quadratically with input dimension.

Two quantization papers supply the compression technique. Low-Precision Random Fourier Features quantizes features to 1–8 bits with stochastic rounding, meaning each value is rounded up or down at random so the result is correct on average. It argues that the number of features dominates precision for generalization. Quantization Algorithms for Random Fourier Features shows that the distribution of feature values does not depend on the kernel width. This makes 2-bit quantizers nearly lossless. Both papers compress a stored batch matrix of features on static data.

In streaming that matrix never exists, because features can be recomputed from the item. The real per-user cost is the weight state. Nobody has asked whether the "features beat precision" finding transfers to weights that are being updated under drift.

The drift literature motivates the two-timescale design. Non-Stationary DPO discounts old preference pairs by a single factor $\gamma^{T-t-1}$. Its own limitation is that it cannot separate timeless preferences from transient whims. PISA separates short-term and long-term taste using a Transformer plus memory-decay equations from ACT-R, a model of human memory. It is trained offline and carries a heavy memory cost.

Our claim is specific and falsifiable. At matched bytes per user, the two-speed quantized state should beat a single-timescale, full-precision random-feature tracker with tuned forgetting. The gap should be largest when a user makes a temporary detour and then returns to their old taste.

Research Program

Each item $x$ has a fixed descriptor. This is the MFCC audio vector on uspop2002, and frozen item embeddings learned from a held-out early period on Deezer, Last.fm and MIND. A shared set of $m$ random frequencies maps $x$ to $z(x)\in\mathbb{R}^m$. These frequencies are generated from a seed, so they cost no per-user memory. Each user holds a slow vector $u$, stored at $b_s$ bits, and a fast vector $v$, stored at $b_f$ bits, giving a budget of $m(b_s+b_f)$ bits. The predicted preference and the updates are

$$\hat r_t(x)=\big(u_t+v_t\big)^\top z(x),\qquad v_{t+1}=\gamma_f\,v_t-\eta\,\nabla \ell_t,$$

where $\ell_t$ is a logistic or pairwise loss on the observed interaction, $\eta$ is a step size, and $\gamma_f<1$ is the fast decay.

Every $K$ interactions, consolidation runs. The slow vector absorbs $u\leftarrow Q_{b_s}(u+\alpha v)$, where $Q_{b_s}$ is stochastic rounding to $b_s$ bits, and the fast vector keeps $(1-\alpha)v$. A passing whim decays in $v$ before much of it is consolidated, while a repeatedly confirmed preference accumulates in $u$. Together the two decays form a sum of two exponentials. This is a crude stand-in for the slower-than-exponential forgetting that ACT-R uses in PISA.

All updates are first-order, with no $m\times m$ covariance. This keeps the method $O(m)$ per user. It also avoids the numerical breakdowns that Mixed-Precision Kernel Recursive Least Squares reports for uniformly low-precision recursive updates, and that C3 Thompson Sampling cites as blocking quantization. Following the mixed-precision recipe, the loss gradient and the consolidation arithmetic are computed in 32-bit registers, and only the stored state is quantized.

The analysis is empirical. We will measure how the bit allocation between $m$, $b_s$ and $b_f$ trades off against tracking error. We will also measure how often stochastic-rounded slow weights stall, meaning updates smaller than one quantization step are lost, or drift without bound.

Baselines

The naive reference is a per-user popularity or recency model. For each user it ranks items by decayed interaction counts, like PISA's P-Top frequency baseline. That baseline overshoots repetition by up to 20 points on Deezer. Anything that cannot beat this has no reason to exist.

The strongest competitor on the central question is a single-timescale online random-feature tracker. It uses full-precision weights and exponential forgetting, with the forgetting rate tuned per dataset, and it is allowed as many features as fit in the same byte budget. This is the obvious "just do NS-DPO-style discounting in random-feature space" design. It is our own construction, so there is no reported number for it on Lacuna.

The strongest published memory-bounded tracker is PA-L-EX from Kernel Expansion for Online Preference Tracking, which reports 68.9% test accuracy under 50% flips on uspop2002. We will rerun it on the same flip protocol and also report it at matched bytes. That requires shrinking its expansion through feature hashing where the degree-2 map exceeds the budget.

A change-detection baseline pairs the single-timescale tracker with the dyadic RFF-MMD detector of Optimal Online Change Detection via Random Fourier Features. RFF-MMD is a two-sample test on random-feature means. When it fires, the tracker resets or speeds up its forgetting.

As unconstrained upper references, we use PISA on Last.fm and Deezer and NRMS on MIND.

  • PISA-P reports 12.16% NDCG on Last.fm and 11.20% on Deezer.
  • NRMS reports 67.76% AUC on MIND.
  • C3 reports a 12.4% click lift on MIND. This is a relative figure under a different protocol, so it serves only as context.

We do not expect to beat PISA outright. Success there means closing most of the gap at under 1 KB per user against PISA's GPU-scale footprint.

Ablations isolate each ingredient:

  • two-speed at full precision, which isolates the timescales;
  • single-speed at low precision, which isolates quantization;
  • an inverted allocation with a low-bit fast store and a high-precision slow store, which tests whether precision belongs with the fast weights.

For fairness, every method gets the same item descriptors and the same prequential stream (predict, then update). Every method also gets the same hyperparameter search budget, set at 50 configurations tuned on an early time slice. All results are reported at three budgets of 256 B, 1 KB and 4 KB per user.

Beating the strongest baseline means a statistically significant gain in prequential accuracy or NDCG@10 at two or more of the three budgets on at least two datasets. It also requires no worse recovery time after flips.

Why not just…?

Why not just use one weight vector at full precision with well-tuned exponential forgetting? This is the real threat. If it matches the two-speed state at equal bytes, the proposal collapses to "random features work for online preference tracking." That is useful but modest. The detour experiment below is designed to separate them. One forgetting rate must either forget the pre-detour taste or lag the detour, while two rates need not. If the gap does not appear there, we report the single-speed result as the finding.

Why not just detect changes and reset? The RFF-MMD detector is minimax-optimal at flagging that a change happened. A reset, however, discards lasting preferences along with stale ones. That is exactly the problem in a detour, where the user comes back. The detector-plus-reset baseline is run on every stream, so if resets cost little in practice, the experiments will show it.

Why not just keep a small per-user embedding inside a shared factorization model? A 64-float embedding costs the same as our 1 KB state, and factorization models are strong. Their weakness is that the per-user vector is tied to globally trained item factors, which need periodic batch retraining. C3's authors cite this cost as the reason they avoid neural retraining on MIND. We include a recency-weighted online factorization baseline at matched bytes, with item factors frozen from the same early period. It can therefore win only if a learned low-dimensional space beats a random high-dimensional one for drifting users. If it does win, that is a direct answer to the question.

Why not just use a sliding window with an exact kernel? The change-detection paper documents the window-size dilemma: a short window reacts fast but is noisy, and a long window is stable but slow. Exact kernels over a window of $K$ items also cost $O(K)$ stored descriptors, which far exceeds our budgets. We include a window at matched bytes, which forces it to be very short.

Proposed Experiments

On uspop2002 we reproduce the PA-L-EX protocol with 50% preference flips. On Deezer and Last.fm we evaluate per-user listening streams chronologically, using natural drift. On MIND we replay clicks in time order, where most articles expire within 48 hours, so item novelty dominates.

The decisive check is a detour injection on Deezer and uspop2002. For a random subset of users, we replace their stream with another user's stream for a window of $W$ interactions, then restore the original. We then measure two things:

  • accuracy during the detour, which captures how fast the tracker adapts;
  • accuracy in the first $W$ interactions after the original stream returns, which captures how much core preference was retained.

The two-speed state should dominate on the second measure without losing on the first. The single-speed tracker cannot do both at any single forgetting rate. We sweep $W$ to find where this advantage appears and where it disappears.

The second check is the bit-allocation sweep. If the LP-RFF result transfers to streaming weights, then at a fixed budget, moving bits from slow-weight precision into more features should help down to about 2 bits. If tracking instead degrades sharply below 4 bits because small updates stall, the precision-asymmetry claim fails. In that case we report where the floor is. We also log divergence and stalled-update counts for every quantized configuration, to address directly the instability that blocked quantization in C3 and KRLS.