Auditing Pay-Per-Token in Large Language Models

1. Problem Statement

The paper addresses a critical economic vulnerability in the "LLM-as-a-Service" market, where providers charge users based on a pay-per-token pricing model.

• The Incentive: Due to the asymmetry of information, the provider observes the entire generative process (the specific token sequence generated by the model), while the user only sees the final string output.
• The Threat: Tokenization is not unique; a single string can be represented by multiple valid token sequences of varying lengths. A malicious provider can exploit this by reporting a tokenization with a higher token count than the one actually generated, thereby inflating their revenue at the user's expense (a "moral hazard").
• The Challenge: Detecting this misreporting is difficult because the user cannot verify the internal tokenization without access to the model's internal state or a trusted third party with such access.

2. Methodology

The authors propose a sequential auditing framework based on martingale theory and e-values. The framework assumes a trusted third-party auditor who has access to the model's next-token probability distribution (e.g., via open weights or regulatory mandates).

A. Formalization as a Sequential Hypothesis Test

The problem is framed as testing two hypotheses regarding the provider's reporting policy $\pi$:

• Null Hypothesis ($H_0$): The provider is faithful ($\pi = \pi_0$), reporting the true token sequence.
• Alternative Hypothesis ($H_1$): The provider is unfaithful ($I(\pi) > 0$), where $I(\pi)$ is the misreporting intensity (the expected excess number of tokens reported).

B. Unbiased Estimator of Token Length

To test these hypotheses, the auditor must estimate the expected number of tokens the model would generate for a specific output string $s$.

• Challenge: The standard autoregressive generation process does not guarantee a specific output string $s$.
• Solution: The authors introduce a modified generation process using masked next-token probabilities. This process forces the model to generate token sequences that result in the string $s$.
• Algorithm 1 (EstimateLength): They develop a novel, unbiased Monte Carlo estimator using randomized truncation (inspired by debiasing techniques for SDEs). It samples sequences from the modified process and uses importance weighting to compute an unbiased estimate of the average token length $E[\text{len}(T) | \text{str}(T)=s]$.

C. Sequential Statistical Test (Martingale)

The auditor interacts with the provider sequentially:

1. Query the provider with a prompt $Q$.
2. Receive a reported token sequence $\tilde{T}$ and string $s = \text{str}(\tilde{T})$.
3. Compute the evidence $E_i = \text{len}(\tilde{T}) - \text{EstimateLength}(Q, s)$.
4. Update a martingale process $M_i$:
   $$M_i = M_{i-1} \cdot (1 + \lambda_i \cdot E_i)$$
   where $\lambda_i$ is a weighting parameter.
5. Decision Rule: If $M_i$ exceeds a threshold $1/\alpha$, the auditor rejects $H_0$ and flags the provider as unfaithful.

3. Key Contributions

1. Theoretical Guarantees:
   • False Positive Control: The framework guarantees that the probability of falsely flagging a faithful provider is bounded by $\alpha$ (Theorem 3), utilizing Ville's inequality for martingales.
   • Detection Guarantee: The framework is guaranteed to detect an unfaithful provider with probability 1 in finite time, regardless of the sophistication of their misreporting policy, provided the misreporting intensity $I(\pi) > 0$ (Theorem 4).
2. Novel Estimator: The development of an efficient, unbiased estimator for the average token length of a specific string, which is a standalone contribution useful for other probabilistic analyses of LLMs.
3. Robustness: The method works for any non-deterministic reporting policy and does not require the auditor to know the specific strategy of the provider, only that the provider is not faithful.

4. Experimental Results

The authors validated the framework using models from the Llama, Gemma, and Ministral families and prompts from the LMSYS Chatbot Arena dataset.

• Faithful Providers: In 150 trials per model, the test process $M$ remained close to its initial value (1) and never crossed the threshold $1/\alpha$ (where $\alpha=0.05$), confirming the low false positive rate.
• Unfaithful Providers: The framework successfully detected misreporting under two simulated policies (Random splitting and Heuristic splitting):
  • Speed: An unfaithful provider was detected after observing fewer than ~70 reported outputs.
  • Intensity Correlation: Detection time decreased rapidly as the misreporting intensity ($I(\pi)$) increased.
  • Robustness: The framework remained effective even when the auditor used a non-quantized model to estimate probabilities while the provider used a quantized version (approximate model access).

5. Significance and Impact

• Market Integrity: This work provides the first rigorous statistical tool to audit the "pay-per-token" pricing model, addressing a fundamental misalignment of incentives between providers and users.
• Regulatory Relevance: The framework aligns with emerging regulations like the EU AI Act (Article 74), which grants auditors access to source code for high-risk AI systems. It offers a concrete mechanism for "market surveillance authorities" to verify billing transparency.
• Trust in AI Services: By enabling third-party verification, the framework can restore trust in LLM-as-a-Service markets, discouraging providers from engaging in "token inflation" strategies.
• Future Directions: The authors suggest extending this to proprietary models via regulatory access and developing benchmarks for various adversarial tokenization policies.

In summary, the paper bridges economic theory (moral hazard), statistical learning (martingales and e-values), and systems engineering to create a robust, provably correct auditing tool for the emerging LLM economy.