Linear Time Relation Extraction via Single Pass Encoding

28 concepts21 papers1 proposal

Extracting structured relationships from unstructured text is a foundational challenge in natural language processing. Traditionally, systems have approached this by first identifying all entity spans and then evaluating every possible pair or combination to determine if a relationship exists.

While intuitive, this Cartesian product approach suffers from a severe computational bottleneck: its time complexity scales quadratically ($O(n^2)$) with the number of entities, and can scale cubically ($O(n^3)$) or exponentially when extracting complex $N$-ary relations. For long documents, multi-party dialogues, or web-scale corpora, this combinatorial explosion makes real-time inference impossible.

To overcome this, a major research direction has emerged focused on single-pass (or one-pass) relation extraction. The core intuition is to collapse the extraction process into a single forward pass over the text, sharing contextual representations across all potential entities and reducing computational complexity from quadratic to linear ($O(n)$).

Traditional (Quadratic):
[Entity A] <--> [Entity B]  (Pass 1)
[Entity A] <--> [Entity C]  (Pass 2)
[Entity B] <--> [Entity C]  (Pass 3)

Single-Pass (Linear):
[Input Text] ---> [Single Forward Pass] ---> All Relations Identified Simultaneously

Researchers achieve this linear-time efficiency through four primary mechanisms: token-level sequence tagging, bounded memory tracking, generative query architectures, and entity-aware attention mechanisms.

Token-Level Tagging and Distance Encoding

One way to bypass the need to evaluate pairs explicitly is to reframe relation extraction as a sequence labeling task. Instead of isolating spans and matching them, the model assigns labels to individual tokens that implicitly encode the relationship and the distance to the target entity.

For example, in Emotion-Cause Pair Extraction (ECPE), traditional models evaluate every combination of emotion clauses and cause clauses. To avoid this, Chaofa Yuan et al. introduced a tagging scheme that embeds the relative distance between a cause and its triggered emotion directly into the token labels (Emotion-Cause Pair Extraction as Sequence Labeling Based on A Novel Tagging Scheme). By predicting these unified tags in a single pass, the model eliminates the Cartesian product bottleneck entirely.

A similar transition from span enumeration to token labeling can be seen in prompt-based Named Entity Recognition (NER). Rather than evaluating every possible text span against a set of templates, Ruotian Ma et al. developed EntLM, which reformulates NER as a direct word-prediction task at the entity's exact position (Template-free Prompt Tuning for Few-shot NER). This shift to token-level labeling yields inference speeds up to 1,930 times faster than traditional template methods.

Even in unsupervised settings, the power of single-pass statistical logic holds. Haodi Feng et al. demonstrated that by calculating Accessor Variety (AV)—a metric measuring the diversity of characters adjacent to a string—systems can extract complex linguistic units in a single pass over a corpus, outperforming computationally expensive iterative training methods (Accessor Variety Criteria for Chinese Word Extraction).

Bounding the Search Space with Memory Buffers

When dealing with long-form text, such as scripts or extended dialogues, entities are often separated by hundreds of words. Evaluating all pairs across these distances is prohibitive. To maintain linear time complexity, models can use a fixed memory buffer or state machine to track active entities dynamically.

In clinical conversations, where symptoms and medications are continuously mentioned and modified, Nan Du et al. developed R-SAT (Relational Span-Attribute Tagging) (Learning to Infer Entities, Properties and their Relations from Clinical Conversations). Instead of comparing every new word to every previous word, R-SAT stores candidate entities in a dedicated memory buffer, updating their attributes as the conversation progresses and keeping the extraction complexity strictly linear.

[Dialogue Stream] ---> [Identify Entity] ---> Store in Memory Slot [1, 2, ... N]
                                                      |
                                           Update Attributes Linearly

This slot-based tracking is also highly effective for narrative analysis. The PeTra architecture, introduced by Shubham Toshniwal et al., tracks people in stories by maintaining a one-to-one mapping between characters and specific memory slots (PeTra: A Sparsely Supervised Memory Model for People Tracking). This bounds the computational complexity to $O(TN)$, where $T$ is the document length and $N$ is the small, fixed number of memory slots, making it feasible to process entire books.

Alternatively, the state space can be managed via parsing actions. Chuang Fan et al. designed a transition-based parsing framework that constructs an emotion-cause directed graph step-by-step (Transition-based Directed Graph Construction for Emotion-Cause Pair Extraction). By processing the text sequentially and using transition operators to form edges, the model builds complex relational graphs in a single linear sweep.

Query-Based Retrieval and Generative Templates

With the advent of sequence-to-sequence architectures and Large Language Models (LLMs), relation extraction can be reframed as a generative or question-answering (QA) task. Instead of performing exhaustive classification, the model treats an entity as an "anchor" query and retrieves all related entities simultaneously.

