Technical Summary: "Is Your LLM Overcharging You? Tokenization, Transparency, and Incentives"

Problem Statement

The paper addresses a fundamental vulnerability in the current "LLM-as-a-Service" pricing model, where users are charged a fixed price per token. The core issue arises from information asymmetry between the provider (agent) and the user (principal). While the provider observes the entire generative process, including intermediate steps and the specific tokenization of the output, the user only sees the final text and pays based on the reported token count.

Because tokenization is not unique—multiple token sequences can represent the same string—a provider has a financial incentive to misreport the tokenization of an output to maximize revenue. For instance, a provider could split a single token representing "Damascus" into four smaller tokens ("Da", "ma", "s", "cus") to charge for four tokens instead of one, without altering the visible text. This constitutes a moral hazard, where the provider maximizes utility at the expense of the user.

The paper investigates whether this misreporting can be detected if providers are required to be transparent (e.g., sharing next-token probabilities) and whether an incentive-compatible pricing mechanism can eliminate this behavior entirely.

Methodology

The authors model the interaction between a user and an LLM provider as a principal-agent problem.

1. Formal Modeling:

   • Utility Function: The provider's utility is defined as the revenue from the reported token sequence minus the energy costs of generation and the reporting policy.
   • Pricing Mechanisms: The study focuses on additive pricing mechanisms, specifically comparing the standard pay-per-token model against a proposed pay-per-character model.
   • Plausibility Constraints: To avoid detection, a misreporting provider must ensure the reported token sequence is "plausible" (e.g., consistent with top-$p$ or top-$k$ sampling distributions) given the string content.

2. Theoretical Analysis:

   • The authors prove that finding the longest plausible tokenization of a string under top-$p$ sampling is NP-Hard. This suggests that optimally maximizing revenue through misreporting without raising suspicion is computationally intractable in the general case.
   • They characterize incentive-compatible pricing mechanisms, proving that a mechanism is incentive-compatible if and only if the price depends linearly on the character count of the output string, not the token count.

3. Algorithmic Proof-of-Concept:

   • Despite the NP-Hardness result, the authors develop an efficient heuristic algorithm (Algorithm 2). This algorithm iteratively splits tokens in the generated output into smaller, plausible tokens to increase the token count.
   • The algorithm checks for plausibility (e.g., verifying if tokens fall within the top-$p$ probability set) and only reports the split sequence if it remains plausible; otherwise, it reports the truthful sequence.
   • The authors analyze the trade-off between the additional revenue gained from overcharging and the computational cost (GPU energy) required to verify plausibility.

4. Empirical Evaluation:

   • Experiments were conducted using LLMs from the Llama, Gemma, and Ministral families.
   • Prompts were sourced from the LMSYS Chatbot Arena platform.
   • The study measured the percentage of overcharged tokens, the fraction of plausible misreports, and the net utility gain for the provider under various parameters (temperature, top-$p$ values, and profit margins).

Key Contributions

1. Incentive Analysis: The paper demonstrates that the pay-per-token mechanism creates a direct financial incentive for providers to misreport tokenizations. Even with transparency requirements, the incentive persists because providers can find some plausible, longer tokenizations that increase revenue.
2. Complexity Result: The authors establish that finding the optimal (longest) plausible tokenization is NP-Hard, implying that a provider cannot easily compute the absolute maximum overcharge without significant computational effort.
3. Heuristic Vulnerability: Crucially, the paper shows that sub-optimal misreporting is computationally cheap and financially profitable. The proposed heuristic algorithm allows providers to significantly overcharge users (e.g., up to 11.2% for specific models and parameters) with a net utility gain that exceeds the cost of verification.
4. Incentive-Compatible Pricing: The paper proves that the only additive pricing mechanism that eliminates the incentive to misreport tokenization is pay-per-character. Under this mechanism, the price is determined solely by the string length, making tokenization irrelevant to the cost.
5. Transition Strategy: The authors propose a method for providers to transition from pay-per-token to pay-per-character while maintaining their average profit margin. This involves setting the price per character ($r_c$) based on the current price per token ($r_o$) and the empirical average ratio of tokens to characters ($tpc$) in the provider's output distribution.

Results

• Overcharging Capability: Using Algorithm 2, unfaithful providers can overcharge users by significant margins. For example, with Llama-3.2-1B-Instruct and $p=0.99$, providers could overcharge by 11.2% of tokens. Even at stricter plausibility thresholds ($p=0.90$), overcharging remained possible (0.28%).
• Profitability: The additional revenue from misreporting consistently surpassed the energy cost of verifying plausibility. For models like Llama-3.2-1B-Instruct, the utility gain exceeded 10.5% for $p=0.99$, regardless of the provider's profit margin.
• Margin Variance: Under the proposed pay-per-character mechanism, a provider's profit margin becomes variable across different outputs (depending on the token-to-character ratio). However, the authors show that by calibrating the character price correctly, the average profit margin remains stable, and the margin remains positive for the vast majority of outputs (e.g., >92% for Llama-3.2-1B-Instruct).
• Language Sensitivity: The study notes that under pay-per-character, languages with higher token-to-character ratios (often minority languages) result in lower provider margins, effectively reducing the cost burden for users of those languages compared to the pay-per-token model.

Significance and Claims

The paper argues that the current pay-per-token pricing mechanism creates a systemic vulnerability where users cannot verify if they are being overcharged, even if providers are transparent about their sampling processes. The authors claim that:

1. Transparency is Insufficient: Merely requiring providers to share next-token probabilities does not prevent overcharging, as efficient heuristics exist to find profitable, plausible misreports.
2. Incentive Compatibility is Necessary: To truly eliminate the incentive for strategic misreporting, the industry must shift to a pay-per-character pricing mechanism. This aligns the cost directly with the value received by the user (the text string) rather than the internal representation (tokens).
3. Feasibility of Transition: The transition to pay-per-character is economically viable for providers, as they can maintain their average profit margins while eliminating the risk of user overcharge.

The authors conclude that without such a paradigm shift, users of LLM-as-a-service remain vulnerable to self-serving providers, drawing parallels to historical market failures in other industries where information asymmetry led to exploitation. They emphasize that while legal and reputational risks exist, strong economic incentives often drive such behavior, necessitating structural pricing solutions.