In traditional information extraction, models typically operate at the sentence level. If a sentence mentions "Einstein" and "Germany," a model only needs to check a handful of words to identify a "born in" relationship. However, as research shifts toward Document-Level Relation Extraction (DocRE), the complexity of this task does not grow linearly with the length of the text—it explodes quadratically.
When moving from a single sentence to a full document, the number of potential entities increases significantly. Because a relationship can exist between any two entities regardless of their distance, a model must evaluate every possible pair. If a document contains $N$ entities, there are $N(N-1)$ potential relations to check. This "combinatorial explosion" creates a massive search space that challenges both computational efficiency and human annotation.
The Scalability Bottleneck
The primary hurdle in DocRE is that the search space for relations grows quadratically with the number of identified units. Steffen Eger, Johannes Daxenberger, and Iryna Gurevych noted this in the context of argumentation mining, where linking discrete reasoning components becomes computationally expensive as document length increases.
This scaling behavior manifests in three distinct ways:
- Annotation Scarcity: It is nearly impossible for human annotators to exhaustively label every valid relationship in a dense document. Xinxin Liu and Ye Wang argue that this leads to "incomplete labeling," where many true relations are left unmarked, confusing standard supervised models.
- Inference Latency: High-parameter models, such as Large Language Models (LLMs), struggle with the sheer volume of pairs. Kehai Chen and colleagues point out that evaluating every possible entity pair with an LLM is prohibitively expensive due to the quadratic growth of the candidate set.
- Signal-to-Noise Ratio: As the number of pairs grows, the vast majority of them will have no relationship (the "NA" class). This imbalance can "distract" models, leading them to miss actual connections amidst the sea of irrelevant pairs.
Pruning the Search Space
To handle this complexity, researchers have moved away from exhaustive pairwise classification toward "filter-then-analyze" architectures.
The LMRC framework by Kehai Chen uses a lightweight neural classifier to act as a gatekeeper, filtering out irrelevant entity pairs before passing only the most promising candidates to a fine-tuned LLM. Similarly, Hao Fang and the creators of GLiM use a graph-enhanced Transformer to narrow down the search space before deploying an LLM to recover missing relations, specifically to address the low recall common in biomedical documents.
Beyond Isolated Pairs
Another strategy involves changing how the model "sees" the relationships. Instead of treating every pair as an independent binary choice, newer methods attempt to model the global context of the document.
- Relational Interdependency: Zheng Zhang and Zhijing Jin introduced the Relation of Relations (RoR) paradigm, which uses Graph Neural Networks to model how one relationship in a document might imply or support another.
- Entity-Pair Graphs: The GREP framework by Fu Zhang 0001 treats the entity pairs themselves as nodes in a reasoning graph. By predicting all possible relations at once through an auxiliary task, the model filters noise more effectively than models that look at pairs in isolation.
- Structural Reformulation: Some researchers bypass the pairwise problem by reframing the task entirely. Yue Zhang reframed entity linking in visually rich documents as a dependency parsing task, using biaffine parsers to efficiently navigate the two-dimensional search space of a document page.
Learning from Incomplete Data
Because the quadratic search space makes perfect datasets impossible, a significant branch of this research focuses on Positive-Unlabeled (PU) learning. Since we cannot be sure if an unlabeled pair is truly "negative" or just "unannotated," frameworks like SSR-PU by Xinxin Liu and P³M by Ye Wang treat the task as learning from a small set of confirmed positives and a large pool of unlabeled data. This shift in framing allows models to remain robust even when human annotators fail to keep up with the $O(N^2)$ complexity of the text.