Certified Sparse Gaussian-Process User Densities for Retrieval

Most recommenders summarize a user as one vector and fetch the items whose embeddings lie closest to it. A person who buys hiking gear, jazz records, and baking tools gets averaged into a point that sits between those clusters and matches none of them. A recent alternative drops the point entirely. It treats the user's taste as a smooth function over item-embedding space and fits it with Gaussian-process regression, a Bayesian method that returns both a predicted score and an uncertainty for every item. That function naturally grows one peak per interest, and its uncertainty supports exploration. Two problems stand in the way of using it at scale. Exact fitting costs grow with the cube of history length. Worse, scoring a whole catalog means evaluating the function at every item, which bypasses the fast nearest-neighbour indexes that production retrieval depends on.

We propose a single construction that addresses both problems and also answers the "how many interests?" question that multi-vector recommenders settle by heuristic. Each user is represented by a sparse Gaussian process, a version that summarizes the history through $M$ learned anchor points called inducing points. Anchors are added greedily, one at a time, until a computable bound on the approximation error falls below a threshold. The number of anchors is therefore set per user by how much of their history remains unexplained, not by a fixed $K$. Because a sparse posterior mean, and also a posterior sample, is a weighted sum of $M$ kernel bumps centred on the anchors, retrieval reduces to $M$ ordinary nearest-neighbour queries plus a reranking step. That step comes with a certificate saying whether any item outside the candidate set could have scored higher.

Core Claim

The inducing points of a sparse Gaussian process can serve directly as a user's multi-interest vectors, and three properties follow that neither existing line of work has. First, the number of interests adapts per user through the variational error term instead of a logarithmic rule or a tuned constant. Second, both the posterior mean and Thompson-sampling draws can be served with standard approximate nearest-neighbour indexes, with a checkable optimality certificate. Third, fitting cost is linear in history length, so long-history users need not be truncated. The empirical claim we will test has two parts. At matched serving cost, meaning the same number of index queries, this model should match exact density-based retrieval on short histories. It should also beat both truncated exact density models and fixed-$K$ multi-vector models on long-history and many-interest users, especially on coverage of tail interests.

Relation to Prior Work

Two papers motivate the problem. GPR4DUR fits an exact per-user Gaussian process with a radial-basis-function kernel (a similarity that decays with squared distance) over pre-trained item embeddings, and retrieves by upper-confidence-bound and Thompson-sampling scores. It reports gains in interest coverage and tail exposure over multi-vector baselines, particularly in low-dimensional embeddings. Its histories are capped near 160 items, and its authors name sparse and collaborative Gaussian processes as open work. We keep its density view but change three things: how the user is compressed, how $M$ is chosen, and how the catalog is searched. NP-Rec avoids matrix inversion by learning an amortized neural process with a Mamba backbone and a categorical decoder. It gives up kernel calibration, and it needs several stochastic decoder passes at inference. Our model keeps closed-form posteriors and puts its cost into index lookups.

The multi-vector systems MIND and ComiRec extract $K$ interest vectors by capsule routing or self-attention. Both run $K$ index queries and then aggregate the results. MIND sets $K$ logarithmically in history length and reports a plateau at 5 to 7 vectors on Tmall. Our serving pattern is deliberately the same as theirs, $M$ index queries followed by aggregation, so that we can make a fair matched-cost comparison. The difference is that our vectors carry weights and uncertainty, and their number is chosen by an error criterion. The geometric case against single centroids comes from the "no man's land" finding in query-integration music retrieval and from the unimodality critiques in multimodal attentive metric learning and diversity-promoting collaborative metric learning. These papers motivate multi-modality but do not tell us how many modes to keep.

One paper constrains the design. Approximation-Aware Bayesian Optimization shows that a sparse Gaussian process with too few or poorly placed inducing points oversmooths narrow peaks, and downstream search then misses them. In recommendation, narrow peaks are exactly the niche interests. A sparse approach could therefore quietly reintroduce the averaging failure. We make this risk the central experimental question rather than an afterthought, and the error-driven anchor placement is our proposed defence.

Research Program

Item embeddings are pre-trained and normalized to the unit sphere, as in GPR4DUR's low-dimensional setting. For user $u$ with history embeddings $X_u$ and labels $y_u$, we fit a sparse variational Gaussian process with shared kernel hyperparameters: a lengthscale $\ell$, an amplitude $s^2$, and a noise level, all learned across users. Inducing locations $Z_u$ start empty. At each step we add the history item that contributes most to the trace term of the variational bound,

$$T_u = \frac{1}{2\sigma^2}\,\mathrm{tr}\!\left(K_{XX} - K_{XZ}K_{ZZ}^{-1}K_{ZX}\right),$$

where $K_{AB}$ is the kernel matrix between point sets $A$ and $B$ and $\sigma^2$ is the observation noise. $T_u$ measures how much prior variance at the user's own history points the anchors fail to explain. An isolated niche interaction keeps high residual variance until it receives its own anchor, which is exactly the property the oversmoothing concern calls for. We stop once $T_u/N_u$ drops below a threshold $\epsilon$, where $N_u$ is the history length, and then refine the anchor locations by gradient steps on the bound. Each step costs $O(N_u M^2)$.

Retrieval relies on one identity. On the unit sphere, the radial-basis-function kernel equals $s^2 e^{-1/\ell^2}\exp(x^\top z/\ell^2)$, so it is monotone in the inner product $x^\top z$. Write a score function as

