Is Your LLM Overcharging You? Tokenization, Transparency, and Incentives

Summary

The paper studies the economic incentives that pay-per-token pricing creates in LLM-as-a-service markets. Framing the interaction as a principal-agent problem — the provider observes the full generative process, the user sees only a reported token sequence — the authors argue that providers have a direct financial incentive to report longer-than-necessary tokenizations of the same output string. The core conceptual move is to formalize this moral hazard and to ask two questions in tandem: whether a self-serving provider can misreport while remaining "plausible" under a next-token-probability transparency requirement, and what pricing mechanism eliminates the incentive altogether. The authors prove that finding the longest plausible tokenization under top-$p$ sampling is NP-hard via a reduction from Hamiltonian path, and extend the hardness to top-$k$ and probability-threshold plausibility. They then show constructively that a simple index-based greedy heuristic (Algorithm 1) already lets a transparent provider overcharge non-trivially, and — using the empirical observation that verification cost is roughly constant in sequence length — that the resulting utility gain remains positive over a wide margin range. On the mechanism side, they characterize additive incentive-compatible pricing as necessarily linear in character counts (Theorem 4.3), motivating a pay-per-character rule and a price $r_c = r_o \cdot \mathrm{tpc}$ that preserves the provider's average pay-per-token margin. The framing is timely and the mechanism-design half is a genuinely useful contribution. Execution evidence strengthens the central story: the energy table, the utility-gain mechanism, the flatness of verification cost, and the pay-per-character margin results all reproduce. However, the marquee overcharge percentages ($11.2\%/1.8\%/0.28\%$) did not reproduce from the released code at scale, and the effect is concentrated at temperature $>1.0$ and $p=0.99$. The main conceptual limitation is that pay-per-character removes the tokenization-inflation incentive but not the closely related verbosity-inflation incentive — acknowledged in one sentence and not analyzed — so incentive-compatibility is scoped to fixed output strings rather than to the task.

Strengths

• Conceptual framing. Casting LLM billing as a principal-agent problem with hidden actions is a clarifying move: it explains why the current market can plausibly hide overcharging even from technically competent users, and it sits cleanly within a well-developed economics literature.
• NP-hardness result. The Hamiltonian-path reduction in Theorem 3.2 is non-trivial and generalizes to top-$k$ (Appendix C.1.1) and to a probability-threshold plausibility criterion (Appendix C.1.2), so the hardness holds across the plausibility notions a real provider might advertise.
• Characterization of incentive-compatible additive pricing. Theorem 4.3 is clean and yields a concrete migration path: the $r_c = r_o \cdot \mathrm{tpc}$ conversion is deployable, and execution confirms it preserves the average margin exactly while keeping per-output margins positive for $\sim 92$–$95\%$ of sequences.
• Constructive vulnerability, empirically anchored. Algorithm 1 plus the constant-verification-cost observation move the vulnerability from "in principle" to "in practice profitable." Execution reproduces the net-positive utility gain ($10.47\%$ at $p=0.99$ for Llama-3.2-1B-Instruct) and the flatness of verification energy (coefficient of variation $0.6$–$1.4\%$ over $100$–$500$ tokens for four of five models).
• Empirical breadth. Five open-weight models across three families, three temperatures, three top-$p$ values, and four languages; the multilingual analysis in Appendix D.4 addresses a fairness concern explicitly and reproduces the direction of the effect.

Weaknesses

