PaperlayerView exact revision on arXiv

Source-linked AI summary

SPARROW: Scalable Taxonomy Induction via Structure-Preserving Partitioning and Constraint-Guided Merging

Yirui Zhang, Yixuan Tang, Yandong Sun, Mong-Li Lee, Anthony Kum Hoe Tung

arXiv:2609.07307v1cs.CL

TL;DR

LLM-based taxonomy induction from flat term lists degrades as concept sets grow, raising a challenge beyond context length alone. SPARROW combines structure-preserving spectral partitioning with constraint-guided incremental fusion. Across benchmarks and backbones, it reports stronger ancestor-level accuracy and structural stability, with gains more pronounced at scale.

  • Problem

    LLM-based taxonomy induction deteriorates as concept sets grow, while maintaining globally coherent relations remains difficult even when local placements appear plausible.

    Source: §1 · pp. 1–2

  • Method

    SPARROW partitions concepts to preserve within-block hierarchical connectivity, induces local taxonomies, and incrementally fuses them using block-level relations as constraints on global placement.

    Source: §1 · p. 2

  • Results

    Across CCS and Google benchmarks and strong- and limited-context backbones, SPARROW achieves superior ancestor-level accuracy and structural stability, with gains more pronounced at scale.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    The results suggest that taxonomy induction's scalability bottleneck is fundamentally structural rather than model-specific.

    Source: §6 · p. 9

    SPARROW assumes single-parent rooted trees and a complete input concept set, and its iterative merge stage incurs token overhead.

    Source: Limitations · p. 9

Abstract

from arXiv · show

Taxonomy induction aims to organize concept sets into coherent hierarchical structures. Recent LLM-based methods can induce taxonomies directly from flat term lists, avoiding the need for corpora, but degrade sharply as concept sets scale up. We argue that this degradation stems not only from context length limitations, but also from structural failures in hierarchical reasoning. To address this, we adopt a divide-and-merge paradigm that partitions concepts into smaller subsets, induces local taxonomies, and merges them into a global hierarchy. However, we identify two structural failure modes inherent to this paradigm: Structural Fragmentation, where partitioning weakens local hierarchical signals, and Parent Displacement, where locally plausible relations are misplaced in the global hierarchy. To address both, we propose SPARROW, a scalable taxonomy induction framework that combines structure-preserving spectral partitioning to retain hierarchical connectivity within each block, and constraint-guided incremental fusion that treats block-level relations as structural constraints rather than ground truth for global placement. Experiments on large-scale benchmarks show that SPARROW consistently achieves the strongest global structural quality across backbones. The code is available at https://github.com/rebeccazyr/SPARROW.

1 Introduction

LLM-based taxonomy induction degrades as concept sets grow, and naive divide-and-merge can introduce structural errors. SPARROW addresses these failures with structure-preserving partitioning and constraint-guided fusion, achieving stronger structural quality across benchmarks and backbones.

1 Introduction

  • LLM-based methods that induce taxonomies from term names deteriorate as concept sets grow, exposing limits in context handling and hierarchical reasoning.The paper argues that maintaining global coherence becomes harder even when individual placements appear locally correct.Source: §1 · p. 1
  • Naive divide-and-merge is brittle at scale because partitioning and merging introduce distinct structural failure modes.Partition quality matters because local induction depends on concepts sharing latent hierarchy within blocks.Source: §1 · p. 2
  • SPARROW uses spectral partitioning to retain within-block hierarchical connectivity and incremental fusion to treat block relations as constraints, not fixed global decisions.Final placement is resolved through explicit LLM reasoning.Source: §1 · p. 2
  • SPARROW targets Structural Fragmentation, where partitioning weakens local hierarchy, and Parent Displacement, where plausible local relations yield incorrect global ancestors.Weak within-block structure can cause root collapse or spurious relations, while missing intermediate concepts can compress ancestor-descendant relations into direct edges.Source: §1 · p. 2
  • SPARROW achieves stronger global structural consistency and scalability across benchmarks, with higher ancestor-level accuracy under strong and limited-context backbones.Its structural stability gains are particularly strong as scale increases.Source: §1 · p. 2

2 Related Work

Prior work induces taxonomies from corpora or flat term lists, while taxonomy merging often assumes overlap between input structures. SPARROW instead targets fixed concept sets and fuses independently induced blocks.

2.1 Corpus-based Taxonomy Induction

  • Corpus-based methods use textual or distributional evidence, whereas this setting starts from a fixed flat concept set without accompanying text.The task is to infer hierarchy among the given concepts rather than discover an inventory from documents.Source: §2.1 · p. 2

2.2 Term-based Taxonomy Induction

  • Term-based LLM methods require candidate terms within a single inference context, limiting consistency as concept sets grow.This holds whether they generate a taxonomy in one pass or layer by layer.Source: §2.2 · p. 3

2.3 Taxonomy Merging and Structural Fusion

  • Existing merging methods assume overlapping nodes or explicit correspondences, unlike independently induced partial hierarchies with disjoint vocabularies.Taxonomy expansion inserts individual concepts into a fixed backbone, whereas SPARROW attaches structured subtrees to an evolving one.Source: §2.3 · p. 3

3 Problem Formulation

The paper formulates large-scale taxonomy induction as inferring a valid rooted-tree edge set from a flat concept set under a single-parent assumption.

3 Problem Formulation

  • The formulation assumes a single-parent rooted tree, with each non-root concept having exactly one parent.Edges represent is-a relations between concepts.Source: §3 · p. 3
  • Given a flat concept set, the task is to infer an edge set that forms a valid rooted tree.Source: §3 · p. 3
  • The paper focuses on concept sets too large for joint inference.Source: §3 · p. 3

4 Methodology

SPARROW decomposes taxonomy induction into partitioning, local induction, and incremental fusion. Its partitioning aims to preserve local hierarchical signals, while fusion uses local structure to constrain global placement.

4.1 Overview

  • SPARROW separates local semantic abstraction from global structural reasoning through partitioning, block-level induction, and constraint-guided incremental fusion.The three stages target Structural Fragmentation and Parent Displacement.Source: §4.1 · p. 4

4.2 Structure-Preserving Partitioning

  • Spectral clustering is motivated by the need to preserve connected semantic structure within blocks rather than optimize geometric compactness alone.The partitioner also respects LLM context budgets while seeking coherent local sub-hierarchies.Source: §4.2 · p. 4

4.3 Block-Level Taxonomy Induction

  • Within each block, an LLM assigns concepts parents from within-block candidates; concepts without a suitable parent attach to the block root for later global placement.The resulting block taxonomies capture fine-grained semantic structure.Source: §4.3 · p. 4

4.4 Constraint-Guided Incremental Fusion

  • Fusion inserts blocks by descending size and processes their nodes in BFS order, using candidate scoping, parent selection, and sibling-or-parent resolution.Candidates are restricted using block-level relations; embedding similarity retrieves top-K candidates for LLM selection, and a second LLM decision resolves sibling versus intermediate-node placement.Source: §4.4 · pp. 4–5

5 Experiments

SPARROW is evaluated on large taxonomies using structural metrics, scalability tests, partitioning comparisons, ablations, and token costs. It achieves stronger global structural quality across backbones, remains stable as inputs grow, and combines local edge retention with globally coherent fusion.

5.1 Experimental Setup

  • Experiments use CCS (1,768 concepts) and Google (5,595), with SemEval-Food and MeSH, including a 10K-concept setting, for cross-domain and scale evaluation.The main CCS and Google comparisons use 1,000-node subsets.Source: §5.1 · p. 5, §5.2 · p. 6

5.2 Main Results

  • SPARROW exceeded TaxoGPT in Ancestor F1 by 0.226 on CCS and 0.126 on Google, and exceeded LLMscorer by 0.147 and 0.292, respectively.On Google, SPARROW and LLMscorer had nearly identical Edge F1 (0.579 vs. 0.588).Source: Table 1 · p. 6, §5.2 · p. 6

5.3 Scalability Analysis

  • As input size increases, SPARROW remains more stable than TaxoGPT and Chain-of-Layer, with the gap especially pronounced on Google at 4K nodes.SPARROW also achieves the highest Node and Ancestor F1 on SemEval-Food and Ancestor F1 of 0.487 on 10K-node MeSH, versus 0.011 for TaxoGPT and 0.015 for Chain-of-Layer.Source: Figure 4 · p. 7, §5.3 · p. 7

