BPE-Tokenizer bauen: Warum dein Modell die R nicht zählen kann

Es gibt zwei naheliegende Arten, Text in ein Netzwerk zu geben, und beide scheitern aus Gründen, die man verstehen sollte, weil das Scheitern die Form der Lösung bestimmt.

Wörter. An Leerzeichen trennen, jedem Wort eine Zahl zuweisen. Englisch hat Hunderttausende Wortformen, und das Modell braucht für jede davon eine embedding-Zeile, also wird das Vokabular — und die Ausgabeschicht, die für jeden Eintrag einen Score erzeugen muss — riesig. Schlimmer ist, was bei der Inferenz passiert: Ein Wort, das das Modell im Training nie gesehen hat, hat keine Zahl. Das ist das Out-of-vocabulary-Problem, und der übliche Flicken besteht darin, alles Unbekannte auf einen einzigen <UNK> token abzubilden, wodurch die Information weggeworfen wird. Außerdem ist „Wort“ kein sauber definiertes Konzept: Chinesisch und Japanisch setzen keine Leerzeichen zwischen Wörter, und Deutsch hängt Substantive beliebig lange aneinander.

Zeichen. Kein Out-of-vocabulary-Problem und ein Vokabular aus gut hundert Symbolen. Aber die Sequenzen werden sehr lang, und Kapitel 9 wird zeigen, dass die Kosten von attention quadratisch mit der Sequenzlänge wachsen. Ein Dokument mit 1000 Wörtern hat ungefähr 5000 Zeichen — eine Sequenz, die vier- bis fünfmal länger ist als nötig, zu einem quadratischen Preis. Und jedes Zeichen trägt für sich fast keine Bedeutung, also verbringen die ersten Schichten ihre Zeit damit, Wörter wieder zusammenzusetzen, die der Tokenizer intakt hätte übergeben können.

Die Antwort liegt dazwischen: Subwörter. Häufige Wörter werden zu einem token, seltene Wörter werden in Stücke zerlegt, und unbekannt ist nie etwas, weil die Stücke am Ende bis auf einzelne Bytes herunterbrechen. Das Interessante ist, dass niemand die Zerlegung entwirft. Der Tokenizer wird trainiert, auf derselben Art von Daten wie das Modell, und er lernt durch Zählen, welche Byte-Sequenzen oft genug zusammen auftreten, um eine eigene Zahl zu verdienen.

Der Algorithmus stammt aus dem Jahr 1994 und war ein Kompressionsalgorithmus. Philip Gage veröffentlichte ihn im C Users Journal als Methode, Dateien zu verkleinern, indem wiederholt das häufigste Paar benachbarter Bytes durch ein Byte ersetzt wird, das in den Daten nicht vorkommt.¹ Dort blieb er zweiundzwanzig Jahre liegen, bis Sennrich, Haddow und Birch ihn 2016 für maschinelle Übersetzung umfunktionierten, um das Out-of-vocabulary-Problem zu lösen.² Heute ist das im Wesentlichen die Art, wie jedes große Sprachmodell liest.

Die Trainingsschleife besteht aus vier Schritten, die wiederholt werden:

Hier ist der gesamte 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

Lass ihn auf 151.191 Bytes englischer Prosa laufen und gib die ersten zwölf Merges aus, während sie passieren. Diesen Teil lohnt es sich langsam zu lesen, denn niemand hat dem Algorithmus irgendetwas über Englisch gesagt:

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)

Drei Dinge in dieser Liste sind erwähnenswert.

Merge 12 ist das Wort „the“ — mit dem Leerzeichen davor und dem Leerzeichen danach, als eine Einheit, entdeckt in der zwölften Iteration einer Schleife, die Paare zählt. Niemand hat ein Wörterbuch geliefert. Es ist da, weil diese fünf Bytes im Englischen häufiger zusammen auftreten als alle anderen fünf.

Merge 3 ist überhaupt kein Text. \xe2\x80 sind die ersten zwei Bytes der UTF-8-Codierung typografischer Interpunktion — Gedankenstrich, typografische Anführungszeichen. Der Algorithmus hat keine Ahnung, dass UTF-8 existiert, und hat gerade ein Stück seiner Struktur wiederentdeckt, weil Mehrbyte-Codierungen konstruktionsbedingt Sequenzen von Bytes sind, die immer zusammen auftreten.

Die meisten frühen Merges enthalten ein Leerzeichen, und das Leerzeichen steht normalerweise links. Das ist der Ursprung eines der verwirrendsten Verhaltensmuster in der Praxis, zu dem wir gleich zurückkommen.

Jeder Merge macht die Sequenz kürzer und das Vokabular größer. Wie weit man das treibt, ist eine echte Entscheidung, und sie lässt sich messen — hier auf denselben 151.191 Bytes:

