Mutable Low-Rank Sketches for Retrain-Free Recommendation

Forum topic · 小凯 · 2026-07-20

Summary

This paper (arXiv:2607.15242) addresses embedding staleness in two-stage recommendation systems, where user embeddings remain frozen between retraining cycles. The authors propose mutable sketches: each user's preferences are stored in a KP-tree, a sparse segment tree with sum aggregation, and a low-rank projection is fit once; embeddings are then recomputed on-the-fly as new ratings arrive. Theoretically, they prove each new observation monotonically tightens the prediction error envelope (Theorem 1), a guarantee FunkSVD and eALS lack. Empirically on KuaiRec, mutable sketches reach 0.810 RMSE while reading only 1.8% of the data, versus 0.822 RMSE for ALS reading 100%, with 8x faster per-batch updates. New users get personalized recommendations in under 1 ms after their first rating without retraining. Sampling-strategy analysis shows KP-tree norm-proportional sampling gives 40-130% better item coverage on sparse matrices (<1% density), while uniform sampling suffices on dense matrices.

Overview

Field: cs.LG Authors: Hector J. Garcia, Nick Clayton Published: 2026-07-16 arXiv: 2607.15242

Abstract

A common bottleneck in two-stage recommendation is embedding staleness: when a user rates a new item, their embedding remains fixed until the next retrain cycle. The authors propose mutable sketches, which store each user's preferences in a KP-tree (a sparse segment tree with sum aggregation), fit a low-rank projection once, and recompute embeddings on-the-fly as ratings arrive.

Key Results

Theoretical guarantee: Each new observation monotonically tightens the prediction error envelope (Theorem 1) — a guarantee FunkSVD and eALS lack.
Accuracy vs. efficiency: On KuaiRec, the mutable sketch achieves 0.810 RMSE at 1.8% data read, compared to ALS's 0.822 RMSE at 100% data read, with 8x faster per-batch updates.
Cold start: A new user receives personalized recommendations in <1 ms after their first rating, with no model retraining required.
Sampling strategies: Across density regimes, the KP-tree's norm-proportional sampling provides 40–130% better item coverage on sparse data (<1% density), while uniform sampling suffices on dense matrices.