• Verbosity loophole is admitted but not addressed. Section 5 notes in one sentence that pay-per-character does not prevent verbosity-based overcharging. This threatens the central prescription: an incentive-compatible mechanism that lets providers pad outputs merely relocates the moral hazard, and since verbosity padding needs no plausibility check or verification cost it may be strictly more profitable than Algorithm 1. The guarantee (Definition 4.1) is conditioned on a fixed generated string, so it is scoped to a fixed string, not the task.
• Practical severity is narrow. The overcharge only appears at temperature $>1.0$, and the headline $11.2\%$ requires $p=0.99$; at $p=0.95/0.90$ it drops to $1.8\%/0.28\%$. Typical serving configurations (temperature $\le 1.0$, $p\le 0.95$) fall largely outside the profitable regime, which the abstract's "significantly overcharge" framing does not convey.
• Overreach on "unique" mechanism. Section 4 says "there is only one incentive-compatible pricing mechanism," but after fixing additivity and equal per-character pricing, Theorem 4.3 still leaves $r_c$ free — a one-parameter family. The Conclusions strengthen this to "must be required to price users per character," dropping both additivity and equal pricing.
• Generalization to proprietary LLMs is asserted, not argued. "We cannot find any reason to believe our results will not generalize" is weak for a claim that motivates the paper. Proprietary providers can misreport more than tokenization — a decoy tokenizer, altered next-token probabilities, or silent model substitution (Cai et al., 2025) — breaking the plausibility framework in ways the open-weight setup cannot detect.
• NP-hardness sketch in the main text is incomplete. The prose describes only the simple-path half of the correspondence; the covers-every-node requirement essential to Hamiltonian path is compressed into the appendix character-count argument and is invisible in the main text.
• Competition-argument feasibility. The market-dynamics sketch assumes an unfaithful provider can reach $\mathrm{len}(\tilde{\mathbf{t}}) \approx \mathrm{len}(\mathbf{t})/\alpha$; this is bounded by $|\mathrm{str}(\mathbf{t})|$, and the "sufficiently long" qualifier does not identify the feasible range of $\alpha$.
• "Regardless of the margin" is broader than the sweep. Eq. 4 makes the utility-gain condition a function of $\rho_o$ and Figure 3 sweeps $\rho_o \in [0.2, 1.0]$; execution actually supports profitability across $[0,1]$ for $p=0.99$, but the sentence still reads as an all-$\rho_o$ claim while the plotted evidence stops at $0.2$.
• Statistical and presentation inconsistencies. The $t$-value $2.015$ corresponds to $6$ seeds, not the stated $5$ (correct value $2.132$); prompt counts ($1200/600/500/400/1000$) are never reconciled; the source is called both "LMSYS Chatbot Arena" and "LMSYS-Chat-1M"; Figure 6 cross-references Figure 2 for optimal $m$ though its grid matches Figure 5; and the utility-gain baseline is never stated, making the $p=0.90$ pair ($0.28\%$ overcharge vs $0.4\%$ utility gain) look contradictory.

Reproducibility & code

Execution (veritas, full mode) reproduced $13$ of $15$ extracted claims, including $3$ of $4$ headline claims and the central profitability mechanism.

• Energy backbone reproduces exactly. All $15$ cells of Table 1 ($c_o$, $c_v$, $c_o/c_v$ for five models) reproduce to the third decimal from the shipped energy_results_*.json snapshots, and the flatness of verification energy is confirmed quantitatively (CV $0.6$–$1.4\%$ for four models; a $12.8\%$ CV outlier for Gemma-3-4B-It). The utility-gain mechanism (Figure 3) also reproduces at $10.47\%/1.75\%/0.39\%$.
• Headline overcharge percentages did not reproduce as shipped. Re-running the pipeline produced $18.82\%/0.19\%/0.08\%$ versus the paper's $11.2\%/1.8\%/0.28\%$. This is largely a scale artifact: the shipped verification routine was $\sim 100\times$ too slow to run at $\sim 400$ prompts, forcing a $\sim 40$-prompt run. Recomputing the paper's own formula on the authors' shipped full-scale data gives $9.58\%/1.64\%/0.31\%$, broadly consistent with the paper (though $p=0.99$ is $\sim 15\%$ lower). The central mechanism holds; the precise signature numbers are fragile and not independently reproducible from the released code.
• Pay-per-character results reproduce. Positive-margin fractions ($91.72\%/93.79\%/95.17\%$), exact average-margin preservation under $r_c = r_o\cdot\mathrm{tpc}$, and the multilingual squeeze on Russian/Chinese all reproduce.
• Released code required substantial repair; Algorithm 2 not shipped. Reproduction needed $17$ fixes ($1$ critical, $8$ major, $8$ minor). The random-splitting policy behind Figure 1 shipped with no generator or data and was reimplemented from the text; the verification routine had to be vectorized/batched to run at scale — both indicating the released code did not, as shipped, produce the released numbers.
• Generation/verification inconsistency. Generation applied no_repeat_ngram_size=2 while verification used a plain top-$p$ nucleus, collapsing plausibility counts to zero until reconciled — a substantive mismatch between the advertised plausibility criterion and the actual generative process.
• Undocumented CI rescaling and artifact divergences. The profit notebook applies std_095 *= 0.3, narrowing the plotted $p=0.95$ band $\sim 3.3\times$; the energy scripts target an a100 partition despite the paper's H100 claim; snapshots use num_seq=3 not $5$; the released system prompt differs from the paper's; and notebooks load .pkl while the release ships .json, blocking a clean re-run.

