💬 NLP

Tokenisation over Bounded Alphabets is Hard

Dit artikel bewijst dat tokenisatie over begrensde alfabetten, inclusief binaire en unaire gevallen, fundamenteel NP-volledig en APX-hard is, waarmee wordt vastgesteld dat de computationele onhandelbaarheid een inherente barrière is in plaats van een artefact van grote invoeralfabetten, en legt de noodzaak uit van heuristische benaderingen in huidige praktische algoritmen.

Oorspronkelijke auteurs: Violeta Kastreva, Philip Whittington, Dennis Komm, Tiago Pimentel

Gepubliceerd 2026-08-11

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Violeta Kastreva, Philip Whittington, Dennis Komm, Tiago Pimentel

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een geheime boodschap naar een vriend probeert te sturen, maar de enige manier om deze te verzenden is door je woorden op te delen in kleine, vooraf goedgekeurde brokjes. Als je "superduper" stuurt, moet je het misschien opdelen in "super" en "duper" in plaats van het hele woord, omdat de woordenlijst van je vriend alleen die twee stukjes bevat. Dit is de kern van tokenisatie, de eerste stap in het leren begrijpen van menselijke taal door computers. Voordat een computer een zin kan lezen, moet hij deze opknippen in deze hanteerbare "tokens" (zoals Lego-steentjes). Het doel is om de tekst zo op te knippen dat er zo min mogelijk steentjes worden gebruikt, wat de boodschap korter en sneller maakt om te verzenden. Dit wordt compressie genoemd. Als je een boek kunt comprimeren tot minder steentjes, kan de computer het sneller lezen en er efficiënter van leren. Jarenlang hebben wetenschappers slimme, hebzuchtige algoritmen gebouwd — zoals een kind dat het grootste beschikbare Lego-stukje grijpt dat het kan vinden — om dit knippen automatisch te doen. Maar een grote vraag bleef hangen: is er een perfecte, wiskundig optimale manier om elke tekst op te knippen, of zijn we overgeleverd aan "goed genoeg" gissingen?

Dit artikel, getiteld "Tokenisation Over Bounded Alphabets Is Hard", duikt in de diepte van die vraag. De auteurs, een team van onderzoekers van ETH Zürich en de Sofia Universiteit, zetten zich af om te bewijzen of het vinden van die perfecte knippermethode daadwerkelijk een nachtmerrie voor computers is, zelfs wanneer de regels eenvoudig zijn. Ze richten zich op twee belangrijke manieren van knippen: Directe Tokenisatie, waarbij je de beste set Lego-steentjes (een vocabulaire) in één keer kiest, en Bottom-Up Tokenisatie, waarbij je begint met enkele letters en paren aan elkaar plakt totdat je geen lijm meer over hebt (merges). De grote twist in hun verhaal is dat ze deze methoden niet testen op het oneindige, chaotische alfabet van alle mogelijke menselijke klanken, maar op de kleine, vaste sets die we daadwerkelijk gebruiken in computers: binair (alleen 0's en 1's, zoals een lichtschakelaar) en unair (slechts één enkel symbool, zoals een snoer van identieke kralen).

De belangrijkste bevinding van het artikel is een luidruchtig "Nee, je kunt niet gemakkelijk de perfecte oplossing vinden." De auteurs bewijzen dat zelfs met de eenvoudigst mogelijke alfabetten — zoals een wereld die alleen uit enen en nullen bestaat — het vinden van de optimale manier om tekst te comprimeren NP-compleet en APX-hard is. In gewone mensentaal betekent dit dat, ongeacht hoeveel rekenkracht je tegen het probleem aan smijt, er geen snel, efficiënt algoritme is dat een optimaal resultaat kan garanderen. Het is niet alleen dat het probleem moeilijk is; het is dat het fundamenteel moeilijk is. Het artikel sluit expliciet de mogelijkheid uit dat de moeilijkheid voortkomt uit de complexiteit van menselijke taal of enorme alfabetten. In plaats daarvan laten ze zien dat de barrière zelfs in de eenvoudigste, meest beperkte scenario's bestaat. Bovendien bewijzen ze dat je zelfs niet "goed genoeg" dicht bij het perfecte antwoord kunt komen in een redelijke tijd; er is geen polynomial-time approximation scheme (PTAS) dat willekeurig dicht bij de beste oplossing komt, tenzij een groot wiskundig mysterie (P = NP) wordt opgelost.

