Tokenization—the practice of converting strings of characters over an alphabet into sequences of tokens over a vocabulary—is a critical yet under-theorized step in the NLP pipeline. Notably, it remains the only major step not fully integrated into widely used end-to-end neural models. This paper aims to address this theoretical gap by laying the foundations of tokenization from a formal perspective. By articulating and extending basic properties about the category of stochastic maps, we propose a unified framework for representing and analyzing tokenization models. This framework allows us to establish general conditions for the use of tokenizers. In particular, we formally establish the necessary and sufficient conditions for a tokenization model to preserve the consistency of statistical estimators. Additionally, we discuss statistical and computational concerns crucial for the design and implementation of tokenization models. The framework and results advanced in this paper represent a step toward a robust theoretical foundation for neural language modeling.
Add the full text or supplementary notes for the publication here using Markdown formatting.