Skip to content

Scroll-Net: Geometry-Aware Constrained Decoding for Multi-Page Document Hierarchy Parsing

Conference: EMNLP 2026
Paper: ACL Anthology
Area: Multimodal VLM
Keywords: Multi-Page Document Hierarchy Parsing, Scroll-Space Coordinate Mapping, Causal Prefix Constrained Decoding, Dual-Stream Disentanglement, Hierarchical Document Structure Analysis

TL;DR

Scroll-Net projects multi-page layouts into a unified continuous scroll-space coordinate frame and decouples geometric and semantic cues via a dual-stream encoder, while using a hard reading-order causal prefix mask and Top-K geometric pruning to guarantee acyclic hierarchical trees and drop autoregressive parent decoding complexity from \(O(N^2)\) to \(O(NK)\).

Background & Motivation

Hierarchical Document Structure Analysis (HDSA) aims to reconstruct the fine-grained logical containment tree and consistent sequential reading order from visually rich documents. Both representations serve as essential structural foundations for downstream document question answering, long-form document comprehension, and agentic information retrieval. However, real-world academic papers, financial prospectuses, and historical archives inevitably span multiple pages. Pagination breaks the continuous flow of layout by confining elements to isolated, page-local normalized coordinate frames, rendering standard distance-based geometric proximity completely uninformative across page boundaries. Existing page-wise pipelines typically parse individual pages independently and attempt post-hoc stitching with heuristic grammars, which severs cross-page structural continuity. Conversely, sequence-based formulations flatten two-dimensional visual layouts into one-dimensional token streams, obscuring fine-grained spatial locality and entangling geometry with textual semantics.

The core tension in multi-page HDSA stems from a triad of interrelated bottlenecks: geometric discontinuity across isolated page frames, the mutual confounding of spatial proximity and semantic affinity, and quadratic decoding complexity. In dense multi-column layouts, spatially adjacent blocks often belong to distinct narrative sections, whereas a section header and its terminating paragraphs frequently span multiple physical pages; without explicit inductive geometric modeling, models disproportionately rely on semantic similarity, which fails when text patterns repeat. Furthermore, conventional joint prediction heads conduct exhaustive pairwise scoring over all document block pairs. This dense formulation induces a quadratic \(O(N^2)\) computational and memory cost, and in the absence of rigorous structural constraints, unconstrained greedy decoding frequently generates topological pathologies such as self-loops and directed cycles.

To overcome these structural hurdles, this work recognizes that in standard document tree annotations following depth-first search (DFS) pre-order traversal, every logical parent node strictly precedes its descendant blocks in the sequential reading order. By explicitly modeling reading order as a temporal backbone, parent prediction can be reformulated as an incremental backward-pointer selection task over a strictly valid historical prefix. Core idea: project multi-page local coordinates into a unified vertical scroll-space frame and decouple geometry from semantics via a dual-stream architecture, then enforce a hard reading-order causal prefix mask and Top-K geometric candidate pruning during autoregressive pointer decoding to produce guaranteed acyclic logical trees with \(O(NK)\) complexity.

Method

Overall Architecture

The Scroll-Net pipeline operates across four coordinated stages: scroll-space coordinate projection, geometry-guided dual-stream encoding, Sinkhorn-based reading order permutation estimation, and sequentially constrained autoregressive pointer decoding. Given a multi-page document of \(P\) pages comprising \(N\) layout blocks, the system first maps page-local bounding boxes into a unified continuous scroll space \(\mathcal{M}\). The dual-stream encoder processes mapped coordinates and multimodal block features through separate Pre-LN Transformer backbones, modulates semantic representations via bidirectional cross-attention, and fuses them via adaptive gating. A Sinkhorn sorting head predicts the global reading order permutation. Finally, a pointer network traverses nodes sequentially according to the predicted order, restricting parent candidate search to an active prefix defined by the causal mask and pruned by scroll-space geometric compatibility.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    In["Multi-Page Document Input<br/>P Pages, N Blocks with Page-Local BBoxes & Visual Features"] --> S1["Scroll-Space Coordinate Mapping<br/>Project Local BBoxes to Continuous Vertical Strip M"]
    S1 --> S2["Geometry-Guided Dual-Stream Encoder<br/>Independent Transformers & Bidirectional Cross-Attention"]
    S2 --> S3["Sinkhorn Reading Order Prediction<br/>Global Permutation via Iterative Doubly-Stochastic Normalization"]
    S3 --> S4["Hard Reading-Order Causal Prefix Constraint<br/>Mask Out Future Candidates to Guarantee Acyclic Decoded Trees"]
    S4 --> S5["Top-K Scroll-Space Geometric Candidate Pruning<br/>Narrow Candidate Pool to Top-K to Cut Decoding to O(NK)"]
    S5 --> Out["Acyclic Logical Hierarchy & Reading Order<br/>Rooted Ordered Document Tree T=(V, E, r, ฯ€)"]

