Construeix un tokenitzador BPE: per què el teu model no pot comptar les erres

Hi ha dues maneres òbvies d’alimentar una xarxa amb text, i totes dues fallen per motius que val la pena entendre, perquè el fracàs defineix la forma de la solució.

Paraules. Divideix pels espais, assigna un número a cada paraula. L’anglès té centenars de milers de formes de paraula i el model necessita una fila d’embedding per a cadascuna, de manera que el vocabulari — i la capa de sortida, que ha de produir una puntuació per a cada entrada — es fa enorme. Pitjor encara és el que passa a la inferència: una paraula que el model no ha vist mai durant l’entrenament no té número. Aquest és el problema out-of-vocabulary, i el pedaç habitual és mapar tot el que és desconegut a un únic token <UNK>, cosa que llença la informació. A més, «paraula» no és un concepte ben definit: el xinès i el japonès no posen espais entre paraules, i l’alemany pot encadenar substantius indefinidament.

Caràcters. Cap problema out-of-vocabulary, i un vocabulari d’un centenar llarg de símbols. Però les seqüències es fan molt llargues, i el Capítol 9 mostrarà que el cost de l’attention creix quadràticament amb la longitud de la seqüència. Un document de 1000 paraules té al voltant de 5000 caràcters: una seqüència quatre o cinc vegades més llarga del que cal, amb un preu quadràtic. I cada caràcter aporta gairebé cap significat per si sol, de manera que les primeres capes es dediquen a reconstruir paraules que el tokenizer podria haver lliurat intactes.

La resposta és al mig: subparaules. Les paraules freqüents es converteixen en un token, les rares es divideixen en peces, i res no és mai desconegut perquè les peces acaben, en última instància, en bytes individuals. La part interessant és que ningú no dissenya el tall. El tokenizer s’entrena, amb el mateix tipus de dades que el model, i aprèn quines seqüències de bytes mereixen tenir el seu propi número comptant amb quina freqüència apareixen juntes.

L’algoritme és de 1994, i era un algoritme de compressió. Philip Gage el va publicar al C Users Journal com una manera d’encongir fitxers substituint repetidament el parell més freqüent de bytes adjacents per un byte que no apareix a les dades.¹ Va quedar allà durant vint-i-dos anys fins que Sennrich, Haddow i Birch el van reaprofitar per a la traducció automàtica el 2016 per resoldre el problema out-of-vocabulary.² Ara és, en essència, com llegeix qualsevol model de llenguatge gran.

El bucle d’entrenament són quatre passos repetits:

Aquí tens l’entrenador sencer:

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

Executa’l sobre 151.191 bytes de prosa anglesa i imprimeix les primeres dotze fusions a mesura que passen. Aquesta és la part que val la pena llegir a poc a poc, perquè ningú no ha dit res sobre anglès a l’algoritme:

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)

Hi ha tres coses d’aquesta llista que val la pena assenyalar.

La fusió 12 és la paraula «the» — amb l’espai al davant i l’espai al darrere, com una sola unitat, descoberta a la dotzena iteració d’un bucle que compta parells. Ningú no hi ha posat cap diccionari. Hi és perquè aquests cinc bytes coapareixen més que qualsevol altres cinc en anglès.

La fusió 3 no és text en absolut. \xe2\x80 són els dos primers bytes de la codificació UTF-8 de la puntuació tipogràfica: el guió llarg, les cometes corbes. L’algoritme no té ni idea que existeixi UTF-8, i acaba de redescobrir una part de la seva estructura, perquè les codificacions multibyte són, per construcció, seqüències de bytes que sempre apareixen juntes.

La majoria de les primeres fusions inclouen un espai, i l’espai sol estar a l’esquerra. Aquest és l’origen d’un dels comportaments més confusos a la pràctica, al qual tornarem d’aquí a poc.

