Tokenization as Finite-State Transduction
This work addresses a foundational issue in NLP for researchers and practitioners by providing a unified theoretical framework for tokenization, though it is incremental in extending existing methods.
The paper tackles the problem of tokenization in neural language models by introducing a finite-state transduction framework that efficiently encodes all possible tokenizations of a regular language, and shows that popular schemes like BPE and WordPiece fit within it, enabling guided generation with constraints that align with the tokenizer's canonical tokenization.
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.