The Foundations of Tokenization: Statistical and Computational Concerns

## Abstract

Abstract Tokenization—the practice of converting strings of characters from an
alphabet into sequences of tokens over a vocabulary—is a critical step in
the NLP pipeline. The use of token representations is widely credited with
increased model performance but is also the source of many undesirable
behaviors, such as spurious ambiguity or inconsistency. Despite its recognized
importance as a standard representation method in NLP, the theoretical
underpinnings of tokenization are not yet fully understood. In particular, the
impact of tokenization on statistical estimation has been investigated mostly
through empirical means. The present paper contributes to addressing this
theoretical gap by proposing a unified formal framework for representing and
analyzing tokenizer models. Based on the category of stochastic maps, this
framework enables us to establish general conditions for a principled use of
tokenizers, and most importantly, 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
designing and implementing tokenizer models, such as inconsistency, ambiguity,
tractability, and boundedness. The framework and results advanced in this
paper contribute to building robust theoretical foundations for
representations in neural language modeling that can inform future empirical
research.

## 1 Introduction

As a critical step in the natural language processing (NLP) pipeline,
tokenization generally refers to the process of breaking up sequences of symbols
into subsequences that can be represented as units or “tokens”. The
tokenization of linguistic data has long been a common practice in the
processing of natural language
(cf. Palmer, ; Jurafsky & Martin, ). However, the
significance of tokenizers took a turn with the emergence of deep neural models
for NLP, where the representation of linguistic units plays a renewed
fundamental role. With the development and widespread adoption of the *Byte
Pair Encoding* (BPE) algorithm (Sennrich et al., ), subword
tokenization became the privileged representation method for neural NLP.
Adapting an existing compression algorithm (Gage, ) to overcome the
challenges of out-of-vocabulary (OOV) terms in the context of neural machine
translation, BPE quickly replaced previous heuristic and rule-based tokenizer
models such as Morfessor (Creutz & Lagus, ) and Moses
(Koehn et al., ), and was soon followed by other data-driven
models, including *WordPiece* (Wu et al., , following
,
) and *Unigram*
(Kudo, ) among the most widely adopted (cf. Mielke et al., , for a
survey).

The importance of subword tokenization for language models (LMs) has grown ever
since and are now built into standard language modeling toolkits,
remaining the only major step not fully integrated into widely used
end-to-end neural models. Among their recognized benefits, two are often
advanced in the literature. Tokenizers offer the capacity of training language
models over an *open vocabulary*, circumventing the difficulties associated
with OOV terms (Sennrich et al., ). Also, tokenization is often
described as an efficient, lossless *encoding* of the original data
(Zouhar et al., ). Moreover, based on empirical evidence of
different kinds, tokenization has been hypothesized to introduce a helpful
inductive bias in language modeling
(Nawrot et al., ; Schmidt et al., ; Uzan et al., ),
although in the current state of the art, this hypothesis remains an open
question. At the same time, tokenizers have also been in the spotlight for
exhibiting undesirable behaviors that can have a negative impact on LMs. To name just a few, tokenization can be the source of spurious
ambiguity (Kudo, ; Cao & Rimell, ), generate
alignment issues (Poesia et al., ; Athiwaratkun et al., ), hinder robustness (Kudo, ; Xue et al., ), or result
in inconsistent scoring in the use of LMs in other scientific fields, like
psycholinguistics (Salazar et al., ; Kauf & Ivanova, ).

The uncovering of undesirable behaviors together with the lack of conclusive
theoretical explanations for either their positive or negative effects in
language modeling motivated several recent attempts to dispense with
tokenization altogether (Xue et al., ; Clark et al., ; Wang et al., , *inter
alia*).
However, in the current state of research, the practical benefits of token
representations in neural language modeling seem to outweigh their
disadvantages, indicating that there is something to be understood rather than
discarded in the process of tokenization.

The study of tokenization models has been an active area of research in recent
years. Most of the work in this direction has been driven by an empirical
perspective (Ding et al., ; Hou et al., ; Domingo et al., ; Fujii et al., , *inter
alia*).
Among the notable exceptions adopting a more theoretical approach are
Guo (); Kudo (); Zouhar et al. (; ); Berglund & van der Merwe (); Rajaraman et al. ().
However, in the current state of the art, we still see a need for a more
foundational perspective from which *necessary conditions for the
consistent use of tokenizers* can be formally established *in general*.
Such a perspective should also provide the means to analyze known issues in
tokenization in a formal way, ultimately informing future empirical research and
contributing to increasing the reliance on models in situations in which properties
such as formal guarantees, verification, or interpretability are as important as
performance for an LM.

Accordingly, the objective of the present paper is to take a decisive step
forward toward a robust theoretical grounding for neural NLP by laying the
foundations of tokenization from a formal perspective. To that end, we
characterize the problem of tokenization in current language modeling as arising
from the fact that, in practice, starting from an alphabet $\Sigma$ of
elementary units, one seeks to estimate a probability distribution over
$\Sigma^{*}$ indirectly, that is, by estimating a probability distribution
over sequences of tokens in $\Delta^{*}$, where the set of tokens
$\Delta$ is, in general, different from $\Sigma$. Therefore, the problem of
tokenization is determined by the forward and backward mappings between
$\Sigma^{*}$ and $\Delta^{*}$. To address this problem, we propose
a formal framework based on what we found to be the simplest mathematical tool
allowing us to characterize tokenizer models in their full generality, namely
the category of stochastic maps. The proposed framework enables us to establish
general conditions for a principled use of tokenizers. Crucially, we prove the
necessary and sufficient conditions for a tokenizer model to preserve the
consistency of statistical estimators. Additionally, this paper aims to advance
the theoretical understanding of existing challenges associated with
tokenization, particularly those pertaining to inconsistency, ambiguity,
tractability, and boundedness. To achieve this, we characterize these known
issues through the lens of formal properties of composable maps, such as
injectivity, multiplicativity, and finite decomposition.

The plan of the paper is as follows. In § 2, we present
preliminary notions, including elementary aspects of formal language theory and
the concept of stochastic maps, extending some existing results to cover the
case of countably infinite sets. We also provide notational and
terminological remarks. In § 3, we propose a unified formal framework
for representing and analyzing tokenization models and establish various results
for the use of tokenizers, including the necessary and sufficient conditions for
a tokenizer model to preserve the consistency of estimators. Finally, in
§§ 4 and 5 we discuss, from a formal perspective,
statistical and computational concerns relevant to the study, design, and
implementation of tokenizer models.

## 2 Preliminaries

### 2.1 Formal Languages, Estimators, and Stochastic Maps

An alphabet $\Sigma$ is a finite, non-empty set of symbols. The
set $\Sigma^{n}\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\overbrace{
\Sigma\times\cdots\times\Sigma}^{n\text{ times}}$ consists of strings of symbols of length $n$.
The symbol $\varepsilon$ denotes the empty string of length 0. The union
$\Sigma^{*}\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\bigcup_{n=0
}^{\infty}\Sigma^{n}$ consists of all
finite strings (including $\varepsilon$) from the alphabet $\Sigma$.
Similarly, we denote by $\Sigma^{\leq N}$ the set of all strings from
$\Sigma$ of length less or equal to $N$. String concatenation is an associative
product $\Sigma^{*}\times\Sigma^{*}\overset{\cdot}{\to}\Sigma^{*}$ for which $\varepsilon$ is an identity element. The triple
$(\Sigma^{*},\cdot,\varepsilon)$ defines a monoid, which is, in
fact, a model of the free monoid on the set $\Sigma$.

A language $L$ over an alphabet $\Sigma$ is a set of strings $L\subseteq\Sigma^{*}$. A language model $p$ is a probability
distribution over $\Sigma^{*}$.
That is, $p$ is a function $p:\Sigma^{*}\to[0,1]$ such that
$\sum_{\bm{\sigma}\in\Sigma^{*}}p(\bm{\sigma})=1.$ Language models
generalize languages in the sense that the support of a language model,
i.e., $\mathrm{supp}\!\left(p\right)=\{\bm{\sigma}\mid p(\bm{\sigma})\neq 0\}$, is a language. The definition of a language model as a probability
distribution on $\Sigma^{*}$ is deliberately broad. In particular, note
that no compatibility between $p$ and the monoidal structure in
$\Sigma^{*}$ is assumed.

