The Quadratic Complexity of Span Based Text Processing

556 concepts453 papers5 proposals

In natural language processing, traditional sequence labeling models operate at the token level. For flat Named Entity Recognition (NER), assigning a tag (like B-PER or I-PER) to each individual word works remarkably well. However, language is rarely perfectly flat. Entities are frequently nested inside one another (e.g., [Bank of [America]]), and coreference resolution requires linking arbitrary text segments across entire documents.

To handle these complex structures, modern architectures often shift from token-level tagging to span-based representations. Instead of evaluating words in isolation, these models treat multi-token text segments as the fundamental units of analysis.

While span-based models offer immense representational power, they introduce a severe computational challenge: a combinatorial explosion in the number of candidate text segments.

The Combinatorial Explosion of Span Enumeration

To understand why span-based models struggle to scale, we must look at how the search space grows with text length. If a sentence contains $N$ tokens, the number of possible contiguous text spans is given by the formula:

$$\frac{N(N + 1)}{2}$$

This means the number of candidate spans scales quadratically, or $\mathcal{O}(N^2)$, relative to the sequence length.

For tasks that require classifying individual spans—such as nested NER or extractive question answering—this quadratic growth quickly becomes expensive. As noted by Sohrab et al., evaluating every possible sub-span directly introduces significant computational overhead compared to linear sequence tagging. Huang et al. observe that this overhead severely limits a model's ability to process long-form documents or capture extended phrases.

Token Sequence:   [ The ]   [ Quick ]   [ Brown ]   [ Fox ]
Length (N=4)

Possible Spans:
1-token:          [The], [Quick], [Brown], [Fox]             (4)
2-token:          [The Quick], [Quick Brown], [Brown Fox]    (3)
3-token:          [The Quick Brown], [Quick Brown Fox]       (2)
4-token:          [The Quick Brown Fox]                      (1)
Total Spans = 10  (Reflects N(N+1)/2)

When models must evaluate every single one of these regions, the computational throughput drops. For instance, Raiman et al. point out that extractive question-answering models encounter severe scalability issues because scoring every possible start-and-end combination creates an expansive search space that hinders real-time throughput.

The Pairwise Bottleneck

The computational bottleneck worsens dramatically when a task requires modeling relationships between different text segments. Consider coreference resolution (determining if two mentions refer to the same entity) or relation extraction (identifying how two entities interact).

If a model must evaluate every possible pair of spans, the complexity compounds from quadratic to quartic:

$$\mathcal{O}\left(\left(N^2\right)^2\right) = \mathcal{O}(N^4)$$

In their landmark end-to-end coreference resolution framework, Lee et al. demonstrated that exhaustively evaluating all potential link pairs creates a massive computational bottleneck that scales poorly to long-form content. Even when a task simplifies the problem by only evaluating relationships between individual tokens rather than full spans, the interaction matrix still scales at $\mathcal{O}(N^2)$, as highlighted by Bekoulis et al..

Xu et al. formalize this challenge within unified span-relation frameworks, noting that a naive implementation faces an $\mathcal{O}(N^4)$ complexity due to the combinatorial explosion of span pairs. This scaling behavior makes processing extensive texts—such as legal contracts, medical records, or multi-page documents—prohibitively expensive on standard hardware, a limitation echoed by Deleu et al..

Sequence Length ($N$) Number of Spans ($\approx \frac{N^2}{2}$) Pairwise Interactions ($\approx \frac{N^4}{4}$)
10 tokens (Short phrase) $\approx 50$ $\approx 2,500$
100 tokens (Paragraph) $\approx 5,000$ $\approx 25,000,000$
1,000 tokens (Document) $\approx 500,000$ $\approx 250,000,000,000$

Algorithmic Solutions to the Bottleneck

To make span-based models practical, researchers have developed several distinct strategies to prune, anchor, or entirely bypass the quadratic search space.

1. Heuristic Pruning and Filtering

The most direct way to handle the bottleneck is to filter out unlikely spans before performing expensive pairwise operations. In their coreference architecture, Lee et al. and Zhang et al. utilize unary mention scores to keep only a small fraction of top-scoring candidate spans. While effective, this approach still requires computing initial representations for all spans, meaning the underlying quadratic cost is mitigated during later stages but not entirely eliminated during initial span generation.

2. Boundary-Driven Filtering

Instead of enumerating spans blindly, models can leverage structural cues by identifying entity boundaries (start and end tokens) first. Zheng et al. and Tan et al. propose boundary-aware networks that locate potential entity edges to prune the search space before classification. Similarly, the authors of Locate and Label adapt object-detection concepts from computer vision, proposing candidate text regions and refining their boundaries before running downstream classifiers.

Exhaustive Search (O(N²)):
[The] [The Quick] [The Quick Brown] [Quick] [Quick Brown] ... (All combinations)

Boundary-Driven Search:
Step 1: Identify high-probability boundaries -> Start: "Quick", End: "Brown"
Step 2: Classify only the bounded candidate -> [Quick Brown]

3. Anchor-Based and Head-Word Tracking

Another strategy anchors spans to specific central words rather than enumerating every boundary combination. Lin et al. introduce Anchor-Region Networks, which identify syntactic head words and dynamically expand boundaries around them, shifting the paradigm from exhaustive searching to a "sequence-to-nuggets" approach. For cross-sentence event argument detection, Zhang et al. similarly use a two-step framework that identifies a head-word first, preventing a cross-sentence search space explosion.

4. Generative Formulations

A more radical departure abandons explicit span extraction altogether, reframing the task as a sequence generation problem. Du demonstrates that document-level event entities can be extracted using a generative encoder-decoder architecture with a pointer mechanism. By generating the target entities sequentially, the model bypasses the need to construct or score an intermediate span matrix, avoiding the quadratic bottleneck entirely.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_quadratic_comparison_complexity_1ff84957,
  title = {quadratic comparison complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quadratic-comparison-complexity/rdr_1ff84957718b45b69ddab4175c218167},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_quadratic_comparison_complexity_1ff84957_v1,
  title = {quadratic comparison complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quadratic-comparison-complexity/rdr_1ff84957718b45b69ddab4175c218167/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake