{"id":"c12a1815-776c-4044-ac02-b975087e4df0","arxiv_id":"2504.15640","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Cequel reduces the LLM query cost of text clustering by selecting a few informative text pairs or triples, turning LLM answers into must-link and cannot-link constraints, and clustering with a PMI-weighted constrained clustering algorithm.","lead":"This paper introduces Cequel, a framework that asks a large language model a small number of carefully chosen questions about pairs or triples of texts, then uses the answers as constraints to cluster the full collection. It aims to get the accuracy of LLM-based clustering while spending far fewer API tokens than comparing every pair of texts.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Budget model in Section 4 omits prompt and response tokens, so the 'same query budget' comparison may overstate the number of feasible LLM queries; a token-accurate rerun is needed to support the central claim.","rationale":"The paper's headline claim is comparative and cost-based, and Section 4's conversion from budget Q to the number of edge or triangle queries is the only place where that comparison is made concrete. If the conversion omits prompt and response tokens, every experiment labeled 'same query budget' is potentially unfair, especially on short-text datasets where overhead dominates document tokens. The reader identified this same weakest assumption, and I agree with that diagnosis. The concern does not by itself refute the framework: the reported margins are often large, the ablations support the component contributions, and the public code and dataset release are real evidence. But because the central claims of cost-effectiveness and consistent outperformance under the same budget are quantitative, the evaluation should be repeated with full token accounting before the claim can be accepted as stated. The proposed test is straightforward: tokenize the actual prompts and outputs, recompute feasible query counts, and rerun the comparison. No error bars or significance tests are reported either, but the token-budget issue is more directly load-bearing for the central claim, so it is the focus here. The verdict should remain conditional until that check is performed.","tokens_in":26494,"tokens_out":6476,"duration_ms":65775,"concrete_test":"Use the tokenizer matching GPT-4o-mini (e.g., tiktoken) to tokenize the exact prompt templates in Tables 1 and 8 plus the expected output response for every edge and triangle query on each dataset. Recompute the maximum N and N_delta that fit within Q=Omega using full input-plus-output token counts, rerun Cequel with that reduced query set, and compare against the same re-budgeted ClusterLLM and PO-PCKMeans baselines. If Cequel's ACC/NMI still exceed the baselines, the conclusion survives; if the gap closes or reverses, the 'same query budget' claim is unsupported as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is explicitly comparative and cost-based: Cequel outperforms baselines 'under the same query budget.' The only place where the budget is operationalized is Section 4, where edge queries are N=Q/(2s) and triangle queries are N_delta=Q/(3s), assuming the only consumed tokens are the two or three document texts. The prompt templates in Tables 1 and 8 include task context, category labels, and instructions, and the LLM responses consume at least one or two output tokens. For short-text datasets such as Tweet, where average text length is about 11 tokens, the prompt template and response can add more tokens than the documents themselves. Thus Q/(2s) and Q/(3s) overstate the number of queries that fit within a real token or dollar budget, and Cequel obtains fewer constraints than claimed under that budget. Because ClusterLLM and PO-PCKMeans are also evaluated under the same nominal Q, their actual token consumption may be misstated too, so the reported 'same query budget' comparison is not yet a fair test. This is not an internal contradiction, but it is the least secured condition for the headline result: no measurement of actual token usage or cost breakdown is reported, and the single monetary figure ($0.0185 on Tweet) is not derived from a model that includes prompts and outputs.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Cequel, a two-stage framework for text clustering under a limited LLM query budget. In the first stage, EdgeLLM or TriangleLLM greedily selects informative text pairs or triplets, respectively, based on spanning-edge/spanning-triangle centralities, and queries an LLM for same-cluster judgments to produce must-link and cannot-link constraints. In the second stage, the authors extend constrained spectral clustering and constrained K-Means to weighted variants (WCSC and WCKMeans), where each constraint is weighted by a PMI-like quantity computed from the text embeddings. The central claim, stated in the abstract and in Section 1, is that under the same token budget Cequel consistently outperforms existing unsupervised and semi-supervised LLM-guided clustering baselines across six benchmark datasets, and that it achieves this with far fewer than the O(n^2) pairwise queries used by graph-clustering approaches. The paper includes an ablation study, a comparison to multiple constrained-clustering back ends, and an analysis of sensitivity to the choice of text encoder and LLM.","tokens_in":26826,"tokens_out":8250,"duration_ms":77354,"significance":"If the central claim holds, Cequel offers a practical reduction in LLM query cost while improving clustering quality over methods such as ClusterLLM and PO-PCKMeans. The design is principled in that the constraints come from an external LLM oracle and the PMI weights are derived from embeddings, so the headline result is not reduced to fitting a constant to the test labels. The paper also provides several strengths: the source code and datasets are publicly linked, the ablations isolate the contributions of the selection strategy and the weighting scheme, and the comparison spans multiple datasets, encoders, and LLMs. The main reservations concern the operationalization of the query budget, the lack of statistical variability information, and the absence of an optimality guarantee for the greedy selection procedures.","major_comments":[{"comment":"The token-budget model N = Q/(2s) and NΔ = Q/(3s) assumes that only the concatenated document texts consume the budget. The prompt templates in Tables 1 and 8 include a task context, category instructions, and, for triangle queries, a five-option multiple-choice block; the model's response also consumes output tokens. For Tweet, the average text length is about 11 tokens, so the prompt/response overhead can exceed the document tokens by a large factor. Because the headline comparison is made 'under the same query budget' and the single cost figure ($0.0185 on Tweet) is not derived from a model that includes prompts and outputs, the number of feasible queries is currently overstated and the comparison is not yet a fair token- or dollar-equivalent test. Please measure actual prompt/response token usage per method and rerun Table 3 and Fig. 4 under a token-accurate budget, or clearly state that the budget counts only document tokens and justify why that is the appropriate cost measure for the intended deployment.","section":"§4, Eqs. (3)–(4)"},{"comment":"All clustering results are reported as single numbers, although both the LLM answers and the KMeans/KMeans++ initializations are stochastic, and the spectral variants are randomized as well. The claim that Cequel 'consistently outperforms' the baselines needs repeated runs with mean and standard deviation (and preferably a paired significance test) before the margins in Table 3 can be considered reliable, particularly on datasets such as Reddit where the reported differences are only a few ACC points.","section":"§7, Table 3"},{"comment":"The greedy selection algorithms are presented as solving a maximization problem for the sum of spanning-edge or spanning-triangle centralities, but no approximation guarantee is established for the greedy solution relative to the exact top-N selection. The ablation in Table 5 compares Max only against Min and Random. Since the selection procedure is a core contribution, please add either a theoretical bound on the greedy objective ratio or an empirical comparison to the exact top-N solution on the smaller datasets (e.g., BBC News and Tweet) to justify that the heuristic is near-optimal.","section":"§5.2 and §6.2, Eqs. (8) and (11)"},{"comment":"The PMI-based weights rely on a normalization range chosen by hand ([0.5, 1.5] for WCSC and [0.01, 0.1]/[0, 0.01] for WCKMeans) and on the '+1' shift in Eq. (5). No sensitivity analysis is reported for these ranges, and the relationship between the PMI formula in Eq. (5) and the stated probability definitions in the surrounding text is not immediately transparent. Please clarify the derivation of Eq. (5) and report how sensitive the results in Tables 3 and 6 are to the chosen ranges.","section":"§4, Eqs. (5)–(6)"}],"minor_comments":[{"comment":"The heading 'Experimental Seup' should be 'Experimental Setup'.","section":"§7.1"},{"comment":"Table 2 lists six datasets, but the text in §7.1 refers to 'five text corpora'; please make the count consistent.","section":"Table 2 and §7"},{"comment":"In the ablation table, the rows labeled 'w/oEdgeLLM' and 'w/oTriangleLLM' do not specify what replaces the removed component (e.g., random selection or the other selection method); please state the replacement to make the ablation interpretable.","section":"Table 4"},{"comment":"The definitions of P(a), P(b), and P(a,b) in the prose do not obviously produce the expression written in Eq. (5); please align the notation and derivation.","section":"Eq. (5)"},{"comment":"The description of WCSC says 'selecting top-K eigenvectors' but does not specify the exact generalized eigenvalue problem involving L and Rα; please add the precise formulation or a reference.","section":"Appendix C.2"},{"comment":"The manuscript uses an outdated ACM 'Conference’17' template and reference metadata; if this is intended as a journal submission, the venue and date metadata should be updated.","section":"Title page and references"}],"recommendation":"major_revision","confidential_remarks":"The paper is a technical report formatted with an old ACM template; the metadata should be refreshed for any journal submission. I do not have concerns about the GenAI disclosure. The main risk is the token-budget accounting, which should be addressed before the cost-effectiveness claim can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"I'll cut to it: this paper deserves a serious referee, but the central cost argument is not fully secured. The triangle-query idea is the main novelty—one API call on a triplet yields three pairwise constraints via a five-way multiple choice—and the greedy selection based on spanning centrality is a reasonable, well-explained heuristic. The authors also ship code, run ablations that support the design choices, and report consistent gains across six datasets, including against strong baselines like ClusterLLM and PO-PCKMeans. That is real work and mostly convincing.\n\nThe soft spot is the budget model. In Section 4, the number of feasible edge queries is Q/(2s) and triangle queries Q/(3s), where s is average tokens per text. That counts only the document tokens. But the prompts in Tables 1 and 8 include task instructions, category context, and for triangles a five-option MCQ block; the LLM's response also costs tokens. On Tweet, where the average text is around 11 tokens, the prompt and response overhead can be several times the document tokens. So the 'same query budget' comparison is not actually a fair token or dollar comparison as reported. The single cost figure ($0.0185 on Tweet) is not derived from a model that includes this overhead. I don't think this kills the paper—Cequel would plausibly still win if overhead were counted equally—but the reported margins are uncertain until a token-accurate cost analysis is done. The stress-test note calls this the least secured condition, and I agree.\n\nTwo smaller issues. There are no repeated trials or error bars, even though the pipeline has stochastic components (GPT-4o-Mini answers and KMeans initialization). And the PMI weights and normalization ranges in Section 4 and WCKMeans are picked ad hoc; a sensitivity analysis would help. None of this is internally contradictory, and the paper does not reduce to a fitted constant.\n\nWho is this for? NLP practitioners who want practical LLM-guided clustering at scale. The mechanism is novel and the implementation is available. I'd send it out for review, but I'd ask for a token-accurate cost model and error bars before accepting. Recommendation: conditional accept with major revisions.","headline":"Cequel has a genuinely useful core and solid experiments, but the cost-comparison claim rests on a budget model that ignores prompt/response tokens—worth refereeing, conditional on fixing that.","tokens_in":27298,"tokens_out":2632,"would_cite":true,"duration_ms":25787,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Cequel claims that a small budget of well-chosen LLM pair and triplet queries, turned into weighted constraints, clusters text better than strong baselines at the same token cost.","keywords":["text clustering","constrained clustering","large language models","query budget","must-link constraints","cannot-link constraints","spanning edge centrality","greedy selection"],"falsifier":"On a short-text corpus, log the actual billed tokens for the exact edge and triangle prompts used in the paper and divide the advertised budget by the real per-query cost; if the resulting number of feasible queries is substantially below $Q/(2s)$ or $Q/(3s)$, then the reported accuracy under 'the same query budget' is not attainable at that budget.","tokens_in":26323,"feed_emoji":"🗂️","tokens_out":4309,"duration_ms":37428,"temperature":0.7,"pith_summary":"This paper tries to show that accurate text clustering can be achieved with a small, fixed budget of queries to a large language model, by asking the model about deliberately chosen text pairs or triplets instead of about every pair. The authors propose Cequel, which selects the most informative pairs and triplets using a graph-theoretic centrality measure, turns the model's yes/no or multiple-choice answers into must-link and cannot-link constraints, and feeds those constraints into weighted variants of constrained spectral and k-means clustering. Across six benchmark datasets, Cequel reports consistently higher accuracy and normalized mutual information than embedding-only methods and three LLM-guided baselines when every method is given the same token budget. The practical stake is that users could get LLM-quality clusters at a cost that scales linearly with the corpus size rather than quadratically.","feed_headline":"Same budget, better clusters: greedy LLM queries win","feed_subtitle":"Choosing informative pairs and triplets before asking the LLM turns a tiny query budget into strong text clusters.","key_machinery":"The load-bearing object is a pair of greedy selection algorithms built on spanning edge centrality (SEC), the effective resistance of an edge in the similarity graph. SEC is estimated by the sum of inverse degrees $\\Phi(t_a,t_b)=1/d(a)+1/d(b)$, which makes the quadratic set of all pairs tractable: the algorithm only needs to inspect three candidates per step and runs in $O(N+n\\log n+nd)$ time. For triangles the same centrality is summed over the three edges, and a min-heap per text keeps the search for the next triplet cheap. The second mechanism is the weighting step: each constraint receives a pointwise mutual information weight derived from text embeddings, and WCSC and WCKMeans fold those weights into the spectral Laplacian or the k-means objective, so noisy LLM answers count for less.","core_discovery":"The paper's central claim is that pairwise supervision from an LLM, concentrated on a handful of informative comparisons, transfers enough signal to cluster an entire corpus. EdgeLLM greedily selects pairs with the largest estimated spanning edge centrality—roughly, pairs whose similarity is most load-bearing for the graph topology—and TriangleLLM extends the idea to triplets, whose multiple-choice answers yield three constraints per query instead of one. The selected constraints are then weighted by pointwise mutual information computed from cheap text embeddings, which down-weights unreliable LLM answers. The authors state that under the same query budget, Cequel outperforms the compared methods on all six datasets, with the best configuration (TriangleLLM plus weighted constrained spectral clustering) reaching 91.01% accuracy on BBC News and 73.10% on Tweet.","pith_inferences":["Outside the paper's own accounting, real API billing counts the prompt template and reply tokens; recomputing constraint counts under true token cost would likely reduce the number of feasible queries, so the headline 'same budget' comparison should be re-run with billed tokens rather than text-only tokens.","The same recipe—greedy centrality-based selection of informative comparisons plus an LLM oracle plus weighted constrained clustering—should transfer to other pairwise-supervision tasks such as entity resolution, record linkage, or relevance judgments, where labeling every pair is expensive.","The PMI weighting could be interpreted as a lightweight calibration of LLM reliability: pairs whose embedding similarity is extreme receive higher weight, so the framework is implicitly betting that the LLM is more trustworthy where cheap embeddings already agree or disagree strongly.","A testable extension: replace the LLM with any expensive oracle (human annotators, search engines, ML models) and the selection algorithms should still improve constraint efficiency, since the centrality and PMI logic does not depend on the oracle's internals."],"forward_implications":["An O(n)-query budget can replace the O(n^2) pairwise oracle calls that graph-based LLM clustering previously required, making LLM-guided clustering feasible for corpora of thousands of documents.","Because TriangleLLM extracts three constraints per query, its performance advantage over EdgeLLM under the same budget follows directly from the ratio $3\\cdot (Q/3s)$ versus $Q/(2s)$; any setting where triplet judgments are reliable should favor triangles.","The weighting scheme is what lets the framework tolerate noisy LLM answers: unweighted constraints lose several accuracy points on Tweet, so ignoring answer reliability would erase most of the gain.","Cequel reaches higher accuracy at a budget of $Q=\\Omega/10$ than two LLM baselines reach at $Q=2\\Omega$ on BBC News and Tweet, so query effectiveness, not raw budget, is the driver."],"supporting_citations":[{"why":"Supplies PCKMeans, the constrained k-means baseline that the paper generalizes into WCKMeans with per-constraint weights.","marker":"[2]"},{"why":"Introduces electrical resistance and spanning edge centrality, the graph-theoretic measure that EdgeLLM's selection criterion is based on.","marker":"[8]"},{"why":"Defines pointwise mutual information, which the paper adapts to weight must-link and cannot-link constraints.","marker":"[12]"},{"why":"Provides the bound on spanning edge centrality that justifies estimating it as the sum of inverse degrees.","marker":"[28]"},{"why":"PO-PCKMeans is the most similar prior LLM-oracle constraint method and a key baseline under the same query budget.","marker":"[61]"},{"why":"Constrained spectral clustering is the base algorithm that WCSC extends by adding PMI weights to constraints.","marker":"[65]"},{"why":"ClusterLLM is the strongest LLM-guided baseline; the paper compares against it and its no-fine-tuning variant across all datasets.","marker":"[77]"}],"fun_headline_variants":["Greedy LLM queries: cheaper text clustering that beats baselines","Cequel: smarter LLM queries for text clustering on a budget","Pick the right pairs: LLM queries maximize clustering signal","TriangleLLM: triple queries yield triple constraints, better clusters","Budget-friendly clustering via selective LLM comparisons"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on the budget model that one edge query costs about two average texts' tokens and one triangle query costs about three; in reality the prompt template, instructions, and the model's response also consume tokens, and for short texts those overheads can dwarf the documents themselves.","fun_headline_variants_meta":{"raw":{"variants":["Greedy LLM queries: cheaper text clustering that beats baselines","Cequel: smarter LLM queries for text clustering on a budget","Pick the right pairs: LLM queries maximize clustering signal","TriangleLLM: triple queries yield triple constraints, better clusters","Budget-friendly clustering via selective LLM comparisons"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000214,"raw_usage":{"total_tokens":1419,"prompt_tokens":932,"completion_tokens":487,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":548,"completion_tokens_details":{"reasoning_tokens":402}},"tokens_in":548,"tokens_out":487,"duration_ms":4577,"temperature":1.0,"reasoning_tokens":402,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:21:02.672851+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a short-text corpus, log the actual billed tokens for the exact edge and triangle prompts used in the paper and divide the advertised budget by the real per-query cost; if the resulting number of feasible queries is substantially below $Q/(2s)$ or $Q/(3s)$, then the reported accuracy under 'the same query budget' is not attainable at that budget.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines pointwise mutual information, which the paper adapts to weight must-link and cannot-link constraints."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Constrained spectral clustering is the base algorithm that WCSC extends by adding PMI weights to constraints."}],"review_version":1}