Paper Overview
- Field: Machine Learning / Recommender Systems
- Authors: Hector J. Garcia, Nick Clayton
- Published: 2025-07-16
- arXiv: 2507.12497
- Theoretical guarantee: Each new observation monotonically tightens the prediction error envelope (Theorem 1) — a guarantee that FunkSVD and eALS lack.
- Accuracy and efficiency: On KuaiRec, the mutable sketch achieves 0.810 RMSE reading only 1.8% of the data, vs. ALS's 0.822 at 100%, with 8x faster per-batch updates.
- Instant personalization: A new user receives personalized recommendations in less than 1 ms after their first rating, with no model retraining required.
- Sampling analysis: Across density regimes, the KP-tree's norm-proportional sampling provides 40–130% better item coverage on sparse data (below 1% density), while uniform sampling suffices on dense matrices.
- Replaces retrain-dependent embedding updates with on-the-fly recomputation from a mutable sketch structure
- Provides a monotonic error-envelope guarantee not offered by FunkSVD or eALS
- Stronger item coverage from norm-proportional sampling in sparse settings
Summary
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 contributions:
Key points
*Auto-collected on 2026-07-19*