The Foundations of Tokenization: Statistical and Computational Concerns
Authors: Juan Luis Gastaldi
John Terilla
Luca Malagutti
Brian DuSell
Tim Vieira
Ryan Cotterell
Venue: ICLR 2025 Poster (2025)
Keywords: Tokenization
Language Models
Consistency
NLP
Theoretical Foundations
Stochastic Maps
Category Theory
Primary area: learning theory
TL;DR: This paper provides theoretical foundations for tokenization in language modeling, establishing necessary and sufficient conditions for the preservation of the consistency of statistical estimators

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 language model estimation has been investigated primarily 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. In addition, we discuss statistical and computational concerns crucial for designing and implementing tokenizer models, such as inconsistency, ambiguity, finiteness, and sequentiality. The framework and results advanced in this paper contribute to building robust theoretical foundations for representations in neural language modeling that can inform future theoretical and empirical research.

Published as a conference paper at ICLR 2025
THE FOUNDATIONS OF TOKENIZATION: STATISTICAL AND COMPUTATIONAL CONCERNS
Juan Luis Gastaldi' John T
Luca Malagutti Brian DuSell' Tim Vieira
Ryan Cotterell
'ETH Zürich City University of New York {juan. luis. gastaldi, Imalagutti, brian. dusell, ryan. cotterteerel1 htt.:jiinf..ee...hh.e..e j jterillaage cuny. cuny.edu edu tim. wee..vviiiieee vieira@gmail.com com
ABSTRACT
Tokenization the practice of converting strings of characters from alphabet into sequences of tokens over 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 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 language model estima- tion has been investigated primarily through empirical means. The present paper contributes to addressing this theoretical gap by proposing unified formal frame- work 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. In addition, discuss statistical and computational concerns crucial for designing and implementing tokenizer models, such as inconsistency. ambiguity, finiteness, and sequentiality. The framework and results advanced in this paper contribute to building robust theoretical foundations for representations in neural language modeling that can inform future theoretical and empirical research.
INTRODUCTION
As 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, known as tokens. The tokenization of linguistic data has long been common practice in the processing of natural language (cf. Palmer, 2000; Jurafsky & Martin, 2024). However, the significance of tokenizers took 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 al., 2016), subword tokenization became the privileged representation method for neural NLP. Adapting an existing compression algorithm (Gage, 1994) to overcome the challenges of voccablvycabulary (OOV) terms in the context of neural machine translation, BPE quickly replaced previous heuristic and rule-based tokenizer models such as Morfessor (Creutz& & Lagus, 2002) and Moses (Koehn et al., 2007), and was soon followed by other data-driven models. including WordPiece (Wu et al., 2016, following Schuster & Nakajima, 2012) and Unigram (Kudo, 2018) among the most widely adopted (cf. Mielke al., 2021, for survey).
The importance of subword tokenization for language models (LMs) has grown ever since, and tokenization methods 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 ability to train language models over open vocabulary, circumventing the difficulties associated with OOV terms (Sennrich et al., 2016). In addition, tokenization is often described as an efficient, lossless encoding of the original data (Zouhar et al., 2023a). Moreover, based empirical evidence of different kinds, tokenization has been hypothesized to introduce a helpful inductive bias in language modeling (Nawrot et al., 2023; Schmidt et al., 2024; Uzan al., 2024), although in the current state of the art, this hypothesis

---

Published as a conference paper at ICLR 2025
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, 2018; Cao & Rimell, 2021), generate alignment issues (Poesia et al., 2022; Athiwaratkun et al., 2024), hinder robustness (Kudo, 2018: 1018; Xue et al., 2022), neglect relevant linguistic features (Bostrom & Durrett, 2020; Hofmann et al., 2021; Gow-Smith et al., 2022; Beinborn & Pinter, 2023) or result in inconsistent scoring in the use of LMs in other scientific fields, like psycholinguisties (Salazar et al., 2020; Kauf & Ivanova, 2023; Giulianelli et al., 2024).
The prominence of undesirable behaviors induced by tokenization, together with the lack of conclusive theoretical explanations for either their positive or negative effects language modeling, motivated several recent attempts to dispense with tokenization altogether (Xue et al., 2022: Clark et al., 2022; Wang al., 2024, inter alia). However, 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., 2019; Hou et al., 2023; Domingo et al., 2023; Fujii et al., 2023, inter aliu). However, some notable exceptions exist where the authors have adopted a more theoretical approach (Guo. 1997; Kudo, 2018; Zouhar et al., 2023b;a; Berglund & van der Merwe, 2023; Rajaraman et al., 2024). The above-cited contributions notwithstanding. this paper contends there is still a need for a more foundational perspective. Among others, such perspective should provide the means to advance results the impact of tokenization on language model estimation, which are conspicuously absent from the literature. A foundational approach should also contribute analyzing known issues in tokenization in formal way, ultimately informing future theoretical and empirical research and contributing to increasing the reliance on models 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 step forward toward robust theoretical grounding for neural NLP by laying the foundations of tokenization from 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 Σ of elementary units, one seeks to estimate a probability distribution over > indirectly, that is, by estimating a probability distribution over sequences of tokens in A where the set of tokens A is, in general, different from E. Therefore, the problem of tokenization is determined by the forward and backward mappings between Σ' and A To address this problem, we propose 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 for a principled use of tokenizers. Crucially, we prove the necessary and sufficient conditions for tokenizer model to preserve the consistency of statistical estimation of language modeling from data. Additionally, this paper aims to advance the theoretical understanding of existing challenges associated with tokenization, particularly those pertaining to inconsistency, ambiguity, finiteness, and sequentiality. To achieve this, we characterize these known issues through the lens of formal properties of composable maps, such as injectivity, multiplicativity, and bounded variation.
establish general conditions
The outline of the paper is as follows. In $2, we present preliminary notions, including elementary aspects of formal language theory and the concept 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 tokenizer models and establish various results for their use, including the necessary and sufficient conditions for 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 I is a finite, nonempty set of symbols. The set T consists of strings of symbols of length n. The symbol & denotes the empty string of length 0. The union 1 def U I consists of
2

---

Published as a conference paper at ICLR 2025
all finite strings (including e) from the alphabet r. Similarly, denote by ISN the set of all strings from of length less than or equal to N.
String concatenation (.) is an associative product I* x 1 + [ for which e is an identity element. The triple (T", ,) defines monoid, which is, in fact, model of the free monoid on the set r. A language L over an alphabet I' is a set of strings L _ r A language model p is probability distri- bution over [", i.e., p is a function p. I - [0, 1] such that Σyer- p(r) = 1. Language models gen- cralize languages in the sense that the support of language model, i.c., supp(p) = { p(7)) + 0), is language. The definition of a language model as probability distribution on ( is deliberately broad. In particular, note that no compatibility between p and the monoidal structure in I' is assumed."
In NLP, practitioners generally seek estimate language model p from examples of naturally occurring text. Formally, the modeler assumes there exists a true distribution pz over I", and considers multiset of naturally occurring texts (7m J== C D to be samples from p². In its most general form, an estimator of p' is a sequence (Pr J of probability distributions on 1 such that pa becomes closer to p*
increases. We call estimator consistent if the sequence (px J converges pointwise to p²?² 2 More precisely, given probability distribution p" I + [0, 1] and a sequence of distributions {pn: I + [0, I]] we say that {pa} is consistent estimator of pd if and only if, for all strings y E r", the sequence of numbers (7.(7)) converges to the number p" (7).
This notion of consistent estimation is general enough to include many estimation methods, where the (with 1 < S 1)) can depend on various properties of the sample, such as the size M, and may be parameterized by a set of parameters 0. In particular, the relationship between the data } } and the estimator {p.) is determined by the practitioner through the choice of an estimation method, e.g., maximum likelihood estimation (MLE; Lehmann & Casella, 1998). MLE is often used in language model estimation where it corresponds to determining { by minimizing the cross entropy loss on the data. As such, MLE amounts to minimizing the relative entropy, also called the Kullback-Leible divergence, DKL (p" Pn.) between p" and Pa, making {pr} consistent estimator of p*. Note that this requires a stronger form of convergence than the one we use in our framework: if PKL(p" Pn.) - then pn. - p* pointwise (a consequence of Pinsker's lemma). By adopting a weak kind of convergence, our definition is, therefore, compatible with a wide variety of convergence measures while remaining relatively easy check for.
Our definition of tokenizer models will require the use of special kind of map between sets called a stochastic map. The reference Baez & Fritz (2014) contains detailed introduction the category of finite sets with stochastic maps between them. Here, we will extend some of the results in Baez & Fritz (2014) cover the case of countably infinite sets, We assume all sets are countable, either finite or countably infinite. A stochastic map from set X to set Y is function from X to the set of probability distributions on Y. We use
X
to denote a stochastic map from X to Y and the notation x + f(y x) to denote the probability of g E Y in the distribution assigned to X. In other words, stochastic map f: X Y is function
X x Y [0,
(z, 1) + fly x)
for all probability of given x, but it is more accurate think of indexing by x rather than conditioning on x because there is no assumption that the numbers fly x)) can be assembled into a joint distribution on X Y.
satisfying Eyey [vv [
X. The notation [ x)) is evocative of the conditional
Significantly, stochastic maps can be composed. The composition
X
an 7
9f
gf: X defined by
In addition, one could typically require, for instance, that p(y -7)) S min(p(7).p(7)))
FFollowig the usual convention, may denote convergence as {px} p", which is not to be confused
with the notation for functional types (e.g., 53" A"). The context of use should prevent any ambiguity.
3

---