5.2 Main Results

  • SPARROW reached Ancestor F1 of 0.403 vs. 0.146 for LLMscorer on CCS and 0.253 vs. 0.171 on Google under LLaMA3-8B-Instruct.On CCS, SPARROW with LLaMA3-8B-Instruct matched TaxoGPT with GPT-5 in Ancestor F1 (0.403 vs. 0.397).Source: §5.2 · pp. 6–7

Block-normalized Intra-edge Density (BID)

  • Overlapping K-means with τ = 0.60 has the highest IER but lower BID, while spectral clustering without overlap has the highest BID and is adopted.The lower BID for overlapping K-means suggests its edge-retention gain relies on large, redundant blocks.Source: Table 2 · p. 7, Block-normalized Intra-edge Density… · p. 7

5.4 Structure Preservation in the Divide Stage

5.5 Ablation Study

  • The divide stage improves Edge F1, but the full framework achieves the strongest Ancestor F1 on both datasets; merge-stage ablations show all three components are individually necessary.Removing candidate scoping lowers Ancestor F1 by 0.260 and uses roughly 6.7× more tokens; Sim.-only, Node-only, and Always-sib lower it by 0.370, 0.214, and 0.240, respectively.Source: Table 3 · p. 8, §5.5 · p. 8, Table 4 · p. 8

5.6 Cost Analysis

  • On CCS at 1K, LLMscorer uses 407,518 tokens, about 6.5× SPARROW’s, and achieves lower Ancestor F1 (0.476 vs. 0.623).SPARROW’s total token use is nearly identical to Chain-of-Layer’s (62,312 vs. 62,038), with higher Ancestor F1 (0.623 vs. 0.271).Source: Table 5 · p. 8, §5.6 · pp. 8–9

6 Conclusion

SPARROW addresses structural fragmentation and parent displacement through structure-preserving spectral partitioning and constraint-guided incremental fusion. Across CCS and Google with strong- and limited-context backbones, it achieves superior ancestor-level accuracy and structural stability, with larger gains at scale.

6 Conclusion

  • SPARROW combines structure-preserving spectral partitioning with constraint-guided incremental fusion to address fragmentation during partitioning and parent displacement during merging.The framework decomposes large-scale induction into tractable local subproblems while preserving global hierarchical consistency.Source: §6 · p. 9
  • Across CCS and Google with strong- and limited-context backbones, SPARROW consistently achieves superior ancestor-level accuracy and structural stability, with gains that become more pronounced at scale.Source: §6 · p. 9
  • The results suggest that taxonomy-induction scalability is fundamentally structural rather than model-specific, and that pipeline design can support hierarchical reasoning with limited-capacity backbones.Source: §6 · p. 9

Limitations

SPARROW's stated limitations concern taxonomy structure, input completeness, and merge-stage efficiency.

Limitations

  • SPARROW supports single-parent rooted trees but not polyhierarchical DAG taxonomies with concepts that may have multiple parents.Source: Limitations · p. 9
  • The method assumes a complete input concept set, so missing intermediate concepts may introduce structural bias.Source: Limitations · p. 9
  • The iterative merge stage incurs token overhead, and improving its efficiency remains future work.Source: Limitations · p. 9

A.1 Data Preparation

The data preparation converts CCS to a strict single-parent tree and samples connected rooted sub-taxonomies at specified scales. Google Product Taxonomy is already tree-structured and requires no conversion.

A.1 Data Preparation

  • CCS is converted from a DAG to a strict tree by retaining concepts with unambiguous single-parent assignments, yielding 1,768 concepts.Google Product Taxonomy is natively tree-structured and requires no conversion.Source: §A.1 · p. 11
  • For each target scale, connected rooted sub-taxonomies are sampled by random growth from the original taxonomy root, preserving inherited parent–child and ancestor relations.Source: §A.1 · p. 11
  • Few-shot examples come from a separate top-level subtree pool, while test subsets are sampled outside that pool to prevent leakage.Source: §A.1 · p. 11
  • Evaluation scales reach 1K concepts for CCS, SemEval-Food, and MeSH, 4K for Google, and 10K for MeSH.Source: §A.1 · p. 11
  • All processed datasets are publicly available in the SPARROW code repository.Source: §A.1 · p. 11