In the LLMERE framework developed by Zhilei Hu et al., event relation extraction is converted into a QA format (Large Language Model-Based Event Relation Extraction with Rationales). The model is prompted to identify all events related to a specific anchor event in a single pass, which reduces inference complexity to $O(n)$ and yields a six-fold increase in processing speed.

Similarly, Jun Xu et al. introduced MAQInstruct, which reframes relation extraction as a multiple-answer selection problem (MAQInstruct: Instruction-based Unified Event Relation Extraction). By querying the model to select all valid target entities from an unordered list in one go, they achieved a 30x speedup over traditional pairwise instruction-based methods.

For document-level extraction involving multi-entity relations, Kung-Hsiang Huang et al. developed TEMPGEN (Document-level Entity-based Extraction as Template Generation). This framework treats extraction as a template generation task using a BART model equipped with a TOPK COPY mechanism. By generating the filled template directly, the model bypasses the exponential cost of checking every combination of entity candidates.

Entity-Aware Attention and Packed Inputs

At the neural architecture level, single-pass extraction relies on modifying the self-attention mechanism of Transformers so that a single forward pass computes representations for all potential relations at once.

Haoyu Wang 0002 et al. pioneered this by introducing entity-aware self-attention and a structured prediction layer into BERT (Extracting Multiple-Relations in One-Pass with Pre-Trained Transformers). This allows the model to share underlying contextual representations across all potential relations within a document, increasing throughput by up to 3.5x without losing accuracy.

[Standard Attention]  ---> Focuses on generic token context
[Entity-Aware Attention] -> Integrates relative positions of multiple terms simultaneously

This strategy is particularly vital for specialized domains. In clinical informatics, Timothy Miller 0002 et al. utilized global sequence pooling within a multi-task BERT model to extract all temporal relations from a medical record simultaneously, cutting computational overhead by 25 times (A BERT-based One-Pass Multi-Task Model for Clinical Temporal Relation Extraction). In scientific literature extraction, Ming Jiang et al. demonstrated that modifying self-attention to account for the relative positions of multiple terms at once provides critical performance stability and efficiency in low-resource scenarios (Improving Scholarly Knowledge Representation: Evaluating BERT-based Models for Scientific Relation Classification).

When moving from binary relations to $N$-ary relations (e.g., connecting an event with its time, location, and multiple participants), the combinatorial explosion is even more severe. To construct $N$-ary relational knowledge graphs efficiently, Haoran Luo et al. developed Text2NKG (Text2NKG: Fine-Grained N-ary Relation Extraction for N-ary relational Knowledge Graph Construction). Their architecture integrates entity information into the input sequence using packed markers, allowing the model to process complex multi-entity relationships simultaneously and successfully dropping the time complexity from cubic ($O(n^3)$) to linear ($O(n)$).

Scaling to Document and Web Levels

The ultimate benefit of transitioning to linear-time, single-pass extraction is scalability. It transforms relational extraction from an expensive, localized operation into a lightweight process capable of handling massive datasets.

This paradigm shift was originally demonstrated at scale by TEXTRUNNER, an Open Information Extraction (OIE) system developed by Michele Banko et al. (Open Information Extraction from the Web). By identifying noun phrases and treating intervening text as candidate predicates validated in real-time by a lightweight classifier, TEXTRUNNER processed billions of web pages in a single linear pass.

Modern applications continue to leverage this scaling behavior. For instance, Rotem Dror et al. showed that moving from pairwise sentence comparisons to a single-pass document processing approach reduces the inference time required for zero-shot event schema induction by two orders of magnitude, enabling near-instantaneous generation of complex event graphs on standard hardware (Zero-Shot On-the-Fly Event Schema Induction).

Similarly, for large-scale Named Entity Linking (NEL) against millions of records, a single author, Sammy Khalife, demonstrated that a two-stage pipeline combining fast information retrieval filtering with graph-based re-ranking achieves linear computational complexity relative to the number of queries (Scalable graph-based method for individual named entity identification). This architecture allows massive entity resolution to run efficiently on standard hardware clusters without the heavy computational overhead typical of deep pairwise matching models.

By restructuring how models look at text—moving from "evaluating combinations" to "encoding holistically"—single-pass relation extraction bridges the gap between deep linguistic understanding and high-throughput production environments.

Key Foundational Work

Building A Large Thesaurus For Information Retrieval (1988) — contributed 1 concept elements to this direction.
Accessor Variety Criteria for Chinese Word Extraction (2004) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_one_pass_relation_extraction_a3101c57,
  title = {one-pass relation extraction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/one-pass-relation-extraction/rdr_a3101c57c9f342c9a7ba43cd8cf3d149},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_one_pass_relation_extraction_a3101c57_v1,
  title = {one-pass relation extraction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/one-pass-relation-extraction/rdr_a3101c57c9f342c9a7ba43cd8cf3d149/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake