Construire un tokenizer BPE : pourquoi votre modèle ne compte pas les « r »

Il existe deux façons évidentes de fournir du texte à un réseau, et toutes deux échouent pour des raisons qu’il vaut la peine de comprendre, car cet échec définit la forme de la solution.

Les mots. Découper sur les espaces, attribuer un nombre à chaque mot. L’anglais compte des centaines de milliers de formes lexicales, et le modèle a besoin d’une ligne d’embedding pour chacune ; le vocabulaire — et la couche de sortie, qui doit produire un score pour chaque entrée — devient donc énorme. Le pire arrive à l’inférence : un mot que le modèle n’a jamais vu pendant l’entraînement n’a pas de nombre. C’est le problème du hors vocabulaire, et le correctif habituel consiste à mapper tout élément inconnu vers un unique token <UNK>, ce qui jette l’information. De plus, « mot » n’est pas un concept bien défini : le chinois et le japonais ne mettent pas d’espaces entre les mots, et l’allemand compose indéfiniment des noms les uns avec les autres.

Les caractères. Pas de problème de hors vocabulaire, et un vocabulaire d’une centaine de symboles. Mais les séquences deviennent très longues, et le chapitre 9 montrera que le coût de l’attention croît quadratiquement avec la longueur de séquence. Un document de 1000 mots compte environ 5000 caractères — une séquence quatre à cinq fois plus longue que nécessaire, pour un prix quadratique. Et chaque caractère porte très peu de sens à lui seul, si bien que les premières couches sont dépensées à réassembler des mots que le tokenizer aurait pu transmettre intacts.

La réponse se situe entre les deux : les sous-mots. Les mots fréquents deviennent un seul token, les mots rares se découpent en morceaux, et rien n’est jamais inconnu, car les morceaux descendent jusqu’aux octets individuels. Le point intéressant est que personne ne conçoit ce découpage. Le tokenizer est entraîné, sur le même type de données que le modèle, et il apprend quelles séquences d’octets méritent leur propre nombre en comptant la fréquence à laquelle elles apparaissent ensemble.

L’algorithme date de 1994, et c’était un algorithme de compression. Philip Gage l’a publié dans le C Users Journal comme une façon de réduire des fichiers en remplaçant répétitivement la paire d’octets adjacents la plus fréquente par un octet qui n’apparaît pas dans les données.¹ Il est resté là pendant vingt-deux ans, jusqu’à ce que Sennrich, Haddow et Birch le réemploient pour la traduction automatique en 2016 afin de résoudre le problème du hors vocabulaire.² C’est désormais ainsi que lisent pratiquement tous les grands modèles de langage.

La boucle d’entraînement répète quatre étapes :

Voici l’entraîneur complet :

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

Exécutez-le sur 151 191 octets de prose anglaise et affichez les douze premières fusions au moment où elles se produisent. C’est la partie qu’il vaut la peine de lire lentement, car personne n’a rien dit à l’algorithme au sujet de l’anglais :

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)

Trois éléments de cette liste méritent d’être signalés.

La fusion 12 est le mot « the » — avec l’espace avant et l’espace après, comme une seule unité, découverte à la douzième itération d’une boucle qui compte des paires. Personne n’a fourni de dictionnaire. Elle est là parce que ces cinq octets coapparaissent plus que n’importe quels cinq autres en anglais.

La fusion 3 n’est pas du texte du tout. \xe2\x80 correspond aux deux premiers octets de l’encodage UTF-8 de la ponctuation typographique — le tiret cadratin, les guillemets courbes. L’algorithme n’a aucune idée qu’UTF-8 existe, et il vient de redécouvrir une partie de sa structure, parce que les encodages multi-octets sont, par construction, des séquences d’octets qui apparaissent toujours ensemble.

La plupart des premières fusions impliquent un espace, et l’espace est généralement à gauche. C’est l’origine de l’un des comportements les plus déroutants en pratique, auquel nous revenons bientôt.

Chaque fusion rend la séquence plus courte et le vocabulaire plus grand. Jusqu’où aller est une vraie décision, et elle peut se mesurer — ici sur les mêmes 151 191 octets :

Les rendements décroissent, visiblement. Doubler de 512 à 1024 achète 0,78 octet par token ; doubler de 2048 à 4096 en achète 1,07 — mieux ici seulement parce que ce corpus est assez petit pour que les fusions plus longues continuent de rapporter. Sur un vrai corpus, la courbe s’aplatit fortement.

Et le coût d’un vocabulaire plus grand n’est pas seulement de la mémoire. Chaque token a besoin d’une ligne d’embedding, et — plus coûteux encore — la couche de sortie du modèle doit produire un score pour chaque entrée du vocabulaire à chaque étape, de sorte que la multiplication matricielle finale évolue avec la taille du vocabulaire. Les modèles réels se situent entre 32 000 et 200 000 : GPT-2 utilisait 50 257, le cl100k de GPT-4 en utilise 100 277, le o200k de GPT-4o double à peu près ce nombre. La tendance est à la hausse, et la raison se trouve dans la section suivante.

Voici le même paragraphe, traduit, mesuré avec les vrais tokenizers fournis par OpenAI :

Le même contenu, le même sens, et avec cl100k la version russe consomme deux fois et demie plus de tokens. Comme les API facturent au token et que les context windows sont mesurées en tokens, ce n’est pas une curiosité linguistique — c’est une ligne budgétaire, une context window effective plus courte, et une réponse plus lente, les trois à la fois, pour tous ceux qui ne travaillent pas en anglais.

Le mécanisme, ce sont les données d’entraînement. Un tokenizer entraîné surtout sur l’anglais dépense son budget de fusions sur des séquences d’octets anglaises. L’espagnol partage l’alphabet latin, il en tire donc encore un certain bénéfice ; le russe presque aucun, parce que les caractères cyrilliques prennent deux octets en UTF-8 et que peu de ces paires étaient assez fréquentes dans le corpus d’entraînement pour mériter une fusion. Le japonais est pire encore : trois octets par caractère, et 72 caractères deviennent 79 tokens — plus de tokens que de caractères.

La colonne o200k montre que c’est un problème soluble, et qu’il est en train d’être résolu. Doubler le vocabulaire et rééquilibrer les données d’entraînement réduit le surcoût espagnol de +39 % à +16 %, et le surcoût russe de +152 % à +39 %. C’est la vraie raison pour laquelle les vocabulaires continuent de grandir : pas la compression pour elle-même, mais le fait que la génération précédente faisait discrètement payer plus cher une grande partie du monde.

L’entraînement a produit une liste ordonnée de fusions. Encoder un nouveau texte la rejoue — et doit la rejouer dans le même ordre, parce que la fusion 12 combine les résultats des fusions 5 et 1. Appliquez-les dans un autre ordre et vous obtenez une tokenization différente, incorrecte, qui ne correspondra à rien de ce que le modèle a vu pendant l’entraînement.

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

Le décodage est trivial en comparaison : chercher les octets de chaque id, les concaténer, décoder en UTF-8. Notez le errors="replace" : un modèle peut émettre une séquence de tokens qui se termine au milieu d’un caractère, et ce n’est pas hypothétique — c’est ce qui arrive lorsqu’une réponse en streaming est coupée au milieu d’un emoji, raison pour laquelle les API de streaming mettent en tampon les octets partiels plutôt que de décoder token par token.

L’aller-retour fonctionne sur n’importe quoi, ce qui est la promesse du BPE au niveau octet :

'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

Une fois le mécanisme clair, tout un ensemble de plaintes qui semblaient sans rapport se révèlent être la même plainte.

Arithmétique. Les nombres ne sont pas découpés de manière cohérente :

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

Pour additionner 1234 et 12345, le modèle doit d’abord déterminer que ['123','4'] et ['123','45'] sont des nombres dont les chiffres s’alignent d’une certaine façon — et l’alignement diffère pour chaque paire de nombres. Les chiffres d’un nombre ne sont pas aux mêmes endroits d’un nombre à l’autre. Certains tokenizers plus récents forcent précisément les chiffres à se découper en groupes cohérents de trois afin de supprimer cet obstacle, et les modèles entraînés avec ceux-ci sont mesurablement meilleurs en arithmétique.

Indentation Python.

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

Quatre espaces et huit espaces sont des tokens uniques différents, et une tabulation est fusionnée avec le caractère qui la suit. L’indentation, qui en Python fait partie de la syntaxe, est représentée de manière incohérente — ce qui explique en grande partie pourquoi les modèles produisaient autrefois du Python avec une indentation subtilement incorrecte, et pourquoi les tokenizers centrés sur le code ajoutent des tokens explicites pour les suites d’indentation courantes.

Orthographe et inversion. Même cause que pour le comptage des r : demander à un modèle d’inverser strawberry, c’est lui demander de réordonner des lettres à l’intérieur de trois ids opaques. Les modèles y parviennent parce qu’ils ont mémorisé des orthographes pendant l’entraînement plutôt qu’en regardant, ce qui explique qu’ils réussissent bien avec les mots fréquents et mal avec les mots rares.

Glitch tokens. Le cas le plus frappant est SolidGoldMagikarp et un ensemble de chaînes similaires qui faisaient se comporter GPT-2 et GPT-3 de manière bizarre — refus de les répéter, production de sorties sans rapport, parfois insultes envers l’utilisateur. L’explication est banale et découle directement du fait que le tokenizer est entraîné séparément du modèle : ces chaînes étaient fréquentes dans le corpus d’entraînement du tokenizer (c’étaient des noms d’utilisateur Reddit), elles ont donc obtenu leur propre token, mais elles étaient rares ou absentes du corpus d’entraînement du modèle. Le résultat est une ligne d’embedding initialisée aléatoirement et presque jamais mise à jour. Le modèle possède un symbole qu’il n’a pour ainsi dire jamais vu, et son comportement à cet endroit dépend de ce qu’a produit l’initialisation aléatoire.

Un tokenizer est une interface avec perte entre le texte et les nombres, et chaque comportement étrange de ce chapitre montre l’interface à l’œuvre. Il faut être clair : le compromis est délibéré. Le BPE au niveau octet signifie qu’aucune entrée n’est jamais irréprésentable, que les séquences sont quatre à cinq fois plus courtes qu’elles ne le seraient avec des caractères, et que les mots fréquents arrivent intacts.

Le prix, c’est que les atomes du modèle ne sont pas nos atomes. Il raisonne sur du texte qu’il ne peut pas épeler, dans des unités choisies par un comptage de fréquences sur un corpus qu’il n’a pas vu, avec un coût par langue que personne n’a négocié.

Vous avez maintenant une séquence d’entiers. C’est le format d’entrée de tout le reste de la partie II.

Ce que vous n’avez pas, c’est une raison pour qu’un entier en suive un autre. Le chapitre suivant introduit l’objectif sur lequel chaque modèle de langage est entraîné, et il est étonnamment simple : étant donné les tokens jusqu’ici, prédire le suivant. Cet objectif unique — pas de labels, pas d’annotation, seulement du texte avec son propre futur comme cible — est ce qui transforme l’internet entier en données d’entraînement, et c’est là que naissent les premières véritables représentations du modèle.

Il exige aussi que la règle de la chaîne des probabilités du chapitre 2 soit exactement correcte, parce que l’affirmation selon laquelle prédire un token à la fois revient à modéliser des documents entiers est une factorisation, pas une métaphore.

Le chapitre 8 porte sur l’objectif autorégressif, les embeddings, et le premier endroit où un modèle apprend quelque chose que personne n’y a mis.

Kudo, T. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (arXiv:1804.10959) introduit le modèle Unigram ; Kudo et Richardson, SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing (arXiv:1808.06226) est l’implémentation qu’utilisent la plupart des modèles multilingues ; Schuster et Nakajima, Japanese and Korean Voice Search (ICASSP 2012) est l’origine de WordPiece. Let’s build the GPT Tokenizer d’Andrej Karpathy et le dépôt karpathy/minbpe qui l’accompagne sont les ancêtres directs du code de ce chapitre et vont beaucoup plus loin, notamment avec la regex de GPT-4 et la gestion des special tokens. Le chapitre 6 du cours LLM de Hugging Face couvre les trois algorithmes côte à côte avec des exemples détaillés.