Cada fusió fa la seqüència més curta i el vocabulari més gran. Fins on portar-ho és una decisió real, i es pot mesurar — aquí sobre els mateixos 151.191 bytes:

Rendiments decreixents, clarament. Duplicar de 512 a 1024 compra 0,78 bytes per token; duplicar de 2048 a 4096 en compra 1,07 — aquí és millor només perquè aquest corpus és prou petit perquè les fusions més llargues continuïn compensant. En un corpus real, la corba s’aplana fort.

I el cost d’un vocabulari més gran no és només memòria. Cada token necessita una fila d’embedding, i — més car encara — la capa de sortida del model ha de produir una puntuació per a cada entrada del vocabulari a cada pas, de manera que la multiplicació de matriu final escala amb la mida del vocabulari. Els models reals se situen entre 32.000 i 200.000: GPT-2 en feia servir 50.257, cl100k de GPT-4 en fa servir 100.277, i o200k de GPT-4o aproximadament ho duplica. La tendència és a l’alça, i la raó és a la secció següent.

Aquí tens el mateix paràgraf, traduït, mesurat amb els tokenizers reals que distribueix OpenAI:

El mateix contingut, el mateix significat, i amb cl100k la versió russa consumeix dues vegades i mitja els tokens. Com que les APIs cobren per token i les context windows es mesuren en tokens, això no és una curiositat lingüística: és una línia dins d’un pressupost, una context window efectiva més curta i una resposta més lenta, les tres coses alhora, per a tothom que no treballa en anglès.

El mecanisme són les dades d’entrenament. Un tokenizer entrenat sobretot en anglès gasta el seu pressupost de fusions en seqüències de bytes angleses. El castellà comparteix l’alfabet llatí, així que encara se’n beneficia una mica; el rus gairebé gens, perquè els caràcters ciríl·lics ocupen dos bytes en UTF-8 i pocs d’aquests parells eren prou comuns al corpus d’entrenament per guanyar-se una fusió. El japonès és encara pitjor: tres bytes per caràcter, i 72 caràcters es converteixen en 79 tokens — més tokens que caràcters.

La columna o200k mostra que és un problema resoluble i que s’està resolent. Duplicar el vocabulari i reequilibrar les dades d’entrenament retalla el sobrecost del castellà de +39 % a +16 %, i el del rus de +152 % a +39 %. Aquesta és la raó real per la qual els vocabularis continuen creixent: no la compressió per si mateixa, sinó el fet que la generació anterior estava cobrant en silenci un extra a una gran part del món.

L’entrenament ha produït una llista ordenada de fusions. Codificar text nou la reprodueix — i l’ha de reproduir en el mateix ordre, perquè la fusió 12 combina els resultats de les fusions 5 i 1. Aplica-les en un ordre diferent i obtindràs una tokenització diferent i incorrecta que no coincidirà amb res del que el model va veure durant l’entrenament.

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

Descodificar és trivial en comparació: busca els bytes de cada id, concatena’ls, descodifica com a UTF-8. Fixa’t en el errors="replace": un model pot emetre una seqüència de tokens que acaba a mig caràcter, i això no és una hipòtesi — és el que passa quan una resposta en streaming es talla al mig d’un emoji, i per això les APIs de streaming emmagatzemen bytes parcials en un buffer en lloc de descodificar token a token.

El viatge d’anada i tornada funciona amb qualsevol cosa, que és la promesa del BPE a nivell de byte:

'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

Un cop el mecanisme és clar, un conjunt de queixes que semblaven no tenir relació resulten ser la mateixa queixa.

Aritmètica. Els números no es divideixen de cap manera consistent:

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

Per sumar 1234 i 12345, el model primer ha d’esbrinar que ['123','4'] i ['123','45'] són números els dígits dels quals s’alineen d’una manera concreta — i l’alineació és diferent per a cada parell de números. Els dígits d’un número no són als mateixos llocs d’un número al següent. Alguns tokenizers més nous obliguen els dígits a dividir-se en grups consistents de tres precisament per eliminar aquest obstacle, i els models entrenats amb aquests tokenizers són mesurablement millors en aritmètica.