Published as a conference paper at ICLR 2025
gf(z ([=1z)=
E BEY
g(z v)f(y (x).
(I)
Since the sum in equation I contains infinitely many summands, it requires to check that the formula for gf(z x) is finite, and that for each X. gf z) defines probability distribution on Z, both of which follow from the fact that:
Σ Ezf(= x) 2EZ
ΣΣ g(= 1))(((())= BEY
Σ NEY SEZ
Σ
g(z g==0((1)))) vy) x) = Σ fly || =1 VEY
one arranges a stochastic map into an [X] x Y matrix with the f(y z) entry in the z, y position, then every entry is nonnegative and the sum of every row is 1. The computation above shows that composition of stochastic maps realized by matrix multiplication, and that-ever when the matrices are infinite-the row-column dot products are finite, and the result of matrix multiplication is again matrix with nonnegative entries whose rows sum 1. This view makes clear that composition of stochastic maps is associative.
Stochastic maps generalize both ordinary probability distributions and functions. A probability distribution over set X can be represented as stochastic map into X from I-element set, denoted
as 1 def [1), i.c., p: 1 my X. In such cases, the customary notation p(z) can be used without risk shorthand for the more cumbersome p(r 1). An ordinary function f: X - Y can be regarded as a stochastic map X ~ Y by mapping æ to the probability distribution on Y concentrated the singleton (f))) in which case say the stochastic map f is deterministie. For simplicity, when a stochastic map f: X - Y is deterministic, writing y = f(z) means that fl x) 1 and f'v' x) 0 for y' y. Composition generalizes both the composition of functions and the pushforward of a probability function via a function. If p: 1 ~ X is a probability distribution on X and f: X Y is deterministic function, then the composition
of ambiguity
- X -nn Y is a stochastic map fp: ~ Y, which is a probability distribution on Y whose formula is fr(v) = Ezex fly | =) =)p(x 1) = Eusg (w) p(z). That is, fp is just the pushforward of the probability distribution p via the function
For any set X, the identity function on X behaves as an identity for stochastic maps. That is idx: X ~ X is the stochastic map defined by idx(x' x) when x' = x and id (x'((x x) 00 when x' A x. In matrix representation, idx is the identity matrix, and satisfies fidx = f -dyyf for all stochastic maps f: X ~ Y. Stochastic maps also come equipped with natural notions of injectivity and surjectivity. The support of the stochastic map f the union of the support of the distributions f(- z) as ranges over X. A stochastic map f: X ~o Y is injective iff the supports of /( #) and [( x²) are disjoint whenever x & x'. A stochastic map s: for all y E Y, there exists E X such that [y x)) * 0. Injectivity and surjectivity for stochastic maps reduce to their ordinary definitions in the case of deterministic maps.
Y is surjective iff,
2.2 NOTATION AND TERMINOLOGY
We adopt the following notational conventions. We denote the length of a string y E I as lyl- The expression Y' < y denotes the fact that 7 =y= "''-'""""""" > for 7, Y >" E I*, that is, 7 is prefix of y. Alphabets will be denoted by uppercase Greek letters (e.g., r. B). In the context of tokenization, we will be interested in maps between strings of languages over two different alphabets, which we will denote Σ and A. For more intuitive presentation that avoids ambiguity, we reserve the term alphabet for the former and call the latter vocabulary, systematically using the green and violet colors to highlight the respective relation to either of these sets. We denote symbols by lowercase Greek letters, e.g., E Σ and 5 E A, calling them characters in the first case and tokens in the second. Strings will be denoted by bold lowercase Greek letters, e.g., o E Σ and å E A 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 these terminological distinctions are for expository purposes only. From the formal perspective advanced in this paper, we do not assume any inherent privilege of Σ over A, focusing instead on how their respective elements can be mapped into each other, Maps are denoted using the color of their codomains.
4

---

Published as a conference paper at ICLR 2025
When necessary, will distinguish the empty character string eg E Σ" from the empty token sequence ε E A Examples strings and tokens will be written in monospace font (e.g., t, the). There are cases where A n Σ * 0, and it will be necessary to distinguish between concatenation in Σx and A In A", concatenation will be denoted as I. So, for example, if Σ = ht, e} and A = [th, he, e). the expression t-h-e denotes the concatenation in E of the three characters t, and e, while the expression tihe represents the concatenation in A of the two tokens and he. The cases when A >0 * 0 are of sufficient significance that we shall generally avoid using the simple juxtaposition of characters to express concatenation. Therefore, the reader should always interpret th as token in A, and not text in Σ' (written t-h). If further notational clarification is needed, square brackets may be used to represent the concatenation of two texts in E* (and likewise for A*). For example, [t-h] denotes the concatenation of the text t-h with the character
E", Should any ambiguity arise between specific characters and tokens (e.g., E E vs. t E A), it will be explicitly disambiguated whenever there is a risk that context alone is insufficient.
A FORMAL FRAMEWORK FOR TOKENIZATION
As observed in the previous pages, in modern NLP, the problem of tokenization arises from the fact that one seeks to estimate model p* over strings of symbols in one alphabet indirectly, that is, by estimating a probability distribution over strings of symbols on a different alphabet. Therefore, from 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 E* of character strings and the set A of token sequences. In order to estimate p" through q. E* needs to be mapped into and from A The connection between E* and A is thus made through a pair of mappings (T, k) 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 Σ. to A is a pair of stochastic maps T (T, k), respectively called the encoder and the decoder, where the encoder is stochastic map T: > ~y A and the decoder is a stochastic map k: A ~m E*.
Definition 3.1 is deliberately broad, covering any pair of
mappings r and k. 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 T and primarily from the point of view of their composition. In particular, we do not require any specific connection between the alphabet Σ and the vocabulary A, 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- that the samples (am) MM m=1 C E* of naturally occurring texts used for estimation model q can be, in turn, transformed into a model over "n through the map K, such that p = rq can be considered as estimate of the original distribution p². When p is given in the form of ieg, say that p is a tokenized language model.
be mapped into A in such way that the estimated
Despite the potential empirical increase in the predictive performance of model resulting from specific tokenization choices, the soundness of such a procedure is not guaranteed for arbitrary 7 and without further conditions. On the one hand, the notion of estimation in A is not well defined unless there exists a reference distribution q² over A to which the estimator (4x } can converge. On the other, assuming such an estimator is consistent, transforming into a consistent estimator of p* requires a way to map the sequence } into a sequence } that converges to p"
Assuming a reference distribution pd exists on Σ*, one obtains a reference 4 on A simply through the composition (Eq. (I)) with the encoder: q²' rpp In other words, the following diagram of stochastic maps commutes
The distribution q² is just the pushforward of the measure p= along t, which then makes the encoder measure- pressrre-r map between (I*, p²) and (A', .9*).
5

---

Published as a conference paper at ICLR 2025
In the same way, {pr} can be obtained by mapping the sequence {9,} through Defining p; kqg. we obtain the following commutative diagram
N
{
{pa}
So far, none of these requirements imposes conditions on T and x. other than being well-defined mappings between their respective domains and codomains. Notably, the notion of estimation of Tp" is well defined for arbitrary т. However, given consistent estimator {9r} J of q", {kgn} is nor guaranteed to converge to p" without further conditions on To establish such conditions, we will need the following lemmas."
Lemma 3.1. Let {po} be sequence of probability distributions over a countable set that converges pointwise to probability distribution Then lim Exex (P((x) p(x)((())))))))))) 0.
Corollary 3.0.1. Let {pa} be sequence of probubility distributions over countable set X that converges pointwise to a probability distribution p. Then {pa} + uniformly.
Lemma 3.2. Let f be stochastic map from X Y, and {P,} be estimator for probability distribution p on X. Then fPn is an estimator for the probability distribution fp on Y.
In other words, Lemma 3.2 says that stochastic maps preserve the consistency of estimators. Armed with Lemma 3.2, 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 reference probability distribution p' over Σ', tokenizer = (T,K) from E' to A", and consistent estimator {qn} of the image reference distribution q² = TP", the sequence {Rqn] is a consistent estimator of p if and only if KTP" =p"
Theorem 3.1 characterizes precisely when consistent estimator {rn} of q" yields consistent
estimator {p.} of p² after decoding. Based on the fundamental principle expressed Theorem 3.1, propose the following definitions:
Definition 3.2. Given a probability distribution p over Σ", tokenizer T (T, from Σ* to A is consistent with respect to p if we have kTP p.
Definition 3.3. Let be probability distribution over "* and T = (T,K) k) a tokenizer from V to A When RT idg., we say that T exact.
Notice that exact tokenizers are consistent, but a tokenizer that is consistent with respect to distribution is not necessarily exact. Take, for instance, probability distribution p over some set X and x' x',x" X such that p(z') = p(x")) c. Then one can fashion tokenizer for which KT (x) all except (T() = x" and 6oT(x") = x'. Such a tokenizer is consistent with respect without being exact. Consistency with respect to all distributions, however, is the same being exact.
Proposition 3.1. A tokenizer T= (r, from Σ' to A" is exact if and only if it is consistent with respect every probability distribution over Σ".
Our whole setting is quite general and can be represented by the following diagram:
N
{g
{pal
www.mm
"The proofs for all formal results (thcorems, propositions, lemmas) have heen placed the Appendix ($8).

---

Published as a conference paper at ICLR 2025
When this diagram commutes, we have that KTP p for all probability distributions p over Σ", and Theorem 3.1 guarantees that {Pn} + p" when {9n} - q².
Exact tokenizers have special properties. First, if tokenizer (T, k) is exact, then is deterministic over the image of r, because idy. also is. We make this notion formal in the following proposition.
Proposition 3.2. Let = (T, x)) be an exact tokenizer from " to A Then K is deterministic on the support of i.e., K. is deterministic almost everywhere.
The condition KT = idy. means 7 is right inverse (or section) of and &. is a left inverse (or retraction) T. The proof of Proposition 3.2 shows that 7(6 o)) places probability zero on every T.
ô A' such that k(or 8) O. Since is deterministic in this case, it follows that, for an exact tokenizer (T, k), the encoder does not place positive probability mass on a token sequence for more than one text. In other words, T is injective. Additionally, it must be that for each text there is a with x(for 6) = 1. and therefore x is surjective.
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 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 T= (T, we say T has a deterministic encoder (resp. decoder) or is --deterministic (resp. k-deterministic) if (resp. x) is deterministic map. When tokenizer T is both r-deterministic and exact, we have that T is also k-deterministic, and k = over T T(E*). Therefore, in such a we say T is bijective.
Noninjective and Inconsistency. Most commonly used tokenizers have deterministic encoders, including BPE (Sennrich et al., 2016) and WordPiece (Wu et al., 2016), as well as Unigram (Kudo, 2018) when used without regularization. As have seen, 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 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 and deterministic maps. Let p" (ar) = 0.2 and p (02) = (aaa) = 0.4, with p (ax, = for i > 3. For q² = =T", we have, therefore, q² (8)) 0.2, 9- (62) for i > 3, and hence kTp'(ar) = 0 & 0.2, (Tp"(a>) Assuming {qn} is a consistent estimator of q². the pushforward of qu. through K. (i.e., kq₂)) would result in an inconsistent estimation of Notice that the consistency of the tokenizer is relative to the distribution. Relative to a different distribution p in E*, where, for instance, p(σ1) = p( = 0 and p p² otherwise, the tokenizer specified in Fig. I is consistent. Hence the importance for tokenizer to be exact.
and q² (8g) = 0.8, with q" (6,) 0.2 + 0.4, and KTp" (a1) = 0.8 + 0.4.
As shown in $3 and illustrated in Example 4.1, 1,, a fundamental cause of a tokenizer's inconsistency is the lack of injectivity of the encoder т. This is not just theoretical concern. Even if in its abstract specification a tokenizer's encoder may appear be injective, implementation decisions often introduce noninjective behaviors. These include normalizing operations, such as lowercasing, stripping accents, removing punctuation, or uniformizing whitespaces (e.g., Moi Patry, 2023). Regardless of how the core tokenization function is defined, including this preprocessing step part of the tokenizer model results in a noninjective encoding that compromises the consistency of estimators.
Even if text normalization is excluded from the decoding function, it can still happen that 7 is undefined for some elements in Σ, and is, therefore, only a partial function. If the exceptions handled by returning unique distinguished token in A (e.g., an 'unknown' token unk). then T 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
7

---

Published as a conference paper at ICLR 2025
Σ
A*
01
81
D" (01) = 0.2
(61) = 0.2
kTP" (TT"( = 0
2
02
p" (0() = 0.4
(02) = 0
KTP (az) = 0.2
03
63
D' (ox) = 0.4
q' (6a) = 0.8
KTP' (oa) = 0.8
K
:
Figure 1: Example of an inconsistent tokenizer
in the context of NMT (e.g.. Luong & Manning, 2016; Jean et al., 2015), ultimately leading to subword tokenizers as a way of providing "open vocabulary" solutions (Sennrich et al., 2016; Wu al., 2016). Formally, it is enough to inject Σ into A (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. Some open vocabulary models, for instance, limit the size of Σ to the sample's k most frequent symbols, mapping all other symbols to an unk character E (e.g., Wu al., 2016). Understood as a preprocessing step, this operation should not affect r's injectivity. However, the use of copy models (c.g., Luong et al., 2015) that keep track of the original out-of-alphabet symbols to restore them in decoding, violates de facto the tokenizer's 's injectivity, and with it, the model's 's consistency over strings including those symbols.
Regardless of whether all symbols in the training sample are included in E, oft-oo--llhhaber symbols can always be encountered at test or inference time. The recourse to a distinguished unk symbol either in Σ or A must, therefore, be handled such a way that the injectivity of is guaranteed. The use of stochastic (e.g., Mielke & Eisner, 2019) over the restricted domains of out-of-alphabe or vocabuluyy elements could, in principle, provide a novel way of addressing this problem in agreement with consistency concerns.
Noninjective k and Ambiguity. Whenever is noninjective, the tokenizer introduces ambiguity in the model because more than one token sequence is mapped into a unique text. In bijective tokenizers, decoding is injective over the encoder's image, thus preventing ambiguity in principle. However, in practice, whenever 7 r(E*) is proper subset of A it may happen that the probability mass placed by the estimated language model outside the image of T is nonzero, reintroducing ambiguity into the model (ef. Example 8.1 in the Appendix for an elementary illustration). This ambiguity is, however, spurious because T was assumed to be deterministic, and hence the ambiguity does not originate from the reference distribution p², but is side effect of the estimator. An obvious source of spurious ambiguity lies in the fact that consistency is property defined in the limit. As a consequence, for any 8 E A gr (6) can and will generally differ from q- (8)) 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 A While spurious ambiguity has been identified among the motivations for introducing subword regularization (Kudo, 2018; Provilkov et al.. 2020), it is often overlooked or disregarded, despite its potential nonnegligible effect on estimation (Cao & Rimell, 2021) although mostly in the case of "strongly out-of-domain evaluation sets" (Chirkova et al., 2023).
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 x must be noninjective for the model to preserve the consistency of estimators. However, the ambiguity thus introduced not spurious in that is deliberately designed for statistical purposes. In current tokenization practices, the main reason for the introduction of stochastic ambiguity is regularization (Kudo, 2018; Provilkov et al., 2020). The claim is that, by exhibiting different token sequences corresponding
For a tokenization- free alternative to the O0V problem, see, for instance, Xue et al. (2022) and Clark et al. (2022), who also offer good overview of existing approaches this problem.
8

---

Published as a conference paper at ICLR 2025
to the same text during training, model increases its capability to handle text compositionality as well as its robustness to noise and tokenization errors. However, one could also conceive of stochastic tokenizer where the possible images of text reflect the objective probabilities of all linguistic ambiguities potentially affecting it (e.g., an icecream, an anicercream, a aincercrream as three possible token sequences for the text: -e--cce---r---aamm) This would require, however, to enhance tokenizers with linguistically motivated segmentation (see, for instance, Bostrom & Durrett, 2020; Hofmann et al., 2021; Gow-Smith al., 2022; Beinborn & Pinter, 2023).
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 language is spread 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 KQn, for single text a Σ* requires summing over all its preimages 5 under K, for which gn (8) > 0, following the composition of stochastic maps presented in the previous section (Eq. (I)). However, such an operation can be computationally challenging because it can imply summing over large
infinite number of terms. For different strategies to address this challenge, see van Merriënboer et al. (2017); Buckman & Neubig (2018); Grave et al. (2019); Hannun al. (2020); Cao & Rimell (2021); Vieira et al. (2024).
5 COMPUTATIONAL CONCERNS: FINITENESS AND SEQUENTIALITY
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 finiteness and sequentiality.
Multiplicativity and Finiteness. Definitions 3.1 to 3.3 are general enough to allow for many kinds of encoding and decoding functions, including uncomputable ones; see Example 8.2 in the Appendix for an example. However, even when 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 that define 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 assess the tractability not only of r and K, but also of their composition KT.
We have seen that when tokenizer model is exact, is a section of K, or equivalently, is injective. It follows that, for any a E Σ', т concentrates the probability mass on only a subset of A.. This property can help reduce computational costs by restricting the sums to just those subsets. However, without further constraints, those subsets can still be infinite. For this reason, we introduce the following definitions.
Definition 5.1. We say a tokenizer model T= (T, x) is multiplicative if its decoder x. respects the concatenation products, i.e., if =(")=)=008(
Definition 5.2. We say the kernel of a multipiccative tokenizer's decoder e is trivial if is maps nonempty token sequences to nonempty token sequences (i.e., if 5 & ca then kc()) # ex).
The most commonly used tokenizers, including BPE, WordPicce, and Unigram, Notice that, for a kernel of multiplicative tokenizer's 's decoder to be trivial, it is enough that k(ā) # ex for any 8 A. This implies that token sequences do not include special tokens that erased during decoding. Importantly, when a multiplicative tokenizer's 's decoder has a trivial kernel, a decoded text cannot be shorter than the token sequence from which has been decoded. This simple observation guarantees that the number of preimages of a text under k is finite. More precisely, we have the following proposition.
multiplicative.
Proposition 5.1. Let T = (T) be a multiplicative tokenizer model whose decoder's 's kernel is trivial. For any d E A k()) =
18] I |o...
Corollary 5.0.1. Let T = (r) v)) he multiplicative tokenizer model whose decoder's 's kernel is trivial. Then for any text o, the set K." (o) 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 text of length n has length less than or equal to So the

