PaperlayerView exact revision on arXiv

Source-linked AI summary

Large Language Models Enable Few-Shot Clustering

Vijay Viswanathan, Kiril Gashteovski, Carolin Lawrence, Tongshuang Wu, Graham Neubig

arXiv:2307.00524v1cs.CL

TL;DR

Semi-supervised clustering can capture an expert’s intent, but existing interactive approaches may demand substantial feedback. This paper tests whether an LLM can amplify a few demonstrations through representation enrichment, pairwise constraints, and correction; keyphrase expansion is consistently effective, while the approaches differ in query cost and benefit.

  • Problem

    Clustering is underspecified without an expert’s desired structure, while interactive semi-supervised methods can require substantial expert feedback.

    Source: §1 · p. 1

  • Method

    The paper incorporates LLMs by enriching document representations with generated keyphrases, using an LLM as a pairwise-constraint pseudo-oracle, and correcting low-confidence cluster assignments.

    Source: §2.1 · p. 2, §1 · p. 2, §2.2 · p. 3

  • Results

    LLM keyphrase expansion improves every metric over K-Means across the tested datasets; pairwise constraints can be effective but require more queries, while post-correction has limited upside.

    Source: §1 · p. 2

  • Takeaways & Limitations

    LLMs are most consistently useful for enriching document representations, supporting further exploration of document expansion for clustering.

    Source: §6 · p. 8

    Entity canonicalization by shared surface form has irreducible errors for polysemous phrases, such as “Marseille.”

    Source: §5.1 · p. 5

Abstract

from arXiv · show

Unlike traditional unsupervised clustering, semi-supervised clustering allows users to provide meaningful structure to the data, which helps the clustering algorithm to match the user's intent. Existing approaches to semi-supervised clustering require a significant amount of feedback from an expert to improve the clusters. In this paper, we ask whether a large language model can amplify an expert's guidance to enable query-efficient, few-shot semi-supervised text clustering. We show that LLMs are surprisingly effective at improving clustering. We explore three stages where LLMs can be incorporated into clustering: before clustering (improving input features), during clustering (by providing constraints to the clusterer), and after clustering (using LLMs post-correction). We find incorporating LLMs in the first two stages can routinely provide significant improvements in cluster quality, and that LLMs enable a user to make trade-offs between cost and accuracy to produce desired clusters. We release our code and LLM prompts for the public to use.

1 Introduction

Clustering is underspecified, and existing expert-guided methods can require substantial feedback. This paper asks whether an LLM can amplify a few expert demonstrations; its experiments find keyphrase expansion consistently improves clustering, while other LLM uses trade off effectiveness and query cost.

1 Introduction

  • Traditional unsupervised clustering cannot know which organization a domain expert wants without that need being specified.The paper characterizes clustering as fundamentally underspecified, citing Caruana (2013).Source: §1 · p. 1
  • Prior interactive methods give experts control but can require 20–100 interactions, making feedback costly on large datasets with many possible clusters.The interaction range is reported for a simulation using split/merge, pairwise constraints, and lock/refine.Source: §1 · p. 1
  • The paper asks whether an expert can give an LLM a few demonstrations of desired interactions, such as pairwise constraints, and let it direct clustering.The proposal builds on work using LLMs as noisy simulations of human decision-making.Source: §1 · p. 1
  • LLM keyphrase expansion improves cluster quality on every metric across all tested datasets; pairwise pseudo-oracle constraints can be effective but require more queries, and post-correction offers limited upside.The methods were tested on five datasets across entity canonicalization, intent clustering, and tweet-topic grouping; LLM-assisted methods can approach human-oracle semi-supervised clustering at a fraction of the cost.Source: §1 · p. 2
  • LLM-based representation expansion and post-correction can be added as plug-ins to text clustering algorithms, while the pseudo-oracle pairwise-constraint method requires K-Means.The authors report that an instruction alone, without demonstrations, adds significant value in their prompt investigation.Source: §1 · p. 2

2 Methods to Incorporate LLMs

The methods use an LLM before, during, or after clustering: to enrich document representations, supply pairwise constraints, or correct uncertain assignments.

2.1 Clustering via LLM Keyphrase Expansion

  • Before clustering, an LLM generates keyphrases for each document; an embedding model encodes them, and their embedding is concatenated with the original document representation.The aim is to make representations task-dependent by highlighting aspects relevant to the clustering need.Source: §2.1 · p. 2

2.2 Pseudo-Oracle Pairwise Constraint Clustering

  • During clustering, an LLM acts as a pairwise-constraint pseudo-oracle, with text-clustering pairs selected through Explore-Consolidate and entity-canonicalization pairs chosen among closest distinct points.The resulting constraints are used with PCKMeans; the prompt includes up to four demonstrations of pairwise constraints.Source: §2.2 · p. 3

