Bouw een BPE-tokenizer: waarom je model de r’s niet kan tellen

Er zijn twee voor de hand liggende manieren om tekst aan een netwerk te voeren, en beide falen om redenen die het waard zijn om te begrijpen, omdat die mislukking de vorm van de oplossing bepaalt.

Woorden. Splits op spaties, geef elk woord een getal. Engels heeft honderdduizenden woordvormen en het model heeft voor elk daarvan een embedding-rij nodig, waardoor de vocabulaire — en de outputlaag, die voor elke entry een score moet produceren — enorm wordt. Erger is wat er bij inference gebeurt: een woord dat het model tijdens training nooit heeft gezien, heeft geen getal. Dat is het out-of-vocabulary-probleem, en de gebruikelijke pleister is om alles wat onbekend is naar één enkele <UNK> token te mappen, waardoor de informatie wordt weggegooid. Bovendien is “woord” geen goed gedefinieerd concept: Chinees en Japans zetten geen spaties tussen woorden, en het Duits plakt zelfstandig naamwoorden eindeloos aan elkaar.

Tekens. Geen out-of-vocabulary-probleem, en een vocabulaire van een stuk of honderd symbolen. Maar de sequenties worden erg lang, en Hoofdstuk 9 laat zien dat de kosten van attention kwadratisch groeien met de sequentielengte. Een document van 1000 woorden telt ongeveer 5000 tekens — een sequentie die vier tot vijf keer langer is dan nodig, tegen een kwadratische prijs. En elk teken draagt op zichzelf bijna geen betekenis, dus de eerste paar lagen zijn bezig woorden weer in elkaar te zetten die de tokenizer intact had kunnen doorgeven.

Het antwoord ligt ertussenin: subwoorden. Veelvoorkomende woorden worden één token, zeldzame woorden worden opgesplitst in stukjes, en niets is ooit onbekend omdat de stukjes onderaan uitkomen bij afzonderlijke bytes. Het interessante is dat niemand de splitsing ontwerpt. De tokenizer wordt getraind, op hetzelfde soort data als het model, en hij leert welke byte-sequenties hun eigen getal waard zijn door te tellen hoe vaak ze samen voorkomen.

Het algoritme komt uit 1994, en het was een compressie-algoritme. Philip Gage publiceerde het in het C Users Journal als een manier om bestanden te verkleinen door herhaaldelijk het meest voorkomende paar aangrenzende bytes te vervangen door een byte die niet in de data voorkomt.¹ Daar bleef het tweeëntwintig jaar liggen, totdat Sennrich, Haddow en Birch het in 2016 hergebruikten voor machinevertaling om het out-of-vocabulary-probleem op te lossen.² Het is nu hoe vrijwel elk groot taalmodel leest.

De trainingslus bestaat uit vier herhaalde stappen:

Hier is de volledige trainer:

def get_stats(ids):
    counts = {}
    for a, b in zip(ids, ids[1:]):
        counts[(a, b)] = counts.get((a, b), 0) + 1
    return counts


def merge(ids, pair, idx):
    out, i = [], 0
    while i < len(ids):
        if i < len(ids) - 1 and ids[i] == pair[0] and ids[i + 1] == pair[1]:
            out.append(idx)
            i += 2
        else:
            out.append(ids[i])
            i += 1
    return out


class BPE:
    def __init__(self):
        self.merges = {}
        self.vocab = {i: bytes([i]) for i in range(256)}

    def train(self, text, vocab_size):
        ids = list(text.encode("utf-8"))
        for i in range(vocab_size - 256):
            stats = get_stats(ids)
            if not stats:
                break
            pair = max(stats, key=stats.get)      
            idx = 256 + i                         
            ids = merge(ids, pair, idx)           
            self.merges[pair] = idx               
            self.vocab[idx] = self.vocab[pair[0]] + self.vocab[pair[1]]
        return ids