Indentació de Python.

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

Quatre espais i vuit espais són tokens individuals diferents, i una tabulació es fusiona amb el caràcter que la segueix. La indentació, que en Python és sintaxi, es representa de manera inconsistent — cosa que explica bona part de per què abans els models produïen Python amb indentació subtilment incorrecta, i per què els tokenizers enfocats a codi afegeixen tokens explícits per a seqüències d’indentació comunes.

Ortografia i inversió. La mateixa causa que comptar les r: demanar a un model que inverteixi strawberry és demanar-li que reordeni lletres dins de tres ids opacs. Els models ho fan perquè han memoritzat grafies durant l’entrenament més que no pas mirant-les, i per això ho fan bé amb paraules comunes i malament amb les rares.

Glitch tokens. El cas més cridaner és SolidGoldMagikarp i un conjunt de cadenes similars que feien que GPT-2 i GPT-3 es comportessin de manera estranya: es negaven a repetir-les, produïen sortida no relacionada, de vegades insultaven l’usuari. L’explicació és prosaica i se segueix directament del fet que el tokenizer s’entrena per separat del model: aquestes cadenes eren freqüents al corpus d’entrenament del tokenizer (eren noms d’usuari de Reddit), així que van guanyar el seu propi token, però eren rares o absents al corpus d’entrenament del model. El resultat és una fila d’embedding que es va inicialitzar aleatòriament i gairebé mai no es va actualitzar. El model té un símbol que essencialment no ha vist mai, i el seu comportament en aquest punt és el que hagi produït la inicialització aleatòria.

Un tokenizer és una interfície amb pèrdues entre text i números, i tots els comportaments estranys d’aquest capítol són la interfície fent-se visible. Val la pena deixar clar que l’intercanvi és deliberat: el BPE a nivell de byte vol dir que cap entrada no és mai irrepresentable, les seqüències són quatre o cinc vegades més curtes que si fossin caràcters, i les paraules comunes arriben intactes.

El preu és que els àtoms del model no són els nostres àtoms. Raona sobre text que no pot escriure, en unitats triades per un recompte de freqüència sobre un corpus que no va veure, amb un cost per idioma que ningú no va negociar.

Ara tens una seqüència d’enters. Aquest és el format d’entrada per a tota la resta de la Part II.

El que no tens és cap motiu perquè un enter segueixi un altre. El capítol següent introdueix l’objectiu amb què s’entrena qualsevol model de llenguatge, i és sorprenentment simple: donats els tokens fins ara, predir el següent. Aquest únic objectiu — sense etiquetes, sense anotació, només text amb el seu propi futur com a diana — és el que converteix tot internet en dades d’entrenament, i és d’on surten les primeres representacions genuïnes del model.

També exigeix que la regla de la cadena de probabilitat del Capítol 2 sigui exactament correcta, perquè l’afirmació que predir un token cada vegada és el mateix que modelar documents sencers és una factorització, no una metàfora.

El Capítol 8 tracta de l’objectiu autoregressiu, els embeddings i el primer lloc on un model aprèn alguna cosa que ningú no hi havia posat.

Kudo, T. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (arXiv:1804.10959) introdueix el model Unigram; Kudo i Richardson, SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing (arXiv:1808.06226) és la implementació que fan servir la majoria de models multilingües; Schuster i Nakajima, Japanese and Korean Voice Search (ICASSP 2012) és l’origen de WordPiece. Let's build the GPT Tokenizer d’Andrej Karpathy i el repositori karpathy/minbpe que l’acompanya són els avantpassats directes del codi d’aquest capítol i van força més enllà, incloent-hi la regex de GPT-4 i el tractament de special-token. El capítol 6 del Hugging Face LLM Course cobreix els tres algoritmes en paral·lel amb exemples resolts.