2.3 Using an LLM to Correct a Clustering

  • After clustering, the method checks low-confidence points against representatives of their assigned clusters and tests alternatives among the four next-closest clusters when needed.Low confidence is identified using the points with the smallest margin between their nearest and second-nearest clusters; points are reassigned on a positive LLM judgment and otherwise retain their assignment.Source: §2.3 · p. 3

3 Tasks

The paper studies entity canonicalization and short-text clustering, describing their data, task definitions, and evaluation measures.

3.1 Entity Canonicalization

  • Entity canonicalization groups noun phrases that refer to the same entity; the task includes hundreds or thousands of clusters, often with few points per cluster.The experiments use OPIEC59k and ReVerb45k, with 490 and 6,700 ground-truth clusters, respectively.Source: §3.1 · pp. 3–4
  • Entity canonicalization is evaluated with macro, micro, and pairwise precision and recall, combined into the corresponding F1 measures.The passage defines each precision and recall measure in terms of predicted and gold clusters or linked point pairs.Source: §3.1 · p. 4

3.2 Text Clustering

  • Short-text clustering covers Bank77 and CLINC user queries and Tweet topics, evaluated against ground truth using normalized mutual information and Hungarian-aligned accuracy.The datasets contain queries or tweets assigned to intent or topic categories.Source: §3.2 · p. 4

4 Baselines

The baselines include task-specific K-Means on embeddings and contrastive-learning clustering methods for text.

4.1 K-Means on Embeddings

  • The K-Means baseline uses task-specific features and cluster counts, with entity mentions clustered through their unique surface forms before assignments are mapped back to mentions.The described K-Means procedure uses K-Means++ initialization.Source: §4.1 · pp. 4–5
  • For entity canonicalization, a simplified multi-view approach concatenates fine-tuned context- and fact-view encodings and applies K-Means in a shared vector space, matching the original reported performance.The original approach alternates between views and uses conflict resolution when their clusterings disagree.Source: §4.1 · p. 5

4.2 Clustering via Contrastive Learning

  • SCCL and ClusterLLM are comparison methods based on contrastive learning; ClusterLLM also uses LLM triplet feedback to choose cluster granularity from a hierarchy.The paper describes both as more complicated and compute-intensive than its proposed methods.Source: §4.2 · p. 5

5 Results

LLM keyphrase expansion is the strongest reported approach across canonicalization and text-clustering comparisons, while LLM-generated pairwise constraints also perform strongly on some datasets. The results qualify surface-form clustering for polysemous mentions and examine what prompt components contribute to text expansion.

5.1 Summary of Results

  • Surface-form clustering has irreducible errors for polysemous mentions, although the Shen et al. (2022) baseline is near-optimal on some metrics, particularly for ReVerb45k.For example, “Marseille” can refer to either the city or the athletic club.Source: §5.1 · p. 5
  • Keyphrase expansion achieved state-of-the-art results on both canonicalization datasets and significantly outperformed KMeans on every text-clustering dataset considered.The comparisons are reported in Table 1 for entity canonicalization and Table 2 for text clustering.Source: §5.1 · p. 5, Table 1 · p. 6, Table 2 · p. 6
  • LLM-pseudo-labeled pairwise constraints achieved strong performance on 3 of 5 datasets, including a new state-of-the-art result on OPIEC59k.Source: §5.1 · p. 6

5.2 LLMs excel at text expansion

  • Keyphrase Clustering was best on 3 of 5 datasets and comparable to pseudo-oracle PCKMeans on the other 2.Source: §5.2 · p. 6
  • The text-expansion ablation compared prompts with and without instructions or demonstration examples on OPIEC59k and CLINC.The supplied passages describe the ablation setup but do not report its outcomes.Source: §5.2 · p. 6

Avg F1 Acc NMI

GPT-3.5 keyphrase clustering outperforms instruction-finetuned encoders in the reported comparison, while prompt components and post-correction have distinct effects. Pairwise pseudo-oracle feedback can improve Macro F1, but its cost and sensitivity to noisy feedback shape when it is useful.

Avg F1 Acc NMI

  • GPT-3.5-based Keyphrase Clustering outperforms instruction-finetuned encoders of different sizes, even with the same prompt.The comparison concerns LLM intervention with demonstrations or instructions removed.Source: Table 3 · p. 6
  • Using both instructions and demonstrations gives the most consistent positive effect on cluster quality.Instructions alone produce more keyphrases with less consistency; demonstrations alone produce a more focused set that can miss the desired aspect.Source: Avg F1 Acc NMI · pp. 6–7
  • Scale is not solely responsible for GPT-3.5's advantage, and the authors speculate instruction-finetuned encoders cannot support the detailed prompts that help few-shot clustering.Instructor-XL performs poorly with the same prompt used for GPT-3.5, while the authors note that their Instructor prompts are brief.Source: Avg F1 Acc NMI · p. 7

5.3 The limitations of LLM post-correction

  • 0.1–5.2 absolute points of improvement: LLM post-correction gives small gains across datasets and metrics.When asked to reconsider the 500 most-uncertain assignments, the LLM changes only a small minority and is disproportionately inaccurate on low-confidence points.Source: §5.3 · p. 7

