Source: arXiv (ICML HiLD 2026) — 2026-07-22
Summary
This paper proposes clustering user inputs and running the LLM only on a representative member of each cluster, letting every other member simply inherit that output — but makes the approach provably safe by guaranteeing each member stays within a set similarity bound of its representative and matches on categorical attributes exactly. The two-stage algorithm runs Mini-batch K-Means to form initial clusters, then greedily picks representatives within each cluster using a method equivalent to the Johnson–Chvátal heuristic for Set Cover over similarity balls in embedding space. The authors report it's roughly 1000x faster than standard clustering baselines at matched cluster counts, and in a production deployment it cut downstream LLM computation 50-fold for a recommender system serving 38 million customers.
Key Takeaways
- Core idea: don't call the LLM per-user, call it once per cluster representative and propagate the output — but only where a per-sample similarity guardrail plus exact categorical-attribute matching make that substitution provably safe, not just "probably fine."
- Two-stage pipeline: Mini-batch K-Means for fast initial clustering, then a greedy representative-selection step equivalent to the Johnson–Chvátal Set Cover heuristic applied over similarity balls in embedding space.
- Reported ~1000x speedup over standard clustering baselines at matched cluster counts — the guardrail logic doesn't come at the cost of clustering throughput.
- Production result: 50x reduction in downstream LLM computation on a 38-million-customer recommender system, moving this from a theoretical technique to a validated at-scale cost lever.
- Addresses a real gap: existing clustering methods don't jointly guarantee minimum within-cluster similarity, exact categorical matching, and scalability to tens of millions of samples simultaneously.
Reel Script
Hook Running an LLM call per user across tens of millions of customers is the kind of cost that kills a product roadmap. A new paper shows how to cut that cost fifty-fold on a real 38-million-customer system, without just hoping similar users get similar answers.
Core Concept The trick sounds obvious at first: group similar inputs into clusters, run the expensive LLM call once per cluster on a representative example, and let every other member of that cluster just reuse the answer. The problem with that idea historically is trust — if your clustering is sloppy, two "similar" users end up sharing an answer that's actually wrong for one of them, and you have no way to bound how often that happens. This paper's contribution is making the substitution provably safe: every member of a cluster is guaranteed to sit within a measurable similarity distance of its representative, and any categorical attributes — things like account tier or region — have to match exactly, not just approximately. It's a two-step process: first a fast approximate grouping pass with Mini-batch K-Means, then a second pass that greedily picks the best representative inside each rough cluster, using a classic algorithm for the Set Cover problem — think of it as picking the fewest, best-placed "hub" points so that every other point is provably close enough to one of them.
Hands-On The two numbers worth writing down: the algorithm clusters roughly 1000x faster than standard baselines when you hold the number of clusters constant, so the safety guarantees aren't costing you clustering speed. Then, in an actual production deployment — a recommender system running against 38 million customers — this cut downstream LLM computation by 50x. That's not a synthetic benchmark; that's calls-per-day math that changes what's affordable to run at that scale.
Takeaway My verdict: this is the kind of unglamorous infrastructure paper that quietly makes previously-uneconomical LLM products viable at consumer scale — the provable guardrail is what separates it from "just cluster your embeddings," which teams have tried and gotten burned by. If you're running per-user LLM calls at any real scale, this clustering-plus-guardrail pattern is worth prototyping before you assume you need a smaller model instead. Follow for more on the cost-cutting techniques that actually hold up in production.