Constrained Decoding for Computationally Efficient Named Entity Recognition Taggers

Brian Lester, Daniel Pressel, Amy Hemmeter, Sagnik Ray Choudhury, Srinivas Bangalore

Abstract

Brian Lester, Daniel Pressel, Amy Hemmeter, Sagnik Ray Choudhury, Srinivas Bangalore. Findings of the Association for Computational Linguistics: EMNLP 2020.

2020.

Introduction

In Named Entity Recognition (NER), the standard architecture employs a Conditional Random Field (CRF) layer to ensure global coherence in sequence labeling. However, the $O(NT^2)$ complexity of the CRF forward algorithm creates a significant computational bottleneck, especially as tag sets grow. This paper investigates whether modern neural encoders, such as BiLSTMs, provide sufficient contextual information to render the learned transition parameters of a CRF redundant, allowing for a more efficient "constrained decoding" approach.

Methodology

The authors propose replacing the BiLSTM-CRF architecture with a two-part alternative:

  1. Cross-Entropy Training: The model is trained using standard token-level cross-entropy loss. This treats NER as a simple classification task for each word, which is significantly faster and easier to parallelize than the global CRF loss.
  2. Constrained Decoding: During inference, the Viterbi algorithm is used with a hand-crafted transition mask instead of a learned matrix. This mask enforces the logical rules of the IOBES tagging scheme (e.g., an "Inside" tag cannot follow an "Outside" tag) by assigning massive penalties to invalid transitions.

Experimental Setup

The approach was evaluated across four diverse sequential prediction tasks:

  • CoNLL 2003: The standard benchmark for news-based NER.
  • WNUT-17: NER for rare and emerging entities in noisy social media text.
  • OntoNotes: A large-scale, multi-domain dataset with 18 entity types.
  • Snips: A slot-filling dataset for voice assistants with a large tag set (39 types).

Key Insights: The Role of Data Characteristics

The effectiveness of constrained decoding depends on how much "work" the CRF layer was doing versus the neural encoder. The authors introduce metrics like "strictly dominated" tokens—instances where the tagging scheme's rules leave only one valid tag option despite local ambiguity.

Table 6: Dataset statistics highlighting tag types, ambiguity, and dominance metrics.

As shown in the table above, datasets like CoNLL (IOBES) have a high percentage of strictly dominated tokens (71.2%), suggesting that the CRF's learned transitions are largely redundant. In contrast, OntoNotes has higher ambiguity (14.9%) and fewer strictly dominated tokens (15.9%), indicating a greater need for the probabilistic modeling provided by a CRF. The authors also note that the IOBES scheme provides more rigid constraints than BIO, making it better suited for this approach.

Results and Efficiency

The results indicate that constrained decoding achieves F1 scores comparable to the CRF baseline on most benchmarks while offering substantial efficiency gains.

Table 1: Performance comparison (F1 score) between CRF and Constrained Decoding across benchmarks.

Key findings include:

  • Speed and Sustainability: The constrained decoding model trained in just 51.2% of the time required by an optimized CRF implementation, leading to a 35% reduction in estimated CO2 emissions.
  • Accuracy: On CoNLL, WNUT-17, and Snips, the difference in F1 scores was statistically insignificant.
  • The OntoNotes Exception: OntoNotes was the only dataset where the CRF significantly outperformed constrained decoding (87.43 vs 86.13 F1). This is attributed to the dataset's higher tag density and the CRF's ability to learn probabilistic transitions (e.g., a "Person" following a "Title") that hard rules cannot capture.

Conclusion

This research demonstrates that for many NER applications, the computationally expensive CRF layer can be replaced with a simple rule-based inference mask. While high-ambiguity datasets like OntoNotes still benefit from the full CRF, the proposed constrained decoding method offers a path toward faster, greener, and more scalable sequence labeling models.

Summary updated

BibTeX
@inproceedings{lester2020constrained,
  author = {Brian Lester and Daniel Pressel and Amy Hemmeter and Sagnik Ray Choudhury and Srinivas Bangalore},
  title = {{Constrained Decoding for Computationally Efficient Named Entity Recognition Taggers}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2020},
  url = {https://openreview.net/forum?id=UMw0XoMbpNE},
}
Figure