The Words a Minimum Separator Can Live Without

TL;DR for operators

A vocabulary that perfectly distinguishes sampled human and AI-generated texts need not contain individually indispensable words. In 272 feature-removal tests across 19 instances with certified minimum separators, researchers found 113 mandatory words, 151 replaceable words, and eight unresolved cases.

The study develops exact optimization methods that establish not only whether a small separating vocabulary works, but whether its size is minimal and whether individual words are necessary. Branch-and-Benders-Cut performs particularly well on the tested text instances, although other methods lead on different optimization metrics.

For AI-evaluation teams, this offers a rigorous way to audit lexical shortcuts in a fixed dataset. For optimization engineers, it clarifies when generating constraints selectively can improve certification. Neither application establishes that the resulting vocabulary will identify AI-generated text reliably outside the sample.

A Small Vocabulary Can Have Many Equally Good Alternatives

Suppose an AI-evaluation team examines human-written and ChatGPT-generated answers to the same collection of questions. It identifies a short list of words such that every human answer differs from every AI answer on at least one selected word.

The list separates the sample perfectly. But what does each word contribute? If one is removed, must the separation fail, or could another word take its place without increasing the list’s length?

This distinction matters when an organization wants to explain why a dataset is separable. A word appearing in a minimum-length explanation might be genuinely unavoidable, or it might be one of several interchangeable choices. Presenting both as essential authorship signals would misrepresent what the optimization establishes.

Marko Djukanović and colleagues examine this problem in Optimization Techniques for Solving the Minimum Red–Blue Separating Set Problem with an Application to Human–AI Text Separation.¹ Their central contribution is an exact optimization framework, followed by computational comparisons and an application that probes the structure of minimum vocabulary separators.

Proving Minimality Requires More Than Finding a Working List

The computational problem is to select the fewest features while ensuring that every pair of objects from opposing classes differs on at least one selected feature.

This is an instance of the Minimum Red–Blue Separating Set Problem (MRBSSP). In its graph formulation, a candidate vertex distinguishes a red–blue pair when its closed neighborhood contains exactly one endpoint.

The problem can be expressed as set cover: each candidate feature covers the cross-class pairs it distinguishes, and every pair must be covered.

For vocabulary separation, the construction is especially concrete. Each document is represented by binary word-incidence indicators. A candidate word distinguishes a human answer from a ChatGPT answer when its indicator differs between them under a fixed occurrence threshold.

The challenge is computational. With many documents, the number of cross-class pairs—and therefore the number of potential separation constraints—can become large.

The researchers address this using safe preprocessing, a GRASP heuristic for constructing feasible solutions, and two exact constraint-generation approaches.

Logic-based Benders decomposition (LBBD) repeatedly solves a relaxed master problem, identifies document pairs the current solution fails to separate, and adds the corresponding constraints.

Branch-and-Benders-Cut (BBC) introduces those constraints through lazy callbacks within a single branch-and-bound tree, avoiding repeated master-search restarts.

Both methods retain exactness because the generated inequalities are valid requirements of the original problem. When the necessary constraints are satisfied and the feasible solution matches a certified lower bound, minimum cardinality is established.

That last distinction matters: finding a small separator gives an upper bound; proving that no smaller separator exists requires an optimality certificate.

The Best Solver Depends on What Must Be Proved

The paper’s main computational evaluation uses 200 feasible random graphs out of 250 generated instances, plus 42 vocabulary-separation instances derived from the English HC3 human–ChatGPT corpus.

The comparison separates three outcomes: the smallest feasible solution found, the strength of the lower bound, and the number of instances certified optimal.

Source: Sections 5.2 and 6.3, Tables 1 and 5.

On random graphs, LBBD supplies the strongest mean lower bound of 13.63, compared with 13.11 for BBC and 12.40 for ILP. Yet BBC certifies 92 optima, only one more than LBBD and two more than ILP.

On the NLP instances, BBC’s 13.21% mean gap improves on LBBD’s 14.38% and ILP’s 23.75%. However, ILP still finds the smallest mean feasible separator, while LBBD retains the strongest mean lower bound.

These are distinct measures of solver performance. An engineer seeking an immediately usable small separator might prioritize feasible-solution quality. A team needing documented minimality must also consider lower-bound progress and completed certificates.

The paper’s cut-batch experiments are parameter-sensitivity tests rather than independent demonstrations of a new advantage. BBC’s selected maximum number of cuts per callback is five on random graphs but two on NLP instances. Adding larger batches can reduce callback rounds without improving final gaps or certificate counts.