In NLP, practitioners generally seek to estimate a language model $p$ from exemplars of naturally occurring text. Formally, the modeler assumes there
exists a true distribution $p^{\star}$ over $\Sigma^{*}$, and considers a
multiset of naturally occurring texts $\{\bm{\sigma}_{n}\}_{n=1}^{N}\subset\Sigma^{*}$ to be samples from $p^{\star}$. In its most general form, an
estimator of $p^{\star}$ is a sequence $\{p_{n}\}$ of probability distributions on
$\Sigma^{*}$ such that $p_{n}$ becomes closer to $p^{\star}$ as $n$
increases. We call an estimator consistent if the sequence $\{p_{n}\}$ converges *pointwise* to $p^{\star}$.(^1^11Following common convention, we will sometimes denote convergence as $\{p_{n}\}\to p^{\star}$, which is not to be confused with the notation for functional types (e.g., $\Sigma^{*}\to\Delta^{*}$). The context of use should be enough to prevent any ambiguity.) More precisely, given a probability distribution $p^{\star}\colon\Sigma^{*}\to[0,1]$ , and a sequence distributions $\{p_{n}\colon\Sigma^{*}\to[0,1]\}$, we say that $\{p_{n}\}$ is a consistent estimator
of $p^{\star}$ if and only if, for all strings $\bm{\sigma}\in\Sigma^{*}$,
the sequence of numbers $\{p_{n}(\bm{\sigma})\}$ converges to the number
$p^{\star}(\bm{\sigma})$.

This notion of consistent estimation is general enough to include many
estimation methods, where the $p_{i}$ can depend on various properties
of the sample, such as the size $N$, or possibly a set of parameters $\theta$.
Likewise, we use pointwise convergence to define consistent estimation because
pointwise convergence is a weak kind of convergence, and so our definition is
compatible with a wide variety of convergence measures, and relatively easy to
check for. For example, a common practice in NLP is to produce an estimator
$\{p_{n}\}$ through a sequence of steps in the process of minimizing *cross
entropy loss*, which amounts to minimizing the *relative entropy* also
called *the Kullback–Leibler divergence*,
$D_{\mathrm{KL}}(p^{\star}\parallel p_{n})$ between $p^{\star}$ and
$p_{n}$. This is a stronger form of convergence: if
$D_{\mathrm{KL}}(p^{\star}\parallel p_{n})\to 0$ then $p_{n}\to p^{\star}$ pointwise (a consequence of Pinsker’s lemma) and so $\{p_{n}\}$ is a
consistent estimator of $p^{\star}$.

Our definition of tokenizer models will require the use of a special kind of map
between sets called a stochastic map. The reference Baez & Fritz ()
contains a detailed introduction to the category of finite sets with stochastic
maps between them. Here, we will extend some of the results in
Baez & Fritz () to cover the case of countably infinite sets. We
assume all sets are countable, either finite or countably infinite. A
stochastic map from a set $X$ to a set $Y$ is a function from $X$ to the
set of probability distributions on $Y$. We use

$$ $X\rightsquigarrow Y$ $$

to denote a stochastic map from $X$ to $Y$ and the
notation $x\mapsto f(y\mid x)$ to denote the probability of $y\in Y$ in the
distribution assigned to $x\in X$. In other words, a stochastic map $f\colon X\rightsquigarrow Y$
is a function

$$ $\displaystyle X\times Y$ $\displaystyle\to[0,1]$ $\displaystyle(x,y)$ $\displaystyle\mapsto f(y\mid x)$ $$

satisfying $\sum_{y\in Y}f(y\mid x)=1$ for all $x\in X$. The notation $f(y\mid x)$ is evocative of the conditional probability of $y$ given $x$, but it’s
more accurate to think of “indexing” by $x$ rather than “conditioning" on $x$
since there is no assumption that the numbers $f(y\mid x)$ assemble into a
joint distribution on $X\times Y$. In particular, the sum $\sum_{x\in X}f(y\mid x)$ could, for example, be infinite.

Significantly, stochastic maps can be composed. The composition

$$ ${X}$ ${Y}$ ${Z}$ $\scriptstyle{f}$ $\scriptstyle{gf}$ $\scriptstyle{g}$ $$

$gf\colon X\rightsquigarrow Z$ is defined by

$$ $gf(z\mid x)=\sum_{y\in Y}g(z\mid y)f(y\mid x).$ (1) $$

Since the sum in equation equation 1 is infinite, it requires a
check that the formula for $gf(z\mid x)$ is finite, and that for each $x\in X$, $gf(-\mid x)$
defines
a probability distribution on $Z$,
both of which follow from the fact that:

$$ $\sum_{z\in Z}gf(z\mid x)=\sum_{z\in Z}\sum_{y\in Y}g(z\mid y)f(y\mid x)=\sum_{ y\in Y}\sum_{z\in Z}g(z\mid y)f(y\mid x)=\sum_{y\in Y}f(y\mid x)=1.$ $$

If one arranges a stochastic map into an $|X|\times|Y|$ matrix with the
$f(y\mid x)$ entry in the $x,y$ position, then every entry is nonnegative and
the sum of every row is $1$. The computation above shows that composition of
stochastic maps is realized by matrix multiplication, and that even when the
matrices are infinite, the row-column dot products are finite and the result of
matrix multiplication is again a matrix with nonnegative entries whose rows sum
to $1$. From this perspective, it is clear that composition of stochastic maps
is associative.

Stochastic maps generalize both ordinary probability distributions and
functions. A probability distribution over a set $X$ can be represented as a
stochastic map into $X$ from a 1-element set, denoted as $\mathbf{1}:=\{1\}$,
i.e., $p\colon\mathbf{1}\rightsquigarrow X$. In such cases, the customary
notation $p(x)$ can be used without risk of ambiguity as a shorthand of the more
cumbersome $p(x\mid 1)$. An ordinary function $f\colon X\to Y$ can be regarded
as a stochastic map $X\rightsquigarrow Y$ by mapping $x$ to the probability
distribution on $Y$ concentrated on the singleton $\{f(x)\}$, in which case we
say the stochastic map $f$ is *deterministic*. For simplicity, when a
stochastic map $f:X\rightsquigarrow Y$ is deterministic, writing $y=f(x)$ means that $f(y\mid x)=1$ and $f(y^{\prime}\mid x)=0$ for $y^{\prime}\neq y$. Composition generalizes both composition of functions
and the pushforward of a probability function via a function. If $p\colon\mathbf{1}\rightsquigarrow X$ is a probability distribution on $X$ and $f:X\to Y$ is a deterministic function, then the composition ${\mathbf{1}}$${X}$${Y}$$\scriptstyle{p}$$\scriptstyle{f}$ is a stochastic map $fp:1\rightsquigarrow Y$, which is a
probability distribution on $Y$ whose formula is $fp(y)=\sum_{x\in X}f(y|x)p(x|1)=\sum_{x\in f^{-1}(y)}p(x)$. That is, $fp$ is just the
pushforward of the probability distribution $p$ via the function $f$.

For any set $X$, the identity function on $X$ behaves as an identity for stochastic maps. That is $\textnormal{id}_{X}\colon X\rightsquigarrow X$ is the stochastic map defined by $\textnormal{id}_{X}(x^{\prime}\mid x)=1$ when $x^{\prime}=x$ and $\textnormal{id}_{X}(x^{\prime}\mid x)=0$ when $x^{\prime}\neq x$. In matrix
representation, $\textnormal{id}_{X}$ is the identity matrix, and satisfies $f\textnormal{id}_{X}=f=\textnormal{id}_{Y}f$ for all stochastic maps $f:X\rightsquigarrow Y$.

The notions of injectivity and surjectivity exist for stochastic maps.
A stochastic map $f:X\rightsquigarrow Y$ is injective iff the support of $f(-\mid x)$ and $f(-\mid x^{\prime})$ are disjoint whenever $x\neq x^{\prime}$. The support of the stochastic map $f$ is the union of the support of the distributions $f(-\mid x)$ as $x$ ranges over $X$. A stochastic map $f:X\rightsquigarrow Y$ is surjective
iff, for all $y\in Y$, there exists $x\in X$ such that $f(y\mid x)\neq 0$. Injectivity and surjectivity for stochastic maps reduce to their ordinary definitions for deterministic functions.

### 2.2 Notation and Terminology

