Well-Quasi-Ordered Subsumption Checks for Growing Taxonomies

Classifiers that respect a label hierarchy, so that "tiger" is never more probable than "mammal", work well when the hierarchy is fixed and finite. Taxonomies are increasingly grown on the fly, though, often by a language model that proposes new categories and parent links. In that setting the consistency machinery has nothing to say about whether the growing hierarchy stays sensible. Duplicate branches, cross-branch redundancies and contradictory parent links can pile up, and the expansion loop has no principled point at which redundancy is guaranteed to surface. This note proposes a fix taken from infinite-state program verification, where search over unbounded spaces is made to terminate by comparing states under a well-quasi-ordering. A well-quasi-ordering (WQO) is a "more general than" relation under which every infinite sequence must contain an earlier element that is more general than a later one.

The key observation is simple. The ordinary tree order of a taxonomy is not a WQO once depth is unbounded. Even with finitely many attribute words, the paths 0·1, 0·0·1, 0·0·0·1 and so on form an infinite set of pairwise incomparable concepts, so a proposer can generate redundant categories forever without any ancestor check firing. Encoding each concept as its sequence of differentiating attributes and comparing concepts by subsequence embedding gives a strictly coarser relation that is a WQO, by Higman's lemma. We propose using this order as the trigger for redundancy and consistency checks during taxonomy expansion. Each check it triggers is resolved by data: a link is kept or removed according to counterexamples found by a coherence-enforcing classifier. We then test whether this produces growing taxonomies that are more accurate and less redundant, and that support more consistent classifiers, than simpler deduplication rules.

Core Claim

Let each concept $c$ be represented by a finite word $w(c) = a_1 a_2 \dots a_n$ over a fixed finite attribute vocabulary $A$. This is the sequence of distinguishing attributes on its path from the root, for example organism, animal, warm-blooded, feline, striped. Define the order

$$c \sqsubseteq d \iff w(c) \text{ embeds as a (not necessarily contiguous) subsequence of } w(d).$$

The prefix relation (being an ancestor in the tree) implies $\sqsubseteq$, but not the converse. Because $A$ is finite, Higman's lemma makes $\sqsubseteq$ a WQO. The expansion loop accepts candidates one at a time. Whenever a new candidate $d$ has an already-accepted $c$ with $c \sqsubseteq d$ but $c$ is not an ancestor of $d$, the loop must resolve the pair. It either adds a parent edge $c \to d$, which turns the taxonomy into a directed acyclic graph and imposes the constraint $P(c) \ge P(d)$, or it records a data witness: an input labelled $d$ but not $c$, which justifies keeping the two concepts unlinked.

The WQO property gives a precise and limited guarantee. No infinite stream of proposals can avoid triggering this check, because redundancy cannot hide among incomparable branches. Under the ordinary tree order it can. We do not claim the guarantee is quantitatively tight. The empirical claim is that the pairs this order flags are the ones that matter. They should be real duplicates and missing multiple-inheritance links, and resolving them with classifier counterexamples should give better taxonomies than deduplication by embedding similarity or by a proposal budget.

Research Program

The design borrows two mechanisms from verification and one from hierarchical classification. From Constrained Monotonic Abstraction: A CEGAR for Parameterized Verification we take its loop: a coarse order is refined only when a counterexample shows it to be wrong, and the refinement is constrained to keep the WQO property. That paper refines a hand-designed order on protocol states using Craig interpolants. We instead refine a learned taxonomy using counterexamples drawn from labelled data. Refinement here means adding attributes to a concept's word, which keeps the vocabulary finite and so preserves the WQO. From the backward-search style of Incremental, Inductive Coverability we take a data structure. We store only the finite set of minimal accepted concepts under $\sqsubseteq$ and test new candidates against it, which keeps each check cheap. That paper also warns that inductive generalization needs downward-finiteness. Our order satisfies this, since each word has finitely many subsequences, and we will keep it that way. From Coherent Hierarchical Multi-Label Classification Networks we take the Max Constraint Module, a layer that sets each parent's probability to at least the maximum of its descendants' probabilities. We rebuild this layer over the current graph after each accepted edge, so the downstream classifier is consistent by construction at every stage. Its residual errors on validation data then serve as counterexamples: a confident child prediction contradicted by a gold parent label marks the corresponding edge as suspect.

The candidate generator is an instruction-tuned language model of the kind used for taxonomy expansion in A Unified Taxonomy-Guided Instruction Tuning Framework for Entity Set Expansion and Taxonomy Expansion. That work proposes concepts and links but has no mechanism for detecting redundancy across branches. The one new learned component is a canonicalizer that maps each free-text proposal to an attribute word over $A$. We build $A$ from a fixed inventory: WordNet lexicographer categories plus a few thousand gloss attributes. This canonicalizer is the main risk in the design. If it maps synonyms to different attribute words, or different concepts to the same word, the subsumption check flags the wrong pairs. We therefore measure its accuracy separately and report all results with gold canonicalization as well as learned canonicalization.

The analysis has one theoretical part and one empirical part. Theoretically, we will state and prove the guarantee for our acceptance rule: every infinite proposal stream triggers infinitely many resolutions. We will also exhibit the infinite antichain that defeats the tree-order check. Empirically, we ask whether flagged pairs are enriched for true redundancies relative to chance and to cosine-similar pairs.

Baselines

The naive reference point runs the language-model proposer with no redundancy check. It stops at a fixed proposal budget and links each accepted concept only to the parent the model names. The Max Constraint Module is still applied downstream. This isolates what any checking adds.

