Technisches Resümee: Tokenisierungs-Multiplizität führt zu willkürlicher Preisvariation bei LLM-as-a-service

1. Problemstellung

Die Arbeit befasst sich mit einem kritischen, jedoch oft übersehenen Problem in der Ökonomie von Large Language Models (LLMs), die als Dienstleistung angeboten werden (LLM-as-a-service). Derzeit verwenden Anbieter vorwiegend ein Pay-per-Token-Preismodell, bei dem Nutzer einen festen Preis pro generiertem Token berechnet wird. Die Standardannahme lautet, dass identische Input-Prompts, die identische Output-Strings ergeben, auch identische Kosten verursachen sollten.

Die Autoren zeigen jedoch auf, dass diese Annahme aufgrund der Tokenisierungs-Multiplizität fehlerhaft ist. Selbst wenn ein LLM exakt denselben Output-String (Zeichen für Zeichen) aus demselben Input-Prompt generiert, kann die zugrunde liegende Sequenz der Token variieren. Da die Preisgestaltung auf der Token-Anzahl statt auf der Zeichenanzahl basiert, führen diese unterschiedlichen Tokenisierungen zu willkürlichen Preisvariationen für denselben Output. Dieses Phänomen tritt besonders häufig bei nicht-englischen Sprachen auf und betrifft sowohl proprietäre als auch Open-Weights-Modelle.

2. Methodik

Empirische Untersuchung

Die Autoren führten umfangreiche empirische Studien zu drei natürlichen Sprachaufgaben durch: Übersetzung, Rechtschreibprüfung und Umformulierung.

• Setup: Sie erstellten 100 Input-Prompts pro Aufgabe unter Verwendung kurzer Wikipedia-Texte. Für die Übersetzung testeten sie Englisch-zu-5-Zielsprache-Paare; für Rechtschreibprüfung und Umformulierung testeten sie 6 Sprachen.
• Ausführung: Jeder Prompt wurde dem LLM 100 Mal mit identischen Parametern, aber unterschiedlichen Random Seeds, zugeführt, um verschiedene Nutzer zu simulieren, die dieselbe Aufgabe anfordern.
• Modelle: Die Studie umfasste proprietäre Modelle (GPT-4o-mini, GPT-4.1, GPT-5-mini, Gemini, Claude) sowie Open-Weights-Modelle (Llama-3.1-8B-Instruct, Qwen2.5-7B-Instruct).
• Messung: Sie identifizierten Paare von Outputs, bei denen die dekodierten Strings identisch waren, sich jedoch in der Länge der Tokenisierung unterschieden. Sie maßen die Wahrscheinlichkeit dieses Vorkomkommens sowie das Ausmaß der daraus resultierenden Preisvariation.

Theoretische Analyse

Die Arbeit definiert die kanonische Tokenisierung formal als die eindeutige Tokenisierung, die ein String während des Trainingsprozesses des LLM erhält (bestimmt durch den Encoder). Die Autoren beweisen ein zentrales theoretisches Ergebnis bezüglich nicht-rekursiver Tokenizer:

• Theorem: Für BPE-, Unigram- und Wordpiece-Tokenizer gilt: Wenn eine partielle Token-Sequenz nicht-kanonisch ist, wird jede Erweiterung dieser Sequenz (das Anhängen weiterer Tokens) ebenfalls nicht-kanonisch sein.
• Implikation: Um eine kanonische Output-Sequenz zu generieren, muss das Modell auf jedem Schritt kanonische partielle Sequenzen generieren. Diese Eigenschaft ermöglicht kontrollierte Generierungsstrategien.

Lösungsvorschlag: Kanonische Generierung

Um die Preisvariation zu elimin Sie, führen die Autoren die kanonische Generierung ein, eine Methode der beschränkten Generierung (constrained generation), die das LLM darauf beschränkt, nur die kanonische Tokenisierung eines jeden Output-Strings zu generieren.

• Algorithmus: Sie schlagen einen effizienten Sampling-Algorithmus basierend auf dem Gumbel-Max-Trick vor.
  • Anstatt explizit eine neue Wahrscheinlichkeitsverteilung zu berechnen (was die Prüfung aller Vokabular-Tokens auf Kanonizität erfordern würde), sampelt der Algorithmus Gumbel-Rauschen für jedes Token.
  • Er rankt die Tokens nach ihren perturbierten Log-Wahrscheinlichkeiten.
  • Er iteriert durch die gerankten Tokens und wählt den ersten aus, der, wenn er an die aktuelle Sequenz angehängt wird, zu einer kanonischen Sequenz führt.
  • Dieser Ansatz verteilt die Wahrscheinlichkeitsmasse nicht-kanonischer Tokens effektiv auf die verbleibenden kanonischen Tokens, ohne eine teure Normalisierung zu benötigen.