Abnehmende Grenzerträge, deutlich sichtbar. Die Verdopplung von 512 auf 1024 bringt 0,78 Bytes pro token; die Verdopplung von 2048 auf 4096 bringt 1,07 — hier nur deshalb besser, weil dieses Korpus klein genug ist, dass längere Merges sich weiter lohnen. Auf einem echten Korpus flacht die Kurve stark ab.

Und die Kosten eines größeren Vokabulars sind nicht nur Speicher. Jeder token braucht eine embedding-Zeile, und — teurer noch — die Ausgabeschicht des Modells muss für jeden Eintrag im Vokabular bei jedem Schritt einen Score erzeugen, also skaliert die finale Matrixmultiplikation mit der Vokabulargröße. Reale Modelle liegen zwischen 32.000 und 200.000: GPT-2 verwendete 50.257, GPT-4s cl100k verwendet 100.277, GPT-4os o200k verdoppelt das ungefähr. Der Trend zeigt nach oben, und der Grund steht im nächsten Abschnitt.

Hier ist derselbe Absatz, übersetzt, gemessen mit den echten Tokenizern, die OpenAI ausliefert:

Derselbe Inhalt, dieselbe Bedeutung, und mit cl100k verbraucht die russische Version zweieinhalbmal so viele token. Da APIs pro token abrechnen und context windows in token gemessen werden, ist das keine sprachliche Kuriosität — es ist gleichzeitig eine Budgetzeile, ein kürzeres effektives context window und eine langsamere Antwort, für alle, die nicht auf Englisch arbeiten.

Der Mechanismus sind die Trainingsdaten. Ein Tokenizer, der vor allem auf Englisch trainiert wurde, gibt sein Merge-Budget für englische Byte-Sequenzen aus. Spanisch teilt das lateinische Alphabet und profitiert deshalb noch etwas; Russisch bekommt fast nichts, weil kyrillische Zeichen in UTF-8 zwei Bytes brauchen und wenige dieser Paare im Trainingskorpus häufig genug waren, um einen Merge zu verdienen. Japanisch ist noch schlimmer: drei Bytes pro Zeichen, und 72 Zeichen werden zu 79 token — mehr token als Zeichen.

Die Spalte o200k zeigt, dass dieses Problem lösbar ist und gelöst wird. Eine Verdopplung des Vokabulars und eine ausgewogenere Trainingsdatenmischung senken den spanischen Overhead von +39 % auf +16 % und den russischen von +152 % auf +39 %. Das ist der wahre Grund, warum Vokabulare weiter wachsen: nicht Kompression um ihrer selbst willen, sondern die Tatsache, dass die vorherige Generation stillschweigend einem großen Teil der Welt einen Aufpreis berechnet hat.

Das Training hat eine geordnete Liste von Merges erzeugt. Encoding von neuem Text spielt sie erneut ab — und es muss sie in derselben Reihenfolge abspielen, weil Merge 12 die Ergebnisse von Merge 5 und 1 kombiniert. Wende sie in einer anderen Reihenfolge an, und du bekommst eine andere, falsche Tokenisierung, die zu nichts passt, was das Modell im Training gesehen hat.

    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 ist im Vergleich trivial: Bytes für jede id nachschlagen, verketten, als UTF-8 decodieren. Beachte das errors="replace": Ein Modell kann eine token-Sequenz ausgeben, die mitten in einem Zeichen endet, und das ist nicht hypothetisch — genau das passiert, wenn eine Streaming-Antwort mitten in einem Emoji abgeschnitten wird, weshalb Streaming-APIs partielle Bytes puffern, statt token für token zu decodieren.

Round-tripping funktioniert mit allem, und genau das ist das Versprechen von 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

Sobald der Mechanismus klar ist, stellt sich heraus, dass eine Reihe scheinbar unabhängiger Beschwerden dieselbe Beschwerde sind.

Arithmetik. Zahlen werden nicht auf irgendeine konsistente Weise gesplittet:

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

Um 1234 und 12345 zu addieren, muss das Modell zuerst herausfinden, dass ['123','4'] und ['123','45'] Zahlen sind, deren Ziffern auf eine bestimmte Weise ausgerichtet sind — und diese Ausrichtung unterscheidet sich für jedes Zahlenpaar. Die Ziffern einer Zahl liegen von einer Zahl zur nächsten nicht an denselben Stellen. Einige neuere Tokenizer erzwingen genau deshalb, dass Ziffern in konsistente Dreiergruppen gesplittet werden, um dieses Hindernis zu entfernen, und Modelle, die damit trainiert wurden, sind messbar besser in Arithmetik.

