---
title: "Mutable Low-Rank Sketches for Retrain-Free Recommendation"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2607.15242v1"
permalink: "https://feed.astralor.com/items/itm_5fc509f605f273c4cd40c508"
published: "2026-07-16T17:39:38.000Z"
score: 78
channel: "ai"
tags: ["ALS","KP-tree","Low-rank Decomposition","Mutable Sketch","Recommender System","Norm-Proportional Sampling"]
---

# Mutable Low-Rank Sketches for Retrain-Free Recommendation

## AI commentary

> This paper hits the core pain point of online recommendation systems: embedding staleness. I especially appreciate the theoretical guarantee (Theorem 1) and the comparative analysis of sampling strategies. For recommendation engineers and data scientists, this is a practical solution that directly reduces retraining costs and improves cold-start experiences.

## At a glance

This paper proposes mutable sketches that store user 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 without retraining. 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. New users receive personalized recommendations in <1 ms after their first rating. The KP-tree's norm-proportional sampling provides 40-130% better item coverage on sparse data (<1% density) compared to uniform sampling.

## Key points

- Proposes mutable sketches to solve embedding staleness, enabling real-time updates without retraining.
- KP-tree implements sum-aggregated sparse segment tree, fits low-rank projection once, and recomputes embeddings dynamically.
- On KuaiRec, mutable sketch achieves 0.810 RMSE with 1.8% data vs. ALS 0.822 with 100% data, 8x faster batch updates.
- KP-tree's norm-proportional sampling improves coverage by 40-130% on sparse data, while uniform sampling suffices on dense matrices.

## Full text

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.

---

Verify against the original before citing; curated by Astral Feed: https://feed.astralor.com/items/itm_5fc509f605f273c4cd40c508