Clustering a pile of customer messages, dialogue logs, or abstracts depends on which aspects of each document you compare. Two banking complaints may share a topic but differ in whether the customer lost a card or never received one. Classical joint feature selection and clustering, which chooses the informative input dimensions and the grouping together, attacks this by alternating between guessing clusters and re-weighting features. But its features are fixed columns of a numerical matrix, such as word counts or embedding coordinates. Those columns often do not encode the distinction that matters, and even when they do, nobody can say what a selected column means. We propose instead to make the features themselves learnable pieces of text. Each feature is a short question an LLM answers about every document, for example "Is the customer reporting a problem that already happened, or asking how to do something?". The set of questions is refined by textual gradients, which are natural-language critiques that an optimizer LLM turns into edits, in the style of TextGrad.
The part we think is new is where the critique comes from. Every textual gradient system in the file, including TextGrad, FlowBot, and Verbalized Machine Learning, builds its critique from ground-truth labels, unit tests, or a reward function. We build it only from the clustering's own evidence. That evidence has three parts: which questions a sparse feature selector assigned zero weight, which pairs of clusters swap or merge when the data is resampled, and which specific documents sit at those unstable boundaries. Put in two sentences: the LLM proposes questions, a numerical sparse clusterer decides which questions actually carve the data, and the documents the clusterer cannot place stably become the critique that drives the next question. If this works, the result is a clustering whose axes are readable questions. It is also a first test of whether textual gradients can be made reliable without any labels.
Core Claim
On fine-grained, high-cardinality text clustering, a question set refined by label-free textual gradients will beat both embedding-based clustering and a one-shot LLM-proposed question set of the same size and token budget. The gain will come from the boundary-document evidence in the critique, not from iteration or extra LLM calls alone. The claim fails, and should be abandoned, if a one-shot proposer shown the same number of documents matches the iterated method.
How It Differs From the Closest Work
Explaining Datasets in Words is the nearest neighbor. It relaxes natural-language predicates into embedding vectors, optimizes them with ordinary gradients, and then asks an LLM to name the resulting direction. Its clusters are defined by one predicate each, and its update signal is a continuous gradient in a frozen embedding space. We differ in three ways. Our text parameters are feature axes shared across all clusters, not per-cluster definitions. The clusters come out of a sparse clusterer run on the answers to those questions. And the update is a genuine textual critique grounded in instability evidence, with no embedding relaxation.
Two other works occupy LLM-guided clustering, and neither learns or selects features. ClusterLLM asks an LLM triplet and pairwise yes/no questions and fine-tunes a small embedder on the answers. LLM-MemCluster keeps a running memory of cluster labels and assigns documents directly. Neither ever produces an explicit, prunable description of what distinguishes clusters.
PAPO is the only work in the file that runs TextGrad without human labels. It does so by trusting majority-vote pseudo-labels, and it gets clustering structure only as a theoretical side effect. We borrow its lesson that self-generated supervision needs a guard against confirmation. Our guard is acceptance on a held-out split rather than seed confidence.
On the feature-selection side, NDFS supplies the numerical inner step. Dependence Guided Unsupervised Feature Selection supplies the motivation: features chosen apart from the clustering need not align with it. Those works select among given columns. We generate the columns.
Research Program
The method alternates two levels, mirroring the outer-structure/inner-parameter split that FlowBot found more stable than single-step rewriting.
Inner loop: answer the questions and cluster numerically. The current question set $Q$ holds $m$ short questions, each with a small closed answer set. An LLM answers all $m$ questions for each document in one batched call. The answers are one-hot encoded into a matrix $X \in \{0,1\}^{N \times p}$, where $N$ is the number of documents and $p$ is the total number of answer options. We then solve an NDFS-style problem:
$$\min_{F \ge 0,\; F^\top F = I,\; W} \; \mathrm{Tr}(F^\top L F) + \alpha \|XW - F\|_F^2 + \beta \sum_{q \in Q} \|W_q\|_F.$$
Here $F \in \mathbb{R}^{N \times K}$ is the soft cluster-indicator matrix for $K$ clusters, $L$ is the graph Laplacian of a nearest-neighbor graph built on $X$, and $W$ is the regression weight matrix. $W_q$ is the block of rows of $W$ belonging to the answer options of question $q$, so the group penalty switches off whole questions rather than individual answer options. $\alpha$ and $\beta$ trade off fitting the cluster indicators against sparsity.
Outer loop: build a critique from label-free evidence. After the inner loop converges, we assemble an evidence packet with three parts:
- The questions whose block norm $\|W_q\|$ fell near zero, together with sample answers. These are candidates for being irrelevant or redundant.
- Cluster pairs that frequently exchange members when the inner loop is re-run on bootstrap resamples.
- For each unstable pair, a handful of documents from each side of the boundary, taken from split A of the data.
The optimizer LLM receives this packet and returns a short critique of what the current questions fail to distinguish. It then proposes an edit: drop, rewrite, or add one question. This packet is the textual gradient. It is specific and contrastive, and no label enters it.
Acceptance on held-out data. An edit is accepted only if the bootstrap stability of the clustering on the disjoint split B improves by more than its resampling noise. Split B is never shown to the optimizer. This works like a line search. It is also our defense against the circular self-rationalization that section 2 of the file flags for PAPO.
$K$ is fixed to the benchmark value in the main experiments, because stability criteria are known to favor trivially coarse partitions when $K$ is free. Choosing $K$ with the question set is a secondary experiment.
Cost. Per-iteration cost is dominated by answering new questions. Old answers are cached, so an edit that adds one question costs one short call per document. Rewrites are scored first on a subsample of documents before full evaluation.
Baselines
The naive reference is a pre-trained sentence embedder, such as E5 or Instructor, followed by $k$-means with the true $K$. On Bank77, ClusterLLM reports 59.90% accuracy for such small embedders. We rerun this baseline ourselves on every dataset.
The strongest existing methods are two. On Bank77 it is ClusterLLM, which reports 70.13% accuracy with gpt-3.5-turbo. On the high-cardinality suite it is LLM-MemCluster, which reports an ARI of 68.9 on MTOP-I (versus 30.0 for the next best baseline) and roughly 54 ARI on Massive-D. These are the right competitors because they are the best published LLM-in-the-loop clusterers on exactly these benchmarks, and neither uses feature selection. That lets us isolate whether learned questions add anything beyond LLM judgment.
For fairness, we rerun both with the same LLM backbone we use for answering and optimizing, and we give them a matched total token budget. We report the published and reproduced numbers side by side. Beating them means exceeding the reproduced number on ARI and accuracy, averaged over at least three seeds, with a margin larger than the seed spread. It also means at least matching the published figure on MTOP-I and Bank77.
We also include Explaining Datasets in Words as a baseline, run under its predicate-clustering mode. The file reports only a 2% F1 gain over unnamed baselines on NYT, AG-News, and DBPedia. We found no reported result on Lacuna for it on Bank77, MTOP-I, or Massive-D, so we will run it ourselves.
Four ablations isolate the key ingredient:
- One-shot schema. An LLM proposes $m$ questions after seeing the same total number of documents the iterated method sees across all iterations. The questions are then clustered once with the identical inner loop. This is the decisive ablation.
- Scalar-guided mutation. Random question edits are accepted by the same held-out stability test, with no critique.
- Generic critique. The textual gradient is replaced by a generic "improve the features" request that carries no boundary documents.
- No sparsity. $\beta = 0$, so all questions are kept and the zero-weight evidence disappears.
Why not just…?
Why not just ask the LLM once for a good set of questions? This is the most serious threat. LLMs have strong priors about what distinguishes banking intents, so a single well-prompted proposal may already capture most of the distinctions. Nothing in the file rules this out. We settle it with the matched one-shot ablation above, which sees the same number of documents and has the same final question count. If the iterated method does not beat it by more than seed variance on the fine-grained datasets, the contribution reduces to "LLM-answered features for clustering." We would report that, rather than the textual-gradient claim. We expect the gap to be largest where the initial proposer lacks domain knowledge, which is why the Massive and MTOP domain/intent splits matter.
Why not just embed and run k-means, or tune the embedder as ClusterLLM does? The file already shows embedding plus $k$-means trailing LLM guidance: 59.90% versus 70.13% on Bank77 for ClusterLLM, and 30.0 versus 68.9 ARI on MTOP-I for LLM-MemCluster. Beating raw embeddings is therefore not the bar. Our claim against ClusterLLM is narrower: comparable or better accuracy together with an explicit, prunable account of what separates clusters. ClusterLLM cannot give that account, because its knowledge lives in fine-tuned embedder weights.
Why not just use LLM-MemCluster directly? It is the accuracy leader and may stay ahead on raw ARI. Its own authors report that it depends on hand-set bounds on the cluster count to avoid collapse or explosion, and that removing its memory drops Massive-D ARI from about 54 to about 7, which shows how much it leans on that single mechanism. Our method runs a principled clusterer on explicit features, so its behavior should not hinge on memory heuristics. The head-to-head on the six-dataset suite decides this. If LLM-MemCluster wins clearly, our remaining value is interpretability at a stated accuracy cost, and we will say so.
Why not just search over question sets with a scalar score? Scalar search is cheaper per step and needs no critique prompt. FlowBot reports that textual gradients reached a HoVer score of 63.20 versus 51.67 for GEPA, at $47.67 versus $130.95 for evolutionary AFlow. That evidence comes from supervised workflow search, though, and may not transfer. The scalar-mutation ablation, run under the same acceptance test and token budget, measures this directly as stability and ARI versus tokens spent.
Proposed Experiments
Datasets and metrics. The main benchmarks are Bank77 and the LLM-MemCluster suite: ArxivS2S, Massive-I, Massive-D, MTOP-I, FewNerd, and FewRel. We report accuracy, NMI, and ARI with labels used only for scoring. The work is restricted to text because the questions must be answerable from the document. Numerical "fat" data such as Carcinoma is out of scope.
Decisive checks. Three results decide the outcome.
The first is the one-shot-versus-iterated gap at matched budget.
The second is whether the label-free acceptance criterion actually tracks truth. Across all proposed edits, we compute the rank correlation between the change in held-out stability and the change in ARI. A weak or negative correlation would mean the loop optimizes a criterion that labels do not endorse, and it would falsify the premise that label-free textual gradients are reliable here. We also inspect whether accepted questions are stable but semantically trivial, for example questions about document length.
The third is an interpretability check. Annotators see only the final questions and the clusters' answer profiles, then assign held-out documents to clusters. Their accuracy is compared against the same task using top-weighted embedding dimensions or ClusterLLM cluster exemplars.
Diagnostic runs. We plot ARI against LLM tokens for all methods. We also run a seeded-failure test: we start from a deliberately poor question set, such as purely topical questions for an intent task, to see whether the boundary-document critique recovers the missing distinction when the other ablations do not.
References
- TextGrad: Automatic "Differentiation" via Text
- FlowBot: Inducing LLM Workflows with Bilevel Optimization and Textual Gradients
- Verbalized Machine Learning: Revisiting Machine Learning with Language Models
- Explaining Datasets in Words: Statistical Models with Natural Language Parameters
- ClusterLLM: Large Language Models as a Guide for Text Clustering
- LLM-MemCluster: Empowering Large Language Models with Dynamic Memory for Text Clustering
- In-context Demonstration Matters: On Prompt Optimization for Pseudo-Supervision Refinement
- Unsupervised Feature Selection Using Nonnegative Spectral Analysis
- Dependence Guided Unsupervised Feature Selection