From Language Models over Tokens to Language Models over Characters
Authors: Tim Vieira
Benjamin LeBrun
Mario Giulianelli
Juan Luis Gastaldi
Brian DuSell
John Terilla
Timothy J. O'Donnell
Ryan Cotterell
Venue: ICML 2025 spotlightposter (2025)
Keywords: tokenization
character
bytes
tokens
language models
probabilistic reasoning
probabilistic inference
Primary area: deep_learning->large_language_models
TL;DR: Efficient algorithms for character-level conditioning of LLMs

Abstract: Modern language models are internally—and mathematically—distributions over *token* strings rather than *character* strings, posing numerous challenges for programmers building user applications on top of them.  For example, if a prompt is specified as a character string, it must be tokenized before passing it to the token-level language model.  Thus, the tokenizer and consequent processing are very sensitive to the specification of the prompt (e.g., whether the prompt ends with a space or not).  This paper presents algorithms for converting token-level language models to character-level ones.  We present both exact and approximate algorithms. In the empirical portion of the paper, we benchmark the practical runtime and approximation quality.  Across four publicly available language models, we find that—even with a small computation budget—our method is able to accurately approximate the character-level distribution at reasonably fast speeds, and that a significant improvement in the language model's compression rate (bits/byte) is achieved.

From Language Models over Tokens to Language Models over Characters
Tim Vieira
Benjamin LeBrun
Mario Giulianelli Juan Luis Gastaldi' Timothy J. O'Donnell 425 Ryan Cotterell
Brian DuSell John Terilla"
Abstract
the prompt boundary problem well other oddities that make interfacing with token-level language models with character-level prompts hard for users.
Modern language models are internally-and mathematically-disrree distribttion over token strings rather than character strings, posing numerous challenges for programmers building user appli- cations top of them. For example, if prompt is specified as a character string, it must be tokenized before passing it to the token-level lan- guage model. Thus, the tokenizer and consequent processing are very sensitive the specification of the prompt (e.g., whether the prompt ends with space or not). This paper presents algorithms for converting token-level language models to character-lewe ones. We present both exact and approximate algorithms. the empirical portion of the paper, we benchmark the practical runtime and approximation quality. Across four publicly available language models, we find that-even with a small computation budget-out method is able to accurately approximate the character-level distribution at reasonably fast speeds, and that a significant improvement in the language model's compression rate (bits/byte) is achieved.
Tokenized language models: A brief overview.' Let E be alphabet of characters, and let E- denote the set of all strings that can be built from it. Suppose there is true distribution pt: over E that we seek to model. We observe a
training corpus of character strings: o , (M) Lid. ps- However, rather than estimating a language model that ap- proximates p directly, we employ a (possibly stochastic) to- kenizer that transforms the training corpus into corpus of token strings. ((1) -(- (")),... 8(M) -(- (M)). Next, we estimate token-level language model to fit the strings (1)) ... 8(M), Lastly, we use pa to generate char- acter strings through the following generative process: (i) sample 8 ~ Pa and (ii) return a = x(ō) where a de- coding function. Let pr denote the resulting distribution of this process. Practically, we hope that the choice of and should aid in ability to estimate pa in the sense that pt pg. Commonly used tokenizers in the realm of LLMs use tokenizers r that break long strings into chunks. Intuitively, generating chunks instead of individual char- acters helps because it effectively shortens strings without obfuscating them using complicated encoding.
c htttp:://gtthihh com/ genlm/ wewgggnnnnlteeee
1. Introduction
The prompt boundary problem. Consider the case of GPT2 (Radford et al., 2019), which was trained over token strings created from byte-pair encoding (BPE; Sennrich et al. (2016); Gage (1994)). Suppose we wish to generate continu- ations of the prompt: fin_the_kingdee Unfortunately, the interface to Pa is not ideal: it does not accept character string; thus, it is common encode it as token string with an encoding function 7
Modern language models are engineered as probability distributions over strings of tokens rather than strings of characters. However, this leads fundamental tension between the users of language models and the engineers who build them. Specifically, token-level models are rife with unintuitive behaviors thth-wt technical bif-eaffle users. As an illustrative example of a common user complaint, we exhibit the prompt boundary problem (see below). This paper provides a principled solution
bhheebbnndd. the.
TBPE ("In_ tiin_the_kinge wiweekkinndooooooocom wtt_ttheeblinn_tthhe
[ 8187 262 13239 1 286 262 7778 3 111 2
In the Jinndon Lof _th _blind
ETH Zürich Mila CCity University of New York "MeGill Univer- sity 'Canada CIFAR AI Chair. Correspondence to: Tim Vieira <tim. stim.f.wee vieirreeegmailil comp.
We adopt the notation of Gastaldi et al. (2025), who gave general characterization for when training with tokenization allows for consistent estimation of the distribution over characters.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
IIn practice, TEPE outputs an integer sequence; we provide the substring gloss for readability.
We write á = 7(7) when 7 deterministic (i.e., a function).

---

From Language Models over Tokens to Language Models over Characters
If we complete the prompt by taking the most likely next token (greedy completion), we generate the following:
end of the prompt. (4) Continue generating as usual. Now, we see how token healing patches the running example:
-one eyed _nan Lis _iin 530 1 12" 188341 5827 7 318" 58221 1 526
TBPE wtt.eeekiinngooooooteee......
In wthe kingdon Lof ,.he _blind . .the [17 8187 262. 13239 2888 2621 7778 1111 262 7
Now that we have our generated output, we can apply the decoding function that maps token strings to character strings as part of the tokenization protocol:
one The most probable next token starting with... is 530 Now, generating the remaining tokens recovers the desired output, as it matches the prompt before we added the whitespace.
KBPE (..)
"nn_the_kiingdonoof.thee innd,
Unfortunately, backing up one token is insufficient for the general case, as the following example will illustrate. Con- sider generating from GPT2 using the prompt Hel Hello,..worl:
bone-eyed_man.is.kiee
This is a good completion, as the string is a well-known proverb. However, we tweak the prompt ever so slightly by inserting trailing whitespace:
TBPE (Hello, Hello , _Mor
11: 476 75
TBPE( "'Bee"In__the ""In_nthe_iinneeeeeee www.ttheeiinnooooo.. of wtt.hhtheeendnttn.
The most likely next character ought to be d as Hello, is common expression (popularized in edu- cational material). However, the most likely token results in Hello, an apparent misspelling of worldwide. Unfortunately, token healing's 's strategy of backing up by a single token cannot salvage the poor tokenization as 75 is still the most common next token that is consistent with the string 1. Thus, after generating 1
= -[ 8188 262 > 13239 2867 262 + 7770 111 262 2 228
In _hehe _kingdon _of the _blind the
greedy completion gives bi _af the world Lare _seen
2885 2821 1, 995 389 > 1775 ""]
because the conditional probability (pZ) of generating the characters we want becomes highly unlikely, dropping from
0.98 ( [TPP( (the) to 5 x 10-7 p& ane Ses (BPE(-- (-- upon appending the character. Hence, the trailing white space undesirably impacts the output, which no longer corresponds to the proverb.
75* we are back where we Helll Mwor wide, started, generating [15496+ 11+ 476 452
+ Getring it right: A simple "probability 101" expression tells us the correct solution to the prompt boundary prob- lem. Consider a A -vavuue random variable Y, distributed according to pa. Then, the correct way to sample from pa conditioned on a character string o is according to
We formalize the prompt boundary problem as fol- lows: Let σ E E' be our initial prompt, such Now, consider a pair of future strings -c and o'3 with a common prefix o' Lnn and _illss) We say a language model interface suffers from the prompt boundary problem if moving the common prefix a' (e.g., .) across the boundary into the prompt does not preserve the relative probability of the pair of future strings, i... the relative probability of o' and o' given a does not equal the relative probability of a and B given a-o'. Our example fails this test because the probability of ...one was much higher than _ills, but then, the relative order swaps after moving into the prompt.
PaIx
( =())=
(I)
Yous
where we have conditioned on the event that the decoded string x<Y) has a as prefix (i.e., x(Y) - σr. While innovative with respect to the literature, the expression PY~pa TT-palY=B o x(Y) > o conveys the probability we interested in precisely and concisely. For the more procedu- rally minded, this corresponds to the following process:
def conditional wtweiiiinnnntnttnneeeeeeeeeeeeee (tc.eengeeeration(c))
Our perspective that the prompt boundary problem arises from incorrectly conditioning the token-level language model on string of characters by using T(r) rather than finding token strings that best match the prompt o.4
2 while True:
3 sample 8 ~ PA
if k(() 2 a: return 8 accept
This is, of course, very inefficient, but fear not-we will provide an equivalent, efficient algorithm.
+ The token healing heuristic: present token healing as a heuristic that mitigates the prompt boundary problem; it works as follows: (1) Tokenize (i.e., encode) the prompt. (2) Backup the tokenized prompt to the penultimate token. (3) Generate the next token subject the constraint that it starts with the unmatched substring at the
Lundberg& & Ribeiro (2023)
Our method finds set of token strings that form a covering, key technical concept we introduce in this paper. We will provide the precise definition in due course; for now, we will illustrate the covering of worl:
'Prohabilistic condition preserves the necessary relative probabili- ties that we specified in the prompt boundary problem.
Thee misspelling is testament to the extent to which the tokenized prompt is out-o--diittiiuttion.
2

---

From Language Models over Tokens to Language Models over Characters
Hello world
ble next characters. Beyond the prompt boundary problem, computing the conditional probability of a character string given token-level language model has many applications.
(0.9820714)
114496111 11
996
Hello wwrldss
[00.0106702)
154966 11 11621
Hello worldwide
100.0070749)
15496' 11"
8688
Applications. Aside from making character-level condi- tioning well-behaved, we highlight a few applications of language models requiring careful character-level reasoning:
Hello
worldl
(0000000830)
114966 11
43249
Hello worldview
(000000036))
154966 11" 29881
+ Character-level constraints: Enforcing character-leved constraints on allowed strings is promising area that has received much recent attention (e.g.. Scholak et al., 2021; Poesia et al., 2022: Geng et al., 2023; Microsoft, 2023; Willard & Louf, 2023; Koo et al., 2024; Loula et al., 2025).
Hell a _world
((0.0000225)
222244 78 11" 995
Hello _Mor 1
100.0000179:
114996 11" 476 75
+ Computational psycholinguistics: Computing the con- textual surprisal (negative log probability) of a character substring to predict human reading times (Hale, 2001; Levy, 2008). Two recent papers (Oh & Schuler, 2024; Pimentel & Meister, 2024) have given algorithms for computing the surprisal of strong assumptions. Our algorithms can compute the contex- tual surprisal of arbitrary character strings. Giulianelli et al. (2024) show experimentally that having the flexibility to compute character substring surprisals leads to a more pre- dictive model of reading time than a fixed notion of a word.
Notice that each token string in the covering has the char- acter string wello, as a prefix (after decoding), but it may have some extra characters (marked by underlining) in the partially matched last token-just like token healing. The size of the complete covering may; in general, be ex- ponential in the length of the character string. However, we can enumerate its pegh-probability members very quickly in practice. Since the worst-case time to find the top- elements of the covering might be exponential, we provide a more aggressive approximation based on beam search that gives a good approximation even with small beam sizes. _world Unlike token healing, the sequence [i549e* 11! 995 is the highest probability member of the covering; thus, it is not pruned away by the aggressive heuristics based on r, as in token healing. The covering is defined only in terms of k, and the pruning is based on the language model probability, which typically prioritizes the token strings that are most reflective of the language model's training data. We provide an algorithm for correctly conditioning token-level model on a character string in $3.4.
words under a number of
Does it work? In the experimental portion of our paper ($4), we report the empirical runtime of our algorithm for converting token-level language models to character-level ones and quantify its accuracy in estimating the conditional distribution over characters. We find that even with a lim- ited computational budget, our method provides an accurate estimate of the conditional distribution over the next char- acter under four publicly available language models. 6 We also find that the compression rate (bits/byte) is significantly improved by estimating the probability of the corpus as a character string rather than a canonical token string.
Character-Ievel model. At the character level, working with the language model is intuitive. Consider, again, our example illustrating the prompt boundary problem. Appending whitespace behaves predictably, as it satisfies the probabilistic chain rule:
2. Background
2.1. Alphabets and Strings
3 [Lone] "in.hh__Aingomoof..ttte.LLLddddd
An alphabet I is non-empty, finite set of elements called symbols. A string 7 over alphabet I' is a finite sequence 7 2- - 7N for some 0 < N < 3o of symbols where Ti... YN E r. Let |y| denote the string's length N. We de- note the empty string as e. For any alphabet I, let I" denote the set of all strings over I, and let I+ denote the set of all non-empty strings over I', For any two strings 7 > E I", we denote their concatenation p'.r". Additionally, we define S.S' (r:'²) 7 E S. E 5'} for any S,S' C r*. Given a string 7 such that |y| 2 t, let Y<t denote the string made from the first t t- characters of y. We write y = 7
= =p3( [_] "In.ttelkkingdoooooffftl...Ldddd
<one "Ih..tte.kingoomofff.f..eeedlddd
Here, 135 denotes the character-level model's conditional dis- tribution. Similarly, recall the Hello,,.world example above.
The character-level model correctly infers that d is the most likely next character given Hello, w.rll. The computation of this conditional probability is simply the total probability of the covering of Hello, worldd divided by the total prob- ability of the covering of worl. These quantities are derived from our concept of covering, which directly leads to an algorithm for determining the distribution over possi-
"Specifically, Llama-3.2-IBB Meta-LJamaa-311-6 DeepSeek-R1- Distill-LJJmma-88, and phi-4 (14B).
3

---

From Language Models over Tokens to Language Models over Characters
if y is prefix y and y < r if y is a proper prefix of y' A is an alphabet of token symbols The relation N defines a partial order on r We write = and > to refer to the relations N and < with their respective arguments transposed.
is a (possibly) stochastic encoder: T(. (r) is proba- bility distribution over S' for each a E >''
R: A - Σ" is decoder function satisfying exactness EsEa- 1 (x((6) = (6 o) = for all a E Ex
2.2. Language Models and Prefix Probability
Definition 2. A tokenized language model pg is language model over En that is parameterized by a language model PA over A and a decoding function k: A + Σ.. This tokenized language model generates character strings via the following process: (i) 8 ~ Pa, (ii) a t k(ō). Thus, the character strings a generated have the distribution:
A language model pr is probability distribution over I' where I is an alphabet. Let Y be a -aaluleed random variable distributed according to and y E r The prefix probability (r) is the probability that Y has prefix y:
(7) Y-Pr
def
P
[==)=
Σ -'Er"
1(' = 7)) (2)
pz(O)
del P YoDa
[m(V) =o]
(6)
We also define the following shorthand for the conditional prefix probability pi('' 7) the probability of the event Y - 7.7 provided that Y ž y
Note that po(() accounts for the fact that many token strings may be associated with given character string through k. To describe that association, we define E(o) def (6 E A x())), the set of encodings for any character string E 10
| / - ()
(T 7)
P Y-pr
(3)
(7)
We may express the probability of y as product of condi- tional prefix probabilities:
What about 7? The reader may notice that r does not appear in Eq. (6). Although is essential for generating training data, once the model Ps has been trained, the in- formation in is not of immediate practical use. Moreover, attempts to leverage seem to lead to faulty heuristics, as we discussed in the introduction. We note that under exactness, (or) must be present in E(r). This is because exactness im- plies that E(r) 2 (5 E A 7(5 o) > 00 for all a E Σ*. In the common case where r is deterministic" we empha- size that E(o) 2 (T(O)). The tokenization model would need to be bijective 12 for E(or) = {T(O)]. Unfortunately, common tokenizers (e.g., BPE) are not bijective.
pr())= = pf (FOS) I 1 hy|
II (1e 7s0)
(4)
where each (T Yet) is an instance of Eq. (3), and
(EOS 7) der pr(7)
(5)
(7)
Here, EOS is a distinguished end-of-string symbol that can- not appear in any alphabet. Of particular interest are the single-symbol conditional prefix distributions (- 7<c), as they may each be interpreted as probability distribu- tion over the set I' U {BOS}-in in fact, modern language models" are defined via the product in Fq. (4) where each single-symbol conditional prefix probability comes from the learned parametric model.
The mirage of the canonical tokenization. Consider the case when the encoder 7 is deterministic. In that case, we write 5 = r(o), and we call this 5 the canonical tokenization of a. Note that even if is deterministic, there may exist many noncanonical tokenizations 8' E E(r) such that 8' # (o) with nonzero probability (8 > 0. Thus, the character string generation process includes a mix of canonical and noncanonical token strings-making it incorrect only consider a character string's ' canonical tokenization when assessing its probability. In practice, the conditional probability IP~pps [Y 8 k(Y) o] over the encodings 5 of a character string o tends to be highly
2.3. Tokenization
We now discuss our basic formalization for tokenization. Definition 1. An (exact) tokenization model is tuple (,,,,TKK) where
is an alphabet of character symbols
'E.g., transformers (Vaswani et al., 2017), RNNs (e.g.. Mikolov et al., 2010), and n-gram models (e.g., Shannon, 1948).
'Many authors (Cao & Rimell, 2021: Chirkova al., 2023; Phan et al., 2024) have discussed this particular complication; however, no algorithms for computing the next-character distribution exist. Note that [E(r)] can he very large, e.g., infinite in the worst case. In the case of BPF, it is exponential in |a]
"The reader may notice that the equations for pr(?), (r' IY), and pf (EOS (7) are mutually recursive. Thus, they may appear circular. The key to resolving this concern is to recognize that pr is given as a hase case. We note, however, that some readers may view Eq. (4) as the definition of the language model pr. taking the components on the right-hand side of Eq. (4) as the base case.
" "L.., r(5) | () E (0, 1) for all ó E A", "a E Σ.. LL,.., a bijective tokenizer is deterministic, exact, and satisfies T(K(5)) = for E A
4

---

From Language Models over Tokens to Language Models over Characters
concentrated on the canonical tokenizations, as illustrated in Example 1 below.
wolld
Hello, world
worlo world
Example 1. Below, we show GPT2's top encodings from wolll), ranked by their conditional probability.
Hello 15496 11
_wolld
H ell
wwold
Hello wwor 1 15496 11 757
This short string has 78 encodings from numerous partitions of wello, into substrings of the tokenization
Hello .world
995
3969578 1 995
(0.9999719):
15496 11' 995
Hell _world
(0.0000022))
28254 78 11" 395
Hella
ld
(0.0000024):
15496 11" 476 335
More formally, every application 01 OMM =((0 5m) of a strict-prefix monotone mapping has the following prop- erties. Each token in 61 .. 5M maps to one or more contigu- ous characters in d1 TM d M- Moreover, the mappings do not exclude any characters, and no edges of the mapping cross one another. Strict prefix monotonicity, in contrast to prefix monotonicity, ensures that there the mapping, i.e., each token maps to al least one character.
He 11e world
(0.0000017):
11545 18798' 11" 995
alphabel A. We see that the probability heavily concentrates on the top string, which is canonical.
II ell 199 695 78 11 995
world
(0.00000004)
Hello
orld 11 266 1764
(0.0000002):
115496
H ello world 139 11189'11 11 995
(0.0000002)
deletions of tokens in
character-level interface. A character-level interface to the toven-level language model pa is available in the following equations, which hold Vo, a' E":
Strict-prefix monotonicity is the key structural property re- quired by $3's algorithms, as it allows us to replace an infi- nite sum with a finite sum in Proposition 1. We briefly men- tion an important special case. A decoder is is multiplica- tive if x(6) 6N) k(ō)) k(Ōx) for all 81 -1-68 8N E A", and non-erasing if k(6) =
p3(0)= = (<(Y) (1)=a) ol
Yapa
(o o0) (o.00
If K. is multi- (8) plicative, it is prefix monotone; if it is also non-erasing, it is strict-prefix monotone. Both BPE and WordPiece are multiplicative and non-erasing.
8
(o)
(EOS | o) (o)
(9)
(o)
These equations show that we can have a complete character- level language model derived from the tokenized language model if we can compute- approximate the necessary summations implied by Eq. (6) and (7); specifically,
3. Algorithms
This section gives algorithms for computing (s((o), (3)) (3(aa' o)) pá (EOS or,, and conditional token generation. We assume throughout that is strict-prefix monotone.
p=(a)= = Σ (xx(5)= = a)
(10)
SEA-
3.1. Covering
p( Σ
1m(()===0 = Pa(
(11)
Eq. (11) shows that we can, in principle, compute the prefix probability () by summing over prefix-encodings of a, P(o) del A x(0) ł a). Although P(a) is infinitely large, can exploit the prefix monotone structure of to find different way to perform the summation by summing over finite set. Let ô E A", 81 6M = 6, and a E Στ. We say that covers o if and only if k(5) 2 a. Monotonicity ensures that for all E P(a), we have that V8' E A": x(6-8') > a. other words, any that decodes to an extension of (i.e., x(()) 2 σ) will continue to do so if we append tokens to it. Thus, we may additionally qualify the relationship ò minimally covers a if additionally n(6ā ... 5M-1) < a. With that in mind, we define (6) as the shortest prefix 8' 3 8 such that ra(8) > o,, i.e., &o maps any ô that covers or to (possibly equal) token string that minimally covers a. Next, we define the set of minimal prefix encodings of o, which we call the covering of a, C(a) de (oo 8 P(a)). A more convenient expression for the covering C(a) of
SEA
We will develop effective methods for these summations for the family of strict-prefix monotone decoders (described in $2.4) where Eq. (10) and Eq. (11) admit a finite summation.
2.4. Key Properties of x
This section defines the essential properties of K. we require.
Definition 3. We say k: A Σ" is
prefix monotone if = 8' = x(6) 3 x(8")
strict-prefix monotone if 5 < 8'
kō) < (6))
In simpler terms, strict- trrict-prefix monotonicity implies that con- catenating a token to the encoding necessarily concatenates at least one character to the decoded character string. The diagrams below illustrate how GPT2's strict-prefix mono- tone i gives rise to a certain alignment between three token strings and the character string Hello,..world:
5

---

From Language Models over Tokens to Language Models over Characters
string E E' is equal the following subset of A
[C(x) is finite for all a Σ". Bear in mind that the cov- ering's size is likely too large to be practical, there may still be large number of summands; however, the set of high-prefia prrefix-robbbbiii elements of the covering tends to be reasonably small, an observation that we verify in $4, and leverage to develop practical algorithms in $3.
{c}
if o =
((o)
fōr. 5m E = n(ō1 8M-1)
otherwise (12)
k(6 dxr))
Example
Hello world 15496111 995
Lastly, we note that the covering contains the set of en- codings, i.e., E(o) S C(or); hence, the encodings may be extracted from the covering as follows: E(or {8 C(ar): x(ō) = o). We may also express the prob-
Recall the covering of the string a = Hello, from the intro- duction. We have repeated on
Hello worlds
154981111 11621
the right and couched in our ter- minology. Note that the complete covering worll)),.warl contains 36, 608 token strings; we only show the top strings according to their re- spective P3. Below, we list several properties and observations about the structure of the covering:
Hello _oolldvide
ability of a in terms of the covering:
15496111 8688
Hello _orldly
p=(or = - o pa(o)
(14)
15496111 43249
&EC(O)
Hella _Morldview 154961111 29081
3.2. Algorithms for (o) and ps(
Hell
world
228244 78 11 995
The enumeration algorithm will enumerate elements of the covering along with their prefix probability (for con- venience). It filters prefixes of token strings that cannot eventually cover the target string a. The strict-prefix mono- tonicity property is essential for this filtering.
Hello _Mor 1
15496' 11" 476 75
The covering for any given string a always has the prop- erty that each non-empty token string the covering decodes string that has as a prefix, i.e., o x(6). This is illustrated by the gloss string in the tokenization. Note that 8 may include partially matched token at its end (i.e., ds in Eq. (12)). We have marked the extra characters by underlining them. We note that the 7th member does not have a partially matched last token. Each token string in the covering has at most one par- tially matched token thanks the condition s(()) < k(6--)) The 7th member of the cover has a completely matched last token; hence, there is no underlining.
Our algorithm enum_covee performs recursive enumera- tion of the members of the covering C(a) along with some metadata. Specifically, the algorithm returns collection of triples where each triple (p',o', o', 8') satisfies d' E C((o), p' p2 and a' x(8').
s def ( ON): if N = 0: return [(1,e,e) # base case out + []
for (p',o', "1,68')) ,0) in enum_cover NN11)
We see that if we were to extend any member E C(a) with an arbitrary string of additional tokens 8', it would continue to decode to a string such that r:(5-8') 2 a. Moreover, minimal (i.e., &e (6) =
if lo'l < N: # extend
10 for 8" E Á::
a" +- x(8'8"")
if 0% =o:: # filter
out append(())) p0"(0" 0"), 88."))
The notion of a covering is used to derive an algorithm for computing character-level probabilities given token- level language model. We first show how gives us the prefix probability and subsequently give equations for the remaining quantities of the character-level language model.
elif d'N = =o: filter character matches out append ( o',)')) return prune (51 ON out) NN.
15
16
Note that this method has an additional parameter, the func- tion prune, which is used on the last line. This method, as the name suggests, is used to limit the size of the covering to prevent excessive growth. We will discuss this parameter shortly. For now, consider the following definition:
Proposition 1. Suppose (2, A,T, R) a tokenization model where is strict- prreft-prefix monotone and pa is a token-level language model. Then, the prefix probubility pá((or) for the character-level model Eq. (6) is given by
def prune_nothing ON, out):
pś(0)= = (b(0)=Er(0)) (8)), SEC(O)
E'
(13)
18
return out
From the output of the enumeration algorithm, we can com- pute the other key objects and quantities (i.e., C(ar), (5()), E(o), (o)))) in the character-level interface.
Proof. See App. B.
Eq. (13) is substantial improvement over Eq. (7) for com- puting (3)) Specifically, we now have a finite sum, as
Time and space complexity. To meaningfully discuss its running time, we assume the following:
6

---

From Language Models over Tokens to Language Models over Characters
x(8'-8") can be evaluated in constant time given x(6"). the cost of evaluating (6, )ςx) is constant given that (6 8<c)) has been computed for 0 s t.
to efficiently filter out the next tokens that disagree with the next character. We can regard the trie local language model that generates the next token character-by-characee according to the probability assigned by P | 6). Each bundle can be unbundled (if necessary) into the respective tuples that the enum_cover algorithm maintains.
Under these assumptions, the running time of mmum_cover(01 -0 xx) can be exponential in N when no pruning is used. We provide detailed bounds on the covering's 's size in App. C. It is straightforward to verify that the space complexity is (((((r))), and the running time is C(A)) E (((o=)))) which is dominated by the | . |C(()) term; thus, O(IA) (C(
3.3. Algorithms for (
This section gives algorithms for computing the character- level conditional prefix probability. Recall the definition of the character-level conditional prefix probability, that is, Eq. (8) and (9), can be computed from a certain ratio of calls to p (and ps: in the case of ROS). From here, Eq. (8) and (9) give straightforward algorithm for computing the distribu- tion over EU {EOS} } given a E Σ", However, direct trans- lation would perform duplicate work. Therefore, we provide the following version, which reuses work between the calls to pš than directly evaluating those equations would do.
Pruning. We now consider some useful pruning heuristics for the algorithm, which make it an approximation but sub- stantially improve its running time. We propose heuristic based on beam search. This heuristic is very effective: it gives us a linear running time as a function of the charac- ter string's 's length. It has a parameter K that controls the approximation quality. Larger K makes the approximation more accurate, and the approximation becomes exact as K approaches the size of the (largest intermediate) covering. We take K to be a global variable in the pseudocode.
31
def cttr__chrracee__pobbbiiiii
N |ol;;; Z+0; p+ (o': 0 for o' d'E d'ECU(BOS)
32
for (p', od'''',8 E enum_ enum_cover(o)::
33
+ Our pruming heuristic: Our pruning heuristic enumerates < K distinct token strings modulo their last token. This choice allows up to | versions of the last token to be enumerated (if is not completely matched). Thus, the work done at each step is O(K [A), and the size of the pruned list is most that size. Therefore, the overall running time is O(N K- [A]) for character string of length N. 14
34
Z += p'
if |o' = N: # #.e., d'=o +=p'
p(FOS) += p' pp'ppp p'.p -P3( 5)
for 8" EA: # extend
o" =(('''8"
p(a'+1)) += 1/ 1/p3((0 18)
39
40
else: # i.e., o'20
41
p(d'+11)
p
19 def _oune_to____tee (o results):
42
return D/Z # Z = p (o)
20 buckets + (
21 for item in results:
3.4. Conditional Generation Pais( (o)
22. (v,o', 0 5M) + item
This section gives simple algorithm for correctly generat- ing token string Y that has given character-level prompt o as its prefix. This algorithm is equivalent to the algorithm in the introduction but significantly faster.
20
# Exclude a partially matched last
key < 81 5 if Ta'l > N else 51-5, 8M
24
25
buckets(key] append (i (em)
56 pruned +- []
27
for bucket in buckets. buckets.top(K)). # by prob.
The algorithm works by enumerating the covering C(o), drawing token string from in proportion to its prefix probability, and finishing the token string by sampling a completion, which can be done from the token-level model.
28 for item in bucket:
29
pruned. cruued.append(C append
30
return pruned
43 def conditionale iaciiionll_ttkennneeeeeee token wtw.etoooeeeeeeeeeeee gen)
Bundled beam summing implementation. App. D de- scribes an implementation strategy that improves the con-
8' ~ Categoricall po/p for (y';_8') in cover return sample_completiont
stant factors associated with the pseudocode above. The key idea to group the token sequences that fall into the same bucket in prune_ t_b_kke buckets into bundle that represents them compactly. In particular, we can
def sample_completion/
trie
48 8" + E
In the case of the common transformer language model (Vaswani et al., 2017), this can he achieved with efficient caching and limiting context windows to constant size.
49
while True:
8 ~ p3(- 8'-8")
50
51
if 8 BOS: break
NNote: finding the (unordered) set of top-K elements from a set S possible (IS)) time via the median-of oo-iiiinn-- algorithm.
8" <- 8".6
return 8'"
7

---

From Language Models over Tokens to Language Models over Characters
DeepSeck D--Ditilll-- Distill-Llama---
Llama
Llama
phi-4 (14B)
0.00044
0.0006
0.0015
0,00033
0.0004
0.0022
0.0010
0.00011
0.00022
0.0002
0.0001
8..0
0.0005
45 1/
$500
0.0000
0.0000
0.0000
10
20
30
40
0
25
50
75
100
125
10
20
30
5
10
15
20
Speed (bytes/sec)
(a) Error (ISD/byte) vs. speed (bytes/sec). Error is computed between the character-level conditional distributions with beam sizes K (2, 16, 32, 64) and reference distribution computed using much larger value of K 128.
DeepSeck-He RR-RR---D-aait Disttill--lamm--eee Lluma-8B
Llana 1amma-3322 3.2-1B
Meta- Luma--3 3.1-8B
phi-4 (14B)
0.70
Surprisal
0,9
0.75
0.65
0.65
0.70
0.60
2
0.8
0.65
0.55
0.60
0.55
0.7
0.60
0.50
0.50
10
20
30
40
40
80
120
10
20
30
40
5
10
15
20
Speed (bytcs/scc)
(h) Surprisal (bits/byte) vs. speed (hytes/sec). The dotted line shows the canonically tokenized baseline's surprisal.
Figure I: Experimental results. Averages are computed over the first 4000 bytes of the wiki test set. Error bars denote bootstrapped 95% confidence intervals. See App. for the full table of results.
The following proposition establishes correctness:
token strings created from byte-pair encoding (BPE; Sennrich et al. (2016); Gage (1994)). 15
Proposition 2. condi Liloonoltoeeeneeeertttttte gen- erates samples according PaJz(- or) for all a E E".
We use the wikitext-1@3-vV corpus source of char- acter strings; we used the version in the datasets library. Specifically, we use the test portion.
Proof. See App. E.
We use the GenLM library with the vLLM (Kwon et al., 2023) backend to perform the efficient, batched evaluation of transformer language models on GPUs. We batch- evaluate all sequence extensions. Experiments were on an L40S GPU with 40GB of memory.
We also note the following corollary, as it gives an inter- pretation for the categorical distribution the efficient
algorithm.
Corollary 1. For all a E,,86 E
Our implementation utilizes a trie to efficiently represent all items in each bucket (see App. D), and the bucket- based pruning heuristic ($3).
p²( 1 (8EC(()) (15)
10. (0))5((((())))) Y~pa
p)(
better understand the quality of the approximation our method provides, we perform the following experiments:""
Thus, we have provided an efficient solution to the prompt boundary problem. We also note that generating from pr: a character at a time is also correct solution to the prompt boundary problem; however, it slower, it does not ben- efit from the fact that the generated string shorter in token
We measure the approximation error the average Jensen-Shannon distance (JSD) to a reference model's conditional distribution over the next byte (Fig. la). We use large beam K 128 as a reference model.
space. This is because once the minimally covering token string has been sampled, the method sample_come will generate complete sequence more efficiently than the Sharacte-att--ttiee sample algorithm.
We evaluate the average surprisal (- log2 probability) of our model's estimated conditional distribution over the next byte in the corpus. As baseline,
the average surprisal (bits/bytes) of the canonical tokenization under the token-level language model (Fig. 1b).
4. Experiments
This section investigates algorithm's 's running time and accuracy. We use the following setup:
Note that in this section be compatible with the byte-pair encoding algorithm. "https:/// t/gtbbb...bb....//// com/ comm/genlm/genlin backend "ome additional baselines and experimental results are included in appendices (F and G).
bytes
of characters
We use the following publicly available models: Llama- 3.2-IB, Meta-Llama-331-88 1-88B, DeepSeek-RI Alama--B, and phi-4 (14B) from the transformers library (Wolf et al., 2020). Each model was trained over
8

---

From Language Models over Tokens to Language Models over Characters
Discussion. As expected, we observe that the speed (bytes/sec) decreases as K increases. We observe an inverse relationship between error (ISD/byte) and speed (bytes/sec); as the processing speed (bytes/sec) decreases, the error also decreases. Notably, this tradeoff is non-linear, with error in- creasing more sharply at higher processing speeds compared to lower speeds. This trend is evident all models; in gen- eral, error appears flatten out after K 2 8. This indicates diminishing returns in reducing error as K gets large. We hypothesize that this occurs because the language model's probability mass is concentrated on limited set of tokeniza- tions, which are adequately covered even with smaller beam sizes. We also observe (as expected) that larger models run more slowly; however, this appears to due to their higher evaluation time rather than the need for larger covers.
Prada Corral, Vésteinn Snæbjarnarson, Samuel Kiegeland, and Yahya Emara for their helpful feedback and discussions. JT would like to thank Rycolab for its hospitality during recent visit. The authors JLG and JT would like to thank Institut des Hautes Études Scientifiques (IHES) for their hospitality while revising this paper. MG was supported by an ETH Zürich Postdoctoral Fellowship. This research was enabled in part by compute resources provided by Mila (mila.quebec).
Impact Statement
The primary impact of this work is a more predictable, user- friendly interface for working with tokenized language mod- els. By ensuring tools behave as expected, we mitigate certain unintended behaviors, such as the prompt-boundary problem highlighted in the introduction. More broadly, we do not anticipate any additional risks beyond those already inherent in the use of tokenized language models.
We also observe that the average per-byte surprisal is sig- nificantly lower under all models than the canonically tok- enized baseline. The reasons for this are twofold: (1) Each model assigns non-negligible probability to noncanonical tokenizations of the corpus, which are being thrown out in the baseline estimate, but that accounted for in our estimate. (2) The most likely tokenization of the corpus is often noncanonical, which our method is better able to find, as our beam beam-summing method uses the probabilities assigned to tokenizations. In contrast, the baseline uses only the hard-coded canonical tokenization. Interestingly, increasing K does not appear to significantly decrease the surprisal, which we suspect is because the relatively greedy (K 2) tokenizations adequately cover it. 18
Limitations
Our method should work well with other tokenized language models, provided they were trained with deterministic tok- enizer. However, if they were trained with stochastic tok- enizer, such as UnigramL (Kudo, 2018) or BPE-Dropout (Provilkov et al., 2020), we would expect that the probabil- ity mass over tokenizations in each covering would not be heavily concentrated on a small subset. Thus, these mod- els may require large beam size, making our approach expensive. Sampling-basee -baied methods may provide better accuracyy tradeoff for this setting.
Conclusion
We have developed an effective method for ameliorating tensions between tokens and characters faced by engineers and users. We gave theory and algorithms that provide a character-level interface to tokenized language models. We characterized and resolved the prompt boundary problem. We investigated the empirical speed and error rates of our method on two modern language models. The primary limitation of our beam summing method is that it requires a very large beam size K if the language model does not favor a small number of tokenizations. The models that we explored in our experiments concentrate mass on a few tokenizations; thus, we did not require large K to estimate their character-level prefix probabilities accurately.
References
Cao, K. and Rimell, L. You should evaluate your language model on marginal likelihood over tokenisations. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2021. URL https: / /aclanthologyy.rg// eenlp-mmanpp... main. 161.
Chirkova, N., Kruszewski, G., Rozen, J., and Dymetman, M. Should you marginalize over possible tokenizations? In Proceedings of the Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), 2023. URL https: h/tp///lcclcc/ http///cannttoooo.ooooooooooooae org 2023.222222222 acl- 1.
Acknowledgments
Gage, P. A new algorithm for data compression. C Users Journal, 12(2), 1994. ISSN 0898-9788. URL https://web.aachhiee.oom arcchive..og//a/2222001111222220 httpss//www.derreyssii.ooopppppp BPE_Gage.pdd.
The authors would like to thank Andreas Opedal, Alex Lew, Ben Lipkin, Jacob Hoover Vigly, Luca Malagutti, Manuel de
We found that K = occasionally resulted in an empty beam, so we do not include it in this experiment.
Gastaldi, J. L.,, Terilla, J., Malagutti, I.,, DuSell, B., Vieira,
9

---

From Language Models over Tokens to Language Models over Characters
T., and Cotterell, R. The foundations of tokenization: Sta- tistical and computational concerns. In Proceedings the International Conference on Learning Representations, 2025. URL htttps://ariiv wwwp:iiioooog/ooooe www.obs/g//////ooooooooos htbbs/2240.1111 11606.
Lundberg, S. and Ribeiro, M. T. The of prompt design: Prompt boundaries and token healing. Medium, 2023, URL https://toowrrdsaatasce art-of prtt boundaries and- token-healing 3b2448344444488888888
com/ ooe
Geng. S., Josifoski. M., Peyrard, M., and West, R. Grammar- constrained decoding for structured NLP tasks with- out finetuning. In Proceedings of the Conference Empirical Methods in Natural Language Processing, 2023. URL https: tttps::/aacaathoollooo owg.orgg///3 2023.222.cc2 emnlp- main. 67..pdf.
Microsoft. Guidance. https://github: http///ccooocooottteoomoo guidance, 2023.
Mikolov, T. Karafiát, M., Burget, L., Černocký, J., and Khudanpur. S. Recurrent neural network based language model. In Proceedings of IN- TERSPEECH, 2010. doi: 10.214377lmterspeechh. 2010-343. URL https://www aiscc-arrchvi orrg/ httsspeech.2000mmkooooooloo.o.e.
Giulianelli, M., Malagutti, L., Gastaldi, J. L., DuSell, B., Vieira, T., and Cotterell, R. On the proper treatment of tokenization in psycholinguistics. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2024. URL https://aclanthology/ org/ 2024. emnlp-main. 1032/.
html.
Oh, B.-D. and Schuler, W. Leading whitespaces of lan- guage models' subword vocabulary poses confound for caleulating word probabilitiess 2024. URL https: //arxiv. org.oggg//aooo attp//bb/////... 10851.
Hale, J. A probabilistic Earley parser as psycholinguistic model. In Meeting of the North American Chapter of the Association for Computational Linguistics, 2001. URL https://aclanthollg org/Ne1-10211 .df.
Phan, B., Havasi, M., Muckley, M. J., and Ullrich, K. Understanding and mitigating tokenization bias in lan- guage models. In ICML Workshop on Theoretical Foun- dations of Foundation Models, 2024. URL https: wwwpeeeewwwweeeeeeeeeee / //openreview. net/ www.:nee/forumiidiieee ottte/oooommdddoddrriyi...
Koo, T., Liu, F., and He, L. Automata-based constraints for language model decoding. In Conference on Lan- guage Modeling, 2024. URI. https://oppereviers ttt//oorummmdddBBdbmmmy
Pimentel, T. and Meister, C. How to compute the prob- ability of a word. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2024. URL https: hwcps///oo..an .rgg/ 2024.022240 -022.emn1p main. 1020/.
Kudo, T. Subword regularization: Improving neural network translation models with multiple subword candidates. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 2018. URL
Poesia, G., Polozov, A., Le, V., Tiwari, A., Soares, G., Meek, C., and Gulwani, S. Synchromesh: Reliable code genera- tion from pre-trained language models. In Proceedings of the International Conference Learning Represen- tations, 2022. URL https: http:////peeeeeeeeeeeeemem wwwprrreeiiieeeeeforrurre. www.werrfffrr id=KmtVD97J43e.
org/P18-1007.
Kwon, W., Li, Z., Zhuang, S., Sheng, Y., Zheng, L., Yu, C. H., Gonzalez, E., Zhang, H., and Stoica, I. Efficient memory management for large language model serving with PagedAttention. In Proceedings the ACM SIGOPS Symposium Operating Systems Principles, 2023. URL https://arxivv org/ abs.a////220000 06180.
Provilkov, I., Emelianenko. D., and Voita, E. BPE- Dropout: Simple and effective subword regularization. Proceedings of the Annual Meeting of the Associa- tion for Computational Linguistics, 2020. URL https: / //aclanthology .rg. acl 170/.
Levy, R. sion. 0277.
Expectation bbased syntactic comprehen- Cognition, 106(3), 2008. ISSN 0010- URL https://www/ http:://wwww.cceeeeddeeeeeee.e.e www.ssieeeeeiit........ com/ science/articn http:///attieeeep/////00////////
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I., et Language models are un- supervised multitask learners. OpenAl blog, 1(8), net/ 2019. http:: http:/tttts//cmeee/s/ss.o...oood pdf.. better- petterrlannugggrmmmma////ggggggg
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. 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 http::://openrvveew net/ forum?id=xoXn62F22000
Scholak, T., Schucher, N., and Bahdanau, D. PICARD: parsing incrementally for constrained auto-regressive decoding from language models. In Proceedings of the Conference on Empirical Methods in Natural, 2021. URL https://doi. htt///oi.ogg///// org/10. 11653/v1/2022 emnlp-main. 779.
10

---

From Language Models over Tokens to Language Models over Characters
Sennrich, R., Haddow, B., and Birch, A. Neural ma- chine translation of rare words with subword units. In Proceedings of the Annual Meeting of the Association for Computational Linguistics. 2016. URL https:// aclanthology.org/e 1tt.oolooo...gg/1--11111 or66
Shannon, C. E. A mathematical theory of communica- tion. The Bell System Technical Journal, 27(4), 1948. URL https::t////ooo /dwi: org/10. 1002 1111553887555 1948. tb00917.X.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. At- tention is all you need. Advances in Neural Infor- mation Processing Systems, 30, 2017. URL https: //arxiv.org. abss/706. 03762.
Willard, B. T. and Louf, R. Efficient guided genera- tion for large language models. CoRR, abs/2307.09702,, 2023. URL https: //doi. 2tt 09702.
Wolf, T., Debut, L., Sanh, V., Chaumond, J., Delangue, C., Moi, A., Cistac, P., Rault, T., Louf, R., Funtowicz, M., Davison, J., Shleifer, S., von Platen, P., Ma. C., Jernite, Y., Plu, J., Xu, C., Le Scao, T., Gugger, S., Drame, M., Lhoest, Q., and Rush, A. Transformers: State-of-the- art natural language processing. In Proceedings of the Conference on Empirical Methods in Natural Language Processing: System Demonstrations, 2020. URL https: //aclanthology.c org/ 2020. emnlp-demos.e 6.

---

From Language Models over Tokens to Language Models over Characters
A. Supplementary Results
This section presents the data for Fig. in tabular form.
A.1. Jensenn-Sannon Distance
-lama-3.2-11
Meta-Llama-3.--8B
K
JSD / byte
bytes sec
JSD byte
bytes / sec
0.00025 (0.00010, 0.00048)
115.18 (110.54, 117.94)
0.00016 (0.00010, 0.00023)
36.03 (35.90, 36.16)
4
0.00006 (0.00005, 0.00007)
91.22 (88.36, 92.97)
0.00005 (0.00004, 0.00005)
32.06 (31.74, 32.27)
8
0.00004 (0.00004, 0.00005)
64.71 (63.50, 65.55)
0.00004 (0.00004, 0.00004)
26.72 (26.43, 26.95)
16
0.00004 (0.00003, 0.00004)
38.77 (37.77, 39.62)
0.00003 (0.00003, 0.00004)
19.03 (18.76, 19.28)
32
0.00004 (0.00004, 0.00004)
20.53 (19.93, 21.11)
0.00003 (0.00002, 0.00003)
11,42 (11.21, 11.62)
0.00003 (0.00003, 0.00004)
9.77 (9.52, 10.02)
0.00002 (0.00002, 0.00002)
5.91 (5.81, 6.02)
128
(not applicable)
4.91 (4.81, 5.02)
(not applicable)
2.97 (2.93, 3.02)
DeepSSekk-RI-Distiil-laaamm
phi-4 (14B)
K
JSD/ byte
bytes sec
JSD byte
bytes see
2
0,00022 (0.00015, 0.00032)
36.64 (36.47, 36.83)
0.00065 (0.00034, 0.00116)
21.17 (21.03, 21.30)
4
0.00009 (0.00007, 0.00014)
32.60 (32.24, 32.87)
0.00012 (0.00008, 0.00017)
19.09 (18.98, 19.18)
8
0.00005 (0.00004, 0.00006)
26.81 (26.52, 27.04)
0.00004 (0.00003, 0.00006)
16.79 (16.69, 16,88)
16
0.00004 (0.00003, 0.00005)
19.26 (18.99, 19.52)
0.00008 (0.00004, 0.00012)
12.81 (12.68, 12.94)
32
0.00005 (0.00003, 0.00007)
11.62 (11.42, 11.83)
0.00003 (0.00003, 0.00004)
7.90 (7.78, 8,01)
64
0.00002 (0.00002, 0.00002)
5.96 (5.86, 6.07)
0.00002 (0.00002, 0.00002)
4.16 (4.10, 4.22)
128
(not applicable)
3.01 (2.97, 3.06)
(not applicable)
2.44 (2.40, 2.48)
12

---

From Language Models over Tokens to Language Models over Characters
A.2. Surprisal
Canonically Tokenized Baseline bits / byte
Model
Llama-3.2-1B
0.76 (0.69, 0.83) 0.66 (0.59, 0.74) 0.93 (0.83, 1.03)
Meta-Llama-331-8B
SrapScck-RI-Distl-Llllmee
phi-4 (14B)
0.68 (0.61, 0.76)
Llama-3.2-1B
Meta-Llama-3.1-8B
K
bits byte
bytes/ sec
bits byte
bytes / sec
2
0.63539 (0.58988, 0.68280)
115.18 (110.54, 117.94)
0.53339 (0.49164, 0.57577)
36.03 (35.90, 36.
0.63593 (0.59076, 0.68238)
91.22 (88.36, 92.97)
0.53173 (0.49087, 0.57468)
32.06 (31.74, 32.27)
0.63540 (0.58932, 0.68020)
64.71 (63.50, 65.55)
0,53202 (0.49109, 0.57463)
26.72 (26.43, 26.95)
16
0.63518 (0.58985, 0.68186)
38.77 (37.77, 39.62)
0.53208 (0.49058, 0.57452)
19.03 (18.76, 19.28)
32
0.63524 (0.58988, 0.68187)
20.53 (19.93, 21.11)
0.53176 (0.49012, 0.57411)
11,42 (11.21, 11.62)
0.63525 (0.59041, 0.68259)
9.77 (9.52, 10.02)
0,53180 (0.48991, 0.57464)
5.91 (5.81, 6.02)
128
0.63550 (0.59101, 0.68157)
4.91 (4.81, 5.02)
0.53175 (0.49091, 0.57396)
2.97 (2.93, 3.02)
DeepSSea-RR--Distil-lammmm
phi-4 (14B)
K
bits / byte
bytes sec
bits / byte
bytes / sec
2
0.76195 (0.70150, 0.82342)
36.64 (36.47, 36.83)
0.56296 (0.51968, 0.60938)
21.17 (21.03, 11.03, 21.30)
4
0.76134 (0.70160, 0.82244)
32.60 (32.24, 32.87)
0.56345 (0.51961, 0.60944)
19.09 (18.98, 19.18)
8
0.76136 (0.70270, 0.82294)
26.81 (26.52, 27.04)
0.56194 (0.51601, 0.60854)
16.79 (16.69, 16.88)
16
0.76101 (0.70137, 0.82419)
19.26 (18.99, 19.52)
0.56228 (0.51854, 0.60802)
12.81 (12.68, 12.94)
32
0.76080 (0.70129, 0.82283)
11.62 (11.42, 11.83)
0.56192 (0.51807, 0.60742)
7.90 (7.78, 8.01)
64
0.76128 (0.70313 0.82384)
5.96 (5.86, 6.07)
0.56206 (0.51752, 0.60760)
4.16 10, 4.22)
128
0.76093 (0.70029, 0.82178)
3.01 (2.97, 3.06)
0.56185 (0.51753, 0.60815)
2.44 (2.40, 2.48)
13

---

From Language Models over Tokens to Language Models over Characters
B. Proof of Proposition 1
Proposition 1. Suppose (2, is a tokenization model where strict-prefix monotone and pa a token-level language model. Then, the prefix probability p3((0) for the character-level model Eq. (6) is given by
p=())= (lo)=Ep((0 Oo())
Y
(13)
óEC(o)
Proof. We prove the proposition through the following manipulations.
pO(0)=
Σ 1fo 1 =(0'))p=(8')
(16)
8'EA-
1fa (c)
(17)
8'EA
1(o (e) Σ (((()) - x(6'0' (/) p3
(18)
6-5--8"EA+
1{ = (E) + Σ 1 1xx(0) < a =(600')) Σ
Pa Pa
(19)
6-8EA
8"E2"
1fo = (E) + Σ
1(x(0) < x((-0())) (6-8")
(20)
E'E
1E3(0)
(21)
6EC(o)
About the steps above: We start with the summation expression for the character-level prefix probability (i.e., Eq. (11)). We expand the summation into two cases (so that it will eventually match the two cases the expression for the covering Eq. (12)). Next, for each summand, we consider its unique minimal prefix 5-5' covering a. We see why E is handled separately, it cannot be covered by token sequence of that form. We exploit the key property of prefix monotone tokenizers (i.e., that once 8-8' covers a, each extension 8-8' 8" continues to cover it). This allows us to rearrange the summation to sum over the extension 8", which is conveniently equal to the prefix probability of 8-0', The final step is to recognize that the summands can all be indexed by the covering C(o).
14

---

From Language Models over Tokens to Language Models over Characters
C. The Size of the Covering
now set about to bound the worst-case size of the covering function. To do so, we introduce additional definitions that characterize the different growth factors.
We define k's fertility
F max max H6 = =(6-0')) S SE oE2
(22)
Example 3. The BPE tokenizer has FBPE 1 because is multiplicative, and its tokens represent distinct substrings. More formally,
FBPE max 1(0' E A: o= =====((08")) x(6-8')
[def of fertility)
(23)
max max 110' E EA: ===0==())(()))) JEA" dEΣ
[def mubipliccatiiit]]
(24)
(6' A: o' o'=
[def function]
(25)
1
[distinctnesa]
(26)
Additionally, we define a k's munch as follows.
M def max max [k((--)] - |s((0]
(27)
dea SEA
In words, the munch measures the length of the largest number of characters that can be introduced by adding one more token to any given context.
Example 4. The munch of a multiplicatiie such as BPE, is maxsea [x())] Put in words, it is the length of the longest detokenization. The munch for GPT-2 is surprisingly long (128).
Proposition 3. Let F and M be the fertility and munch of k. Then, for all a E E',
(28)
where
0
in <
1
i 0
C(n)
(29)
C())
otherwise)
j=n-M M
Proof. The base cases N & 0 are straightforward. Consider the case of a string of length N 2 Inductive hypothesis: Suppose for all strings a' with |o'l < N, [C(o') S C((o')).
15

---

From Language Models over Tokens to Language Models over Characters
Let be an arbitrary string with length N 0.
(30)
=
-0--0
x(6-8))
(31)
N
Ufö-BE k(0) = 01 o3.0 ON 1 x(6-))}
(32)
I=
N-1
(ŌE =(0)=
DEE:DEAA ,0 ON 3 {x(6-8))
(33)
j= -=N-M -M
[((()ma)))
SF
S F.
(34)
j=N M
inductive hypothesis
< F Σ CUI
(35)
N
= =(N)
(36)
Thus, the proposition holds true by the principle of induction.
Corollary 2. Let N lorl- Consider the following cases:
When M = N and F = 1, C(N) 2
When M = N and F 2 0, C(N) F(1+F)*
Otherwise, C(N)= = FN Fib(NN M) where Fib(N, M) is the Noh Mth-order Fibonacci number."
In all cases, C (N) oc.
In the proposition below, we show that the covering can easily be exponential in size: Proposition 4.
((()) (2(2
(37)
Proof. We prove the proposition by constructing an example that achieves the lower bound.
Let = (a).
a aa
Let k be multiplicative, and define x()) def a, (2) def aa.
Let be an arbitrary string from >" Let N = |o).
Then, |E(a)) 2 the number of nonnegative integer solutions (n, m) to m + 2n = N. This is because can build the N accounts for So if n the number of token and m the number of token 2, must have that 1 + 2n N. The number of solutions grows like 9(2-N). Lastly, because C(a) 2 E(o), we have that (C(ar) 1(21ol), Thus, the proposition holds.
using a sequence of", ; or as each accounts for and each as
19 "Mhh-oodee Fibonacci numbers variation of the well-known Fibonacci (i.e., M 2) that the previous M numbers in the sequence instead of the previous two.
16

---

From Language Models over Tokens to Language Models over Characters
D. Bundled Beam Summing Implementation
Upon implementing this scheme, we observed that it is possible to efficiently reason about all the next tokens that extend a given token sequence in the cover in bulk. The key idea is group the token sequences that fall into the same bucket in prune_ trune_top_Kee Sop___buckeee into Bundle (see below) that represents them compactly. In particular, we can use probability trie to efficiently filter out the next tokens that disagree with the next character. This improves the per-iteration cost of that filter as the data structure does the organizational work ahead of time (in bulk). We can regard the probability trie as local language model that generates the next token tharacter-yy-charece according to the probability assigned to it by Pá 6). Each bundle can be unbundled (see method unbundle) into the respective tuples that the envm_cover algorithm maintains. The algorithms are otherwise equivalent.
s4 def beam(01--
s5 if N = 0: return [Bundle E, e, (s)
56 candidates < Q
57
for bundle in beam(o1--oN))) (ictered_bundLL + bundle. filter
59
if filterrd_bundle is not None:
60
candidates Candiddtts..appennffllll... (fleen(filtered_bbbm) for extended_bundle in bundle, extend():
61
62
candidates.. senddiddtes.appen(((eee append(extended__uug (fteeneeee_uulllee.llee((rr))))" filter(ax))
63 Keep top-K K bundles according their prefix probability
return topx (candidates, key=lambda bundle: -bundle.pp
Each bundle is an instance of the following class with four member variables: the prefix probability p. token string character string o, and reference to local probability trie trie. The trie provides the character-level probabilities of the distribution over possible next tokens: (- 6). The trie is also augmented with special symbol EOT to denote the end of this next token." 20
65 class Bundle(p, 8, o, trie):
67
def filter(o'):
68
if trie.p(o' o)) = 0: return # no tokens give prefix and prob
return Bundle trie(o' o), 6, a'o', trie)
69
70
71
def extend():
72
Z + trie.p(EOT o)
73
if Z > 0: emit tokens that decode to for (0',p') in brie. fieelokens[[]) yield Bundle( 1/, 5.0', build_trie(d-'')
74
75
The code below builds the probability trie from the possible next tokens. It figures out the character strings associated with those next tokens and puts them into the trie with the respective probabilities."
76 def build_trie(d):
x(6)
# remember common prefix
78 Irie + ProbabilityTrie()
# uses EOT to mark the end of token
79 for A
80 a-0' a-O' =x6-00")
# use new characters, i.e., ignore prefix o # add o' and 8' to trie with this probability
s1 trie. hiieaddd('',8 ( [8)
82 return Irie
The probability trie has the following functionality:
trie. tokenso [o'] stores the set of tokens that decode to o' along with their respective mass.
29This is completely analogous to how EOS marks the end of a string.
Note that EOS is handled as an indivisible symhol the probability trie, whereas other tokens can he expanded into characters (or bytes).
17

---

From Language Models over Tokens to Language Models over Characters
Irie.p(o') σr) returns the probability of the character o' given o, it is proportional to
1K((8-8) = (1x(()))) ž o.0
if = COT
brie.plo' o0) Σ p 6)
(38)
otherwise
We note that the trie implicitly depends on the token string used in its creation.
To aid in understanding how the bundled algorithm relates the original algorithm, give the following methods.
83 class Bpn 6, a, trie):
84
85 def unbundle()
86
agenda [o]
while agenda:
0' + agenda.
Z + f(EO. o')
89
if Z > 0:
90
for (8'.p') pp)) E trie.tokens [o']:
91
yield (p-1', x(6-8'), 8-8')
92
for o" in trie.p(- lo):
93
if o" * EOT: agenda ap'end
96 def rebundle_beam(beam)
97 return [item for bundle in beam for item in bundle. unbundle
We note that unbundle_ cuuundle_beambbemm(o)) gives precisely the same of elements as the unbundled algorithm (i.e., enum_cover((r)) on the same string and the bucket-based pruning scheme with parameter K (up to reordering).
To compute the next-character probability, we use the following algorithm:
vs def mext_chaarateer.prbbaallttt
method-beam):
{a': 0 for o' U [FOs}}
for bundle in method((a): # use beam approximation by default for a' E Σ:
P(o') += bundle.p bundle.trie.p(o' bundle.or)
103
for ext_bundle in bundle. extend()::
for e'
104
p(a') ext_bundle.pp ext_bundlee.rie.ppo" (ext_bundle.r)
105
Z sum(p. values))
return (o': p( for of Σ}
18

---

From Language Models over Tokens to Language Models over Characters
E. Proof of Proposition 2
Proposition 2. condi tional_ cond
generates samples according to PaIs(- for all o E Er.
Proof (Sketch). Choose an arbitrary A"
Paps(6lo)
= P Y = ) al
(39)
Ympa
1 ((x(0) 2 a
= PP)(
(40)
P (M(() a
Y~Da
Pá (6) ビ [
(41)
(o)
Let 8' (0) (i.e., the shortest prefix of 6 such that k<(0) = σ). Choose 8" such that 8'-8" 6.
p (EOS 8'' (00 8') 1 (x((') ba}
(42)
(O(
sample completion
sample from covering
We can see that the algorithm samples from this distribution because it samples a token string 8' from the covering in proportion to the right factor in Eq. (42) and then samples a completion 8" of in proportion to the left factor of the equation. Thus, the sample 5 8'-5" has probability Pajs (6 (r), and condi tional, tonnnalltteennneertttiii sampling procedure for
a correct
19

---

From Language Models over Tokens to Language Models over Characters
F. Token Healing Baseline
We implemented an additional baseline character-level model based on a token healing heuristic described in $1. While not competitive with our proposed methods, we include it here for completeness. Explain the idea, and provide pseudocode below. The experimental results are summarized in Tab. We observe significantly higher surprisal (bits/byte) and error (ISD/bytes) compared to the methods in Fig. 1.
An approximate covering inspired by token healing. Our version of the token healing heuristic is based an approximate covering. Given character string E Σ* and its tokenization di ... 8N = ( we define its token healing approximate covering as follows:
C del (61 8N-1 8' m(Ōx) k(('))
(43)
By construction, x(01 -- 6N-1) o 3 n(01 6N). it is straightforward to that (o)al(o)) S C(o). We also note that the size of this approximate covering is bounded by the size of the token alphabet: (Cnea(()) [4].
Implementation. The code below implements a method for efficiently constructing (o)) ). It is based on the bundled implementation given App. D.
def token_ boken_healing.. co)e if o =: no tokens to heal
110
return [Bundle(1, E, E, build_trie(s)] else
m
112
81 T. Ón + r(o)
113
trie bu 1N-1)
o' x66x) return [Bundle (p2(61 8N-1) trie.plo' |=), 8N-1, o', tric)]
We first tokenize the input character sequence or into a sequence of tokens 6. We then construct a probability trie for -1 -1 (i.c., all but the last token), allowing us to compute the probability each possible next character of by querying the trie with the character suffix a' corresponding to the final token.
Compared to the beam algorithm, token_ heal iigiinnoooo cover method represents extreme form of pruning: it returns a beam of exactly one bundle. It also differs from the variant of token healing we described in $1, which produces token-level predictions rather than character-level predictions.
To estimate p (: o) we use cchraccte_pproheee still fails to place an appropriately high probability on when conditioned on Hello, This happens for the same reasons as we described $1.
Lakeen_healinge coverr. However, this approximation
Experimental results. The table below presents experimental results that may be compared to those of other methods in the paper. We found that the method performs poorly enough that do consider it competitive approximation.
Model
Surprisal (bits/byte)
Error (JSD/byte)
Speed (bytes/sec)
SeepSeee--I--istil-LLLiin Llama-3.2-1B
2.529 (2.391, 2.670)
0.1907 1800,00, 0.2015)
36.70 (36.64, 36.76)
2.126 (2.010, 2.246)
0.1790 (0.1691 0.19
119.35 (118.73, 119.84)
Meta-Llamaa3311991
2.116 (1.992, 2.243)
0.1840 (0. 1738, 0.1646)
36.61 (36.55, 36.67)
phi-4 (14B)
2.204 (2.075, 2.333)
0.1857 (0. 1757, 0. 1960)
21.24 (21.13, 21.30)
Table 1: Surprisal, JSD, and speed for the token- -hallig baseline across models using the same experimental settings as Fig. 1.
2f a s, ChealE) de
20

---

From Language Models over Tokens to Language Models over Characters
G. Probability-Based Pruning Heuristic
This section presents some additional experimental results with more extensive pruning method, based on the relative contribution of token string to the current cover approximation.
Probability-based pruning heuristic. The method works by augmenting the beam pseudocode with some additional pruning based threshold 0 [o, 1]. The benefit of this pruning is that it avoid calls bundle. extend(), which requires evaluating the language model (i.e., the performance bottleneck of our algorithm). It is often the case that for given character string prefix, there is no reason to perform any extend operations because all tokenizations of that string are low probability; thus, filtering operations are needed.
116 def beamk, (0 ON):
117 if N 0: return [Bundle(1, E, e, b candidates + []
< beam(11 NN-1)
for bundle in B:
fiudeee +- bundle. filterf
122
if filtered__bude is not None:
123
candidates sppend(filteree__und13
124
+ A. sum(bundle. for bundle in candidates)
for bundle in
if bundle p 7:
for likended_bundI1. in bundle, extend(()
candidates. (extendded _unddle_dddeeeeeee filter
129
Keep top- K bundles according to their prefix probability
130
return topx (candidates, key=lambda bundle: -bundle.p)
21

---

From Language Models over Tokens to Language Models over Characters
Experiments. Below, we extend the experiments of the main text with this additional pruning heuristic to better understand its speed and accuracy.
DeepSeck-RI SeisSock-RI-istillee S
Jama-88
Liama-3 2:2-B
Meta-LLlama- 3.1-8B
phi-4 (14B)
0.0025
0,0008
0.0006
0.0012
0.0020
0.0006
0.0009
JSD
0.0015
0.0004
0.0010
0.0004
0.0006
0.0005
0.0002
0.0002
0.0003
0.0000
0.0000
0.0000
m3
0.0000
25
50
75
100
100
200
300
30
60
90
21
40
60
Speed (bytes/sec)
2.0
8.0
32.0
0.0
0.0025
Max beam size
Prune threshold
4.0
64.0
0.001
0.01
(a) Error (JSD/byte) vs. speed (bytes/sec), Here we compute the JSD between the byte-level conditional distributions computed with beamx.0 for (K, 8) (4, 8, 16, 32, 64} x {0, 0.001, 0.0025, 0.01} and the reference model (K 128, 0 0). Missing values indicate "dead-ending" (i.e., empty beam) result of overly aggressive pruning.
DeepScok-R1 Boaicck----Diiill---a------
Llama-3.2-1
Meta-Llama-- 3.1-8
phi-4 (14B)
0.70
Surprisal
0.9
0.75
0.65
0.65
0.70
0.60
0.8
0.65
0.55
0.60
140
0.55
0.60
0.50
0.50
25
50
75
100
200
300
30
60
90
10
20
30
40
50
Speed (bytes/scc)
2.0
8.0
32.0
0.0
0.0025
Max beam size
Prunc threshold
4.0
16.0
64.0
0.001
0.01
(b) Average surprisal (bits/hyte) vs. speed (bytes/sec) for beamı, with {4,8, 16, 32, 64) {0, 0.001, 0.0025, 0.01}. The dotted line represents surprisal of the canonically tokenized under the token-level language model. Missing values indicate infinite surprisal result excessive pruning.
Figure 2: Additional experimental results showing the effects of the pruming thresholds on error vs. speed and surprisal vs. speed using the same settings in $4.
22


Reviews:
[{"review_id": "FXQ4isb6fd", "reviewer": "Reviewer_us9y", "summary": "This paper is motivated by addressing the \"prompt boundary problem\" in token-level language models. In models using tokenizers like BPE, even small changes at the prompt boundary, such as adding a whitespace, can dramatically alter the next token distribution in unintuitive ways, which is undesired behavior.\nThe authors propose a principled solution to convert token-level language models into character-level ones. Their method is built around the concept of a \"covering\" - the set of all minimal token sequences that, when decoded, would produce a given character string or a string having it as a prefix. By considering the weighted probability distribution across this entire covering rather than just a single tokenization, the method correctly computes character-level probabilities from token-level language models.\nThe paper presents both exact algorithms and efficient approximations based on beam search for computing these character-level probabilities. Their experiments show that with reasonable computational resources, their method achieves high accuracy in estimating character-level distributions with minimal error at practical speeds on models like Llama 3.1 8B, effectively solving the prompt boundary problem and creating a more intuitive interface for working with tokenized language models.", "questions": "", "limitations": "", "rating": 3, "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\nMany reviewers suggested that our evaluation methodology, which uses a large beam as a proxy for ground truth character-level probabilities, may have some systematic bias. We will add discussion to the paper about the challenge of designing a faithful evaluation as well as the possible pitfalls in our large-beam evaluation scheme.\n\nThat being said, we agree that our evaluation can be improved. In subsequent revisions of the paper, we will seek to address this in the following ways:\n\n- **Additional baselines and comparisons**:\n  - **Token healing for character-level probabilities**: Thanks to a suggestion from reviewer DnV9, we will add a comparison between our algorithm and an algorithm based on token healing for inferring character-level probabilities.\n\n  - **Perplexity per byte**: Based on the suggestion by reviewer DnV9, we will add a comparison between our method’s byte-level cross-entropy and the byte-normalized cross-entropy of a token-level language model.\n\n  - **Increased beam-width**: We will further increase the beam width of the baseline model, bringing it even closer to the ground truth and reducing any potential bias in the comparison.\n\n- **Evaluation of downstream accuracy on LM reasoning benchmarks**: We agree that some evaluation of the downstream effects of our approach would strengthen the paper.  Therefore, we will investigate the feasibility of adding an evaluation of the downstream accuracy on one or more common LM reasoning benchmarks (e.g., HellaSWAG or GLUE).  However, we do not necessarily expect to see benefits.  It's possible that randomly shifting the prompt boundary to the left would be interesting.  Consider an example from HellaSWAG:\n\n  ```\n  Prompt: \"A man is sitting on a roof. He \"\n  . \"is using wrap to wrap a pair of skis.\",  \n  2. \"is ripping level tiles off.\",  \n  3. \"is holding a rubik's cube.\", \n  4. \"starts pulling up roofing on a roof.\"\n  ```\n  We would randomly shift the prompt left, e.g., move `\"of. He\"` from the end of the prompt to the possible continuations:\n\n  ```\n  Prompt: \"A man is sitting on a ro\"\n  1. \"of. He is using wrap to wrap a pair of skis.\", \n  2. \"of. He is ripping level tiles off.\", \n  3. \"of. He is holding a rubik's cube.\", \n  4. \"of. He starts pulling up roofing on a roof.\"\n  ```\n\nWe note, however, that we do not claim that our method must improve performance on downstream tasks, e.g., math reasoning. The purpose of our approach is to enable a character-level interface to a tokenized LM, which naturally solves the prompt boundary problem.\n\n### Response to Reviewer us9y\n\nThank you for the review and constructive suggestions for improving our experimental evaluation.  [We are also glad you appreciated the color coding!]\n\n> For the experiment, the ground truth in this evaluation is an approximation obtained using a very high beam size (K = 128) from the same method, it may inherit the biases or errors of that approximation. Evaluating on real-world datasets would provide stronger evidence that the method effectively resolves the prompt boundary problem in practical scenarios, rather than only on controlled benchmarks.\n\nThis is a reasonable concern: Essentially, the concern is that beam size K=64 might be really good at predicting K=128 because they systematically make the same kinds of errors.  We treat K=128 as essentially ground truth, which we have not proven is the case.  We will discuss this issue in the revised paper, as it is an important limitation of our experiment design.  Thank you.\n\n> The evaluation is primarily conducted on a single corpus. Expanding experiments to include diverse, real-world datasets would help validate the method’s robustness and provide more practical insights into how it improves actual problem-solving.\n\nThanks for this suggestion! We will investigate the feasibility of adding a downstream accuracy evaluation on a common LM benchmark, e.g., HellaSWAG, GLUE.  Note that we do not intend to claim that our method will necessarily improve model performance on downstream tasks (unless there are prompt boundary issues).  We emphasize that enabling a character-level interface to language models is valuable in its own right—for instance, when measuring character-level surprise for psycholinguistic experiments ([Giulianelli et al., 2024](https://arxiv.org/abs/2410.02691)) or handling tasks that inherently require fine-grained character-level control.\n\n> The evaluation is evaluated against the same method but with higher beam search K, this may introduce bias.\n\nGreat point.  Please see the general response.", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "For the experiment, the ground truth in this evaluation is an approximation obtained using a very high beam size (K = 128) from the same method, it may inherit the biases or errors of that approximation. Evaluating on real-world datasets would provide stronger evidence that the method effectively resolves the prompt boundary problem in practical scenarios, rather than only on controlled benchmarks.", "theoretical_claims": "yes", "experimental_designs_or_analyses": "please see above", "relation_to_broader_scientific_literature": "This paper is related to tokenization in LLMs, prior works have identified the problems with token-level models processing character-level prompts, this paper formalizes this problem of prompt boundary. This work also relates to constrained decoding works, where converting a token-level LLM to a character level LLM helps in constrained decoding.", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "Pros:\n1. The paper effectively formalizes the challenge of converting token-level LLMs to express character-level outputs. Its formulation is clear and the use of color-coded notations enhances readability.\n2. The proposed method incorporates beam search pruning to significantly improve efficiency. \n3. The authors demonstrate its effectiveness under a reasonable computational budget.\n\nCons:\n1. The evaluation is primarily conducted on a single corpus. Expanding experiments to include diverse, real-world datasets would help validate the method’s robustness and provide more practical insights into how it improves actual problem-solving.\n2. The evaluation is evaluated against the same method but with higher beam search K, this may introduce bias.", "other_comments_or_suggestions": "no", "questions_for_authors": "please see other sec", "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": "0HvHX7zsCj", "reviewer": "Reviewer_zQVq", "summary": "This paper presents an algorithm for converting token-level language models for character level language models. The authors present compelling analysis as well as detailed explanation. This work also includes practical experimental evaluation results.", "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\nMany reviewers suggested that our evaluation methodology, which uses a large beam as a proxy for ground truth character-level probabilities, may have some systematic bias. We will add discussion to the paper about the challenge of designing a faithful evaluation as well as the possible pitfalls in our large-beam evaluation scheme.\n\nThat being said, we agree that our evaluation can be improved. In subsequent revisions of the paper, we will seek to address this in the following ways:\n\n- **Additional baselines and comparisons**:\n  - **Token healing for character-level probabilities**: Thanks to a suggestion from reviewer DnV9, we will add a comparison between our algorithm and an algorithm based on token healing for inferring character-level probabilities.\n\n  - **Perplexity per byte**: Based on the suggestion by reviewer DnV9, we will add a comparison between our method’s byte-level cross-entropy and the byte-normalized cross-entropy of a token-level language model.\n\n  - **Increased beam-width**: We will further increase the beam width of the baseline model, bringing it even closer to the ground truth and reducing any potential bias in the comparison.\n\n- **Evaluation of downstream accuracy on LM reasoning benchmarks**: We agree that some evaluation of the downstream effects of our approach would strengthen the paper.  Therefore, we will investigate the feasibility of adding an evaluation of the downstream accuracy on one or more common LM reasoning benchmarks (e.g., HellaSWAG or GLUE).  However, we do not necessarily expect to see benefits.  It's possible that randomly shifting the prompt boundary to the left would be interesting.  Consider an example from HellaSWAG:\n\n  ```\n  Prompt: \"A man is sitting on a roof. He \"\n  . \"is using wrap to wrap a pair of skis.\",  \n  2. \"is ripping level tiles off.\",  \n  3. \"is holding a rubik's cube.\", \n  4. \"starts pulling up roofing on a roof.\"\n  ```\n  We would randomly shift the prompt left, e.g., move `\"of. He\"` from the end of the prompt to the possible continuations:\n\n  ```\n  Prompt: \"A man is sitting on a ro\"\n  1. \"of. He is using wrap to wrap a pair of skis.\", \n  2. \"of. He is ripping level tiles off.\", \n  3. \"of. He is holding a rubik's cube.\", \n  4. \"of. He starts pulling up roofing on a roof.\"\n  ```\n\nWe note, however, that we do not claim that our method must improve performance on downstream tasks, e.g., math reasoning. The purpose of our approach is to enable a character-level interface to a tokenized LM, which naturally solves the prompt boundary problem.\n\n### Response to Reviewer zQVq\n\nThank you for the thoughtful review and the kind words.\n\n> Methods And Evaluation Criteria: The authors evaluated their algorithms using GPT2 and Llama 8B models on the Wikitext dataset—a reasonable choice. They measured performance using Jensen-Shannon distance between a high-budget model (treated as ground truth) and various faster approximation models. While this approach makes practical sense, it remains somewhat unsatisfying. Could the authors compare their methods against a truly exact model using full coverings, at least in small-scale settings? This would provide a more rigorous baseline for evaluation.\n\nUnfortunately, using a truly exact model is not feasible as marginalizing over tokenization of even short strings quickly becomes infeasible.  We don't think that short string comparisons of beam summing's performance would necessarily generalize to the case of longer strings.  So we worry that it might be misleading.\n\nAnother option we considered was evaluating our method's ability to convert a probabilistic context-free grammar over a tokenized set of symbols into a character-level model, as it is possible to compute those probabilities in cubic time; however, it is unclear whether the results would generalize to the general LM setting.  We are happy to discuss this option further in the discussion period.", "claims_and_evidence": "The claims are backed by convincing theoretical and empirical analysis.", "methods_and_evaluation_criteria": "The authors evaluated their algorithms using GPT2 and Llama 8B models on the Wikitext dataset—a reasonable choice. They measured performance using Jensen-Shannon distance between a high-budget model (treated as ground truth) and various faster approximation models. While this approach makes practical sense, it remains somewhat unsatisfying. Could the authors compare their methods against a truly exact model using full coverings, at least in small-scale settings? This would provide a more rigorous baseline for evaluation.", "theoretical_claims": "They appear reasonable.", "experimental_designs_or_analyses": "See my concerns in Methods And Evaluation Criteria. The experimental design and analysis is largely convincing.", "relation_to_broader_scientific_literature": "To the best of my knowledge, this paper is very upfront about introducing prior work, including mentioning existing solution to the token boundary problem using token healing heuristics, and also presents compelling analysis revealing their short comings.", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "Strength:\n\n- Generally the paper is well written, the authors made considerable effort to put together this research.\n- The research topic and idea is very novel and compelling.\n- I really appreciate the author's effort in systematically explaining the problem, existing solutions and their shortcomings. The explanations are valuable contributions in and of itself.\n\nWeakness:\n\n- Would be great if the authors can repeat the comparison with an exact character model.", "other_comments_or_suggestions": "N/A.", "questions_for_authors": "N/A.", "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": "8uRrAMTwsc", "reviewer": "Reviewer_DnV9", "summary": "The paper highlights the fact that language models over tokens are _not_ language models over characters, at least the way they are normally used. To be specific, the standard procedure of taking a prompt, tokenizing it, and then sampling from the model conditioned on the token sequences is _not_ the same thing as sampling from the model's distribution conditioned on the prompt as a textual prefix. The paper introduces the idea of a _covering_ which is a sufficient set of token sequences that, if evaluated by the model, allow one to sample properly from the text conditioned distribution. An approximation of this covering is also given for computational convenience.", "questions": "", "limitations": "", "rating": 3, "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\nMany reviewers suggested that our evaluation methodology, which uses a large beam as a proxy for ground truth character-level probabilities, may have some systematic bias. We will add discussion to the paper about the challenge of designing a faithful evaluation as well as the possible pitfalls in our large-beam evaluation scheme.\n\nThat being said, we agree that our evaluation can be improved. In subsequent revisions of the paper, we will seek to address this in the following ways:\n\n- **Additional baselines and comparisons**:\n  - **Token healing for character-level probabilities**: Thanks to a suggestion from reviewer DnV9, we will add a comparison between our algorithm and an algorithm based on token healing for inferring character-level probabilities.\n\n  - **Perplexity per byte**: Based on the suggestion by reviewer DnV9, we will add a comparison between our method’s byte-level cross-entropy and the byte-normalized cross-entropy of a token-level language model.\n\n  - **Increased beam-width**: We will further increase the beam width of the baseline model, bringing it even closer to the ground truth and reducing any potential bias in the comparison.\n\n- **Evaluation of downstream accuracy on LM reasoning benchmarks**: We agree that some evaluation of the downstream effects of our approach would strengthen the paper.  Therefore, we will investigate the feasibility of adding an evaluation of the downstream accuracy on one or more common LM reasoning benchmarks (e.g., HellaSWAG or GLUE).  However, we do not necessarily expect to see benefits.  It's possible that randomly shifting the prompt boundary to the left would be interesting.  Consider an example from HellaSWAG:\n\n  ```\n  Prompt: \"A man is sitting on a roof. He \"\n  . \"is using wrap to wrap a pair of skis.\",  \n  2. \"is ripping level tiles off.\",  \n  3. \"is holding a rubik's cube.\", \n  4. \"starts pulling up roofing on a roof.\"\n  ```\n  We would randomly shift the prompt left, e.g., move `\"of. He\"` from the end of the prompt to the possible continuations:\n\n  ```\n  Prompt: \"A man is sitting on a ro\"\n  1. \"of. He is using wrap to wrap a pair of skis.\", \n  2. \"of. He is ripping level tiles off.\", \n  3. \"of. He is holding a rubik's cube.\", \n  4. \"of. He starts pulling up roofing on a roof.\"\n  ```\n\nWe note, however, that we do not claim that our method must improve performance on downstream tasks, e.g., math reasoning. The purpose of our approach is to enable a character-level interface to a tokenized LM, which naturally solves the prompt boundary problem.\n\n\n### Response to Reviewer DnV9\n\nThank you so much for your review. It has been incredibly helpful as your suggestions for additional baselines are fantastic, and we will add them (more below). \n\n> re: \"bits per byte\" suggestion\n\nThank you for this suggestion! This is a great comparison to run, and we plan to add it to our experimental evaluation.\n\n> re: a token-healing-based baseline\n\nThis is an incredibly good suggestion. Coincidentally, we used that method precisely during debugging but didn't think of adding it as a baseline.  What an excellent idea - thank you! \n\n> I think the footnote corresponding to \"10\" in Figure 1 seems to be missing?\n\nIt will be fixed in the next revision.  The text for the two footnotes in Fig 1 (i.e., 10 and 11) appear on the previous page, on lines 376–384 [left column], as footnotes labeled with the same numbers.\n\n> Re: Importance sampling\n\nImportance sampling could be used to estimate the prefix probability (and indeed it is unbiased for that).  However, it does not give an unbiased conditional prefix probability, as it requires the division of two prefix probabilities.  We briefly experimented with sequential Monte Carlo but found that noncanonical token sequences were strongly overrepresented.  For example, when we use it on the string `\"SELECT * FROM\"` roughly 94% of GPT-2's samples start with the token `S` rather than the canonical token `SELECT`. So, we ended up ruling it out in favor of beam search.  Perhaps a more sophisticated proposal distribution would help.  We suspect that it is useful to represent particles as \"buckets\" as we did in our pruning heuristic (starting on line 337).\n\nIt's possible that we should add something about this 'negative result' to an appendix.", "claims_and_evidence": "The paper proceeds very logically from its premise to conclusions. I believe all of the theoretical claims made are well-supported.", "methods_and_evaluation_criteria": "I think the method proposed (using the full cover) is exactly the correct thing to do, although it is not very practical due to its exponential time complexity (which is unavoidable). The approximation given is the most natural approximation of the full problem.\n\nThe evaluation criterion (JSD on next byte) is valid but I do think leaves something to be desired. I would be interested in seeing the cross-entropy loss at the byte level, this could be compared to the byte normalized loss of the LM at the token level (i.e. the \"bits per byte\") which is obtained by converting the standard cross entropy loss from units of nats/token to bits/byte (for a certain text).", "theoretical_claims": "I did not carefully check the proofs in the appendix, but I strongly believe the propositions are correct.", "experimental_designs_or_analyses": "The existing experiments are valid and I appreciate the results. But I think the paper misses a chance to really motivate the problem. Basically the existing comparison is between the proposed algorithm with a small beam width and the same algorithm with a large beam width. I think the paper would be much stronger if a comparison was made between the proposed algorithm and the existing practice of simply tokenizing the prefix and sampling as well as the token healing correction heuristic. Of course, neither of these are the \"correct\" thing and so I would expect the proposed algorithm to beat them soundly, especially with a large beam width. If there is a big difference, then there's a clear motivation for using the proposed algorithm if one cares about byte conditioned sampling. On the other hand, if there isn't a big difference, it means that the heuristics may be \"good enough\" which is something we didn't know before!", "relation_to_broader_scientific_literature": "This paper can be thought of as an extension of the work of marginalizing over segmentations of a text (Cao & Rimell, 2021; Chirkova et al., 2023) but done in a manner that is \"open to the right,\" which allows one to consider sampling an extension of the text.", "essential_references_not_discussed": "I'm not aware of any prior papers on this exact topic. All of the related papers I know of are discussed fairly in the paper.", "other_strengths_and_weaknesses": "I really appreciate the clarity of the presentation. I found the paper very enjoyable to read.", "other_comments_or_suggestions": "I think the footnote corresponding to \"10\" in Figure 1 seems to be missing?", "questions_for_authors": "Some of the existing works on the marginalization problem (e.g. Cao & Rimell, 2021; Chirkova et al., 2023) tackle the problem using importance sampling, which has the benefit of being unbiased. Is there any way to apply a similar idea in the setting of conditional generation?", "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": "2rJS5fehjF", "reviewer": "Reviewer_9E2G", "summary": "The paper presents algorithms to convert token-level language models to character-level ones, addressing the prompt boundary problem. It introduces the concept of covering and proposes both exact and approximate algorithms. The main findings include that the method can accurately approximate the character-level distribution with a small computation budget. The key algorithmic idea is to find a covering of token strings that form a key technical concept, allowing the selection of members in proportion to their normalized prefix probability. The paper also provides an efficient algorithm for conditional token generation.", "questions": "", "limitations": "", "rating": 3, "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\nMany reviewers suggested that our evaluation methodology, which uses a large beam as a proxy for ground truth character-level probabilities, may have some systematic bias. We will add discussion to the paper about the challenge of designing a faithful evaluation as well as the possible pitfalls in our large-beam evaluation scheme.\n\nThat being said, we agree that our evaluation can be improved. In subsequent revisions of the paper, we will seek to address this in the following ways:\n\n- **Additional baselines and comparisons**:\n  - **Token healing for character-level probabilities**: Thanks to a suggestion from reviewer DnV9, we will add a comparison between our algorithm and an algorithm based on token healing for inferring character-level probabilities.\n\n  - **Perplexity per byte**: Based on the suggestion by reviewer DnV9, we will add a comparison between our method’s byte-level cross-entropy and the byte-normalized cross-entropy of a token-level language model.\n\n  - **Increased beam-width**: We will further increase the beam width of the baseline model, bringing it even closer to the ground truth and reducing any potential bias in the comparison.\n\n- **Evaluation of downstream accuracy on LM reasoning benchmarks**: We agree that some evaluation of the downstream effects of our approach would strengthen the paper.  Therefore, we will investigate the feasibility of adding an evaluation of the downstream accuracy on one or more common LM reasoning benchmarks (e.g., HellaSWAG or GLUE).  However, we do not necessarily expect to see benefits.  It's possible that randomly shifting the prompt boundary to the left would be interesting.  Consider an example from HellaSWAG:\n\n  ```\n  Prompt: \"A man is sitting on a roof. He \"\n  . \"is using wrap to wrap a pair of skis.\",  \n  2. \"is ripping level tiles off.\",  \n  3. \"is holding a rubik's cube.\", \n  4. \"starts pulling up roofing on a roof.\"\n  ```\n  We would randomly shift the prompt left, e.g., move `\"of. He\"` from the end of the prompt to the possible continuations:\n\n  ```\n  Prompt: \"A man is sitting on a ro\"\n  1. \"of. He is using wrap to wrap a pair of skis.\", \n  2. \"of. He is ripping level tiles off.\", \n  3. \"of. He is holding a rubik's cube.\", \n  4. \"of. He starts pulling up roofing on a roof.\"\n  ```\n\nWe note, however, that we do not claim that our method must improve performance on downstream tasks, e.g., math reasoning. The purpose of our approach is to enable a character-level interface to a tokenized LM, which naturally solves the prompt boundary problem.\n\n### Reviewer 9E2G\n\nThank you for your review, particularly the questions!\n\n> Other Comments Or Suggestions: The paper is well-written and clear overall. However, there are a few minor issues. For example, in the section on \"Key Properties of κ,\" the definition of strict-prefix monotonicity could be made more explicit with additional examples. Additionally, the notation in some parts of the paper is quite dense and could be simplified for better readability.\n\nThank you for the suggestions.  We will do some editing for improving readability including examples like this will help us do that.\n\n\n> Questions For Authors:\n\n> 1. How does the proposed method handle cases where the language model's probability mass is not concentrated around a limited set of tokenizations?\n\nThis is an excellent question.  Unfortunately, if mass is not concentrated, then our beam summing estimate will be skewed.  Fortunately, as the method is based on beam search, even if the beam size K is smaller than what is needed to cover the entire distribution, our method can still pick up on the more likely tokenizations.  We will add some discussion about this in the revised paper.\n\n> 2. What are the computational requirements for the beam summing method when dealing with very large beam sizes?\n\nWe provide time and space complexity analyses in section 3.2.  The short answer is that time and space are linear in the beam size K.  The primary bottleneck in using more samples is that we make up to K language model calls at each position of the character string.  \n\n> 3. Could the covering concept be extended to handle more complex tokenization schemes, such as those used in multilingual language models?\n\nThis sounds very interesting.  What are some of the complexities that multi-lingual language models have?  If you could please provide some pointers/citations, we would love to dig into your question.", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence. The authors provide a detailed analysis of the prompt boundary problem and demonstrate how their method resolves it. They also present empirical results on two publicly available language models, GPT2-large and Llama 3.1 8B, showing the accuracy and efficiency of their approach. The experiments include measuring the Jensen-Shannon distance (JSD) between the character-level conditional distributions with different beam sizes and the reference model, as well as the processing speed in characters per second.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense for the problem at hand. The authors address the fundamental tension between token-level models and character-level prompts, which is a significant challenge for users of large language models. The evaluation criteria, including the JSD and processing speed, are appropriate for assessing the quality and efficiency of the proposed algorithms.", "theoretical_claims": "I did not check the correctness of the proofs for theoretical claims in detail, but the provided proofs in the paper seem logically sound and follow standard mathematical reasoning. The proofs for Proposition 1 and Proposition 2 are based on manipulating summations and leveraging the properties of strict-prefix monotonicity, which are key concepts in the paper.", "experimental_designs_or_analyses": "The experimental designs and analyses seem valid. The authors use standard benchmark datasets (wikitext-103-v1) and modern language models (GPT2-large and Llama 3.1 8B) for evaluation. The experiments are designed to measure the accuracy and efficiency of the proposed method, and the results are presented in a clear and understandable manner. The use of beam search with different beam sizes to approximate the covering is a reasonable approach, and the trade-off between error (JSD) and speed (characters/sec) is well-documented.", "relation_to_broader_scientific_literature": "The key contributions of the paper are related to the broader scientific literature in several ways. The work builds upon previous research on tokenization models and their limitations, such as the issues discussed by Cao & Rimell (2021) and Chirkova et al. (2023). The concept of covering is a novel contribution that addresses the prompt boundary problem, which has been highlighted in prior work like Lundberg & Ribeiro (2023). The paper also contributes to the field of computational psycholinguistics by providing a method to compute contextual surprisal for arbitrary character strings, as discussed by Giulianelli et al. (2024). The proposed algorithms and methods are likely to influence future research on language model interfaces and tokenization strategies.", "essential_references_not_discussed": "Since I am not familiar with the relevant literature, I cannot be sure.", "other_strengths_and_weaknesses": "The paper has several strengths. It addresses a fundamental problem in the interface between token-level language models and character-level prompts, which is a significant challenge for users of large language models. The proposed algorithms are novel and provide a principled solution to the prompt boundary problem. The empirical evaluation is thorough and demonstrates the effectiveness of the proposed methods. \n\nHowever, there are also some weaknesses. The paper assumes that the language model's probability mass is concentrated around a limited set of tokenizations, which may not always be the case. Additionally, the beam summing method requires a very large beam size K if the language model does not favor a small number of tokenizations, which could be a limitation in practice.", "other_comments_or_suggestions": "The paper is well-written and clear overall. However, there are a few minor issues. For example, in the section on \"Key Properties of κ,\" the definition of strict-prefix monotonicity could be made more explicit with additional examples. Additionally, the notation in some parts of the paper is quite dense and could be simplified for better readability.", "questions_for_authors": "I have a few important questions for the authors:\n\n    1. How does the proposed method handle cases where the language model's probability mass is not concentrated around a limited set of tokenizations?\n    2. What are the computational requirements for the beam summing method when dealing with very large beam sizes?\n    3. Could the covering concept be extended to handle more complex tokenization schemes, such as those used in multilingual language models?", "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: The paper investigates the problem that language models are sensitive to the specification of the prompt (e.g., if the prompt ends with a space or not). They proceed logically, derive theoretical insights and a practical algorithm that seems to perform well. This meta-reviewer is particularly excited because the paper studies an important problem from an application point of view and provides a solution which is both theoretically and empirically sound.
Decision: Accept (spotlight poster)