GPKmeans is 30× faster after constraints exist—but its 1,435 LLM calls sit outside the stopwatch

GPKmeans reports a 58.75% macro-average clustering accuracy (ACC) across nine text datasets, alongside 65.96% NMI and 46.39% ARI. Those are the best macro averages in the paper’s comparison, but the margins over the strongest non-GPKmeans result are modest: 1.57, 0.59 and 0.53 percentage points, respectively. The evaluation uses INSTRUCTOR-large embeddings and five matched random seeds per dataset where the method is stochastic. Source: paper, Sections 6.1–6.2

The more eye-catching result is speed. GPKmeans averages 3.43 seconds per downstream clustering run, compared with 116.77 seconds for LSCK, 102.73 seconds for LSCK-HC and 128.42 seconds for PCCC. That yields the paper’s roughly 30× claim against LSCK-HC, plus 34.0× against LSCK and 37.4× against PCCC. Each solver run has a one-hour timeout, and the runtime table covers the clustering stage after constraints have been generated. Source: paper, Section 6.2.4

That boundary matters. The stopwatch excludes offline LLM generation. GPKmeans makes 1,435 successful prompt requests reconstructed from cached logs: 154 for must-link generation and 1,281 for cannot-link construction. LSCK uses 5,593 calls, while LSCK-HC totals 6,430. The paper therefore supports two separate findings: GPKmeans needs fewer calls than those baselines, and its optimizer is faster once constraints are stored. It does not establish a 30× end-to-end latency or cost advantage for the complete LLM-plus-clustering pipeline. Source: paper, Sections 6.1.4 and 6.2.4

The quality result is also tied to the constraint source. All LLM constraints are generated offline with deepseek-v4-flash. The paper reports 88.91% pair-weighted must-link accuracy for GPKmeans’ anchor-based source versus 72.57% for LSCK’s, while both use the same cannot-link pairs and score 97.75% there. Under identical generated constraints, GPKmeans beats PCCC by 5.72 points in ACC, 2.54 in NMI and 4.66 in ARI, isolating the effect of the solver more cleanly than the full-pipeline comparison. Source: paper, Sections 6.1.5 and 6.2.1–6.2.2

The practical takeaway is narrow but useful: bounded soft penalties can outperform hard enforcement when LLM-produced relations are noisy, and cached local updates can make the downstream solver cheap. A production decision still needs the missing end-to-end ledger—prompt tokens, wall-clock annotation time, model price, retries and sensitivity to replacing deepseek-v4-flash—before treating “30× faster” as a pipeline-level result.