Építs BPE tokenizert: miért nem tudja a model megszámolni az r-eket?

Két kézenfekvő módja van annak, hogy szöveget adjunk egy hálózatnak, és mindkettő olyan okból bukik el, amelyet érdemes megérteni, mert maga a kudarc rajzolja ki a megoldás formáját.

Szavak. Daraboljunk szóközök mentén, rendeljünk minden szóhoz egy számot. Az angolban több százezer szóalak van, és a modelnek mindegyikhez kell egy embedding sor, így a szótár — és a kimeneti réteg, amelynek minden bejegyzéshez pontszámot kell adnia — óriásira nő. Még rosszabb, ami inference közben történik: egy olyan szónak, amelyet a model a training során sosem látott, nincs száma. Ez az out-of-vocabulary probléma, a szokásos toldozás pedig az, hogy minden ismeretlent egyetlen <UNK> tokenre képezünk le, ami eldobja az információt. Ráadásul a „szó” nem jól definiált fogalom: a kínai és a japán nem tesz szóközt a szavak közé, a német pedig főneveket kapcsol egymás után elvileg korlátlanul.

Karakterek. Nincs out-of-vocabulary probléma, a szótár pedig nagyjából száz jelből áll. Csakhogy a sorozatok nagyon hosszúvá válnak, és a 9. fejezet megmutatja majd, hogy az attention költsége négyzetesen nő a sorozathosszal. Egy 1000 szavas dokumentum körülbelül 5000 karakter — négyszer-ötször hosszabb sorozat, mint amekkorára szükség lenne, ráadásul négyzetes áron. És minden egyes karakter önmagában szinte semmilyen jelentést nem hordoz, ezért az első néhány réteg arra megy el, hogy újra összerakja azokat a szavakat, amelyeket a tokenizer eleve egészben is átadhatott volna.

A válasz a kettő között van: subwordök. A gyakori szavak egyetlen tokenné válnak, a ritka szavak darabokra esnek, és soha semmi nem ismeretlen, mert a darabok végül egyedi byte-okig vezetnek vissza. Az érdekes rész az, hogy senki nem tervezi meg a felosztást. A tokenizer trainingen megy keresztül, ugyanolyan típusú adaton, mint a model, és úgy tanulja meg, mely byte-sorozatok érdemelnek saját számot, hogy megszámolja, milyen gyakran fordulnak elő együtt.

Az algoritmus 1994-ből származik, és eredetileg tömörítési algoritmus volt. Philip Gage a C Users Journal hasábjain publikálta, mint módszert fájlok zsugorítására: ismételten lecserélte a leggyakoribb szomszédos byte-párt egy olyan byte-ra, amely nem fordul elő az adatban.¹ Huszonkét évig ott pihent, amíg Sennrich, Haddow és Birch 2016-ban újra nem használta gépi fordításhoz, az out-of-vocabulary probléma megoldására.² Lényegében ma minden nagy nyelvi model így olvas.

A training loop négy ismétlődő lépésből áll:

Íme a teljes 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

Futtasd 151.191 byte angol prózán, és nyomtasd ki az első tizenkét merge-et, ahogy megtörténnek. Ezt a részt érdemes lassan olvasni, mert senki nem mondott semmit az algoritmusnak az angolról:

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)

Három dologra érdemes rámutatni ebben a listában.

A 12. merge a „the” szó — előtte és utána szóközzel, egyetlen egységként, egy párokat számoló loop tizenkettedik iterációjában felfedezve. Senki nem adott neki szótárt. Azért van ott, mert ez az öt byte gyakrabban fordul elő együtt, mint bármely másik öt az angolban.

A 3. merge egyáltalán nem szöveg. A \xe2\x80 a tipográfiai írásjelek UTF-8 kódolásának első két byte-ja — a gondolatjelé, a dőlt idézőjeleké. Az algoritmusnak fogalma sincs, hogy létezik UTF-8, mégis újra felfedezte a szerkezetének egy darabját, mert a több byte-os kódolások definíció szerint olyan byte-sorozatok, amelyek mindig együtt jelennek meg.

A korai merge-ek többsége szóközt tartalmaz, és a szóköz általában a bal oldalon van. Innen ered az egyik legzavaróbb gyakorlati viselkedés, amelyhez rövidesen visszatérünk.