We adopt the following notational conventions. Alphabets will be denoted by
uppercase Greek letters (e.g., $\Sigma$, $\Delta$). In the context of
tokenization, we will be interested in looking at maps between strings of
languages over two different alphabets, which we will denote as $\Sigma$ and
$\Delta$. For a more intuitive presentation that avoids ambiguity, we reserve
the term alphabet for the former and call vocabulary the latter
instead. We denote symbols by lowercase Greek letters, e.g., $\sigma\in\Sigma,\delta\in\Delta$, calling them characters in the first
case and tokens in the second. Strings will be denoted by bold lowercase
Greek letters, e.g., $\bm{\sigma}\in\Sigma^{*},\bm{\delta}\in\Delta^{*}$, reserving the name character strings or texts for
the former and token strings or token sequences for the latter. The
reader should keep in mind this terminological distinctions are for expository
purposes only. From the formal perspective advanced in this paper, we do not assume any inherent privilege of $\Sigma$ over $\Delta$, focusing, instead, on how their respective elements can be mapped into each other.

When necessary, we will distinguish the empty character string $\varepsilon_{\Sigma}\in\Sigma^{*}$ from the empty token sequence $\varepsilon_{\Delta}\in\Delta^{*}$. Examples of strings and tokens will be
written in monospace font (e.g., t, the). There are cases
where $\Delta\cap\Sigma^{*}\neq\emptyset$, and it will be necessary to
distinguish between concatenation in $\Sigma^{*}$ and $\Delta^{*}$. In
$\Delta^{*}$, concatenation will be denoted as $\shortmid$. So, for example,
if $\Sigma=\{\texttt{t},\texttt{h},\texttt{e}\}$ and $\Delta=\{\texttt{th},\texttt{he},\texttt{e}\}$, the expression
$\texttt{t}\cdot\texttt{h}\cdot\texttt{e}$ denotes the concatenation in
$\Sigma^{*}$ of the three characters t, h, and
e, while the expression $\texttt{t}{\shortmid}\texttt{he}$ represents the
concatenation in $\Delta^{*}$ of the two tokens t and
he. The cases when $\Delta\cap\Sigma^{*}\neq\emptyset$ are of
sufficient significance that we shall generally avoid using simple juxtaposition
of characters to express concatenation. Therefore, the reader should always
interpret th as a token in $\Delta$, and not a text in
$\Sigma^{*}$ (written $\texttt{t}\cdot\texttt{h}$). If further notational
clarification is needed, square brackets may be used to represent the
concatenation of two texts in $\Sigma^{*}$ (and likewise for
$\Delta^{*}$). For instance,
$[\texttt{t}\cdot\texttt{h}]\cdot\texttt{e}$ denotes the concatenation of the
text $\texttt{t}\cdot\texttt{h}$ with the character e in
$\Sigma^{*}$. Should any ambiguity between specific characters and tokens
arise (e.g., $\texttt{t}\in\Sigma$ vs. $\texttt{t}\in\Delta$), it
will be explicitly disambiguated whenever there is a risk that context alone is
insufficient.

## 3 A Formal Framework for Tokenization

As observed in the previous pages, in current NLP, the problem of tokenization
arises from the fact that one seeks to estimate a model $p^{\star}$ over strings
of symbols in one alphabet *indirectly*, that is, by estimating a
probability distribution $q$ over strings of symbols on a different
alphabet. Therefore, from a strictly formal perspective, the problem of
tokenization can be characterized as that of the respective mappings between two
sets of strings, conventionally referred to as the set $\Sigma^{*}$ of
character strings and the set $\Delta^{*}$ of token sequences. In order
to estimate $p^{\star}$ through $q$, $\Sigma^{*}$ needs to be mapped
into and from $\Delta^{*}$. The connection between $\Sigma^{*}$
and $\Delta^{*}$ is thus made through a pair of mappings $(\tau,\kappa)$ that constitutes the basis of our formal characterization
of tokenization. Accordingly, in its most general form, a tokenizer can be
defined as follows:

###### Definition 3.1 .

A tokenizer model (or simply
tokenizer) from $\Sigma^{*}$ to $\Delta^{*}$ is a pair of
stochastic maps $\mathcal{T}=(\tau,\kappa)$, respectively called
the encoder and the decoder, where the encoder is a stochastic
map $\tau\colon\Sigma^{*}\rightsquigarrow\Delta^{*}$, and the decoder is a stochastic map $\kappa\colon\Delta^{*}\rightsquigarrow\Sigma^{*}$.

Definition 3.1 is deliberately broad, covering *any* pair of
string-to-string mappings $\tau$ and $\kappa$. Other than the fact that
the domain of each mapping constitutes the codomain of the other, we define the
encoder and decoder as arbitrary stochastic maps. In other words, we will be
regarding $\tau$ and $\kappa$ primarily from the point of view of their
*composition*. In particular, we do not require any specific connection
between the alphabet $\Sigma$ and the vocabulary $\Delta$, and hence the use
of the terms encoder and decoder is also strictly conventional. However, the
distinction is motivated by an implicit assumption behind the established use of
tokenizers in language models—namely, that the samples $\{\bm{\sigma}_{n}\}_{n=1}^{N}\subset\Sigma^{*}$ of naturally occurring texts used for estimation can
be mapped into $\Delta^{*}$ in such a way that the estimated
model $q$ can be, in turn, transformed into a model $p$ over
$\Sigma^{*}$ through the map $\kappa$, such that $\kappa q=p$ can be considered as an estimate of the original distribution
$p^{\star}$.

Despite the potential empirical increase in a model’s predictive performance
resulting for specific tokenization choices, the soundness of such a procedure
is not guaranteed for arbitrary $\tau$ and $\kappa$ without further
conditions. On one hand, the notion of estimation in
$\Delta^{*}$ is not well-defined unless there exists a reference
distribution $q^{\star}$ over $\Delta^{*}$ to which the estimator
$\{q_{n}\}$ can converge. On the other, assuming such an estimator is consistent,
transforming it into a consistent estimator of $p^{\star}$ requires a way to map
the sequence $\{q_{n}\}$ into a sequence $\{p_{n}\}$ that converges to $p^{\star}$.

Assuming a reference distribution $p^{\star}$ exists on $\Sigma^{*}$, one
obtains a reference $q^{\star}$ on $\Delta^{*}$ simply as the composition
(Eq. 1) with the encoder: $q^{\star}=\tau p^{\star}$. In
other words, the following diagram of stochastic maps commutes

The distribution $q^{\star}$ is just the pushforward of the measure
$p^{\star}$ along $\tau$, which then makes the encoder $\tau$ a
*measure-preserving map* between $(\Sigma^{*},p^{\star})$
and $(\Delta^{*},q^{\star})$

In the same way, $\{p_{n}\}$ can be obtained by mapping the sequence $\{q_{n}\}$ through $\kappa$. By defining $p_{i}=\kappa q_{i}$, we
obtain the following commutative diagram

So far, none of these requirements imposes conditions on $\tau$ and
$\kappa$ other than being well-defined mappings between their respective
domains and codomains. Notably, the notion of estimation of
$\tau p^{\star}$ is well defined for arbitrary $\tau$. However, given a
consistent estimator $\{q_{n}\}$ of $q^{\star}$, $\{\kappa q_{n}\}$* is not guaranteed to converge to* $p^{\star}$ without further
conditions on $\kappa$. To establish such conditions, we will need the
following lemmas.

###### Lemma 3.1 .

Let $\{p_{n}\}$ be a sequence of probability distributions over a countable set
$X$ that converges pointwise to a probability distribution $p$. Then
$\lim_{n\to\infty}\sum_{x\in X}|p_{n}(x)-p(x)|=0$.

###### Proof.

Fatou’s lemma applied to $X$ with the counting measure implies that for any
sequence of nonnegative functions $\{f_{n}\}$ on $X$,

$$ $\sum_{x\in X}\liminf_{n\to\infty}f_{n}(x)\leq\liminf_{n\to\infty}\sum_{x\in X} f_{n}(x).$ (2) $$

We’ll apply this to $f_{n}:=p_{n}+p-|p_{n}-p|$. First, note that since
$\lim_{n\to\infty}p_{n}(x)=p(x)$, we have $\liminf_{n\to\infty}f_{n}(x)=p(x)+p(x)-0=2p(x)$ so the left hand side of equation 2 becomes $\sum_{x\in X}2p(x)=2$. Therefore,

$$ $\displaystyle 2$ $\displaystyle\leq\liminf_{n\to\infty}\sum_{x\in X}f_{n}(x)$ $\displaystyle=\liminf_{n\to\infty}\sum_{x\in X}p_{n}(x)+p(x)-|p_{n}(x)-p(x)|$ $\displaystyle=\liminf_{n\to\infty}\sum_{x\in X}p_{n}(x)+\sum_{x\in X}p(x)-\sum _{x\in X}|p_{n}(x)-p(x)|$ $\displaystyle=\liminf_{n\to\infty}1+1-\sum_{x\in X}|p_{n}(x)-p(x)|$ $\displaystyle=2-\limsup_{n\to\infty}\sum_{x\in X}|p_{n}(x)-p(x)|.$ $$

