At the heart of many information extraction tasks lies a simple, deceptively difficult question: Are these two things the same? Whether we are identifying if two mentions in a novel refer to the same character, or if two records in a database represent the same person, we are performing Entity Resolution (ER) or Coreference Resolution.
The fundamental challenge of this field is the "Quadratic Bottleneck." If you have $N$ items, a naive system must compare every item to every other item to find matches. This results in $O(N^2)$ complexity. As Shyam Upadhyay and Dan Roth point out in Revisiting the Evaluation for Cross Document Event Coreference, this scaling behavior is "cheating" in small benchmarks but becomes a catastrophic failure in the real world. When $N$ moves from a thousand to a million, the number of comparisons jumps from a million to a trillion.
Recent research has focused on breaking this $O(N^2)$ wall, moving toward linear-time systems that can handle web-scale data.
The Memory Problem in Long Documents
In standard coreference resolution, models often try to represent every possible text span and evaluate all potential pairs. This makes processing long documents like novels computationally prohibitive.
To solve this, Shubham Toshniwal and Sam Wiseman introduced the concept of Bounded Memory Neural Networks in Learning to Ignore. The intuition is that a reader doesn't keep every entity in active memory at once. By learning an intelligent "forgetting" strategy—tracking only a fixed number of active entities—the model achieves linear runtime complexity.
Similarly, Yuval Kirstain and Ori Ram proposed the s2e (start-to-end) model in Coreference Resolution without Span Representations. By ditching explicit span representations in favor of bilinear functions over span boundaries, they reduced memory usage by two-thirds, allowing long documents to be processed in a single batch.
Scaling Across the Corpus: Blocking and Hashing
When moving from a single document to a massive corpus—Cross-Document Coreference Resolution (CDCR)—the quadratic problem intensifies. You cannot compare every mention in Document A to every mention in Document B across millions of files.
The primary mechanism to defeat this is Blocking. The goal is to partition the data so that comparisons only happen within small, likely-to-match groups. Anshumali Shrivastava and colleagues demonstrated this in Blocking Methods Applied to Casualty Records from the Syrian Conflict using Locality Sensitive Hashing (LSH).
LSH works by hashing items such that similar items "collide" into the same bucket with high probability. This transforms a global $O(N^2)$ search into a series of local, much smaller searches. In the context of deep learning, Muhammad Ebraheem and Shafiq Joty used this in DeepER, converting database rows into dense semantic vectors and using LSH to group them, eliminating the need for brittle, hand-crafted rules.
Streaming and Sequential Resolution
For real-time applications, we cannot wait for a "batch" of data to arrive. Mark Dredze and Paul McNamee pioneered a Streaming CDCR approach in Streaming Cross Document Entity Coreference Resolution. Instead of offline clustering, they used a "Doubling Algorithm" for streaming clustering.
The intuition here is incremental: as a new mention arrives, you don't compare it to every previous mention. Instead, you compare it to existing clusters or use efficient hashing to find a small set of candidates. This theme is echoed by Emily Allaway and Shuai Wang in Sequential Cross-Document Coreference Resolution, where they build cluster representations incrementally, significantly lowering complexity compared to traditional graph-based methods.
Reformulating the Search Space
Sometimes, the best way to avoid $O(N^2)$ is to change the geometry of the problem.
- Constrained Decoding: In Parallel Sentence Mining by Constrained Decoding, Pinzhen Chen and Kenneth Heafield turned a quadratic sentence search into a beam search by constraining a translation model with a prefix tree (trie) of the target corpus.
- Orthogonal Range Search: Zifan Liu and Ashish Tiwari reframed data constraint verification in Rapidash as a geometric search problem, moving from quadratic time to near-linear performance.
- Segmentation: Ali Ghodsi reimagined coreference as a computer vision-style segmentation problem in Segmentation Approach for Coreference Resolution Task, identifying entire clusters in a single pass rather than scoring pairs.
By moving away from exhaustive pairwise comparisons through hashing, memory-efficient architectures, and geometric reformulations, these researchers are enabling AI to move from processing single documents to understanding entire "data lakes" and global news streams.