ArXiv

Mutable Low-Rank Sketches for Retrain-Free Recommendation

2026-07-16 · 17:39 UTC ·Hector J. Garcia, Nick Clayton ·1 min read
Authors
Hector J. Garcia, Nick Clayton
Categories
cs.LG
arXiv
https://arxiv.org/abs/2607.15242v1
PDF
https://arxiv.org/pdf/2607.15242v1

Brief

Mutable Low-Rank Sketches use a KP-tree to maintain sparse per-user preference sketches and a single low-rank projection to produce embeddings on arrival, enabling retrain-free updates. The paper proves monotonic tightening of the error envelope (Theorem 1) and reports strong KuaiRec results (0.810 RMSE at 1.8% read, 8× faster updates). Only the abstract was available.

Why it matters

Mutable sketches store each user in a KP-tree (a sparse segment tree with sum aggregation), fit one low-rank projection, and recompute embeddings on-the-fly; Theorem 1 shows each new observation monotonically tightens the prediction-error envelope (a guarantee FunkSVD and eALS lack).

Key details

  • On KuaiRec the mutable sketch achieves 0.810 RMSE while reading 1.8% of the data versus ALS at 0.822 RMSE using 100% of data; per-batch updates are 8× faster and a new user gets personalized recommendations in <1 ms after their first rating with no retraining.
  • KP-tree norm-proportional sampling yields 40–130% better item coverage on very sparse matrices (<1% density), while uniform sampling is adequate for dense matrices.
Source evidence

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.

Comment: 6 pages, 3 figures, 8 tables