It follows that $\limsup_{n\to\infty}\sum_{x\in X}|p_{n}(x)-p(x)|\leq 0$. So
$\lim_{n\to\infty}\sum_{x\in X}|p_{n}(x)-p(x)|=0$.
∎

###### Corollary 3.0.1 .

Let $\{p_{n}\}$ be a sequence of probability distributions over a countable set
$X$ that converges pointwise to a probability distribution $p$. Then
$\{p_{n}\}\to p$ uniformly.

###### Proof.

Since the sum of nonnegative numbers is always greater than any particular
term in the sum and $\lim_{n\to\infty}\sum_{x\in X}|p_{n}(x)-p(x)|=0$, we
can conclude that the sequence $\{p_{n}\}\to p$ uniformly.
∎

###### Lemma 3.2 .

Let $f$ be a stochastic map from $X$ to $Y$, and $\{p_{n}\}$ be an estimator for
a probability distribution $p$ on $X$. Then $fp_{n}$ is an estimator for the
probability distribution $fp$ on $Y$.

###### Proof.

Fix $y\in Y$. We will show that $\{fp_{n}(y)\}\to fp(y)$.
By Lemma 3.1, we have that $\lim_{n\to\infty}\sum_{x\in X}\lvert p_{n}\left(x\right)-p\left(x\right)\rvert
=0.$ Therefore,

$$ $\displaystyle\lim_{n\to\infty}\left\lvert fp_{n}(y)-fp(y)\right\rvert$ $\displaystyle=\lim_{n\to\infty}\left\lvert\sum_{x}f(y\mid x)p_{n}(x)-\sum_{x}f (y\mid x)p(x)\right\lvert$ (3) $\displaystyle\leq\lim_{n\to\infty}\sum_{x}f(y\mid x)\left\lvert p_{n}\left(x \right)-p\left(x\right)\right\lvert$ (4) $\displaystyle\leq\lim_{n\to\infty}\sum_{x}\lvert p_{n}\left(x\right)-p\left(x \right)\rvert$ (5) $\displaystyle=0.$ (6) $$

∎

In other words, Lemma 3.2 says that *stochastic maps preserve
the consistency of estimators*. Armed with this lemma, it is now easy to
establish a simple but fundamental principle for the use of tokenization
models in language modeling:

###### Theorem 3.1 (Fundamental Principle of Tokenization) .

Given a reference probability distribution $p^{\star}$ over $\Sigma^{*}$,
a tokenizer $\mathcal{T}=(\tau,\kappa)$ from $\Sigma^{*}$
to $\Delta^{*}$, and a consistent estimator $\{q_{n}\}$ of the image
reference distribution $q^{\star}=\tau p^{\star}$, the sequence
$\{\kappa q_{n}\}$ is a consistent estimator of $p^{\star}$ if
and only if $\kappa\tau p^{\star}=p^{\star}$.

###### Proof.

By hypothesis, $\{q_{n}\}\to q^{\star}$ and by definition $q^{\star}=\tau p^{\star}$.
By Lemma 3.2,
applying $\kappa$ to both sides, we have that $\{\kappa q_{n}\}\to\kappa q^{\star}$ and so

$$ $\{\kappa q_{n}\}\to\kappa\tau p^{\star}.$ $$

Therefore, if $\kappa\tau p^{\star}=p^{\star}$ we have $\{\kappa q_{n}\}\to p^{\star}.$ Conversely, if $\{\kappa q_{n}\}\to p^{\star}$ we have both $\{\kappa q_{n}\}\to p^{\star}$ and $\{\kappa q_{n}\}\to\kappa\tau p^{\star}$ and so by the uniqueness of limits, $\kappa\tau p^{\star}=p^{\star}$.
∎

Our whole setting can be represented with the following diagram:

This setting is quite general, and Theorem 3.1
characterizes precisely when a consistent estimator $\{q_{n}\}$ of $q^{\star}$
yields a consistent estimator $\{p_{n}\}$ of $p^{\star}$ after decoding. Based
on the fundamental principle expressed in Theorem 3.1, we
propose the following definitions:

###### Definition 3.2 .

Given a probability distribution $p$ over $\Sigma^{*}$, a
tokenizer $\mathcal{T}=(\tau,\kappa)$ from
$\Sigma^{*}$ to $\Delta^{*}$ is consistent with respect
to $p$ if we have $\kappa\tau p=p$.

###### Definition 3.3 .

Let $p$ be a probability distribution over
$\Sigma^{*}$ and $\mathcal{T}=(\tau,\kappa)$ a tokenizer
from $\Sigma^{*}$ to $\Delta^{*}$. When $\kappa\tau=\textnormal{id}_{\Sigma^{*}}$, we say that $\mathcal{T}$ is exact.

Notice that
exact tokenizers are consistent, but a tokenizer that is consistent with respect
to a distribution $p$ is not necessarily exact.
Take, for instance, a probability distribution $p$ over some set $X$ and
$x^{\prime},x^{\prime\prime}\in X$ such that $p(x^{\prime})=p(x^{\prime\prime})=c$. Then one can fashion a
tokenizer for which $\kappa\tau(x)=x$ for all $x$ except
$\kappa\tau(x^{\prime})=x^{\prime\prime}$ and $\kappa\tau(x^{\prime\prime})=x^{\prime}$. Such a
tokenizer is consistent with respect to $p$ without being exact. Consistency
with respect to all distributions, however, is the same as being exact.

###### Proposition 3.1 .

A tokenizer $\mathcal{T}=(\tau,\kappa)$ from $\Sigma^{*}$
to $\Delta^{*}$ is exact if and only if it is consistent with respect
to every probability distribution over $\Sigma^{*}$.

###### Proof.

Exact means $\kappa\tau=\textnormal{id}_{\Sigma^{*}}$ hence
$\kappa\tau p=p$ for every probability distribution
$p$ on $\Sigma^{*}$. To prove the other direction, suppose that
$\kappa\tau p=p$ for every $p$ on
$\Sigma^{*}.$ Fix an arbitrary $\bm{\sigma}\in\Sigma^{*}$. Let
$p_{\bm{\sigma}}$ be the point mass distribution on $\Sigma^{*}$ concentrated
on $\bm{\sigma}$. So $p_{\bm{\sigma}}(\bm{\sigma})=1$ and $p_{\bm{\sigma}}(\bm{\sigma}^{\prime})=0$ for any
$\bm{\sigma}^{\prime}\neq\bm{\sigma}.$ By hypothesis, $p_{\bm{\sigma}}=\kappa\tau p_{\bm{\sigma}}.$ Apply to $\bm{\sigma}$ to get $1=\kappa\tau p_{\bm{\sigma}}(\bm{\sigma})$. The right hand side, as the pushforward of $p_{\bm{\sigma}}$
via $\kappa\tau$, says $1=p_{\bm{\sigma}}(\kappa\tau(\bm{\sigma})).$ Since $p_{\bm{\sigma}}$ takes the value $1$ at
only one point, it follows that the argument $\kappa\tau(\bm{\sigma})=\bm{\sigma}$. Since $\bm{\sigma}$ was arbitrary, we conclude that $\kappa\tau=\textnormal{id}_{\Sigma^{*}}$, i.e., the tokenizer $(\tau,\kappa)$ is
exact.
∎

Significantly, exact tokenizers have special properties. First, if a tokenizer
$(\tau,\kappa)$ is exact, then $\kappa$ is deterministic over
the image of $\tau$, because $\textnormal{id}_{\Sigma^{*}}$ also is. Formally:

###### Proposition 3.2 .

Let $\mathcal{T}=(\tau,\kappa)$ be an exact tokenizer from $\Sigma^{*}$
to $\Delta^{*}$. Then $\kappa$ is deterministic on the support of $\tau$ (or, $\kappa$ is deterministic “$\tau$ almost everywhere.”)

###### Proof.

Assume $(\tau,\kappa)$ is exact, i.e.,
$\kappa\tau=\textnormal{id}_{\Sigma^{*}}$, and let $\bm{\sigma}\in\Sigma^{*}$.

Since $\sum_{\bm{\delta}\in\Delta^{*}}\tau(\bm{\delta}\mid\bm{\sigma})=1$ and $\kappa\tau(\bm{\sigma}|\bm{\sigma})=\textnormal{id}_{\Sigma^{*}}(\bm{\sigma}
\mid\bm{\sigma})=1$. We
obtain:

