RAILS: Retrieval-Augmented Incremental LLM Clustering at Scale

Armin Oliya; Aleksandra Sawczuk; Radosław Białobrzeski

cs.LGSep 21, 2026

RAILS: Retrieval-Augmented Incremental LLM Clustering at Scale

Authors: Armin Oliya, Aleksandra Sawczuk, Radosław Białobrzeski

Abstract

Using a Large Language Model (LLM) as the clusterer at production scale is hard: prompts cannot hold the entire label space, and per-document serial processing does not deliver the throughput real workloads require. We present RAILS, a retrieval-augmented incremental LLM clusterer that turns clustering into a simple loop over a growing label pool and scales through document batching with bounded concurrency. On six public benchmarks RAILS exceeds the strongest prior LLM-clustering method on average, lifting accuracy from 51.2% to 59.3%, NMI from 67.2% to 74.8%, and ARI from 45.4% to 54.7%. We further report production-deployment evidence from a SaaS ticket-topic-discovery pipeline, where RAILS has replaced a traditional HDBSCAN stage with higher clustering quality, transparent prompt-driven control, and stateful incremental operation.

Explore similar work

Efficient Clustering with Provable Guardrails for LLM Inference at Scale
Jul 22, 2026Longshaokan Wang, Wai Tsang Keung, Punit Ghodasara +3Image Clustering LLM Inference Efficiency
Agentic Clustering: Controllable Text Taxonomies via Multi-Agent Refinement
May 31, 2026Simon Löwe, Emily SilcockMulti-Agent Large Language Model Systems Agentic Tool Use
Cluster, Route, Escalate: Cascaded Framework for Cost-Aware LLM Serving
Jun 25, 2026Yasmin Moslem, Magdalena Kacmajor, Vasudevan Nedumpozhimana +11Large Language Model Serving Escalation

Jul 22, 2026 · cs.LGJ/K move · Enter open · S save

Efficient Clustering with Provable Guardrails for LLM Inference at Scale

Longshaokan Wang, Wai Tsang Keung, Punit Ghodasara, Roman Wang+2

Amazon

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.

Image Clustering LLM Inference Efficiency Scalability Inference Cost Semantic Similarity Metrics Streaming Guardrails

Open paper Ask about it PDF

Abstract

Explore similar work

Efficient Clustering with Provable Guardrails for LLM Inference at Scale

Agentic Clustering: Controllable Text Taxonomies via Multi-Agent Refinement

Cluster, Route, Escalate: Cascaded Framework for Cost-Aware LLM Serving