Technische Samenvatting: Tokenisatie met Splitsbomen (ToaST)

Probleemstelling

Tokenisatie is een fundamentele stap in natuurlijke taalverwerking, maar bestaande methoden vertrouwen vaak op hebberige heuristieken die niet optimaal zijn voor compressie of prestaties in downstream taken. Hoewel Byte Pair Encoding (BPE) het aantal tokens minimaliseert via een hebberige samenvoegstrategie, is dit een heuristische benadering. Eerdere studies hebben aangetoond dat het vinden van een tokenisator die compressie maximaliseert NP-compleet is, zelfs over beperkte alfabetten. Bovendien blijft de relatie tussen compressie en prestaties in downstream taken onderwerp van debat; terwijl sommige studies een correlatie suggereren, betogen anderen dat compressie alleen onvoldoende is om de kwaliteit van tokenisatie te verklaren. Bestaande alternatieven, zoals UnigramLM of PathPiece, maken gebruik van verschillende inferentieprocedures (bijvoorbeeld ablative top-down of kortste-pad-inferentie), maar staan nog steeds voor uitdagingen op het gebied van globale optimalisatie en computationele schaalbaarheid.

Methodologie

De auteurs introduceren Tokenization with Split Trees (ToaST), een methode voor subwoord-tokenisatie die de constructie van kandidaat-tokens ontkoppelt van de selectie van de definitieve vocabulaire. De aanpak bestaat uit drie hoofdfasen:

1. Constructie van de Splitsboom

In tegenstelling tot BPE, dat tokens van onderop naar boven opbouwt, of UnigramLM, dat kansen van boven naar beneden leert, construeert ToaST een volledige binaire boom voor elke unieke pretoken in het trainingscorpus, onafhankelijk van elke vocabulaire.

