Mutable Low-Rank Sketches for Retrain-Free Recommendation

TL;DR - A research paper proposing "mutable low-rank sketches" that let recommender systems update user embeddings on-the-fly as new ratings arrive, eliminating the retrain-cycle staleness that plagues two-stage recommendation.

• Stores each user's preferences in a KP-tree (sparse segment tree with sum aggregation) and fits a low-rank projection once, recomputing embeddings instantly per new rating with no retraining.
• Claims a theoretical guarantee (Theorem 1) that each new observation monotonically tightens the prediction-error envelope — something FunkSVD and eALS reportedly lack.
• On KuaiRec: 0.810 RMSE reading only 1.8% of data vs. ALS's 0.822 at 100%, with 8× faster per-batch updates and <1 ms personalized recs after a new user's first rating.
• Norm-proportional sampling via the KP-tree gives 40–130% better item coverage on sparse data (<1% density); uniform sampling suffices when matrices are dense.