# Mutable Low-Rank Sketches for Retrain-Free Recommendation

arXiv: https://arxiv.org/abs/2607.15242 · HTML: https://mlsanity.com/paper/2607.15242/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 30 references that are in the map.
- First posted on arXiv 16 Jul 2026.

## Builds on (most cited first, 11 of 11)

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Neural Collaborative Filtering](https://mlsanity.com/paper/1708.05031/) (2017)
- [Fast Matrix Factorization for Online Recommendation with Implicit Feedback](https://mlsanity.com/paper/1708.05024/) (2017)
- [KuaiRec: A Fully-observed Dataset and Insights for Evaluating Recommender Systems](https://mlsanity.com/paper/2202.10842/) (2022)
- [A quantum-inspired classical algorithm for recommendation systems](https://mlsanity.com/paper/1807.04271/) (2018)
- [AutoEmb: Automated Embedding Dimensionality Search in Streaming Recommendations](https://mlsanity.com/paper/2002.11252/) (2020)
- [Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning](https://mlsanity.com/paper/1910.06151/) (2019)
- [Monolith: Real Time Recommendation System With Collisionless Embedding Table](https://mlsanity.com/paper/2209.07663/) (2022)
- [Quantum-inspired algorithms in practice](https://mlsanity.com/paper/1905.10415/) (2019)
- [Dynamic Embedding Size Search with Minimum Regret for Streaming Recommender System](https://mlsanity.com/paper/2308.07760/) (2023)
- [Optimal Matrix Sketching over Sliding Windows](https://mlsanity.com/paper/2405.07792/) (2024)

## Abstract (arXiv)

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.