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

arXiv: https://arxiv.org/abs/2609.07307 · HTML: https://mlsanity.com/paper/2609.07307/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 31 references that are in the map.
- First posted on arXiv 7 Sep 2026.

## Builds on (most cited first, 17 of 17)

- [SciRepEval: A Multi-Format Benchmark for Scientific Document Representations](https://mlsanity.com/paper/2211.13308/) (2022)
- [TaxoGen: Unsupervised Topic Taxonomy Construction by Adaptive Term Embedding and Clustering](https://mlsanity.com/paper/1812.09551/) (2018)
- [STEAM: Self-Supervised Taxonomy Expansion with Mini-Paths](https://mlsanity.com/paper/2006.10217/) (2020)
- [Hearst Patterns Revisited: Automatic Hypernym Detection from Large Text Corpora](https://mlsanity.com/paper/1806.03191/) (2018)
- [Chain-of-Layer: Iteratively Prompting Large Language Models for Taxonomy Induction from Limited Examples](https://mlsanity.com/paper/2402.07386/) (2024)
- [TaxoAdapt: Aligning LLM-Based Multidimensional Taxonomy Construction to Evolving Research Corpora](https://mlsanity.com/paper/2506.10737/) (2025)
- [Prompting or Fine-tuning? A Comparative Study of Large Language Models for Taxonomy Construction](https://mlsanity.com/paper/2309.01715/) (2023)
- [Enquire One's Parent and Child Before Decision: Fully Exploit Hierarchical Structure for Self-Supervised Taxonomy Expansion](https://mlsanity.com/paper/2101.11268/) (2021)
- [Taxonomy-guided Semantic Indexing for Academic Paper Search](https://mlsanity.com/paper/2410.19218/) (2024)
- [Distilling Hypernymy Relations from Language Models: On the Effectiveness of Zero-Shot Taxonomy Induction](https://mlsanity.com/paper/2202.04876/) (2022)
- [Corpus2Skill: Distilling Enterprise Knowledge into Navigable Agent Skills for QA and RAG](https://mlsanity.com/paper/2604.14572/) (2026)
- [Rank, Chunk and Expand: Lineage-Oriented Reasoning for Taxonomy Expansion](https://mlsanity.com/paper/2505.13282/) (2025)
- [Find Parent then Label Children: A Two-stage Taxonomy Completion Method with Pre-trained Language Model](https://mlsanity.com/paper/2406.17739/) (2024)
- [TaxoAlign: Scholarly Taxonomy Generation Using Language Models](https://mlsanity.com/paper/2510.17263/) (2025)
- [Euler/X: A Toolkit for Logic-based Taxonomy Integration](https://mlsanity.com/paper/1402.1992/) (2014)
- [Towards Building Knowledge by Merging Multiple Ontologies with CoMerger: A Partitioning-based Approach](https://mlsanity.com/paper/2005.02659/) (2020)
- [CHisAgent: A Multi-Agent Framework for Event Taxonomy Construction in Ancient Chinese Cultural Systems](https://mlsanity.com/paper/2601.05520/) (2026)

## Abstract (arXiv)

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.