Language Models over Canonical Byte-Pair Encodings
Authors: Tim Vieira
Tianyu Liu
Clemente Pasti
Yahya Emara
Brian DuSell
Benjamin LeBrun
Mario Giulianelli
Juan Luis Gastaldi
Timothy J. O'Donnell
Ryan Cotterell
Venue: ICML 2025 poster (2025)
Keywords: tokenization
probabilistic inference
structured prediction
constrained generation
Primary area: deep_learning->large_language_models
TL;DR: Tokenized language model place nontrival probability on invalid, noncanonical encodings; fixing these mistakes with our new methods improves helps!

Abstract: Modern language models represent probability distributions over character strings as distributions over (shorter) token strings derived via a deterministic tokenizer, such as byte-pair encoding. While this approach is highly effective at scaling up language models to large corpora, its current incarnations have a concerning property: the model assigns nonzero probability mass to an exponential number of *noncanonical* token encodings of each character string—these are token strings that decode to valid character strings but are impossible under the deterministic tokenizer (i.e., they will never be seen in any training corpus, no matter how large). This misallocation is both erroneous, as noncanonical strings never appear in training data, and wasteful, diverting probability mass away from plausible outputs. These are avoidable mistakes!  In this work, we propose methods to enforce canonicality in token-level language models, ensuring that only canonical token strings are assigned positive probability. We present two approaches: (1) canonicality by conditioning, leveraging test-time inference strategies without additional training, and (2) canonicality by construction, a model parameterization that guarantees canonical outputs but requires training. We demonstrate that fixing canonicality mistakes improves the likelihood of held-out data for several models and corpora.