Python-Einrückung.

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

Vier Leerzeichen und acht Leerzeichen sind verschiedene einzelne token, und ein Tab ist mit dem Zeichen danach verschmolzen. Einrückung, die in Python Syntax ist, wird inkonsistent repräsentiert — das ist ein großer Teil davon, warum Modelle früher Python mit subtil falscher Einrückung erzeugten, und warum code-fokussierte Tokenizer explizite token für häufige Einrückungsläufe hinzufügen.

Rechtschreibung und Umkehren. Dieselbe Ursache wie beim Zählen der r: Ein Modell zu bitten, strawberry rückwärts zu schreiben, heißt, es zu bitten, Buchstaben innerhalb von drei undurchsichtigen ids neu anzuordnen. Modelle tun das, indem sie Schreibweisen im Training auswendig gelernt haben, nicht indem sie hinschauen — weshalb es bei häufigen Wörtern gut klappt und bei seltenen schlecht.

Glitch-token. Der auffälligste Fall ist SolidGoldMagikarp und eine Reihe ähnlicher Strings, die GPT-2 und GPT-3 zu merkwürdigem Verhalten brachten — sie weigerten sich, sie zu wiederholen, erzeugten zusammenhangslose Ausgaben oder beleidigten manchmal den Nutzer. Die Erklärung ist banal und folgt direkt daraus, dass der Tokenizer getrennt vom Modell trainiert wird: Diese Strings waren im Trainingskorpus des Tokenizers häufig (es waren Reddit-Nutzernamen), also verdienten sie ihren eigenen token, waren aber im Trainingskorpus des Modells selten oder fehlten ganz. Das Ergebnis ist eine embedding-Zeile, die zufällig initialisiert und fast nie aktualisiert wurde. Das Modell hat ein Symbol, das es im Grunde nie gesehen hat, und sein Verhalten dort ist schlicht das, was die zufällige Initialisierung ergeben hat.

Ein Tokenizer ist eine verlustbehaftete Schnittstelle zwischen Text und Zahlen, und jedes seltsame Verhalten in diesem Kapitel ist die Schnittstelle, die durchscheint. Es lohnt sich klarzustellen, dass der Trade-off absichtlich ist: byte-level BPE bedeutet, dass keine Eingabe je undarstellbar ist, Sequenzen vier- bis fünfmal kürzer sind als Zeichenfolgen wären, und häufige Wörter intakt ankommen.

Der Preis ist, dass die Atome des Modells nicht unsere Atome sind. Es schlussfolgert über Text, den es nicht buchstabieren kann, in Einheiten, die durch eine Häufigkeitszählung über ein Korpus gewählt wurden, das es nicht gesehen hat, mit Kosten pro Sprache, die niemand verhandelt hat.

Du hast jetzt eine Sequenz von Ganzzahlen. Das ist das Eingabeformat für alles im Rest von Teil II.

Was du nicht hast, ist irgendein Grund dafür, warum eine Ganzzahl auf eine andere folgen sollte. Das nächste Kapitel führt das Ziel ein, auf das jedes Sprachmodell trainiert wird, und es ist verblüffend einfach: Gegeben die bisherigen tokens, sag den nächsten voraus. Dieses eine Ziel — keine Labels, keine Annotation, nur Text mit seiner eigenen Zukunft als Target — ist es, was das gesamte Internet in Trainingsdaten verwandelt, und es ist der Ort, an dem die ersten echten Repräsentationen des Modells entstehen.

Es erfordert außerdem, dass die Kettenregel der Wahrscheinlichkeit aus Kapitel 2 exakt stimmt, denn die Behauptung, dass das Vorhersagen eines token nach dem anderen dasselbe ist wie das Modellieren ganzer Dokumente, ist eine Faktorisierung, keine Metapher.

Kapitel 8 behandelt das autoregressive Ziel, embeddings und die erste Stelle, an der ein Modell etwas lernt, das niemand hineingelegt hat.

Kudo, T. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (arXiv:1804.10959) führt das Unigram-Modell ein; Kudo und Richardson, SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing (arXiv:1808.06226) ist die Implementierung, die die meisten multilingualen Modelle verwenden; Schuster und Nakajima, Japanese and Korean Voice Search (ICASSP 2012) ist der Ursprung von WordPiece. Andrej Karpathys Let's build the GPT Tokenizer und das zugehörige karpathy/minbpe-Repository sind die direkten Vorfahren des Codes in diesem Kapitel und gehen deutlich weiter, einschließlich GPT-4-Regex und Handling von special tokens. Kapitel 6 des Hugging Face LLM Course behandelt die drei Algorithmen nebeneinander mit durchgerechneten Beispielen.