$$ $\displaystyle 0$ $\displaystyle=\sum_{\bm{\delta}\in\Delta^{*}}\tau(\bm{\delta}\mid\bm{\sigma})- \kappa\tau(\bm{\sigma}|\bm{\sigma})$ (7) $\displaystyle=\sum_{\bm{\delta}\in\Delta^{*}}\tau(\bm{\delta}\mid\bm{\sigma})- \sum_{\bm{\delta}\in\Delta^{*}}\kappa(\bm{\sigma}\mid\bm{\delta})\tau(\bm{ \delta}\mid\bm{\sigma})$ (8) $\displaystyle=\sum_{\bm{\delta}\in\Delta^{*}}\tau(\bm{\delta}\mid\bm{\sigma})- \kappa(\bm{\sigma}\mid\bm{\delta})\tau(\bm{\delta}\mid\bm{\sigma})$ (9) $\displaystyle=\sum_{\bm{\delta}\in\Delta^{*}}\tau(\bm{\delta}\mid\bm{\sigma})( 1-\kappa(\bm{\sigma}\mid\bm{\delta})).$ (10) $$

Since Eq. 10 is a sum of nonnegative terms that equals zero, each terms must be zero. It follows that if $\tau(\bm{\delta}\mid\bm{\sigma})>0$ for some $\bm{\delta}$ (e.g.: $\bm{\delta}$ is in the support of $\tau$) then then $1-\kappa(\bm{\sigma}\mid\bm{\delta})=0\Leftrightarrow\kappa(\bm{\sigma}\mid\bm
{\delta})=1$. From which it follows that

$$ $\kappa(\bm{\sigma}^{\prime}\mid\bm{\delta})=\begin{cases}1&\text{if $\bm{ \sigma}^{\prime}=\bm{\sigma}$}\\ 0&\text{if $\bm{\sigma}^{\prime}\neq\bm{\sigma}.$}\end{cases}.$ $$

∎

The condition $\kappa\tau=\textnormal{id}_{\Sigma^{*}}$ means $\tau$ is a right
inverse (or section) of $\kappa$ and $\kappa$ is a left inverse (or retraction) of $\tau$. The proof of Proposition 3.2 shows that
$\tau(\bm{\delta}\mid\bm{\sigma})$ places probability zero on every $\bm{\delta}\in\Delta^{*}$ such that $\kappa(\bm{\sigma}\mid\bm{\delta})=0$. Since $\kappa$ is deterministic in this case,
it follows that for an exact tokenizers ($\tau$, $\kappa$), the encoder does not place positive probability mass on a token sequence for more than one text. In other words, $\tau$ is
injective. Additionally, it must be that for each text $\bm{\sigma}$ there is a $\bm{\delta}$ with $\kappa(\bm{\sigma}\mid\bm{\delta})=1$, and therefore $\kappa$ is surjective.

###### Definition 3.1 .

###### Lemma 3.1 .

###### Proof.

###### Corollary 3.0.1 .

###### Proof.

###### Lemma 3.2 .

###### Proof.

###### Theorem 3.1 (Fundamental Principle of Tokenization) .

###### Proof.

###### Definition 3.2 .

###### Definition 3.3 .

###### Proposition 3.1 .

###### Proof.

###### Proposition 3.2 .

###### Proof.

## 4 Statistical Concerns: Inconsistency and Ambiguity

While in most concrete cases of statistical language modeling a tokenizer’s
consistency is implicitly or explicitly assumed, there are many ways in which
the conditions established in the previous section can, and in practice do, fail
to be satisfied. In this section, we discuss two main statistical concerns to be
considered when implementing or using tokenizers, namely inconsistency and
ambiguity, and associate them with the properties of maps introduced in the
previous section. The following definitions will be convenient:

###### Definition 4.1 .

Given a tokenizer $\mathcal{T}=(\tau,\kappa)$, we say $\mathcal{T}$ has a deterministic encoder (resp. decoder) or is
$\bm{\tau}$-deterministic (resp.
$\bm{\kappa}$-deterministic) if $\tau$ (resp. $\kappa$)
is a deterministic map. When a tokenizer $\mathcal{T}$ is both
$\tau$-deterministic and exact, we have that $\mathcal{T}$ is also
$\kappa$-deterministic, and $\kappa=\tau^{-1}$ over
$\tau(\Sigma^{*})$. Therefore, in such a case we say $\mathcal{T}$ is strictly bijective.

###### Definition 4.1 .

#### Noninjective 𝝉 𝝉 \bm{\tau} bold_italic_τ and Inconsistency.

Most commonly
used tokenizers have deterministic encoders, including BPE
(Sennrich et al., ) and WordPiece (Wu et al., ), as well
as Unigram (Kudo, ) when used without regularization. As we
have seen, deterministic functions can be understood as a particular case of
stochastic maps where the probability mass is concentrated on one element.
Tokenizers with deterministic encoders thus constitute a simplified form of
tokenization. However, even in this simplified setting, the consistency of the
tokenization process is not guaranteed.
The following example offers an elementary intuition of this
circumstance.

###### Example 4.1 .

Consider the simple configuration
represented in Fig. 1, where both $\tau$ and $\kappa$ are deterministic maps. Let $p^{\star}(\bm{\sigma}_{1})=0.2$ and
$p^{\star}(\bm{\sigma}_{2})=p^{\star}(\bm{\sigma}_{3})=0.4$, with $p^{\star}(\bm{\sigma}_{i})=0$
for $i>3$. For $q^{\star}=\tau p^{\star}$, we have, therefore,
$q^{\star}(\bm{\delta}_{1})=0.2$, $q^{\star}(\bm{\delta}_{2})=0$, and
$q^{\star}(\bm{\delta}_{3})=0.8$, with $q^{\star}(\bm{\delta}_{i})=0$ for $i>3$, and
hence $\kappa\tau p^{\star}(\bm{\sigma}_{1})=0\neq 0.2$,
$\kappa\tau p^{\star}(\bm{\sigma}_{2})=0.2\neq 0.4$, and
$\kappa\tau p^{\star}(\bm{\sigma}_{1})=0.8\neq 0.4$. Assuming
$\{q_{n}\}$ is a consistent estimator of $q^{\star}$, the pushforward of
$q_{n}$ through $\kappa$ (i.e., $\kappa q_{n}$) would
result in an inconsistent estimation of $p^{\star}$. Notice that the consistency
of the tokenizer is relative to the distribution. Relative to a different
distribution $p$ in $\Sigma^{*}$, where, for instance,
$p(\bm{\sigma}_{1})=p(\bm{\sigma}_{2})=0$ and $p=p^{\star}$ otherwise, the
tokenizer specified in Fig. 1 is consistent.

Figure: Figure 1: Example of an inconsistent tokenizer with $\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}\tau$ represented in violet and $\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}\kappa$ represented in teal.

As shown in § 3 and illustrated in Example 4.1, a
fundamental cause of a tokenizer’s inconsistency is the *lack of
injectivity of the encoder* $\tau$. This is not just a theoretical concern.
Even if in its abstract specification a tokenizer’s encoder may appear to be
injective, implementation decisions often introduce noninjective behaviors.
These include normalizing operations, such as lowercasing, stripping accents,
removing punctuation, or uniforming whitespaces
(e.g., Moi & Patry, ). Irrespective of how the core
tokenization function is defined, including this preprocessing step as part of
the tokenizer model results in a noninjective encoding that compromises the
consistency of estimators.

Even if all text normalization is excluded from the decoding function, it can
still happen that $\tau$ is undefined for some elements in $\Sigma$, and
is, therefore, only a partial function. If the exceptions are handled by
returning a unique distinguished token in $\Delta$ (e.g., an ‘unknown’ token
unk), then $\tau$ becomes noninjective, incurring the risk of
inconsistency. The appeal to an unk token and the difficulties associated with
it have been widely studied from the perspective of OOV terms, especially in the
context of NMT
(e.g., Luong & Manning, ; Jean et al., ), ultimately
leading to subword tokenizers as a way of providing “open vocabulary”
solutions (Sennrich et al., ; Wu et al., ).(^2^22For a tokenization-free alternative to the OOV problem, see, for instance, Xue et al. () and Clark et al. (), who also offer a good overview of existing approaches to this problem.) Formally, it is enough to
inject $\Sigma$ into $\Delta$ (i.e., to include the alphabet in the
vocabulary) to achieve an open vocabulary, something most tokenizers do by
default. However, open vocabulary solutions do not entirely remove the risk of
noninjective decoding, which is not reducible to OOV problems. Some open
vocabulary models, for instance, limit the size of $\Sigma$ to the sample’s $k$
most frequent symbols, mapping all other symbols to an unk character *in
$\Sigma$* (e.g., Wu et al., ). Understood as a preprocessing step,
this operation should not affect $\tau$’s injectivity. However, the use of
copy models (e.g., Luong et al., ) that keep track of the
original out-of-alphabet symbols to restore them in decoding, violates *de
facto* the tokenizer’s injectivity, and with it, the model’s consistency over
strings including those symbols.