Language Models over Canonical Byte-Pair Encodings
Tim Vieira
Tianyu Liu'
Clemente Pasti'
Yahya Emara'
Brian DuSell' Benjamin LeBrun"
Mario Giulianelli
Juan Luis Gastaldi
Timothy J. O'Donnell 324
Ryan Cotterell
Abstract
Modern language models represent probability distributions over character strings as distribu- tions over (shorter) token strings derived via a deterministic tokenizer, such byte-pair encod- ing. While this approach is highly effective scaling up language models to large corpora, its current incarnations have a concerning property: the model assigns nonzero probability mass to an exponential number of noncanonical token encod- ings of each character string these are token strings that decode valid character strings but are impossible under the deterministie tokenizer (i.e., they will never be seen in any training corpus, no matter how large). This misallocation is both erroneous, as noncanonical strings never appear in training data, and wasteful, diverting proba- bility mass away from plausible outputs. These are avoidable mistakes! In this work, we propose methods enforce canonicality in token-level language models, ensuring that only canonical to- ken strings are assigned positive probability. We present two approaches: (1) canonicality by con- ditioning, leveraging test-time inference strategies without additional training, and (2) canonicality by construction, model parameterization that guarantees canonical outputs but requires training. We demonstrate that fixing canonicality mistakes improves the likelihood of held-out data for sev- eral models and corpora.
lello Jorid
Hello,
Hello 436
1ic -ert bise 18750r
all a world
lapr soon sersin aas
Hello orld
1is40e for zser 1764
ello fap seneer in sas
Frseson ease
Figure I. The figure shows the canonical and noncanonical encod- ings of the string Hello,_worll. The diagram shows the top-8 token encodings of the string according to their probability (de- scending top to bottom), there are hundreds of them for this short string. Note that the canonical token encoding is the most likely one (i.e., is the top), which is reassuring as most representative of the training data.
distributions over different space of token strings (de- noted A*). In the case of the prevalent byte-pair encoding (BPE; Gage, 1994), each token may be regarded as a multi- character (or multi-byte) chunk of a UTF-8-encoder string. Such a language model trained by encoding its training data into token strings, which has the benefit of compressing the large corpus. The BPE encoding is pair of functions: encoding function Σ' + A that maps given input character string o to its canonical encoding 5 = r(a)), and decoding function k: A + Σ' that maps any token string 5 back to a character string o = x(5). The result of training on a corpus of token strings is language model pa that gen- erates a token string ö and decodes a character string o.
thub. http://ccc/ggeem/nnnonnaaaiiiioo
1. Introduction
We define the set of canonical token strings D C A as those that appear as the canonical encoding of at least one character string, i.e., def (T(O) | ""}. These are the only strings that are possible in the tokenized training data of Pa- The set of noncanonical token strings is, thus, A D. Even though Pa has never-and will never-sce a noncanonical token string in its training data, it will still place nonzero probability mass on them due to model archi- tecture and training limitations. Fig. shows an example
Modern language models are probability distributions over character strings (denoted Σ*) that are parameterized as
ETH Zürich Mill McGill University 'Canada CIFAR Al Chair. Correspondence to: Tim Vieira <tim.f w.w.iiiregeaiil.......... comm.
Proceedings of the 12nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Language Models over Canonical Bytc-Pair Encodings
of string with its canonical encoding and its exponentially many noncanonical encodings.
Cross-entropy: H(p, wnf - EEE p(x) log (())
KL divergence: KL(pllg) E.Ex p(z) log p(a)
g(x)
These quantities are related via (L(pllg) H(p, H(p).
Fixing canonicality mistakes. Removing noncanonical strings from the support of the estimated distribution Pa can improve the likelihood of the correct token strings. We describe two families of methods for doing so
and H(p) H(p, p). Lastly, we follow the information- theoretic convention that log 0 _ne 0 in these definitions.
2.3. Language Models
Canonicality by conditioning: We explore efficient test- time inference methods for conditionally generating text that satisfies the canonicality constraint without retraining. Canonicality by construction: We explore methods that impose canonicality constraints directly in the language model's parameterized architecture and give method to fine-tune its parameters.
A language model pr is a probability distribution over a set of strings I Thus, we can define a string- valued random variable Y ~ pr with this distribution. Moreover, we can compute the conditional probabilities of different events pertaining to the random variable Y, as normally do in probability theory. However, since Y is string-var string-valued, the comparisons and transformations applied to it must be string-friendly. We define the prefix probability:
In addition to these novel methods, this paper presents the following contributions:
(-)
def
Pr Y ビ 7 Yopr
Σ 1( > Dy> pr((() (la)
We prove that our methods can only improve the fit to the true distribution over tokens.
Y'EL
and the conditional prefix probability:
We show empirically that fixing canonicality mistakes using methods improves the likelihood of held-out data for several models and corpora.
(Y 7 (-()) pf(
pF (T' 7) def Pr
(1b)
Youp
As side effect of pursuing the goal of generating only canonical token strings, we discovered an efficient, in- cremental canonicality test for BPE (see App. B) that is significantly simpler than prior work (e.g., Berglund et al., 2024; Cognetta & Okazaki, 2024), as does not require automata theory to understand implement.
pr pr(r)
př (EOS) (r)
(1c)
pF(
We can use conditional prefix probability to factorize the probability Pr( of string y = "1"" as the conditional probability of each of its symbols Y1... 7r. followed by an end-of-string event EOS:
by
2. Preliminaries
(r = pf 7) II
[p I vet) 1=1
(1d)
2.1. Strings
Note that each conditional prefix distribution pf( Y is a probability distribution over I [EOS). Many language models are defined via the product in Eq. (Id) where each single-symbol conditional prefix probability comes from parametric model trained by predicting the next token given the previous context. Examples of this include transformers (Vaswani et al., 2017), RNNs (e.g., Mikolov et al., 2010; Sundermeyer et al., 2015), and n-gram models (e.g., Shannon, 1948).
An alphabet is a non-empty, finite set of symbols (e.g.. bytes, characters, or tokens) from which we can build strings. string is finite-length sequence of symbols from a given alphabet. Let I' be an alphabet. Let I*x denote the set of all strings over T. We use |y| to denote the length of the string and to denote the string of zero length. Let y'""" denote the concatenation of of' and y" We write Yen det 7n- to access the first denote that y is prefix of 7', and Y 2 y denote that r is has y as a prefix. The set of bigrams of a given string DIGRAMS(11 del Ynn 1 <J.
symbols of the string y. Let y
2.4. Tokenized Language Models
An (exact, deterministic) tokenization model (Gastaldi et al., 2025) is a tuple (E, A, r.) where Σ is an alphabet of characters (or bytes), A an alphabet of tokens, 7: Σ 4 A is an encoding function, K: A + E' a decoding function, and x(T(a))
2.2. Information- Theorreiic Quantities
For completeness, we include definitions of the following common information-theoreti quantities, which are mea- sured in bits. Let log be the logarithm function in base 2 throughout this paper. Let and be probability distribu- tions over a countable domain X.
for all E+
Here, EOS an event, not a symbol; thus, it may never appear in any well-formed string. Note that for and to form bijection between E- and A", we would additionally require 7(x(6)) = 5 for all 6 E A"
Entropy: H(p) del -EEe ((x) logp(x)
2

---

Language Models over Canonical Byte-Pair Encodings
A tokenized language model is language model Pe over character strings E¹ that is parameterized by a token- level language model Pa over A and a decoding function k: A' + E". The tokenized language model defines the following probability distribution over E":
(P())
he
the
83 258
1169
pI( de
Σ 1 (6 BEA-
(2)
480
th
400
th
x
th
the
400
1169
Notice that is conspicuously absent from this expression, as it is only part of the estimation process, which we char- acterize below. In $4, we consider alternatives to Eq. (2) that exploit prior knowledge of to force the probability of noncanonical token strings to be zero.3 3
tha n
than
12898 '77
14813
tha n
thanks
12898 77 591
27547
ing 817 278
hing
722
Th inging
hing ing
817 14146
51" 722 278
Estimating a tokenized language model. Let be some probability distribution over Σ we wish to estimate. As is standard statistical estimation, we take a large sample (()) (M) lid. ps. Next, we encode each strings of characters into strings of tokens, giving us a corpus of token strings: ((m) = (()r for S. m S M. Let pA denote the distribution of these token strings:
Figure 2. Short examples of canonical and noncanonical token strings from GPT2's tokenizer. Because the canonicalization op- eration yp is idempotent, each example in the second column is canonical. These examples were chosen highlight some of BPE's unintuitive preferences, e.g., BPF is not a longest-match tokenizer, and canonicalization can increase the string's 's length.
the encoding function of BPE works as follows: each char- acter of an input string 01 .M oN is initially mapped to an individual token, then pairs of tokens are iteratively merged into bigger tokens according to list of merge rules M. We refer the reader App. B for a formal definition of BPE.
(0)
Σ ((T())=80p$C OEE
(3)
Next, we estimate a token-level language model pa to fit the strings 5(1) ((),,.,(MM)) After estimation, we have a dis- tribution Pa over strings of tokens rather than strings of characters. Thus, to generate a string of characters, we first generate a token string 5 ~ Pa, and decode it (via x())) to get character string. This process is why the tokenized language model's 's character strings are distributed accord- ing to Eq. (2).* Tokenization is used in practice because working with (short) token strings is easier than (long) char- acter strings. The most commonly used tokenization scheme for modern language models is byte-pair encoding (BPE; Sennrich et al., 2016; Gage, 1994), which a simple and effective algorithm for shortening text (Zouhar et al., 2023).
2.6. Canonicality
To facilitate discussion, we start by introducing some termi- nology. The set of canonical strings:
D def (T(a) EoEE
(4a)
The set of noncanonical strings D del A *\2 D, and the set of canonical prefixes:
ò Aur A 8 8','''
(4b)
2.5. Byte-Pair Encoding
We say that 5 is canonical if 5 D. say 5 is canonical
prefix if E D. We define the canonicalization function
Byte-pair encoding (BPE; Gage, 1994; Sennrich et al., 2016) a commonly used tokenization scheme. 5 Intuitively,
:: A + - DD as ((() del r(x(6)). Note that D = {v(()
E A }. We say that our language model pa is canonical
3 VVieira et al. (2024) give algorithms for working with tokenized language models at the character (or byte) level, including algo- rithms for computing conditional probabilities.
if $ D = (0) O, i.e., EseD PA (o) = 1.
'Gastaldi et al. (2025) characterizes the conditions required for tokenized language models to estimate pt: consistently.
Membership tests. We can test membership in D via the round-trip test: ô E D + (()) 8. We note, however, that testing membership in D for general tokenizers is less
'BEE is the most prevalent tokenization strategy in modern language models; it used by OpenAl's GPT-2 (Radford et al.,
2019), GPT-3 (Brown et al., 2020), GPT-3.5 (OpenAl, 2022), and GPT-4 (OpenAL, 2024a), GPT-4o (OpenAI, 2024b); Meta's Llama 1 (Touvron et al., 2023a). Llama 2 (Touvron et al., 2023b), and Llama (Ilama Team, 2024); Mistral's 7 (Mistral AI, 2023), Au (Mistral AI, 2024a), and Nemo (Mistral AI, 2024b);
NeoX (Black et al., 2022); EleutherAl's Pythia (Biderman et al., 2023); Anthropic's ' Claude (Anthropic, 2023a) and Claude 2 (Anthropic, 2023b); Google's Gemma (Gemma Team, 2024); and A12's OLMo 1 (Groeneveld al., 2024) and OLMo 2 (Team OLMo, 2025).
3

---

Language Models over Canonical Bytc-Pair Encodings
straightforward.
Note that (g) (T)))( meaning that we may inter- pret the globally canonicalized model renormalizing r/s- We note that the effect of conditioning the language model to generate only canonical token strings may dramatically change the conditional prefix distributions of the distribu- tion. We will discuss the details of how to approximately and exactly generate samples from g.
Membership tests for BPE. App. B provides efficient algorithms for membership in these sets for BPE. Lemma 3 shows that for BPE D D. i.e., the round-trip test is a cor- rect membership test for D. We also provide a very efficient incremental algorithm for performing these membership tests that exploits the properties of the BPE encoding proce- dure. Fig. shows examples of canonicalized BPE strings.
3.1. Theoretical Guarantees for Conditioning
Why do we condition? The conditional distribution lets us preserve what matters: the relative probabilities of canonical strings, ensuring that we eliminate the wasteful mass allocated noncanonical strings without distorting the existing mass canonical strings.
3. Canonicality by Conditioning
Recall (Eq. (2)) that a tokenized language model defines language model pr: (o) over Σ" However, it is common practice to evaluate the probability of a character string a E >n using the following sub-distribution over 2nd during both likelihood- based training and evaluation:
The following proposition shows that test-time conditioning improves our estimate g of the true distribution P\-
Proposition Assuming that the true distribution over tokens p'A is canonical, the globally canonicalized model g guarantees the following reduction in KL divergence:
pO)()) del (T((()))
(5)
The problem with p/s is that Eoer- can be < 1, making it is an improper probability distribution over Σ*
KL(P's (l - -KL(p' l1 = - log Z
Unfortunately, every token string- canonicll or not-is assigned a nonzero probability under a noftmax-normalized model: thus, modern language models allocate (typically small) probability to each and every noncanonical string. The leakage of mass to noncanonical strings is compounded by the fact that D is an exponentially sparse subset of A
20
Proof: See App. D.
We may interpret Proposition I as saying that, no matter how good or how bad of a model the original language model Pa is with respect to the true distribution PA. we can expect reduction in the KL divergence equal to - log Z, bringing it closer to Ph- This reduction is large if Z is small, i.e., the token strings generated in pa are unlikely to be canonical, modest if Z R 1, and zero if Z = 1. In other words, the change in KL quantifies the value of having the constraint as prior knowledge.
Our first approach to this problem defines a language model 9 that is the result of probabilistic conditioning on the event that the generated token string is in D.
Definition 1. The globally canonicalized language models gs, and g are defined as the following probability distribu- tions over Ed and A respectively:
3.2. Algorithms for Approximate Conditioning
(r(o) def g(((o))
(6a)
3.2.1. EXACT ALGORITHMS
Pr Y = E DD g( del
(6b) The simplest exact conditioning algorithm for sampling
Y Y~ps
from g is rejection sampling:
Prympa (V =6
(6c)
Pry [ E D]
I def rejection_samplingg)
2 while True:
= 7 (A) D}
(6d)
3
8 3~pa PA
if 8 E D: return 5
where Z is the canonicality rate:
However, the rejection sampling algorithm can be inefficient if Z is small, as its expected running time per sample is (1/Z). When Z R this is pretty fast. However, when it is smaller, it can be unusably slow.
Z def
Pr |Y D] YEPA
(6e)
'When the tokenization function 7 is implemented as a finite-state transducer, we may derive an efficient finitc-state automaton that describes the prefix language of its outputs.
"More formally, the conditional distribution is the unique distribu- tion g over 2 that maintains the relative probabilitics of any pair 8, 8' E D--that is, pa (8'), g()) = (0)) g(0"). (")) The only way to achieve this is to set g (o) for all 5 E D, where normalization fixes 17 = 1/7. Thus, q g is the unique way preserve relative prohability subject to the canonicality constraint.
MMore precisely, as a function of a length limit N. the fraction of canonical strings in the universal of token strings 1: (8) :
decreases exponentially quickly. This is evident as each character string has one canonical encoding, and exponentially many noncanonical encodings as a function of its length.
4

---

Language Models over Canonical Bytc-Pair Encodings
Another correct sampling algorithm is ancestral sampling:
2. It has the correct support: The local distribution can only place positive probability on canonical strings; it elimi- nates noncanonical strings by masking out any token 8' that would render the extended string 5-8' noncanonical.
def ancestral_samplinge
E-E
while True:
3. It often gives a reasonable approximation to the condi- tional global distribution: We expect this to be a good
8' (-)
if 8' = EOS: return 6
approximation when (8) 1, which we may expect in practice as noncanonical strings tend to be assigned tiny probabilities, making the sum in Eq. (9d) close to 1.
8 - 8-8'
10
Here, each step of the algorithm samples token (or BOS) from the globally canonicalized model's conditional prefix distribution. Unfortunately, computing 9 exactly is in- tractable as it requires summing over infinitely many future strings. Thus, ÿ must be approximated." In $3.2.2, we will provide a cheap, local approximation and, in $3.2.3, we will devise strategy for improving the sighteiigts of the local approximation by using more computation.
Unfortunately, the locally canonicalized model gives a warped approximation to g. as Proposition shows: Proposition 2.
18++1
{(6) - (
II (8
(10a)
3.2.2. A LOCALLY CANONICALIZED APPROXIMATION
der 2ry (8)
Our locally canonicalized model E is a distribution over A that approximates ancestral_sampling for sampling from g by using the following local approximation 7 to the global prefix probability J.
Thus,
we(6) Pa(0) ((6)
1 E D}
(10b)
Proof: See App. D.
Definition 2. The locally canonicalized model is a language model over A', which assigns probability zero to noncanonical strings. The probability of a token string under is defined ruto-regressively as
We call (x) the weight of the locally canonicalized sam- plc (in relation to P.). We note that the weight describes the change in relative probability of the canonical token strings 8 E D. We call this unwanted change warping. There is no warping in the globally canonicalized case, as the relative probability is unchanged. In $3.2.3, we describe methods that can unwarp the local distribution at the cost of additional computation.
[8]
{(δ) vet 7 (EOS 6) II
7 (6e 62)
(9a)
t=1
where its next-token conditional distributions are defined as
7 (BOS) 8) der PEOSOSS 8)118 E D}
Despite the warping, the local distribution & comes with the following reassuring theoretical property, guaranteeing that it helps estimate the true distribution pi-
(9b)
7(6)
? 70' 8)) de (0' 8) E D} 7(6)
Proposition 3. Assuming that the true distribution over tokens P's is canonical, the locally canonicalized model & guarantees the following reduction in KL divergence:
(9c)
where 7 (8) normalizes the distribution over A U {EOS} that lead to a canonical extension of the string:
KL(P' |Pa) KL (1
E 8~pp's
[log we wo()))
(11)
70) # 1 (EOS 18)
(9d)
20
+ Ep0
1) E
D}
Proof: See App. D.
SEAA
Proposition 3 confirms the intuitive notion that local canoni- calization cannot make the language model worse. 10
This distribution is practical for the following reasons:
1. is efficient: The canonicality checks are cheap to com- pute (App. B), and there is very little additional overhead over sampling from the base conditional distribution.
3.2.3. SAMPLING- BASED INFERENCE
Unfortunately, sampling from 9 is hard because we cannot efficiently compute the conditional prefix probability y
WW also mention more sophisticated approximations, such as learning (Zhao et al., 2024), adaptive upper bounds (Park et al., 2025), and sequential Monte Carlo steering (Lew et al., 2023; Loula et al., 2025). We do not explore these more sophisticated strategies, as the local approximation works surprisingly well.
10 "rrppssition 3 may be generalized to any distribution Specif-
ically, KL(p's llpa) - KL(p' g] -Bs-p3 [log (a( 9(d) However, it may necessarily be reduction, it is for 2, if the distorts the distribution too much.
5

---

Language Models over Canonical Bytc-Pair Encodings
(and rejection sampling is slow when Z is small). In this
which has support with size most M. Thus, impor- tance sampling and resampling give a parameter M that improves the approximation as we make it larger.
section, we show how to the local approximation in conjunction with sampling-basel inference improve the fidelity to at the cost of increased computation. These methods use the local distributions as a proposal distribution to produce candidates that will be properly weighted and resampled in a manner so that they maintain a principled approximation to the global distribution g. Therefore, in expectation and in the limit, these methods produce exact samples; thus, they do not warp the distribution.
4. Canonicality by Construction
The method we present this section augments the out- put layer of the transformer architecture with canonicality constraints. Thus, it requires additional training and test- time computation. Fortunately, this additional computation, at least in the case of BPE, is minimal thanks to efficient algorithms for checking canonicality (see App. B).
The warping in the locally canonicalized method can occur because the sampling algorithm approximated the conditional prefix probability canonicality, meaning that we may sample a string of tokens that looks good initially, but we end up stuck with a bad string prefix because overestimated the conditional prefix probability. In contrast, rejection sampling restarts the sample once noncanonicality is detected, whereas the local method ignores noncanonical tokens and forces the current string to complete. We can fix the bias in the local approximation by exploiting our knowledge of (ō) for each sample É. More specifically, we( is proportional the of in samples from with respect to the target distribution g. Therefore, we can correctly account for this in expectation by weighting each sample by its wy factor. This is the principle behind the importance sampling methods we describe below."!
Suppose we have a base architecture, i... a parametric family of language models (PolDER" that parameterized by real-valued vector of parameters 0 _R We assume log pa (o()) is continuously differentiable with respect 0 for all 8 A and that each pe is valid language model over A For example, {pe ) 'EER can be parametric family of transformers or recurrent neural networks." 13 Let pá denote the conditional prefix probability one such model.
Definition 3. Our canonicalized architecture is a paramet- ric family of language models {Co)oeR> that is built on top of a base architecture {poLBERD. We define each la in terms of po in the following manner:
over- under-representaaiion
|8]
(Ø) def COOS
5) II (o det)
(15a)
Proposition 4.
Z E [w) = PA (8) D}] bot
where each Eo 82t) is defined one of the following distributions over A U [FOS}:
(12)
and
((5)
Proof: See App. D.
(6 88) del Po 8) 15 E
D
(15b)
(5)
Thus, we can apply importance sampling to obtain an unbiased estimate 7 of % given 511) ... (M) iid. &
Eg (FOS) 8) (EOS
1 E D}
(15c)
(6)
M
2
Σ
(m)))
(13)
M
and (5) ensures normalization:
m=1
We may also estimate the global distribution g as follows:
(5) (FOS 6) E
(15d)
Σ (8" 18) E D)
O def
Σ
(14)
M
Much like the locally canonicalized model (Def. 2), non- canonical strings are forced to have probability zero using canonicality checks in the definition of its conditional prefix probabilities Eq. (15b) and (15c).
Note that the quotient with 2 leads to statistical bias; how- ever, that bias vanishes as M grows larger. If desired, we may also for drawing approximate samples using method known as importance resampling. This method produces approximate samples from by sampling 8 ~ g.
We note that for these estimates converge their correct values, we require pa (6) E D) > = {(6) > for all 8 E A', This is ensured when our prefix canonicality test 1 1,5 E DJ is exact. More generally, it is safe to allow for false positives but not false negatives. 13 "Our experiments use transformer- language models.
"FFor rigorous treatment of the technical conditions required for importance resampling and estimation converge, we refer the reader to Chatterjee& & Diaconis (2017).
6

---

Language Models over Canonical Bytc-Pair Encodings
Why train? Suppose the original model pa is equal to some po in our family; let o denote its parameters. Clearly, if we set 0 = o the model lo is no different from f. The reason we optimize 0 beyond e is that
5. Experiments
This section evaluates our proposed methods- by constraints (global and local; $3) and canonicality by conditioning (54)-by measuring their impact on real datasets and language models. This evaluation complements the theoretical guarantees of Proposition I and Proposition 3, by quantifying the log-loss (C; Eq. (16)) on held-out data.
the training objective for ( pressured the parameters to model canonicality, but now that pressure is gone because the canonicalized architecture (Def. 3) enforces that con- straint for all O. Thus, the parameters that were previously used model canonicality preferences can be repurposed to model any other textual phenomena in the training data.
5.1. Setup
Datasets.
We experiment the following two datasets:
Training pa- Given training corpus or ,.. . (M) itd.
Penn Treebank (PTB, Marcus et al., 1993) (test split; 3761 strings, 82k words, 439k characters)
Ps: of character strings, let ((M) be their corre- sponding (canonical) tokenizations. We define L(p), the
WikiText (Merity et al., 2017) (test split; 4358 strings, 234k words and 1286k characters)
log-loss (average negative log-likelihood) of the training corpus under a language model p:
Models.
We experiment with the following models:
((p)
Σ log p(g(((() 10211
(16)
GPT-2 models (Radford et al., 2019) of increasing size (small, medium, and large)
M
Llama models (Llama Team, 2024) of increasing size (3.2-1B, 3.2-3B, and 3.1-8B).
Log-loss is reasonable (and common) training objective, as minimizing C(f)) also minimizes KL (l in the limit of infinite data (with perfect optimization). However, training large language model with L from scratch is prohibitively costly. Instead, we fine-ture tune an existing (non- canonical) large language model.
Pre-tokenization. Our efficient bigram- -based canonical- ity test 1160-'' E DJ (App. B) makes the simplifying as- sumption that the tokenizer r is only based on BPE. How- ever, in practice, systems use an additional pre-tokenization step that breaks text into chunks called pre-tokens (e.g.. based on spaces and punctuation). Most pre-tokenizers are based on hand-crafted regular expressions; the GPT-2 and Llama models each use a distinct pre-tokenization regular expressions. Since these models make use pre-tokenization, our incremental test occasionally makes some mistakes. Par- ticularly, concerning are instances of false negatives, i.c., we rule out a bigram as noncanonical when canonical. False negatives are problematic for estimation (Footnote 12). These errors caused by the interaction of the pre-tokenizer and the tokenizer." 14 To work around these rare exceptions, we determined (small) set of overrides for our canonicality test by identifying the bigrams where we have made a false negative judgment on a corpus of canon-
We use the following fine-tuning objective, which strikes balance between fitting the log-loss objective while main- taining some fidelity to the original language model pa:
0 def (1- - A) [((e) + X (L(eollps)
(17)
Here, we use the KL divergence between to and the original unconstrained model distribution p.a as a regularizer (e.g., Christiano et al., 2017: Stiennon et al., 2020; Ziegler et al., 2020; Korbak et al., 2022). The regularization parameter 0 X 1 is used to trade fidelity to the original model (higher) against fidelity to the fine-tuning data (lower).
in fact
Optimization. Our optimization algorithm is based on stochastic gradient descent. To optimize (0), on each step, we randomly choose with probability A which of the two terms to perform a gradient step on.
"FFor example. under the GPT-2 tokenizer, the token bigram An 198" 198 may or may not be canonical, depending the con- text. For instance, in the following example, it is canonical:
1. For the log-loss updates, we sample a minibatch of ex- amples from the fine-tuning corpus and use the sample average of that minibatch's 's gradient proximation to the gradient over the entire corpus.
T(H1, AnAnI) 17258 11
Hi
An
198
198
48
efficient ap-
because the pre-tokenizer creates separate pretokens each newline, preventing BPE from merging them. However, in the next example, it is not canonical:
2. We estimate the gradient of the KI. regularization term using Amini et al.'s 's (2025) Rao- BlakBlaakwellized method using samples from the current lg.
7Hi AnAn) = 17259
Hi
AnAn
11 628
because the pre-tokenizer does not create separate pretokens for the newlines, allowing BPE to merge them.
Experiments initialize lo with the same parameters as PA-
7

---

Language Models over Canonical Bytc-Pair Encodings
ical strings. We note that this workaround occasionally introduces false positives. 15
Model
Baseline
Local
Global
Llama GPT-2
small
201.0
200.7
199.1
medium
195.1
194.5
193.1
5.2. Canonicality by Conditioning
PTB
large
189.4
188.9
188.2
IB
171.2
171.1
169.7
Methology. Fig. 3 reports the log-loss of the local l and
(m)))) M global methods on each dataset ((pAm) Im=1) as well as
3B
165.0
165.0
164.2
8B
161.5
161.5
160.1
Pa, which serves as our baseline. Below are the details of how we estimated the log-loss of each method.
Llama GPT-2
small
369.2
367.0
367.3
Wikilext
medium
334.1
333.2
332.2
Baseline: The log-loss for the baseline method is
large
320.8
319.1
319.6
M
IB
286.7
284.4
285.2
((ps) = M m=1
Σ
pa
(6(m))
(18a)
3B
264.6
262.0
263.7
8B
248.2
245.8
246.8
Global: The log-loss for the global method is
Figure 3. Log-los (C; bits/string) for the baseline (pa). local (t). and global (g) methods across two datasets and models. Bold- ing indicates that the number is the best in its row. See text for discussion of statistical significance.
((g)= ((Pa) + log 7 z L(Pa) + log 7
(18b)
where ğ is computed by Eq. (13) using 2000 samples from f. Note that log Z < O; thus, the global method can
only improve the log-loss, (gg) I (ps)). 16
Local: The log-loss for the local method is
For the local method, the log-loss reduction is positive for all strings, but the amount varies across strings; nonetheless, is trivially statistically significantly bet- ter than the baseline method according the paired- permutation test (i.e., p 0).
C(L) C(pa)+ +
1 M
Σ
log (6(m)
(18c)
m==
def
W
Local vs. global: On the PTB dataset, we found that the global method is significantly better than the local method for all models. However, on the WikiText dataset, the local model better in all cases except GPT-2-medium.
1 Note that 37 Em= method can only improve the log-loss, L(()= S L(pa).
I log ())) S O: thus, the local
Relationship to theory. Proposition I shows that the re- duction in KL divergence is equal to - log Z, which is equal the difference in log-loss L(Pa) L(g). Proposi- tion 3 shows that the reduction in KL divergence is equal to -Espp [log wx)d)], which is equal to the difference in log-loss ((ps)= - (()) (in expectation).
Takeways. On principle (S3.1), we maintain that the global method (based conditioning) is the correct solution, as it is the only distribution that preserves the relative probabilities for canonical strings. Additionally, our experiments support the local method as a practical approximation to the global distribution, which we expected to be the case because the probability allocated to each noncanonical token generally quite small, meaning that the warping not large; see discussion Item in $3.2.2). Interestingly, some datasets (e.g.. WikiText),, the warping induced by the local method with respect to the global distribution can be advantageous, i.e., its reduction in log-loss with respect to the WikiText distribution is larger than that of the global method.
Observations.
For the global method, the change in the log-loss is inde- pendent of the dataset because log Z is independent of the dataset. However, for the local method, it is dependent because W dependent on the dataset. Statistical significance:
For the global method, the log-loss reduction is positive and constant for every string; therefore, it is trivially sta- tistically significantly better than the baseline method according to the paired-permutation test (i.e., p 0).
Log- eog-canonicalityy rate vs. length. We found that the GPT- models generate very long strings, so we investigated the tradeoff's in the log-canonicality rate for truncating the lengths of the strings generated by each model. Fig. 4 shows the effect of length on the log-canonicality rate estimate log 2, using 2000 samples taken from É. We see that for the Llama methods, the log-canonicality rate stabilizes after 256 tokens, but for the GPT-2 models, it continues decreasing. Thus, for practical reasons, our experiments with GPT-2
A complete solution to the pre ne-tokenization challenges would build transducer that accurately models the seetokknn which we then compose with a transducer implementing BPE (see App. B.4). We leave this investigation for future work. IIn the case of the GPT-2 models, restricted strings to have length 1024, as these models tend ramble. We analyze this choice further Fig. 4.
8

---

Language Models over Canonical Byte-Pair Encodings
GPT-2s
GPT-2M
GPT-2- LLaMays
Data
Model
Method
LLaMa
LLaMass
N/A
.001
.01
.1
.2
201.4
143.7
143.7
143.6
146.8
S
PTB
200.7
143.6
143.6
143.6
146.8
2
log
M
195.0
128.6
128.9
128.6
132.1
194.5
128.3
128.7
128.4
132.0
-2
Wikilext
369.2
331.7
331.7
331.7
335.7
M S
367.0
331.7
331.7
331.7
335.6
128
256
512
1024
maximum string length
334.1
293.9
294.0
293.9
298.7
333.2
293.7
293.8
293.8
298.8
Figure Log-canonicality rate vs. (tokenized) length, including 95% confidence intervals, for each model.
Figure 5. Log-loss (bits/string) of fine-tuned models held-out portions of WikiText and PTR. The column laheled N/A reports the log-loss of the baselines Pa and f. The other columns correspond to the value of the regularization parameter used in the fine- tuning loss. The rows labeled p the original architecture and l canonicalize architecture.
will be based on a limit length of 1024, but bear in mind that this means that the actual log-canonicality rate is likely to be much smaller, meaning the reduction in log-loss for GPT-2 is larger than Fig. 3 indicates.
that reguarlization towards the original model should not be done too strongly.
Supplementary error analysis. frequent canonicality errors made by each model.
App. E analyzes the most
Takeaways. Unsurprisingly, fine-tuning for the specific
dataset useful regardless of whether we use the original or canonicalized architecture. Fine-tuning with the canonical- ized architecture performs slightly better, but improvements appear to be small. It is possible that training the canon- icalized architecture from scratch on a huge dataset would yield better results than our proof-of-concept experiment.
5.3. Canonicality by Construction
Methodology. We fine-tuned two language models, GPT- 2s and GPT-2M." 17 on the PTB train set and a subset of the WikiText train set with 50K strings and 4.2M words. We consider fine-tuning the canonicalized architecture (Eo) and the original architecture (por) using the training criterion FA for À= E {0.001, 0.01, 0.1, 0.2). As baseline, we consider the original model Pa and the locally constrained model f, as these models serve initialization for fine tuning. Fig. 5 reports the log-loss L (bits/string) on the held-out datasets for each method mentioned above.
Conclusion
We have demonstrated that enforcing canonicality in token- level language models eliminates systemic probability mass misallocation, leading to improved likelihoods on held-out data across multiple models and corpora. Our proposed methods- by conditioning and canonicality by construction cmnstruttio-prrovddee practical solutions that either refine inference or modify the model architecture to ensure only canonical token strings are assigned positive probability. In theoretical results
Observations.
all cases (i.e., models, datasets, and methods), we ob- serve a large improvement in log-loss from fine-tuning. The reduction in log-loss is larger in the case of PTB. Provided that À is small enough, we see a consistent reduc- tion in log-loss when comparing tg and Pgr However, the difference between lg and Par is comparatively smaller than we saw in Fig. 3.
addition to the empirical benefits, establish that correcting these mistakes strictly improves model fit. Moreover, our discovery of an efficient incremen- tal test for BPE canonicality simplifies prior approaches, making it more accessible for practical deployment. These findings underscore the importance of aligning token-based probability models with their training distributions, thereby paving the way for more accurate language modeling.
Generally, a the smaller values of work best, indicating
"Unfortunately, we are unable to fine-tune larger models due to computational constraints. However, the models used here serve proof of concept.
A Acknowledgments
"aach model is trained for 3 epochs using the AdamW optimizer (Loshchilov & Hutter, 2019) with a learning rate of 5e and linear learning rate decay. For efficiency, we use bfloat16 16 to represent the model parameters. We use minibatch of size for estimating the gradient of each term of the F, objective.
The authors would like to thank John Terilla, Marco Cognetta, Ben Lipkin, Luca Malagutti, and Manuel de Prada Corral for their helpful feedback and discussions.

---

Language Models over Canonical Byte-Pair Encodings
Impact Statement
Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan,
J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G.,
Potential benefits. By introducing methods to enforce canonicality, we improve a given model's fidelity the underlying distribution that generated the text. These con- tributions have broad implications for the reliability of lan- guage models, particularly in applications where precise probability estimates are crucial. By climinating avoidable modeling errors, we advance the goal of more reliable and robust language models.
Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan. T., Child, R., Ramesh, A., Ziegler, D. M., Wu,
J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCan- dlish, S., Radford, A., Sutskever, I., and Amodei, D. Language models are few-shot learners, 2020. URL ittps://arxils http://xxiv....aab/...s//
wwrggabs/2200 14165.
Chatterjee, S. and Diaconis, The sample size required in importance sampling, 2017. URL https: org/ abs/1511.01433
Potential harms. Constraining tokenization may inad- vertently reduce robustness to rare, noisy, or adversarial inputs by ruling out alternative tokenizations of the same character string. While the canonicality constraint does not remove any character strings from the language, it does restrict the model to assign nonzero probability only to single canonical tokenization of each string. This may dis- proportionately affect rare or unconventional spellings, as their probability mass may be less sharply concentrated on a single tokenization. Future work should provide a deeper analysis of whether or not canonicality enforcement helps or hurts in these settings ensure fair and robust language model behavior across diverse linguistic contexts.
Christiano, P. F., Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, D. Deep reinforcement learning from human preferences. In Advances in Neural Information Processing Systems, 2017. URL httpttt//rocceediiiiiig neurips. cc/ httpee/iilee//ppe//21/////i /att/////a/////a/a/aa/////////aa dacceacddfa2c1111510744444444469
.ddf.
Cognetta, M. and Okazaki, N. Tokenization as finite-state transduction, 2024. URL https://arxii. orggbss//rr///////////// 2410. 15696.
Gage, A new algorithm for data compression. Users Journal, 12(2). 1994. ISSN 0898-9788. URL https://web.ce http://www....i..........o... http://rwwiieerre/ee//////111110 http::/www.derrrysss...coo/ppppp BPE 3PE_Gage..pff
References
Amini, A., Vieira, T., and Cotterell, R. Better estimation of the KL divergence between language models, 2025. URL
106377
Authropic. Introducing Claude, 2023a. URL https: https://wwww anthropic..com//eww/iiiie hww//////////ntrrrruiinngg--oge/
Gastaldi, J. L., Terilla, J., Malagutti, L., DuSell, B., Vieira, T., and Cotterell, R. The foundations of tokenization: Sta- tistical and computational concerns. In Proceedings of the International Conference on Learning Representations, 2025. URL https: /arxiv.//axvv..o/ otgg/bs/////// 11606.
Anthropic. Claude 2, 2023b. URL https://vww.
com anthropic..ommneew///ee wtt.///www//c/dee.........e/eeee
Berglund, M., Martens, W., and van der Merwe, B. Con- structing a BPE tokenization DFA, 2024. URL https: abws//05.... //arxiv.org hrtpiv..orggbb/2445555 07671.
Gemma Team. Gemma: Open models based on Gemini research and technology, 2024. URL https://arxiv..
org/abs/2403.c0 08295.
Biderman, S., Schoelkopf, H., Anthony, Q. G., Bradley, H., O' Brien, K., Hallahan, E., Khan, M. A., Purohit, S., Prashanth, U. S., Raff, E., Skowron, A., Sutawika, L., and Van Der Wal, O. Pythia: A suite for analyzing large lan- guage models across training and scaling. In Proceedings of the International Conference on Machine Learning, 2023. URL https: wwwppeeedonns..../// mlr. wtt.ssml.....r...... press//202// biderman23a. html.
Groeneveld, D.,, Beltagy, I,, Walsh, E., Bhagia, A., Kin- ney, R., Tafjord, O., Jha, A., Ivison, H., Magnusson, I., Wang, Y., Arora, S., Atkinson, D., Authur, R., Chandu, K., Cohan, A., Dumas, J., Elazar, Y., Gu, Y., Hessel, J., Khot, T., Merrill, W., Morrison, J., Muennighoff, N., Naik, A., Nam, C., Peters, M., Pyatkin V., Ravichan- der, A., Schwenk, D., Shah, S., Smith, W., Strubell. E.. Subramani, N., Wortsman, M., Dasigi, Lambert, N., Richardson, K., Zettlemoyer, L., Dodge, J., Lo, K., Sol- daini, L., Smith, N., and Hajishirzi, H. OL Acceler- ating the science of language models. In Proceedings of the Annual Meeting of the Association for Computational Linguistics, 2024, URL https: //a:://acllaa //tpa//aaaaaaoyy....///a org/ 2024.acl- acl-long....o...ooo..ooooooo.mcs 841/.
Black, S., Biderman, S., Hallahan, E.,, Anthony, Q., Gao, L., Golding, I.,, He, H., Leahy, C., McDonell, K., Phang, J., Pieler, M., Prashanth, U. S., Purohit, S., Reynolds, L., Tow, J., Wang. B., and Weinbach, S. GPT-NeoX-20B: An open-source autoregressive language model, 2022. URL https://arxiv. www.orggggb................ httgg/bbs/222../////
10

---

Language Models over Canonical Bytc-Pair Encodings
Korbak, T., Perez, E., and Buckley, C. RL with KL
OpenAI. GPT-4 technical report, 2024a. URL https://
penalties is better viewed Bayesian inference. In Findings of the Association for Computational Linguis- tics: EMNLP. 2022. URL https: http://///alanhooooyyy org/2022. eertiinng-eenlp....
mmxiv.orggabs//2303..1 08774.
OpenAl. Hello GPT-4o, 2024b. URL, https://openai. com/indexx/hello-gp-- gotttloo.gp--//....o
Park, K., Wang, J., Berg- Berg-Kirkpatrick, T., Polikarpova, N., and D' A'Attoni L. Grammar-aligned decoding. Advances in Neural Information Processing Sys- lems, 2025. URL http:://operreiiee.nttffoooo id=567ve8E1Lu.
Lew, A. K., Zhi-Xuan, T., Grand, G., and Mansinghka, V. K. Sequential Monte Carlo steering of large language models using probabilistic programs, 2023. URL https: //arxiv.org abs/2306. 03081.
Lindmark, V. Analyzing the effect of DFA compression in token DFAs, 2024. URL https: htww://wwwwwwwwo/ diva-portal. org/smaahh/get/divaz2 1aw.:laaa:21111/3//11 F888423 pdf.
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, Language models are unsupervised multitask learners, 2019. URL https: //ops://ccnn openai.. s m_m twmliiiiiiee task
Llama Team. The Llama 3 herd of models, 2024. URL https://arxiv. wwtpxxivorr///bbbi wwt.:orgg/////////e 21783.
Loshchilov, I. and Hutter, F. Decoupled weight decay reg- ularization. In Proceedings of the International Confer- ence on Learning Representations, 2019. URL https: //openreview. wwwptttp/pddeee httpearrwww...eee/efffoaaadadddn 71--
Sennrich, R., Haddow, B., and Birch, A. Neural chine translation of rare words with subword units. In Proceedings of the Anmual Meeting of the Association for Computationaa Linguistics, 2016. URL https:// aclanthology httphhooloo..ggg1161110 org/
Loula, J., LeBrun, B., Du, L.,, Lipkin, B., Pasti, C., Grand, G., Liu, T., Emara, Y., Freedman, M., Eisner, J., Cot- terell, R., Mansinghka, V., Lew, A. K., Vieira, T., and O'Donnell, T. J. Syntactic and semantic control of large language models via sequential Monte Carlo. In Proceed- ings of the International Conference on Learning Rep- resentations, 2025. URL https://openrevie/ net/ Forum?id=xoXn22F2DD
Shannon, C. E. A mathematical theory of communica- tion. The Bell System Technical Journal, 27(4), 1948. URL https://dol org/10 j. 15138/7355538555555 1948. tb00917.x.
Stiennon, N., Ouyang, L., Wu, J.. Ziegler, D., Lowe, R., Voss, C., Radford, A., Amodei, D., and Chris- tiano, P. F. Learning to summarize with human feedback. Advances in Neurul Information Process- ing Systems, 2020. URL httpss:/pprocee neurips.cc/paper neuripps.cc/pperr.ffeee////ppppp 1 (1998505552299908886666661111111
Marcus, M. P., Santorini, B., and Marcinkiewicz, M. A. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313-330, 1993. URL httpss://aclanthologg wrtp://-2//////////
pdf.
Merity, S., Xiong, C., Bradbury, J., and Socher, R. Pointer sentinel mixture models. In International Conference on Learning Representations, 2017, URL https:// openreview.net/forreee hetprrvviee.ee/foooonniideyyy 2udxx..
Sundermeyer, M., Ney, H., and Schlüter, From feed- forward to recurrent LSTM neural networks for lan- guage modeling. IEEE/ACM Transactions Audio, Speech, and Language Processing, 23(3), 2015. URL https://ieeexplore. ieee. wrtp//ocumen//7655339
Mikolov, T., Karafiát, M., Burget, L., Černocký, J., and Khudanpur, S. Recurrent neural network based language model. In Proceedings of INTERSPEECH, 2010. URL
Team OLMo. OLMo 2 furious, 2025. URL https://
arxiv. www.orr//bb/2000 00656.
wwt.://rrrrgneetsppeeeee.e 201 ht10mmmkkkooo11.innreseecchhhhh
Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., Rodriguez, A., Joulin, A., Grave, E., and Lam- ple, G. LLaMA: Open and efficient foundation language models, 2023a. URL https://arxivv http:/wwwwrg/ab//////// 13971.
Mistral AI. Mistral 7B, 2023. URL https::/missstall....
neuss//moouuriinn-miissrrral---
Mistral AI. Au large, 2024a. URL https::/miistral..at
news/mistaal-lagge
Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaci, Y.. Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., Bikel, D., Blecher, L., Ferrer, C. C., Chen, M., Cucurull, G., Esiobu, D.., Fernandes, J., Fu, J., Fu, W., Fuller, B., Gao, C., Goswami, V., Goyal, N., Hartshorn,
Mistral AI. Mistral nemo, 2024b. URL https:::////ist ai/news//iistral-nnnnd
OpenAI. Introducing ChatGPT, 2022. URL https://
openai. htmmaai.coomiinee//chttgtg//

---

Language Models over Canonical Byte-Pair Encodings
A., Hosseini, S., Hou, R., Inan, H., Kardas, M., Kerkez, V., Khabsa, M., Kloumann, I., Korenev, A., Koura, P. S., Lachaux, M.-A., Lavril, T., Lee, J., Liskovich, D., Lu, Y., Mao, Y., Martinet, X., Mihaylov, T., Mishra, P., Molybog, I,, Nie, Y., Poulton, A., Reizenstein, J., Rungta, R., Saladi, K., Schelten, A., Silva, R., Smith, M., Subramanian, R., Tan, X. E., Tang, B., Taylor, R., Williams, A., Kuan, X., Xu, Yan, Z., Zarov, Zhang, Y., Fan, A., Kambadur, M., Narang, S., Rodriguez, A., Stojnic, R., Edunov, S., and Scialom, T. Llama 2: Open foundation and fine- tuned chat models, 2023b. URL https::/aaxxii..rgg 0tss/337.009288
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Attention is all you need. Advances in Neural Information Process- org/abs/
ing Systems, 30, 2017. URL 1706. 03762.
Vieira, T., LeBrun, B., Giulianelli, M., Gastaldi. J. L., DuSell, B., Terilla, J., O'Donnell, T. J., and Cotterell, R. From language models over tokens to language models over characters. In Proceedings of the Interna- tional Conference on Machine Learning, 2024. URL https://arxiv.orr wwt..o////////////////////////// 03719.
Zhao, S., Brekelmans, R., Makhzani, A., and Grosse, R. Probabilistic inference in language models via twisted sequential Monte Carlo, 2024. URL https://arxiv. org/abs/24044 17546.
Ziegler, D. M., Stiennon, N., Wu, J., Brown, T. B., Radford, A., Amodei, D., Christiano, P., and Irving, G. Fine-tuning language models from human preferences, 2020. URL https://arxivv www.:/og/////////e 0011199998999
Zouhar, V., Meister, C., Gastaldi, J., Du, I.., Vieira, T., Sachan, M., and Cotterell, R. A formal perspective on byte-pair encoding. In Findings of the Associa- tion for Computational Linguistics, 2023. URL https: // //aclanthology org/2023 findings-acl. 38.
12

---

Language Models over Canonical Byte-Pair Encodings
A. Limitations and Future Work
Future experimental work. estimate probabilities. We do not have any experiments evaluating any qualitative difference in the sample quality from the canonicalized methods.
A limitation of our experimental design is that we only evaluate our approach's 's ability to
Models overregularize Language models often place a higher probability on a noncanonical encoding of the string than the canonical one. Here is an interesting example from WikiText corpus (Merity et al., 2017):
II xs """A = Robert ter An'nAn'n'n Robert Boulter is an English film , \ 12 television and theatre actor He had guest @-@ starring role on the television is series The Bill in 2000 """ www.eecdeeeuuuff""""
In the case of GPT-2, the conditional probability of the canonical tokenization is only 2.7%, and it is ranked 4th in the (partially enumerated) set of encodings of this string:
An'n .Robert, _B oul ter LF An An Ankn An _Roberr .B aul ter _is Jan JFnglish
_film_ _filll
_television ,and _ttheatee
0.7799:
628 796" 5199 "347" 2852 353 796" 220 198"198" 198" 628 "198" 5199 "347" 2852 353 318 281" 3594 2646 '837" 5581
290 21421
Lactor -. _He _had_ La -guest -
_sstarring _rale _on _the _.elevision _series _hee _aill Lin _20000 -..
8674 '754" 679' 550 '257' 8319 "220" 31'13"3"" 20495 2597 "319" 262" 5581
2168 "333
3941 "287" 4751 '764'229
0.1151: Antn LF _Robert _B oul ter LF - An In Anin An _RRbbert ..B oul ter _is Lan JEnglish _film -. _television ,and Ltthateee
'966 5199 "347'2852" 353 753'796'222 198"119""8""" 628 '198" 5199 "347"2852' 3533'3"33"" 318 281" 3594 "2646" '837" 5581
"290" 21421
actor _He _hadd La gguest _e e ..sttaringg... ..olee __on the ,.television, ,.series _.The _,111 ,,in _.2000
8674 7744 679 550 225'' 8319 14'8"12'31" 28495 2597 "319" 262"
5581
2168 3333
3941 '287" 4751 '764'22
0.0493:
Anin Robert .B oul ter Ja An AnAn In'n Robert _ oul ter .1s Lan E.nglishh .ffinm ..television_.en .ad
628 796 5199 3347 2852 353 796 220 198" 628" 628 5199 "347 2852 353'318 281' 3594 2646 '837" 5581 290 21421
ccctor .. He had La -guest Je 8674 764 679 550 257'' 8319 2488"12'a1
..sstarring rrole _on the .television seeries The _Bi111 Jin .22000 5581
20495 2597 "319" 262"
2168 '38
3941
2287 4751 '764"228
0.0273:
Antn J Robert .B aul ter o An'n Inin In Robert _B oul ter Lis Len Engglishhh _Fiinn wwtlevviiiinnn.... cnd theatre
796" 5199 "347" 2852 35a" 796 228"2222" 628 "188" 5198 "347 2852 353 281" 3594 2646 '837" 5581 298 21421
cactor
Jle _ad La guest _ 8 ..starring... rrlee _on the _.eelevision .series _The _fill _.in 2628
8674 '784 679' 550 '257' 8319 "2488"s 12 "a""" 28495 2597 "319" 262"
5581
2168 "383 3941
"287"
4751 '764'220
0
Antn
Robert
oul ter - in An An'n An Robertt J oul ter Lis Lan _Englishh Fiil - _tleevision Land Ltheatre
628 220 28" 5199 2852' 353 798' 228 198 198" 628 "988" 5198 "347' 2852 353 318 281" 3594 22646 "837" 5581
2290" 21421
Lector u. He had La gguest Je 8674 "784" 679" sse '257' 8319 "2488'12'3" 31" 20495 2597 "319" 262"
sttrriing rrlee .oon the .teleeision ..eries The _Bi11 Jin .22000
5581 2168 "333 3941 '287' 4751 '764'22'
0.0061: 628 796"" 5199 "347" 2852 353'3393 796 198" 628 1988 198" 5199 "347" 2852 353 318 281""" 3594 2246 '87"" 5581
Antn JF Robert _B oul ter JF An AnAn An An .Rbbert JB aul ter Lis Lan JEnglish _film of ,eteleiision and Lheatre
299 21421
Lactor Jle _had La gguest J - 9 ustarring,.. 20495 2597 "319" 262"
urale rrlee _on the _eteeeiiiinn .series _The _Aill _iin _,26
8674 '754 679" s5e 225'' 8319 22488" 2488"12231"
5581 2168 "383 3941 '287' 4751 '764'228
Antn Robert _B aul ter =F An'n In Antn _Rbeert _B oul ter Lis Lan _English _filn_ -. _ttelevisin Land _theatre
0.0032: 628 7966" 5199 2252"252" '333333"" 796 220" 628 198" 628 5199 "347' 285228222 3188"38888 281" 3594 2644 '837" 5581
298" 21421
Lactor -. _e _ad La -guest _e # .sttrring .rale _on _he _eweevieeoo.nncc. _series _hhhe _Bill _in _22000
8674 "754"679" 550 '257" 8319 "2488'12" 12'3"" 20495 2597 "319" 262"
5581
2168 3333 3941
"287"
4751 '764'220
Anin _F .Robert _B oul ter LF Vn In An'n An _Roberr .B oul ter _is Lan JEnglishh _filmm __tellevssion .aaiiisioo__nnd____ _teeatee
0.0011: 628 796" 5199 "347 2852 353' 796 220 198" 198" 628 '198" 5199 "34" 2852 353 318 281 3594 2246 '837" 5581 299 21421
aactor ... _He ..had La ggesst _e 8 ..star ring .role _oon ..the televisioo s.eerees _,The__ _B111 _in _2000 .......
8574 754 679' 558 257' 8319 2448" 12'31" 3491 '1896" 2597 "319" 262"
5581 2168 383 3941 228''
4751 '764'220
0.0002:
Antn JF Robert 628 796" 5199 3347" 2852' 353 796 228 228"198"11 198"198" 628 '198" 5199 "347'2052 205220222 353 318 281" 3594 2646 '837" 5581
oul ter JF - An An AnAn An _.Robert ..B oul ter .is .an .EEglishh _fi1mm ... teeleviiion .add theatre
290 21421
Jactor u. Jle _ad La guest J. e ..sttrring, _role, _oon, _. deee.eeeiision..eeee
The _B111 .in .2280
8674 764 679' 550 '25'' 8219 220 "1''a1"" 20495 2597 "319" 262" 5581
2168 333 3941 228 4751 220 13
UTF-8 Encoding. The very first step in representing text is the choice of string encoding. UTF-8 is an encoding that maps strings of characters into bytes, which is used to store almost every webpage on the internet. The scheme uses a variable- width encoding of each Unicode character that uses between I and 4 bytes, with more common Unicode characters requiring fewer bytes. The UTF-8 encoding imposes additional validity constraints on token strings. In future work, we may extend our work on BPE encoding validity one step further to ensure that the byte string that the BPE string decodes is valid UTF-8 string. For better or worse, UTF-8 decoding errors are typically suppressed, e.g., by the Huggingface transformers library.
Implementation note. Byte-pair encoding (as the name suggests) typically takes bytes as inputs. Note that popular interfaces like huggingface try to make things easier for users by hiding the UTF-8 encoding step that maps strings to bytes
13

---

Language Models over Canonical Bytc-Pair Encodings
from users by exposing only string interface. We require finer-grained control to implement the round-trip test correctly; must avoid encoding and decoding from the text's encoding (e.g., UTF-8). Therefore, use custom implementation of byte-pair encoding. Note that the transformers library does not provide methods to work directly with byte strings.
(rcoode(uuf-8")) b' V' is the encoding of the hugging face emoji
However, if we try to decode the following prefix of the byte string b' 'xxf0x99fxxa' decooee we get an error as it is an invalid UTF-8 string. Note that if we use b' 'xfo xx0 deecdee""ttf errors="ignore" or b' "Xxff\x9fXxxa decodee(uur ("utf-8", "replace") the errors may go unnoticed. Many packages (e.g., transformers and tiktoken) suppress these errors.
Other tokenization models. We limited our experiments to BPE, as it is by far the most commonly used tokenization model (Footmote 5). However, many other tokenizers exist, such as longest-matchh tokenization (used by WordPiece) and other finite-state transduction-basse tokenizers. These other tokenizers can plug directly into our framework as long as they provide efficient membership tests for D. In the case of tokenizers), the membership is straightforward operation on the automaton. We note that D o D, in general- it specifically does not hold for aingstt-match tokenizers.
methods (which include longest-match
More sophisticated inference algorithms. Future work may wish to explore sequential importance resampling (SIR) methods or other sequential Monte Carlo methods (SMC), which have shown great promise as methods for constrained generation from language models (e.g., Lew et al., 2023; Zhao et al., 2024). Sequential importance resampling, for example, provides the computational benefit of not waiting until a complete string is sampled from the local model to resample. works by evolving many string prefixes in parallel. Now, when any given string is "stuck" in a low-probability region, can be probabilistically replaced by another string in the collection. Many SMC algorithms, including SIR, are GPU-friendly.
Distillation. Another interesting direction to explore related to fine-tuning is the distillation of the (approximately) globally canonicalized model y. We could do that by minimizing (L(g]l() using stochastic gradient descent.
Precision vs. recall. It can be challenging to correctly capture all of the constraints that the inputs must satisfy. In this paper, we explored the canonicality constraints that BPE models have. We provided efficient methods for testing canonicality, and we needed to validate those against reference canonicality procedures (as a kind of regression test). It may be impossible to capture every nuance of particular implementation perfectly. And, in some cases, there are even "bugs" or "undesirable" behaviors that the reference implementations have. For example, the pre-tokenization system used by GPT-2 was designed to split the possessive marker ('s) from a phrase like OpenAI system - OpenAI ss]_syste; however, the rule has the following behavior which is likely not intensional OpenAI_Inc: 's_system OpenAI [Inc]] sys_sys it fails to split the possessive correctly because the regular expression used by the pre-tokenizer prioritizes over 's in this example. More generally, reasoning about complicated software system using formal models will always present challenge between fidelity and analytical tractability.
Evaluation on downstream tasks. Our study deliberately centers on a task-agnostic metric-KL KL. divergence. We proved that our canonicalization methods are guaranteed to improve this metric (Propositions and 3) and we quantified the effect empirically ($5). However, many language-model applications are judged with task-specifi metrics that may be misaligned with KL divergence. Thus, an improvement in KL divergence does not guarantee an improvement in the task-specific metrics. Assessing how canonicalization influences concrete reasoning important direction for future work.
each task's 's own evaluation metric-remaing an
14

---

Language Models over Canonical Byte-Pair Encodings
B. Efficient Membership Tests for BPE
This section gives a formal definition of byte-pair encoding (BPE) and novel algorithms for the following membership tests pertaining it:
the canonical set D (see Theorem
the canonical prefix set D (see Lemma 3)
an incremental membership test for single-token extensions, i.e., 8.8' E D given that ò E D (see Proposition 5)
Our key insight is that a token string is canonical and only if all of its constituent bigrams are canonical; see Theorem 1. Thus, our membership test runs in time linear in the length the string-we iterate over all bigrams in the strings and check their canonicality; we call this the bigram test. Moreover, our test simple implement, unlike similar tests given in prior work (e.g.. Berglund et al., 2024; Cognetta & Okazaki, 2024). A consequence of Theorem I is that D = D (see Lemma 3), which means that membership in the set of canonical prefixes reduces to membership in the canonical set."
B.1. Byte-Pair Encoding
Byte-pair encoding (BPE; Gage, 1994; Sennrich et al., 2016) is currently the most commonly used tokenization method, as it has been used in most recent saate-of-the-aeee language models." 20 We formalize BPE as follows.
Definition 4. Byte-pair encoding is pair (2,M) that defines a tokenization model (E,A, We describe the assumptions on ME, and the construction of (E, A. T, below:
a base alphabet of characters (or bytes)
M [d'', (a) (Mn) is the merge list where o' dmy (mm) E Et for m 1,,,, M.
We define the subword alphabet S det "o''''"" (o', oo"
) E M].
We define the token alphabet A such that for each 5 E A, there a unique object (e.g., an identifier) for each distinct element of the subword alphabet S. The reason for this technical detail to avoid confusion between the concalenation of
subwords and the concatenation of tokens.
We define the base encoder T: S A and base decoder k: A bijective maps between the subword alphabet and set of base tokens A C A.
We define the decoder k: A T
E" to be the pointwise extension of the base decoder: k(ō b.) def k(ō1) -M. 5((x)) N)
We define the encoder T: Ex
A in the pseudocode, which is a deterministic string rewriting process based on applying a sequence of merge rules to the current string of tokens until no more merges are available." 21,22
+
def T(01 - "NN):
def rewrite(81 6N): for (a',a") in M N-1]:
5 < I(01) I(ON)
21
while True:
22
for n in 23 if (1((5)),((6) k(6m41)) = o")
17 + rewrite())
18 if 8' = return
24 return 81 8n-1 I(o' o") 8n+2 8N return 51 NN
8 5- 8'
25
Note that the merge rules applied in specific deterministic order to any given string; thus, there is unique way to derive the output tokenization from the input string.
We note that, in principle, the bigram canonicality tests can be precomputed and cached for maximal efficiency. However, we found that to be impractical for models with large token vocabularies. In App. B.3, we provide very efficient method that can test bigram canonicality.
"0See Footnote
We note that can be implemented much more efficiently using careful choice of data structure (see, e.g., Zouhar et al., 2023).
We note that Berglund et al. (2024) refers this incarnation of BPE as the SentencePiece BPE algorithm.
15

---

Language Models over Canonical Byte-Pair Encodings
B.2. Simple and Efficient Membership Tests
Definition 5. We define the of canonical bigrams as
{8-8' 16,8' E (.,((66))) 8.87.
(19)
where yp is the canonicalization function ($2.6).
Definition 6. We define the set of bigram-canonical strings B as strings composed of only canonical bigrams: B c ( BIGRAMS()) C 3)--
(20)
In general, it is possible for a token in the token vocabulary not to be canonical. Such tokens can always be removed from the token vocabulary without changing the result the BPE tokenizer. We assume, for simplicity, that the token vocabulary contains no such tokens.
Assumption 1. For all 8 A, sp()) =
Definition 7. We define the truncated canonicalizationn şr as follows:
26 def Pr (0):
27
01 ON + x(6)
# decode token string
28
((0) + I .. I(ON)
initialize with base tokens
29
for t= 0,..... 1):
g(++1) (e
if g(++1)= 8(4) return 8(t)
return 8(2")
Remark 1. It straightforward verify that vp Pooo as equivalent code for T(((-) where we have added the option of truncating the number of iterations performed in 7 fixpoint iteration loop. Setting T oc, disables the truncation; thus, ip = Poo.
16

---

Language Models over Canonical Bytc-Pair Encodings
Lemma (Canonicalization process synchronization), Suppose that abe DD both ab, be D. Suppose further that b is nonempty. Then, there exists sequence {(az, bt, Ct, de; ex) such that the following equations hold for all t 2 0:
9r (abe) :Pa, (a) Pb, (b)pc,
Pt def
Sd, (ab) Pa, (a) (b) (Pe, (bc) (b) (c)
(21)
Proof. We will prove Lemma by induction on i, and by explicitly constructing the sequence {(ar, by, Ct, de, ee)
Let denote the number of distinct iterations of p(abc).
Base case (Po). In this case, is straightforward to verify that (au, bu, cu, du, co) (0, 0.0.0,0, 0, satisfies Po because each canonicalization call returns precisely the base tokenization of its argument. Thus, Po holds.
Induction step. Suppose Po Pj hold. We seek show that PJ+1 holds.
Since P3 holds, there must exist (at, by, Ct, de, ex) satisfying the equations in Pt. To prove that Pi+1 holds, we will construct (oe+1, 1 C,+1, de+1, 1++1) such that the equations in P++1.
We first observe that at time t, (e(abb)= = a (1) (00 c(t) where
(t) is the tokenization at step of the substring over the characters in a in the canonicalization process for abc
( is the tokenization step f of the substring over the characters in b in the canonicalization process for abc
(t) is the tokenization at step t of the substring over the characters in in the canonicalization process for abc
The only way for this observation to be false is for a merge to straddle the boundary between (* and ((()) or ((t) and clt), which is impossible because of our premise that abc E or both ab, be E 'D. More specifically, there ever were a merge between (!) and (t) then ab and abc could not be canonical, as the final tokenization would not respect the boundary
between a and b. Similarly, if there ever were a merge between b(t) and c(t), then by analogous reasoning, be and abc could not be canonical.
We now turn to case analysis:
1. Suppose t < T, then the (++1)tt step of p(abc) applies to the highest-priority" bigram of a (())) Consider the following subcases characterizing the possible positions for this merge:
(a) The merge is in (1).
Then, (0t+1, b Ct+1, de+1,,e++) (a, + 1, by, Ct de + 1, eq) satisfies Pt+1 because
must also be the highest-priority merge in (t), which is step a++1 of ((a). It must also be the highest-priritty merge in a (1),, which is step de+1 of ((ab).
The other canonicalization processes unaffected, so they copy their position on this step.
(b) The merge is in (())
Then, (0r+1, be+1, 1, C++1,
= (a,, b, + C2 de + e, + satisfies Pa+1 because must also be the highest-priority merge in b(t), which is step bi+1 of (pb). must also be the highest-priority merge in a ((),, which is step d++1 of ((ab).
must also be the highest-priority merge in ((9) which is step e++1 of (bc)).
The other canonicalization processes are unaffected, so they copy their position on this step.
(c) The merge is in c(t).
Then, (01+1, b C++1. (++1) = (a,, br, + 1, 1, + 1) satisfies Pi+1 because
It must also be the highest-priority merge in c!!), which is step c+11 of (pc).
must also be the highest-priority merge in c(t), which is step e++1 of (bc)).
The other canonicalization processes are unaffected, so they copy their position on this step. 2. Suppose T. No merges exist.
Then, (at+1, be+1, C4+1, de+1, e++1) = (ae; be, Ct, de, ex) satisfies Pe+1 because (abe)) pr((abc) (()( (T))((T) (TT), by definition of T' which implies that no further changes are possible and all processes must copy their position on this step, and continue do so forever.
Therefore, Pt holds for all 2 0 by the principle of induction.
Le.. the bigram with the lexicographically lowest pair of (position in the merge list, position in the current token string). Note that there can no ties under this ordering.
17

---

Language Models over Canonical Byte-Pair Encodings
Example This example seeks illustrate Lemma 1. Consider the following three token strings from the GPT-2 lokenizer:
token 30081
ized
268 12
1143
For these tokens, we have ::(ab))= = re- tokenized.. Our worked example will focus on only the first equation Pa (repeated below for convenience), the other equations behave very similarly:
:P((ab)) Pu. (a) (b)
Before moving forward with the example, we note that each token during the canonicalization process will be rendered tree because is a convenient representation for showing which merges were done build each of them. For example, inputs b, and represented by the following trees:
a
b
C=
e
z
K
e
n
Each row in the table below corresponds time step t, and the content of each column is the status of the canonicalization process at that time. We mark cells that are copied from the cell immediately above them with dash (-).
(abbb)
Lo. (a)
Sh,
Pe, (c)
d
1
e
n
t
e
i
d
4
t
e
O
k
e
n
5
K
e
n
Z
P
6
K
u
2
z
d
7
e
8
e
We that at every step t, the equation (abe) Pa, (a) Pb) (c) is satisfied for appropriate choice of (a,, by, ct). Specifically, we count the number of non-copy actions in each row. In the example, for = 8, we have (at, b,, c.) = (1, 41). This example also allows us to see the case analysis used in the proof for the location of the merge in action.
2'We give a more formal presentation these trees App. B.3.
18

---

Language Models over Canonical Byte-Pair Encodings
Lemma (Interlocking Canonicalization).
Va De A+, : abe + ab be D
(22)
Proof. Fix a E ,", A+, and e E A' arbitrarily.
We will consider the direction of the bi-implication separately.
Case (=). Suppose that abc D. Then, Lemma 1 gives us sequence {[a bi, cz. de, ex)) such that the following equations hold for all 2 0.
Pr(abc) Pai (a) (b) Pd. (ab) Pa. (a) (b) Pe. = (b)
Pt def
(23a)
Now, consider (ar, by, Ct dr, eT), which gives
@r (r((bb) = Par (a) Per (c) Pdy (ab) Por (a) Pbr (b)
(23b)
Per (bc) Pbr (b) (c)
which implies the following because, at time T, each of the canonicalization processes has reached its respective fixpoint:
((abe) (b)())(b)(())
x(ab) ((a)p(b)
(23c)
(bcc) = ((b))(())
which implies the following because each call to must return the canonicalization of its respective argument:
p(abc) abc
p(ab) = ab
(23d)
p(bc) = bc
Therefore, ab and be are also canonical.
Case (-). Suppose ab, be E D. Then, following an identical argument as the -accse, we can see that abe E Thus, the bi-implication holds; thus, Lemma 2 holds.
19

---

Language Models over Canonical Bytc-Pair Encodings
Theorem establishes that BPE token string is canonical if and only if all of its bigrams are canonical, Theorem 1. D B.
Proof. We seek to prove, for all A", that 3 ò B. We do this using induction on prefixes of and Lemma 2.
Choose ô = -1 NN A A arbitrarily. Let the induction hypothesis P(1) be that dgg D + ògi B.
Base cases. We first prove P(O) and, if [6] 2 1, P(1).
Case P(0). To prove P(O), we seek to show that òco = =E D = 8go = = B. Both sides of the bi-implication are always true: ē E 'D because (p() = ((x())) r()) E; and E E B because it contains no bigrams, hence it is vacuously true. Therefore, P(O) is true.
Case P(1). To prove that P(1) is true for cases where |6| 2 1, we seek to show that δ=ı = 61 E -D== و=س =0 E Again, both sides of the bi-implication are always true. By Assumption 1, we know that d1
true. Since ò has no
bigrams, ò1 E B is vacuously true. Therefore, P(1) is true.
Induction step. Assume P(i), that dgi E DD + dz: E B, where i 2 2. We seek to prove P(i + 1), that dgit1 E D = 8 sit+ E B. We prove each direction of the bi-implication separately.
Forward. We seek to prove 05i+1 ED
= =D=> 85t+1 E B. Assume d5i+1 = 0 E D. By Lemma 2, we know that 15 E DD and 5,61+1 E D. Since 8 15 E D, by P(i), we know that 8 E B. Since 8 85i-154 B and 5,65+1 D, all of the bigrams 651-15 8 are canonical, so 851+1
Backward. We seek to prove 852+1 B = 854+1 D. Assume 8ea+1 =dgi-1d;d2411 E B. Then Rgi-10e B, because it contains only subset of the bigrams in 8 Then, by P(i), we know that 8gi-1 E D. From 0 E B and Def. 6, we know that 5,6;41 E D. Since ògi-1d; E 'D and 0,5,41 E D, by Lemma 2, we know that 150-10,0411 = 8 E D.
By induction, we know P(N) is true, so ô E D + ò E B, and the proof is complete.
Note that if string with length less than equal has no bigrams; thus, the property is trivially satisfied, i.e., all length-zero and length-one token strings are canonical. latter is thanks to Assumption 1.
20

---

Language Models over Canonical Bytc-Pair Encodings
Lemma 3. For BPE, 26 the set of canonical strings is prefix closed, iee, D D.
Proof. We prove D D and D CD.
Part (D D). Obvious by definition of D.
Part 2 (D D).
1. Suppose 8 E D
2. by definition of D. there is 8' E D such that 8'
3. by Theorem 1, the bigrams of 8' are all canonical subset of those of 8', they also all canonical 5. since the bigrams of 8 are all canonical, by Theorem 1, 6 E D
4. since ō < 8', its bigrams
Therefore, B D.
More generally, Lemma holds any tokenization model with bigram-based canonicality test (i.e., 5 D BIGRAMS(5) C.B
21

---

Language Models over Canonical Bytc-Pair Encodings
B.3. An Even Faster Bigram Test
BPE derivations. Our canonicality test involves the inspection of the merge structure within tokenization of string. For that purpose, define the derivation of given string ((r) string of trees t tt where each in (for 1,.., N is binary tree. For our purposes, (binary) tree is recursive data type composed of either pair of trees or base token. The pseudocode below shows how can be augmented to produce these derivation trees for given string:
33 def ((OI t t ((-)()))-TT0N))
19 def step_ dtep_derivation(i: (x
40 for (a', E EM: for n E NN 41
34
35
while True:
t' < step_derivation(t)
42 if (1s(tn), k((n+1)) = (o', "0))
if t' =t: return t+t t'
return 11- Ln- (bay bn+1) In42 return t1.t
Note that y(-) is an adaptation of r. The difference is that has been replaced with function that creates trees instead of replacing them with tokens. We have also extended return the subword denoted by the derivation.
For each token 8 E A, associate with it unique canonical derivation (6). However, we note that when 17(6)] > 1, it means that the token does not canonically tokenize to itself. Assumption ensures hn6)] = for all ò E A.
Additional notation.
For notational convenience, we define the following:
For any EEE let Iet.eMM MM[]] denote the following:
If é Σ. return its position in some fixed, arbitrary ordering of Σ.
If Σ+ return the rank position of the merge l in the merge list plus |>] (as offset), and de if & is not in M.
We extend M[t] to trees & as follows.
For tree E A: M[ M[x(t).
For tree of the form = s"): M[t] M[ssss M(ss()),<ss))))
We define the following ordering relations on merge rules and subtrees: We define
<r - Mi4 < M[r]. We define
i >> r, & S r, and l 2 analogously.
Given token 8 A, we define the leftt spine S(r( of (6) to the ordered set containing the root node and its left descendants (ordered from root to leaf); and, define the right spine R()(5)) analogously (for right descendants).
In given tree, define the function that returns the parent node for any of its subtrees.
At a high level, we that token 8" conflicts with bigram 8-5' if and only if 8" applies with an earlier rank over any overlapping span of the same character string. More formally, we that 8" (nontrivially) overlaps with ó and 8' and only if
Intuition.
x(6) "n On
(24a)
x(6') ont1 ON
(24b)
<(6-0') On-0n-
(24c)
x(6") 04-'a, oj where 1 sisn<jsn
(24d)
However, for 8" conflict with 8-8", would need to include a merge over the span de oy that blocks least one merge in and 8' from occurring in (=5-8").
(8)
76')
(5")
(8')
ip
01
Opr "4 Jj
NN
0j
O
We say that node p left descendant of node q if p is the left child of g or left descendant of the left child of q. We define the right descendants p in an analogous manner.
22

---

Language Models over Canonical Bytc-Pair Encodings
In the diagram above, the derivation for the bigram d-8' is denoted by the juxtaposition of triangles, one for each token's derivation tree. We have denoted the canonical derivation trapezoid, as it is generally the union of multiple triangles; there may be 1, 2, or more tokens in the canonicalized bigram (06-8'). In orange, we have drawn third triangle for the conflicting token 8". We note that 7(8") must intersect ((6) at a node along its right-spine R(r(5)), and it must intersect (((") at a node along its left-spine S(7(""). In the diagram, the and s' represent the subtrees at respective points of the intersection with the hypothetical conflicting tree. The orange are from s to is used to show that any two nodes along the left and right edges could, principle, be a conflicting tree. Crucially, however, the rank of the merge pair must precede the competing merge pairs present in the existing tokens ó and 8'. We make this more precise below.
Definition 8. token 8" conflicts with the bigram 6-8' if and only if (8") is a subtree of ((p(668')) (which may string of trees) but not subtree of either (6) or (8").
We can find a conflicting token by exploiting the structure of the tokenization algorithm.
Definition 9. Let 8" be a token such that 7(8") = (s. s for some $ E R(((()) and s' E S(7(8')). We say that 8 is a minimal conflict for the bigram 8-8' if and only if (s) > {s, 8²) S <s').
The reason why 8 identified by Def. 9 is minimal is that its definition identifies the earliest possible deviation, i.c., the earliest merge rule that could apply on their shared string "1 T" NN that was in the existing merges and 8'. Note that the asymmetry < versus is precisely what breaks ties between equal rank merges in favor of the left-most match, prescribed in the procedure for that was provided in Def. 4.
Below is an algorithm for finding the minimal conflicting tree between 8 and 8', if one exists.
def Find_conflicte :
16
t (0)
47
L 0c
48
while True:
49
1' + (6")
50
R R+ 00
51
while True:
52
if T>> M(( < R: return (1,2") # conflict
if a(t') E break # t' is a leaf
53
54
R+M[[
35
(+,_)+ + +
descend the left spine
56
EE break # is a leaf
57
M
58
(.1) -
# descend the right spine
return None
The Find_conflict algorithm finds the minimal conflict between a pair of tokens 5 and 8' (if one exists). We note that useful consequence of Assumption 1 is that we do not need to check subtrees that exist off of the spines for conflicts, making our procedure more efficient than computing the canonicalized string from scratch, e.g., by rumning t on the decoded string =(6-5"). Instead, our algorithm searches for a minimal conflicting tree: either stops once it has found such a tree, or has exhausted the limited options for such a tree. Finding the minimal conflict (if it exists) is also faster than computing the entire canonical tokenization (ōō-"", it only requires finding the first difference rather than completely building the canonicalized bigram." 29
Definition 10. We define + AA A as the following relation on pairs of tokens:
(6,,8") del (finnd_cofllict((..8 None)
(25)
Please refer back to Fig. 2 for examples.
2e that the find cond_cofflict algorithm can he efficiently vectorized so that it computes the complete vector of valid tokens very efficiently. We will provide Py PoTchh implementation in our public code release (upon publication).
23

---

Language Models over Canonical Bytc-Pair Encodings
The proposition below establishes that & provides correct membership for the of canonical bigrams B. Proposition 5. ( 8") - 5.6' E B
Proof. Observe that ( + 8-0' E B) = (-4(6,8) proposition by proving each conjunct separately.
= 6-0' $ B) A (-0088))
= ô-0' $ B). We will prove the
Part (- 8.8' E B). 1. Suppose- -0(6,8',
8'). Then, there exists conflicting pair (s, find_conflict((;0)) i.e. (8,5)) satisfies x T()) ss, TT')). Below is schematic representation of such conflict:
7
7(8))
conflict (8,
((s)
8 S (s')
14
2. Thus, the conflicting merge (s, s²) would have been preferred by 7 if it were on the character string x(6-8"):
{8,
A1
A
the conflicting merge blocks both of the merges below because π (s) = (Me, s) > (8,5") and (T') = (6', 2 (.)
(
π T(s')
P1
ME
14
The existence of this intermediate step means that is impossible for 6-8' to be a canonical bigram; thus, 8-8' $
Part 2 (-0(0)8") 5-8' & B).
1. Suppose 8-8' & B. Then, =08-0") + 8-8', by definition.
2. Then, there must exist conflicting merge (s, s") as subtree in (55-8') that blocks 8-8' from being built. Now, because both and 8 are canonical in isolation (Assumption 1), the conflict (s, s') must straddle the boundary between the å and 8':
(8')
This implies that must be subtree along the right edge of å and s' must be a subtree along the left edge of 8', as those precisely the only ways that the straddling merge block 8 and 8', it would need to satisfy TTs) > (s,8") S *s').
under our cireumstances. Lastly, for (s, to
3. This characterization is equivalent to (6,66')
Note that ss (3)) enforces the left-most merge preference in BPE's encoding procedure т, i.e., in the of tie between overlapping merges the same rank, left-most merge is taken.
24

---

Language Models over Canonical Byte-Pair Encodings
B.4. Connections to Canonicality Algorithms
Definition 11. We can describe the set of canonical tokenizations with the following finite-state automaton:
states A
alphabet = A
8' - 8' 8.8' E E
transitions {6
initial = A
accepting
Note that we never construct the automaton.
Generality. Our method works under broader set of assumptions than Berglund et al. (2024); Lindmark (2024), as they require the merge list to be proper. This condition is, in fact, restrictive: the Llama tokenizer (used in our experiments) not proper, but the GPT-2 tokenizer is proper.
Practicality. The automaton has V nodes and < V2 edges where V |اه, In practice, the machine very close to having V edges (even after DFA minimization!) because the transitions do not rule many tokens. This means that the explicit machine is enormous. For example, GPT2 has 50K states and nearly 2,500,000,00 edges, making it way too large to build. Storing the edges that are absent is significantly more efficient. On the other hand, our version never builds the machine, so the memory complexity is not problem. It is also possible to use more sophisticated automata representation that allows for failure Iransitions; we refer the reader to Cognetta & Okazaki (2024); Lindmark (2024) for further discussion of the technique.
25

---

Language Models over Canonical Byte-Pair Encodings
C. Supporting Proofs and Lemmata
Proposition Suppose that the tokenization model (T, Ki E, A) is exact, then
VO E A δ E ( =
(26)
Proof. Fix arbitrary 8 A We consider each direction separately:
Part 1 (8 E D = (()) 8):
1. Suppose 6 E
2. = do E ; =((o) by definition D
3. = x(r(or) o by exactness assumption
4. T()(T(o))) = r(o) because is function
5. = T(x(6))= = 5 substitute r(ar + 5
6. - x())= = 8 by definition of yp
7. Thus, this direction holds.
Part 2 (8 E = -6) 5);
Suppose <0()) =
2.
(n(())
3. 30 :': 6 = T specifically, a T(0)
4. = 8 E D by definition of D
5. Thus, this direction holds.
Since each directions have been proven, the proposition holds.
Corollary 1.
D (x(()) (8)
(27)
Proposition 7. Let (T) be exact. Then, (r, K) is a bijection between (2", D).
Proof. The bijection follows directly from the following:
Exactness means Yo E E": k(((or) =. Proposition 6 ensures that Vō E D: ((x(6)) 6.
Thus, we have bijection, and the proposition holds.
Proposition 8. For an exact tokenization model (E, A, T, R.), the canonicalization operator is idempotent, iee.
(0)) 8' = <p(8)) 8' for all d, 8' E A*
(28)
Proof. The proposition is equivalent ((p(())) = :(8) for all E
Fix 8,8' A arbitrarily.
1. Suppose ((0)= = 8'
2. - ><((0)) = 8' by definition of 9
= T(x(T(x(6))) = T()(6')) because 7 and x are functions
= T(((f(x()))) (x=('') by exactness
6. ((<(0))=(<((0)))
substitution 8' + (0) 7. x(0)= p(z()) by definition of
26

---

Language Models over Canonical Bytc-Pair Encodings
D. Proofs for Section 4 (Canonicality by Conditioning)
Proposition 1. Assuming that the true distribution over tokens p is canonical, the globally canonicalized model guarantees the following reduction KL divergence:
KL(P's Pa) KL(p's g
log
Proof.
KL(P's (1)) Σ (5) log P1(0)
(29a)
9(6)
SEA
PA (6) E D)
--H(p') Σ (6) log
(29b)
0
--H(p') Σ (0)
E 1o
Σ (8) log
(29c)
SEA
SEA
SEA"
--H(p')= Σ
(6) log (6) log Z
(29d)
НEA*
= KL |/ + log
(29e)
Now, the proposition follows by basic algebra.
Proposition
11+1
7 (6
{ - p0)) E D}
(10a)
(6)
Thus,
we( Pa(0)
1 E D)
(10b)
{(6)
Proof.
|8]
((5) 7 (FOS 8) II
7 (5, 8cc)
(30a)
t=1
PA (ROS
(5) E D} [8]
(5. 8et) 01 E D)
(30b)
7())
7 (62c))
[8|
18|+1
-1
Pa (FOS 8)
II
PA (5 8c))
118 E DJ II
18 DD
πI
(B
(30c)
(=1
t=1
18|+1
(60 D)
II
(6cr)
(30d)
Proposition 3. Assuming that the true distribution over tokens PAA is canonical, the locally canonicalized model & guarantees the following reduction KL divergence:
KL(p') |l PAA) KL(p1 ( = E
[log w. (6)]
(11)
8~pp
27

---

Language Models over Canonical Byte-Pair Encodings
Proof.
KL(P's 10)= Σ P1( log (o)
(31a)
{(0)
SEA-
=-H(p's) Σ
Pa (ō) (())
(31b)
SEA*
Pa (6) E D) wr(6) by Proposition 2
=-H(pA) Σ
PA (o) log
(31c)
by assumption
--((A)) Σ DEA
PA (1(
E 11g D) + Σ PA lo) log we
(31d)
BEAL
SEA
= KKLP's |pa)+ +
E
llog wx(
(31c)
8~pA
Now, the proposition follows by algebra.
Proposition 4.
(5)1) D} {(0)
7 = E [w>(o)]
(12)
Proof.
2 = Σ PA D}
(32a)
(6
(32b)
RED
Σ 8(8) (6)
(32c)
E(O)
SED
(
Σ (())
(32d)
(o)
PA
BED
Σ ((5) (
(32e)
SED
E (6)
(32f)
28

---

Language Models over Canonical Bytc-Pair Encodings
E. Frequently Generated Noncanonical Bigrams
Because BPE canonicality is determined entirely by bigram constraints (App. B), a natural question is: Which of those constraints does language model violate most often? To find out, we catalogue the model's most frequently produced noncanonical bigrams in hopes of revealing some specific aspects of BPE canonicality that it struggles model.
The bigram frequency is defined as
1
(
def
Σ
110-8' = a
E 8mpa
016 a.
(33)
8mpa
6-8' (BIIRAGGA)))())
We must estimate y because computing μ exactly is infeasible. We do so by sampling: Given sample 8(1), the following is an (unbiased) Monte Carlo estimator:
((M) ltd
Pa.
M
18(m) -1
(a 3)
def
(m) (m)) 1 100 0
a-B
(34)
M m=
[+1
t=1
However, we found that using the following (unbiased) Rao-Blackwelliize Monte Carlo estimator provided better coverage for noncanonical bigrams, as they are individually rare:
M
[8(m)
(a-3)
Σ m=1
I (5 (m)) 8' = 0z pp
(m) (441)
(35)
M
S'EA
The Blo-Blackwellized estimator uses the exact conditional expectation over the token at step + 1 rather than the single i+1 providing significant variance reduction with little effect on the running time.
sample token o ((m)
Experiment. Tab. 1 and 2 show the noncanonical bigrams (i.e., a-3 & B3 that we have estimated (for each model) to be the most frequent via with M 2000 samples.
Observations and takeaways. Inspecting the tables, we see that large portion of the frequently generated noncanonical bigrams are frequent substrings that have been tokenized incorreetly. for example, _normal ized substring_ _normalized which all things should tokenized _normalized
'114 corresponds to frequent
39279 Hooeeer, there does not appear to be
clear pattern for why these models struggle with these specific bigrams over others; further investigation needed.
29

---

Language Models over Canonical Byte-Pair Encodings
GPT-2 Small
GPT-2 Medium
GPT-2 Large
Bigram
Freq.
Bigram
Freq.
Bigram
Freq.
eros
3.86e-3
\xc21xa6
4.58e-3
Axc2Xxa0
4.67e-3
380
27498
220
1849
220
1849
J
Pr
1.99e-3
neck er
2.36e-3
sson
2.81e-3
42668
263
'72
Be
ech
1.94e-3
ands
2.33e-3
.5A 14719 '36
1.96e-3
2855
1746
1.66e-3
1.73e-3
_Bul E
1.71e-3
35841
'86
'685
1.59e-3
11
8.73c-4
\xe2\x88\\x44
968
1.36e-3
1.56e-3
8.10e-4
Ans ys 28038
1.18e-3
2297 7723
2937 '32
'893
1.35e-3
go
7.68e-4
upp 2211 228
6.24e-4
35 144
2188 334
python
29412 88
1.21e-3
301 '37357
rush
6.81e-4
11
5.93e-4
1.20e-3
..coll ide
5.91e-4
udd
5.32e-4
599 '83
2927
485
449 4185
insspcc
9.64e-4
BBackk hawks
5.82e-4
ppolite
4.84e-4
10184
223
2619
27221
23507 '386
9.56e-4
4.52e-4
4.08e-4
3628 47
2797 '81
278 '78
EF
OR
9.34e-4
ned lated
4.31e-4
stan bul 14192 156665
3.97e-4
25425
'1881
1158
'1293
.cc 1ling
7.36e-4
4.01e-4
3.97e-4
3978 '5
2905 4386
18604 '12
nornall
ized
5,78c-4
ging
3.75e-4
_cancel ed
3,92e-4
3487
1144
519 2667
14241 276
_een acide
5.34e-4
D
3.11e-4
_Cnngress nan
3.44e-4
5215 16207
35 '403
3162 '885
_V 8g
4.70e-4
.Bur
2.41e-4
JESP N
3.43e-4
569 518
5481 '381
9428
rrong ful
4.46e-4
exin
enia
2.39e-4
ski pped
2.88e-4
2642
39366 22885
20545 14496
ab us
3.56e-4
Che
wan
2.27e-4
.eat en 4483
2.62e-4
397 385
7376
'814
An nie
3.46e-4
x
2.27e-4
-repair
ing
2.51e-4
1052
39568 '87
9185
2278
.provision
al 2.82e-4
Che wich
2.26e-4
m alogy
2.29e-4
Table Most frequently generated noncanonical bigrams generated by GPT-2 models.
30

---

Language Models over Canonical Byte-Pair Encodings
Llama 3.2-1B
Llama 3.2-3B
Llama 3.1-8B
Bigram
Freq.
Bigram
Freq.
Bigram
Freq.
1xc2\xa6lxx2\xet
Xxxe23xxae
5.15e-3
\xe31x88'xx00
\xe31x88lxx8
6.41e-3
\xe31x881x80
9.60e-3
9421
23249
23249
23243
23249
1xc2ixaë
1xc21xa0
3.06e-3
1xc2|xa8
1xc21xa8
4.64e-3
Rivers ide
3.46e-3
3633
2.04e-3
1.86e-3
.anthrop ony
1.13e-3
'19
.c
6.67e-4
ende
1.60e-3
el ta
6.92e-4
522 3423
'85
2629
6.33e-4
<(((
sart
1.54e-3
K 42601 '42
4.55e-4
2279 "790
11861
22996
2.60e-4
bent
1.07e-3
Axc2vxa
\xc2\xa0
4.22e-4
12258 11328
938 '939
4194
4194
2.47e-4
\xc2Xxae
9.16e-4
Vxc2ixae
3.27e-4
58745 278
187958
'200
4194
220
_Ind
2.10e-4
\xc2\xa0 \xc2\xa8 4194
5.75e
YA
3.05e-4
2314 '72
4194
27542
'87582
2.03e-4
5.50e-4
YY
2.70c-4
12250 7242
751 '83
27542
10026
ERIC
2.03e-4
\xc2\xae
3.52e-4
_nebbr
2.67e-4
37 37816
17529 2228
31819
14997
vol 12821 2111
2.03e-4
3.49e-4
phet _Pra
2.25e-4
12682 268
1322
22718
cole
2.00e-4
2.32e-4
And
1.67e-4
56745 '598
18
3112 '88
ERICA
1.93e-4
\xc2/xa0 17529
Axc2\xa0
2.29e-4
ens
1.37e-4
37 196399
4194
548 '229
arm ae
1.60c-4
M ovie 28112
1.62e-4
\xd8)>ab2xxx80xbbee xxblit \xd1/x96 (x96
1.29c-4
2227 '684
1646
164471
27385
F ORIA
1.53e-4
ip les
1.1le-4
_Sou 1s
1.29e-4
37 191118
575 645
9424 4485
_SER IES
1.43e-4
ReSharper ed
1.07e-4
Janthrop
1.11e-4
14311 '5482
53255
229
41.488
M OST
1.20c-4
atty
1.07e4
GE 1
1.03e-4
4327
23758 '83
11010
_beg ins
1.13e-4
collections
1.03e-4
.II van
9.89e-5
2197 1354
721
52237
358 11682
Serve
9.67e-5
1p ple
1.01e-4
_diff usion
9.33e-5
12 166155 61521
575
698
3722 7713
IR CN
9.33e-5
_G hana
1.01e-
ACC ORG
9,01e-5
'715
Table 2. Most frequently generated noncanonical bigrams generated by Llama models.
31


Reviews:
[{"review_id": "6iarV1UwGb", "reviewer": "Reviewer_99cZ", "summary": "This paper examines a key limitation of current language models: the fact that they allocate probability mass to token sequences that are impossible given their tokenizer. For example, for GPT4's tokenizer, the token sequence __t_, _he_ will never occur (since \"the\" is tokenized as __the_), yet GPT4 assigns a non-zero probability to it. The authors provide a formal characterization of this problem as \"non-canonical\" token encodings and introduce two approaches to enforce canonicality. They conduct a small series of experiments, finding that enforcing canonicality improves the likelihood of unseen data.\n\n### Update after rebuttal\n\nI continue to believe that this is a strong paper that merits acceptance, especially if the authors follow through on the commitments made during the rebuttal.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### General Response\n**Clarity and notation improvements**: Several reviewers pointed out that our mathematical presentation, although precise, could be more reader-friendly in various places. In the next revision, we will include more reminders about notation and add several clarifying remarks where beneficial.\n\n**Experimental setup and discussion**: We recognize that many of the reviewers found our experiments section excessively terse. We completely agree and will seek to improve the readability of this section in the next revision, which will be easier with the additional space. \n\n**Evaluation of downstream accuracy**: Our initial submission focuses on a theoretical characterization of the problem and our proposed solutions. As such, our evaluation was mainly focused on the task-agnostic measures of (a) the rate of canonicality in language models and (b) the effectiveness of our proposed algorithms for enforcing canonicality. However, we agree with the reviewers that including some evaluation of the downstream effects of our canonicalization methods will considerably strengthen the paper.  We will investigate the feasibility of extending our evaluation to include some common LM reasoning benchmarks, e.g., HellaSWAG and GLUE.  If the reviewers have other/better suggestions, we kindly ask that they share them.\n\n\n### Response to Reviewer 99cZ\n\nThank you for your review, kind words, and excellent suggestions for additional discussion and deepening our evaluations.\n\n> Essential References Not Discussed:\n\nThanks for these suggestions. We will use them to contextualize our paper better in the broader tokenization literature.\n\n> Other Strengths And Weaknesses: I enjoyed reading this paper. It provides a rigorous theoretical treatment of a problem that has been floating around in the tokenization literature for a while; its insights could inspire a lot of follow-up work. The paper is also very well written -- I could not spot a single typo.\n\nThank you!\n\n> My main concern is about the missing breadth of the experimental evaluation, but this might still be acceptable for a paper whose focus is on a theoretical contribution.\n\nPlease see the general response.", "claims_and_evidence": "The claims in the paper are supported by convincing evidence: the theoretical analysis is sound as far as I can tell, and the experiments support the conclusions from the theoretical part.", "methods_and_evaluation_criteria": "The methods make sense, but the evaluation has certain limitations: it does not consider to what extent enforcing canonicality affects performance on downstream tasks. I think examining this would be important, as it would give an indication how valuable the paper's insights could be in practice.", "theoretical_claims": "I checked the theoretical claims and could not detect any issues -- the analysis seems well-motivated and sound.", "experimental_designs_or_analyses": "I checked the experimental analyses and could not detect any issues, apart from the fact that they are very short, and a more extensive evaluation, especially with respect to downstream tasks, would have been desirable (see above).", "relation_to_broader_scientific_literature": "The findings of the paper constitute a significant departure from prior work; the problem of alternative tokenizations of the same character string is well known in the literature, but the probabilistic treatment, as well as the proposed approaches for canonicalization, are novel as far as I can tell.", "essential_references_not_discussed": "There is not any _particular_ reference I am missing, but in general the paper could be better contextualized with respect to other papers that examine alternative tokenizations of the same character string. For example, there has been quite a bit of work examining the effects of non-canonical but morphologically correct tokenizations. The fact that all these studies have been dealing with a problem that only this paper characterizes in a theoretical way would further underscore the relevance of the findings.\n\n[Different Tokenization Schemes Lead to Comparable Performance in Spanish Number Agreement](https://aclanthology.org/2024.sigmorphon-1.4/) (Arnett et al., SIGMORPHON 2024)\n\n[Improving Tokenisation by Alternative Treatment of Spaces](https://aclanthology.org/2022.emnlp-main.786/) (Gow-Smith et al., EMNLP 2022)\n\n[Superbizarre Is Not Superb: Derivational Morphology Improves BERT’s Interpretation of Complex Words](https://aclanthology.org/2021.acl-long.279/) (Hofmann et al., ACL 2021)\n\n[Greed is All You Need: An Evaluation of Tokenizer Inference Methods](https://aclanthology.org/2024.acl-short.73/) (Uzan et al., ACL 2024)", "other_strengths_and_weaknesses": "I enjoyed reading this paper. It provides a rigorous theoretical treatment of a problem that has been floating around in the tokenization literature for a while; its insights could inspire a lot of follow-up work. The paper is also very well written -- I could not spot a single typo.\n\nMy main concern is about the missing breadth of the experimental evaluation, but this might still be acceptable for a paper whose focus is on a theoretical contribution.", "other_comments_or_suggestions": "You use two different citations for Gage (1994).", "questions_for_authors": "Is there any principled reason why you did not conduct any evaluation on downstream tasks?", "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": "5DfSAZNXVj", "reviewer": "Reviewer_SszZ", "summary": "This paper addresses the problem of non-canonical tokenization, which arises when there are multiple tokenizations that decode to the same sequence of input characters (all of which are assigned some probability by a language model), but only one is ever produced by the deterministic tokenizer. The paper asserts that this is a problem, because it prevents the language model from properly learning the ground-truth distribution over sequences of tokens. They present two approaches for alleviating non-canonical tokenization. The first is a test-time strategy which does not require any extra training and generates text conditional on the canonically constraint, while the second requires training to ensure canonical tokenization outputs.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### General Response\n**Clarity and notation improvements**: Several reviewers pointed out that our mathematical presentation, although precise, could be more reader-friendly in various places. In the next revision, we will include more reminders about notation and add several clarifying remarks where beneficial.\n\n**Experimental setup and discussion**: We recognize that many of the reviewers found our experiments section excessively terse. We completely agree and will seek to improve the readability of this section in the next revision, which will be easier with the additional space.\n\n**Evaluation of downstream accuracy**: Our initial submission focuses on a theoretical characterization of the problem and our proposed solutions. As such, our evaluation was mainly focused on the task-agnostic measures of (a) the rate of canonicality in language models and (b) the effectiveness of our proposed algorithms for enforcing canonicality. However, we agree with the reviewers that including some evaluation of the downstream effects of our canonicalization methods will considerably strengthen the paper.  We will investigate the feasibility of extending our evaluation to include some common LM reasoning benchmarks, e.g., HellaSWAG and GLUE.  If the reviewers have other/better suggestions, we kindly ask that they share them.\n\n### Response to Reviewer SszZ\n\n> citation or evidence\n\n\"Easier\" is a bit open-ended here. One thing that is clearly \"easier\" is that training runs faster.  Some have conjectured that tokenization makes it \"easier\" to learn long-distance dependencies as the distance between tokens is shorter than the distance between (say) characters.  We will look for some citations to strengthen this claim, and we will rephrase it.\n\n> additional evaluation\n\nPlease see the general response.\n\n> marginal decreases with scale\n\nIndeed, we did see in the case of GPT-2 (small, medium, large) that increasing model size/accuracy improves the canonicality rate.  However, we also saw in the case of Llama that the canonicality rate is very low.  We will include comparisons with the larger Llama models to see how the trend generalizes to the case of Llama.\n\nWe also note that the longer the generated sequences are, the higher the noncanonicality rate becomes.  We will extend our canonicality rate experiments to include longer sequence lengths to better illustrate this point.\n\n> the ultimate goal\n\nLooks like you got cut off on that last sentence.  I will attempt to complete it in order to reply.  I suspect you were asking, \"How can we be sure that canonicalizing the LM helps us generate high-quality text?\"  This is a great question and one to dig into more in future work now that we have developed the machinery to answer it.  It is closely related to the general response about downstream evaluation.\n\n> Appendix B\n\nGreat suggestion!\n\n> “is a prefix of”\n\nSorry, for the oversight\n\n> Where is g with a right arrow on top of it defined? If line 229, then would recommend to not use it before it is defined\n\nApologies! Eq. (11b) should have been a def=\n\n> Figure 2\n\nYes, they are token sequences paired with their token ids.  The caption \"The table shows short examples of canonical and noncanonical strings …\" should be revised to say TOKEN strings.\n\n> ϵ\n\nε is the length-0 string, defined in §2.1. We will add a reminder here, e.g., a pseudocode comment.\n\n> confusing to use ℓ\n\nWe thought that ℓ for \"local\" and g for \"global\" made a good mnemonic. Do you have another suggestion? We use $\\matcal{L}$ for the loss.\n\n> arrow on top\n\nWe will explain our notational conventions. The arrow means that the function takes a prefix of a string rather than a complete string.\n\n> Do 5.1 and 5.2 use the “conditioning” method, and 5.3 the “fine-tuning” method? This could be made more clear/explicit, particularly 5.1 and 5.2\n\nCorrect. We will improve the writing of section 5.\n\n> 1. model architecture\n\nThe change: we take the transformer's output layer, which is a softmax over the entire vocabulary, and modify to sums over the canonical tokens given the prefix rather than all tokens.\n\n> 2. ... which phenomena?\n\nThe \"phenomena\" we had in mind was *any* phenomena in language. So, the idea is that if the LM doesn't have to use its representational capacity to learn canonicality, then it could use its capacity to represent something else that helps it predict the next word better.\n\n> 3. non-deterministic tokenization\n\nIndeed, this is a possibility. There was a lot of interest in the early days of BPE in training with subword regularization, e.g., \"BPE dropout\" – the hope being that training on lots of different tokenization would provide a useful kind of data augmentation.  However, this idea is not used by any of the state-of-the-art large language models (see footnote 5).\n\n> 4. Byte Latent Tokenizer\n\nUnfortunately, we are not sufficiently familiar with this method to comment.\n\n> 5. additional evals\n\nSee general response", "claims_and_evidence": "L140: “The tokenization is used in practice because modeling (short) token strings is easier than modeling (long)\ncharacter strings. Commonly used tokenizers—in particular, those based on byte-pair encoding (BPE; Sennrich et al., 2016; Gage, 1994b)—have this property, which is why they are widely used.” Is there a citation or evidence for this claim?", "methods_and_evaluation_criteria": "Perplexity makes sense as a first evaluation, but additional evaluation datasets — which get at the quality of the outputs, not just the perplexity (so e.g. in-context learning tasks, math tasks, etc) — would strengthen the claim that canonicality is a genuine problem.", "theoretical_claims": "No", "experimental_designs_or_analyses": "Yes, they seemed reasonable at a high level", "relation_to_broader_scientific_literature": "The paper is very relevant to the LLM tokenization literature. However, it seems to make a very novel observation about canonicality, so there are not direct references that it clearly builds on. It also presents a new, simplified algorithm for detecting BPE canonicality.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths: The paper illuminates a widespread but overlooked phenomenon in the output of large language models, induced by tokenization. It appears to be an important problem, and they present multiple methods for addressing it which improve the perplexity in experiments, deriving useful results/algorithms relating to byte pair encoding along the way. The explanations are relatively clear (with the small exception of some notation, noted in the next section)\n\nWeaknesses:\n\nEvaluation: ultimately, we care about the learned distribution over characters, not token sequences. However, perplexity is the only metric evaluated, so we don’t actually know whether fixing the canonicalization problem really produces higher quality outputs. It would therefore strengthen the paper to evaluate their method on e.g. in-context learning, or question-answering, tasks. \n\nAlso, the paper’s experimental results find that the larger the model, the more likely it is to have learned to output canonical token sequences. This would seem to indicate that the marginal gain of canonicalizing could decrease with scale.", "other_comments_or_suggestions": "* The central claim of the paper is that non-canonicality is an obvious problem (“Any probability mass assigned to them is simply an error” L039). But a priori, this is not entirely clear (although it does seem very likely). Although language models are trained on next-token prediction, the evaluation we actually care about is at the word-level, so modeling the distribution over token sequences is not the ultimate goal — the ultimate goal is to generate high quality text. How can we be sure that\n\n* The section in Appendix B that explains BPE could be made clearer in several ways, particularly with the inclusion of a detailed, step by step example labeled with each of the mathematically defined functions. It would also be helpful to repeat definitions from the main body, such as the definition of “BIGRAMS” or $\\mathcal{B}$. \n\n* I did not see where the notation for “is a prefix of” (squiggly less than or equal to symbol) was defined\n\n* Where is g with a right arrow on top of it defined? If line 229, then would recommend to not use it before it is defined\n\n* In Figure 2, the table contains token sequences, not strings? Also, what are the numbers (token IDs)?\n\n* In the ancestral_sampling algorithm, L25, what is $\\epsilon$?\n\n* It is somewhat confusing to use $\\ell$ for a language model, rather than for a loss function\n\n* Explain somewhere what it means to have the arrow on top? Is there a consistent theme in all variables that have an arrow on top?\n\n* Do 5.1 and 5.2 use the “conditioning” method, and 5.3 the “fine-tuning” method? This could be made more clear/explicit, particularly 5.1 and 5.2\n* The table on the upper right of page 8 needs to have a caption\n\nA few typos:\n\n* Line 158, “the general tokenizers” -> “general tokenizers”\n* Line 200, “distrbutions”\n* Line 308, “distribution over” —> “distributions over”", "questions_for_authors": "1. In what sense is the second method a change in “model architecture”? The language models in Definition 3 look more like another test-time strategy (like the first method), which simply updates the sampling scheme. Am I misunderstanding something? \n2. I don’t understand the paragraph “Why train”? (L330-L338). Which training objective for $\\theta^{(0)}$ “pressured the parameters to modal canonicality”? What does “Thus, if the parameters are used to model canonicality preferences, they can be repurposed to model different phenomena.” mean — which phenomena?\n3. Instead of encouraging, or enforcing, canonicality, what about using a randomized tokenization of the training data, i.e. making the tokenization method non-deterministic? \n4. Recent work (e.g. the Byte Latent Tokenizer) has moved away from traditional tokenization methods like byte pair encoding. How could the ideas about canonicality in this paper apply to BLT, if at all? \n5. Did the authors consider evaluating their method on any mathematical datasets? Is non-canonicality a problem for number tokenization?", "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": "IFFAILv71e", "reviewer": "Reviewer_y53f", "summary": "This paper considers an issue with language models trained on BPE-tokenized sequences, where they assign positive probability to so-called non-canonical sequences that could not result from the BPE encoding procedure. They give efficient membership tests for canonicality, and several methods for enforcing the support of the model to be contained in the canonical sequences; one set of methods is through more expensive inference time sampling algorithms, and one is via the parameterization of the language model (which uses additional training). Experiments show that these methods can indeed significantly increase the modelled likelihood across several datasets.\n\n## Update after rebuttal\n\nThe authors have answered well some questions and clarifications I had. Including some of the discussion into new versions of the paper could make the paper even better (its state at submission was already very novel and interesting). I recommend acceptance.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Clarity and notation improvements**: Several reviewers pointed out that our mathematical presentation, although precise, could be more reader-friendly in various places. In the next revision, we will include more reminders about notation and add several clarifying remarks where beneficial.\n\n**Experimental setup and discussion**: We recognize that many of the reviewers found our experiments section excessively terse. We completely agree and will seek to improve the readability of this section in the next revision, which will be easier with the additional space.\n\n**Evaluation of downstream accuracy**: Our initial submission focuses on a theoretical characterization of the problem and our proposed solutions. As such, our evaluation was mainly focused on the task-agnostic measures of (a) the rate of canonicality in language models and (b) the effectiveness of our proposed algorithms for enforcing canonicality. However, we agree with the reviewers that including some evaluation of the downstream effects of our canonicalization methods will considerably strengthen the paper.  We will investigate the feasibility of extending our evaluation to include some common LM reasoning benchmarks, e.g., HellaSWAG and GLUE.  If the reviewers have other/better suggestions, we kindly ask that they share them.\n\n### Response to y53f\n\nThank you for your review, suggestions, and interesting questions!\n\n> Methods And Evaluation Criteria\n\nFantastic suggestion - I can't believe we missed that! \n\nThe perplexity evaluation is on a held-out test set.  We will clarify this in the next revision.\n\nWe will add more details about the experimental setup and release the code upon publication.\n\n> Missing minus sign in Prop 1 and 3\n\nThanks for catching that!\n\n> In my opinion, there are insufficient experimental details, as I mentioned above.\n\nPlease see the general response.\n\n> ⪯ symbol is undefined\n\nSorry about that! x ⪯ y it means x is a prefix of y\n\n> Top left table on page 8\n\nThanks!\n\n> In the \"Why train?\" section. Suppose we initialized a standard (non-canonicalized) language model at θ(0) such that the support is on canonical sequences only.\n\nSoftmax always assigns a nonzero probability to all options.  So it is not possible unless we change the model's parameterization to not use softmax.\n\n> If trained with say maximum likelihood on only canonical sequences, would it be the case that this standard model also has no optimization pressure for canonicality, because the gradients will not assign mass to non-canonical sequences?\n\nIntuition: At the output layer, the gradient update does two things: (1) it attempts to increase the probability of the (observed) canonical sequences, and (2) it attempts to decrease the probability of all unobserved sequences (including the noncanonical sequences). \n\nHowever, because the network has many layers, pushing the probability of the observed sequence up may have the unwanted side effect of increasing the probability of some noncanonical tokenizations that share latent representations, etc.  Note that the gradient signal also seeks to lower the probability of unobserved sequences (which include noncanonical sequences). This means that the latent representations in the network will be updated to push those probabilities down.  \n\nIn our revised parameterization, the network does not have to learn the canonicality function - it will be baked into the model.  So, during learning, the gradient update can focus on teasing apart the plausible candidates, not the ones that we can rule out with our filter.  This will likely give a signal to learn from as the noise of needing to push down the probability of noncanonical sequences is removed.\n\n> understanding misallocated probability\n\nIndeed, the main concern is that noncanonical mass is allocated in ways that are not constant. That said, even if the mass allocated was a (small) constant to each noncanonical token, then ancestral sampling from the model would sample these tokens and the model will end up with essentially out-of-distrbution contexts. Additionally, the longer the model generates, the higher the probability of falling off the canonical path becomes.\n\n> \"My GPUs are from NVI\"\n\nThis is known as the \"prompt boundary problem,\" and it has been solved in [Vieira et al (2024)](https://arxiv.org/abs/2412.03719). They solve it by correctly conditioning the LM on a character string prefix.  We believe it is directly compatible with our canonicalized LM.  This is a much more direct approach than hoping that subword tokens happen to have picked up a [weak] signal that shouldn't be in the model to begin with unless the LM was trained with stochastic tokenizers or other kinds of data augmentation!", "claims_and_evidence": "In general, the claims are supported.", "methods_and_evaluation_criteria": "For the experiment in Section 5.3, the improvement in perplexity of $l_\\theta$ is conflated with the fact that $l_\\theta$ is trained partially with the language modelling loss on the dataset of interest. A useful baseline would be to train $p_{\\Delta}$ with the language modelling loss on PTB and WikiText-103, without any canonicality constraints. Some additional experimental details here would also be helpful such as hyperparameters and training setup. Also, if the perplexity reported on a test set, or the same data that it was trained on?", "theoretical_claims": "In the proofs of proposition 1 and 3, the term $H(p^*_{\\Delta})$ is missing a negative sign throughout, but this is a small issue.\n\nI did not check most other proofs.", "experimental_designs_or_analyses": "In my opinion, there are insufficient experimental details, as I mentioned above.", "relation_to_broader_scientific_literature": "BPE is an extremely common method for LLM tokenizers, which has several noted downsides. Studies that improve BPE or work towards different tokenization frameworks could be very impactful.", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "This paper elegantly tackles a systematic issue in a widely used technique. It seems pretty novel, and it has theoretical insights that connect closely to actually empirical practice. For instance, in Appendix A, the authors include thoughtful comments and examples related to BPE and tokenization in actual language models. However, I do have some questions about the utility of the work (see below).", "other_comments_or_suggestions": "$\\preceq$ symbol is undefined. This was confusing to me.\n\nTop left table on page 8 should be labelled with $-\\log(\\hat{Z})$.", "questions_for_authors": "In the \"Why train?\" section. Suppose we initialized a standard (non-canonicalized) language model at $\\theta^{(0)}$ such that the support is on canonical sequences only. If trained with say maximum likelihood on only canonical sequences, would it be the case that this standard model also has no optimization pressure for canonicality, because the gradients will not assign mass to non-canonical sequences?\n\nI have trouble understanding how misallocated probability mass could impact practical applications of LLMs. If all sequences had a constant bias in probability caused by mass on noncanonical sequences, then this would have no impact, correct? Perhaps if there were systematic biases, say in a domain like mathematical proofs, where mass on noncanonical sequences leads to higher probabilities of wrong answers, then this could be an issue. Any thoughts on this?\n\nAnother related question: could the ability to assign positive probability to certain sequences be beneficial in certain cases? For instance, if the language model makes a mistake and starts generating a canonical sequence of tokens that leads to a wrong answer, perhaps it may have to start generating a noncanonical sequence to get to a right answer? Or, perhaps the user prompt for a base language model is cut-off or has a typo at the end, and to complete the sentence it may be relatively easy for a language model to complete the query with a noncanonical sequence of tokens? E.g. if the prompt were \"My GPUs are from NVI\", and a good completion is \"My GPUs are from NVIDIA\", and NVIDIA were a token, might it be hard for a canonicalized language model to output the desired completion?", "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": "85YvF0tQ7E", "reviewer": "Reviewer_1h8t", "summary": "The submission discusses issues arising from tokenization wherein language models place positive probability mass on sequences unobservable during training. The submission presents approaches for both test time and train time for lessening the severity of this issue.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### General Response\n\n**Clarity and notation improvements**: Several reviewers pointed out that our mathematical presentation, although precise, could be more reader-friendly in various places. In the next revision, we will include more reminders about notation and add several clarifying remarks where beneficial.\n\n**Experimental setup and discussion**: We recognize that many of the reviewers found our experiments section excessively terse. We completely agree and will seek to improve the readability of this section in the next revision, which will be easier with the additional space.\n\n**Evaluation of downstream accuracy**: Our initial submission focuses on a theoretical characterization of the problem and our proposed solutions. As such, our evaluation was mainly focused on the task-agnostic measures of (a) the rate of canonicality in language models and (b) the effectiveness of our proposed algorithms for enforcing canonicality. However, we agree with the reviewers that including some evaluation of the downstream effects of our canonicalization methods will considerably strengthen the paper.  We will investigate the feasibility of extending our evaluation to include some common LM reasoning benchmarks, e.g., HellaSWAG and GLUE.  If the reviewers have other/better suggestions, we kindly ask that they share them.\n\n\n### Response to Reviewer 1h8t\n\nThank you for your review!  We are sorry about the \"jarring\" terseness of the experiment section. We will revise it in the next revision.\n\n> GPT2 is a bit outdated, but it is enough to demonstrate the claim of the paper.\n\nNote that we included experiments with Llama 3.2-1B as well as GPT-2-[small, medium, large]. In that setting, we saw that Llama 3.2-1B's canonicality rate was surprisingly significantly lower (.763) than the GPT-2 models ([0.895, 0.929, 0.944]).  This means that the more modern Llama model benefits MORE from conditionally canonical generation. \n\nNonetheless, we agree that our experiments could benefit from a wider range of language models. For the next revision, we will extend our evaluation to include some of the larger Llama models.\n\nIn the fine-tuning experiments, we limited them ot GPT-2-small and medium.  Since these experiments are the most compute intensive.\n\n> The writing could do a bit more handholding in the methodology and experiment sections, but even these exceed the quality of a typical machine learning paper. \n\nWe will revise the paper to include more \"handholding\" and reminders to help unpack the terse notation.\n\nSee also: general response\n\n> I'm sure local canonicalization exists in some codebases, but I haven't seen it nicely formalized in literature.\n\nThe closest methods we could find are discussed in appendix B.3.  As noted in appendix B.3, our method is significantly simpler to implement and uses significantly less memory.  In fact, we initially tried using these methods for this paper, but they consumed so much memory that we couldn't build the complete automaton without running out of memory.\n\nWe suspect that if other canonicality filtering methods exist in other code bases, they are heuristics rather than principled methods with proofs.  Getting the details right about the BPE canonicality filter was surprisingly nontrivial; as you can see, we have an extensive appendix (B) detailing why our method is correct.  However, we note that the final filtering rule that we derived through all that painstakingly detailed work is very simple to implement (a simple bigram test) and it is possible that someone out there \"intuited\" it, but if they had proven it correct, we'd strongly suspect that they would have at least arXived it or released code for it unless proprietary :-(\n\n> The submission introduces ⋅ for concatenation but then switches to ⟨⟩ for bigrams.\n\nGood point - we could use juxtapositions to denote the bigram instead of \n\n> Byte-rair encoding\n\nSorry about that - we spotted that one after submission!\n\n> In Section 5, I find the bulleting without quite jarring to read.\n\nWe will improve the readability.  In particular, the terse style of the experiment section in the final version.  It was written in this very terse style because we were short on space.  We appreciate you for pushing through despite the jarring style!\n\n> It would help clarity to remind the reader of definitions in more places (the submission uses a lot of different symbols and symbol modifiers).\n\nThank you - we agree that adding gentle reminders about the notation throughout the paper will improve the readability a lot, and we will do so in our next revision.", "claims_and_evidence": "> Are the claims made in the submission supported by clear and convincing evidence?\n\nYes, the paper is quite well written up until the experiments section.", "methods_and_evaluation_criteria": "GPT2 is a bit outdated, but it is enough to demonstrate the claim of the paper.", "theoretical_claims": "I did not check the proofs.", "experimental_designs_or_analyses": "The experimental design seems fine.", "relation_to_broader_scientific_literature": "The submission does a sufficient job relating the paper to broader scientific literature.", "essential_references_not_discussed": "> Are there related works that are essential to understanding the (context for) key contributions of the paper, but are not currently cited/discussed in the paper?\n\nNo.", "other_strengths_and_weaknesses": "The main idea of the paper is very simple, but the conceptual clarity of the paper is impressive nonetheless. The writing could do a bit more handholding in the methodology and experiment sections, but even these exceed the quality of a typical machine learning paper. I'm sure local canonicalization exists in some codebases, but I haven't seen it nicely formalized in literature. The idea of training or fine-tuning in a way that enforces canonicalization feels like it has the potentially to be quite useful.", "other_comments_or_suggestions": "The submission introduces $\\cdot$ for concatenation but then switches to $\\langle \\rangle$ for bigrams.\n\nByte-rair encoding\n\nIn Section 5, I find the bulleting without quite jarring to read.\n\nIt would help clarity to remind the reader of definitions in more places (the submission uses a lot of different symbols and symbol modifiers).", "questions_for_authors": "None.", "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:

Meta-review: This paper points out that language models assign non-zero probabilities to token sequences which will never appear because of the tokenizer algorithm. The authors present two approaches to address this problem in language models, and show that addressing it increases the model's estimated likelihood of held-out data, across GPT-2 models and one Llama model. Reviewers agree the paper is well motivated and well written and that the methods introduced are practical and appropriate for the task. 

Multiple reviewers have flagged, however, that the authors should evaluate the impact of this approach on downstream tasks, and we agree. We encourage the authors to evaluate on a suite of downstream evals - including HellaSwag, as the authors have mentioned, but even better would be a suite of downstream evals (e.g., Arc-Easy, Arc-Challenge, PiQA, BoolQ, possibly from an eval framework like mosaicml's llm-foundry or Eleuther AI's llm harness). This paper would be even stronger with evaluations that closed the loop to show when canonicalizing language models improves a practical downstream task. 

Nevertheless, this is a strong submission and we recommend its acceptance for ICML.
Decision: Accept (poster)