Optimized Algorithms for Text Clustering with LLM-Generated Constraints

Conference: AAAI 2026
arXiv: 2601.11118
Code: https://github.com/weihong-wu/LSCK-HC
Area: AIGC Detection / Text Clustering
Keywords: Text Clustering, LLM constraint generation, k-means, semi-supervised clustering, local search

TL;DR

Proposes the LSCK-HC framework, which utilizes LLMs to generate must-link/cannot-link constraints in set formats (rather than traditional pairwise constraints), and integrates with a penalized local search clustering algorithm. It achieves clustering accuracy comparable to SOTA on 5 short text datasets while reducing the number of LLM queries by over 20 times.

Background & Motivation

Background: Short Text Clustering (STC) is a fundamental task in NLP, with k-means and its variants being widely used. To improve clustering quality, semi-supervised approaches introduce pairwise must-link (ML) and cannot-link (CL) constraints as prior knowledge. Recently, LLMs have been utilized to automatically generate these constraints via In-Context Learning.

Limitations of Prior Work: (1) Traditional constraint generation relies heavily on manual annotation by experts or existing labels, which is highly expensive; (2) Using LLMs to generate pairwise constraints (such as the FSC method) requires a massive number of queries (often tens of thousands), which is extremely costly and yields limited improvements; (3) Constraints generated by LLMs may contain noise or errors, yet existing clustering algorithms are not specifically optimized for the characteristics of LLM-generated constraints.

Key Challenge: The query efficiency for pairwise constraints is extremely low; each LLM call only determines the relation between two specific points, requiring an exponential number of queries to cover a sufficient proportion of the dataset. Furthermore, because generated constraints inevitably contain errors, the balance between hard constraint satisfaction and soft constraint penalization has not been optimized for characteristics unique to LLM outputs.

Goal: (1) Reduce the query cost of LLM-based constraint generation; (2) Improve the accuracy of the generated constraints; (3) Design clustering algorithms robust to noisy or erroneous constraints.

Key Insight: Extend the constraint format from pairwise to set-based, allowing one LLM query to generate multiple relationships, and differentiate hard/soft constraints using confidence thresholds.

Core Idea: Replace pairwise constraints with set-based constraints to improve query efficiency, and employ a penalized local search to tolerate erroneous constraints generated by the LLM.

Method

Overall Architecture

The input short text dataset is encoded into vectors using embedding models (e.g., Instructor-large or E5). The framework consists of two phases: (1) Constraint Generation: Candidate point sets are selected, and LLMs are queried to determine relationships, thereby generating collections of ML/CL constraints; (2) Constrained Clustering: Hard ML constraints are utilized to initialize clustering centroids, soft ML constraints are processed via penalized merging, and CL constraints are handled through max-weight matching integrated with local search.

Key Designs

1. Set-Based Must-Link Constraint Generation:

   • Function: Generates multiple ML relations within a single LLM query, rather than determining them pairwise.
   • Mechanism: Divides the data into representative subsets based on coreset techniques, where points within each subset are similar to each other. The texts corresponding to a subset are sent to the LLM, which returns grouped results (e.g., \(\{t_1, t_2, t_3\}, \{t_4\}\)). Every group containing 2 or more texts forms an ML set constraint.
   • Design Motivation: Coreset ensures that the selected candidate points do not differ excessively along a single dimension, thereby enhancing the LLM's judgment accuracy; the set representation allows a single query to cover multiple constraint relationships.

2. Confidence-Based Differentiation of Hard/Soft ML Constraints:

   • Function: Categorizes ML constraints into high-confidence (hard) and low-confidence (soft) based on the consistency of the LLM responses.
   • Mechanism: Computes pairwise distances or diameters within the constraint sets over different grid scales \(r_j = (1+\varepsilon)^j \cdot \sqrt{cost_{kc}/10n\delta}\), and uses binary search to find a distance threshold \(\psi\). For each candidate threshold, the LLM is queried multiple times (5 times for pairwise, 10 times for sets). If all responses are consistent, ML constraints below this diameter threshold are classified as hard constraints.
   • Design Motivation: Hard constraints are utilized in the initialization phase (affecting seed selection in k-means++), where erroneous constraints introduce higher risks; thus, high-confidence filtering is essential.

3. Cannot-Link Constraint Generation:

   • Function: Generates set-based CL constraints containing at most \(k\) elements.
   • Mechanism: Standard uniformly samples candidate points \(q\) from uncovered points whose distance from the current CL set exceeds the threshold \(r = cost_{kc}\). The LLM determines whether \(q\) should be joined to the current CL set. If the LLM returns "None", the point is added; otherwise, the search for the next point continues until the CL set size reaches \(k\) or no new points can be found.
   • Design Motivation: The distance threshold ensures that the candidate points indeed originate from different clusters, simplifying the LLM's classification task.

4. Penalized ML Clustering (Alg. 1):

   • Function: Handles the assignment of soft ML constraints.
   • Mechanism: For each soft ML set \(X\), points are initially assigned to physical nearest centroids, forming sub-partitions. The algorithm iteratively selects two partitions \(P_i, P_j\) with the largest diameter and compares the merging cost against the cost of keeping the original assignment plus penalties: if \((w_m + d(\bar{P_j}, c_j)) \cdot |P_j| + (w_m + d(\bar{P_i}, c_i)) \cdot |P_i| > \sum_{p \in P_i \cup P_j} d(p, c_{ij})\), they are merged. The runtime complexity is \(O(nk^2)\).

