# Fast WordPiece Tokenization

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

## Key facts

- Cited by 87 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Dec 2020.

## Built on by (most cited first, 30 of 87)

- [Do All Languages Cost the Same? Tokenization in the Era of Commercial Language Models](https://mlsanity.com/paper/2305.13707/) (2023)
- [Between words and characters: A Brief History of Open-Vocabulary Modeling and Tokenization in NLP](https://mlsanity.com/paper/2112.10508/) (2021)
- [A Review of Large Language Models and Autonomous Agents in Chemistry](https://mlsanity.com/paper/2407.01603/) (2024)
- [LLMs are Good Sign Language Translators](https://mlsanity.com/paper/2404.00925/) (2024)
- [SERENGETI: Massively Multilingual Language Models for Africa](https://mlsanity.com/paper/2212.10785/) (2022)
- [StrucTexTv2: Masked Visual-Textual Prediction for Document Image Pre-training](https://mlsanity.com/paper/2303.00289/) (2023)
- [EndoChat: Grounded Multimodal Large Language Model for Endoscopic Surgery](https://mlsanity.com/paper/2501.11347/) (2025)
- [MAGNET: Improving the Multilingual Fairness of Language Models with Adaptive Gradient-Based Tokenization](https://mlsanity.com/paper/2407.08818/) (2024)
- [A general-purpose material property data extraction pipeline from large polymer corpora using Natural Language Processing](https://mlsanity.com/paper/2209.13136/) (2022)
- [The Foundations of Tokenization: Statistical and Computational Concerns](https://mlsanity.com/paper/2407.11606/) (2024)
- [Subobject-level Image Tokenization](https://mlsanity.com/paper/2402.14327/) (2024)
- [pNLP-Mixer: an Efficient all-MLP Architecture for Language](https://mlsanity.com/paper/2202.04350/) (2022)
- [UnifieR: A Unified Retriever for Large-Scale Retrieval](https://mlsanity.com/paper/2205.11194/) (2022)
- [Understanding and Mitigating Tokenization Bias in Language Models](https://mlsanity.com/paper/2406.16829/) (2024)
- [DictaBERT: A State-of-the-Art BERT Suite for Modern Hebrew](https://mlsanity.com/paper/2308.16687/) (2023)
- [ScanDL: A Diffusion Model for Generating Synthetic Scanpaths on Texts](https://mlsanity.com/paper/2310.15587/) (2023)
- [Multimodal Medical Code Tokenizer](https://mlsanity.com/paper/2502.04397/) (2025)
- [Is Your LLM Overcharging You? Tokenization, Transparency, and Incentives](https://mlsanity.com/paper/2505.21627/) (2025)
- [POINTS1.5: Building a Vision-Language Model towards Real World Applications](https://mlsanity.com/paper/2412.08443/) (2024)
- [Evaluating Tokenizer Performance of Large Language Models Across Official Indian Languages](https://mlsanity.com/paper/2411.12240/) (2024)
- [What changes when you randomly choose BPE merge operations? Not much](https://mlsanity.com/paper/2305.03029/) (2023)
- [Tokenization and Representation Biases in Multilingual Models on Dialectal NLP Tasks](https://mlsanity.com/paper/2509.20045/) (2025)
- [MaxMatch-Dropout: Subword Regularization for WordPiece](https://mlsanity.com/paper/2209.04126/) (2022)
- [MultiLegalSBD: A Multilingual Legal Sentence Boundary Detection Dataset](https://mlsanity.com/paper/2305.01211/) (2023)
- [Superpixel Tokenization for Vision Transformers: Preserving Semantic Integrity in Visual Tokens](https://mlsanity.com/paper/2412.04680/) (2024)
- [RadarLLM: Empowering Large Language Models to Understand Human Motion from Millimeter-Wave Point Cloud Sequence](https://mlsanity.com/paper/2504.09862/) (2025)
- [Serialized EHR make for good text representations](https://mlsanity.com/paper/2510.13843/) (2025)
- [An Interpretable Ensemble of Graph and Language Models for Improving Search Relevance in E-Commerce](https://mlsanity.com/paper/2403.00923/) (2024)
- [Knowledge of Pretrained Language Models on Surface Information of Tokens](https://mlsanity.com/paper/2402.09808/) (2024)
- [A Survey of Source Code Representations for Machine Learning-Based Cybersecurity Tasks](https://mlsanity.com/paper/2403.10646/) (2024)

## Abstract (arXiv)

Tokenization is a fundamental preprocessing step for almost all NLP tasks. In this paper, we propose efficient algorithms for the WordPiece tokenization used in BERT, from single-word tokenization to general text (e.g., sentence) tokenization. When tokenizing a single word, WordPiece uses a longest-match-first strategy, known as maximum matching. The best known algorithms so far are O(n^2) (where n is the input length) or O(nm) (where m is the maximum vocabulary token length). We propose a novel algorithm whose tokenization complexity is strictly O(n). Our method is inspired by the Aho-Corasick algorithm. We introduce additional linkages on top of the trie built from the vocabulary, allowing smart transitions when the trie matching cannot continue. For general text, we further propose an algorithm that combines pre-tokenization (splitting the text into words) and our linear-time WordPiece method into a single pass. Experimental results show that our method is 8.2x faster than HuggingFace Tokenizers and 5.1x faster than TensorFlow Text on average for general text tokenization.