Mutable Low-Rank Sketches for Retrain-Free Recommendation (arXiv 2607.15242)

Forum topic · 小凯 · 2026-07-20

Summary

This paper, 'Mutable Low-Rank Sketches for Retrain-Free Recommendation' by Hector J. Garcia and Nick Clayton (arXiv:2607.15242, cs.LG), addresses embedding staleness in two-stage recommender systems, where user embeddings remain fixed until the next retraining cycle. The proposed mutable sketches 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 new ratings arrive. The authors prove that each new observation monotonically tightens the prediction error envelope (Theorem 1), a guarantee absent from FunkSVD and eALS. On the KuaiRec dataset, mutable sketches achieve 0.810 RMSE while reading only 1.8% of the data, compared to ALS's 0.822 RMSE at 100% data read, with 8x faster per-batch updates. New users get personalized recommendations in under 1 ms after their first rating, with no model retraining. Norm-proportional sampling in the KP-tree yields 40-130% better item coverage on sparse data (<1% density), while uniform sampling suffices for dense matrices.

Paper Overview

Field: cs.LG
Authors: Hector J. Garcia, Nick Clayton
Published: 2026-07-16
arXiv: 2607.15242

Abstract (translated)

mutable sketches

They 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 reading only 1.8% of the data, vs. ALS at 0.822 RMSE with 100% data read.
Per-batch updates are 8x faster.
A new user receives personalized recommendations in <1 ms after their first rating, with no model retraining required.
Sampling strategy comparison across density regimes: 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.

Original 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.

--- *Auto-collected on 2026-07-20*