Technische Samenvatting: Tokenisatie-veelheid leidt tot willekeurige prijsvariatie in LLM-as-a-service

1. Probleemstelling

Het artikel behandelt een kritisch, maar vaak over het hoofd gezien probleem in de economie van Large Language Models (LLM's) die als dienst worden aangeboden (LLM-as-a-service). Momenteel maken aanbieders voornamelijk gebruik van een betaling-per-token prijsmodel, waarbij gebruikers een vaste prijs per gegenereerd token in rekening worden gebracht. De standaardveronderstelling is dat identieke input-prompts die resulteren in identieke output-strings, ook identieke kosten zouden moeten opleveren.

De auteurs tonen echter aan dat deze veronderstelling gebrekkig is vanwege tokenisatie-veelheid (tokenization multiplicity). Zelfs wanneer een LLM exact dezelfde output-string genereert (karakter voor karakter) vanuit dezelfde input-prompt, kan de onderliggende sequentie van tokens verschillen. Omdat de prijsstelling gebaseerd is op het aantal tokens in plaats van op het aantal karakters, leiden deze verschillende tokenisaties tot willekeurige prijsvariaties voor dezelfde output. Dit fenomeen komt met name veel voor bij niet-Engelse talen en heeft invloed op zowel propriëtaire als open-weights modellen.

2. Methodologie

Empirisch onderzoek

De auteurs hebben uitgebreide empirische studies uitgevoerd naar drie natuurlijke taaltaken: vertaling, spellingcontrole en herformulering.

• Opzet: Ze hebben 100 input-prompts per taak geconstrueerd met behulp van korte Wikipedia-teksten. Voor vertaling testten ze Engelse-naar-5-doeltaal paren; voor spellingcontrole en herformulering testten ze 6 talen.
• Uitvoering: Elke prompt werd 100 keer aan de LLM gevoed met identieke parameters maar verschillende random seeds om verschillende gebruikers te simuleren die dezelfde taak aanvragen.
• Modellen: De studie omvatte propriëtaire modellen (GPT-4o-mini, GPT-4.1, GPT-5-mini, Gemini, Claude) en open-weights modellen (Llama-3.1-8B-Instruct, Qwen2.5-7B-Instruct).
• Meting: Ze identificeerden paren van outputs waarbij de gedecodeerde strings identiek waren maar de tokenisatie-lengtes verschilden. Ze maten de waarschijnlijkheid van deze gebeurtenis en de omvang van de resulterende prijsvariatie.

Theoretische analyse

Het artikel definieert canonieke tokenisatie formeel als de unieke tokenisatie die een string ontvangt tijdens het trainingsproces van de LLM (bepaald door de encoder). De auteurs bewijzen een cruciaal theoretisch resultaat met betrekking tot niet-herstellende (non-recovering) tokenizers:

• Stelling: Voor BPE-, Unigram- en Wordpiece-tokenizers geldt dat als een gedeeltelijke tokensequentie niet-canonieke is, elke uitbreiding van die sequentie (het toevoegen van meer tokens) ook niet-canonieke zal zijn.
• Implicatie: Om een canonieke output-sequentie te genereren, moet het model in elke stap canonieke gedeeltelijke sequenties genereren. Deze eigenschap maakt gecontroleerde generatiestrategieën mogelijk.

Voorgestelde oplossing: Canonieke generatie

Om prijsvariatie te elimineren, introduceren de auteurs canonieke generatie, een methode voor gecontroleerde generatie die de LLM beperkt tot het genereren van enkel de canonieke tokenisatie van elke output-string.

• Algoritme: Ze stellen een efficiënt sampling-algoritme voor gebaseerd op de Gumbel-Max trick.
  • In plaats van expliciet een nieuwe waarschijnlijkheidsverdeling te berekenen (wat het controleren van alle vocabulaire-tokens op canoniciteit zou vereisen), samplet het algoritme Gumbel-ruis voor elk token.
  • Het rangschikt tokens op basis van hun geperturbeerde log-waarschijnlijkheden.
  • Het itereert door de gerangschikte tokens en selecteert de eerste die, wanneer toegevoegd aan de huidige sequentie, resulteert in een canonieke sequentie.
  • Deze aanpak herverdeelt effectief de waarschijnlijkheidsmassa van niet-canonieke tokens naar de resterende canonieke tokens zonder dure normalisatie.

3. Belangrijkste resultaten

Tokenisatie-veelheid

• Alomtegenwoordigheid: Tokenisatie-veelheid werd waargenomen in alle geteste modellen en taken. Voor open-weights modellen (Llama, Qwen) kwam het regelmatig voor bij alle drie de taken. Propriëtaire modellen vertoonden ook dit probleem, zij het met variërende frequenties.
• Taalafhankelijkheid: Het fenomeen komt aanzienlijk vaker voor in minderheidstalen (bijv. Turks, Swahili) dan in het Engels. Bijvoorbeeld, in vertalingstaken resulteerde tot wel 7% van de prompts voor Turks en Swahili in identieke strings met verschillende tokenisatie-lengtes.
• Prijsvariatie: Wanneer veelheid optreedt, kan het prijsverschil aanzienlijk zijn. De auteurs observeerden relatieve prijsverschillen van tot wel 15% voor dezelfde output-string tussen de kortste en de langste tokenisatie.
• Lange outputs: In langere teksten hebben tokenisatie-fouten de neiging te propageren; als een woord met een niet-canonieke tokenisatie wordt gegenereerd, volgen latere voorkomens van dat woord vaak hetzelfde niet-canonieke patroon, waardoor het prijsverschil wordt gecompenseerd.

Prestaties van canonieke generatie

• Theoretische garantie: De auteurs bewijzen dat de distributie van token-sequenties gegenereerd via canonieke generatie aantoonbaar dichter (in termen van KL-divergentie) bij de ware distributie van sequenties die tijdens de training zijn gezien dan de standaard generatie.
• Empirische prestaties: Experimenten op vertaling, spellingcontrole, herformulering en de MGSM (multilinguale wiskunde) benchmark laten zien dat canonieke generatie vergelijkbaar is met standaard generatie wat betreft:
  • Kwaliteit: Metrieken zoals vertaalkwaliteitsscores, edit distance en cosine similarity vertoonden verwaarloosbare verschillen (vaak binnen de foutmarge).
  • Runtime: De tijd per token nam slechts marginaal toe (bijv. van 0,019s naar 0,020s), wat de efficiëntie van het Gumbel-Max gebaseerde sampling-algoritme aantoont.
• Niet-canoniciteitspercentage: Standaard generatie produceerde niet-canonieke outputs in 6% tot 29% van de gevallen, afhankelijk van het model en de taak, terwijl canonieke generatie dit percentage door ontwerp terugbracht naar 0%.

4. Betekenis en Claims

Het artikel beweert het eerste empirische bewijs te leveren dat tokenisatie-veelheid leidt tot willekeurige en ongewenste prijsvariatie in LLM-as-a-service, zelfs wanneer aanbieders "getrouw" (faithful) zijn (d.w.z. niet opzettelijk de token-aantallen manipuleren).

• Economische impact: De bevindingen dagen de eerlijkheid van het pay-per-token model uit, door aan te tonen dat gebruikers aanzienlijk verschillende bedragen kunnen worden in rekening gebracht voor een identieke waarde (tekst) vanwege stochastische variaties in tokenisatie.
• Technische bijdrage: De introductie van canonieke generatie biedt een praktische oplossing die deze prijsvariatie elimineert zonder de modelprestaties op te offeren of de latentie significant te verhogen.
• Theoretisch inzicht: Het bewijs dat BPE, Unigram en Wordpiece niet-herstellend zijn, biedt een fundamenteel begrip van waarom niet-canonieke sequenties ontstaan en hoe deze via stap-voor-stap beperkingen kunnen worden voorkomen.

De auteurs concluderen dat hoewel canonieke generatie de sampling-ruimte iets beperkt (wat potentieel tot marginaal lagere prestaties kan leiden in specifieke gecontroleerde scenario's), het effectief het probleem van willekeurige prijsstelling oplost terwijl de output van hoge kwaliteit behouden blijft.