When we read a story, we instinctively map events onto a mental timeline. We know that a "fire" must happen before an "investigation," which in turn precedes a "report." For a machine to achieve this level of understanding, it must perform Temporal Relation Extraction (TRE).
However, the traditional way we teach machines to do this—by comparing pairs of events—hits a mathematical wall as soon as the story gets long. Recent research has shifted away from exhaustive pairwise comparisons toward more scalable structures like dependency graphs and absolute timelines.
The Quadratic Bottleneck
The fundamental challenge in temporal reasoning is complexity. If a document has $n$ events, the number of potential relationships between them is $n(n-1)/2$. This is a quadratic ($O(n^2)$) growth curve.
As Taylor Cassidy, Nathanael Chambers, and colleagues noted in An Annotation Framework for Dense Event Ordering, manually identifying every possible relation is often impractical. If a news article has 50 events, an annotator would need to check 1,225 pairs. By 100 events, that number jumps to nearly 5,000.
This complexity creates a "sparsity" problem. Because humans cannot feasibly label every pair, they only label the most obvious ones. Inderjeet Mani and James Pustejovsky pointed out early on in Machine Learning of Temporal Relations that this leads to datasets where many implicit links are missing, leaving machine learning models with a "noisy" and incomplete ground truth.
From Webs to Graphs
To break the quadratic bottleneck, researchers have reimagined temporal relations as a Temporal Dependency Graph (TDG). Instead of a dense web where every event connects to every other event, a TDG treats time like a tree or a directed acyclic graph. Each event is linked to a "parent" event or a time expression that governs it.
This shift changes the task from $O(n^2)$ to something much closer to linear ($O(n)$). Jiarui Yao and Nianwen Xue demonstrated in Annotating Temporal Dependency Graphs via Crowdsourcing that this structure allows non-expert crowdsourcers to produce high-quality, dense data for entire articles.
On the modeling side, Puneet Mathur and Vlad I. Morariu introduced DocTime, a parser that uses a "Time-Transformer" to reconstruct these paths. By focusing on the graph structure rather than isolated pairs, the model can better capture the chronological flow of long-form text.
Enforcing Global Consistency
Even with better structures, models often make "impossible" predictions—for example, deciding that Event A is before B, B is before C, but C is before A.
To solve this, Qiang Ning and Dan Roth proposed a structured learning approach in A Structured Learning Approach to Temporal Relation Extraction. Instead of treating each pair as an independent coin flip, they use global transitivity constraints. If the model knows A < B and B < C, the system is mathematically forced to conclude A < C. This logic helps "fill in" the missing labels in sparse datasets, effectively turning a weakness (missing data) into a source of supervision.
Absolute Anchoring
A third path to scalability is to stop comparing events to each other and start comparing them to the calendar.
In Temporal Anchoring of Events for the TimeBank Corpus, Nils Reimers and Iryna Gurevych argued that anchoring events to absolute dates reduces annotation effort by 85%. If you know Event A happened on "Oct 12" and Event B happened on "Oct 13," their relative order is automatically resolved without ever needing a pairwise comparison.
Similarly, Anna Rogers and Anna Rumshisky developed NarrativeTime, which uses a timeline-based interface. By placing events on a visual line, annotators implicitly define the relationship between every single pair of events in a single pass, achieving "full density" at high speed.
Why It Works
The transition from pairwise labeling to structured anchoring works because it aligns the computational task with the underlying nature of time. Time is a single dimension. By forcing models to respect the geometry of a line (through graphs, transitivity, or timestamps), we prevent them from getting lost in the quadratic explosion of a multi-event story. This shift has enabled the creation of massive benchmarks like MAVEN-ERE, which provides the scale necessary for modern neural architectures to finally master the "when" of natural language.