Even if all symbols in the training sample are included in $\Sigma$,
*out-of-alphabet* symbols can always be encountered at test or inference
time. The recourse to a distinguished unk symbol *both in $\Sigma$ and
$\Delta$* must, therefore, be handled in such a way that the injectivity of
$\tau$ is guaranteed. The use of a stochastic $\kappa$ (e.g., Mielke & Eisner, ) over the restricted domains of
out-of-alphabet/vocabulary elements could, in principle, provide novel ways of
addressing this problem in agreement with consistency concerns.

###### Example 4.1 .

#### Noninjective 𝜿 𝜿 \bm{\kappa} bold_italic_κ and Ambiguity.

Whenever
$\kappa$ is noninjective, the tokenizer introduces *ambiguity* in the
model because more than one token sequence is mapped into a unique text. In
strictly bijective tokenizers, decoding is injective over the encoder’s image,
thus preventing ambiguity in principle. However, in practice, whenever
$\tau(\Sigma^{*})$ is a proper subset of $\Delta^{*}$,
it may happen that the probability mass placed by the estimated language model
outside the image of $\tau$ is nonzero, reintroducing ambiguity into the
model (cf. Example 4.2 for an elementary illustration). This
ambiguity is, however, *spurious* because $\tau$ was assumed to
be deterministic, and hence the ambiguity does not stem from the reference
distribution $p^{\star}$, but is a side-effect of the estimator. An obvious
source of spurious ambiguity resides in the fact that consistency is a property
defined *in the limit*. As a consequence, for any $\bm{\delta}\in\Delta^{*}$, $q_{n}(\bm{\delta})$ can and will generally differ from
$q^{\star}(\bm{\delta})$. Spurious ambiguity can also result from the fact that,
due to the properties of gradient descent and certain activation functions such
as softmax, neural models are incapable of assigning zero probability to
elements of $\Delta^{*}$. Although spurious ambiguity has been
identified among the motivations for introducing subword regularization
(Kudo, ; Provilkov et al., ), it is often overlooked or
disregarded, despite its potential nonnegligible effect on estimation
(Cao & Rimell, ; Chirkova et al., ).

###### Example 4.2 .

Take, for instance, a strictly bijective tokenizer such as BPE or WordPiece,
with $\kappa$ performing concatenation of the token maps in the usual way.
Let $\Sigma=\{\textnormal{{t}},\textnormal{{h}},\textnormal{{e}}\}$
and $\Delta=\{\textnormal{{t}},\textnormal{{h}},\textnormal{{e}},\textnormal{{th}},
\textnormal{{he}}\}$.
In this minimal configuration, it is easy to see that
$\kappa(\textnormal{{t}}{\shortmid}\textnormal{{h}}{\shortmid}\textnormal{{e}})
=\kappa(\textnormal{{t}}{\shortmid}\textnormal{{he}})=\kappa(\textnormal{{th}}
{\shortmid}\textnormal{{e}})=\textnormal{{t}}\cdot\textnormal{{h}}\cdot
\textnormal{{e}}\in\Sigma^{*}$. However, BPE or WordPiece being strictly bijective
tokenizers, $\tau$ can only map the value of $\kappa$ to at most
one of the latter’s arguments, say
$\tau(\textnormal{{t}}\cdot\textnormal{{h}}\cdot\textnormal{{e}})=\textnormal{{
th}}{\shortmid}\textnormal{{e}}$. We then have that
$\tau(\kappa(\textnormal{{t}}{\shortmid}\textnormal{{he}}))\neq\textnormal{{t}}
{\shortmid}\textnormal{{he}}$ (and likewise for
$\textnormal{{t}}{\shortmid}\textnormal{{h}}{\shortmid}\textnormal{{e}}$). If the estimator happens to place nonzero
probability mass on any of the latter two token sequences, the model will
exhibit spurious ambiguity.

Spurious ambiguity is not the only kind of ambiguity that can result from the
use of tokenization in language models. Whenever a tokenizer model is
stochastic, a deterministic $\kappa$ must be noninjective for the model to
preserve the consistency of estimators. However, the ambiguity thus introduced
is not spurious in that it is deliberately designed for statistical purposes. In
current tokenization practices, the main reason for the introduction of
*stochastic* ambiguity is regularization
(Kudo, ; Provilkov et al., ). The claim is that, by
exhibiting different token sequences corresponding to the same text during
training, a model increases its capability to handle text compositionality as
well as its robustness to noise and tokenization errors. However, one could also
conceive of a stochastic tokenizer where the possible images of a text reflect
the objective probabilities of all *linguistic* ambiguities potentially
affecting it (e.g., $\texttt{an}{\shortmid}\texttt{icecream}$, $\texttt{an}{\shortmid}\texttt{ice}{\shortmid}\texttt{cream}$, $\texttt{a}{\shortmid}\texttt{nice}{\shortmid}\texttt{cream}$ as three possible token sequences for the text: $\texttt{a}\cdot\texttt{n}\cdot\texttt{i}\cdot\texttt{c}\cdot\texttt{e}\cdot
\texttt{c}\cdot\texttt{r}\cdot\texttt{e}\cdot\texttt{a}\cdot\texttt{m}$).

Although all these classes of ambiguity (spurious, stochastic, and linguistic)
are both formally and semantically different, they all represent the same
challenge for the tokenizer’s consistency: The probability mass indirectly
assigned by the model to one text in a language is spread out over different
token sequences. Notice that all these cases of ambiguity can coexist, and hence
their impact is difficult to evaluate. Yet, from a formal perspective, the
solution for all these cases is the same: The computation of
$\kappa q_{n}$ for a single text $\bm{\sigma}\in\Sigma^{*}$
requires marginalizing over all its preimages $\bm{\delta}$ through $\kappa$, for
which $q_{n}(\bm{\delta})>0$, following the composition of stochastic maps
presented in the previous section (Eq. 1). However, such
operation can be computationally challenging because it can imply summing over a
large or even infinite number of terms. For different strategies to address that
challenge, see
van Merriënboer et al. (); Buckman & Neubig (); Grave et al. (); Hannun et al. (); Cao & Rimell ().

###### Example 4.2 .

## 5 Computational Concerns: Tractability and Boundedness

As the end of the previous section shows, even when a tokenizer model is
consistent and all statistical concerns are taken into account, there are still
computational aspects that can hinder the practice of tokenization. In this
section, we turn to issues of tractability, and boundedness.

#### Multiplicativity and Tractability.

Definitions 3.1, 3.2 and 3.3 are general enough to allow for all
kinds of encoding and decoding functions, including uncomputable ones
Consider the following example:

###### Example 5.1 .

Let $\Sigma=\Delta=\{\textnormal{{0}},\textnormal{{1}}\}$, and define
$\mathcal{T}_{unc}=(\tau_{unc},\kappa_{unc})$ as a deterministic model in the
following way:

$$ $\tau_{unc}(\bm{\sigma})=\begin{cases}\bm{\sigma}{\shortmid}\textnormal{{1}},& \text{if $\bm{\sigma}$ describes a valid}\\ &\text{Turing Machine followed by}\\ &\text{an input for which it halts.}\\ \bm{\sigma}{\shortmid}\textnormal{{0}},&\text{otherwise.}\end{cases}\qquad \kappa_{unc}(\bm{\delta})=\begin{cases}\varepsilon,&\text{if $\bm{\delta}\in \Delta$.}\\ \bm{\sigma},&\text{otherwise, where $\bm{\delta}=\bm{\sigma}{\shortmid}\delta$ .}\end{cases}$ $$

Significantly, $\mathcal{T}_{unc}$ is not only well-defined but also exact and
therefore consistent for any language model $p$ over $\Sigma^{*}$.
However, $\tau_{unc}$ is famously an uncomputable function, and hence
$\mathcal{T}_{unc}$ is an uncomputable tokenizer.

However, even when a tokenizer model is computable, its tractability is
not guaranteed. Indeed, there are many reasons that could make the computation
of tokenization intractable. Many of the operations defining tokenizer models
involve sums over infinite sets. This is particularly true for the composition
of stochastic maps whenever it is performed over an infinite domain, as in our
case. Therefore, it is crucial to assess the tractability not only of $\tau$ and $\kappa$, but also of their composition $\kappa\tau$.

