Byg en BPE-tokenizer: Derfor kan din model ikke tælle r'erne

Der er to oplagte måder at give tekst til et netværk på, og begge fejler af grunde, der er værd at forstå, fordi fejlen definerer løsningens form.

Ord. Del på mellemrum, og giv hvert ord et tal. Engelsk har hundredtusindvis af ordformer, og modellen har brug for en embedding-række til hver, så ordforrådet — og outputlaget, som skal producere en score for hvert opslag — bliver enormt. Værre er det, der sker ved inference: et ord, modellen aldrig så under træning, har intet tal. Det er out-of-vocabulary-problemet, og den normale lappeløsning er at mappe alt ukendt til én enkelt <UNK> token, hvilket smider informationen væk. Desuden er »ord« ikke et veldefineret begreb: Kinesisk og japansk sætter ikke mellemrum mellem ord, og tysk kan sammensætte ét substantiv med et andet i det uendelige.

Tegn. Intet out-of-vocabulary-problem og et ordforråd på omkring hundrede symboler. Men sekvenserne bliver meget lange, og kapitel 9 viser, at attention-omkostningen vokser kvadratisk med sekvenslængden. Et dokument på 1000 ord er omkring 5000 tegn — en sekvens fire til fem gange længere, end den behøver at være, til en kvadratisk pris. Og hvert tegn bærer næsten ingen betydning alene, så de første par lag bliver brugt på at samle ord igen, som tokenizer kunne have afleveret intakte.

Svaret ligger imellem dem: subwords. Almindelige ord bliver til én token, sjældne ord deles i stykker, og intet er nogensinde ukendt, fordi stykkerne til sidst ender ved individuelle bytes. Det interessante er, at ingen designer opdelingen. Tokenizer trænes på samme slags data som modellen, og den lærer, hvilke bytesekvenser der fortjener deres eget tal, ved at tælle hvor ofte de optræder sammen.

Algoritmen er fra 1994, og den var en komprimeringsalgoritme. Philip Gage udgav den i C Users Journal som en måde at gøre filer mindre på ved gentagne gange at erstatte det hyppigste par af tilstødende bytes med en byte, der ikke forekommer i dataene.¹ Den lå der i toogtyve år, indtil Sennrich, Haddow og Birch i 2016 genbrugte den til maskinoversættelse for at løse out-of-vocabulary-problemet.² Det er nu sådan, stort set alle store sprogmodeller læser.

Træningsløkken er fire trin, der gentages:

Her er hele træneren:

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

Kør den på 151.191 bytes engelsk prosa, og udskriv de første tolv merges, efterhånden som de sker. Det er den del, der er værd at læse langsomt, fordi ingen har fortalt algoritmen noget om engelsk:

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)

Tre ting i den liste er værd at pege på.

Merge 12 er ordet »the« — med mellemrummet før og mellemrummet efter, som én samlet enhed, opdaget i den tolvte iteration af en løkke, der tæller par. Ingen leverede en ordbog. Det er der, fordi de fem bytes forekommer sammen oftere end nogen andre fem på engelsk.

Merge 3 er slet ikke tekst. \xe2\x80 er de første to bytes i UTF-8-kodningen af typografisk tegnsætning — tankestregen, de krøllede anførselstegn. Algoritmen aner ikke, at UTF-8 findes, og den har netop genopdaget et stykke af dets struktur, fordi multibyte-kodninger per konstruktion er sekvenser af bytes, der altid optræder sammen.

De fleste tidlige merges involverer et mellemrum, og mellemrummet står normalt til venstre. Det er oprindelsen til en af de mest forvirrende adfærdstyper i praksis, som vi vender tilbage til om lidt.

Hver merge gør sekvensen kortere og ordforrådet større. Hvor langt man skal presse det, er en reel beslutning, og den kan måles — her på de samme 151.191 bytes:

Aftagende udbytte, helt synligt. En fordobling fra 512 til 1024 køber 0,78 bytes pr. token; en fordobling fra 2048 til 4096 køber 1,07 — bedre her kun fordi dette corpus er lille nok til, at længere merges stadig betaler sig. På et rigtigt corpus flader kurven kraftigt ud.

Og omkostningen ved et større ordforråd er ikke kun hukommelse. Hver token har brug for en embedding-række, og — dyrere endnu — modellens outputlag skal producere en score for hvert opslag i ordforrådet ved hvert trin, så den sidste matrixmultiplikation skalerer med ordforrådsstørrelsen. Rigtige modeller ligger mellem 32.000 og 200.000: GPT-2 brugte 50.257, GPT-4's cl100k bruger 100.277, GPT-4o's o200k omtrent fordobler det. Tendensen går opad, og årsagen er i næste afsnit.

Her er det samme afsnit, oversat og målt med de rigtige tokenizers, som OpenAI leverer:

Samme indhold, samme betydning, og med cl100k bruger den russiske version to en halv gange så mange tokens. Da API'er fakturerer pr. token, og context windows måles i tokens, er det ikke en sproglig kuriositet — det er en post i et budget, et kortere effektivt context window og et langsommere svar, alle tre på én gang, for alle der ikke arbejder på engelsk.

Mekanismen er træningsdataene. En tokenizer, der primært er trænet på engelsk, bruger sit merge-budget på engelske bytesekvenser. Spansk deler det latinske alfabet, så det får stadig noget ud af det; russisk får næsten intet, fordi kyrilliske tegn fylder to bytes i UTF-8, og få af de par var almindelige nok i træningscorpusset til at fortjene en merge. Japansk er endnu værre: tre bytes pr. tegn, og 72 tegn bliver til 79 tokens — flere tokens end tegn.