Draai hem op 151.191 bytes Engelse proza en print de eerste twaalf merges terwijl ze gebeuren. Dit is het deel dat je langzaam moet lezen, want niemand heeft het algoritme iets over Engels verteld:

merge   1: b'e' + b' '   -> b'e '     (occurred 4433 times)
merge   2: b' ' + b't'   -> b' t'     (occurred 3302 times)
merge   3: b'\xe2' + b'\x80' -> b'\xe2\x80'  (occurred 3247 times)
merge   4: b' ' + b'a'   -> b' a'     (occurred 2335 times)
merge   5: b' t' + b'h'  -> b' th'    (occurred 2253 times)
merge   6: b'i' + b'n'   -> b'in'     (occurred 2011 times)
merge   7: b't' + b' '   -> b't '     (occurred 1904 times)
merge   8: b'e' + b'r'   -> b'er'     (occurred 1813 times)
merge   9: b'd' + b' '   -> b'd '     (occurred 1703 times)
merge  10: b'o' + b'u'   -> b'ou'     (occurred 1554 times)
merge  11: b' ' + b's'   -> b' s'     (occurred 1467 times)
merge  12: b' th' + b'e '-> b' the '  (occurred 1270 times)

Drie dingen in die lijst verdienen aandacht.

Merge 12 is het woord “the” — met de spatie ervoor en de spatie erna, als één geheel, ontdekt in de twaalfde iteratie van een lus die paren telt. Niemand leverde een woordenboek aan. Het staat daar omdat die vijf bytes vaker samen voorkomen dan welke andere vijf dan ook in het Engels.

Merge 3 is helemaal geen tekst. \xe2\x80 zijn de eerste twee bytes van de UTF-8-encoding van typografische interpunctie — het em-streepje, de gekrulde aanhalingstekens. Het algoritme heeft geen idee dat UTF-8 bestaat, en het heeft zojuist een stuk van de structuur ervan herontdekt, omdat multibyte-encodings per constructie sequenties van bytes zijn die altijd samen verschijnen.

De meeste vroege merges bevatten een spatie, en die spatie staat meestal links. Dat is de oorsprong van een van de meest verwarrende gedragingen in de praktijk, waar we zo op terugkomen.

Elke merge maakt de sequentie korter en de vocabulaire groter. Hoe ver je dat doorduwt is een echte keuze, en die kun je meten — hier op dezelfde 151.191 bytes:

Afnemende meeropbrengsten, duidelijk zichtbaar. Verdubbelen van 512 naar 1024 levert 0,78 bytes per token op; verdubbelen van 2048 naar 4096 levert 1,07 op — hier beter, maar alleen omdat dit corpus klein genoeg is dat langere merges blijven renderen. Op een echt corpus vlakt de curve hard af.

En de kosten van een grotere vocabulaire zijn niet alleen geheugen. Elke token heeft een embedding-rij nodig, en — duurder nog — de outputlaag van het model moet bij elke stap voor elke entry in de vocabulaire een score produceren, dus de laatste matrixvermenigvuldiging schaalt met de vocabulairegrootte. Echte modellen zitten tussen 32.000 en 200.000: GPT-2 gebruikte 50.257, GPT-4’s cl100k gebruikt 100.277, GPT-4o’s o200k verdubbelt dat ongeveer. De trend is omhoog, en de reden staat in de volgende sectie.

Hier is dezelfde alinea, vertaald, gemeten met de echte tokenizers die OpenAI levert:

Dezelfde inhoud, dezelfde betekenis, en met cl100k verbruikt de Russische versie tweeënhalf keer zoveel tokens. Omdat API’s per token afrekenen en context windows in tokens worden gemeten, is dat geen taalkundige curiositeit — het is een regel in een budget, een kortere effectieve context window en een tragere respons, alle drie tegelijk, voor iedereen die niet in het Engels werkt.

