From Language Models over Tokens to Language Models over Characters
Tim Vieira Ben LeBrunMario GiulianelliJuan Luis GastaldiBrian DuSellJohn Terilla, Timothy J. O’DonnellRyan Cotterell ETH ZürichMila -- Quebec Artificial Intelligence InstituteMcGill UniversityCity University of New YorkCanada CIFAR AI Chair, Mila · 2024
Read From Language Models over Tokens to Language Models over Characters by Tim Vieira Ben LeBrunMario GiulianelliJuan Luis GastaldiBrian DuSellJohn Terilla, Timothy J. O’DonnellRyan Cotterell ETH ZürichMila -- Quebec Artificial Intelligence InstituteMcGill UniversityCity University of New YorkCanada CIFAR AI Chair, Mila (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-03719.txt.
Introduction
Language models read and write in tokens, chunks of text, rather than single letters, and that mismatch causes real headaches for builders. Tim Vieira and co-authors present methods in a 2024 paper for turning a token-level model into a true character-level one. They give both an exact conversion and a faster approximate one, then test speed and accuracy on four public models.
Even with a small computing budget, the approximate method matched the true character-level behavior closely and ran at usable speed. It also improved how tightly the model compressed text. The authors say character-level models would make prompts behave more predictably for users.
Catalog record
| CREATOR | Tim Vieira Ben LeBrunMario GiulianelliJuan Luis GastaldiBrian DuSellJohn Terilla, Timothy J. O’DonnellRyan Cotterell ETH ZürichMila -- Quebec Artificial Intelligence InstituteMcGill UniversityCity University of New YorkCanada CIFAR AI Chair, Mila |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 105 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-03719
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
From Language Models over Tokens to Language Models over Characters Tim Vieira Ben LeBrunMario GiulianelliJuan Luis GastaldiBrian DuSellJohn Terilla, Timothy J. O’DonnellRyan Cotterell ETH ZürichMila -- Quebec Artificial Intelligence InstituteMcGill UniversityCity University of New YorkCanada CIFAR AI Chair, Mila 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 analyses are very sensitive to the specification of the prompt (e.g., if 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. We find that—even with a small computation budget—our method is able to accurately approximate the character-level distribution (less than 0.00021 excess bits / character) at reasonably fast speeds (46.3 characters / second) on the Llama 3.1 8B language model. https://github.com/rycolab/token-to-char-lm 1 Introduction For various technical reasons, modern language models are engineered as probability distributions over strings of tokens rather than strings of characters . However, this leads to a fundamental tension between the users of large language models and the engineers who build them. Specifically, token-level models are rife with unintuitive behaviors that—without a technical fix—baffle users. As an illustrative example of a common user complaint, we exhibit the prompt boundary problem (see below). This paper provides a principled solution to the prompt boundary problem as well as other oddities that make interfacing with token-level language models with character-level prompts hard for users. Tokenized language models: A brief overview. Let {\color[rgb]{0.3828,0.4492,0.0742}\Sigma} be an alphabet of characters, and let {\color[rgb]{0.3828,0.4492,0.0742}{\color[rgb]{0.3828,0.4492,0.0742}\Sigma}^{*}} denote the set of all strings that can be built from it. Suppose there is a true distribution p_{{\color[rgb]{0.3828,0.4492,0.0742}\Sigma}}^{*} over {\color[rgb]{0.3828,0.4492,0.0742}{\color[rgb]{0.3828,0.4492,0.0742}\Sigma}^{*}} that we seek to model. We observe a training corpus of character strings: {\color[rgb]{0.3828,0.4492,0.0742}\boldsymbol{\sigma}}^{(1)},\ldots,{\color[rgb]{0.3828,0.4492,0.0742}\boldsymbol{\sigma}}^{(M)}\mathrel{\overset{{\text{i.i.d.}}}{\sim}}p_{{\color[rgb]{0.3828,0.4492,0.0742}\Sigma}}^{*} . However, rather than estimating a language model that approximates p_{{\color[rgb]{0.3828,0.4492,0.0742}\Sigma}}^{*} directly, we employ a (possibly stochastic) 1 1 1 The tokenizer {\color[rgb]{0.5508,0.0391,0.3477}\tau} is often deterministic (e.g., byte-pair encoding ( sennrich-etal-2016-neural ) ), but stochastic tokenizers (e.g., UnigramLM ( kudo-2018-subword ) ) are also of interest to the community. tokenizer {\color[rgb]{0.5508,0.0391,0.3477}\tau} that transforms the training corpus into a corpus of token strings. {\color[rgb]{0.5508,0.0391,0.3477}\boldsymbol{\delta}}^{(1)}\sim{\color[rgb]{0.5508,0.0391,0.3477}\tau}(\cdot\mid{\color[rgb]{0.3828,0.4492,0.0742}\boldsymbol{\sigma}}^{(1)}),\ldots,{\color[rgb]{0.5508,0.0391,0.3477}\boldsymbol{\delta}}^{(M)}\sim{\color[rgb]{0.5508,0.0391,0.3477}\tau}(\cdot\mid{\color[rgb]{0.3828,0.4492,0.0742}\boldsymbol{\sigma}}^{(M)}) . Next, we estimate a token-level language model to fit the strings {\color[rgb]{0.5508,0.0391,0.3477}\boldsymbol{\delta}}^{(1)},\ldots,{\color[rgb]{0.5508,0.0391,0.3477}\boldsymbol{\delta}}^{(M)} . Lastly, we use p_{{\color[rgb]{0.5508,0.0391,0.3477}\Delta}} to generate character strings by means of the following generative process: (i) sample {\color[rgb]{0.5508,0.0391,0.3477}\boldsymbol{\delta}}\sim p_{{\color[rgb]{0.5508,0.0391,0.3477}\Delta}} and (ii) return {\color[rgb]{0.3828,0.4492,0.0742}\boldsymbol{\sigma}}={\color[rgb]{0.3828,0.4492,0.0742}\kappa}({\color[rgb]{0.5508,0.0391,0.3477}\boldsymbol{\delta}}) where {\color[rgb]{0.3828,0.4492,0.0742}\kappa} is a decoding function. Let p_{{\color[rgb]{0.3828,0.4492,0.0742}\Sigma}} denote the resulting distribution of this process. Practically, we hope that the choice of {\color[rgb]{0.5508,0.0391,0.3477}\tau} and {\color[rgb]{0.3828,0.4492,0.0742}\kappa} should aid in our ability to estimate p_{{\color[rgb]{0.3828,0.4492,0.0742}\Sigma}}^{*} in the sense that p_{{\color[rgb]{0.3828,0.4492,0.0742}\Sigma}}^{*}\approx p_{{\color[rgb]{0.3828,0.4492,0.0742}\Sigma}} . 2 2 2 gastaldi2024foundations give a general characterization of which tokenizers allow consistent statistical estimation. Commonly used tokenizers in the realm of LLMs use tokenizers {\color[rgb]{0.5508,0.0391,0.3477}\tau} that break long strings into chunks. Intuitively, generating chunks instead of individual characters helps because it effectively shortens strings without obfuscating them using a complicated encoding. The prompt boundary problem. Consider the case of GPT2 ( radford2019language ) , which was trained over token strings created from byte-pair encoding (BPE; sennrich-etal-2016-neural ; gage1994bpe ). Suppose we wish to generate continuations of the prompt: "In␣the␣kingdom␣of␣the␣blind,␣the Unfortunately, the language model p_{{\color[rgb]{0.5508,0.0391,0.3477}\Delta}} does not accept a character string; thus, it is common to encode it as a token string with an encoding function {\color[rgb]{0.5508,0.0391,0.3477}\tau}_{{\color[rgb]{0.5508,0.0391,0.3477}\text{BPE}}} : 3 3 3 In practice, {\color[rgb]{0.5508,0.0391,0.3477}\tau}_{{\color[rgb]{0.5508,0.0391,0.3477}\text{BPE}}} outputs an integer sequence; however, we provide the substring gloss for readability. , 4 4 4 Here we write {\color[rgb]{0.5508,0.0391,0.3477}\boldsymbol{\delta}}={\color[rgb]{0.5508,0.0391,0.3477}\tau}({\color[rgb]{0.3828,0.4492,0.0742}\sigma}) instead of {\color[rgb]{0.5508,0.0391,0.3477}\boldsymbol{\delta}}\sim{\color[rgb]{0.5508,0.0391,0.3477}\tau}(\cdot\mid{\color[rgb]{0.3828,0.4492,0.0742}\boldsymbol{\sigma}}) since {\color[rgb]{0.5508,0.0391,0.3477}\tau} is deterministic (i.e., a function). {\color[rgb]{0.5508,0.0391,0.3477}\tau}_{{\color[rgb]{0.5508,0.0391,0.3477}\text{BPE}}}({\color[rgb]{0.3828,0.4492,0.0742}\texttt{"In{\textvisiblespace}the{\textvisiblespace}kingdom{\textvisiblespace}of{\textvisiblespace}the{\textvisiblespace}blind,{\textvisiblespace}the}})=[\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{"}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{1}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{In}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{818}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}the}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{262}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}kingdom}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{13239}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}of}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{286}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}the}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{262}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}blind}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{7770}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{,}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{11}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}the}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{262}}}}}$}}] If we complete the prompt by taking the most likely next token (also known as greedy completion ), we generate the following continuation: [\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}one}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{530}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{-}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{12}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{eyed}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{18834}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}man}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{582}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}is}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{318}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}king}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{5822}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{."}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{526}}}}}$}}] Now that we have our generated output, we can apply the decoding function {\color[rgb]{0.3828,0.4492,0.0742}\kappa} that maps token strings to character strings as part of the tokenization protocol: {\color[rgb]{0.3828,0.4492,0.0742}\kappa}_{{\color[rgb]{0.3828,0.4492,0.0742}\text{BPE}}}([\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{"}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{1}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{In}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{818}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}the}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{262}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}kingdom}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{13239}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}of}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{286}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}the}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{262}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}blind}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{7770}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{,}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{11}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}the}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{262}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}one}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{530}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{-}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{12}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{eyed}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{18834}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}man}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{582}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}is}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{318}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}king}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{5822}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{."}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{526}}}}}$}}]) ={\color[rgb]{0.3828,0.4492,0.0742}\texttt{"}}{\color[rgb]{0.3828,0.4492,0.0742}\texttt{In}}{\color[rgb]{0.3828,0.4492,0.0742}\texttt{{\textvisiblespace}the}}{\color[rgb]{0.3828,0.4492,0.0742}\texttt{{\textvisiblespace}kingdom}}{\color[rgb]{0.3828,0.4492,0.0742}\texttt{{\textvisiblespace}of}}{\color[rgb]{0.3828,0.4492,0.0742}\texttt{{\textvisiblespace}the}}{\color[rgb]{0.3828,0.4492,0.0742}\texttt{{\textvisiblespace}blind}}{\color[rgb]{0.3828,0.4492,0.0742}\texttt{,}}{\color[rgb]{0.3828,0.4492,0.0742}\texttt{{\textvisiblespace}the}}{\color[rgb]{0.3828,0.4492,0.0742}\texttt{{\textvisiblespace}one}}{\color[rgb]{0.3828,0.4492,0.0742}\texttt{-}}{\color[rgb]{0.3828,0.4492,0.0742}\texttt{eyed}}{\color[rgb]{0.3828,0.4492,0.0742}\texttt{{\textvisiblespace}man}}{\color[rgb]{0.3828,0.4492,0.0742}\texttt{{\textvisiblespace}is}}{\color[rgb]{0.3828,0.4492,0.0742}\texttt{{\textvisiblespace}king}}{\color[rgb]{0.3828,0.4492,0.0742}\texttt{."}} This is a good completion, as the string is a well-known proverb. However, if we tweak the prompt ever so slightly by inserting a trailing whitespace: {\color[rgb]{0.5508,0.0391,0.3477}\tau}_{{\color[rgb]{0.5508,0.0391,0.3477}\text{BPE}}}({\color[rgb]{0.3828,0.4492,0.0742}\texttt{"In{\textvisiblespace}the{\textvisiblespace}kingdom{\textvisiblespace}of{\textvisiblespace}the{\textvisiblespace}blind,{\textvisiblespace}the{\textvisiblespace}}})=[\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{"}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{1}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{In}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{818}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}the}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{262}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}kingdom}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{13239}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}of}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{286}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}the}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{262}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}blind}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{7770}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{,}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{11}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}the}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{262}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{220}}}}}$}}] greedy completion returns [\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{ills}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{2171}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}of}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{286}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}the}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{262}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}world}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{995}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}are}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{389}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}seen}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{1775}}}}}$}},\cdots] This happens because the conditional probability ( {\overrightarrow{p_{{\color[rgb]{0.5508,0.0391,0.3477}\Delta}}}} ) of generating the characters we want becomes extremely unlikely: Before: 0.98 ={\overrightarrow{p_{{\color[rgb]{0.5508,0.0391,0.3477}\Delta}}}}(\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}one}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{530}}}}}$}}\,\mid{\color[rgb]{0.5508,0.0391,0.3477}\tau}_{{\color[rgb]{0.5508,0.0391,0.3477}\text{BPE}}}({\color[rgb]{0.3828,0.4492,0.0742}\texttt{"In{\textvisiblespace}the{\textvisiblespace}kingdom{\textvisiblespace}of{\textvisiblespace}the{\textvisiblespace}blind,{\textvisiblespace}the}})) After: 0.0000005 ={\overrightarrow{p_{{\color[rgb]{0.5508,0.0391,0.3477}\Delta}}}}(\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{one}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{505}}}}}$}}\,\mid{\color[rgb]{0.5508,0.0391,0.3477}\tau}_{{\color[rgb]{0.5508,0.0391,0.3477}\text{BPE}}}({\color[rgb]{0.3828,0.4492,0.0742}\texttt{"In{\textvisiblespace}the{\textvisiblespace}kingdom{\textvisiblespace}of{\textvisiblespace}the{\textvisiblespace}blind,{\textvisiblespace}the{\textvisiblespace}}})) Hence, the trailing white space undesirably impacts the output, which no longer corresponds to the proverb. This behavior is odd, as we would expect the most likely continuation (shown above) to be invariant to whether or not the whitespace character ( ␣ ) is in the prompt or the continuation. More broadly, the prompt boundary problem may be generally characterized as an unwanted sensitivity to the characters at the boundary and the continuation. Our perspective is that the prompt boundary problem arises from incorrectly conditioning the token-level language model on a string of characters by using {\color[rgb]{0.5508,0.0391,0.3477}\tau}({\color[rgb]{0.3828,0.4492,0.0742}\boldsymbol{\sigma}}) rather than finding token strings that best match the prompt {\color[rgb]{0.3828,0.4492,0.0742}\boldsymbol{\sigma}} . \hookrightarrow The token healing heuristic: token-healing present token healing as a heuristic that mitigates the prompt boundary problem. Token healing 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 to the constraint that it starts with the unmatched substring at the end of the prompt. (4) Continue generating as usual. Now, we can see how token healing patches the running example: {\color[rgb]{0.5508,0.0391,0.3477}\tau}_{{\color[rgb]{0.5508,0.0391,0.3477}\text{BPE}}}({\color[rgb]{0.3828,0.4492,0.0742}\texttt{"In{\textvisiblespace}the{\textvisiblespace}kingdom{\textvisiblespace}of{\textvisiblespace}the{\textvisiblespace}blind{\textvisiblespace}}})=[\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{"}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{1}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{In}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{818}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}the}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{262}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}kingdom}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{13239}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}of}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{286}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}the}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{262}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}blind}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{7770}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{,}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{11}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}the}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{262}}}}}$}},\cancel{\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{220}}}}}$}}}] The most probable next token starting with ␣ is \stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}one}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{530}}}}} . From here, generating the remaining tokens recovers the desired output because it matches the prompt before we added the whitespace. Unfortunately, backing up one token is insufficient for the general case, as the following example will illustrate. Consider generating from GPT2 using the prompt Hello,␣worl : {\color[rgb]{0.5508,0.0391,0.3477}\tau}_{{\color[rgb]{0.5508,0.0391,0.3477}\text{BPE}}}({\color[rgb]{0.3828,0.4492,0.0742}\texttt{Hello,{\textvisiblespace}worl}})=[\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{Hello}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{15496}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{,}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{11}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}wor}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{476}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{l}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{75}}}}}$}}] The most likely next character ought to be d as Hello,␣world is a common expression (popularized in educational material). However, the most likely token is Hello,␣worlwide , an apparent misspelling of worldwide . 5 5 5 The misspelling is a testament to the extent to which the tokenized prompt is out-of-distribution. Unfortunately, token healing’s strategy of backing up by a single token cannot salvage the poor tokenization as \stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{l}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{75}}}}} is still the most common next token that is consistent with the string l . Thus, after generating \stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{l}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{75}}}}} , we are back where we started, generating [\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{Hello}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{15496}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{,}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{11}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{{\textvisiblespace}wor}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{476}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{l}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{75}}}}}$}},\mbox{{$\stackrel{{\scriptstyle\raisebox{-6.02777pt}{{\color[rgb]{0.5508,0.0391,0.3477}{wide}}}}}{{\raisebox{-4.30554pt}{{\color[rgb]{0.5,0.5,0.5}{4421}}}}}$}}] . \hookrightarrow Getting it right: A simple “probability 101” expression tells us the correct solution to the prompt boundary problem. Consider a {\color[rgb]{0.5508,0.0391,0.3477}{\color[rgb]{0.5508,0.0391,0.3477}\Delta}^{*}} -valued random variable {\color[rgb]{0.5508,0.0391,0.3477}Y} , distributed according to p_{{\color[rgb]{0.5508,0.0391,0.3477}\Delta}} . Then, the correct way to sample from p_{{\color[rgb]{0.5508,0.0391,0.3477}\Delta}} conditioned on a character string {\color[rgb]{0.3828,0.4492,0.0742}\boldsymbol{\sigma}} is according to p_{{\color[rgb]{0.5508,0.0391,0.3477}\Delta}\mid{\color[rgb]{0.3828,0.4492,0.0742}\Sigma}}({\color[rgb]{0.5508,0.0391,0.3477}\boldsymbol{\delta}}\mid{\color[rgb]{0.3828,0.4492,0.0742}\boldsymbol{\sigma}})\mathrel{\overset{\raisebox{-0.75346pt}{{def}}}{=}}\mathop{\mathbb{P}}_{\begin{subarray}{c}{\color[rgb]{0.5508,0.0391,0.3477}Y}\sim p_{{\color[rgb]{0.5508,0.0391,0.3477}\Delta}}\end{subarray}}\left[{\color[rgb]{0.5508,0.0391,0.3477}Y}\!=\!{\color[rgb]{0.5508,0.0391,0.3477}\boldsymbol{\delta}}\,\middle|\,{\color[rgb]{0.3828,0.4492,0.0742}\kappa}({\color[rgb]{0.5508,0.0391,0.3477}Y})\succeq{\color[rgb]{0.3828,0.4492,0.0742}\boldsymbol{\sigma}}\right] (1) where we have conditioned on the event that the decoded string {\color[rgb]{0.3828,0.4492,0.0742}\kappa}({\color[rgb]{0.5508,0.0391,0.3477}Y}) has {\color[rgb]{0.3828,0.4492,0.0742}\boldsymbol{\sigma}} as a prefix (i.e., {\color[rgb]{0.3828,0.4492,0.0742}\kappa}({\color[rgb]{0.5508,0.0391,0.3477}Y})\succeq{\color[rgb]{0.3828,0.4492,0.0742}\boldsymbol{\sigma}} ). While innovative with respect to the literature, the expression \mathop{\mathbb{P}}_{\begin{subarray}{c}{\color[rgb]{0.5508,0.0391,0.3477}Y}\sim p_{{\color[rgb]{0.5508,0.0391,0.3477}\Delta}}\end{subarray}}\left[{\color[rgb]{0.5508,0.0391,0.3477}Y}\!=\!{\color[rgb]{0.5508,0.0391,0.3477}\boldsymbol{\delta}}\,\middle|\,{\color[rgb]{0.3828,0.4492,0.0742}\kappa}({\color[rgb]{0.5508,0.0391,0.3477}Y})\succeq{\color[rgb]{0.3828,0.4492,0.0742}\boldsymbol{\sigma}}\right] conveys the probability we are interested in precisely and concisely. For the more procedurally minded, this corresponds to the following generation process: 6 6 6 We adopt the common notational convention