Search papers, labs, and topics across Lattice.
This paper introduces a two-stage clustering algorithm designed to enhance the efficiency of LLM inference by ensuring measurable quality control for each input member relative to its cluster representative. By leveraging Mini-batch K-Means for initial clustering and a greedy selection process for representatives, the method guarantees minimal within-cluster similarity and exact matching of categorical attributes. The approach not only scales effectively to tens of millions of samples but also achieves significant performance improvements, reducing inference costs and latency by up to 50-fold in real-world applications.
Clustering LLM inputs can cut inference costs and latency by 50-fold while maintaining personalization, a game-changer for scaling AI applications.
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.