Key Designs

1. Scroll-Space Coordinate Mapping: Resolving cross-page geometric discontinuity across isolated coordinate frames

In standard paginated document pipelines, elements located at the bottom of page \(p\) and the top of page \(p+1\) are separated by an artificial coordinate gap despite being visually and logically continuous. Scroll-Net introduces a globally continuous scroll space \(\mathcal{M} = [0, 1] \times \mathbb{R}_{\ge 0}\), conceptualizing the multi-page document as a single vertical strip. For an arbitrary bounding box \(c = (cx, cy, w, h)\) residing on page \(p \in \{1, \dots, P\}\), the transformation function \(\Phi: \mathcal{P} \to \mathcal{M}\) applies a page-indexed vertical shift: $$ \tilde{c}_x = cx, \quad \tilde{c}_y = cy + p - 1, \quad \tilde{w} = w, \quad \tilde{h} = h $$ By assuming unit-normalized page heights, this mapping places each page \(p\) onto the interval \([p-1, p)\) along the continuous vertical axis. Under \(\mathcal{M}\), the pairwise Euclidean distance \(d_{\mathcal{M}}\) and continuous relative offsets are globally comparable across all block pairs, enabling unified computation of \(D_g\)-dimensional pairwise geometric feature vectors \(f_{ij}\) and supporting 2D relative positional encoding (2D-RPE) across the entire document.

2. Geometry-Guided Dual-Stream Disentanglement and Contrastive Alignment: Disentangling spatial proximity from semantic affinity in dense multi-column layouts

Physical adjacency does not guarantee logical affiliation: adjacent blocks across columnar gutters belong to distinct sections, while headings and their trailing paragraphs may span multiple pages. The dual-stream encoder processes geometry and semantics in distinct representational subspaces. The geometric stream projects mapped coordinates \(\tilde{x}_i\) concatenated with a learnable page embedding \(d_p\) into dimension \(d\), while the semantic stream independently projects LayoutLMv3 features \(s_i \in \mathbb{R}^{d_s}\) to dimension \(d\). Both streams pass through separate Pre-LN Transformer encoders (\(L_e\) layers) before exchanging information across \(L_f\) bidirectional cross-attention layers. Semantics are updated conditioned on the geometry-updated stream to inject a geometry-first inductive bias, followed by a dynamic MLP gating module \(\psi\) producing weights \((\alpha_i^{\text{geo}}, \alpha_i^{\text{sem}})\) to yield unified node embeddings \(H\). To amplify structural margin between true parents and spatial distractors, Scroll-Net optimizes an auxiliary contrastive alignment loss: $$ \mathcal{L}{\text{contrast}} = -\frac{1}{|S(h_i, h_{pa^}|} \sum_{i \in S_{nr}} \log \frac{\exp(\text{sim(b_i)}) / \tau_c)}{\exp(\text{sim}(h_i, h_{pa^(b_i)}) / \tau_c) + \sum_{k \in \mathcal{N}_i^-} \exp(\text{sim}(h_i, h_k) / \tau_c)} $$ Mining hard negatives \(\mathcal{N}_i^-\) dynamically from high-scoring candidate logits penalizes spurious semantic matches and sharpens hierarchy boundaries.