We have seen that when a tokenizer model is exact, $\tau$ is a section for
$\kappa$, or equivalently, $\tau$ is injective. It follows that, for any
$\bm{\sigma}\in\Sigma^{*}$, $\tau$ concentrates the probability mass on
only a subset of $\Delta^{*}$. This property can help reduce the
computational costs by restricting the sums to just those subsets. However,
without further constraints, those subsets can still be infinite. For this reason, we consider the following properties:

###### Definition 5.1 .

We say a tokenizer model $\mathcal{T}=(\tau,\kappa)$ is
multiplicative if its decoder $\kappa$ respects the concatenation
products; that is, if
$\kappa(\bm{\delta}^{\prime}{\shortmid}\bm{\delta}^{\prime\prime})=\kappa(\bm{
\delta}^{\prime})\cdot\kappa(\bm{\delta}^{\prime\prime})$.

###### Definition 5.2 .

We say the kernel of a multiplicative tokenizer’s decoder $\kappa$ is trivial if $\kappa$ maps nonempty token sequences to nonempty
token sequences (i.e., if $\bm{\delta}\neq\varepsilon_{\Delta}$ then
$\kappa(\bm{\delta})\neq\varepsilon_{\Sigma}$).

The most commonly used tokenizers, including BPE, WordPiece, and Unigram, are
multiplicative. An obvious consequence of multiplicative tokenizers is that
decoding preserves the prefix structure of token sequences. More precisely, let
$\bm{\delta}^{\prime}\preceq\bm{\delta}$ denote the fact that $\bm{\delta}=\bm{\delta}^{\prime}{\shortmid}\bm{\delta}^{\prime\prime}$
for $\bm{\delta},\bm{\delta}^{\prime},\bm{\delta}^{\prime\prime}\in\Delta^{*}$ (and likewise for
$\bm{\sigma},\bm{\sigma}^{\prime},\bm{\sigma}^{\prime\prime}\in\Sigma^{*}$). Then we have that
$\bm{\delta}^{\prime}\preceq\bm{\delta}$ implies $\kappa(\bm{\delta}^{\prime})\preceq\kappa(\bm{\delta})$. This property is crucial in autoregressive models, where
each token in a sequence depends only on the tokens preceding it and can then be
computed in a left-to-right fashion. In these cases, multiplicativity ensures
that the model’s output can be decoded on the fly, excluding decoding functions
such as string reversal. Moreover, notice that, for a kernel of a multiplicative
tokenizer’s decoder to be trivial, it is enough that $\kappa(\delta)\neq\varepsilon_{\Sigma}$ for any $\delta\in\Delta$. This implies that token sequences
do not include special tokens that are erased during decoding, e.g., padding or
end-of-sentence tokens.

Importantly, when a multiplicative tokenizer’s decoder has a trivial kernel, a
decoded text cannot be shorter than the token sequence from which it has been
decoded. This simple observation guarantees that the number of preimages of a
text under $\kappa$ is finite. More precisely,

###### Proposition 5.1 .

Let $\mathcal{T}=(\tau,\kappa)$ be a multiplicative tokenizer
model whose decoder’s kernel is trivial. If
$\kappa(\delta_{1}{\shortmid}\delta_{2}{\shortmid}\ldots{\shortmid}\delta_{m})=
\sigma_{1}\cdot\sigma_{2}\cdot\ldots\cdot\sigma_{n}$ then $m\leq n$.

###### Proof.

We can reason by induction. The property is true when $m=1$ since 1 is the
minimun length of any possible image of $\kappa$. Assume it is true for
$m=k$ and let $\bm{\delta}=\delta_{1}{\shortmid}\ldots{\shortmid}\delta_{k}{\shortmid}\delta_
{k+1}$.
Then $\kappa(\bm{\delta})=\kappa(\delta_{1}{\shortmid}\ldots{\shortmid}\delta_{k})
\cdot\kappa(\delta_{k+1})=\sigma_{1}\cdot\ldots\cdot\sigma_{r}\cdot\sigma_{r+1
}\cdot\ldots\cdot\sigma_{r+s}$, where $\kappa(\delta_{k+1})=\sigma_{r+1}\cdot\ldots\cdot\sigma_{r+s}$. Since $r\geq k$ and $s\geq 1$, we
have that $r+s\geq k+1$.
∎

###### Corollary 5.0.1 .

Let $\mathcal{T}=(\tau,\kappa)$ be a multiplicative tokenizer model
whose decoder’s kernel is trivial.
Then for any text $\bm{\sigma}$, the set $\kappa^{-1}(\bm{\sigma})$ is finite.

Proposition 5.1 guarantees that, if no token in the vocabulary is mapped
to the empty string, then the length of every preimage of a text $\bm{\sigma}$ of
length $n$ has length less than or equal to $n$. So the number of elements in
$\kappa^{-1}(\bm{\sigma})$, and hence also the support of $\tau$ for any
given $\bm{\sigma}\in\Sigma^{*}$ when $(\tau,\kappa)$ is
exact, is bounded by $\sum_{i=1}^{n}|\Delta|^{i}$.

Since this bound is exponential in $n$, the exact or approximate computation of
a tokenizer’s encoding and decoding so that the consistency of the language
model is not compromised requires the appeal to multiple strategies as the ones
mentioned at the end of § 4. Ideally, the complexity a
tokenizer model (that is, of the composition $\kappa\tau$) should be
at most linear in the length of the input text. By placing all the probability
mass on one token sequence, $\kappa\tau$ in exact deterministic
tokenizers, such as BPE and WordPiece, can be computed in linear time as long as
$\tau$ and $\kappa$ can be computed in linear time. However, rigorously
handling spurious ambiguity still represents a challenge in these cases.

###### Example 5.1 .

###### Definition 5.1 .

###### Definition 5.2 .

###### Proposition 5.1 .

###### Proof.

###### Corollary 5.0.1 .

#### Finite Decomposition and Boundedness.

Finally, even though
multiplicativity ensures the length of all the preimages of
$\kappa^{-1}(\bm{\sigma})$ is bounded by the length of $\bm{\sigma}$, texts themselves
may have unbounded length. In practice, the bounded character of tokenization
is secured externally, namely by fixing a hyperparameter that artificially
limits the length of input texts. However, it can be desirable to address
boundedness as an internal property of a tokenizer. For this reason, we
introduce the following definitions:

###### Definition 5.3 .

Given two sets $A,B$, and a
map $f\colon A^{*}\to B^{*}$ we say $f$ is of finite type
if, there exists $n\in\mathbb{N}$ such that, for every $\bm{a}\in A^{*}$, there exists a nonempty $\bm{a}^{\prime}\in A^{\leq n}$ such
that $\bm{a}=\bm{a}^{\prime}\cdot\bm{a}^{\prime\prime}$ and
$f(\bm{a})=f(\bm{a}^{\prime})\cdot f(\bm{a}^{\prime\prime})$.

###### Definition 5.4 .

A tokenizer model $\mathcal{T}=(\tau,\kappa)$ is called
bounded if both $\tau$ and $\kappa$ are of finite type.

If a tokenizer is bounded, it means the input can be decomposed into bounded
components. The “maximal munch” approach
(Reps, ; Palmer, ) adopted by WordPiece, for instance,
iteratively maps the successive longest prefixes of a text to tokens in the
vocabulary. WordPiece’s encoder is thus bounded by the maximum length of the
preimages of $\Delta$ through $\tau$, and can therefore be implemented as
a finite-state transducer (Song et al., ). Notice, however, that, in
general, if a tokenizer is bounded in the sense of
Definitions 5.3 and 5.4, that does not mean there exists a tractable
algorithm to find the decomposition $\bm{a}=\bm{a}^{\prime}\cdot\bm{a}^{\prime\prime}$, which could, in principle, depend on the entire
$\bm{a}$. Significantly, Berglund & van der Merwe () showed that,
under specific conditions on the structure of the list of rules or “merges”,
BPE is also bounded and an algorithm can be found to compute
$\tau(\bm{\sigma}^{\prime}){\shortmid}\tau(\bm{\sigma}^{\prime\prime})=\tau(\bm
{\sigma})$ in an online
fashion with finite lookahead. Moreover,
Berglund et al. () proposed an algorithm for
constructing deterministic finite automata representing BPE’s encoder.

###### Definition 5.3 .

###### Definition 5.4 .

## 6 Conclusion