Minden merge rövidebbé teszi a sorozatot és nagyobbá a szótárt. Valódi döntés, meddig érdemes tolni, és mérhető is — itt ugyanazon a 151.191 byte-on:

Jól látható a csökkenő hozadék. Az 512-ről 1024-re duplázás 0,78 byte-ot vesz tokenenként; a 2048-ról 4096-ra duplázás 1,07-et — itt azért jobb, mert ez a corpus elég kicsi ahhoz, hogy a hosszabb merge-ek továbbra is megtérüljenek. Valódi corpuson a görbe keményen ellaposodik.

A nagyobb szótár költsége pedig nem csak memória. Minden tokenhez kell egy embedding sor, és — ami drágább — a model kimeneti rétegének a szótár minden bejegyzéséhez minden lépésben pontszámot kell előállítania, ezért a végső mátrixszorzás a szótármérettel skálázódik. A valódi modellek 32.000 és 200.000 között járnak: a GPT-2 50.257-et használt, a GPT-4 cl100k 100.277-et, a GPT-4o o200k nagyjából ennek a dupláját. A trend felfelé tart, az ok pedig a következő szakaszban van.

Íme ugyanaz a bekezdés lefordítva, az OpenAI által ténylegesen szállított tokenizerekkel mérve:

Ugyanaz a tartalom, ugyanaz a jelentés, és a cl100k mellett az orosz verzió két és félszer annyi tokent fogyaszt. Mivel az API-k token alapján számláznak, a context window pedig tokenben van mérve, ez nem nyelvészeti érdekesség — hanem költségvetési sor, rövidebb effektív context window és lassabb válasz egyszerre, mindenkinek, aki nem angolul dolgozik.

A mechanizmus a training adat. Egy főként angolon trainingelt tokenizer a merge-keretét angol byte-sorozatokra költi. A spanyol osztozik a latin ábécén, ezért még kap némi előnyt; az orosz szinte semmit, mert a cirill karakterek két byte-ot foglalnak UTF-8-ban, és ezek közül kevés pár volt elég gyakori a training corpusban ahhoz, hogy merge-et érdemeljen. A japán még rosszabb: karakterenként három byte, és 72 karakterből 79 token lesz — több token, mint karakter.

A o200k oszlop azt mutatja, hogy ez megoldható probléma, és éppen meg is oldják. A szótár megduplázása és a training adatok újraegyensúlyozása a spanyol többletet +39 %-ról +16 %-ra, az oroszt +152 %-ról +39 %-ra vágja. Ez az igazi oka annak, hogy a szótárak folyamatosan nőnek: nem az önmagáért való tömörítés, hanem az, hogy az előző generáció csendben a világ nagy részével felárat fizettetett.

A training egy rendezett merge-listát állított elő. Új szöveg kódolásakor ezt játsszuk vissza — és ugyanabban a sorrendben kell visszajátszani, mert a 12. merge az 5. és az 1. merge eredményét kombinálja. Más sorrendben alkalmazva más, hibás tokenizációt kapsz, amely nem fog egyezni semmivel, amit a model training közben látott.

    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")

A dekódolás ehhez képest triviális: keresd ki minden id byte-jait, fűzd össze őket, dekódold UTF-8-ként. Figyeld meg a errors="replace" részt: egy model kibocsáthat olyan token-sorozatot, amely egy karakter közepén ér véget, és ez nem hipotetikus — pontosan ez történik, amikor egy streaming válasz egy emoji közepén szakad meg, ezért pufferelik a streaming API-k a részleges byte-okat ahelyett, hogy tokenenként dekódolnának.

A round-trip bármin működik, és ez a byte-level BPE ígérete:

'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

Amint a mechanizmus világos, egy sor egymástól függetlennek tűnő panaszról kiderül, hogy ugyanaz a panasz.

Aritmetika. A számok semmilyen konzisztens módon nincsenek felosztva:

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

A 1234 és a 12345 összeadásához a modelnek előbb ki kell találnia, hogy a ['123','4'] és a ['123','45'] olyan számok, amelyek számjegyei egy adott módon igazodnak — és az igazodás minden számpárnál más. Egy szám számjegyei nem ugyanott vannak egyik számtól a következőig. Néhány újabb tokenizer éppen ezért kényszeríti a számjegyeket konzisztens hármas csoportokra, hogy eltávolítsa ezt az akadályt, és az ilyeneken trainingelt modellek mérhetően jobbak aritmetikában.

