# Detect-Order-Construct: A Tree-Based Framework for Hierarchical Document Structure Analysis

> A research note on Detect-Order-Construct (Wang et al., 2024), a three-stage pipeline for hierarchical document structure reconstruction that introduces the Comp-HRDoc benchmark for simultaneous evaluation of page object detection, reading order prediction, TOC extraction, and full structure reconstruction.

- Authors: Hunter Heidenreich
- Published: 2026-04-02
- Benchmark: Comp-HRDoc Benchmark <https://github.com/microsoft/CompHRDoc>
- Source: Bevaya Labs, <https://labs.bevaya.ai/>

---


## TL;DR

Wang et al. propose Detect-Order-Construct, a three-stage framework that decomposes hierarchical document structure reconstruction into page object detection (Detect), reading order prediction (Order), and table-of-contents extraction (Construct). All three stages are cast as relation prediction tasks solved by multi-modal transformer-based models with structure-aware designs. The authors also introduce Comp-HRDoc, the first benchmark to evaluate all four sub-tasks of hierarchical document structure analysis concurrently.

## What kind of paper is this?

**Dominant:** $\Psi\_{\text{Method}}$: The central contribution is a new pipeline architecture and a family of multi-modal, transformer-based relation prediction models tailored to chain (reading order) and tree (TOC) structures. Most of the paper describes the Detect, Order, and Construct modules, their architectural details, and ablations verifying each design choice.

**Secondary:** $\Psi\_{\text{Resource}}$: The paper introduces Comp-HRDoc, a new benchmark built on top of the HRDoc-Hard dataset. This benchmark extends existing annotations to support simultaneous evaluation of four sub-tasks, and is released publicly.

**Secondary:** $\Psi\_{\text{Evaluation}}$: The paper also proposes a new metric, Reading Edit Distance Score (REDS), for evaluating reading order prediction when multiple independent reading-order groups are present, addressing a gap in existing metrics.

## What is the motivation?

Document structure analysis has historically been fragmented: prior work tackled page object detection, reading order prediction, and table-of-contents (TOC) extraction as isolated tasks. No end-to-end system or benchmark addressed all of them together.

Key limitations the authors identify in prior work:

- **DocParser** (Rausch et al., 2021) handled physical layout parsing with rule-based relation classification, but ignored logical structure such as TOC.
- **HRDoc / DSPS** (Ma et al., 2023) introduced a hierarchical parsing system, but assumed reading order was provided as ground truth. Its line-level relation prediction scaled quadratically with the number of text lines, making it impractical for long documents.
- Existing reading-order metrics (e.g., full-ranking metrics from Quirós et al.) assume a single linear reading order and cannot handle documents with multiple independent reading-order groups (e.g., newspapers with parallel articles).

The authors frame hierarchical document structure reconstruction as recovering a rooted tree $H$ whose nodes are page objects and whose edges encode three relationship types: text-region reading order, graphical-region attachment (caption-to-figure, footnote-to-table), and TOC parent-child relationships among section headings.

## What is the novelty?

### Unified relation prediction formulation

All three pipeline stages are cast as dependency-parsing-style relation prediction problems. For any pair of elements $(e\_i, e\_j)$, a score is computed:

$$
f\_{ij} = FC\_q(F\_{e\_i}) \circ FC\_k(F\_{e\_j}) + \text{MLP}(r\_{b\_{e\_i}, b\_{e\_j}})
$$

where $\circ$ is the dot product, $FC\_q$ and $FC\_k$ project element representations into distinct feature spaces, and $r\_{b\_{e\_i}, b\_{e\_j}}$ is a spatial compatibility feature vector encoding relative position and size. A softmax cross-entropy loss (rather than binary cross-entropy) enforces a single-successor constraint consistent with the chain structure of reading order:

$$
s\_{ij} = \frac{\exp(f\_{ij})}{\sum\_N \exp(f\_{ij})}
$$

### Detect module: hybrid top-down and bottom-up detection

A shared CNN backbone (ResNet) provides multi-scale features. A top-down detector (DINO or Mask2Former) localises graphical objects (tables, figures, displayed formulas). A bottom-up text-region detection model then groups text lines into text regions using the intra-region reading order predicted by the relation head, followed by plurality voting for logical role classification. Multi-modal representations fuse visual embeddings (RoIAlign on fused feature maps), text embeddings from BERT, and 2D positional embeddings:

$$
U\_{t\_i} = FC(\text{Concat}(V\_{t\_i},\, T\_{t\_i},\, B\_{t\_i}))
$$

A single-layer Transformer encoder enhances these representations via self-attention before the relation and classification heads operate.

### Order module: inter-region reading order with attention fusion

For each detected text region, an attention mechanism aggregates the constituent text-line features produced by the Detect module into a single region representation:

