Technical Summary: Tokenization Multiplicity Leads to Arbitrary Price Variation in LLM-as-a-service

1. Problem Statement

The paper addresses a critical, yet overlooked, issue in the economics of Large Language Models (LLMs) offered as a service (LLM-as-a-service). Currently, providers predominantly utilize a pay-per-token pricing model, where users are charged a fixed price per token generated. The standard assumption is that identical input prompts yielding identical output strings should result in identical costs.

However, the authors demonstrate that this assumption is flawed due to tokenization multiplicity. Even when an LLM generates the exact same output string (character-for-character) from the same input prompt, the underlying sequence of tokens may differ. Since pricing is based on token count rather than character count, these different tokenizations lead to arbitrary price variations for the same output. This phenomenon is particularly prevalent in non-English languages and affects both proprietary and open-weights models.

2. Methodology

Empirical Investigation

The authors conducted extensive empirical studies across three natural language tasks: translation, spell checking, and rephrasing.

• Setup: They constructed 100 input prompts per task using short Wikipedia texts. For translation, they tested English-to-5-target-language pairs; for spell checking and rephrasing, they tested 6 languages.
• Execution: Each prompt was fed to the LLM 100 times with identical parameters but different random seeds to simulate different users requesting the same task.
• Models: The study included proprietary models (GPT-4o-mini, GPT-4.1, GPT-5-mini, Gemini, Claude) and open-weights models (Llama-3.1-8B-Instruct, Qwen2.5-7B-Instruct).
• Measurement: They identified pairs of outputs where the decoded strings were identical but the tokenization lengths differed. They measured the probability of this occurrence and the magnitude of the resulting price variation.

Theoretical Analysis

The paper formally defines canonical tokenization as the unique tokenization a string receives during the LLM's training process (determined by the encoder). The authors prove a key theoretical result regarding non-recovering tokenizers:

• Theorem: For BPE, Unigram, and Wordpiece tokenizers, if a partial token sequence is non-canonical, any extension of that sequence (appending more tokens) will also be non-canonical.
• Implication: To generate a canonical output sequence, the model must generate canonical partial sequences at every step. This property allows for constrained generation strategies.

Proposed Solution: Canonical Generation

To eliminate price variation, the authors introduce canonical generation, a constrained generation method that restricts the LLM to only generate the canonical tokenization of any output string.

• Algorithm: They propose an efficient sampling algorithm based on the Gumbel-Max trick.
  • Instead of explicitly computing a new probability distribution (which would require checking all vocabulary tokens for canonicity), the algorithm samples Gumbel noise for each token.
  • It ranks tokens by their perturbed log-probabilities.
  • It iterates through the ranked tokens and selects the first one that, when appended to the current sequence, results in a canonical sequence.
  • This approach effectively redistributes the probability mass of non-canonical tokens to the remaining canonical tokens without expensive normalization.

3. Key Results

Tokenization Multiplicity

• Prevalence: Tokenization multiplicity was observed across all tested models and tasks. For open-weights models (Llama, Qwen), it occurred regularly across all three tasks. Proprietary models also exhibited the issue, though with varying frequencies.
• Language Dependency: The phenomenon is significantly more prevalent in minority languages (e.g., Turkish, Swahili) compared to English. For example, in translation tasks, up to 7% of prompts for Turkish and Swahili resulted in identical strings with different tokenization lengths.
• Price Variation: When multiplicity occurs, the price difference can be substantial. The authors observed relative price differences of up to 15% for the same output string between the shortest and longest tokenization.
• Long Outputs: In longer texts, tokenization errors tend to propagate; if a word is generated with a non-canonical tokenization, subsequent occurrences of that word often follow the same non-canonical pattern, compounding the price difference.

Canonical Generation Performance

• Theoretical Guarantee: The authors prove that the distribution of token sequences generated via canonical generation is provably closer (in terms of KL-divergence) to the true distribution of sequences seen during training than standard generation.
• Empirical Performance: Experiments on translation, spell checking, rephrasing, and the MGSM (multilingual math) benchmark show that canonical generation is comparable to standard generation in terms of:
  • Quality: Metrics such as translation quality scores, edit distance, and cosine similarity showed negligible differences (often within the margin of error).
  • Runtime: The time per token increased only marginally (e.g., from 0.019s to 0.020s), demonstrating the efficiency of the Gumbel-Max based sampling algorithm.
• Non-Canonicity Rate: Standard generation produced non-canonical outputs in 6% to 29% of cases depending on the model and task, whereas canonical generation reduced this rate to 0% by design.

4. Significance and Claims

The paper claims to provide the first empirical evidence that tokenization multiplicity leads to arbitrary and undesirable price variation in LLM-as-a-service, even when providers are "faithful" (i.e., not intentionally manipulating token counts).

• Economic Impact: The findings challenge the fairness of the pay-per-token model, showing that users can be charged significantly different amounts for identical value (text) due to stochastic variations in tokenization.
• Technical Contribution: The introduction of canonical generation offers a practical solution that eliminates this price variation without sacrificing model performance or significantly increasing latency.
• Theoretical Insight: The proof that BPE, Unigram, and Wordpiece are non-recovering provides a foundational understanding of why non-canonical sequences arise and how they can be prevented via step-by-step constraints.

The authors conclude that while canonical generation slightly restricts the sampling space (potentially leading to marginally lower performance in specific constrained scenarios), it effectively solves the problem of arbitrary pricing while maintaining high-quality output generation.