# A dynamic programming algorithm for span-based nested named-entity recognition in O(n^2)

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 53 references that are in the map.
- First posted on arXiv 10 Oct 2022.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Rethinking the Inception Architecture for Computer Vision](https://mlsanity.com/paper/1512.00567/) (2015)
- [Deep Biaffine Attention for Neural Dependency Parsing](https://mlsanity.com/paper/1611.01734/) (2016)
- [A Unified Generative Framework for Various NER Subtasks](https://mlsanity.com/paper/2106.01223/) (2021)
- [Locate and Label: A Two-stage Identifier for Nested Named Entity Recognition](https://mlsanity.com/paper/2105.06804/) (2021)
- [A Minimal Span-Based Neural Constituency Parser](https://mlsanity.com/paper/1705.03919/) (2017)
- [Differentiable Dynamic Programming for Structured Prediction and Attention](https://mlsanity.com/paper/1802.03676/) (2018)
- [A Sequence-to-Set Network for Nested Named Entity Recognition](https://mlsanity.com/paper/2105.08901/) (2021)
- [Nested Named Entity Recognition via Second-best Sequence Learning and Decoding](https://mlsanity.com/paper/1909.02250/) (2019)
- [Neural Segmental Hypergraphs for Overlapping Mention Recognition](https://mlsanity.com/paper/1810.01817/) (2018)
- [Nested Named Entity Recognition with Partially-Observed TreeCRFs](https://mlsanity.com/paper/2012.08478/) (2020)
- [Multi-Grained Named Entity Recognition](https://mlsanity.com/paper/1906.08449/) (2019)
- [Labeling Gaps Between Words: Recognizing Overlapping Mentions with Mention Separators](https://mlsanity.com/paper/1810.09073/) (2018)
- [Nested Named Entity Recognition as Latent Lexicalized Constituency Parsing](https://mlsanity.com/paper/2203.04665/) (2022)
- [Span-based discontinuous constituency parsing: a family of exact chart-based algorithms with time complexities from O(n^6) down to O(n^3)](https://mlsanity.com/paper/2003.13785/) (2020)

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

- [Named Entity Recognition Under Domain Shift via Metric Learning for Life Sciences](https://mlsanity.com/paper/2401.10472/) (2024)
- [Filtered Semi-Markov CRF](https://mlsanity.com/paper/2311.18028/) (2023)
- [Tree-Averaging Algorithms for Ensemble-Based Unsupervised Discontinuous Constituency Parsing](https://mlsanity.com/paper/2403.00143/) (2024)

## Abstract (arXiv)

Span-based nested named-entity recognition (NER) has a cubic-time complexity using a variant of the CYK algorithm. We show that by adding a supplementary structural constraint on the search space, nested NER has a quadratic-time complexity, that is the same asymptotic complexity than the non-nested case. The proposed algorithm covers a large part of three standard English benchmarks and delivers comparable experimental results.