🤖 AI

DOSA: A Tree-Guided, Self-Regressive Framework for Long Document Structure Analysis

The paper proposes DOSA, a tree-guided, self-regressive framework that incrementally reconstructs document-level semantic trees by processing multi-page documents chunk-by-chunk to effectively capture long-range dependencies and heterogeneous layouts, achieving state-of-the-art performance on document structure analysis benchmarks.

Original authors: Bohou Li, Benjamin Sowell, Mehul Shah, Mark Lindblad, Henry Lindeman

Published 2026-07-28

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Bohou Li, Benjamin Sowell, Mehul Shah, Mark Lindblad, Henry Lindeman

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to understand a massive, multi-volume encyclopedia that was printed on loose sheets of paper, scattered across a giant floor. Some pages have pictures, some have lists, and some have big bold titles. To make sense of this mess, you don't just read the words; you have to figure out how the pieces fit together. Is that picture part of the paragraph above it? Is that list a child of the title, or is it a separate section entirely? This is the world of "visually-rich documents," where information isn't just a stream of text, but a complex puzzle of shapes, positions, and styles. For computers to truly "read" these documents—whether they are legal contracts, scientific papers, or slide decks—they need to solve a specific puzzle called Document Structure Analysis. They need to build a "semantic tree," which is like a family tree for the document's parts, showing who is the parent of whom and in what order everyone should be read. Without this, a computer might see a title and a paragraph as two unrelated strangers, missing the fact that they are actually a parent and child.

Enter DOSA (Document Structure Analyzer), a new method proposed by researchers at Glean Technologies to solve this puzzle for long, multi-page documents. Think of trying to build a 1,000-piece LEGO castle all at once; it's overwhelming, and if you make a mistake early on, the whole thing might collapse. Previous methods tried to look at the whole document at once, which is like trying to hold the entire castle in your hands while building it—it gets too heavy and the computer gets confused. DOSA takes a different approach: it builds the castle one small section at a time. It processes the document in "chunks," like assembling one room of the castle before moving to the next. But here is the clever twist: as it builds each new room, it doesn't just look at the bricks in its hand; it looks at the "rightmost branch" of the castle it has already built. This acts as a guide, telling the computer exactly which parts of the previous rooms are relevant to the new ones. By using this "tree-guided" map, DOSA avoids getting lost in the sheer size of the document.

