Crie um tokenizer BPE: por que seu modelo não conta os R's

Há duas maneiras óbvias de fornecer texto a uma rede, e ambas falham por motivos que vale entender, porque a falha define o formato da solução.

Palavras. Divida por espaços, atribua um número a cada palavra. O inglês tem centenas de milhares de formas de palavras, e o modelo precisa de uma linha de embedding para cada uma; então o vocabulário — e a camada de saída, que precisa produzir uma pontuação para cada entrada — fica enorme. Pior é o que acontece na inferência: uma palavra que o modelo nunca viu no treinamento não tem número. Esse é o problema de fora do vocabulário, e o remendo usual é mapear tudo que é desconhecido para um único token <UNK>, o que joga a informação fora. Além disso, “palavra” não é um conceito bem definido: chinês e japonês não colocam espaços entre palavras, e o alemão compõe um substantivo sobre outro indefinidamente.

Caracteres. Sem problema de fora do vocabulário, e um vocabulário de pouco mais de cem símbolos. Mas as sequências ficam muito longas, e o Capítulo 9 mostrará que o custo de attention cresce quadraticamente com o comprimento da sequência. Um documento de 1000 palavras tem por volta de 5000 caracteres — uma sequência quatro a cinco vezes mais longa do que precisaria ser, por um preço quadrático. E cada caractere carrega quase nenhum significado sozinho, então as primeiras camadas são gastas remontando palavras que o tokenizer poderia ter entregue intactas.

A resposta está entre os dois: subpalavras. Palavras comuns viram um token, palavras raras se dividem em partes, e nada jamais é desconhecido porque as partes chegam, no limite, a bytes individuais. A parte interessante é que ninguém desenha a divisão. O tokenizer é treinado, no mesmo tipo de dados do modelo, e aprende quais sequências de bytes merecem seu próprio número contando com que frequência ocorrem juntas.

O algoritmo é de 1994, e era um algoritmo de compressão. Philip Gage o publicou no C Users Journal como uma forma de encolher arquivos substituindo repetidamente o par mais frequente de bytes adjacentes por um byte que não ocorre nos dados.¹ Ele ficou ali por vinte e dois anos até Sennrich, Haddow e Birch o reaproveitarem para tradução automática em 2016, para resolver o problema de fora do vocabulário.² Hoje é assim que essencialmente todo grande modelo de linguagem lê.

O loop de treinamento tem quatro passos repetidos:

Aqui está o treinador inteiro:

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

Rode-o em 151.191 bytes de prosa em inglês e imprima os doze primeiros merges à medida que acontecem. Esta é a parte que vale ler devagar, porque ninguém contou nada sobre inglês ao algoritmo:

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)

Três coisas nessa lista merecem atenção.

O merge 12 é a palavra “the” — com o espaço antes e o espaço depois, como uma unidade única, descoberta na décima segunda iteração de um loop que conta pares. Ninguém forneceu um dicionário. Ela está ali porque esses cinco bytes coocorrem mais do que quaisquer outros cinco em inglês.

O merge 3 não é texto algum. \xe2\x80 são os dois primeiros bytes da codificação UTF-8 de pontuação tipográfica — o travessão, as aspas curvas. O algoritmo não faz ideia de que UTF-8 existe, e acabou de redescobrir uma parte de sua estrutura, porque codificações multibyte são, por construção, sequências de bytes que sempre aparecem juntas.

A maioria dos merges iniciais envolve um espaço, e o espaço geralmente fica à esquerda. Essa é a origem de um dos comportamentos mais confusos na prática, ao qual voltaremos em breve.

Cada merge encurta a sequência e aumenta o vocabulário. Até onde levar isso é uma decisão real, e pode ser medida — aqui nos mesmos 151.191 bytes:

Retornos decrescentes, visivelmente. Dobrar de 512 para 1024 compra 0,78 byte por token; dobrar de 2048 para 4096 compra 1,07 — melhor aqui apenas porque este corpus é pequeno o bastante para que merges mais longos continuem compensando. Em um corpus real, a curva achata forte.

E o custo de um vocabulário maior não é só memória. Cada token precisa de uma linha de embedding e — mais caro ainda — a camada de saída do modelo precisa produzir uma pontuação para cada entrada no vocabulário a cada passo, então a multiplicação de matriz final escala com o tamanho do vocabulário. Modelos reais ficam entre 32.000 e 200.000: o GPT-2 usou 50.257, o cl100k do GPT-4 usa 100.277, o o200k do GPT-4o praticamente dobra isso. A tendência é de alta, e o motivo está na próxima seção.

Aqui está o mesmo parágrafo, traduzido, medido com os tokenizers reais que a OpenAI distribui:

O mesmo conteúdo, o mesmo significado, e com cl100k a versão em russo consome duas vezes e meia mais tokens. Como APIs cobram por token e context windows são medidas em tokens, isso não é uma curiosidade linguística — é uma linha no orçamento, uma context window efetiva mais curta e uma resposta mais lenta, as três coisas de uma vez, para todo mundo que não trabalha em inglês.

O mecanismo são os dados de treinamento. Um tokenizer treinado principalmente em inglês gasta seu orçamento de merges em sequências de bytes do inglês. O espanhol compartilha o alfabeto latino, então ainda recebe algum benefício; o russo quase nenhum, porque caracteres cirílicos ocupam dois bytes em UTF-8 e poucos desses pares foram comuns o bastante no corpus de treinamento para ganhar um merge. O japonês é ainda pior: três bytes por caractere, e 72 caracteres viram 79 tokens — mais tokens do que caracteres.