3. Hard Reading-Order Causal Prefix Constraint and Decoupled Root Modeling: Eliminating cyclic graph topologies and mitigating root dominance

Benchmark annotations conform to depth-first pre-order tree traversal, imposing the sequential temporal constraint that a logical parent must precede its children in reading order: \(\pi^{-1}(pa(v)) < \pi^{-1}(v)\). Scroll-Net exploits this structural regularity during autoregressive pointer decoding. At decoding step \(t\) for block \(i = \pi(t)\), the candidate parent pool is strictly constrained to the causal prefix \(\mathcal{A}_t = \{0\} \cup \{\pi(1), \dots, \pi(t-1)\}\), where 0 denotes the virtual root node. An additive hard causal mask is enforced on raw attention logits: $$ m_t[j] = \begin{cases} 0, & j \in \mathcal{A}_t \ -\infty, & \text{otherwise} \end{cases} $$ Because all non-root pointers are restricted to earlier positions in the imposed sequence, self-loops, forward connections, and directed cycles are structurally prohibited. Furthermore, to prevent the virtual root from being overwhelmed by the \(N\) competing non-root candidates, Scroll-Net decouples root classification from parent pointer selection: a dedicated classifier is trained with class-balanced binary cross-entropy, and its calibrated logit is injected additively into the root column \(\ell_t[0]\) at inference.

4. Top-K Scroll-Space Geometric Candidate Pruning: Reducing sequential decoding complexity from quadratic to linear

While the causal prefix mask ensures topological validity, the prefix \(\mathcal{A}_t\) expands linearly with sequence length, preserving an overall \(O(N^2)\) parent decoding complexity. Scroll-Net solves this scalability bottleneck by precomputing a localized candidate set \(\mathcal{C}_i\) for each node using a parallel two-layer MLP edge scorer operating on pairwise scroll features \(f_{ij}\). During sequential decoding, the active attention set is narrowed to: $$ \mathcal{A}_t^K = \mathcal{A}_t \cap ({0} \cup \mathcal{C}_i) $$ Because \(|\mathcal{C}_i| = K\) with \(K \ll N\) (empirically \(K=64\)), the effective candidate size satisfies \(|\mathcal{A}_t^K| \le K + 1\). This shrinks the autoregressive decoding complexity from \(O(N^2)\) to \(O(NK)\). Crucially, the auxiliary candidate scorer runs in parallel across all pairs prior to decoding, reducing overall end-to-end inference latency by 36.5% and peak memory by 46.5% without degrading structural accuracy.

Loss & Training

