这篇论文提出了一种不用重训练就能实时更新用户嵌入的方法，用KP-tree存储偏好，在KuaiRec上只用1.8%数据就比ALS效果好，速度还快8倍。
推荐系统两阶段架构中嵌入陈旧性是常见瓶颈：用户对新物品评分后，其嵌入需等待重训练循环才能更新。论文提出可变草图方法，用KP-tree（带求和聚合的稀疏线段树）存储用户偏好，仅需一次低秩投影就能在评分到达时动态重算嵌入。理论证明每新增观测值都会单调收紧预测误差范围（Theorem 1），这是FunkSVD和eALS不具备的保证。在KuaiRec数据集上，可变草图仅读取1.8%的数据就达到0.810 RMSE，而ALS使用100%数据为0.822，且每批更新速度提升8倍。新用户在首次评分后不到1毫秒即可获得个性化推荐，无需任何模型重训练。
Mutable Low-Rank Sketches for Retrain-Free Recommendation
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.