Efficient Extraction of Long and Nested Text Spans

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 258 papers61 conceptsfrozen 2026-10-04

In traditional Natural Language Processing, we often treat sentences as sequences of individual tokens. To identify a person's name or a medical condition, we label each word (e.g., using BIO tagging). However, this approach struggles with "nested" entities—like identifying "France" inside the phrase "The Embassy of France."

To solve this, researchers shifted toward span-based models. Instead of labeling words, these models treat every possible sub-sequence (span) in a sentence as a candidate entity. While conceptually elegant, this approach introduces a massive computational hurdle: a sentence of length $n$ has $O(n^2)$ possible spans. To keep models fast, the field has historically relied on a "length cap"—a maximum span width (often 10 tokens).

Recent research has focused on breaking this length cap, allowing models to identify the long, complex, and nested entities found in legal, medical, and technical domains without exploding in complexity.

The Computational Trap of Exhaustive Enumeration

The intuition behind span-based models, such as the work on MGNER by Congying Xia and colleagues, is that a span has a holistic meaning that individual words do not. By representing a span as a single vector, we can better capture the "phraseness" of a mention.

However, as noted across dozens of papers—from Kea in 1999 to DirectRel in 2022—imposing a fixed maximum window size is the standard way to manage this $O(n^2)$ search space. If a model only looks at spans up to 10 words long, it is fundamentally "blind" to an 11-word entity. This is not just a theoretical problem; Enwei Zhu points out in Deep Span Representations for Named Entity Recognition that this architectural constraint makes it impossible to retrieve long citations, legal titles, or complex technical descriptions.

Strategy 1: Propose and Refine

One way to break the length cap is to move from exhaustive enumeration to a two-stage process. Instead of checking every possible span, the model first "proposes" likely candidates and then "refines" them.

The PnRNet (Propose-and-Refine) architecture by Shuhui Wu and Yongliang Shen exemplifies this. By using a Transformer decoder to refine coarse entity proposals, the model can identify entities of arbitrary length. This mirrors how object detection works in computer vision: first find a "bounding box" of interest, then look closer to determine exactly what is inside. This approach effectively bypasses the need for a hard-coded length heuristic.

Strategy 2: Boundary-Based Representations

Another breakthrough involves changing how we represent a span. Traditional models might concatenate the vectors of every word in a span, which is memory-intensive.

Yuval Kirstain, Omer Levy, and Ori Ram introduced the s2e (start-to-end) model, which represents a span using only its boundaries. By using clever bilinear functions over the start and end tokens, they achieved state-of-the-art coreference resolution while using less than a third of the memory. Because the representation only depends on two points (the start and the end), the model can theoretically handle a span of any length without the computational cost increasing for longer phrases.

Strategy 3: Hierarchical and Multi-Grained Interaction

For nested entities, the challenge is understanding the relationship between a "parent" span and its "child" spans.

The HIT model by Yu Wang and colleagues uses a Head-Tail Detector to find boundaries and a Token Interaction Tagger to model the "glue" between words. Similarly, Congying Xia's MGNER treats NER as a detection task, allowing it to naturally capture "France" inside "The Embassy of France" by recognizing that both spans have high "entity-ness" scores despite their overlap.

In specialized domains like aircraft maintenance, the PANDA framework by Nobal B. Niraula leverages linguistic patterns—like the fact that English part names usually end in a "head noun"—to iteratively discover complex, multi-word entities that would be truncated by standard length caps.

Scaling to Long Documents

The final frontier for this research is moving from single sentences to entire documents. In Small Language Model Makes an Effective Long Text Extractor, Yelin Chen and Jie Tang introduce SeNER. By using a memory-efficient span-interaction module (BiSPA), they can process sequences 6x longer than previous models.

This shift suggests that the future of information extraction lies in moving away from rigid, local windows and toward flexible, global architectures that treat the entire document as a field of potential spans, regardless of how many tokens they contain.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 47 papers
  2. Version 1 · 2026-10-04 · 58 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_fixed_length_span_constraint_7d51f255,
  title = {fixed-length span constraint},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fixed-length-span-constraint/rdr_7d51f255c0ea4c259e90b957a21db01a},
  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_efficient_extraction_of_long_and_nested__7d51f255_v1,
  title = {Efficient Extraction of Long and Nested Text Spans},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/efficient-extraction-of-long-and-nested-text-spans/rdr_7d51f255c0ea4c259e90b957a21db01a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}