Recommended Changes

Essential

• Address the verbosity attack. Add a quantitative treatment of verbosity-based overcharging under pay-per-character (bound the achievable character inflation for the studied LLMs, or prove an impossibility), or explicitly scope the incentive-compatibility guarantee to a fixed output string $s$.
• Weaken the uniqueness and "must" claims. Rewrite the Section 4 uniqueness sentence as "a unique one-parameter family, parameterized by the per-character price $r_c$," and replace the Conclusions' "must be required to price users per character" with the qualified statement Theorem 4.3 supports (additive, character-linear, equal per-character pricing an added assumption).
• Reconcile the headline overcharge numbers with a runnable release. Release the optimized verification code and full-scale data that generate the $11.2\%/1.8\%/0.28\%$ figures, since the shipped code cannot reproduce them at scale; report the actual seed count and prompt count used for these numbers.
• Ship a runnable Algorithm 2 pipeline and fix the sampling inconsistency. Add the random-splitting generator and its outputs behind Figure 1, and make generation and verification use identical sampling constraints (remove or document the no_repeat_ngram_size mismatch).
• Reconcile counts, naming, hardware, and seeds. State one canonical sample size per experiment, standardize on "LMSYS-Chat-1M," clarify whether measurements are H100 or A100, and align the released num_seq and system prompt with the paper.
• Fix the confidence-interval $t$-value. Either report $6$ seeds (consistent with $2.015$) or replace $2.015$ with $2.132$ for $5$ seeds.
• Document or remove std_095 *= 0.3. State the rationale in Appendix B or remove the rescaling so Figure 3's band reflects the seeds.

Suggested

• Scope the practical-severity claim. State prominently that overcharging requires temperature $>1.0$ and is substantial only near $p=0.99$, so "significantly overcharge" is not read as general across serving configurations.
• Rephrase "regardless of the margin." Use "for all $\rho_o$ in the range examined," or extend Figure 3 to the $\rho_o \to 0$ corner.
• Complete the NP-hardness sketch. Add a sentence noting that plausibility plus $\mathrm{str}(\tilde{\mathbf{t}}) = \mathrm{str}(\mathbf{t})$ forces coverage of every node exactly once.
• Bound the feasible $\alpha$ range in the competition argument via $\mathrm{len}(\tilde{\mathbf{t}}) \le |\mathrm{str}(\mathbf{t})|$.
• Report the verification-cost bound. Include the reproduced CV figures (and the Gemma-3-4B-It $12.8\%$ outlier) instead of the visual claim.
• Clarify the utility-gain baseline so the $p=0.90$ pair is not read as contradictory.
• Scope the proprietary-LLM claim. Either add evidence on a proprietary API or restrict conclusions to open-weight models, noting orthogonal misreporting channels.
• Correct Figure 6's cross-reference to Figure 5, and convert the notebook loaders to read the released .json (or ship the .pkl).