The researchers found that this step-by-step, self-guided method works incredibly well. When they tested DOSA on five different datasets, including a very tricky one called DocHieNet filled with complex, multi-page layouts, it outperformed the current best methods. On that challenging benchmark, DOSA improved accuracy by up to 4 points on a scale called F1 and nearly 20 points on a scale called TEDS (which measures how similar the computer's tree is to the real one). Even more impressively, it beat powerful, general-purpose AI models like Gemini-2.5-Pro and GPT-5.2, suggesting that for this specific job of building document trees, a specialized, structured approach is better than just asking a giant AI to "guess" the structure. The paper suggests that by fusing visual clues (like where a box is on the page), text content, and the size of the objects, DOSA can reconstruct the document's logic with high precision, even without needing to memorize the entire document in one go. However, the authors note that while this method is robust, it isn't perfect; it currently focuses on tree structures and doesn't yet handle more complex web-like connections, like citations, and it can still be tripped up if it makes a mistake early on that it can't correct later.

Technical Summary: DOSA – A Tree-Guided, Self-Regressive Framework for Long Document Structure Analysis

Problem Definition

Document Structure Analysis (DSA) aims to uncover the logical, spatial, and semantic relations among page objects (e.g., headers, tables, text blocks) in visually-rich documents (PDFs, slide decks) to construct a semantic tree. While early work focused on single-page documents using visual features, modern applications require handling multi-page documents with long-range dependencies and heterogeneous layouts.

Existing transformer-based approaches for multi-page documents face significant challenges:

Computational Overhead: The quadratic complexity of self-attention makes processing documents with thousands of page objects prohibitive.
Attention Dilution: In long sequences, attention mechanisms often fail to focus on relevant elements, leading to accuracy degradation.
Cross-Page Modeling: Reconciling long-range dependencies across diverse page layouts remains non-trivial for standard architectures.

Methodology

The authors propose DOSA (DOcument Structure Analyzer), a unified framework that reformulates long-document structure analysis as an incremental, self-regressive semantic tree construction problem. Instead of processing an entire document in a single pass, DOSA operates chunk-by-chunk, using the partially constructed tree as structural context for subsequent predictions.

1. Self-Regressive Semantic Tree Construction

Chunking: The document is partitioned into $M$ chunks, each containing up to $N$ page objects (matching the transformer's input limit).
Incremental Update: Starting from the first chunk, the model predicts hierarchical (parent-child) and ordering (predecessor) relations. These predictions update the semantic tree $T_{i-1}$ to form $T_i$ .
Cycle Resolution: To handle potential structural inconsistencies (e.g., cycles) caused by classification errors, a decycling procedure removes the lowest-confidence edge. Conflicts between parent-child and ordering predictions are resolved using spatial ordering based on bounding boxes.

2. Tree-Guided Context Selection

To address the limitation of isolated chunk processing, DOSA leverages the intrinsic ordering of documents.

Rightmost Branch Invariant: Theoretically, if a page object in a new chunk has a parent in the previously constructed tree, that parent must lie on the rightmost branch of the tree (corresponding to the current reading order).
Soft Window Mechanism: To improve robustness against early prediction errors, DOSA employs a "rightmost-branches-based soft window." Context objects are retrieved starting from the rightmost branch of the partial tree. If the context window is not full, objects are added from the second rightmost branch, then the third, and so on. This preserves multiple structurally plausible candidates, mitigating error propagation.

3. In-Chunk Model Architecture

The backbone is a lightweight multimodal model consisting of three components:

Feature Extraction (Backbone): Extracts and fuses four feature types for each page object:
- Visual: ResNet-50 FPN with MultiScaleROIAlign.
- Semantic: Text content (or category fallback) encoded via BERT.
- Category: Integer-based embedding.
- Sizing: Normalized width, height, and area vectors.
- These are concatenated and projected via an MLP into a 1024-dimensional fused embedding.
Transformer Encoder: A 6-layer encoder processes the sequence of fused embeddings. It utilizes global positional encoding combining relative page indices within the chunk and normalized bounding box coordinates to capture spatial and cross-page order.
Relation Classifier: A multi-class classifier (MLP) predicts the parent and immediate predecessor for each object by concatenating candidate object representations. The model is trained using Focal Loss to handle class imbalance.

Key Contributions

Unified Framework: DOSA reformulates DSA as an incremental, self-regressive process, leveraging partially constructed trees as structural priors to enable scalable parsing of long documents.
Efficient Model Design: The framework integrates visual, semantic, categorical, and sizing features to predict relations without relying on large-scale document-specific foundation model pretraining.
Tree-Guided Context: The introduction of a tree-guided context selection mechanism (specifically the soft window on rightmost branches) allows the model to model long-range dependencies while avoiding the computational cost of full-document encoding.
Empirical Validation: Extensive experiments demonstrate that DOSA outperforms state-of-the-art methods and large language model baselines.

Experimental Results

Experiments were conducted on five benchmarks: arXivDocs, E-Periodica (single-page), and HRDS, HRDH, DocHieNet (multi-page).

Performance on Multi-Page Benchmarks: On the challenging DocHieNet benchmark, DOSA achieved improvements of approximately 4 F1 points and 19 TEDS points over the previous state-of-the-art (DHFormer).
Comparison with LLMs: DOSA significantly outperformed large language model baselines (Gemini-2.5-Pro and GPT-5.2) on DocHieNet, achieving an F1 of 81.80 vs. 69.53 (GPT-5.2) and a TEDS of 76.81 vs. 57.82. This suggests that explicit structural modeling is superior to purely generative reasoning for hierarchical reconstruction.
Ablation Studies:
- Context: Removing context or using simple sequential windows resulted in substantial performance drops, validating the necessity of tree-guided retrieval.
- Features: Removing category embeddings caused a massive performance drop (11.67 F1 points), highlighting their critical role. Sizing embeddings provided a modest but consistent benefit.
- Reading Order: Even when relying on inferred reading order rather than ground truth, DOSA outperformed DHFormer (which requires ground-truth order), demonstrating the framework's robustness.

Significance and Claims

The paper claims that DOSA addresses the critical bottleneck of processing long, multi-page documents by shifting from a "single-pass" paradigm to a "self-regressive, tree-guided" approach. By conditioning each inference step on a structurally relevant subset of context (the rightmost branches of the semantic tree), the framework effectively mitigates the sequence-length and attention-dilution limitations of transformers.

The authors emphasize that this approach enables scalable and coherent parsing of long documents without the prohibitive computational costs of full-document attention or the reliance on massive foundation models. The results suggest that task-aware mechanisms for identifying relevant context are more effective than implicit attention patterns, offering a practical solution for applications requiring accurate document chunking, structured extraction, and hierarchy-aware summarization.

Limitations

The authors acknowledge that the current framework does not model citation or reference relations (graph-based structures beyond trees) and that the soft window mechanism, while robust, does not fully eliminate the impact of early prediction errors. Future work may explore adaptive error-correction mechanisms.