The strongest practical competitor is embedding deduplication. A candidate is rejected or merged when the cosine similarity between its sentence embedding and that of an existing node exceeds a threshold tuned on validation data. It is strong for two reasons: it is what practitioners already do, and it also terminates, because only finitely many well-separated points fit on a sphere. Any advantage of our method must therefore come from what gets flagged, not from termination itself.

A third baseline uses the tree-order check: a candidate is compared only against its claimed ancestors. This is the exact ablation for the WQO ingredient, since it uses the same pipeline with the non-WQO order.

A matched-random-trigger ablation flags the same number of pairs as our method but chooses them uniformly at random, and resolves them with the same counterexample procedure. This separates "the order picks the right pairs" from "more checks help".

A final ablation resolves every flagged pair by merging, without counterexamples. This tests whether data-driven refinement matters.

All variants share the same proposer, the same canonicalizer, the same seed taxonomy, the same number of proposal calls and the same classifier training budget. Thresholds for the deduplication baseline get the same number of tuning runs as our one free parameter, the minimum witness count.

For the downstream classifier, the strongest reference numbers in the file come from ProTeCt: Prompt Tuning for Taxonomic Open Set Classification. On the ImageNet WordNet hierarchy it reports Hierarchical Consistent Accuracy rising from 2.99% to 37.74% and Mean Treecut Accuracy rising from 46.98% to 88.61%, but on a fixed, gold taxonomy. For hierarchical multi-label tasks, C-HMCNN reports the best average rank (1.25) across 20 benchmarks. No reported result was found on Lacuna for taxonomy-expansion edge precision on any of these benchmarks, so expansion quality has no external number to beat.

We count the method as winning if three things hold. It must beat cosine deduplication on edge F1 and duplicate rate at matched proposal budget. It must beat the random-trigger ablation. Its downstream ProTeCt-style classifier on the grown taxonomy must close a meaningful share of the gap to the gold-taxonomy figures above.

Why not just…?

Why not just cap the number of proposals or the depth? A cap guarantees termination, but it says nothing about where redundancy sits. It keeps whatever arrives first, including duplicates in distant branches. The verification literature also shows that bounding without subsumption fails on unbounded problems. For example, unpruned backward search did not finish on Bingham (h=250), which Incremental, Inductive Coverability proves safe in 0.2 seconds. The naive baseline measures this directly through the duplicate rate as a function of budget.

Why not just deduplicate by embedding similarity? This is the real threat, and we treat it as one. It terminates, it is cheap, and it catches surface-level synonyms well. Its weakness should be cross-branch structural redundancy: "pet > dog" against "mammal > canine > domestic", where the descriptions differ in wording but the attribute structure embeds. It also proposes no edge, only a merge or rejection, so it cannot create the multiple-inheritance links that a directed acyclic graph needs. If cosine deduplication matches our edge F1 and duplicate rate, the WQO order adds nothing in practice. We would then report that, and fall back to the narrower contribution of counterexample-guided resolution. The head-to-head comparison at matched budget settles this.

Why not just enforce consistency with the Max Constraint Module and skip the order entirely? That module guarantees $P(\text{parent}) \ge P(\text{child})$ over whatever graph it is given, but it cannot repair a wrong or redundant graph. On a taxonomy with duplicated branches it spreads probability mass across copies and stays "consistent" while being wrong. The naive baseline keeps this module, so any gain over it is attributable to the graph, not the output layer.

Why not just use order or hyperbolic embeddings, which encode partial orders geometrically? Finer Grained Entity Typing with TypeNet found that order embeddings reach only about 44–50 MAP on CoNLL-YAGO, against 74.8 for bilinear scoring under negative sampling. Hyperbolic constraints such as those in Geometric Constraints for Small Language Models to Understand and Expand Scientific Taxonomies also give no discrete subsumption test. We include a hyperbolic-distance trigger as an additional flagging rule in the random-trigger comparison slot.

Proposed Experiments

We simulate expansion by deleting subtrees from gold hierarchies and asking each method to regrow them from a pruned seed. The gold hierarchies are the WordNet hierarchy over ImageNet used by ProTeCt; TypeNet, with 1,941 types, average depth 7.8 and up to 14 levels; and the FunCat and Gene Ontology hierarchies among the 20 C-HMCNN benchmarks. TypeNet matters most, because deep, densely typed hierarchies are where cross-branch redundancy should appear.

Expansion quality is measured by four quantities: edge precision, recall and F1 against the deleted gold structure; the rate of duplicate nodes; the rate of cycles or contradictory links; and the number of proposals until the loop stops producing accepted concepts. Downstream quality is measured by retraining a coherent classifier on each grown taxonomy. For ImageNet this is the ProTeCt setup, reporting Hierarchical Consistent Accuracy and Mean Treecut Accuracy. For TypeNet with CoNLL-YAGO it is a CNN-bilinear typer with the Max Constraint Module, reporting MAP. For FunCat and the Gene Ontology it is C-HMCNN, reporting area under the average precision–recall curve.

The decisive check is the precision of flagged pairs. Among pairs flagged by the subsequence order but not by the tree order, what fraction are gold duplicates or gold multiple-inheritance links? We compare this with cosine-flagged and randomly flagged pairs at equal counts. If subsequence-flagged pairs are not clearly enriched, the core claim fails regardless of downstream numbers. A second check reruns everything with gold canonicalization, which separates failures of the order from failures of the canonicalizer. A third check is adversarial. We feed the proposer a constructed stream of pairwise tree-incomparable but redundant concepts, modelled on the 0ⁿ1 antichain, and confirm that the tree-order check never fires while ours does. This makes the theoretical separation observable.