5. Penalized CL Clustering (Alg. 2):

   • Function: Processes CL constraints using maximum weight matching paired with local search.
   • Mechanism: For each CL set \(Y\), an auxiliary bipartite graph \(G(C, Y; E)\) is constructed to compute the maximum weight matching between centroids and CL points. For each point in the match, the variation \(g_y\) upon its removal is calculated. If the maximum variation is below a threshold, the current match is accepted; otherwise, the point is removed and assigned to its nearest centroid.

Loss & Training

This work introduces a clustering algorithm rather than a deep learning training routine. The core objective function is the traditional k-means objective combined with penalties for constraint violations: $\(\sum_{i=1}^{k} \sum_{x \in A_i} \|x - c(A_i)\|^2 + w_m \cdot (\text{ML violations}) + w_{cl} \cdot (\text{CL violations})\)$

Key Experimental Results

Main Results

Constraints are generated via Instructor-large embeddings and GPT-4o on 5 text datasets (Tweet, Banking77, CLINC-I, CLINC-D, GoEmo).

Dataset	Constraint Ratio	LSCK-HC ACC	PCK ACC	k-means++ ACC	Gain (vs k-means++)
Tweet	40%	~68%	~65%	~62%	+6%
CLINC-D	40%	~78%	~75%	~74%	+4%
Banking77	20%	Best	-	-	Optimal at 20% constraint ratio

Query Efficiency Comparison (Constraint Generation)

Dataset	Constraint Ratio	FSC #Query	Ours #Query	Fold Reduction	FSC ML-RI	Ours ML-RI
Banking77-ML	2%	5260	91	57x	9.92%	96.42%
Banking77-ML	20%	26580	480	55x	11.40%	85.83%
CLINC-ML	2%	25095	91	275x	42.05%	96.25%
Tweet-ML	2%	13070	99	132x	50.00%	100.00%
Tweet-CL	20%	31485	821	38x	99.17%	99.56%

Key Findings

• 20x to 275x Reduction in Query Count: The set constraint format is key, as a single query covers multiple relations.
• Substantial Improvement in ML Constraint Quality: FSC's ML accuracy is extremely low at low ratios (only 9.92% on Banking77) because its ML constraints are indirectly inferred from CL constraints. In contrast, the proposed method directly selects candidate sets based on distance, achieving ML accuracy of 85-100%.
• 20% Constraint Ratio is the Sweet Spot: Higher ratios introduce more erroneous constraints and the improvement tends to saturate.
• Weaker embedding models (such as E5) benefit more from constrained clustering (with an ARI gain of nearly 10%), as lower baselines leave more room for error correction.

Highlights & Insights

• Transitioning from Pairwise to Set Constraints is the Core Innovation: This not only reduces query counts but also improves constraint accuracy due to cross-verification of points within the set. This concept is transferable to any semi-supervised task requiring relation judgments by LLMs.
• Hard/Soft Constraint Separation Strategy: High-confidence constraints guide initialization (as k-means++ is sensitive to seed selection), while low-confidence constraints are handled flexibly through penalties. This hierarchical trust strategy is highly applicable to any downstream task using LLM-generated annotations.
• Local Search is More Robust than PCK: PCK's performance degrades when the constraint ratio exceeds 10%, whereas local search remains robust through penalty-merge iterations.

Limitations & Future Work

• Validated only on short text clustering; performance on long documents or multimodal data remains unknown.
• Constraint generation depends heavily on the distance structure of the embedding space; if embedding quality is poor, candidate selection deteriorates.
• Setting of penalty weights \(w_m\) and \(w_{cl}\) lacks an automatic tuning mechanism.
• Only two LLMs (GPT-4o and DeepSeek) were evaluated; variance in constraint quality across other models has not been fully explored.
• Assumption of a fixed \(k\) value; scenario with unknown cluster counts is more common in practical applications.

Related Work & Insights

• vs FSC (Viswanathan et al. 2024): FSC uses min-max selected pairwise queries with PCK clustering, resulting in massive queries and low ML accuracy. LSCK-HC transitions to set constraints, reducing queries by 20x+ and improving ML accuracy from <50% to >85%.
• vs COP-KMeans: COP utilizes greedy hard constraint satisfaction, completely failing in the presence of erroneous constraints. The penalty mechanism in LSCK-HC naturally tolerates errors.
• vs BH-KM (Baumann & Hochbaum 2022): BH-KM uses mixed-integer programming (MIP) to handle soft constraints but exhibits poor scalability, failing under large volumes of constraints. LSCK-HC offers a more practical time complexity of \(O(nk^2)\).

Rating

• Novelty: ⭐⭐⭐⭐ The idea of replacing pairwise constraints with set constraints is simple and effective. The separation of hard/soft constraints matches LLM characteristics well.
• Experimental Thoroughness: ⭐⭐⭐⭐ Comprehensive analysis over 5 datasets, multiple embeddings and LLM comparisons, query efficiency, and constraint quality.
• Writing Quality: ⭐⭐⭐⭐ Formal formulations are clear and the pseudocode is standard, although some notations are dense.
• Value: ⭐⭐⭐⭐ Provides general reference value for query efficiency optimization in LLM-assisted semi-supervised learning.

Related Papers

• [NeurIPS 2025] Synthesizing Performance Constraints for Evaluating and Improving Code Efficiency
• [ACL 2026] Temporal Flattening in LLM-Generated Text: Comparing Human and LLM Writing Trajectories
• [ICLR 2026] Learn-to-Distance: Distance Learning for Detecting LLM-Generated Text
• [ACL 2026] DetectRL-X: Towards Reliable Multilingual and Real-World LLM-Generated Text Detection
• [ICML 2026] Black-Box Detection of LLM-Generated Text Using Generalized Jensen-Shannon Divergence