Linear Time Coreference Resolution via Bounded Entity Memory

This direction is merged into another direction: quadratic comparison complexity. Its last version stays readable and citable here.

Version 1 of 120 papers31 conceptsfrozen 2026-10-04

Traditional coreference resolution (CR) models suffer from a fundamental scaling problem: they are typically designed to compare every new mention of an entity against every previous mention in a document. This exhaustive pairwise comparison results in a computational complexity of at least $O(n^2)$, where $n$ is the number of mentions. As Matt Grenander, Shay B Cohen, and Mark Steedman point out in Sentence-Incremental Neural Coreference Resolution, some architectures even reach $O(n^4)$, making the processing of long-form text like novels or continuous data streams computationally prohibitive.

To solve this, a new research direction treats coreference not as a global clustering problem, but as an incremental entity tracking task. By maintaining a fixed-size memory of active entities, these models achieve linear complexity ($O(n)$), enabling coreference resolution at "book scale."

From Mention Pairs to Entity Slots

The core intuition behind this shift is that a reader does not need to remember every previous mention to understand who "he" refers to in a current sentence. Instead, the reader maintains a mental model of the entities currently active in the narrative.

In Learning to Ignore: Long Document Coreference with Bounded Memory Neural Networks, Shubham Toshniwal and colleagues formalize this using a bounded memory architecture. Instead of comparing a new mention to all previous mentions, the model compares it to a small, fixed number of "memory cells" or "slots," each representing a specific entity cluster.

When a new mention appears, the model has three choices:

  1. Link the mention to an existing entity slot.
  2. Start a new entity by occupying an empty slot.
  3. Overwrite (forget) an existing entity slot to make room for the new one.

This mechanism transforms the task into a streaming process. Because the number of slots is constant, the time required to process each mention remains constant, regardless of how long the document becomes.

Why Bounded Memory Works

It might seem counterintuitive that a model can resolve references in a 200,000-word book using only a few dozen memory slots. However, Shubham Toshniwal demonstrates in Efficient and Interpretable Neural Models for Entity Tracking that most entities in a narrative are transient.

In any given scene or paragraph, only a handful of characters or objects are "top-of-mind." By implementing an intelligent eviction policy—essentially learning which entities are unlikely to be mentioned again—the model can maintain high accuracy. Toshniwal found that even in complex literary texts, maintaining as few as 20 active entity representations is often sufficient to match the performance of unbounded models.

Architectural Innovations for Long Context

To further refine this, Qipeng Guo and Yue Zhang introduced a Dual Cache system. This architecture uses a fixed-size memory buffer to replace exhaustive comparisons, specifically designed to handle the unique challenges of long-document neural CR.

Similarly, Robert L. Logan and Andrew McCallum applied these principles to Streaming Cross-Document Entity Coreference. They showed that by storing only a small fraction (roughly 10%) of observed mentions in an incremental clustering framework, systems can scale to massive, continuous datasets with negligible loss in accuracy.

Benchmarking at Book Scale

The ultimate test for these incremental models is the "book scale" challenge. Giuliano Martinelli 0001 and Roberto Navigli introduced BOOKCOREF, a benchmark featuring documents averaging over 200,000 tokens. Their work confirms that while standard models struggle or fail under these constraints, incremental architectures trained on large-scale "silver" data can achieve significant performance gains, proving that linear-time entity tracking is the most viable path forward for processing human-scale narratives.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_linear_time_coreference_resolution_via_b_5ac3dff7,
  title = {Linear Time Coreference Resolution via Bounded Entity Memory},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-time-coreference-resolution-via-bounded-entity-memory/rdr_5ac3dff7015d4777a04aefe63882bbc7},
  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_linear_time_coreference_resolution_via_b_5ac3dff7_v1,
  title = {Linear Time Coreference Resolution via Bounded Entity Memory},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-time-coreference-resolution-via-bounded-entity-memory/rdr_5ac3dff7015d4777a04aefe63882bbc7/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}