De onderzoekers pakken ook het unaire geval aan, waarbij het alfabet slechts één symbool heeft (denk aan een bericht dat volledig uit de letter "a" bestaat). Je zou kunnen denken: "Als ik maar één letter heb, hoe moeilijk kan dat dan zijn?" Verrassend genoeg bewijzen ze dat zelfs hier, het vinden van de optimale manier om de tekst op te knippen, sterk NP-compleet is. Dit is een zwaar wiskundig resultaat dat suggereert dat de moeilijkheid niet slechts een eigenaardigheid is van grote datasets; het zit ingebakken in de logica van het optimaal comprimeren van tekst.

Dus, wat betekent dit voor de toekomst? Het artikel biedt geen nieuw, magisch algoritme om het probleem op te lossen. In plaats daarvan legt het uit waarom de tools die we vandaag de dag gebruiken, zoals BPE (Byte-Pair Encoding) en UnigramLM, gedwongen zijn om heuristisch te zijn — wat betekent dat ze slimme afkortingen en gissingen gebruiken in plaats van het perfecte antwoord te berekenen. De auteurs betogen dat omdat het vinden van het perfecte antwoord computationeel onmogelijk is om snel te doen, onderzoekers moeten stoppen met het najagen van de "heilige graal" van de optimale tokenizer en zich in plaats daarvan moeten richten op het bouwen van betere, bewezen goede benaderingsmethoden. De deur naar perfectie is vergrendeld en de sleutel bestaat niet; het beste wat we kunnen doen is leren om de beste lock-pick te kiezen die we hebben.

Probleemstelling
Recente theoretische studies hebben vastgesteld dat het vinden van een optimale tokenizer voor een dataset NP-volledig is. Deze eerdere resultaten berusten echter op de aanname dat tokenisatie opereert over onbegrensde grote alfabetten. In de praktische natuurlijke taalverwerking opereren tokenizers over vaste, begrensde alfabetten (bijv. bytes met grootte 256, Unicode-tekens met grootte ~170.000, of binaire/bitstrings met grootte 2). Het blijft een open vraag of de computationele onhandelbaarheid van tokenisatie voortduurt wanneer de alfabetgrootte begrensd is door een constante. Dit artikel adresseert deze kloof door de complexiteit van tokenisatie over begrensde alfabetten te analyseren, waarbij specifiek wordt onderzocht of optimale tokenizers efficiënt gevonden kunnen worden voor binaire (grootte 2) en unaire (grootte 1) alfabetten.

Methodologie
De auteurs definiëren het $n$ -aire tokenisatieprobleem, waarbij het invoeralfabet $\Sigma$ een grootte $n$ heeft. Zij analyseren twee natuurlijke varianten van tokenisatie:

Directe Tokenisatie: Het vinden van een vocabulaire $S$ van grootte $K$ die, wanneer deze optimaal op een dataset wordt toegepast, de totale compressielengte minimaliseert.
Bottom-up Tokenisatie: Het vinden van een sequentie van $K$ merge-operaties die, wanneer deze sequentieel op een dataset wordt toegepast, de totale compressielengte minimaliseert.

De gebruikte objectieve functie is de compressielengte (het totaal aantal tokens na codering), wat correleert met de kosten voor modeltraining en inferentie. De auteurs maken gebruik van standaard complexiteitstheoretische technieken om hardheid vast te stellen:

