When humans read a standard novel, they consume text linearly: top-to-bottom, left-to-right, line by line. Because of this, traditional Natural Language Processing (NLP) models and Transformers are built on the assumption of a one-dimensional sequence of tokens.
However, visually-rich documents (VRDs)—such as multi-column scientific papers, financial forms, invoices, and manga panels—are inherently multi-dimensional. When an Optical Character Recognition (OCR) engine or document parser extracts text from these layouts, it must flatten a 2D spatial arrangement into a 1D string. This transition introduces a fundamental challenge in document AI: how do we accurately reconstruct the logical reading order when the physical layout is non-linear?
The Serialization Gap
The core problem of flattening 2D layouts into 1D sequences is known as the serialization gap. As Hao Wang et al. demonstrate using human eye-tracking data in DocTrack: A Visually-Rich Document Dataset Really Aligned with Human Eye Movement for Machine Reading, humans scan complex documents non-linearly, jumping between columns, callout boxes, and figures based on visual hierarchy.
When standard machine reading models force this text into a rigid, linear sequence, they suffer from semantic fragmentation. For example, if a model reads across a two-column page from left to right without recognizing the column boundary, sentences from Column A and Column B become interleaved. The resulting token stream loses its logical flow, making it nearly impossible for downstream language models to correctly link entities or extract relationships.
Why Spatial Heuristics Fail
Historically, document processing pipelines relied on hard-coded geometric heuristics to determine reading order. A classic example is raster scanning or basic spatial clustering, which groups text blocks based on their physical coordinates.
In practice, raw OCR outputs are messy and fragmented, as noted by Yuta Nakashima et al. in ReLayout: Towards Real-World Document Understanding via Layout-enhanced Pre-training. In complex layouts, physical proximity does not equal semantic continuity. A sidebar or a footnote might be physically closer to a central paragraph than the next logical sentence in the main text stream.
To mitigate this, some systems employ advanced geometric sorting algorithms. For instance, Zhangxuan Gu et al. introduce an Augmented XY Cut algorithm in XYLayoutLM: Towards Layout-Aware Multimodal Networks For Visually-Rich Document Understanding to clean up messy OCR sequences before feeding them into a Transformer. Yet, as argued by Armineh Nourbakhsh et al. in AliGATr: Graph-based layout generation for form understanding, any fixed top-to-bottom or left-to-right heuristic remains a noisy approximation. These hard-coded rules lack the flexibility to adapt to the diverse reading paths found in real-world forms or multi-column reports.
Purely spatial reasoning can identify multiple geometrically plausible paths. Resolving this ambiguity requires looking at the text itself. Early work by Marco Aiello et al. in Combining Linguistic and Spatial Information for Document Analysis combined spatial constraints with shallow natural language processing, checking whether the linguistic content of two blocks "fit" together grammatically to determine the correct path.
The Circularity of Structure and Sequence
A major conceptual hurdle in this field is a catch-22 known as the reading order-structure circularity. To determine the correct reading order of a document, a model often needs to understand its hierarchical structure—for example, recognizing that a block of text is a caption or a sidebar tells the model that it should be read outside the main narrative flow. Conversely, to parse that hierarchical structure accurately, sequence-based models typically require a pre-defined, correct reading order to begin with.
Puneet Mathur et al. highlight this limitation in LayerDoc: Layer-wise Extraction of Spatial Hierarchical Structure in Visually-Rich Documents. When sequence-based models encounter highly non-linear interfaces like forms or mobile applications, they struggle because they cannot resolve this circular dependency. Breaking this loop requires moving away from flat, one-dimensional permutations entirely.
From Linear Permutations to Graphs and Trees
To handle non-linear document layouts naturally, researchers have shifted from predicting a single linear sequence to modeling documents as graphs or trees.
Reading Order as a Directed Acyclic Graph
Instead of forcing a model to find one absolute linear sequence, the authors of Modeling Layout Reading Order as Ordering Relations for Visually-rich Document Understanding (Chong Zhang et al.) reformulate reading order as a set of ordering relations represented by a Directed Acyclic Graph (DAG).
[Title]
│
▼
[Column A: Para 1] ───► [Optional Figure]
│ │
▼ ▼
[Column A: Para 2] ───► [Column B: Para 1]
A DAG allows for branching and merging paths, which perfectly matches how humans read visually-rich documents. For instance, a reader might look at a figure before or after reading the accompanying paragraph; both sequences are valid. Forcing a model to converge on a single arbitrary sequence introduces artificial noise during training, whereas a graph preserves the underlying structural relationships.
Graph Convolutional Networks for Re-organization
Other approaches use Graph Convolutional Networks (GCNs) combined with Pointer Networks to dynamically re-organize scattered text blocks. As shown by Liangcheng Li et al. in An End-to-End OCR Text Re-organization Sequence Learning for Rich-Text Detail Image Comprehension, treating OCR text boxes as nodes in a graph allows the model to leverage both local spatial coordinates and semantic features to learn the correct logical sequence, bypassing rigid sorting heuristics.
Hierarchical Tree Parsing
Rather than outputting an ordered list, models can parse documents directly into nested trees. In PDF-to-Tree: Parsing PDF Text Blocks into a Tree, Yue Zhang 0073 et al. introduce a transition-based parser that organizes disorganized text blocks into a hierarchical tree of sections, subsections, and paragraphs. By explicitly nesting non-linear elements like sidebars or footnotes into their own subtrees, the main narrative flow remains uninterrupted, preventing context fragmentation.
Layout-Aware Pre-training
To make deep learning models natively aware of non-linear flows, modern architectures incorporate reading order directly into their pre-training objectives.
Instead of treating layout as a passive feature, Hao Tian et al. introduce an explicit "Reading Order Prediction" task in ERNIE-Layout: Layout Knowledge Enhanced Pre-training for Visually-rich Document Understanding. During pre-training, the model is given a collection of text segments with shuffled coordinates and must learn to predict the next logical segment. This forces the network to treat layout as a primary modality alongside text and vision.
A similar evolution has occurred in scene text spotting (reading text on billboards, packaging, or product labels), where text can be curved, rotated, or multi-line. Traditional sequential models fail when text does not follow a linear left-to-right path. To overcome this, Junyeop Lee et al. developed the SATRN architecture in On Recognizing Texts of Arbitrary Shapes with 2D Self-Attention, utilizing 2D self-attention mechanisms that allow the model to jump between arbitrary points in 2D space to track character sequences dynamically.
Furthermore, to handle dense or complex text arrangements without getting trapped by strict sequence-length limitations, Taeho Kil et al. employ "starting-point prompting" in Towards Unified Scene Text Spotting Based on Sequence Generation. By predicting the exact starting position of a text sequence, auto-regressive models can naturally determine the correct reading order for complex layouts without relying on a fixed raster scan.
Key Foundational Work
Combining Linguistic and Spatial Information for Document Analysis (2000) — contributed 1 concept elements to this direction.
Data GroundTruth, Complexity, and Evaluation Measures for Color Document Analysis (2002) — contributed 1 concept elements to this direction.