---

Published as a conference paper at ICLR 2025
number of elements in i x= (o), and hence also the support of for any given E' when (T) is exact, is bounded by Ei= | Since this bound is exponential in n. the exact or approximate computation of tokenizer's '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 of tokenizer model (that is, of the composition k7) should be at most linear in the length of the input text. By placing all the probability mass on one token sequence, KT in exact deterministic tokenizers, such BPE and WordPiece, can be computed in linear time long as T and x can be computed in linear time. However, rigorously handling spurious ambiguity still represents a challenge these cases. In uollow-up work. Vieira al. (2024) exploit the finiteness of k k= (ar) to introduce both exact and approximate algorithms for converting token-level language models to character-level ones, assuming x prefix monotone, i.e., 8' 3 d = x(6') 3 n()), a weaker condition implied by multiplicativity which is crucial in autoregressive models."
Bounded Variation and Sequentiality. Finally, even though multiplicativity ensures that the length of every preimage of (a) ( is bounded by the length of a, the latter may still be unbounded. In prac- tice, the bounded character of tokenization is secured externally by fixing a hyperparameter that artifi- cially limits the length of input texts. However, boundedness can be addressed as an internal property of a tokenizer. For this purpose, we introduce the following definitions, adapted from Berstel (1979). Definition 5.3. The (left) distance between two strings 7,7' E I is the number:
1/, det + - 2/ A/1. where Y A o is the longest common prefix of and Definition 5.4. A functinn f: I BB has bounded variation if and only if 2 0. 3C 2
7,76 E Er",lly Il, & = 1 < Ck-
The importance of Definition 5.4 is that, following Choffrut's 's (1979) theorem, whenever f preserves rational sets, if f has bounded variation, then it is subsequential, that is, it can be realized by a deterministic finite-state transducer enhanced with function over terminal states (cf. Definition 8.4 in the Appendix). Since subsequential functions are closed under composition (Berstel, 1979, prop. IV.2.5), for to be subsequential, it is enough that both and x are. Given that most commonly used tokenizers are multiplicative, the following result is significant.
Proposition 5.2. If a function f: - + B" is multiplicative then it has bounded variation.
However, in the context of tokenizers, multiplicativity concerns only the decoder (a multiplicative encoder T is not a desirable feature for a tokenizer), thus shifting the focus towards the encoder r. The "maximal munch" approach (Reps, 1998; Palmer, 2000) adopted by WordPiece, for instance, itera- tively 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 A under T, and is, therefore, subsequential (cf. Song et al., 2021, for a realization of WordPiece by a finite-state transducer). Moreover, assuming specific conditions
the structure of the list of rules "merges", Berglund & van der Merwe (2023) and Berglund et al. (2024) proposed an algorithm for constructing deterministic finite automata realizing BPE's encoder, thus suggesting that, under such conditions, BPE is also subsequential.
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 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, finiteness, and sequentiality, by characterizing the latter through formal properties of composable maps such as injectivity, multiplicativity, or bounded variation. 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.
Note that Vieira et al. (2024) call "non-crasing" the fact that x has trivial kernel.
10

---

Published as a conference paper at ICLR 2025
7 ACKNOWLEDGEMENTS
The authors thank Saced Zakeri for pointing out an interesting interplay between a general fact about the Banach spaces L (X) for any measure space X and the fact that for the little (? spaces, the e norm is smaller than the 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.
REFERENCES
Ben Athiwaratkun, Shiqi Wang, Mingyue Shang, Yuchen Tian, Zijian Wang, Sujan Kumar Gonu- gondla, Sanjay Krishna Gouda, Rob Kwiatowski, Ramesh Nallapati, and Bing Xiang. Token alignment via character matching for subword completion, 2024.
John C. Baez and Tobias Fritz. A Bayesian characterization of relative entropy. CoRR, abs/1402.3067, org/abs/ 402. 3067.
2014. URL http::ttttaaae
Lisa Beinborn and Yuval Pinter. Analyzing cognitive plausibility of subword tokenization. In
Proceedings of the 2023 Conference on Empirical Methods Natural Language Processing, pp. 4478-44888 Singapore, December 2023, Association for Computational Linguistics. doi: 10. 18653/v1/2023.emml 16668/112223.emmlpmmii..777 URL httttss:/aaaaaathollllooooooo
or org/ momlp-main. 272.
Martin Berglund and Brink van der Merwe. Formalizing BPE tokenization. In Proceedings of the 13th International Workshop Non-Classical Models of Automata and Applications, Famagusta, North Cyprus, 18th-19h September, 2023, volume 388 of Electronic Proceedings in Theoretical Computer Science, pp. 16 27. Open Publishing Association, 2023, doi: 10.4204/EPTCS. 3.8..4
Martin Berglund, Willeke Martens, and Brink van der Merwe. Constructing BPE tokenization DEA. In Implementation and Application of Automata, pp. 66-78, Cham, 2024. Springer Na- ture Switzerland. ISBN 978-3-031-711122 URL attps://linke. springer com/ chapter/10. 1007
Jean Berstel. Transductions and Context- Languages. Teubner, Stuttgart, Germany, 1979.
Kaj Bostrom and Greg Durrett. Byte pair encoding is suboptimal for language model pretraining. In Trevor Cohn, Yulan He, and Yang Liu (eds.), Findings of the Association for Computational Linguisties: EMNLP 2020, pp. 4617-4624 Online, November 2020. Association for Computational Linguistics. doi: 10. 10.18653/v112022 /20.:////2......nnnnne/mm////// findinng--emll-14444 2020. Findings-emnlp 414.
URL
hatp//acccanooooggyyyoooo org/
Jacob Buckman and Graham Neubig. Neural lattice language models. Transactions of the Association for Computational Linguistics, 6:529-541, 2018. doi: 20.11622aalaa_00033 URL https: / //aclanthology..ooo org /og////-//-- 1036.
Kris Cao and Laura Rimell. You should evaluate your language model on marginal likelihood over tokenisations. In Marie-Francing Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih (eds.), Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 2104-2114, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics. doi: //aclanthology.com org/ emnlp-main. 161.
URL https:
Nadezhda Chirkova, Germán Kruszewski, Jos Rozen, and Mare Dymetman. Should you marginalize over possible tokenizations? In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Proceedings of the 61 Annual Meeting of the Association for Computational Linguistics (Volume
2: Short Papers), pp. 1-12, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10.18653/v
URL https: htt.ttps::/aclaaneeeeet http///aaaaaatttocceoca/o org/ 2223. acl-short.
C. Choffrut. A generalization of Ginsburg and Rose's characterization of G-S-M mappings. In Automata, Languages and Programming. Springer Berlin Heidelberg, 1979.
Jonathan H. Clark, Dan Garrette, Iulia Turc, and John Wieting. Canine: Pre-training an effi- cient tokenization-free encoder for language representation. Transactions of the Association for Computational Linguistics, 10:73-911 2022. doi: 10. 162/tacl a 00448. URL https: // //aalaanthllog.orr/22222/ 1tw.122...acl11...11 t.c

---

Published as a conference paper at ICLR 2025
Mathias Creutz and Krista Lagus. Unsupervised discovery of morphemes. In Proceedings of the ACL-02 Workshop on Morphological and Phonological Learning, pp. 21-30. Association for Computational Linguisties, July 2002. doi: 10.3115/111664.111
URL https://
aclanthology. org/We2-0603.
Shuoyang Ding, Adithya Renduchintala, and Kevin Duh. A call for prudent choice of subword merge operations neural machine translation. Mikel Foreada, Andy Way, Barry Haddow, and Rico Sennrich (eds.), Proceedings of Machine Translation Summit XVII: Research Track, pp. 204-213, Dublin, Ireland, August 2019. European Association for Machine Translation. URL http://acaantooooo..orr//////
Miguel Domingo, Mercedes García-Martinez, Alexandre Helle, Francisco Casacuberta, and Manuel Herranz. How much does tokenization affect neural machine translation? In Computa- tional Linguistics and Intelligent Text Processing, pp. 545-554, Cham, 2023. Springer Na- ture Switzerland. ISBN 978-3-031-24337-0. URL htt:::/iinnk..rrc www.innnn.eeeeeeeeeeooomm/ooeeee chapter/ 10. 1007/978-3-03111 0000--3333-1223--01113 24337---388...
Takuro Fujii, Koki Shibata, Atsuki Yamaguchi, Terufumi Morishita, and Yasuhiro Sogawa. How do different tokenizers perform downstream tasks in scriptio continua languages?: A case study in Japanese. In Vishakh Padmakumar, Gisela Vallejo, and Yao Fu (eds.), Proceedings of the 61st Annual Meeting of the Association for Computational Linguisties (Volume 4: Student Research Workshop), pp. 39-49, Toronto, Canada, July 2023, Association for Computational Linguistics. URL https: /acl aat.aaaaaanooooyyyyoooooooooooaa org/ 2023. acl-srw.5
doi:
Philip Gage. new algorithm for data compression. C Users Journal, 12(2), 1994. ISSN 0898-9788.
URL https://dl. acm. htrg/doi/abb///// 55555/177919 177914.
Mario Giulianelli, Luca Malagutti, Juan Luis Gastaldi, Brian DuSell, Tim Vieira, and Ryan Cotterell. On the Proper Treatment of Tokenization in Psycholinguistic. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, November 2024. doi: 10. https://aclanthologg org/ emnlp- main. 1032/.
1032. URL
Edward Gow-Smith, Harish Tayyar Madabushi, Carolina Scarton, and Aline Villavicencio. Im- proving tokenisation by alternative treatment of spaces. In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang (eds.), Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 11430-11444 11443, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguisties. doi: 10.1 1663////2222..mmppmmma https://aclantthol.og org/2022.22222 emnlp-main.
URL
Edouard Grave, Sainbayar Sukhbaatar, Piotr Bojanowski, and Armand Joulin. Training hybrid language models by marginalizing over segmentations. In Anna Korhonen, David Traum, and Lluis Mårquez (eds.), Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 1477-1482, Florence, Italy, July 2019. Association for Computational Linguistics. doi: 10.18653/v1/P19- 1143. URL https: h/clantholll htt.aaaatoooooooooooooooo org/p19-114/
Jin Guo. Critical tokenization and its properties. Computational Linguistics, 23(4):569-596, 1997. URL https://aclanthhlogg 001.3//-40/////44444
Awni Hannun, Vineel Pratap, Jacob Kahn, and Wei-Ning Hsu, Differentiable weighted finite-state transducers, 2020. URL htttts:///aatttt httpp/////aaxxx.oog/bb////////// org/abs/2010 01003.
Valentin Hofmann, Janet Pierrehumbert, and Hinrich Schützze Superbizarre is not superb: Derivational morphology improves BERT's interpretation of complex words. In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli (eds.), Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 1 11th International Joint Conference on Natural Language Processing (Volume Long Papers), pp. 3594-3608, Online, August 2021. Association for Computational Linguistics. doi: 10.18653/v1/2003 1a URL org/2021 acl- acl-alcg.............omoaooolm.. .79.
279.
Jue Hou, Anisia Katinskaia, Anh-Duc Vu, and Roman Yangarber. Effects sub-word segmentation performance of transformer language models. In Proceedings of the 2023 Conference
12

---

Published as a conference paper at ICLR 2025
Empirical Methods in Natural Language Processing, pp. 7413-7422 Singapore, December 2023. Association for Computational Linguistics. doi: 10.18653/w112023. hatp:223mmmmmmmmmmnmmm 459. URL https: // laacllantologg.orgg///o
eeinl-mmaie 459.
Sébastien Jean, Kyunghyun Cho, Roland Memisevic, and Yoshua Bengio. On using very large target vocabulary for neural machine translation. In Chengqing Zong and Michael Strube (eds.), Proceedings of the 53rd Annual Meeting of the Association for Computational Linguisties and the 7th International Joint Conference on Natural Language Processing ( Volume I: Long Pupers), pp. 1-10, Beijing, China, July 2015. Association for Computational Linguistics. doi: 10.3115/vll P15-1001. URL https: htttps://aclaathoology org org/P15-1801
Daniel Jurafsky and James H. Martin. Speech and Language Processing: An Introdaction Natural Language Processing, Computational Linguistics, and Speech Recognition. Third edition edition, 2024. URL https: /twp::///bb...
/web. berebbsttane stanford. ccuu/-jurafssy/slppp
Carina Kauf and Anna Ivanova. A better way to do masked language model scoring. In Anna Rogers, Jordan Boyd-Grabel and Naoaki Okazaki (eds.), Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 925-935, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 1220533///2222allsssss URL https: wclanthology......o .rgg/..rr////.. 2023.02233322 acl who.t..shr..88
Philipp Koehn, Hieu Hoang, Alexandra Birch, Chris Callison-Burch, Marcello Federico, Nicola Bertoldi, Brooke Cowan, Wade Shen, Christine Moran, Richard Zens, Chris Dyer, Ondřej Bojar, Alexandra Constantin, and Evan Herbst. Moses: Open source toolkit for statistical machine translation. In Sophia Ananiadou (ed.), Proceedings the 45th Annual Meeting of the Association for Computational Linguistics Companion Volume Proceedings of the Demo and Poster Sessions, pp. 177-180, Prague, Czech Republic, June 2007. Association for Computational Linguistics. URL http:::////llathhoogyyy wwwpooooyyyyogg//7-22200 org/P07-20055
Taku Kudo. Subword regularization: Improving neural network translation models with multiple subword candidates. In Iryna Gurevych and Yusuke Miyao (eds.). Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 66-75, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 10. 10.18653/v1/P18 1007. URL httpshtt//caaaatho//////////// http:///llaanttoooooo.o.o//////a 1001.
Erich L. Lehmann and George Casella. Theory of Point Estimation. Springer Texts in Statistics. Springer, 2nd edition, 1998. ISBN 978-0-388 278-0-387-98502-2.
Minh- Shan-TThng Luong and Christopher Manning. Achieving open vocabulary neural machine trans- lation with bybrid word-character models. In Katrin Erk and Noah A. Smith (eds.), Proceedings of the 54th Annual Meeting of the Association for Computational Linguisties (Volume Lonng Pa- pers), pp. 1054-1063, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 20118853/11/11- 1100. URL https: h/tp://aaaaaallooo////o/ org/P16-1100.
Thang Luong, Ilya Sutskever, Quoc Le, Oriol Vinyals, and Wojciech Zaremba. Addressing the rare word problem in neural machine translation. In Chengqing Zong and Michael Strube (eds.), Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing ( (Volume 1: Long Papers), pp. 11-19, Beijing, China. July 2015. Association for Computational Linguistics. doi: 10.3115/v1/ P15-1002, URL hwwph:ttps//tm htttts::/aclanthhllol
org/ P155 1002.
Sabrina J. Mielke and Jason Eisner. Spell once, summon anywhere: A two-level voca-vocy language model. AAAI' 19/AАA 19/EAA/' AAAI Press, 2019. ISBN 978- 1-57735--79---1- doi: 10.1669/aai..v33h00 333016843. URL htt.s:tts::///t //tii//dooooo//// http:///ooooog////////// org/10 0. 1609/aaai v33101 13333111111111......
Sabrina J. Mielke, Zaid Alyafeai, Elizabeth Salesky, Colin Raffel, Manan Dey, Matthias Gallé, Arun Raja, Chenglei Si, Wilson Y. Lee, Benoît Sagot, and Samson Tan. Between words and characters: A brief history of open- modeling and tokenization in NLP. CoRR, abs/21 12. 12500088,, 2021. URL httttps:/aaxxvv.rreeee
10508.
Anthony Moi and Nicolas Patry. HuggingFace's Tokenizers, April 2023, URL https: //githgtt com/huggingfface/ www.aa/tetootsss.......
13

---

Published as a conference paper at ICLR 2025
Piotr Nawrot, Jan Chorowski, Adrian Lancucki, and Edoardo Maria Ponti. Efficient transformers with dynamic token pooling. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Proceedings of the 6l Anmual Meeting of the Association for Computational Linguistics (Volume I: Long Pupers), pp. 6403-6417, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10. 10.18866/11/2223.ac--ooggg
URL https: https://acllanthologs org//022
acl-long. 353.
David D. Palmer. Tokenisation and sentence segmentation. In Handbook of Natural Language Processing, chapter 2, pp. 24-25, Marcel Dekker, 2000.
Gabriel Poesia, Oleksandr Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. Synchromesh: Reliable code generation from pre-trained language models, 2022.
Ivan Provilkov, Dmitrii Emelianenko, and Flena Voita. BrF-dropout: Simple and effective subword regularization. In Dan Jurafsky, Joyce Chai, Natalic Schluter, and Joel Tetreault (eds.), Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 1882-1892, Online, July 2020. Association for Computational Linguistics. doi: 10. 1/2.:////222..clllmoo 170. URL https: /acps//hllaantoooyo...oooo wttp:///........mm........mm
acl-main. 170.
Nived Rajaraman, Jiantao Jiao, and Kannan Ramchandran. Toward a theory of tokenization in LLMSs, 2024.
Thomas Reps. "Maximal-muneh" tokenization in linear time. ACM Trans. Program. Lang. Syst., 20(2)259-273, mar 1998. ISSN 0164-0925. doi: 10.1 10.1145/77333.2266663 URL https://doi. org/10. 11 1145/276393, 276394.
Julian Salazar, Davis Liang, Toan Q. Nguyen, and Katrin Kirchhoff. Masked language model scoring. In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel Tetreault (eds.), Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 2699-2712, Online, July 2020. Association for Computational Linguistics. doi: 10.18653/w1/2022.ac/ main... URL https://aclanthol..og orrp:///lloyy.o//222222 acl m20.
Craig W. Schmidt, Varshini Reddy, Haoran Zhang, Alec Alameddine, Omri Uzan, Yuval Pinter, and Chris Tanner. Tokenization more than compression, 2024.
Mike Schuster and Kaisuke Nakajima. Japanese and Korean voice search. In 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5149-5152, 2012. doi: 10.1 109/IC/SSP..212..222222 2.689099.
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. In Katrin Erk and Noah A. Smith (eds.), Proceedings of the 54th Anmual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 1715-1725, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10. 18653/v1//16 1162 URL https: / www.thooooc.cc.....ccm.oomo org/P16-
Xinying Song, Alex Salcianu, Yang Song, Dave Dopson, and Denny Zhou. Fast WordPiece tokenization. In Marie-Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih (eds.), Proceedings of the 202I Conference on Empirical Methods Natural Language Processing, pp. 2089-2103, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguisties. doi: 10. 18653/v112021 wenlp-main.neee URL https://aclanthol orrgattohooooyooo/22211111
org.2021. emnlp-main. 160.
Omri Uzan, Craig W. Schmidt, Chris Tanner, and Yuval Pinter. Greed is all you need: An evaluation of tokenizer inference methods, 2024.
Bart van Merriënboer, Amartya Sanyal, Hugo Larochelle, and Yoshua Bengio. Multiscale sequence modeling with a learned dictionary, 2017. URL https:://rxttt http://axii..og/rbb//////a
00762.
Tim Vieira, Ben LeBrun, Mario Giulianelli, Juan Luis Gastaldi, Brian DuSell, John Terilla, Timothy J. O'Donnell, and Ryan Cotterell. From Language Models over Tokens Language Models over Characters, 2024. URL pnttps://arxiee
Junxiong Wang, Tushaar Gangavarapu, Jing Nathan Yan, and Alexander M. Rush. MambaByte: Token-free Selective State Space Model, 2024. URL https:tt////.i.....t// orgp//i..or///bobo wrgg/b//////ggg 13660.
14

---

Published as a conference paper at ICLR 2025
Yonghui Wu, Mike Schuster, Z. Chen, Quoe V. Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, Jeff Klingner, Apurva Shah, Melvin Johnson, Xiaobing Liu, Lukasz Kaiser, Stephan Gouws, Yoshikiyo Kato, Taku Kudo, Hideto Kazawa, Keith Stevens, George Kurian, Nishant Patil, Wei Wang, Cliff Young, Jason R. Smith, Jason Riesa, Alex Rudnick, Oriol Vinyals, Gregory S. Corrado, Macduff Hughes, and Jeffrey Dean. Google's neural machine translation system: Bridging the gap between human and machine translation. ArXiv, abs//609.00 44, 2016. URL https://appt semanti ticaanttccccarrrr Orgg/CrppsIDD. 3603249..
Linting Xue, Aditya Barua, Noah Constant, Rami AI-Rfou, Sharan Narang, Mihir Kale, Adam Roberts, and Colin Raffel. ByT5: Towards token-free future with pre-trained byte-to-byte models. Transactions of the Association for Computational Linguistics, 10:291-306, 2022. doi: 10.1 10.1162/tac__a000A URL https: https://aclaattheee
org/ /02..2222222222 tacl-1.11 17.
Vilém Zouhar, Clara Meister, Juan Gastaldi, Li Du, Mrinmaya Sachan, and Ryan Cotterell. To- kenization and the noiseless channel. In Anna Rogers, Jordan Boyd-Graber,, and Naoaki Okazaki (eds.), Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 5184-5207, Toronto, Canada, July 2023a. Asso- ciation for Computational Linguistics. doi: 10.18633w1/20233cclHorrr //aclanthology.orggee http:y/..rrg/2333/ acl- 284.
URL https:
Vilém Zouhar, Clara Meister, Juan Gastaldi, Li Du, Tim Vieira, Mrinmaya Sachan, and Ryan Cotterell. A formal perspective on byte-pair encoding. Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Findings of the Association for Computational Linguistics: ACL 2023, pp. 598-6188-988 Toronto, Canada, July 2023b. Association for Computational Linguistics. doi: 10.18653/v 1/2023 findings-acll acl.38. URL https: //walaaaaallogyy......... org 2023. findings-acl. 38.
15

---

Published as a conference paper at ICLR 2025
8 APPENDIX
8.1 PROOFS
Lemma 3.1. Let {po} be sequence of probability distributions over a countable set X that
converges pointwise to probability distribution Then lim Exex (P,(x) p(z) = 0.
Proof. Fatou's s lemma applied to X with the counting measure implies that for any sequence of nonnegative functions [fn] on X.
Σ
lim inf fn(x) S lim inf En((t) n
10000
ZEX
We will apply this to /n == Pr +
Pn pl. First, note that since lim (x) = p(æ), we
have lim =000 (x() = p(x) + p(x) = 2p(x:) the left hand side of equation 2 becomes Exex 2p(x) = 2. Therefore,
2 < lim inf n-
fn(x)
(3a)
zEX
lim inf
Σ
Pa(x) + p(x) (pn(())) p((x)
(3b)
2EX
lim inf
Σ
Pm(x)) +
Σ p(x)= - -E (Pm(x)) - pp())
(3c)
#EX
xEX
xEX
lim 1 +1
(pn(x) p(x))
(3d)
vEX
= 2 - --lmssp
Pn (3r) -p(x))/-
(3e)
n
xEX
follows that limsup,--er Exsx (2(x) - p(x)) S O. so limn- Exex (Pn(x)
Corollary 3.0.1. Let }Pa} be a sequence of probability distributions over countable set X that converges pointwise a probability distribution p. Then {pa} p uniformly.
Proof. Since the sum of nonnegative numbers is always greater than any particular term in the sum and
limo ExEx x (px p(x)] = 0, we can conclude that the sequence {Pa} + uniformly. O
Lemma 3.2. Let f be stochastic map from X Y, and {pu} be estimator for probability distribution p on X. Then fPn is an estimator for the probability distribution fp on Y.
Proof. Fix Y. We will show that (fP + fp(v). By Lemma 3.1, we have that lim, ΣxEx Pn (x) p (x)) 0. Therefore,
lim (P) fp(1)1 lim n00
Σ fly x))x(x) ESl
fly x)p(x)
(4a)
n-
FE
Tex
lim ~
Σ fly x) Ip (x) - p (x)
(4b)
zeX
lim
Σ
Pn (z) - px))
(4c)
n xEx
0.
(4d)
Theorem 3.1 (Fundamental Principle of Tokenization). Given a reference probability distribution p" over Σt, tokenizer T = (T, from E' to A and consistent estimator {qn} of the image reference distribution q² = rp". the sequence {mqn} is a consistent estimator of p" if and only if kTP" p'.
16