NP-hardheid: Bewezen via polynomiale-tijd reducties van bekende NP-harde problemen (specifiek 3-OCC-MAX2SAT en Vertex Cover) naar de tokenisatie-beslissingsproblemen.
APX-hardheid: Bewezen via L-reducties (approximatie-preserverende reducties) van APX-complete problemen. Dit toont aan dat de problemen niet behoren tot de klasse PTAS (Polynomial-Time Approximation Scheme), wat betekent dat ze niet in polynomiale tijd willekeurig goed benaderd kunnen worden, tenzij P = NP.
Gap-problemen: De auteurs definiëren gap-versies van de problemen om expliciete hardheidsconstanten voor approximatie af te leiden.

Belangrijkste Bijdragen en Resultaten

Binaire Tokenisatie is APX-hard:
Het artikel bewijst dat zowel binaire directe tokenisatie als binaire bottom-up tokenisatie APX-hard zijn.

Direct geval: Er wordt aangetoond dat binaire directe tokenisatie niet in polynomiale tijd benaderd kan worden met een approximatieverhouding $\rho < 1,000002$ (tenzij P = NP).
Bottom-up geval: Eveneens is binaire bottom-up tokenisatie APX-hard met een hardheidsconstante van $\rho < 1,0000001$ .
Deze resultaten impliceren dat zelfs voor het eenvoudigste niet-triviale alfabet (binair), het vinden van een optimale tokenizer computationeel onhandelbaar is, en dat geen polynomiale algoritme een garantie kan bieden op een benadering die willekeurig dicht bij het optimum ligt.

Unaire Tokenisatie is Sterk NP-volledig:
De auteurs onderzoeken het unaire geval (alfabetgrootte 1), wat theoretisch de "eenvoudigste" variant is.

Zij bewijzen dat unaire directe tokenisatie sterk NP-volledig is. Dit wordt bereikt via een reductie van het Vertex Cover-probleem. Het bewijs stelt vast dat de hardheid inherent is aan de probleemstructuur en niet een artefact is van de inputrepresentatie (string vs. stringlengte).
Voor unaire bottom-up tokenisatie stelt het artikel vast dat een variant bekend als Optimal Pair Encoding (OPE) tokenisatie (ten minste) zwak NP-volledig is, via een reductie van het Addition Chain-probleem. De complexiteit van standaard unaire bottom-up tokenisatie blijft een open vraag in dit werk.

Hiërarchie van Hardheid:
Het artikel stelt een duidelijke hiërarchie vast: als $n$ -aire tokenisatie hard is, dan is $n'$ -aire tokenisatie voor alle $n' > n$ ook hard. Bij consequent zijn de hardheidsresultaten voor binaire en unaire gevallen ook triviaal uitbreidbaar naar alle grotere begrensde alfabetten (inclusclusief byte- en Unicode-alfabetten).

Betekenis en Claims
Het artikel claimt dat deze resultaten het begrip van de complexiteit van tokenisatie fundamenteel veranderen. Door te bewijzen dat tokenisatie hard blijft, zelfs over unaire en binaire alfabetten, tonen de auteurs aan dat de computationele onhandelbaarheid niet een artefact is van grote alfabetten of complexe merge-operaties. In plaats daarvan is het een fundamentele barrière die inherent is aan het probleem van het optimaal comprimeren van data via tokenisatie.

Deze bevindingen bieden een theoretische rechtvaardiging voor waarom huidige praktische algoritmen, zoals Byte-Pair Encoding (BPE) en UnigramLM, vertrouwen op heuristieken en greedystrategieën in plaats van exacte optimalisatie. Het artikel concludeert dat toekomstig onderzoek zich moet richten op het ontwikkelen van bewijsbaar goede benaderingsalgoritmen of het versoepelen van de probleemrestricties, aangezien het vinden van exacte optimale tokenizers waarschijnlijk onmogelijk is voor elke niet-triviale datasetgrootte.

Meer zoals dit