3. Kernergebnisse

Tokenisierungs-Multiplizität

• Häufigkeit: Tokenisierungs-Multiplizität wurde in allen getesteten Modellen und Aufgaben beobachtet. Bei Open-Weights-Modellen (Llama, Qwen) trat sie regelmäßig in allen drei Aufgaben auf. Auch proprietäre Modelle zeigten das Problem, wenngleich mit variierenden Häufigkeiten.
• Sprachabhängigkeit: Das Phänomen tritt in Minderheitensprachen (z. B. Türkisch, Swahili) signifikant häufiger auf als im Englischen. Beispielsweise führten bei Übersetzungsaufgaben bis zu 7 % der Prompts für Türkisch und Swahili zu identischen Strings mit unterschiedlichen Tokenisierungs-Längen.
• Preisvariation: Wenn Multiplizität auftritt, kann der Preisunterschied erheblich sein. Die Autoren beobachteten relative Preisunterschiede von bis zu 15 % für denselben Output-String zwischen der kürzesten und der längsten Tokenisierung.
• Lange Outputs: Bei längeren Texten neigen Tokenisierungsfehler dazu, sich fortzupflanzen; wenn ein Wort mit einer nicht-kanonischen Tokenisierung generiert wird, folgen spätere Vorkommen desselben Wortes oft demselben nicht-kanonischen Muster, was den Preisunterschied verstärkt.

Leistung der kanonischen Generierung

• Theoretische Garantie: Die Autoren beweisen, dass die Verteilung der mittels kanonischer Generierung erzeugten Token-Sequenzen (gemessen an der KL-Divergenz) nachweislich näher an der wahren Verteilung der während des Trainings gesehenen Sequenzen liegt als die Standard-Generierung.
• Empirische Leistung: Experimente zu Übersetzung, Rechtschreibprüfung, Umformulierung und dem MGSM-Benchmark (multilingualer Mathematik) zeigen, dass die kanonische Generierung hinsichtlich der Qualität mit der Standard-Generierung vergleichbar ist:
  • Qualität: Metriken wie Übersetzungsqualitäts-Scores, Edit-Distanz und Kosinus-Ähnlichkeit zeigten vernachlässigbare Unterschiede (oft innerhalb der Fehlermarge).
  • Laufzeit: Die Zeit pro Token stieg nur marginal an (z. B. von 0,019s auf 0,020s), was die Effizienz des Gumbel-Max-basierten Sampling-Algorithmus demonstriert.
• Nicht-Kanonizitätsrate: Die Standard-Generierung produzierte in 6 % bis 29 % der Fälle (je nach Modell und Aufgabe) nicht-kanonische Outputs, während die kanonische Generierung diese Rate durch Design auf 0 % reduzierte.

4. Bedeutung und Behauptungen

Das Paper behauptet, den ersten empirischen Beleg dafür zu liefern, dass Tokenisierungs-Multiplizität zu willkürlichen und unerwünschten Preisvariationen bei LLM-as-a-service führt, selbst wenn die Anbieter „treu“ sind (d. h. die Token-Anzahl nicht absichtlich manipulieren).

• Ökonomische Auswirkungen: Die Ergebnisse stellen die Fairness des Pay-per-Token-Modells infrage und zeigen, dass Nutzer für denselben Wert (Text) aufgrund stochastischer Variationen in der Tokenisierung signifikant unterschiedliche Beträge berechnet bekommen können.
• Technischer Beitrag: Die Einführung der kanonischen Generierung bietet eine praktische Lösung, die diese Preisvariation eliminiert, ohne die Modellleistung oder die Latenz signifikant zu beeinträchtigen.
• Theoretische Erkenntnis: Der Beweis, dass BPE, Unigram und Wordpiece nicht-rekursiv sind, liefert ein grundlegendes Verständnis dafür, warum nicht-kanonische Sequenzen entstehen und wie diese durch schrittweise Beschränkungen verhindert werden können.

Die Autoren kommen zu dem Schluss, dass die kanonische Generierung zwar den Sampling-Raum leicht einschränkt (was potenziell zu geringfügig niedrigerer Leistung in spezifischen, beschränkten Szenarien führen kann), sie aber das Problem der willkürlichen Preisgestaltung effektiv löst und gleichzeitig eine qualitativ hochwertige Output-Generierung aufrechterhält.