$$
\begin{aligned}
\alpha\_{tn\_j} &= FC\_1(\tanh(FC\_2(F\_{tn\_j}))) \\\\
w\_{tn\_j} &= \frac{\exp \alpha\_{tn\_j}}{\sum\_j \exp \alpha\_{tn\_j}} \\\\
U\_{O\_n} &= \sum\_j w\_{tn\_j} F\_{tn\_j}
\end{aligned}
$$

A three-layer Transformer encoder then models interactions among all page objects before the inter-region reading order relation head predicts both the successor and the relation type (text-region order vs. graphical-region attachment).

### Construct module: tree-aware TOC relation prediction

Given section headings in predicted reading order, the Construct module uses Rotary Positional Embedding (RoPE) to inject order information into a Transformer encoder. The TOC Relation Prediction Head predicts both parent-child and sibling relations simultaneously. Final TOC construction uses a greedy tree-insertion algorithm (Algorithm 1 in the paper) that inserts each heading into the rightmost subtree of the growing tree by combining parent and sibling scores element-wise, enforcing a valid tree structure during decoding.

### Comp-HRDoc benchmark and REDS metric

Comp-HRDoc extends HRDoc-Hard (1,000 train / 500 test documents) with new annotations for page object detection (segmentation-level) and reading order. The Reading Edit Distance Score (REDS) is defined as:

$$
\text{REDS} = 1 - \frac{D}{N}
$$

where $D$ is the minimum total Levenshtein distance between predicted and ground-truth reading-order groups (matched via Hungarian assignment) and $N$ is the total number of basic units. Paragraph boundary markers are included as explicit tokens so that paragraph segmentation errors are penalised within the reading-order evaluation.

## What experiments were performed?

### Datasets

- **PubLayNet**: 340k training pages from PubMed Central, 5 object classes. Metric: COCO-style mAP at IoU 0.50:0.95.
- **DocLayNet**: 69k human-annotated pages from diverse document types, 11 object classes. Metric: COCO-style mAP.
- **HRDoc**: Human-annotated hierarchical reconstruction dataset. Two splits: HRDoc-Simple (1,000 docs) and HRDoc-Hard (1,500 docs). Metrics: per-class F1 for semantic unit classification; Micro- and Macro-STEDS for hierarchical reconstruction.
- **Comp-HRDoc**: The authors' new benchmark (1,000 train / 500 test, drawn from HRDoc-Hard). Metrics: segmentation mAP, REDS, and Semantic-TEDS for TOC and reconstruction.

### Baselines

- Page object detection: Mask R-CNN, Faster R-CNN, YOLOv5, DINO, Mask2Former.
- Reading order: enhanced replication of the partial-order algorithm of Quirós et al. (2022).
- TOC extraction: Multimodal Tree Decoder (MTD, Hu et al., 2022).
- Hierarchical reconstruction: DSPS Encoder from HRDoc (Ma et al., 2023), evaluated with ground-truth reading order and bounding boxes as upper-bound conditions.

### Ablations

- Hybrid strategy vs. pure Mask2Former for detection.
- Visual-only vs. visual+text modalities in the Detect and Construct modules.
- Removing sibling-finding head from TOC Relation Prediction Head.
- Removing the tree-insertion algorithm.
- Replacing softmax cross-entropy with binary cross-entropy loss.

## What are the outcomes/conclusions?

### Page object detection

On DocLayNet, the proposed Detect module achieves 81.0% mAP, compared to 76.8% for YOLOv5 (the prior leading method). Gains are especially pronounced for Page-footer (90.0% vs. 61.1%) and Section-header (83.2% vs. 74.6%). On PubLayNet, the Vision+Text variant reaches 96.5% mAP on the validation set, outperforming prior multimodal methods such as VSR (95.7%).

### Comp-HRDoc end-to-end results

On the authors' own benchmark (Table 6 in the paper):

| Sub-task | Metric | Best prior | Ours |
|---|---|---|---|
| Page object detection | Seg mAP | 73.54% (Mask2Former) | 88.06% |
| Reading order (text) | REDS | 0.7741 (Quirós et al.) | 0.9319 |
| Reading order (graphical) | REDS | 0.8583 (Quirós et al.) | 0.8637 |
| TOC extraction | Micro-STEDS | 0.6755 (MTD) | 0.8605 |
| Hierarchical reconstruction | Micro-STEDS | 0.6903 (DSPS w/ GT) | 0.8371 |

The DSPS baseline for hierarchical reconstruction was allowed ground-truth reading order and bounding boxes; the proposed system uses only predicted values.

### HRDoc hierarchical reconstruction

