# Tokenization Multiplicity Leads to Arbitrary Price Variation in LLM-as-a-service

arXiv: https://arxiv.org/abs/2506.06446 · HTML: https://mlsanity.com/paper/2506.06446/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 50 of its 66 references that are in the map.
- First posted on arXiv 6 Jun 2025.

## Builds on (most cited first, 30 of 50)

- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates](https://mlsanity.com/paper/1804.10959/) (2018)
- [Efficient Large-Scale Language Model Training on GPU Clusters Using Megatron-LM](https://mlsanity.com/paper/2104.04473/) (2021)
- [Language Models are Multilingual Chain-of-Thought Reasoners](https://mlsanity.com/paper/2210.03057/) (2022)
- [How Good is Your Tokenizer? On the Monolingual Performance of Multilingual Language Models](https://mlsanity.com/paper/2012.15613/) (2020)
- [xCOMET: Transparent Machine Translation Evaluation through Fine-grained Error Detection](https://mlsanity.com/paper/2310.10482/) (2023)
- [Black-Box Tuning for Language-Model-as-a-Service](https://mlsanity.com/paper/2201.03514/) (2022)
- [Multilingual Jailbreak Challenges in Large Language Models](https://mlsanity.com/paper/2310.06474/) (2023)
- [Language Model Tokenizers Introduce Unfairness Between Languages](https://mlsanity.com/paper/2305.15425/) (2023)
- [BPE-Dropout: Simple and Effective Subword Regularization](https://mlsanity.com/paper/1910.13267/) (2019)
- [Do All Languages Cost the Same? Tokenization in the Era of Commercial Language Models](https://mlsanity.com/paper/2305.13707/) (2023)
- [From Words to Watts: Benchmarking the Energy Costs of Large Language Model Inference](https://mlsanity.com/paper/2310.03003/) (2023)
- [A* Sampling](https://mlsanity.com/paper/1411.0030/) (2014)
- [Tokenization counts: the impact of tokenization on arithmetic in frontier LLMs](https://mlsanity.com/paper/2402.14903/) (2024)
- [MegaScale: Scaling Large Language Model Training to More Than 10,000 GPUs](https://mlsanity.com/paper/2402.15627/) (2024)
- [Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation](https://mlsanity.com/paper/2403.06988/) (2024)
- [The Language Barrier: Dissecting Safety Challenges of LLMs in Multilingual Contexts](https://mlsanity.com/paper/2401.13136/) (2024)
- [Fast WordPiece Tokenization](https://mlsanity.com/paper/2012.15524/) (2020)
- [A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learning](https://mlsanity.com/paper/2110.01515/) (2021)
- [Energy Considerations of Large Language Model Inference and Efficiency Optimizations](https://mlsanity.com/paper/2504.17674/) (2025)
- [Are You Getting What You Pay For? Auditing Model Substitution in LLM APIs](https://mlsanity.com/paper/2504.04715/) (2025)
- [A Formal Perspective on Byte-Pair Encoding](https://mlsanity.com/paper/2306.16837/) (2023)
- [From Language Models over Tokens to Language Models over Characters](https://mlsanity.com/paper/2412.03719/) (2024)
- [You should evaluate your language model on marginal likelihood over tokenisations](https://mlsanity.com/paper/2109.02550/) (2021)
- [Toward a Theory of Tokenization in LLMs](https://mlsanity.com/paper/2404.08335/) (2024)
- [How BPE Affects Memorization in Transformers](https://mlsanity.com/paper/2110.02782/) (2021)
- [How Much Does Tokenization Affect Neural Machine Translation?](https://mlsanity.com/paper/1812.08621/) (2018)
- [Task-Adaptive Tokenization: Enhancing Long-Form Text Generation Efficacy in Mental Health and Beyond](https://mlsanity.com/paper/2310.05317/) (2023)

## Abstract (arXiv)

Providers of LLM-as-a-service have predominantly adopted a simple pricing model: users pay a fixed price per token. Consequently, one may think that the price two different users would pay for the same output string under the same input prompt is the same. In our work, we show that, surprisingly, this is not (always) true. We find empirical evidence that, particularly for non-english outputs, both proprietary and open-weights LLMs often generate the same (output) string with multiple different tokenizations, even under the same input prompt, and this in turn leads to arbitrary price variation. To address the problem of tokenization multiplicity, we introduce canonical generation, a type of constrained generation that restricts LLMs to only generate canonical tokenizations -- the unique tokenization in which each string is tokenized during the training process of an LLM. Further, we introduce an efficient sampling algorithm for canonical generation based on the Gumbel-Max trick. Experiments on a variety of natural language tasks demonstrate that our sampling algorithm for canonical generation is comparable to standard sampling in terms of performance and runtime, and it solves the problem of tokenization multiplicity.