Het mechanisme is de trainingsdata. Een tokenizer die vooral op Engels is getraind besteedt zijn merge-budget aan Engelse byte-sequenties. Spaans deelt het Latijnse alfabet, dus profiteert nog enigszins; Russisch bijna niet, omdat Cyrillische tekens in UTF-8 twee bytes innemen en weinig van die paren vaak genoeg voorkwamen in het trainingscorpus om een merge te verdienen. Japans is nog erger: drie bytes per teken, en 72 tekens worden 79 tokens — meer tokens dan tekens.

De o200k-kolom laat zien dat dit probleem oplosbaar is en dat het wordt opgelost. De vocabulaire verdubbelen en de trainingsdata opnieuw balanceren verlaagt de Spaanse overhead van +39 % naar +16 %, en de Russische van +152 % naar +39 %. Dat is de echte reden dat vocabulaires blijven groeien: niet compressie om de compressie, maar het feit dat de vorige generatie stilletjes een groot deel van de wereld extra liet betalen.

Training leverde een geordende lijst merges op. Nieuwe tekst encoden speelt die opnieuw af — en moet dat in dezelfde volgorde doen, omdat merge 12 de resultaten van merges 5 en 1 combineert. Pas ze in een andere volgorde toe en je krijgt een andere, verkeerde tokenization die niet overeenkomt met wat het model tijdens training heeft gezien.

    def encode(self, text):
        ids = list(text.encode("utf-8"))
        while len(ids) >= 2:
            stats = get_stats(ids)
            # the pair whose merge came FIRST during training wins   
            pair = min(stats, key=lambda p: self.merges.get(p, float("inf")))   
            if pair not in self.merges:
                break
            ids = merge(ids, pair, self.merges[pair])
        return ids

    def decode(self, ids):
        return b"".join(self.vocab[i] for i in ids).decode("utf-8", errors="replace")

Decoding is in vergelijking triviaal: zoek de bytes van elke id op, plak ze aan elkaar, decodeer als UTF-8. Let op de errors="replace": een model kan een token-sequentie uitsturen die midden in een teken eindigt, en dat is geen hypothetisch geval — het gebeurt wanneer een streamingrespons midden in een emoji wordt afgekapt, en daarom bufferen streaming-API’s gedeeltelijke bytes in plaats van token voor token te decoden.

Round-tripping werkt op alles, en dat is de belofte van byte-level BPE:

'strawberry'                            -> 6 tokens, decode == original: True
'Alice was beginning to get very tired' -> 14 tokens, decode == original: True
'café — naïve — 日本語'                   -> 23 tokens, decode == original: True

Zodra het mechanisme duidelijk is, blijken een aantal ogenschijnlijk losse klachten dezelfde klacht te zijn.

Rekenen. Getallen worden niet op een consistente manier opgesplitst:

1234     -> 2 tokens  ['123', '4']
12345    -> 2 tokens  ['123', '45']
1000000  -> 3 tokens  ['100', '000', '0']
3.14159  -> 4 tokens  ['3', '.', '141', '59']
2024     -> 2 tokens  ['202', '4']

Om 1234 en 12345 op te tellen moet het model eerst uitvinden dat ['123','4'] en ['123','45'] getallen zijn waarvan de cijfers op een bepaalde manier uitlijnen — en die uitlijning verschilt voor elk paar getallen. De cijfers van een getal staan niet van het ene getal op het andere op dezelfde plekken. Sommige nieuwere tokenizers dwingen cijfers juist om in consistente groepen van drie te splitsen om dit obstakel weg te nemen, en modellen die daarmee zijn getraind zijn meetbaar beter in rekenen.

Python-inspringing.

'    x = 1'      -> 5 tokens  ['   ', ' x', ' =', ' ', '1']
'        x = 1'  -> 5 tokens  ['       ', ' x', ' =', ' ', '1']
'\tx = 1'        -> 4 tokens  ['\tx', ' =', ' ', '1']