In this work, we have addressed the use of token representations in NLP from a
foundational perspective. Relying on the category of stochastic maps as an
elementary formal tool, we proposed a general definition of a tokenizer as an
arbitrary pair of composable maps. The framework proposed enabled us to
formally establish several properties of tokenization, and most importantly, the
necessary and sufficient condition for a tokenizer to preserve the consistency
of estimators. Furthermore, our approach allowed to shed new theoretical light
on known issues concerning tokenization, namely inconsistency, ambiguity,
tractability, and boundedness, by characterizing the latter through formal
properties of composable maps such as injectivity, multiplicativity, or finite
decomposition. We believe this framework will inform future empirical research
and contribute to establishing and developing theoretical and practical aspects
of representation learning in NLP on solid grounds, especially in cases where
the reliance on a model requires to go beyond its mere performance, and take into account properties such as formal
guarantees, verification, theoretical soundness, interpretability, or liability.

## 7 Limitations

Statistical and computational concerns are not the only concerns relevant to a
foundational approach to tokenization. In particular, this paper does not
address structural concerns, i.e., structural properties of the sets
$\Sigma^{*}$ and $\Delta^{*}$ such as their monoidal structure, the
preservation of structural features through $\tau$ and $\kappa$, or the
important question of the choice of $\Delta$. Algorithmic concerns related to
the effective computation of exact tokenizers have been left unaddressed, as
well as theoretical concerns related to interpretability and the possible
relation to linguistic segmentation. Although the perspective adopted here is
purely formal, and as such, self-contained, some aspects alluded in this paper
could benefit from the insights given by experimental results. These points will
be the object of future work.

## 8 Acknowledgments

The authors thank Saeed Zakeri for pointing out an interesting interplay between
a general fact about the Banach spaces $L^{1}(X)$ for any measure space $X$ and
the fact that for the little $l^{p}$ spaces, the $l^{\infty}$ norm is smaller than
the $l^{1}$ norm, which led to the proof of Lemma 3.1. The
authors also thank Li Du for useful feedback at the early stages of this work.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 4
questions: Comments:
- While you mention the relation between tokenization and linguistic segmentation, you should give more credit to the line of work that has investigated this link over the last few years (e.g., [Bostrom & Durrett, 2020](https://aclanthology.org/2020.findings-emnlp.414/), [Hofmann et al., 2021](https://aclanthology.org/2021.acl-long.279/), [Gow-Smith et al., 2022](https://aclanthology.org/2022.emnlp-main.786/), [Beinborn & Pinter, 2023](https://aclanthology.org/2023.emnlp-main.272/)), which is also relevant for your discussion of linguistic ambiguities (lines 395-399).
- Lines 405-410: I think you should mention that the practical benefit of this operation has been shown to be negligible in most cases ([Chirkova et al., 2023](https://aclanthology.org/2023.acl-short.1/)).
- I would recommend putting the examples from the appendix back into the main paper, especially Example 8.1. You have a bit of space left, so this should be feasible, and it would help illustrate your arguments.

Typos:
- Line 120: "distributions" -> "distribution"
- Line 158: "equation equation 1" -> "equation 1"
- Line 205: "this" -> "these"
- Line 459: "complexity a tokenizer model" -> "complexity of a tokenizer model"
soundness: 3
strengths: The paper has several strengths:

- Tokenization is a critical aspect of modern-day natural language processing, but its theoretical underpinnings are not yet fully understood. The formalisms introduced in the paper help close this gap and might become the basis for future work.
- The application of stochastic maps to tokenization is novel.
- The presentation is excellent; the writing is clear and overall easy to follow.
summary: Disclaimer: I previously reviewed an earlier version of this paper during its submission to NeurIPS 2024.

This paper proposes a formal approach to tokenization. Specifically, the authors apply the notion of stochastic maps (Baez & Fritz, 2014) to tokenization models, which allows them to formalize key properties of tokenizers such as their consistency. In a next step, they use their framework to analyze further statistical and computational aspects of tokenization (e.g., spurious ambiguity).
weaknesses: This is a completely theoretical paper without any empirical evaluation. While not a weakness _per se_, the authors mention that their findings have implications for the practical use of tokenizers (e.g., line 95). Compared to the version of the paper that was under submission at NeurIPS 2024, the authors have added sections discussing practical aspects of their observations (e.g., lines 345-350), but I still believe that a proper case study showcasing the practical value of the proposed formal framework would greatly enhance the potential impact of the paper. This is particularly desirable since many of the discussed problems are well-known in the community, so it is not clear what exactly the paper adds beyond a new theoretical perspective.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 4
questions: Would it be possible to provide some concrete examples of how the framework can be used to shed new light on differences between different types of tokenizers?
soundness: 4
strengths: The paper presents a novel framework for representing and analyzing tokenizers in the form of stochastic maps. The proposed framework has the potential to provide more a foundational statistical understanding of tokenizer behavior, which may lead to practical improvements.
summary: This paper presents a formalization of the tokenization process in modern language models. The formalization is based on the category of stochastic maps, which presents a novel and unified framework for representing and analyzing tokenizers. The paper also provides some examples of sing the framework to account for tokenizer behavior such as ambiguity and inconsistencies.
weaknesses: The paper provides some examples of how the framework can be utilized to shed new light on tokenizer behavior such as ambiguity and inconsistency, but it is not immediately clear to what extent the proposed framework can lead to practical improvements of tokenizer performance.

---

confidence: 1
contribution: 2
initial_rating: 5
presentation: 3
questions: I am unsure if I am not a relevant reviewer for this paper or if the paper is too foundational for the conference.
soundness: 3
strengths: — Theoretical position paper is from a foundational perspective, and mathematically justified analysis is introduced; strict definitions and notation conventions are presented.
summary: The authors address the problems of tokenization and use of the token representations in NLP from a foundational mathematical perspective. Based on the category of stochastic maps, the authors propose a general definition of a tokenizer as an arbitrary pair of composable maps, and this theoretical framework enables to establish general conditions for a principled use of tokenizers and the necessary and sufficient conditions for a tokenizer model to preserve the consistency of statistical estimators. The statistical and computational concerns (inconsistency, ambiguity, tractability, and boundedness) are discussed. To achieve this, authors characterize these known issues through the lens of formal properties of composable maps, such as injectivity, multiplicativity, and finite decomposition.
weaknesses: It's still unclear how to apply this knowledge to practical issues and better tokenizers for LLMs.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: Can the authors further clairify the connection between 3.1 and the rest of the paper please?
soundness: 3
strengths: The paper proposes an interesting and also promising theoretical direction to examine the tokenization problems: by explicitly examining the relationship between the true language model under its alphabet and the learned language model with the practical alphabet. Under this framework, the paper has shown some interesting preliimary results:
- Define propery the consistency from analysis viewpoint
- The propoerty of encoder and decoder and connect them with the problem of inconsistency and ambiguity
summary: The paper investigates into the tokenization process for language modelling from a theoretical viewpoint. 

The framework examines language modelling as mapping between a true language model on an alphabet and a learned language model on a separate alphabet, known as a stochastic map. In section 3, the paper establishes convergence property for various distributions in different spaces, as well as necessary function properties (injectivity and surjectivity). Later on, the paper leverages such properties to examine the problems (e.g injectivity, surjectivity) of current language models and connect them with concrete issues such as inconsistency, ambiguity, tractability, etc.
weaknesses: The connections between the derived properties/theorems and the NLP practice/problems are not strong. My arguments are stated as the following:
- In theorem 3.1 the authors derive the condition to make the estimator consistent; however, this property is nowhere more leveraged, the paper discusses in more detail the exact mappings and the derived injectivity/surjectivity properties which do not require the analysis from 3.1 and makes 3.1 a isolated construction without any implication built inside the paper.
- The injectivity (and surjectivity) discussions look more like discussions as a "related work" section. For example, no derivations are shown for problems such as "how severe the problem is when injectivity assumption is broken" or "when injectivity are ensured by certain techniques, what is the advantage quantified/bounded mathematically".
- While the boundness and tractability discussions are interesting, they are of observational nature. The paper will have significantly more impact if the paper is able to derive algorithms/improvements/theoretical implication out of them.

Meta-review: This paper presents a foundational perspective on tokenization and established some formal properties of tokenization; the authors established these properties via the utilization of stochastic maps, which is novel. 

Strengths:
- Very clear exposition.
- Novel work where there has been very little theoretical work on tokenization.

Weaknesses:
- No empirical validation of the framework (which is not a huge issue in my opinion).

Decision: Accept (Poster)