Kolonnen o200k viser, at det er et løsbart problem, og at det er ved at blive løst. En fordobling af ordforrådet og en genbalancering af træningsdataene sænker den spanske overhead fra +39 % til +16 %, og den russiske fra +152 % til +39 %. Det er den egentlige grund til, at ordforråd bliver ved med at vokse: ikke komprimering for komprimeringens skyld, men det faktum, at den forrige generation stille og roligt opkrævede ekstra betaling fra en stor del af verden.

Træningen producerede en ordnet liste af merges. Encoding af ny tekst afspiller den — og den skal afspille den i samme rækkefølge, fordi merge 12 kombinerer resultaterne af merge 5 og 1. Anvend dem i en anden rækkefølge, og du får en anden, forkert tokenization, som ikke matcher noget, modellen så under træning.

    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 er trivielt til sammenligning: slå hver id's bytes op, sammenkæd dem, decode som UTF-8. Bemærk errors="replace": en model kan udsende en token-sekvens, der slutter midt i et tegn, og det er ikke hypotetisk — det er det, der sker, når et streaming-svar bliver afbrudt midt i en emoji, og derfor buffer streaming-API'er delvise bytes i stedet for at decode token for token.

Round-tripping virker på alt, hvilket er løftet i 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

Når mekanismen er klar, viser en række klager, der ellers ligner noget forskelligt, sig at være den samme klage.

Aritmetik. Tal deles ikke på nogen konsistent måde:

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']

For at lægge 1234 og 12345 sammen skal modellen først finde ud af, at ['123','4'] og ['123','45'] er tal, hvis cifre flugter på en bestemt måde — og flugten er forskellig for hvert talpar. Cifrene i et tal er ikke de samme steder fra det ene tal til det næste. Nogle nyere tokenizers tvinger cifre til at blive delt i konsistente grupper på tre netop for at fjerne denne forhindring, og modeller trænet med dem er målbart bedre til aritmetik.

Python-indrykning.

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

Fire mellemrum og otte mellemrum er forskellige enkelte tokens, og en tab er fusioneret med tegnet efter den. Indrykning, som i Python er syntaks, repræsenteres inkonsistent — hvilket er en stor del af grunden til, at modeller tidligere producerede Python med subtilt forkert indrykning, og hvorfor kodefokuserede tokenizers tilføjer eksplicitte tokens for almindelige indrykningsruns.

Stavning og omvendt rækkefølge. Samme årsag som ved at tælle r'erne: at bede en model om at vende strawberry om er at bede den om at omarrangere bogstaver inde i tre uigennemsigtige ids. Modeller gør det ved at have memoriseret stavemåder under træning i stedet for ved at kigge, og derfor gør de det godt for almindelige ord og dårligt for sjældne.

Glitch tokens. Det mest slående tilfælde er SolidGoldMagikarp og en række lignende strenge, der fik GPT-2 og GPT-3 til at opføre sig bizart — nægte at gentage dem, producere urelateret output, nogle gange fornærme brugeren. Forklaringen er jordnær og følger direkte af, at tokenizer trænes separat fra modellen: de strenge var hyppige i tokenizerens træningscorpus (de var Reddit-brugernavne), så de fortjente deres egen token, men de var sjældne eller fraværende i modellens træningscorpus. Resultatet er en embedding-række, der blev initialiseret tilfældigt og næsten aldrig opdateret. Modellen har et symbol, den i praksis aldrig har set, og dens adfærd dér er, hvad den tilfældige initialisering nu engang blev til.

En tokenizer er en lossy grænseflade mellem tekst og tal, og hver mærkelig adfærd i dette kapitel er grænsefladen, der skinner igennem. Det er værd at være tydelig om, at byttet er bevidst: byte-level BPE betyder, at intet input nogensinde er umuligt at repræsentere, sekvenser er fire til fem gange kortere, end tegn ville være, og almindelige ord ankommer intakte.

Prisen er, at modellens atomer ikke er vores atomer. Den ræsonnerer om tekst, den ikke kan stave, i enheder valgt af en frekvensoptælling over et corpus, den ikke så, med en omkostning pr. sprog, som ingen forhandlede.

Du har nu en sekvens af heltal. Det er inputformatet for alt i resten af del II.

Det, du ikke har, er nogen grund til, at ét heltal skulle følge et andet. Næste kapitel introducerer det mål, enhver sprogmodel trænes på, og det er forbløffende enkelt: Givet de hidtidige tokens, forudsig den næste. Det ene mål — ingen labels, ingen annotation, bare tekst med sin egen fremtid som target — er det, der gør hele internettet til træningsdata, og det er der, modellens første ægte repræsentationer kommer fra.

Det kræver også, at kædereglen for sandsynlighed fra kapitel 2 er helt rigtig, fordi påstanden om, at det at forudsige én token ad gangen er det samme som at modellere hele dokumenter, er en faktorisering, ikke en metafor.

Kapitel 8 er det autoregressive mål, embeddings og det første sted, hvor en model lærer noget, ingen har lagt ind.

Kudo, T. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (arXiv:1804.10959) introducerer Unigram-modellen; Kudo og Richardson, SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing (arXiv:1808.06226) er den implementering, de fleste flersprogede modeller bruger; Schuster og Nakajima, Japanese and Korean Voice Search (ICASSP 2012) er oprindelsen til WordPiece. Andrej Karpathys Let's build the GPT Tokenizer og det tilhørende karpathy/minbpe repository er de direkte forfædre til koden i dette kapitel og går betydeligt længere, inklusive GPT-4-regexen og håndtering af special-token. Kapitel 6 i Hugging Face LLM Course gennemgår de tre algoritmer side om side med gennemarbejdede eksempler.