Scalable method improves building hierarchical concept trees from large lists
SPARROW: Scalable Taxonomy Induction via Structure-Preserving Partitioning and Constraint-Guided Merging
Computation and Language
Summary
Organizing ideas or concepts into a clear family tree structure is hard when the list of ideas is very large. The paper finds that existing AI methods struggle not only because of technical limits but also because they lose important connections when trying to break down the problem into smaller parts. The authors present a new approach called SPARROW that keeps the connections intact when splitting concepts and carefully combines smaller groupings into a big hierarchy. Their experiments show that this approach builds better and more accurate concept trees for large sets of ideas.
taxonomy inductionconcept hierarchylarge language modelsspectral partitioninghierarchical reasoningstructural fragmentationparent displacementincremental fusionhierarchical structureconstraint-guided merging
Authors
Yirui Zhang, Yixuan Tang, Yandong Sun, Mong-Li Lee, Anthony Kum Hoe Tung
Abstract
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.