SPARROW: Scalable Taxonomy Induction via Structure-Preserving Partitioning and Constraint-Guided Merging¶
Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/rebeccazyr/SPARROW
Area: LLM Reasoning
Keywords: Taxonomy Induction, Large Language Model Reasoning, Divide-and-Merge, Spectral Partitioning, Constraint-Guided Fusion
TL;DR¶
To overcome context window constraints and global structural reasoning failures in LLM-based taxonomy induction over large flat concept sets, SPARROW introduces a divide-and-merge framework coupling structure-preserving spectral graph partitioning with constraint-guided incremental fusion, achieving state-of-the-art ancestor-level structural consistency at scales up to 10,000 concepts.
Background & Motivation¶
Taxonomies are foundational knowledge structures that organize concepts into hierarchical directed trees, powering downstream semantic applications ranging from structured search and taxonomy-enhanced retrieval-augmented generation to recommendation systems and knowledge integration. Traditional taxonomy induction frameworks heavily rely on massive text corpora, mining hypernym-hyponym (is-a) statistical associations through handcrafted lexical-syntactic patterns, probabilistic topic models, or geometric embedding clustering. With the advent of Large Language Models (LLMs), recent advances demonstrate that internal world knowledge acquired during pretraining enables language models to infer valid hierarchical relations directly from flat terminology lists without relying on text corpora. However, existing LLM-driven induction methods exhibit catastrophic performance degradation as concept sets scale from hundreds of terms to thousands, where even state-of-the-art closed-source backbones fail to preserve input coverage and global structural coherence.
This degradation stems fundamentally from two intrinsic structural failure modes embedded in naive divide-and-merge paradigms. First, Structural Fragmentation occurs during concept set partitioning: when partitioned blocks lack sufficient latent hierarchical connectivity, local induction either collapses concepts uniformly onto the local block root or hallucinates spurious local parent-child edges that permanently corrupt downstream integration. Second, Parent Displacement arises during the merge phase: because any given block contains only an isolated subset of the global taxonomy, missing intermediate nodes force true multi-hop ancestor-descendant paths to collapse into direct parent-child edges. Lifting these locally plausible subtrees as rigid monolithic units permanently bakes structural compression errors into the global hierarchy.
Addressing both weak local signals and global topological drift requires decoupling semantic abstraction from global structural reasoning, ensuring partitioning retains topological connectivity while transforming block-level relations into search constraints rather than immutable facts. Core idea: propose SPARROW, a scalable divide-and-merge framework that couples structure-preserving normalized spectral graph clustering to retain latent hierarchical connectivity within local blocks, with a constraint-guided incremental fusion mechanism that leverages block-level topological priors as pruning constraints to orchestrate candidate scoping, path-aware parent selection, and sibling-versus-parent structural arbitration.
Method¶
Overall Architecture¶
SPARROW follows a principled divide-and-merge paradigm to construct a globally coherent single-parent rooted tree \(\mathcal{T} = (\mathcal{V}, \mathcal{E})\) from an expansive flat concept set \(\mathcal{C}\). The overall architecture comprises three sequentially linked stages: Structure-Preserving Partitioning, Block-Level Taxonomy Induction, and Constraint-Guided Incremental Fusion.
In the partitioning stage, concepts are embedded into semantic vector space to form a sparse \(k\)-NN affinity graph, decomposed via normalized spectral clustering with an eigengap heuristic into compact, highly connected sub-blocks. In the block-level induction stage, each sub-block is processed independently by an LLM within a bounded context window to generate a local taxonomy. In the global merge stage, the largest block taxonomy is initialized as the primary structural seed, and remaining blocks are sequentially integrated in descending order of size; within each block, concepts are ingested in Breadth-First Search (BFS) order through a three-step attachment pipeline to update the evolving global hierarchy.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Input: Flat Concept Set 𝒞"] --> B["Structure-Preserving Partitioning<br/>kNN Affinity Graph + Spectral Eigengap"]
B --> C["Block-Level Taxonomy Induction<br/>Bounded Context Independent Local Trees"]
C --> D["Constraint-Guided Incremental Fusion<br/>Seed Taxonomy Init + Outer BFS Block Loop"]
D --> E["1. Constraint-Guided Candidate Scoping<br/>Restrict to Block Parent Subtree Excl. Siblings"]
E --> F["2. Path-Aware Parent Selection<br/>Top-K Retrieval + LLM Subsumption & Path Context"]
F --> G["3. Sibling-or-Parent Resolution<br/>Dynamic Intermediate Node Insertion & Re-parenting"]
G --> H["Output: Unified Global Taxonomy 𝒯"]
Key Designs¶
1. Structure-Preserving Spectral Partitioning: Mitigating Structural Fragmentation Standard geometric clustering methods such as K-means optimize for convex spherical clusters around Euclidean centroids, which fundamentally conflicts with the manifold topology of taxonomy subtrees—where gold subtrees exhibit high topological connectivity in semantic embedding space but only moderate centroid concentration. Partitioning via centroid clustering cuts vital vertical hierarchy lines, depriving local blocks of vertical inductive signal and causing local taxonomies to flatten out. SPARROW therefore deploys structure-preserving normalized spectral clustering over a sparse \(k\)-nearest-neighbor graph. For each concept \(c_i \in \mathcal{C}\) mapped to a dense embedding \(e_i\), edge weights are computed using a Gaussian radial basis kernel over cosine distance \(d_{ij} = 1 - \frac{e_i \cdot e_j}{\|e_i\| \|e_j\|}\) as \(W_{ij} = \exp(-\gamma d_{ij}^2)\) with \(\gamma = 1.0\). The cluster count \(B\) is dynamically determined using the spectral eigengap heuristic within an adaptive interval derived from backbone context capacity, \([\max(2, \lfloor 0.7 k^* \rfloor), \min(\lceil 1.3 k^* \rceil, n-1)]\) where \(k^* = \lceil n / s_m \rceil\). This maintains optimal intra-block edge retention and compactness, ensuring local blocks contain genuine vertical branches.
2. Constraint-Guided Candidate Scoping: Mitigating Search Complexity and Topological Drift When attaching concepts from an incoming block into the growing global tree, searching across all previously merged nodes introduces quadratic LLM inference cost and induces high parent displacement errors due to semantic distraction. SPARROW resolves this by converting the structural relations produced during block-level induction into global search constraints. Because nodes within an incoming block are traversed in BFS order, the block-level parent \(p\) of incoming node \(v\) is guaranteed to have already been attached to the global hierarchy. Furthermore, sibling relationships \(s \in \text{sibling}(v)\) identified during local induction rule out mutual subsumption. Consequently, the valid candidate parent space in the global tree is strictly bounded to the subtree of \(p\) while explicitly carving out the subtrees of all block siblings \(s\): $\(Candi(v) = subtree(p) \setminus \bigcup_{s \in sibling(v)} subtree(s)\)$ For unconstrained root concepts, the candidate pool defaults to all currently placed global nodes. This pruning shrinks the candidate pool into a targeted semantic corridor, eliminating cross-branch false attachments while dramatically lowering prompt token overhead.
3. Path-Aware Parent Selection: Aligning Hierarchical Subsumption with Depth Continuity Within the scoped candidate pool \(Candi(v)\), the top-\(K\) candidates (default \(K=10\)) are retrieved via embedding cosine similarity and submitted to the LLM for definitive parent selection. Instead of providing isolated concept labels, SPARROW enriches each candidate with its complete root-to-node taxonomy path and its current set of direct child nodes. The LLM evaluates three explicit hierarchical criteria: (1) Subsumption, requiring the candidate parent to semantically cover both the incoming query and all of its known descendants; (2) Granularity Alignment, preferring candidate parents whose existing children share a comparable degree of semantic abstraction with the query; and (3) Depth Continuity, avoiding abrupt skips across hierarchy levels. If no retrieved non-root candidate satisfies strict subsumption, the node is safely attached to the global ROOT, allowing fine-grained placement to be resolved adaptively by subsequent attachments.
4. Sibling-or-Parent Resolution: Restoring Compressed Multi-Hop Ancestries Because block partitioning isolates subsets of terms, intermediate concepts are frequently omitted during local induction, creating false direct parent-child edges that artificially compress taxonomy depth. Once candidate parent \(P\) is selected, SPARROW invokes a secondary LLM arbitration call to establish the topological placement of incoming node \(v\) relative to \(P\)'s existing children. If \(v\) matches the semantic abstraction level of \(P\)'s current children, it is attached as a co-equal sibling. Conversely, if \(v\) semantically subsumes a subset of \(P\)'s existing children, \(v\) is dynamically inserted as an intermediate parent between \(P\) and those subsumed children, actively re-parenting the affected subtree under \(v\). This online structural surgery dynamically reconstructs multi-hop ancestral chains without requiring costly global tree restructuring.
Benchmark & Evaluation Protocol¶
Experiments are evaluated on two primary real-world taxonomy benchmarks: the ACM Computing Classification System (CCS, pruned to a strict 1,768-concept single-parent tree spanning 6 levels of depth) and Google Product Taxonomy (Google, featuring 5,595 e-commerce concepts up to 7 hierarchical levels). Cross-domain and extreme-scale validation are further conducted on SemEval-2016 TExEval-2 Food (1K concepts) and Medical Subject Headings (MeSH, evaluated at 1K and 10K concepts). Structural quality is quantified through three complementary metrics: Node F1 (concept coverage), Edge F1 (direct parent-child correctness), and Ancestor F1 (global path consistency from root to leaf, highly sensitive to macro-level topological displacement). Baselines encompass one-pass generation (TaxoGPT), top-down layer-wise construction (Chain-of-Layer), and pairwise parent ranking (LLMscorer), evaluated across both commercial strong-context backbones (GPT-5) and open-weight constrained-context models (LLaMA3-8B-Instruct).
Key Experimental Results¶
Main Results¶
On the 1,000-concept evaluation setting, SPARROW demonstrates substantial improvements in global hierarchical fidelity, particularly in Ancestor F1. The main comparative results across GPT-5 and LLaMA3-8B-Instruct are summarized below:
| Dataset | Backbone | Method | Node F1 | Edge F1 | Ancestor P | Ancestor R | Ancestor F1 |
|---|---|---|---|---|---|---|---|
| CCS (1K) | GPT-5 | TaxoGPT | 0.855 | 0.278 | 0.696 | 0.277 | 0.397 |
| CCS (1K) | GPT-5 | Chain-of-Layer | 0.683 | 0.401 | 0.751 | 0.165 | 0.271 |
| CCS (1K) | GPT-5 | LLMscorer | 1.000 | 0.482 | 0.488 | 0.464 | 0.476 |
| CCS (1K) | GPT-5 | SPARROW | 0.969 | 0.412 | 0.670 | 0.582 | 0.623 |
| CCS (1K) | LLaMA3-8B | TaxoGPT | 0.030 | 0.006 | 0.029 | 0.001 | 0.002 |
| CCS (1K) | LLaMA3-8B | Chain-of-Layer | – | – | – | – | – |
| CCS (1K) | LLaMA3-8B | LLMscorer | 1.000 | 0.226 | 0.222 | 0.109 | 0.146 |
| CCS (1K) | LLaMA3-8B | SPARROW | 0.841 | 0.100 | 0.560 | 0.315 | 0.403 |
| Google (1K) | GPT-5 | TaxoGPT | 0.896 | 0.566 | 0.700 | 0.556 | 0.619 |
| Google (1K) | GPT-5 | Chain-of-Layer | 0.609 | 0.383 | 0.893 | 0.246 | 0.386 |
| Google (1K) | GPT-5 | LLMscorer | 0.995 | 0.588 | 0.402 | 0.519 | 0.453 |
| Google (1K) | GPT-5 | SPARROW | 0.977 | 0.579 | 0.770 | 0.721 | 0.745 |
| Google (1K) | LLaMA3-8B | TaxoGPT | 0.033 | 0.004 | 0.171 | 0.002 | 0.004 |
| Google (1K) | LLaMA3-8B | Chain-of-Layer | – | – | – | – | – |
| Google (1K) | LLaMA3-8B | LLMscorer | 0.916 | 0.253 | 0.304 | 0.119 | 0.171 |
| Google (1K) | LLaMA3-8B | SPARROW | 0.649 | 0.198 | 0.247 | 0.257 | 0.253 |
Ablation Study¶
Systematic ablations were performed on CCS and Google (1K) to isolate pipeline-stage impacts, followed by fine-grained component ablations of the fusion operators on Google (1K):
| Configuration / Variant | Stage / Focus | Node F1 | Edge F1 | Ancestor F1 | Mechanism & Impact |
|---|---|---|---|---|---|
| CCS Stage Pipeline | |||||
| ✗ Split + ✗ Merge | One-pass baseline (TaxoGPT) | 0.855 | 0.278 | 0.397 | Unbounded context induces severe hallucinations and omissions |
| ✓ Split + ✗ Merge | Divide-only (flat root placement) | 0.969 | 0.411 | 0.465 | Local edge precision improves, but cross-block paths remain severed |
| SPARROW (Full) | Spectral split + Constraint merge | 0.969 | 0.412 | 0.623 | Global tree consistency restored (+0.158 Ancestor F1 over unmerged) |
| Google Stage Pipeline | |||||
| ✗ Split + ✗ Merge | One-pass baseline (TaxoGPT) | 0.896 | 0.566 | 0.619 | Suffers when capturing deep multi-level hierarchies |
| ✓ Split + ✗ Merge | Divide-only (flat root placement) | 0.977 | 0.563 | 0.587 | High local precision but incomplete global paths |
| SPARROW (Full) | Spectral split + Constraint merge | 0.977 | 0.579 | 0.745 | Complete path reconstruction yielding +0.126 Ancestor F1 gain |
| Google Merge Operators | |||||
| w/o Scope | Remove candidate scoping | 0.977 | 0.547 | 0.484 | Anc. F1 drops 0.260; incurs 6.7× token explosion across all nodes |
| Sim.-only | Pure similarity parent selection | 0.977 | 0.406 | 0.374 | Anc. F1 drops 0.370; fails to discriminate semantic abstraction |
| Node-only | Parent selection without path context | 0.977 | 0.559 | 0.530 | Anc. F1 drops 0.214; missing macro context leads to misplacements |
| Always-sib. | Disable intermediate node insertion | 0.977 | 0.556 | 0.504 | Anc. F1 drops 0.240; locks in parent displacement and flattens tree |
| SPARROW (Full) | Complete fusion pipeline | 0.977 | 0.579 | 0.744 | Synergistic combination achieving peak structural recovery |
Key Findings¶
- Constrained Backbones Outperform Unstructured Strong Models: On CCS with the limited-capacity LLaMA3-8B backbone, SPARROW achieves an Ancestor F1 of 0.403, surpassing the monolithic GPT-5 TaxoGPT baseline (0.397). Unpartitioned baselines collapse completely on 8B models (TaxoGPT F1 drops to 0.002, while Chain-of-Layer crashes from prompt length overflow).
- Superior Pareto Efficiency in Token Budget: SPARROW consumes 62,312 total tokens on CCS-1K (10,254 local + 52,058 fusion), matching Chain-of-Layer (62,038) while more than doubling its Ancestor F1 (0.623 vs 0.271). Furthermore, it expends only ~15% of the token cost of LLMscorer (407,518 tokens) while outperforming it by 0.147 in Ancestor F1.
- Robustness at Extreme 10K Scale: In the 10,000-concept MeSH benchmark, baselines completely degrade (TaxoGPT and Chain-of-Layer obtain 0.011 and 0.015 Ancestor F1 respectively), whereas SPARROW retains an Ancestor F1 of 0.487, confirming that structural divide-and-merge eliminates context length scaling walls.
Highlights & Insights¶
- Topological Priors as Bounded Geometric Search Constraints: Rather than treating block taxonomies as immutable rigid subgraphs or discarding them after induction, SPARROW converts within-block ancestry into strict subtree search bounds (\(subtree(p) \setminus \bigcup subtree(s)\)), reconciling local inductive prior with global positioning flexibility.
- Spectral Connectivity Outperforms Convex Spatial Clustering: By demonstrating that true taxonomy subtrees form connected graph manifolds rather than spherical clusters in embedding space, the authors prove that normalized spectral clustering yields 76.6% intra-block edge retention (14.6% higher than K-means), establishing an optimal structural foundation for bounded local induction.
- Bi-directional Sibling-or-Parent Dynamic Grafting: Resolving whether an incoming concept is a peer or an intermediate ancestor circumvents the irreversible flattening problem inherent in single-pass top-down or bottom-up incremental insertion.
Limitations & Future Work¶
- Strict Single-Parent Tree Assumption: SPARROW is formally designed for rooted directed trees where each concept has exactly one parent, rendering it incapable of inducing polyhierarchical directed acyclic graphs (DAGs) where concepts belong to multiple parent domains.
- Vulnerability to Missing Intermediate Concepts in Closed Sets: The framework assumes a closed vocabulary; if vital intermediate superordinate categories are missing from the input concept set, the parent selection module is forced into boundary approximations or default root fallbacks.
- Sequential Ingestion Latency during Merge: Although candidate scoping drastically minimizes LLM token consumption, sequential BFS node attachment inside the inner loop presents an execution throughput bottleneck that could benefit from subtree-level parallelization.
Related Work & Insights¶
- vs TaxoGPT (Chen et al., 2023): TaxoGPT attempts global text generation via prompting in one shot, suffering from attention dispersion and severe token truncation as concept lists expand; SPARROW guarantees bounded prompt contexts and enforces global topological consistency through constraint-guided fusion.
- vs Chain-of-Layer (Zeng et al., 2024): Chain-of-Layer expands taxonomies layer-by-layer from the root down, causing candidate sets to balloon rapidly and failing irrevocably on limited-context models; SPARROW decouples induction into constant-size spectral blocks and reconstructs multi-hop paths incrementally.
- vs LLMscorer (Jain & Anke, 2022): LLMscorer conducts independent candidate parent ranking for each node, achieving high coverage but missing holistic tree topology at prohibitive \(O(N)\) token expenses; SPARROW scopes parent candidates via block structure, delivering higher ancestor fidelity at a fraction of the inference cost.
Rating¶
- Novelty: ⭐⭐⭐⭐☆ [Identifies two fundamental structural failure modes in divide-and-merge taxonomy induction and proposes an elegant spectral-clustering and constraint-scoped fusion solution]
- Experimental Thoroughness: ⭐⭐⭐⭐⭐ [Exhaustive evaluations across four domains up to 10K nodes, multiple model backbones, detailed component ablations, and token expenditure accounting]
- Writing Quality: ⭐⭐⭐⭐⭐ [Clear mathematical problem formulation, incisive dissection of structural failure modes, and well-designed conceptual illustrations]
- Value: ⭐⭐⭐⭐☆ [Offers an actionable, computationally efficient blueprint for scaling automated ontology and taxonomy construction with LLMs]