5.4 How much does LLM guidance cost?

  • Pairwise-constraint pseudo-labeling has the greatest API cost in the experiments, while Keyphrase Correction's cost scales linearly with dataset size.The authors describe this scaling as infeasible for clustering very large corpora.Source: §5.4 · p. 7, Table 5 · p. 7

5.5 Using an LLM as a pseudo-oracle is cost-effective

  • For OPIEC59k, $41 in worker wages would buy fewer than 700 human labels, compared with 20K GPT-3.5 labels at the same cost.The estimate assumes an $11-per-hour wage and an annotator labeling roughly three pairs per minute.Source: §5.5 · p. 7
  • With sufficient pseudo-oracle feedback, pairwise-constraint K-Means improves Macro F1 without dramatically reducing Pairwise or Micro F1.Figure 5 compares feedback amounts on OPIEC59k and also shows the algorithm's sensitivity to a noisy oracle.Source: §5.5 · p. 7, Figure 5 · p. 8
  • At the reported price point, GPT-3.5 is more effective than a true pairwise-constraint oracle; the latter needs at least 2500 labeled pairs to deliver value for entity canonicalization.The authors conclude that querying an LLM is more cost-effective than hiring a human labeler when maximizing empirical performance.Source: §5.5 · p. 8

6 Conclusion

The conclusion reports consistent clustering improvements from simple LLM interventions across varied text-clustering tasks. Representation enrichment is the most consistently useful approach in the authors' findings.

6 Conclusion

  • Simple LLM interventions provide consistent improvements to cluster quality across a variety of text-clustering tasks.The authors characterize their work as a proof of concept.Source: §6 · p. 8
  • Enriching document representations is the most consistently useful role for LLMs in the reported work.The authors say this finding motivates more elaborate approaches to document expansion via LLMs.Source: §6 · p. 8
  • The authors present their findings as motivation for more elaborate LLM-based document-expansion approaches.They describe the work as a simple proof of concept.Source: §6 · p. 8

A Pairwise Constraint Pseudo-Oracle Prompt

The prompt excerpt describes a task-specific pairwise-constraint pseudo-oracle prompt and its demonstration examples. It includes an example prompt for reference.

A Pairwise Constraint Pseudo-Oracle Prompt

OPIEC59k Prompt

The OPIEC59k prompt asks the model to judge whether entity names would link to the same Wikipedia article. It uses context sentences and strict criteria to help resolve ambiguity.

OPIEC59k Prompt

  • The prompt asks whether two entity names would likely link to the same Wikipedia article when used as separate anchor text.Entity names may be truncated, abbreviated, or ambiguous.Source: OPIEC59k Prompt · p. 10
  • For each entity, the prompt supplies up to three Wikipedia context sentences, all linking to the same article.The examples are intended to aid in resolving ambiguity between entities with similar or overlapping meanings.Source: OPIEC59k Prompt · p. 10
  • The prompt says context sentences may not represent typical usage, but should help resolve ambiguity.Source: OPIEC59k Prompt · p. 10
  • The decision should use criteria including shared contexts, topic, and domain and scope of meaning.Source: OPIEC59k Prompt · p. 10
  • The task counts as successful when entities are grouped consistently by the Wikipedia articles they refer to.Source: OPIEC59k Prompt · p. 10

B Keyphrase Expansion Prompt

The section presents a domain-specific prompt for keyword expansion, using four entities from each dataset as demonstrations and providing the exact prompts.

B Keyphrase Expansion Prompt

OPIEC59k Prompt

The prompt asks for alternate names for Wikipedia entity strings based on the article title they refer to, using context sentences to disambiguate them.

OPIEC59k Prompt

  • The prompt requests comprehensive alternate-name lists for Wikipedia entity strings, with context sentences to clarify the intended referent.It asks for the lists in JSON format.Source: OPIEC59k Prompt · p. 11
  • The examples also include the generic entity string “fictional character” and outputs such as “fictional characters,” “characters,” and “character.”Source: OPIEC59k Prompt · pp. 11–12
  • Another example supplies Catholicism context sentences and alternate names including “Catholic Church,” “Roman Catholic,” and “Catholic.”Source: OPIEC59k Prompt · p. 12
  • For “Earth, Wind & Fire,” context sentences accompany the alternate names “Earth & Fire,” “Earth,” and “Wind & Fire.”Source: OPIEC59k Prompt · p. 12
  • The prompt pairs Queen Elizabeth context sentences with the alternate names “Elizabeth II” and “HM.”Source: OPIEC59k Prompt · p. 12
  • For Napoleon, context sentences accompany the alternate names “Napoleon Bonaparte,” “Emperor Napoleon,” and “Napoleon I.”Source: OPIEC59k Prompt · p. 12

Related papers

Loading 2307.00524v1…