Vier spaties en acht spaties zijn verschillende losse tokens, en een tab is samengesmolten met het teken erna. Inspringing, die in Python syntax is, wordt inconsistent weergegeven — wat een groot deel verklaart van waarom modellen vroeger Python produceerden met subtiel verkeerde inspringing, en waarom codegerichte tokenizers expliciete tokens toevoegen voor veelvoorkomende inspringreeksen.

Spelling en omkeren. Dezelfde oorzaak als bij het tellen van de r’s: een model vragen om strawberry om te keren is het vragen letters binnen drie ondoorzichtige ids te herschikken. Modellen doen dat doordat ze tijdens training spellingen hebben gememoriseerd, niet doordat ze kijken, en daarom doen ze het goed bij veelvoorkomende woorden en slecht bij zeldzame.

Glitch tokens. Het opvallendste geval is SolidGoldMagikarp en een set vergelijkbare strings die GPT-2 en GPT-3 zich bizar lieten gedragen — weigeren ze te herhalen, niet-gerelateerde output produceren, soms de gebruiker beledigen. De verklaring is alledaags en volgt rechtstreeks uit het feit dat de tokenizer apart van het model wordt getraind: die strings kwamen vaak voor in het trainingscorpus van de tokenizer (het waren Reddit-gebruikersnamen), dus kregen ze hun eigen token, maar ze waren zeldzaam of afwezig in het trainingscorpus van het model. Het resultaat is een embedding-rij die willekeurig werd geïnitialiseerd en bijna nooit is bijgewerkt. Het model heeft een symbool dat het in wezen nooit heeft gezien, en zijn gedrag daar is wat de willekeurige initialisatie toevallig opleverde.

Een tokenizer is een verliesgevende interface tussen tekst en getallen, en elk vreemd gedrag in dit hoofdstuk is die interface die doorschemert. Het is goed om helder te zijn dat de ruil bewust is: byte-level BPE betekent dat geen enkele input ooit niet weer te geven is, sequenties zijn vier tot vijf keer korter dan tekens zouden zijn, en veelvoorkomende woorden komen intact binnen.

De prijs is dat de atomen van het model niet onze atomen zijn. Het redeneert over tekst die het niet kan spellen, in eenheden gekozen door een frequentietelling over een corpus dat het niet heeft gezien, met kosten per taal waar niemand over heeft onderhandeld.

Je hebt nu een sequentie van gehele getallen. Dat is het inputformaat voor alles in de rest van Deel II.

Wat je niet hebt, is een reden waarom het ene gehele getal op het andere zou volgen. Het volgende hoofdstuk introduceert de objective waarop elk taalmodel wordt getraind, en die is verrassend simpel: gegeven de tokens tot nu toe, voorspel de volgende. Die ene objective — geen labels, geen annotatie, alleen tekst met zijn eigen toekomst als target — is wat het hele internet in trainingsdata verandert, en daar komen de eerste echte representaties van het model vandaan.

Daarvoor moet ook de kettingregel van probability uit Hoofdstuk 2 exact kloppen, want de bewering dat één token tegelijk voorspellen hetzelfde is als hele documenten modelleren is een factorisatie, geen metafoor.

Hoofdstuk 8 gaat over de autoregressieve objective, embeddings, en de eerste plek waar een model iets leert dat niemand erin heeft gestopt.

Kudo, T. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (arXiv:1804.10959) introduceert het Unigram-model; Kudo en Richardson, SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing (arXiv:1808.06226) is de implementatie die de meeste meertalige modellen gebruiken; Schuster en Nakajima, Japanese and Korean Voice Search (ICASSP 2012) is de oorsprong van WordPiece. Andrej Karpathy’s Let’s build the GPT Tokenizer en de bijbehorende karpathy/minbpe repository zijn de directe voorouders van de code in dit hoofdstuk en gaan aanzienlijk verder, inclusief de GPT-4-regex en special-token-afhandeling. Hoofdstuk 6 van de Hugging Face LLM Course behandelt de drie algoritmen naast elkaar met uitgewerkte voorbeelden.