A.2 Implementation Details.

Implementation details specify prompting and run configurations, the LLMscorer and spectral-clustering procedures, and incremental taxonomy fusion. The supplied table captions identify additional benchmark result scopes but do not provide cell values.

A.2 Implementation Details.

  • All methods use 5-shot prompting; Table 1 reports means over five runs for TaxoGPT, Chain-of-Layer, and SPARROW, while Figure 4 shows one run per scale.LLMscorer outputs are deterministically decycled before evaluation.Source: §A.2 · p. 11
  • LLMscorer retrieves 50 candidate parents per child using cosine similarity over SPECTER2 embeddings, then asks the evaluated chat backbone to select one parent.The resulting edges satisfy the single-parent constraint by construction, and cycles are removed deterministically before evaluation.Source: §A.2 · p. 11
  • The spectral-clustering configuration sets a backbone-dependent reference count k∗=⌈n/sm⌉, searches a candidate cluster range around it, and selects K by the largest eigengap.sm is 70 for LLaMA3-8B-Instruct and 100 for other evaluated backbones.Source: §A.2 · p. 11
  • Fusion initializes the global taxonomy with the largest block, then merges remaining blocks in descending block size and processes incoming nodes breadth-first.Parent candidates are retrieved from already-placed nodes, retaining the top 10 by default; fusion uses candidate scoping, parent selection, and sibling-versus-parent resolution.Source: §A.2 · p. 11
  • Table 6 reports cross-domain and extreme-scale F1 results with GPT-5, with bold indicating the best value for each dataset and scale.Source: Table 6 · p. 12
  • Table 7 reports CCS F1 results at the 1K scale with additional open-weight backbones.Source: Table 7 · p. 12

A.3 Additional Experimental Results

Additional evaluations report SPARROW’s advantages across several benchmarks and backbones, while robustness tests, embedding analyses, and qualitative cases examine fusion behavior and its limits.

A.3 Additional Experimental Results

  • SPARROW leads Node and Ancestor F1 on SemEval-Food, while TaxoGPT leads Edge F1; on MeSH, SPARROW leads Ancestor F1 at 1K and 10K and retains stronger global structure at 10K.On CCS, Table 7 reports the same relative advantage with two additional open-weight backbones; Table 8 reports variability across five GPT-5 runs.Source: §A.3 · p. 12

A.4 Robustness and Block-Size Sensitivity

  • Fusion retains a positive Ancestor F1 gain at a 50% Cut Edge Ratio; on CCS at 1K, block size 100 balances local induction, edge retention, and fusion cost.Smaller blocks increase cut edges and fusion tokens while enlarging the recoverable Ancestor F1 gain.Source: §A.4 · p. 12, Table 9 · p. 12, Table 10 · p. 12

A.5 Embedding-Space Connectivity

  • Gold subtrees are highly connected but only moderately centroid-compact in the SPECTER2 kNN graph, supporting connectivity-preserving rather than compactness-only partitioning.Connectivity is the fraction of nodes in the largest connected component; centroid purity measures concentration around the set centroid.Source: §A.5 · p. 12, Table 11 · p. 13

A.6 Qualitative Fusion Cases

  • Fusion recovers a cut relation by restoring Design and analysis of algorithms as the parent of Data structures design and analysis.Source: §A.6 · p. 13
  • Sibling-or-parent resolution inserts Scene understanding below Computer vision tasks, preserving the intermediate level rather than flattening the hierarchy.Source: §A.6 · p. 13
  • A plausible attachment can remain structurally wrong: Spam detection is placed under Software and application security instead of its gold parent, Web search engines.The case illustrates sensitivity to candidate retrieval and local semantic ambiguity.Source: §A.6 · p. 13

A.7 Prompts for SPARROW

  • Candidate parents must subsume every child of the query; preferences also favor matching granularity and smooth depth, with ROOT as fallback.Source: §A.7 · p. 13
  • The prompt permits either a sibling attachment or inserting the query as an intermediate parent and moving affected children beneath it.Source: §A.7 · p. 13
Loading 2609.07307v1…