Mutable Low-Rank Sketches for Retrain-Free Recommendation
2026-07-16 • Machine Learning
Machine Learning
AI summaryⓘ
The authors address a common problem in recommendation systems where user preferences don't update quickly after new ratings, called embedding staleness. They introduce mutable sketches, which use a special data structure (KP-tree) to update user profiles instantly without retraining the whole model. Their method reduces prediction errors as new data arrives and runs faster than traditional algorithms. They also show better item coverage, especially with sparse data, by using a smart sampling strategy.
two-stage recommendationembedding stalenessKP-treemutable sketcheslow-rank projectionFunkSVDeALSsampling strategiessparse dataRMSE
Authors
Hector J. Garcia, Nick Clayton
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. We 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. We prove that each new observation monotonically tightens the prediction error envelope (Theorem 1), a guarantee that FunkSVD and eALS lack. On KuaiRec, the mutable sketch achieves 0.810 RMSE at 1.8% data read vs. ALS 0.822 at 100%, with 8x faster per-batch updates. A new user receives personalized recommendations in <1 ms after their first rating, with no model retraining required. A comparison of sampling strategies across density regimes shows that 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.