---

Published as a conference paper at ICLR 2025
Proof. By hypothesis, {qn} q" and by definition q" =T'". By Lemma 3.2, applying both sides, we have that {kqM) + sig" and so
{kqa} + KTP".
Therefore, if KTP" =p" we have (kqa) + pr. Conversely, if {kqm) + p¹ we have both {Nam - p" and {Riqg) KTP" and by the uniqueness of limits, KTP" = p
Proposition 3.1. A tokenizer T = (T, from E" to A is exact if and only if is consistent with respect to every probability distribution over Σ*
Proof. Exact means кт = idg- hence KTP for every probability distribution on Σ". To prove the other direction, suppose that Kту = p for every p on Σ". Fix an arbitrary point mass distribution on Σn concentrated on a. So Po (ar = 1 and (o = 0 for any o' # a. By hypothesis, Po = KTPa. Apply to to get of Pe via к7, says Po (xT((r)) Since Po takes the value at only one point, it follows that the argument (o) = a. Since was arbitrary, we conclude that KT idg-, i... the tokenizer (T, K) exact.
Σ* Let Per be the
( The right hand side, as the pushforward
Proposition 3.2. Let (T, be exact tokenizer from Σ- to At. Then is deterministic the support Tf T, i.e., i. is deterministic almost everywhere.
Proof. Assume (T, R) is exact, i.c., AT ids-, and let ""
Since EsEs. 7(6 σ) 1 and kT = idy- (o o) 1. We obtain:
Σ
76 or) - kT(()
(5a)
Σ
7(6 o) Σ
x(o 88) o)
(5b)
SEA*
SEA'
Σ
7(6 () - <(a 8)T(6 ()
(5c)
БEΛ*
Σ
7(6 o) x(a 8)).
(5d)
Since Eq. (5d) is sum of nonnegative terms that equals zero, each terms must be zero. It follows that T( o) > for some (c.g.: is in the support of r) then then x-x(o 8) = + x(o 8) 1.
From which it follows that
{1 if foo==
x(O' (8)
( i to."
x) be a multiplicative tokenizer model whose decoder's kernel is trivial. Proposition 5.1. Let = (T, For any ó E A k()) = o [6| < |o].
Proof. We reason by induction. Let (8) m and |o| n. The property is true when m since 1 is the minimun length of any possible image of к. Assume it is true for m = k and let 81.... 16100+11 Then x()) x( 1dx)-Kt -x))x(())11) dr.... -, -T where k(0 0rt1 -rts- Since 2 lo and 1, we have that r + k 1.
Proposition 5.2. If function f: 1 + 3 is multiplicative then it has bounded variation.
Proof. Assume f is multiplicative and let l be given. Suppose 7, E r satisfy 2' s k. Let
Ck
max
(
"E"" ET **
17

---

Published as a conference paper at ICLR 2025
Write 7 and 7 y =::0////--- and v/ 7 7 "y" Notice that || nn'| and look at (l((r).((>))
1>"1 + lnd 1 k.
((T()) I15(Y A o Y²), ; f(7 >
(6a)
lIf(T - --)--f(""" f("")'"))))))))))")) f(r f()"))
(6b)
-II(("",
(6c)
+((7")+15(7"))
(6d)
S CCh
(6e)
8.2 EXAMPLES
Example 8.1. Take, for instance, bijective tokenizer such BPE or WordPiece, with performing concatenation of the token maps in the usual way. Let Σ = et and A = ht, th, he). In this minimal configuration, it is easy to see that k(tihie) However, BPE or WordPiece being bijective tokenizers, can only map the value of k. to at most one of the latter's 's arguments. say T (t--h-e) thie. We then have that T (s(t he)) tihe (and likewise for tihle). If the estimator happens to place nonzero probability mass on any of the latter two token sequences, the model will exhibit spurious ambiguity.
x(tihe) <(thie)
t-h-e E E"
Example 8.2. Let E = A {0, }, and define Tanc (Tancy Krnne) deterministic model in the following way:
oil, if a describes a valid Turing Machine followed by an input for which it halts. otherwise.
i E, or, otherwise, where d.
(o)
Kunc (0)
o 0
Significantly, Tune is not only well-defined but also exact and therefore consistent for any language model over E* However, Tune is famously uncomputable function, and hence Tune is uncomputable tokenizer.
8.3 DEFINITIONS
Definition 8.1. A (left) sequential transducer a 6-tpple (Q,T,B,i,o,)) where:
is set of states an input alphabet is an output alphabet an initial state is an input "next state" function
B
iEQ
o: DDDCxxTOQ
*:
DD Q x
an output function.
Definition 8.2. A function f: [* B² is sequential if is realized by sequential transducer, i.e., ((>) = (i 7)
Definition 8.3. A (left) subsequential transducer is 7-tuple H. where: is a sequential transducer is terminal function.
(Q, i,
p: Q B
Definition 8.4. A function f: D + B is subsequential if is realized by subsequential transducer (Q, T, B, i, o, *, P), iee, f()) = ((ix))p(ion))
18


Reviews:
[{"review_id": "mGyUM7cIdu", "reviewer": "Reviewer_yPjZ", "summary": "Disclaimer: I previously reviewed an earlier version of this paper during its submission to NeurIPS 2024.\n\nThis 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).", "questions": "Comments:\n- 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).\n- 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/)).\n- 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.\n\nTypos:\n- Line 120: \"distributions\" -> \"distribution\"\n- Line 158: \"equation equation 1\" -> \"equation 1\"\n- Line 205: \"this\" -> \"these\"\n- Line 459: \"complexity a tokenizer model\" -> \"complexity of a tokenizer model\"", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper has several strengths:\n\n- 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.\n- The application of stochastic maps to tokenization is novel.\n- The presentation is excellent; the writing is clear and overall easy to follow.", "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mtuCyKHmKB", "reviewer": "Reviewer_pg9p", "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.", "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?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "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.", "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9mGyWG0Tdo", "reviewer": "Reviewer_rVcs", "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.", "questions": "I am unsure if I am not a relevant reviewer for this paper or if the paper is too foundational for the conference.", "limitations": "", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "— Theoretical position paper is from a foundational perspective, and mathematically justified analysis is introduced; strict definitions and notation conventions are presented.", "weaknesses": "It's still unclear how to apply this knowledge to practical issues and better tokenizers for LLMs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bzLg0e4iV9", "reviewer": "Reviewer_btSn", "summary": "The paper investigates into the tokenization process for language modelling from a theoretical viewpoint. \n\nThe 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.", "questions": "Can the authors further clairify the connection between 3.1 and the rest of the paper please?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "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:\n- Define propery the consistency from analysis viewpoint\n- The propoerty of encoder and decoder and connect them with the problem of inconsistency and ambiguity", "weaknesses": "The connections between the derived properties/theorems and the NLP practice/problems are not strong. My arguments are stated as the following:\n- 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.\n- 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\".\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)