A coluna o200k mostra que esse é um problema solucionável e que está sendo resolvido. Dobrar o vocabulário e reequilibrar os dados de treinamento reduz o sobrecusto do espanhol de +39 % para +16 %, e o do russo de +152 % para +39 %. Esse é o verdadeiro motivo pelo qual os vocabulários continuam crescendo: não compressão pela compressão, mas o fato de que a geração anterior cobrava silenciosamente um extra de uma grande parte do mundo.

O treinamento produziu uma lista ordenada de merges. Codificar novo texto a reproduz — e precisa reproduzi-la na mesma ordem, porque o merge 12 combina os resultados dos merges 5 e 1. Aplique-os em uma ordem diferente e você obtém uma tokenização diferente e errada, que não corresponderá a nada que o modelo viu no treinamento.

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

Decodificar é trivial em comparação: procure os bytes de cada id, concatene, decodifique como UTF-8. Observe o errors="replace": um modelo pode emitir uma sequência de tokens que termina no meio de um caractere, e isso não é hipotético — é o que acontece quando uma resposta em streaming é interrompida no meio de um emoji, por isso APIs de streaming armazenam bytes parciais em buffer em vez de decodificar token por token.

O round-trip funciona com qualquer coisa, que é a promessa do BPE em nível de bytes:

'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

Depois que o mecanismo fica claro, um conjunto de reclamações que pareciam não relacionadas se revela a mesma reclamação.

Aritmética. Números não são divididos de forma consistente:

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

Para somar 1234 e 12345, o modelo precisa primeiro descobrir que ['123','4'] e ['123','45'] são números cujos dígitos se alinham de uma forma específica — e o alinhamento difere para cada par de números. Os dígitos de um número não estão nos mesmos lugares de um número para o outro. Alguns tokenizers mais novos forçam dígitos a se dividir em grupos consistentes de três justamente para remover esse obstáculo, e modelos treinados com eles são mensuravelmente melhores em aritmética.

Indentação em Python.

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

Quatro espaços e oito espaços são tokens únicos diferentes, e uma tabulação é fundida com o caractere depois dela. A indentação, que em Python é sintaxe, é representada de forma inconsistente — o que é grande parte do motivo pelo qual modelos costumavam produzir Python com indentação sutilmente errada, e por que tokenizers focados em código adicionam tokens explícitos para sequências comuns de indentação.

Ortografia e inversão. Mesma causa da contagem dos r's: pedir a um modelo para inverter strawberry é pedir que ele reordene letras dentro de três ids opacos. Modelos fazem isso por terem memorizado grafias durante o treinamento, não por olhar, e é por isso que fazem bem com palavras comuns e mal com raras.

Glitch tokens. O caso mais marcante é SolidGoldMagikarp e um conjunto de strings parecidas que fizeram o GPT-2 e o GPT-3 se comportarem de forma bizarra — recusando-se a repeti-las, produzindo saída não relacionada, às vezes insultando o usuário. A explicação é mundana e segue diretamente do fato de que o tokenizer é treinado separadamente do modelo: essas strings eram frequentes no corpus de treinamento do tokenizer (eram nomes de usuário do Reddit), então ganharam seu próprio token, mas eram raras ou ausentes no corpus de treinamento do modelo. O resultado é uma linha de embedding que foi inicializada aleatoriamente e quase nunca atualizada. O modelo tem um símbolo que essencialmente nunca viu, e seu comportamento ali é o que quer que a inicialização aleatória tenha produzido.

Um tokenizer é uma interface com perdas entre texto e números, e todo comportamento estranho neste capítulo é a interface aparecendo. Vale deixar claro que a troca é deliberada: BPE em nível de bytes significa que nenhuma entrada é irrepresentável, as sequências são quatro a cinco vezes mais curtas do que seriam com caracteres, e palavras comuns chegam intactas.

O preço é que os átomos do modelo não são os nossos átomos. Ele raciocina sobre texto que não consegue soletrar, em unidades escolhidas por uma contagem de frequência sobre um corpus que ele não viu, com um custo por idioma que ninguém negociou.

Agora você tem uma sequência de inteiros. Esse é o formato de entrada para tudo no restante da Parte II.

O que você não tem é qualquer motivo para um inteiro seguir outro. O próximo capítulo apresenta o objetivo com que todo modelo de linguagem é treinado, e ele é surpreendentemente simples: dados os tokens até agora, prever o próximo. Esse único objetivo — sem rótulos, sem anotação, apenas texto com seu próprio futuro como alvo — é o que transforma a internet inteira em dados de treinamento, e é de onde vêm as primeiras representações genuínas do modelo.

Ele também exige que a regra da cadeia de probabilidade do Capítulo 2 esteja exatamente correta, porque a afirmação de que prever um token por vez é o mesmo que modelar documentos inteiros é uma fatoração, não uma metáfora.

O Capítulo 8 é o objetivo autorregressivo, embeddings e o primeiro lugar em que um modelo aprende algo que ninguém colocou ali.

Kudo, T. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (arXiv:1804.10959) introduz o modelo Unigram; Kudo e Richardson, SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing (arXiv:1808.06226) é a implementação que a maioria dos modelos multilíngues usa; Schuster e Nakajima, Japanese and Korean Voice Search (ICASSP 2012) é a origem do WordPiece. Let's build the GPT Tokenizer, de Andrej Karpathy, e o repositório karpathy/minbpe que o acompanha são os ancestrais diretos do código deste capítulo e vão consideravelmente além, incluindo a regex do GPT-4 e o tratamento de special-token. O capítulo 6 do Hugging Face LLM Course cobre os três algoritmos lado a lado com exemplos resolvidos.