# Linear-Time Modeling of Linguistic Structure: An Order-Theoretic Perspective

arXiv: https://arxiv.org/abs/2305.15057 · HTML: https://mlsanity.com/paper/2305.15057/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 86 references that are in the map.
- First posted on arXiv 24 May 2023.

## Builds on (most cited first, 25 of 25)

- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019)
- [SpanBERT: Improving Pre-training by Representing and Predicting Spans](https://mlsanity.com/paper/1907.10529/) (2019)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [Deep Biaffine Attention for Neural Dependency Parsing](https://mlsanity.com/paper/1611.01734/) (2016)
- [End-to-end Neural Coreference Resolution](https://mlsanity.com/paper/1707.07045/) (2017)
- [Order-Embeddings of Images and Language](https://mlsanity.com/paper/1511.06361/) (2015)
- [Neural Language Modeling by Jointly Learning Syntax and Lexicon](https://mlsanity.com/paper/1711.02013/) (2017)
- [Simple and Accurate Dependency Parsing Using Bidirectional LSTM Feature Representations](https://mlsanity.com/paper/1603.04351/) (2016)
- [Revealing the Myth of Higher-Order Inference in Coreference Resolution](https://mlsanity.com/paper/2009.12013/) (2020)
- [Efficient Second-Order TreeCRF for Neural Dependency Parsing](https://mlsanity.com/paper/2005.00975/) (2020)
- [Coreference Resolution without Span Representations](https://mlsanity.com/paper/2101.00434/) (2021)
- [Head-Driven Phrase Structure Grammar Parsing on Penn Treebank](https://mlsanity.com/paper/1907.02684/) (2019)
- [Viable Dependency Parsing as Sequence Labeling](https://mlsanity.com/paper/1902.10505/) (2019)
- [Straight to the Tree: Constituency Parsing with Neural Syntactic Distance](https://mlsanity.com/paper/1806.04168/) (2018)
- [Constituent Parsing as Sequence Labeling](https://mlsanity.com/paper/1810.08994/) (2018)
- [Scheduled Multi-Task Learning: From Syntax to Translation](https://mlsanity.com/paper/1804.08915/) (2018)
- [Tetra-Tagging: Word-Synchronous Parsing with Linear-Time Inference](https://mlsanity.com/paper/1904.09745/) (2019)
- [Second-Order Neural Dependency Parsing with Message Passing and End-to-End Training](https://mlsanity.com/paper/2010.05003/) (2020)
- [Bracketing Encodings for 2-Planar Dependency Parsing](https://mlsanity.com/paper/2011.00596/) (2020)
- [A Unifying Theory of Transition-based and Sequence Labeling Parsing](https://mlsanity.com/paper/2011.00584/) (2020)
- [Headed-Span-Based Projective Dependency Parsing](https://mlsanity.com/paper/2108.04750/) (2021)
- [A Critical Analysis of Biased Parsers in Unsupervised Parsing](https://mlsanity.com/paper/1909.09428/) (2019)
- [A Structured Span Selector](https://mlsanity.com/paper/2205.03977/) (2022)

## Built on by (most cited first, 2 of 2)

- [Modeling Layout Reading Order as Ordering Relations for Visually-rich Document Understanding](https://mlsanity.com/paper/2409.19672/) (2024)
- [Revisiting the Phenomenon of Syntactic Complexity Convergence on German Dialogue Data](https://mlsanity.com/paper/2408.12177/) (2024)

## Abstract (arXiv)

Tasks that model the relation between pairs of tokens in a string are a vital part of understanding natural language. Such tasks, in general, require exhaustive pair-wise comparisons of tokens, thus having a quadratic runtime complexity in the length of the string. We show that these exhaustive comparisons can be avoided, and, moreover, the complexity of such tasks can be reduced to linear by casting the relation between tokens as a partial order over the string. Our method predicts real numbers for each token in a string in parallel and sorts the tokens accordingly, resulting in total orders of the tokens in the string. Each total order implies a set of arcs oriented from smaller to greater tokens, sorted by their predicted numbers. The intersection of total orders results in a partial order over the set of tokens in the string, which is then decoded into a directed graph representing the desired linguistic structure. Our experiments on dependency parsing and coreference resolution show that our method achieves state-of-the-art or comparable performance. Moreover, the linear complexity and parallelism of our method double the speed of graph-based coreference resolution models, and bring a 10-times speed-up over graph-based dependency parsers.