Scroll-Net is trained end-to-end using a composite multi-task objective: $$ \mathcal{L} = \mathcal{L}{\text{root}} + \lambda}} \mathcal{L{\text{parent}} + \lambda}} \mathcal{L{\text{edge}} + \lambda}} \mathcal{L{\text{path}} + \lambda}} \mathcal{L{\text{RO}} + \lambda $$ Here, }} \mathcal{L}_{\text{contrast}\(\mathcal{L}_{\text{root}}\) is a dynamically weighted binary cross-entropy over calibrated root logits \(\tilde{\rho}_t\); \(\mathcal{L}_{\text{parent}}\) is cross-entropy computed strictly over non-root candidates; \(\mathcal{L}_{\text{edge}}\) supervises the precomputation edge classifier; \(\mathcal{L}_{\text{path}} = \frac{1}{|\mathcal{V}|} \sum_{(t, j) \in \mathcal{V}} \max(0, \ell_t[j])\) penalizes unmasked logit violations for future positions; \(\mathcal{L}_{\text{RO}}\) supervises the Sinkhorn doubly-stochastic permutation matrix with cross-entropy; and \(\mathcal{L}_{\text{contrast}}\) provides representation alignment. Loss weights are balanced at \(\lambda_{\text{parent}} = 1.2\), \(\lambda_{\text{edge}} = 0.3\), \(\lambda_{\text{path}} = 1.2\), \(\lambda_{\text{RO}} = 1.0\), and \(\lambda_{\text{contrast}} = 0.5\). Models are optimized using AdamW with learning rate \(2 \times 10^{-4}\) and cosine decay over 40 epochs on two NVIDIA GeForce RTX 3090 GPUs.

Key Experimental Results

Main Results

Scroll-Net was evaluated on four standardized benchmarks: HRDoc-Simple, HRDoc-Hard, E-Periodica, and DocHieNet, alongside Comp-HRDoc for comprehensive cross-page evaluation. Metrics comprise child\(\to\)parent directed Link F1 and Tree-Edit-Distance Similarity (TEDS).

Method HRDoc-Simple Link F1 / TEDS HRDoc-Hard Link F1 / TEDS E-Periodica Link F1 / TEDS DocHieNet Link F1 / TEDS
DocParser (Rausch et al., 2019) 56.8 / 28.7 47.4 / 22.4 35.2 / 18.7 23.3 / 6.8
DSG (Rausch et al., 2023) 84.8 / 83.2 74.0 / 64.3 67.2 / 60.1 53.5 / 33.9
DOC (Wang et al., 2024b) โ€“ / 95.1 โ€“ / 85.5 โ€“ / โ€“ โ€“ / โ€“
DHFormer (Xing et al., 2024) 99.3 / 98.7 93.4 / 89.1 92.5 / 84.9 77.8 / 57.6
Scroll-Net-B (Ours) 95.3 / 91.2 90.5 / 87.4 87.9 / 83.5 78.3 / 61.6
Scroll-Net-L (Ours) 98.2 / 96.5 94.2 / 89.8 91.5 / 87.4 80.1 / 62.4

On the structurally complex Comp-HRDoc benchmark evaluated under UniHDSA's STEDS protocol, Scroll-Net-L established a new state-of-the-art: DOC-R18 scored 83.7 / 83.7 (Micro / Macro); UniHDSA-R18 reached 88.0 / 87.8; UniHDSA-R50 obtained 88.9 / 88.6; Scroll-Net-B achieved 87.5 / 87.3; while Scroll-Net-L achieved 89.4 / 89.1, outperforming all prior multi-stage and unified frameworks.

Ablation Study

The authors conducted cumulative component additions, leave-one-out isolations, and efficiency analyses on Comp-HRDoc under oracle and predicted reading orders.

Component Configuration (Comp-HRDoc, Oracle RO) Link F1 โ†‘ CPE-F1 (Cross-Page) โ†‘ TEDS โ†‘ Description
Single-page baseline 56.8 โ€” 43.2 Restricted to intra-page predictions; zero cross-page links
+ Scroll-space frame 82.4 78.6 76.5 Restores cross-page comparability (+25.6 Link F1 gain)
+ Geometric bias 86.9 84.3 82.8 Explicit relative spatial offsets and scale ratios
+ Sequential consistency 89.7 87.5 86.4 Hard causal prefix mask guarantees acyclicity
+ Contrastive alignment 90.5 88.4 87.4 InfoNCE alignment separates confusable candidate pairs

Leave-one-out ablations (Table 5) confirm that removing scroll-space mapping causes the single largest performance drop (\(-7.7\) Link F1 to 82.8). Disabling sequential consistency results in a \(-3.6\) drop (to 86.9), removing geometric bias causes a \(-3.1\) drop (to 87.4), removing the dual-stream encoder drops Link F1 by \(-2.7\) (to 87.8), and removing contrastive alignment leads to a \(-1.4\) drop (to 89.1).

Efficiency benchmarks (Table 4 & 9) show that unpruned decoding averages 167.5 candidates per step, incurring 6,324 MB peak memory and 3,884 ms latency. Enforcing geometric pruning with \(K=64\) narrows candidate count to 69.8, reduces peak memory to 3,384 MB (\(-46.5\%\)), and reduces latency to 2,466 ms (\(-36.5\%\)), while achieving identical Link F1 (87.4) and CPE-F1 (83.9). Geometric candidate recall@64 reaches 95.6% (and 98.9% at \(K=256\)).

Key Findings

  • Scroll-space frame is the dominant enabler of cross-page hierarchy recovery: The single-page model predicts zero cross-page edges. A simple page-embedding baseline achieves 81.5 CPE-F1, whereas Scroll-Net's unified coordinate projection achieves 88.4 CPE-F1, bridging cross-page disconnects.
  • Hard causal masking decisively outperforms soft and unconstrained decoding: Under predicted reading order, soft masking yields only 62.0 Link F1 / 55.3 CPE-F1, and unmasked decoding reaches 84.2 / 80.8, whereas hard masking attains 87.4 / 83.9. Eliminating cyclic structural errors far outweighs the minor risk of excluding a true parent due to reading order noise (observed true-parent exclusion rate is only 1.43%).
  • High resilience against page-height variations: Under synthetic random page-height perturbations of up to \(\pm 30\%\) along the vertical axis, Scroll-Net retains a Link F1 of 85.1, still surpassing the unperturbed no-mask baseline (84.2), indicating robust tolerance to non-uniform aspect ratios.

Highlights & Insights

  • Continuous vertical scroll mapping for discrete multi-page layouts: Modeling paginated documents as an uninterrupted continuous strip elegantly unifies intra-page and inter-page geometry, providing a differentiable spatial coordinate frame for global relation modeling.
  • Translating tree traversal conventions into decoding causal masks: Converting the DFS pre-order annotation assumption into an autoregressive causal prefix constraint mathematically guarantees acyclic tree generation, replacing cumbersome post-hoc cycle-removal heuristics.
  • Geometry-first cross-attention inductive bias: Maintaining independent geometric and semantic streams until late cross-attention prevents spatial locality from being conflated with textual affinity in dense multi-column layouts.

Limitations & Future Work

  • Reliance on standardized vertical pre-order layouts: The model's core assumptions of pre-order tree traversal and monotonic vertical page concatenation are tailored for academic and formal document layouts. Performance may degrade on non-linear layouts, multi-directional broadsheets, foldouts, or documents with non-standard reading paths.
  • Sensitivity to upstream layout extraction quality: As a hierarchy parsing framework, Scroll-Net assumes pre-extracted block bounding boxes and text tokens; segmentation errors or missed elements from upstream OCR engines directly propagate through the causal decoding chain.
  • Future directions: Extending scroll space to multi-directional continuous manifolds for complex foldout media, and integrating end-to-end visual tokenization with constrained tree decoding to eliminate upstream cascading errors.
  • vs DSG (Rausch et al., 2023): DSG parses individual pages independently and relies on grammar-based post-hoc stitching; Scroll-Net natively models global cross-page interactions via scroll space and autoregressive pointers, improving DocHieNet TEDS from 33.9 to 62.4.
  • vs UniHDSA (Wang et al., 2025): UniHDSA introduces document-level grouping but retains page-centric coordinates during per-page feature encoding; Scroll-Net establishes globally comparable coordinates from the input level, outperforming UniHDSA-R50 on Comp-HRDoc (89.4 vs 88.9 Micro-STEDS).
  • vs DOC (Wang et al., 2024b): DOC relies on dense pairwise scoring with \(O(N^2)\) complexity and soft constraints that permit structural cycles; Scroll-Net enforces hard causal prefix constraints and Top-K pruning, guaranteeing acyclic graphs while reducing decoding complexity to \(O(NK)\).

Rating

  • Novelty: โญโญโญโญโญ Elegant integration of continuous scroll-space geometry with reading-order causal constraints for acyclic tree parsing.
  • Experimental Thoroughness: โญโญโญโญโญ Rigorous evaluation across four diverse benchmarks, comprehensive cumulative and leave-one-out ablations, perturbation tests, and latency profiling.
  • Writing Quality: โญโญโญโญโญ Exceptionally clear narrative, rigorous formal task formulation, and well-motivated design principles.
  • Value: โญโญโญโญโญ Solves the fundamental quadratic scaling and topological invalidity bottlenecks of multi-page document parsing, providing high-value infrastructure for long-document understanding agents.