New Clustering Method Scales LLM Inference with Guardrails

Scaling large language model (LLM) applications to millions of users faces significant bottlenecks due to inference costs and latency. A common strategy involves clustering inputs and processing only cluster representatives, with other members inheriting the output. However, existing clustering methods often lack the ability to provide per-sample quality control, such as guaranteeing minimal within-cluster similarity or exact matching of categorical attributes, especially at scale. This paper proposes a two-stage algorithm to address these limitations. It first generates initial clusters using Mini-batch K-Means, then greedily selects representatives within each cluster, a process akin to the Johnson-Chvatal heuristic for Set Cover. This approach inherently enforces similarity and attribute guardrails and scales efficiently, running in near-linear time for large datasets. Benchmarks show it is 10-1000x faster than standard methods and capable of handling data sizes where others fail. A deployment for 38 million customers cut downstream costs and latency by 50-fold, enabling a production launch for a persona-based recommender system.