The GRASP comparison provides another boundary. On NLP instances, standalone GRASP finds smaller mean separators than the evaluated VNS heuristic, 13.73 versus 14.30, with a statistically significant paired difference. On random graphs, their difference is not significant.

These heuristic results concern feasible solutions, not proofs of minimum size.

All principal exact-method runs use a 3,600-second solver-phase limit after preprocessing and a short GRASP warm start. On larger NLP instances, those excluded preparations can require thousands of additional seconds. Consequently, the benchmark does not establish equivalent end-to-end execution costs.

A Minimum Separator Does Not Make Every Word Mandatory

The paper’s most revealing application begins only after a minimum separator has been certified.

For each selected word, the researchers forbid that word and solve the restricted problem again. Three outcomes are possible:

• Mandatory: Excluding the word makes separation infeasible or proves that every remaining separator must be larger.
• Replaceable: Another separator of the original minimum size exists without that word.
• Inconclusive: The computational limit prevents either conclusion.

Under an extended 7,200-second BBC limit, the researchers obtain 19 certified NLP instances suitable for this analysis.

Of the 113 mandatory words, 96 are objective-critical: removing them provably increases the minimum size. Another 17 are feasibility-critical: removing them makes separation impossible within the specified candidate vocabulary.

The variation between instances is substantial. Two analyzed instances have unique optimal vocabularies, while four standard instances have no words certified mandatory.

A word’s presence in one optimal list therefore says little about whether all optimal lists contain it.

Even marginal coverage can mislead. Although 245 of the 272 tested words rank within the top 10% of candidates by the number of cross-class pairs they distinguish, some low-coverage words remain indispensable because they separate difficult pairs that other words cannot distinguish.

For explainability practitioners, this suggests a more precise feature report: distinguish a feature’s contribution in one solution from its necessity across every equally small solution.

Common Words Can Separate Texts Without Explaining Authorship

The vocabulary-restriction experiments reveal a further interpretive problem.

On the 32 standard NLP instances, stop words account for approximately 6% of candidate vocabulary. Yet using only stop words yields the same median deterministic greedy separator size as the full vocabulary across the 28 instances where a stop-word-only separator exists.

This is a vocabulary-restriction analysis using a greedy heuristic, not a second exact-optimality result. Nevertheless, it establishes that short function words can provide substantial separation capacity in these samples.

Stricter word-occurrence thresholds also alter the result. Across the structural experiment, 97 of 168 tested words in the stricter variants are mandatory, compared with 16 of 104 in the standard instances.

The representation determines which alternatives are available. Indeed, restoring a previously removed duplicate vocabulary candidate changes one word’s classification from mandatory to replaceable.

These observations give dataset auditors a concrete warning: an apparently precise vocabulary explanation can depend on normalization, occurrence thresholds, and candidate filtering.

A perfect within-sample separator may reflect lexical patterns associated with the particular documents rather than stable characteristics of human or AI authorship.

What Dataset Auditors and Optimization Teams Can Actually Use

Cognaptus inference: For an AI-evaluation team auditing a fixed human–AI comparison corpus, minimum vocabulary separation can serve as a dataset diagnostic. The team can establish a compact separating vocabulary, certify minimality where computationally feasible, and test selected words for necessity.

The resulting report should preserve the occurrence threshold, preprocessing rules, candidate vocabulary, certificate status, and unresolved restrictions. This allows auditors to distinguish evidence of unavoidable features from evidence of interchangeable lexical alternatives.

For optimization-platform engineers, the paper motivates measuring feasible solution quality, lower-bound progress, certificate completion, and total processing time separately. BBC is a credible candidate for workloads resembling these text instances, but the tested performance does not establish a universally preferred solver.

The boundary is equally concrete. All NLP results concern sampled English HC3 human and ChatGPT answers. The authors do not evaluate accuracy on unseen documents, newer generators, other languages, adversarially modified text, or production operating conditions. Only 19 of the 42 NLP instances support the certified word-level structural analysis, and eight restricted tests remain unresolved.

A team considering automated AI-text detection would therefore need a separate predictive evaluation before making deployment claims.

The Explanation Is Stronger When Its Alternatives Are Known

The study offers two complementary forms of rigor: algorithms that can certify a smallest separating set, and restricted optimization tests that establish which elements of that set are unavoidable.

Its most consequential finding for AI evaluation is that minimum size and individual feature necessity are different properties. More than half of the tested selected words admit equally small replacements under the study’s fixed representations.

A certified vocabulary separator can explain exactly how a particular sample is distinguishable. Understanding how many alternative explanations exist makes that result more informative. Establishing whether any of those explanations will hold for new text remains a separate empirical task.

Cognaptus: Automate the Present, Incubate the Future.