# HELD: Extracting Variable-Depth Logical Document Hierarchy from Long Documents > HELD frames logical document hierarchy recovery as sequential tree construction: a put-or-skip binary classifier built on BiLSTM and CNN components decides, position by position, where to insert each physical object into a growing tree, enabling variable-depth hierarchies to be extracted from documents with hundreds of pages. - Authors: Bevaya AI Team - Published: 2026-04-02 - Paper: Preprint (arXiv) - Paper: Published (JCST 2022) - Source: Bevaya Labs, --- ## TL;DR HELD (Hierarchy Extraction from Long Document) treats logical document hierarchy recovery as sequential tree construction: a put-or-skip binary classifier decides where to insert each physical object into a growing rightmost-branch tree, handling variable-depth hierarchies up to 11 levels in documents with thousands of physical objects. On proprietary Chinese financial, English financial, and arXiv datasets it outperforms rule-based and sequence-labeling baselines by meaningful margins. The paper also proposes a stricter evaluation metric that requires the full root-to-node path to be correct, not just the depth. ## What kind of paper is this? **Dominant:** $\Psi\_{\text{Method}}$: The headline contribution is the HELD algorithm: a tree-construction procedure with a BiLSTM/CNN put-or-skip classifier, three traversal variants, optional explicit heading extraction, and an error-tolerance training strategy. The bulk of the paper ablates these design choices. **Secondary:** $\Psi\_{\text{Resource}}$: Three new proprietary datasets are constructed (1,030 Chinese financial, 1,203 English financial, and 1,732 arXiv documents) with multi-annotator hierarchy labels. The documents themselves are drawn from public sources (CNINFO, arXiv), but the annotated hierarchies are not released. $\Psi\_{\text{Evaluation}}$: The paper also introduces a path-correctness metric that is strictly stronger than the depth-only measure used in prior work. ## What is the motivation? PDF and other rendered document formats preserve visual layout but discard the logical hierarchical structure that was present in the original editing format (e.g., WORD, LaTeX). Recovering this structure is a prerequisite for hierarchical browsing, passage retrieval, high-quality information extraction, and document re-flow. Prior approaches fall into three families, each with limitations the authors identify: - **Rule-based methods** (e.g., HEPS [Manabe & Tajima, 2015]) rely on assumptions such as "headings with the same visual style occupy the same hierarchical depth." These assumptions break down on financial disclosures and other domain-specific documents where the same numbering pattern appears at multiple levels. - **Sequence-labeling methods** (e.g., TOC [Bentabet, ICDAR 2019], Rahman & Finin 2017) classify each physical object into an absolute depth label. Because the label space is fixed, they cannot generalize to unseen depths, and because they use a window of neighboring objects, they struggle with the very long distances found in hundred-page documents. - **Tree-generation methods** (Pembe & Güngor, NLE 2014) build a tree node by node and capture containment/parallel relationships, but that prior work uses logistic regression and lacks a systematic study of design variants. The HELD paper targets long documents specifically. The authors show that 90% of headings in their benchmark sit at depths 3 through 7, with a maximum of 11, which is well beyond the 4-level cap that existing datasets assume. ## What is the novelty? The central idea is to view hierarchy construction as sequential insertion into a tree, guided by a binary classifier that answers "should I put the current node here, or skip to the next candidate position?" ### Rightmost-branch insertion At any point during construction, the only positions that can receive the next physical object (to preserve the pre-order reading sequence) are the last-child slots of the nodes on the current rightmost branch. Formally, the rightmost branch is the path from the root $\phi$ to the current rightmost leaf; all possible insertion positions $S\_i = \\{s\_j^i\\}\_{j=1}^{M\_i}$ are the last-child positions of nodes on this branch. ### Objective function The model is trained by maximizing the log-likelihood of inserting each node $c\_i$ at the correct position $s\_i^{\ast}$ while minimizing it at all incorrect positions: $$ \log P(T) = \sum\_{i=1}^{N} \log P(c\_i \mid \mathcal{T}\_{c\_1, \dots, c\_{i-1}}) $$ Expanding the per-node term: $$ \log P(c\_i \mid \mathcal{T}\_{c\_1, \dots, c\_{i-1}}) = \sum\_{j=1}^{M\_i} \left( \mathbf{1}(s\_j^i = s\_i^{\ast}) \cdot \log P(c\_i \mid ctx(s\_j^i)) - \mathbf{1}(s\_j^i \neq s\_i^{\ast}) \cdot \log P(c\_i \mid ctx(s\_j^i)) \right) $$ This is a binary cross-entropy objective over all candidate positions for each node. ### Put-or-skip classifier For each candidate position $s$, the classifier estimates $P(c \mid ctx(s))$ using the local context: the immediate parent $z$ and the existing siblings $g\_1, \dots, g\_K$ at that position. Three Bi-LSTMs are used in sequence: one encodes the text of each element into a vector $\mathbf{v}\_x$; a second combines the text representations of the candidate context into a final text vector $\mathbf{v}$; a third does the same for format features (font family, size, color, bold, italic, centering, indent) to produce $\mathbf{u}$. The combined $[\mathbf{v}; \mathbf{u}]$ is passed through a feed-forward layer and a sigmoid to produce the insertion probability. ### Traversal order variants Three strategies for which positions to probe are studied: - **Traversal-all**: probe all positions, select the highest-probability one. - **Root-to-leaf**: probe from root toward the leaf and return the first position whose probability exceeds 0.5. - **Leaf-to-root**: same as root-to-leaf but in reverse order. The authors prove theoretically that $N\_{l2r} < N\_{r2l} < N\_{all}$ in terms of classifier calls, where the subscripts follow the paper's abbreviations: l2r = leaf-to-root, r2l = root-to-leaf, all = traversal-all; $N\_{\cdot}$ counts how many positions are probed under each strategy given a perfect oracle. Root-to-leaf offers a favorable accuracy-efficiency tradeoff in practice. ### Two-step explicit heading extraction In the one-step variant, heading and non-heading objects are inserted by the same procedure. In the two-step variant, a separate heading classifier (Bi-LSTM + multi-layer CNN + self-attention) first identifies headings. The tree is then built over headings only; non-headings are appended as leaf children of the immediately preceding heading. This reduces the number of nodes the put-or-skip module must process by roughly 75%, producing an 8.3$\times$ speedup while improving accuracy. ### Error-tolerance training Because earlier nodes may be misplaced during inference, the authors augment training data by simulating random misplacements and generating additional training tuples from the resulting imperfect trees. This is most beneficial on the noisier English dataset. ### Path-correctness metric Previous work defines a node as correctly inserted when it ends up at the right depth. HELD introduces a stricter criterion: a node is correct if and only if its entire path from the root matches the ground-truth path. This matters for downstream applications such as passage retrieval, where ancestor identity, not just depth, is needed. ## What experiments were performed? ### Datasets Three proprietary datasets are constructed from publicly downloadable documents: - **Chinese dataset**: 1,030 prospectuses and annual reports from CNINFO (China Securities Exchange); split 830/100/100. - **English dataset**: 1,203 annual reports from Hong Kong Exchange; split 1,110/100/100 (approximately). - **arXiv dataset**: 1,732 scientific papers from arXiv; split 1,432/150/150. Documents have at least 500 physical objects, and hierarchies reach up to 11 levels. Each document was annotated by at least two annotators with conflict resolution by a senior annotator. ### Baselines - **HEPS** (Manabe & Tajima, 2015): rule-based, adapted to PDF (web-page features removed). - **TOC** (Bentabet, ICDAR 2019): sequence-labeling with CNN replacing LSTM for the longer documents. - **Pembe's model** (Pembe & Güngor, NLE 2014): tree-generation with logistic regression. ### Evaluation Node accuracy (fraction of nodes with a fully correct root-to-node path) and per-level $F1\_k$ are the primary measures. Efficiency is tracked via average processing time per document and the number of put-or-skip classifier calls (#inquiry). Downstream evaluation uses passage retrieval on 110 Chinese IPO prospectuses with 138 queries (88 train / 50 test), measured by mAP and recall@k. A GBDT ranker is trained on BM25 plus four hierarchy-derived features: BM25AncMax (max BM25 over ancestor headings), SameWordAnc (word overlap with ancestor text), Pos (absolute sibling position), and PosRatio (relative sibling position). ### Hyperparameters - Character embeddings: skip-gram, 24 dimensions. - Heading recognition network: 9-layer Network-in-Network with kernel sizes 5-1-5-5-1-5-5-1-5 and increasing channel counts (128 to 512). - Put-or-skip Bi-LSTMs: hidden dimensions of 128 ($\mathbf{v}\_x$), 512 ($\mathbf{u}\_T$, visual), and 64 ($\mathbf{u}\_F$). - Optimizer: Adam, learning rate 0.00005, mini-batch size 128. - Hardware: 2 NVIDIA Titan 1080Ti GPUs with Horovod distributed training. - Beam size: 1 (greedy search; beam size 3 adds roughly 10$\times$ cost with minimal accuracy change: +0.0005 on Chinese but -0.0026 on English). ## What are the outcomes/conclusions? ### Accuracy vs. baselines Using the path-correctness metric, the best HELD variant (2step, traversal-all, greedy) achieves: - Chinese: 0.9731 vs. 0.3764 (HEPS), 0.9403 (TOC), 0.9339 (Pembe) - English: 0.7301 vs. 0.4779 (HEPS), 0.6436 (TOC), 0.6563 (Pembe) - arXiv: 0.9578 vs. 0.8375 (HEPS), 0.8908 (TOC), 0.9034 (Pembe) The English dataset is hardest because visual/textual cues are more ambiguous (many headings match no numbering regex, and heading depth is less predictable from format alone). ### Traversal order Root-to-leaf and traversal-all achieve nearly identical accuracy. Root-to-leaf is 1.2$\times$ faster; leaf-to-root is 2.4$\times$ faster but noticeably less accurate. The paper recommends root-to-leaf for general use. ### Two-step vs. one-step Explicit heading extraction increases accuracy by 1.5 to 11 percentage points and reduces inference time by 8.3$\times$ by cutting the number of nodes the put-or-skip module handles. ### Feature ablation (put-or-skip) Removing sibling features hurts more than removing parent features, especially on English (accuracy drops from 0.7301 to 0.6445 without siblings, vs. 0.7007 without the parent). Sibling context carries strong cues because consecutive headings at the same level share formatting and numbering patterns. ### PDFLux noise experiment When the commercial PDFLux layout recognizer (F1 approximately 0.97 on physical object detection) is used instead of ground-truth physical objects, overall accuracy drops by 1.5 percentage points on Chinese and 0.6 on English. The hierarchy extraction is reasonably robust to layout recognition noise at this quality level. ### Passage retrieval Combining all four hierarchy features with BM25 raises mAP from 0.149 to 0.338 and recall@1 from 0.083 to 0.218 on the Chinese prospectus subset. BM25AncMax and position features contribute the most individually. ### Limitations The authors acknowledge that the greedy construction process creates cascading errors: if a high-level heading is placed incorrectly, all of its descendants inherit the error. The proposed path-correctness metric makes this failure mode visible (unlike depth-only metrics), and the authors suggest Monte Carlo Tree Search as a future remedy. The datasets are also not publicly released, limiting independent replication. ## Reproducibility ### Models - The put-or-skip classifier is a stack of three Bi-LSTMs with hidden dimensions 128, 512, and 64, combined with a feed-forward layer and sigmoid output. The heading classifier uses a Bi-LSTM followed by 9 CNN layers (Network-in-Network) and a self-attention layer. - No pretrained checkpoints are released. The paper does not describe any pretrained language model backbone; text is encoded from scratch using character embeddings. - Character embeddings are trained with skip-gram, dimension 24. ### Algorithms - Training: Adam optimizer, learning rate 0.00005, batch size 128. No number of training epochs or steps is reported. - Error-tolerance augmentation: random misplacements are simulated during training data generation to expose the model to imperfect predecessor insertions. - Inference: greedy (beam size 1) with root-to-leaf traversal for the recommended configuration. - No mixed precision, gradient clipping, or learning rate schedule details are reported. ### Data - All three datasets are annotated by the authors from publicly downloadable documents (CNINFO and arXiv). The annotations are not released. - Multi-annotator pipeline: at least two annotators per document; a senior annotator resolves conflicts. - Physical object detection uses the commercial PDFLux tool, not a released open-source system. - No data augmentation beyond the error-tolerance training examples is described. ### Evaluation - Primary metric is node accuracy under the path-correctness definition: a node is correct iff its full root-to-node path matches ground truth. Per-level $F1\_k$ values are also reported. - Efficiency is measured as average wall-clock seconds per document and #inquiry (put-or-skip calls). - Passage retrieval uses mAP and recall@k (k = 1, 5, 10) with GBDT ranking. - No error bars or multi-run statistics are reported for any result. ### Hardware - Training: 2 NVIDIA Titan 1080Ti GPUs, Horovod for distributed parameter updates. Total GPU-hours are not reported. - Inference: the recommended 2step root-to-leaf configuration processes a document in approximately 36 seconds on the training hardware; traversal-all takes 42.58 seconds. These are wall-clock times, not normalized to a standard GPU. - No cloud cost or energy consumption estimates. ## BibTeX ```bibtex @article{cao2022held, title={Extracting Variable-Depth Logical Document Hierarchy from Long Documents: Method, Evaluation, and Application}, author={Cao, Rongyu and Cao, Yixuan and Zhou, Ganbin and Luo, Ping}, journal={Journal of Computer Science and Technology}, volume={37}, pages={699--718}, year={2022}, doi={10.1007/s11390-021-1076-7} } ```