On HRDoc-Hard, the proposed method exceeds DSPS Encoder by approximately 16.6 percentage points in Micro-STEDS and 15.8 points in Macro-STEDS, despite not receiving ground-truth reading order as input.

### Key ablation findings

The tree-insertion algorithm is the most critical single component for TOC extraction: removing it drops Micro-STEDS from 0.8605 to 0.7111. Switching to binary cross-entropy loss causes a similar drop (to 0.7002), confirming the importance of the softmax dependency-parsing formulation. The hybrid detection strategy accounts for a 9.86% mAP gain over pure Mask2Former for page object detection. Adding text modality adds another 4.66% for semantically sensitive categories.

### Limitations

- The Construct module assumes section headings have been correctly identified by earlier stages; heading recognition errors propagate directly into TOC quality.
- Section numbers play a large role in the model's ability to infer heading hierarchy; documents without numbered sections cause notable failures.
- The framework has so far been evaluated only on structured academic and technical PDF documents. Extension to contracts, financial reports, and handwritten material is left for future work.
- Future work also mentions graph-based logical structures, which the current tree-based formulation cannot directly represent.

## Reproducibility

### Models

- **Backbone**: ResNet-50 for PubLayNet/DocLayNet; ResNet-18 for HRDoc/Comp-HRDoc (to reduce GPU memory for multi-page processing).
- **Graphical object detector**: DINO for PubLayNet/DocLayNet; Mask2Former for HRDoc/Comp-HRDoc.
- **Text encoder**: BERT-Base (uncased), used to extract text-line embeddings.
- **Transformer encoder (Detect module)**: 1-layer, 12 heads, 768 hidden dim, 2048 FFN dim.
- **Transformer encoder (Order module)**: 3-layer, same hyperparameters.
- Pretrained weights for ResNet are from ImageNet classification; BERT weights are from the standard HuggingFace BERT-Base release. No model weights for the trained system are reported as publicly available.

### Algorithms

- **Optimizer**: AdamW; betas (0.9, 0.999), epsilon 1e-8.
- **PubLayNet**: lr 1e-5 (backbone), 2e-5 (BERT); weight decay 1e-4 (backbone), 1e-2 (BERT); batch size 16; 12 epochs; lr divided by 10 at epoch 11.
- **DocLayNet**: same lr schedule, 24 epochs, lr divided by 10 at epoch 20.
- **HRDoc / Comp-HRDoc**: lr 2e-4 (backbone), 4e-5 (BERT); weight decay 1e-2 for both; batch size 1; 20 epochs; linear warmup for 2 epochs then linear decay to 0.
- **Multi-scale training**: shorter side randomly chosen from [512, 640, 768] (PubLayNet/DocLayNet) or [320, 416, 512, 608, 704, 800] (HRDoc/Comp-HRDoc); longer side capped at 800 or 1024, respectively. Test: shorter side 640 or 512.
- **Loss**: softmax cross-entropy (dependency parsing formulation) for all relation prediction heads.

### Data

- PubLayNet: publicly available, IBM license (research use). ~340k training pages from PubMed Central.
- DocLayNet: publicly available on HuggingFace, CC-BY-4.0. ~69k human-annotated pages.
- HRDoc: publicly available (AAAI 2023 release); license not explicitly stated in the paper.
- Comp-HRDoc: released at `https://github.com/microsoft/CompHRDoc` under the MIT license (per the repository).

### Evaluation

- **PubLayNet / DocLayNet**: COCO-style mAP at IoU thresholds 0.50:0.05:0.95.
- **HRDoc semantic unit classification**: per-class F1 score.
- **HRDoc / Comp-HRDoc hierarchical reconstruction**: Semantic-TEDS (Micro and Macro), which measures tree-edit distance on the predicted vs. ground-truth document trees weighted by semantic content.
- **Comp-HRDoc reading order**: REDS (proposed in this paper), accounting for multiple reading-order groups via Hungarian matching and including paragraph boundary tokens.
- Comparisons for hierarchical reconstruction use DSPS Encoder with access to ground-truth reading order and bounding boxes, which is a favourable baseline condition. The end-to-end evaluation in Comp-HRDoc is therefore more demanding for the proposed system.
- No error bars or statistical significance tests are reported; results are single-run.

### Hardware

- All experiments: 8 Nvidia Tesla V100 GPUs (32 GB memory each).
- Training time is not reported.
- Inference hardware and latency are not reported.

## BibTeX

```bibtex
@article{wang2024detectorderconstruct,
  title={Detect-Order-Construct: A Tree Construction based Approach for Hierarchical Document Structure Analysis},
  author={Jiawei Wang and Kai Hu and Zhuoyao Zhong and Lei Sun and Qiang Huo},
  journal={Pattern Recognition},
  year={2024},
  doi={10.1016/j.patcog.2024.110426}
}
```