# Tokenization as Finite-State Transduction

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 34 references that are in the map.
- First posted on arXiv 21 Oct 2024.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing](https://mlsanity.com/paper/1808.06226/) (2018)
- [Between words and characters: A Brief History of Open-Vocabulary Modeling and Tokenization in NLP](https://mlsanity.com/paper/2112.10508/) (2021)
- [Fast WordPiece Tokenization](https://mlsanity.com/paper/2012.15524/) (2020)
- [Automata-based constraints for language model decoding](https://mlsanity.com/paper/2407.08103/) (2024)
- [A Formal Perspective on Byte-Pair Encoding](https://mlsanity.com/paper/2306.16837/) (2023)
- [Toward a Theory of Tokenization in LLMs](https://mlsanity.com/paper/2404.08335/) (2024)
- [The Foundations of Tokenization: Statistical and Computational Concerns](https://mlsanity.com/paper/2407.11606/) (2024)
- [Where is the signal in tokenization space?](https://mlsanity.com/paper/2408.08541/) (2024)
- [Distributional Properties of Subword Regularization](https://mlsanity.com/paper/2408.11443/) (2024)

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

- [UTF-8 Plumbing: Byte-level Tokenizers Unavoidably Enable LLMs to Generate Ill-formed UTF-8](https://mlsanity.com/paper/2511.05578/) (2025)
- [NCO: A Versatile Plug-in for Handling Negative Constraints in Decoding](https://mlsanity.com/paper/2605.10065/) (2026)
- [Beyond Perplexity: UTF-8 Validity in Byte-aware Language Models](https://mlsanity.com/paper/2606.14122/) (2026)
- [Trie Automata for Constrained Decoding over Large Finite Sets](https://mlsanity.com/paper/2608.12574/) (2026)
- [Component-Weighted Centroid Search for Exact Incremental BPE](https://mlsanity.com/paper/2609.40016/) (2026)

## Abstract (arXiv)

Tokenization is the first step in modern neural language model pipelines where an input text is converted to a sequence of subword tokens. We introduce from first principles a finite-state transduction framework which can efficiently encode all possible tokenizations of a regular language. We then constructively show that Byte-Pair Encoding (BPE) and MaxMatch (WordPiece), two popular tokenization schemes, fit within this framework. For BPE, this is particularly surprising given its resemblance to context-free grammar and the fact that it does not tokenize strings from left to right. An application of this is to guided generation, where the outputs of a language model are constrained to match some pattern. Here, patterns are encoded at the character level, which creates a mismatch between the constraints and the model's subword vocabulary. While past work has focused only on constraining outputs without regard to the underlying tokenization algorithm, our framework allows for simultaneously constraining the model outputs to match a specified pattern while also adhering to the underlying tokenizer's canonical tokenization.