  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 tokenizer 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 tokenizer
model to preserve the consistency of statistical estimators. Additionally, we
discuss statistical and computational concerns crucial for the design and
implementation of tokenizer models. The framework and results advanced in this
paper represent a step toward a robust theoretical foundation for neural
language modeling.
