Summary
This paper, posted on zhichai.net and available as arXiv 2507.12497, addresses embedding staleness in two-stage recommender systems, where user embeddings stay fixed until the next retrain cycle. The authors, Hector J. Garcia and Nick Clayton (published 2025-07-16), propose mutable sketches: each user's preferences are stored in a KP-tree, a sparse segment tree with sum aggregation. A low-rank projection is fitted once, and embeddings are recomputed on-the-fly as ratings arrive. The paper proves that each new observation monotonically tightens the prediction error envelope (Theorem 1), a guarantee lacking in FunkSVD and eALS. Experiments on KuaiRec show the mutable sketch achieves 0.810 RMSE reading only 1.8% of the data, compared to ALS's 0.822 RMSE at 100% data, with 8x faster per-batch updates. New users receive personalized recommendations in under 1 ms after their first rating without model retraining. A comparison of sampling strategies across density regimes shows KP-tree's norm-proportional sampling provides 40-130% better item coverage on sparse data (below 1% density), while uniform sampling suffices for dense matrices.
Paper Overview
- Field: Machine Learning
- Authors: Hector J. Garcia, Nick Clayton
- Published: 2025-07-16
- arXiv: 2507.12497
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 paper proposes 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.
The authors prove that each new observation monotonically tightens the prediction error envelope (Theorem 1), a guarantee that FunkSVD and eALS lack.
Key Results
- On KuaiRec, the mutable sketch achieves 0.810 RMSE at 1.8% data read, vs. ALS's 0.822 RMSE at 100% data, with 8x faster per-batch updates.
- A new user receives personalized recommendations in less than 1 ms after their first rating, with no model retraining required.
- 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 for dense matrices.
---
*Auto-collected on 2026-07-19*
This page is an English static mirror generated for search and AI citation.
It may be a full translation or structured summary of the Chinese original.
Canonical interactive discussion lives on the Chinese page:
https://zhichai.net/topic/178442251