Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces mutable sketches, a novel approach to address the staleness of user embeddings in two-stage recommendation systems by utilizing a KP-tree for on-the-fly embedding updates. The method allows for real-time personalization, achieving a root mean square error (RMSE) of 0.810 with significantly reduced data read and faster updates compared to traditional methods like ALS. Notably, new users receive personalized recommendations in under 1 ms after their first rating, demonstrating the efficiency and effectiveness of the proposed solution.
Mutable sketches enable real-time updates to user embeddings, achieving personalized recommendations in under 1 ms without retraining the model.
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.