Efficient Clustering with Quality Guardrails for LLM-based Recommender Systems at Industry Scale

Abstract

LLMs can be prohibitively expensive and slow to run at scale, especially for applications that invoke an LLM per sample over millions of inputs. A natural way to scale is to cluster the inputs, run the LLM only on cluster representatives, and propagate the outputs to other cluster members. However, the outputs a member receives are only as good as its match to the representative. Off-the-shelf clustering methods optimize an aggregate objective, targeting average-case quality without per-sample guardrails. As a result, members can be assigned to poorly-matched representatives, and the inherited outputs -- though appropriate for the representative -- may be irrelevant or even unsafe for the member. For example, a parent of a toddler grouped with parents of older children could receive age-inappropriate recommendations. Most clustering methods also scale poorly to millions of inputs in runtime and memory, limiting their use at industry scale. We propose a scalable two-stage clustering algorithm with provable per-sample guardrails: every sample is guaranteed to share a user-specified minimal embedding similarity and exact attribute match with its representative. The algorithm first generates initial clusters with Mini-batch K-Means, then greedily selects representatives within each to satisfy the guardrails. We provide theoretical guarantees, complexity analysis, and benchmarks against common methods on internal and public datasets. Our method delivers per-sample guardrails while running substantially faster and scaling to data sizes where most standard methods become intractable. We demonstrate its impact in a real-world deployment clustering 38 million customers, reducing downstream LLM cost and runtime by 50-fold while preserving personalization. This unblocked the launch of a persona-based recommender system that delivers significant gains in revenue and engagement in an A/B test.

V1 accepted at High Dimensional Learning Dynamics workshop, ICML 2026 (non-archival), V2 accepted at The Third Workshop on Agentic and Generative AI for E-Commerce, RecSys 2026 (non-archival)