• Preprocessing: Trainingsdata wordt opgesplitst in pretokens met behulp van een reguliere expressie.
• Splitslogica: Voor een gegeven pretoken splitst het algoritme deze recursief op in twee niet-lege delen. Het splitspunt wordt deterministisch gekozen om het minimumaantal van de resulterende linker- en rechter-byte-n-grammen te maximaliseren ($\max \min(c_p, c_{p'})$), gebaseerd vooraf berekende n-gramstatistieken uit het corpus.
• Structuur: Dit proces gaat door tot de bladeren enkele bytes zijn. De knopen van deze bomen vormen de set van alle kandidaat-tokens. Deze constructie is onafhankelijk van de definitieve vocabulaire en vereist geen iteratieve training.

2. Recursieve Inferentie

Gegeven een vocabulaire $V$, wordt tokenisatie uitgevoerd via een recursieve afdaling door de splitsboom:

• Beginnen bij de wortel (de volledige pretoken), controleert het algoritme of de huidige knoop in $V$ zit.
• Als de knoop in $V$ zit, wordt deze uitgegeven als een token.
• Zo niet, dan verwerkt het algoritme recursief de twee kinderen.
• Eigenschappen: Deze procedure garandeert dat elke vocabulaire die alle noodzakelijke enkele bytes bevat, een geldige tokenisatie oplevert. Het verwijderen van een token uit de vocabulaire dwingt de inferentie simpelweg om verder in de boom af te dalen, zonder cascade-effecten op andere tokens, in tegenstelling tot op samenvoeging gebaseerde methoden.

3. Vocabulaire-selectie via Integer Programming

De kerninnovatie is het formuleren van vocabulaire-selectie als een Integer Program (IP) om het totale aantal tokens over het trainingscorpus te minimaliseren.

• Variabelen: Binaire variabelen $x_i$ geven aan of kandidaat-token $i$ in de vocabulaire zit. Binaire variabelen $z_{jk}$ geven aan of knoop $k$ in splitsboom $j$ tijdens inferentie wordt uitgegeven.
• Doelfunctie: Minimaliseer het totale gewogen aantal uitgegeven tokens: $\min \sum_{j} c_j \sum_{k} z_{jk}$.
• Beperkingen:
  • Vocabulaire-grootte: De som van geselecteerde tokens moet gelijk zijn aan de doelgrootte $m$.
  • Dekking: Voor elk pad van een blad naar de wortel moet precies één knoop worden geselecteerd (zodat de volledige pretoken wordt gedekt).
  • Consistentie: Een knoop kan alleen worden uitgegeven ($z_{jk}=1$) als deze in de vocabulaire zit ($x_i=1$) en geen van zijn voorouders.
• Oplossen: Het IP wordt ontspannen tot een Lineair Program (LP). In de praktijk is de LP-ontspanning "bijna-integraal", wat betekent dat de oplossing zeer weinig fractionele waarden bevat. Een eenvoudige afrondingsheuristiek wordt toegepast om een geheeltallige oplossing te verkrijgen die bewezen bijna-optimaal is (binnen een verwaarloosbaar deel van het globale optimum).

Belangrijkste Bijdragen

1. Nieuw Tokenisatiekader: ToaST introduceert een op splitsbomen gebaseerde aanpak die de hebberige benaderingen van BPE en de specifieke inferentiebeperkingen van UnigramLM vermijdt.
2. Globale Optimalisatie: Door vocabulaire-selectie te formuleren als een IP met een strakke LP-ontspanning, vindt ToaST een vocabulaire die het totale aantal tokens voor een gegeven set splitsbomen globaal minimaliseert, in plaats van te vertrouwen op lokale hebberige beslissingen.
3. Schaalbaarheid: De methode schaalt kwadratisch met het aantal splitsbomen, waardoor het verwerken van grote corpusse (die 99% van de pretoken-aantallen dekken) binnen haalbare trainingstijden mogelijk is.
4. Ontkoppeld Ontwerp: De scheiding tussen boomconstructie (gebaseerd op corpusstatistieken) en vocabulaire-selectie (gebaseerd op optimalisatie) maakt flexibele uitbreidingen mogelijk, zoals het integreren van morfologische of karakterniveau-preferenties zonder de optimalisatiemodel opnieuw te trainen.

Experimentele Resultaten

De auteurs hebben ToaST geëvalueerd op Engelse tekst met behulp van het CulturaX-dataset en dit vergeleken met BPE, WordPiece en UnigramLM.

• Compressie: Bij vocabulaire-groottes van 40.960 en hoger reduceert ToaST het aantal tokens met meer dan 11% ten opzichte van alle baselines. Dit wordt gemeten in bytes per token.
• Tokenverdeling: ToaST reduceert de frequentie van "Leaf"-tokens (enkele-byte fallbacks) significant met 14–19x ten opzichte van baselines bij een vocabulaire-grootte van 65.536. Omgekeerd produceert het aanzienlijk meer "Root"-tokens (volledige pretokens), wat wijst op een betere behoud van semantische eenheden.
• Rényi-efficiëntie: ToaST bereikt een hogere Rényi-efficiëntie (met $\alpha=2.5$), wat wijst op een uniformere tokenverdeling en minder hoog-frequente tokens, wat vaak correleert met betere prestaties in downstream taken.
• Prestaties in downstream taken: In experimenten met het trainen van taalmodellen van 1,5 miljard parameters (nanochat) behaalde ToaST de hoogste CORE-score (een gemiddelde van 22 benchmarks), en presteerde het 2,6% tot 7,6% beter dan de baselines. Het presteerde aanzienlijk beter dan BPE en UnigramLM, en was de beste performer op 13 van de 22 individuele taken.
• Kwaliteit van optimalisatie: De LP-ontspanning bleek uitzonderlijk strak. Over 128 probleeminstanties was het maximale relatieve gat tussen de afgeronde geheeltallige oplossing en de LP-bodem $5.76 \times 10^{-7}$, waarbij veel instanties volledig integraal waren.

Betekenis en Beweringen

De paper beweert dat ToaST de waarde aantoont van het direct optimaliseren van tokenisatie voor compressie met behulp van een kader voor globale optimalisatie, in plaats van te vertrouwen op hebberige heuristieken. De auteurs betogen dat de superieure compressie leidt tot een groter effectief contextvenster en bijgevolg tot verbeterde prestaties in downstream taken.

De betekenis van het werk ligt in:

• Praktijktoepasbaarheid: Ondanks de theoretische NP-compleetheid van optimale tokenisatie, maakt de LP-ontspanning de aanpak computationeel haalbaar en praktisch voor training op grote schaal.
• Prestaties: De empirische resultaten suggereren dat de 11% reductie in het aantal tokens vertaalt naar meetbare winsten in de prestaties van taalmodellen (CORE-score), wat de hypothese ondersteunt dat betere compressie correleert met betere modelbruikbaarheid.
• Flexibiliteit: De architectuur maakt toekomstige uitbreidingen mogelijk, zoals het verwerken van multi-byte karakters of morfologische splitsingen, door de hiërarchie van boomconstructie te wijzigen zonder de optimalisatielogica van de vocabulaire te veranderen.

De auteurs merken beperkingen op, specifiek dat experimenten uitsluitend zijn uitgevoerd op Engelse tekst, en dat de effectiviteit van training op de top-aggregatie van pretokens kan variëren voor talen zonder spaties als scheidingsteken. Ze onthullen ook het gebruik van LLM's voor de implementatie van code en het genereren van figuren.