Efficient Clustering with Provable Guardrails for LLM Inference at Scale

📄 arXiv: 2607.19704v1 📥 PDF

作者: Longshaokan Wang, Wai Tsang Keung, Punit Ghodasara, Roman Wang, Ali Dashti, Francesc Moreno-Noguer

分类: cs.LG, stat.ML

发布日期: 2026-07-22

备注: Accepted for presentation at ICML HiLD workshop 2026 (non-archival)

💡 一句话要点

提出高效聚类方法以降低大规模LLM推理成本

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大规模语言模型 聚类算法 推理优化 个性化推荐 高效计算

📋 核心要点

  1. 现有聚类方法在大规模应用中无法保证每个样本的质量控制，导致推理成本和延迟高。
  2. 本文提出的两阶段算法通过Mini-batch K-Means生成初始聚类，并贪婪选择聚类代表，确保相似性和属性控制。
  3. 实验结果表明，该方法在速度上比传统聚类方法快10-1000倍，并成功应用于3800万用户的推荐系统中，降低了50倍的成本和延迟。

📝 摘要（中文）

随着基于大规模语言模型（LLM）应用的用户数量激增，推理成本和延迟成为主要瓶颈。本文提出了一种聚类输入的方法，仅对聚类代表进行LLM调用，从而让其他成员继承输出。现有聚类方法无法在大规模下提供每个样本的质量控制。我们提出的两阶段算法通过Mini-batch K-Means生成初始聚类，并在每个聚类内贪婪选择代表，确保相似性和属性的控制。该算法在处理速度上比传统方法快10-1000倍，并成功应用于3800万用户的个性化推荐系统中，显著降低了下游成本和延迟。

🔬 方法详解

问题定义：本文旨在解决大规模LLM推理中的高成本和延迟问题。现有聚类方法无法在大规模下提供每个样本的质量控制，导致推理效率低下。

核心思路：我们提出了一种两阶段的聚类算法，首先使用Mini-batch K-Means生成初始聚类，然后在每个聚类内贪婪选择代表。这种设计确保了聚类内样本的相似性和属性一致性。

技术框架：算法分为两个主要阶段：第一阶段使用Mini-batch K-Means进行初始聚类，第二阶段在每个聚类中选择代表。该算法在时间复杂度和内存使用上均表现出色，适应性强。

关键创新：本研究的主要创新在于提供了每个样本的相似性和属性控制，且算法在大规模数据集上表现出色，显著提高了处理速度。与现有方法相比，我们的方法在保证质量的同时，极大地提升了效率。

关键设计：算法的时间复杂度为O(nd + n^2 d/K)，内存复杂度为O(nd + n^2/K^2)，其中n为样本数量，d为特征维度，K为初始聚类数量。该设计使得算法在K与n成比例增长时仍能保持线性复杂度。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果显示，本文提出的聚类方法在处理速度上比传统方法快10-1000倍，且在3800万用户的个性化推荐系统中成功降低了下游成本和延迟达50倍。这一显著提升展示了该方法在实际应用中的巨大潜力。

🎯 应用场景

该研究的聚类方法可广泛应用于个性化推荐系统、在线服务和大规模数据处理等领域。通过降低推理成本和延迟，能够提升用户体验并支持更多用户的同时访问。未来，该方法有潜力推动更多基于LLM的应用落地，促进智能服务的发展。

📄 摘要（原文）

Scaling LLM-based applications to millions of users is bottlenecked by the inference cost and latency of modern foundation models. A natural fix is to cluster the inputs and call the LLM only on cluster representatives, letting other members inherit the output -- but this is only safe if each member is measurably close to its representative. Existing clustering methods do not offer such per-sample quality control at scale: none jointly guarantee a minimal within-cluster similarity, exact matching of categorical attributes, and scalability to tens of millions of samples. We propose a two-stage algorithm that generates initial clusters with Mini-batch K-Means, then greedily selects representatives within each initial cluster -- a step equivalent to the Johnson-Chvatal heuristic for Set Cover over alpha-balls in embedding space. The algorithm enforces the similarity and attribute guardrails exactly by construction, and runs in $O(nd + n^2 d/K)$ time and $O(nd + n^2/K^2)$ memory for $n$ samples, feature dimension $d$, and $K$ initial clusters -- linear in $n$ when $K$ grows proportionally with $n$. We provide benchmarks against common clustering methods on internal and public datasets: our method not only delivers per-sample guardrails but also runs 10-1000x faster and scales to data sizes where most standard methods become intractable. Deployed on 38 million customers for a persona-based recommender, the clustering method cut downstream cost and latency by 50-fold while preserving personalization and unblocked the production launch.