Canonical Autoregressive Generation
Ivi Chatzi, Nina Corvelo Benz, Stratis Tsirtsis, Manuel Gomez-Rodriguez · 2025
Read Canonical Autoregressive Generation by Ivi Chatzi, Nina Corvelo Benz, Stratis Tsirtsis, Manuel Gomez-Rodriguez (2025) 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-2506-06446.txt.
Introduction
Ivi Chatzi, Nina Corvelo Benz, Stratis Tsirtsis, and Manuel Gomez-Rodriguez wrote a 2025 paper exposing a pricing quirk in pay per token language model services. Providers charge a fixed price per token, so the same answer should cost every user the same. The authors show it often does not.
The catch is tokenization: models can split the same output string into tokens in several ways, and longer splits cost more. This happens often for non English outputs, in both commercial and open models. Their fix is canonical generation, which restricts models to the single tokenization used in training. A sampling algorithm built on a classic trick makes that restriction efficient. Tests across language tasks show the method works, restoring one string, one price.
Catalog record
| CREATOR | Ivi Chatzi, Nina Corvelo Benz, Stratis Tsirtsis, Manuel Gomez-Rodriguez |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 50 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-06446
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Canonical Autoregressive Generation Ivi Chatzi, Nina Corvelo Benz, Stratis Tsirtsis, Manuel Gomez-Rodriguez Abstract State of the art large language models are trained using large amounts of tokens derived from raw text using what is called a tokenizer. Crucially, the tokenizer determines the (token) vocabulary a model will use during inference as well as, in principle, the (token) language. This is because, while the token vocabulary may allow for different tokenizations of a string, the tokenizer always maps the string to only one of these tokenizations—the canonical tokenization. However, multiple lines of empirical evidence suggest that large language models do not always generate canonical token sequences, and this comes with several negative consequences. In this work, we first show that, to generate a canonical token sequence, a model needs to generate (partial) canonical token sequences at each step of the autoregressive generation process underpinning its functioning. Building upon this theoretical result, we introduce canonical sampling, a simple and efficient sampling method that precludes a given model from generating non-canonical token sequences. Further, we also show that, in comparison with standard sampling, the distribution of token sequences generated using canonical sampling is provably closer to the true distribution of token sequences used during training. 1 Introduction One of the most distinctive characteristics of large language models (LLMs) is that they are trained using large amounts of text data from diverse sources, including websites, books, scientific articles and code repositories [ 1 ] . During the training process, a tokenizer breaks down the text into sequences of tokens, which are the units that make up sentences and paragraphs, and the LLM learns to predict the next token in a sequence based on the preceding tokens. Importantly, since tokenizers typically utilize a deterministic, rule-based mapping from text to token sequences [ 2 , 3 , 4 , 5 ] , each unique string is always mapped into one tokenization referred to as the canonical tokenization [ 6 ] . Consequently, one may conclude that, at the end of the training process, LLMs will have learned to generate exclusively canonical token sequences. However, there is empirical evidence that this conclusion does not hold—LLMs do generate both canonical and non-canonical token sequences [ 7 , 8 , 6 , 9 , 10 , 11 ] . In this work, we argue that the generation of non-canonical token sequences is unlikely to bring performance benefits, and it does actually have negative consequences. First, it does not increase the expressiveness of a LLM since any non-canonical token sequence can be mapped to a canonical token sequence while preserving its string-level representation. However, they can be exploited to circumvent safety guidelines because they are out-of-distribution samples [ 12 ] . Second, it can lead to a multiplicity of (plausible) tokenizations of an output string, and this creates a financial incentive for an LLM provider to strategize and misreport the (number of) tokens a model used to generate the output [ 11 ] . Third, in the context of LLM evaluation, it becomes (computationally) hard to compute the perplexity of a given string [ 7 , 8 , 6 ] . Motivated by the above observations, we develop a simple and efficient sampling method that precludes an LLM from generating non-canonical token sequences. Our method is based on the following theoretical result, which may be of independent interest: to generate a canonical token sequence, a model needs to generate (partial) canonical token sequences at each step of the autoregressive generation process underpinning its functioning. More specifically, building upon this result, our method utilizes the Gumbel-Max trick to efficiently sample only from the subset of tokens that can lead to (partial) canonical token sequences at each step of the generation. Importantly, we are able to show that, in comparison with standard sampling, the distribution of token sequences generated by canonical sampling is provably closer to the true distribution of token sequences used during training. Related work. The study of tokenization has a rich history in natural language processing [ 13 , 14 ] . More recently, in the context of LLMs, there has been a renewed interest in formalizing tokenization and analyzing its properties [ 15 , 16 , 17 ] , with the Byte-Pair Encoding (BPE) tokenization algorithm in particular receiving increased attention [ 18 , 19 , 20 ] . The impact of tokenization on LLMs has also been studied empirically [ 21 , 22 ] in generation tasks involving foreign languages [ 23 ] , translation [ 24 ] , arithmetic [ 25 ] , mental health [ 26 ] , and privacy [ 27 , 28 ] , among others. Moreover, there have also been efforts to design token-free LLMs that operate at the character or byte level [ 29 , 30 , 31 , 32 , 33 ] , as well as stochastic tokenizers [ 4 , 34 ] . However, none of the above works has paid attention to the existence and significance of non-canonical tokenizations. Only very recently, there has been a paucity of work studying the impact of non-canonical tokenizations on text perplexity calculations [ 7 , 8 , 6 , 9 , 10 ] , safety guidelines [ 12 ] , and financial incentives of LLM providers [ 11 ] . However, none of the above works has studied how to prevent the generation of non-canonical token sequences, which is the focus of our work. 2 Preliminaries In this section, we first define and formally characterize (deterministic) tokenizers and canonical tokenizations. Then, we briefly review the popular Byte-Pair Encoding (BPE) tokenization algorithm [ 2 , 3 ] . Finally, we conclude with a description of the aspects of LLM training and generation that are relevant for our work. Tokenizers and canonical tokenizations. Tokenizers are tools that operate on sequences of characters ( i.e. , strings) and sequences of tokens, and can transform one type into the other. Formally, let \Sigma be a finite set of characters and \Sigma^{*} be the set of all finite strings that can be created using the characters in \Sigma . Similarly, let V be a finite set of tokens, which we will refer to as the vocabulary, and V^{*} be the set of all finite token sequences that can be created using the tokens in V . Then, a tokenizer {\mathcal{T}} is characterized by a tuple {\mathcal{T}}\coloneqq(\Sigma,V,\texttt{enc},\texttt{dec}) , where \texttt{enc}:\Sigma^{*}\rightarrow V^{*} is an encoder, which transforms strings to token sequences, and \texttt{dec}:V^{*}\rightarrow\Sigma^{*} is a decoder, which transforms token sequences to strings. Let \bm{\sigma} be a string and \mathbf{s}\in V^{*} be a token sequence such that \texttt{dec}(\mathbf{s})=\bm{\sigma} , then, we will say that \mathbf{s} is a (valid) tokenization of the string \bm{\sigma} . Here, note that there may be multiple tokenizations of a string \bm{\sigma} , that is, there may exist \mathbf{s},\mathbf{s}^{\prime}\in V^{*} such that \mathbf{s}\neq\mathbf{s}^{\prime} and \texttt{dec}(\mathbf{s})=\texttt{dec}(\mathbf{s}^{\prime})=\bm{\sigma} . However, given a string \bm{\sigma} , the encoder deterministically picks a single tokenization \texttt{enc}(\bm{\sigma}) among all tokenizations of \bm{\sigma} , which is often called the canonical tokenization [ 6 ] . The BPE tokenization algorithm. There exist many tokenization algorithms to construct the set of characters \Sigma , the set of tokens V , the encoder enc , and