Собираем BPE-tokenizer: почему модель не может посчитать буквы R

Есть два очевидных способа подать текст в сеть, и оба ломаются по причинам, которые важно понять, потому что именно эта поломка задаёт форму решения.

Слова. Разбить по пробелам, присвоить каждому слову число. В английском сотни тысяч словоформ, и модели нужна строка embedding для каждой, поэтому словарь — и выходной слой, который должен выдавать оценку для каждой записи, — становится огромным. Хуже то, что происходит на inference: у слова, которого модель никогда не видела при обучении, нет числа. Это проблема out-of-vocabulary, и обычная заплатка — отображать всё неизвестное в один token <UNK>, что просто выбрасывает информацию. Кроме того, «слово» — не строго определённое понятие: в китайском и японском между словами не ставят пробелы, а немецкий может бесконечно сцеплять одно существительное с другим.

Символы. Нет проблемы out-of-vocabulary, а словарь состоит примерно из сотни с небольшим символов. Но последовательности становятся очень длинными, и глава 9 покажет, что стоимость attention растёт квадратично с длиной последовательности. Документ на 1000 слов — это около 5000 символов: последовательность в четыре-пять раз длиннее, чем нужно, и с квадратичной ценой. Кроме того, каждый символ сам по себе почти не несёт смысла, поэтому первые несколько слоёв тратятся на повторную сборку слов, которые tokenizer мог бы передать целиком.

Ответ находится посередине: подслова. Частые слова становятся одним token, редкие слова разбиваются на части, и ничто никогда не бывает неизвестным, потому что в основании частей лежат отдельные байты. Самое интересное в том, что разбиение никто не проектирует. Tokenizer обучается на данных того же типа, что и модель, и учится определять, какие последовательности байтов заслуживают собственного числа, считая, как часто они встречаются вместе.

Алгоритм появился в 1994 году и был алгоритмом сжатия. Philip Gage опубликовал его в C Users Journal как способ уменьшать файлы, многократно заменяя самую частую пару соседних байтов байтом, который не встречается в данных.¹ Он пролежал так двадцать два года, пока Sennrich, Haddow и Birch в 2016 году не переиспользовали его для машинного перевода, чтобы решить проблему out-of-vocabulary.² Теперь именно так читает практически каждая крупная языковая модель.

Цикл обучения — это четыре повторяющихся шага:

Вот весь 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

Запустим его на 151 191 байте английской прозы и выведем первые двенадцать merges по мере их появления. Эту часть стоит читать медленно, потому что алгоритму никто ничего не рассказывал об английском:

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)

В этом списке стоит отметить три вещи.

Merge 12 — это слово «the»: с пробелом перед ним и пробелом после него, как единая единица, найденная на двенадцатой итерации цикла, который считает пары. Никто не дал алгоритму словарь. Оно там потому, что эти пять байтов в английском встречаются вместе чаще любых других пяти.

Merge 3 — это вообще не текст. \xe2\x80 — первые два байта UTF-8-кодировки типографской пунктуации: длинного тире, фигурных кавычек. Алгоритм понятия не имеет, что существует UTF-8, но он только что заново открыл часть его структуры, потому что многобайтовые кодировки по построению являются последовательностями байтов, которые всегда появляются вместе.

Большинство ранних merges включают пробел, и пробел обычно стоит слева. Это источник одного из самых сбивающих с толку поведений на практике; к нему мы скоро вернёмся.

Каждый merge делает последовательность короче, а словарь — больше. Насколько далеко стоит заходить, — реальное решение, и его можно измерить. Вот результаты на тех же 151 191 байте:

Убывающая отдача видна сразу. Удвоение с 512 до 1024 даёт 0,78 байта на token; удвоение с 2048 до 4096 даёт 1,07 — здесь лучше только потому, что корпус достаточно мал и более длинные merges всё ещё окупаются. На настоящем корпусе кривая резко выравнивается.

И цена большего словаря — это не только память. Каждому token нужна строка embedding, а ещё дороже то, что выходной слой модели должен выдавать оценку для каждой записи словаря на каждом шаге, так что финальное матричное умножение масштабируется с размером словаря. Реальные модели находятся между 32 000 и 200 000: GPT-2 использовала 50 257, cl100k в GPT-4 использует 100 277, o200k в GPT-4o примерно удваивает это число. Тренд идёт вверх, и причина — в следующем разделе.

Вот тот же абзац, переведённый и измеренный настоящими tokenizers, которые поставляет OpenAI:

То же содержание, тот же смысл, и с cl100k русская версия потребляет в два с половиной раза больше tokens. Поскольку API тарифицируются по token, а context windows измеряются в tokens, это не лингвистическое любопытство: это строка в бюджете, более короткое эффективное context window и более медленный ответ — всё сразу — для всех, кто работает не на английском.

Механизм — в обучающих данных. Tokenizer, обученный в основном на английском, тратит свой бюджет merges на английские байтовые последовательности. Испанский использует латиницу, поэтому всё ещё получает часть выгоды; русский почти не получает, потому что кириллические символы занимают два байта в UTF-8, и лишь немногие из этих пар были достаточно частыми в обучающем корпусе, чтобы заслужить merge. С японским ещё хуже: три байта на символ, и 72 символа превращаются в 79 tokens — tokens больше, чем символов.