Python behúzás.

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

Négy szóköz és nyolc szóköz különböző egyedi token, a tab pedig össze van olvasztva az utána következő karakterrel. A behúzás, amely Pythonban szintaxis, inkonzisztensen van reprezentálva — nagyrészt ezért fordult elő régen, hogy a modellek finoman hibás behúzású Pythont állítottak elő, és ezért adnak a kódra fókuszáló tokenizerek explicit tokeneket a gyakori behúzássorozatokhoz.

Betűzés és visszafelé írás. Ugyanaz az ok, mint az r-ek számolásánál: amikor arra kérsz egy modelt, hogy fordítsa meg a strawberry szót, azt kéred tőle, hogy rendezzen át betűket három átlátszatlan id-n belül. A modellek ezt úgy csinálják, hogy training során megjegyzett írásmódokra támaszkodnak, nem úgy, hogy ránéznek; ezért megy jól a gyakori szavaknál, és rosszul a ritkáknál.

Glitch tokenek. A legfeltűnőbb eset a SolidGoldMagikarp és egy sor hasonló string, amelyek miatt a GPT-2 és a GPT-3 bizarrul viselkedett — nem volt hajlandó megismételni őket, oda nem illő outputot adott, néha sértegette a felhasználót. A magyarázat prózai, és közvetlenül következik abból, hogy a tokenizert a modeltől külön trainingelik: ezek a stringek gyakoriak voltak a tokenizer training corpusában (Reddit-felhasználónevek voltak), ezért saját tokent kaptak, de ritkák vagy hiányzók voltak a model training corpusában. Az eredmény egy embedding sor, amelyet véletlenszerűen inicializáltak, és szinte soha nem frissítettek. A modelnek van egy szimbóluma, amelyet lényegében sosem látott, és a viselkedése ott olyan, amilyenre a véletlen inicializáció épp beállította.

A tokenizer veszteséges interfész szöveg és számok között, és a fejezet minden furcsa viselkedése abból fakad, hogy ez az interfész átlátszik. Érdemes világosan látni, hogy a csere szándékos: a byte-level BPE azt jelenti, hogy nincs reprezentálhatatlan input, a sorozatok négyszer-ötször rövidebbek, mint karakterekkel lennének, és a gyakori szavak egyben érkeznek.

Az ár az, hogy a model atomjai nem a mi atomjaink. Olyan szövegről következtet, amelyet nem tud kibetűzni, olyan egységekben, amelyeket egy általa nem látott corpuson végzett gyakoriságszámlálás választott ki, és nyelvenként eltérő költséggel, amelyet senki nem alkudott meg.

Most már van egy egész számokból álló sorozatod. Ez a bemeneti formátuma a II. részben következő mindennek.

Ami nincs, az bármilyen ok arra, hogy az egyik egész számot miért követné egy másik. A következő fejezet bevezeti azt az objective-et, amelyen minden nyelvi model trainingel, és amely meglepően egyszerű: az eddigi tokenek alapján jósoljuk meg a következőt. Ez az egyetlen objective — nincsenek címkék, nincs annotáció, csak szöveg, amelynek saját jövője a cél — alakítja az egész internetet training adattá, és innen származnak a model első valódi reprezentációi.

Ehhez az is kell, hogy a 2. fejezet valószínűségi láncszabálya pontosan stimmeljen, mert az az állítás, hogy egyenként tokeneket jósolni ugyanaz, mint teljes dokumentumokat modellezni, faktorizáció, nem metafora.

A 8. fejezet az autoregresszív objective-ről, az embeddingekről és az első olyan pontról szól, ahol a model megtanul valamit, amit senki nem tett bele.

Kudo, T. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (arXiv:1804.10959) vezeti be az Unigram modelt; Kudo és Richardson, SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing (arXiv:1808.06226) az az implementáció, amelyet a legtöbb többnyelvű model használ; Schuster és Nakajima, Japanese and Korean Voice Search (ICASSP 2012) a WordPiece eredete. Andrej Karpathy Let's build the GPT Tokenizer anyaga és a hozzá tartozó karpathy/minbpe repository a fejezet kódjának közvetlen elődje, és jóval tovább megy, beleértve a GPT-4 regexet és a special-token kezelést. A Hugging Face LLM Course 6. fejezete a három algoritmust egymás mellett, kidolgozott példákkal tárgyalja.