$$g(x)=\sum_{m=1}^{M} w_m\, k(x,z_m).$$

Here $w = K_{ZZ}^{-1}m_u$ gives the posterior mean, with $m_u$ the variational mean. Alternatively $w = K_{ZZ}^{-1}\tilde u$ gives a Thompson draw, with $\tilde u$ sampled from the variational posterior over anchor values; this decoupled draw drops the small residual variance that the anchors do not capture. For each anchor with $w_m>0$ we fetch the top-$L$ items by inner product from a standard index and rerank their union by $g$. Let $\tau_m$ be the kernel value of the $L$-th result for anchor $m$. Any unretrieved item then scores at most $\sum_{w_m>0} w_m \tau_m$. When the best retrieved score exceeds this bound, the returned list is exactly the true top set. Otherwise $L$ is doubled for the anchors that are binding. We will report how often the certificate holds and what the average $L$ is.

The upper-confidence-bound score does not decompose this way, because its variance term is quadratic in the kernel vector. We therefore use Thompson sampling as the exploration rule that the indexes can serve. As a diagnostic, we will also compare against exact upper-confidence-bound scoring over the full catalog on small catalogs. Streaming updates in the style of recurrent-memory online interdomain GPs and cross-user collaborative priors are natural extensions, but they are out of scope here.

Baselines

The naive reference is a single-vector model, mean pooling of history embeddings in the YouTube-DNN style that MIND compares against. MIND reports beating this kind of model by over 60% in HitRate@50 on TmallData (MIND). It sets the floor that any multi-interest method must clear.

The strongest point-based competitors are MIND and ComiRec-SA/DR. They run on the same item embeddings, embedding dimensions, and splits, and we tune $K$ over the same budget of configurations that we spend tuning $\epsilon$. The reported reference points are ComiRec's +8.65% Recall@50 on the Alibaba industrial data, and its Amazon result that raising $\lambda$ from 0 to 0.25 more than doubled diversity (23.2% to 55.1%) at about a 5% Recall cost (ComiRec). The decisive comparison is at matched index queries, where MIND's $K$ equals our mean $M$. Beating it means higher Recall@50 and interest coverage at equal or lower query count, with the gap growing for users with many interests.

The strongest density competitor is GPR4DUR itself, run exactly as published with histories truncated near 160. No reported result was found on Lacuna for GPR4DUR's numeric Recall, coverage, or tail-exposure values on Amazon or ML-1M; the file states qualitatively that it alone improved tail exposure on Amazon. We will therefore reproduce it. Beating it means matching it within noise on users with fewer than 160 items, and exceeding it on users with longer histories, at lower serving latency than exhaustive catalog scoring.

NP-Rec is run with its published architecture under an equal training-compute budget. It reports a 13.94% average improvement across datasets over its own baselines (NP-Rec).

Three ablations isolate the key ingredient. The first uses fixed $M$ with k-means anchors, which tests whether the error-driven selection matters. The second uses the full GPR4DUR scorer on our model's candidate set, which tests the retrieval approximation. The third is an exact Gaussian process on randomly subsampled rather than recency-truncated history, which tests whether long history matters at all.

Why not just…?

Why not just truncate history and keep exact GPR4DUR? This is the most serious threat. At a few hundred items, exact fitting is cheap, so cubic cost by itself is a weak motivation. We take that seriously, and our claim rests on two other things: serving through indexes, and adaptive $M$. The stratified-by-history-length experiment settles the remaining question. If long-history users show no gain over truncation, we will report that the value lies in serving and adaptivity, not in scale.

Why not just run k-means on each user's history and use the centres as MIND-style vectors? This is close to what we do, and the fixed-$M$ k-means ablation exists to test it. k-means places centres by item frequency, so it tends to merge a single-purchase niche interest into a large neighbouring cluster. The trace criterion instead gives that item an anchor because its residual variance stays high. If the k-means ablation matches our model on tail exposure, the Gaussian-process machinery adds little beyond Thompson exploration, and we will say so.

Why not just tune $K$ in MIND or ComiRec? A global $K$ cannot be right for both narrow and broad users. MIND's own plateau at 5 to 7 vectors suggests that the averaged optimum hides this per-user mismatch. The matched-query comparison, broken down by number of interest categories, tests this directly.

Why not just use NP-Rec? It amortizes inference well, but it does not provide calibrated kernel uncertainty or index-compatible scoring. If it wins on accuracy at comparable latency, our advantage reduces to calibration and the certificate. We will measure calibration through held-out interaction likelihood.

Proposed Experiments

We use Amazon Books, ML-1M, and Taobao, the shared benchmarks of MIND, ComiRec, and GPR4DUR, with GPR4DUR's protocol and embedding dimensions of 4, 8, and 32. Metrics are Recall@50, NDCG@50, interest-wise coverage, tail-exposure improvement, mean and maximum $M$, index queries per user, certificate hit rate, and end-to-end latency.

Three checks are decisive. The first is a history-length-stratified comparison against truncated GPR4DUR. The second is a sweep of $\epsilon$ that traces tail exposure against $M$, to test whether too small a budget recreates centroid collapse as the oversmoothing result predicts. The third is the matched-query comparison against MIND and ComiRec. The core claim fails if error-driven anchors give no tail-coverage gain over k-means anchors at equal $M$, or if certified index retrieval loses more than a small fraction of exact-scoring recall.