Столбец o200k показывает, что это решаемая проблема и что её решают. Удвоение словаря и перебалансировка обучающих данных снижают надбавку для испанского с +39 % до +16 %, а для русского — с +152 % до +39 %. Вот настоящая причина, по которой словари продолжают расти: не сжатие ради сжатия, а то, что предыдущее поколение незаметно брало с большой части мира дополнительную плату.

Обучение произвело упорядоченный список merges. Кодирование нового текста воспроизводит его — и должно воспроизводить в том же порядке, потому что merge 12 объединяет результаты merges 5 и 1. Примените их в другом порядке, и получите другую, неправильную tokenization, которая не совпадёт ни с чем из того, что модель видела при обучении.

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

Декодирование по сравнению с этим тривиально: найти байты каждого id, склеить, декодировать как UTF-8. Обратите внимание на errors="replace": модель может выдать последовательность tokens, которая заканчивается посередине символа, и это не гипотетика — именно так бывает, когда streaming-ответ обрывается в середине emoji. Поэтому streaming API буферизуют частичные байты, а не декодируют token за token.

Round-trip работает на чём угодно — это обещание 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

Когда механизм понятен, набор на вид несвязанных жалоб оказывается одной и той же жалобой.

Арифметика. Числа не разбиваются каким-то последовательным образом:

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

Чтобы сложить 1234 и 12345, модель сначала должна выяснить, что ['123','4'] и ['123','45'] — это числа, цифры которых выровнены определённым образом, причём выравнивание отличается для каждой пары чисел. Цифры числа не находятся в одних и тех же местах от одного числа к другому. Некоторые новые tokenizers специально заставляют цифры разбиваться на согласованные группы по три, чтобы убрать это препятствие, и модели, обученные с ними, измеримо лучше справляются с арифметикой.

Отступы в Python.

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

Четыре пробела и восемь пробелов — это разные одиночные tokens, а tab слит с символом после него. Отступы, которые в Python являются синтаксисом, представлены непоследовательно — это во многом объясняет, почему модели раньше генерировали Python с едва заметно неправильными отступами и почему ориентированные на код tokenizers добавляют явные tokens для частых последовательностей отступов.

Правописание и обращение строки. Та же причина, что и при подсчёте букв r: попросить модель обратить strawberry — значит попросить её переставить буквы внутри трёх непрозрачных ids. Модели делают это за счёт запомненных при обучении написаний, а не за счёт взгляда на буквы, поэтому хорошо справляются с частыми словами и плохо — с редкими.

Glitch tokens. Самый яркий случай — SolidGoldMagikarp и набор похожих строк, которые заставляли GPT-2 и GPT-3 вести себя странно: отказываться их повторять, выдавать несвязанный вывод, иногда оскорблять пользователя. Объяснение прозаично и напрямую следует из того, что tokenizer обучается отдельно от модели: эти строки были частыми в обучающем корпусе tokenizer (это были имена пользователей Reddit), поэтому получили собственный token, но были редкими или отсутствовали в обучающем корпусе модели. В результате появилась строка embedding, которая была инициализирована случайно и почти никогда не обновлялась. У модели есть символ, который она фактически никогда не видела, и её поведение там — какое уж получилось из случайной инициализации.

Tokenizer — это интерфейс с потерями между текстом и числами, и каждое странное поведение в этой главе — это проявление интерфейса наружу. Важно ясно понимать, что компромисс выбран сознательно: byte-level BPE означает, что не существует непредставимого ввода, последовательности в четыре-пять раз короче, чем были бы символы, а частые слова поступают целиком.

Цена в том, что атомы модели — не наши атомы. Она рассуждает о тексте, который не может написать по буквам, в единицах, выбранных частотным подсчётом по корпусу, которого она не видела, и с ценой по языкам, о которой никто не договаривался.

Теперь у вас есть последовательность целых чисел. Это входной формат для всего остального в части II.

Чего у вас нет — так это причины, по которой одно целое число должно следовать за другим. Следующая глава вводит цель, на которой обучается каждая языковая модель, и она удивительно проста: имея tokens на данный момент, предсказать следующий. Одна эта цель — без labels, без разметки, просто текст с его собственным будущим в качестве target — превращает весь интернет в обучающие данные, и именно из неё появляются первые настоящие представления модели.

Ещё для этого нужно, чтобы chain rule вероятности из главы 2 была абсолютно точной, потому что утверждение, что предсказание одного token за раз эквивалентно моделированию целых документов, — это факторизация, а не метафора.

Глава 8 — это autoregressive objective, embeddings и первое место, где модель учится чему-то, чего туда никто не закладывал.

Kudo, T. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (arXiv:1804.10959) вводит модель Unigram; Kudo and Richardson, SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing (arXiv:1808.06226) — реализация, которую использует большинство мультиязычных моделей; Schuster and Nakajima, Japanese and Korean Voice Search (ICASSP 2012) — источник WordPiece. Let's build the GPT Tokenizer Андрея Карпати и сопутствующий репозиторий karpathy/minbpe — прямые предки кода в этой главе; они идут значительно дальше, включая regex GPT-4 и обработку special tokens. Глава 6 курса Hugging Face LLM Course рассматривает все три алгоритма бок о бок с разобранными примерами.