Construa um tokenizer BPE: porque é que o seu modelo não consegue contar os R

Há duas formas óbvias de dar texto a uma rede, e ambas falham por razões que vale a pena compreender, porque a falha define a forma da solução.

Palavras. Dividir por espaços, atribuir 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, por isso o vocabulário — e a camada de saída, que tem de produzir uma pontuação para cada entrada — torna-se enorme. Pior é o que acontece em inferência: uma palavra que o modelo nunca viu no treino não tem número. Esse é o problema out-of-vocabulary, e o remendo habitual é mapear tudo o que é desconhecido para um único token <UNK>, o que deita a informação fora. Além disso, «palavra» não é um conceito bem definido: o chinês e o japonês não põem espaços entre palavras, e o alemão compõe substantivos uns sobre os outros indefinidamente.

Caracteres. Não há problema out-of-vocabulary, e o vocabulário tem pouco mais de uma centena de símbolos. Mas as sequências tornam-se 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 cerca de 5000 caracteres — uma sequência quatro a cinco vezes mais longa do que precisa de ser, por um preço quadrático. E cada carácter transporta quase nenhum significado por si só, por isso as primeiras camadas acabam gastas a reconstruir palavras que o tokenizer poderia ter entregado intactas.

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

O algoritmo vem de 1994, e era um algoritmo de compressão. Philip Gage publicou-o no C Users Journal como uma forma de reduzir ficheiros substituindo repetidamente o par mais frequente de bytes adjacentes por um byte que não ocorre nos dados.¹ Ficou ali durante vinte e dois anos, até Sennrich, Haddow e Birch o reaproveitarem para tradução automática em 2016, para resolver o problema out-of-vocabulary.² Hoje é essencialmente assim que todos os grandes modelos de linguagem leem.

O ciclo de treino repete quatro passos:

Aqui está o trainer 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

Corra-o em 151.191 bytes de prosa inglesa e imprima as primeiras doze fusões à medida que acontecem. Esta é a parte que vale a pena ler devagar, porque ninguém disse nada ao algoritmo sobre inglês:

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)

Há três coisas nessa lista que merecem destaque.

A fusão 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 ciclo que conta pares. Ninguém forneceu um dicionário. Está lá porque esses cinco bytes coocorrem mais do que quaisquer outros cinco em inglês.

A fusão 3 nem sequer é texto. \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 da sua estrutura, porque codificações multibyte são, por construção, sequências de bytes que aparecem sempre juntas.

A maioria das primeiras fusões envolve um espaço, e o espaço costuma estar à esquerda. É essa a origem de um dos comportamentos mais confusos na prática, ao qual voltaremos daqui a pouco.

Cada fusão torna a sequência mais curta e o vocabulário maior. Até onde avançar é uma decisão real, e pode ser medida — aqui nos mesmos 151.191 bytes:

Rendimentos decrescentes, visivelmente. Duplicar de 512 para 1024 compra 0,78 bytes por token; duplicar de 2048 para 4096 compra 1,07 — melhor aqui apenas porque este corpus é suficientemente pequeno para fusões mais longas continuarem a compensar. Num corpus real, a curva achata com força.

E o custo de um vocabulário maior não é apenas memória. Cada token precisa de uma linha de embedding e — mais caro ainda — a camada de saída do modelo tem de produzir uma pontuação para cada entrada do vocabulário em cada passo, por isso a multiplicação matricial final escala com o tamanho do vocabulário. Modelos reais situam-se entre 32.000 e 200.000: o GPT-2 usava 50.257, o cl100k do GPT-4 usa 100.277, o o200k do GPT-4o praticamente duplica isso. A tendência é de subida, e a razão está na secção seguinte.

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

O mesmo conteúdo, o mesmo significado, e com cl100k a versão russa consome duas vezes e meia os tokens. Como as APIs cobram por token e as context windows são medidas em tokens, isto não é uma curiosidade linguística — é uma linha num orçamento, uma context window efetiva mais curta e uma resposta mais lenta, as três coisas ao mesmo tempo, para todos os que não trabalham em inglês.

O mecanismo são os dados de treino. Um tokenizer treinado sobretudo em inglês gasta o seu orçamento de fusões em sequências de bytes inglesas. O espanhol partilha o alfabeto latino, por isso ainda obtém algum benefício; o russo quase nenhum, porque os caracteres cirílicos ocupam dois bytes em UTF-8 e poucos desses pares eram suficientemente comuns no corpus de treino para merecer uma fusão. O japonês é ainda pior: três bytes por carácter, e 72 caracteres tornam-se 79 tokens — mais tokens do que caracteres.

A coluna o200k mostra que este é um problema resolúvel e que está a ser resolvido. Duplicar o vocabulário e reequilibrar os dados de treino reduz o sobrecusto do espanhol de +39 % para +16 %, e o do russo de +152 % para +39 %. Essa é a verdadeira razão pela qual os vocabulários continuam a crescer: não compressão por si só, mas o facto de a geração anterior estar silenciosamente a cobrar um extra a uma grande parte do mundo.

O treino produziu uma lista ordenada de fusões. Codificar novo texto reprodu-la — e tem de a reproduzir pela mesma ordem, porque a fusão 12 combina os resultados das fusões 5 e 1. Aplique-as por outra ordem e obtém uma tokenização diferente e errada, que não corresponderá a nada que o modelo tenha visto no treino.

    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 é trivial em comparação: procurar os bytes de cada id, concatenar, descodificar como UTF-8. Repare no errors="replace": um modelo pode emitir uma sequência de tokens que termina a meio de um carácter, e isso não é hipotético — é o que acontece quando uma resposta em streaming é cortada a meio de um emoji, razão pela qual as APIs de streaming armazenam bytes parciais em buffer em vez de descodificarem token a token.

O round-trip funciona em qualquer coisa, que é a promessa do BPE ao nível dos 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

Assim que o mecanismo fica claro, um conjunto de queixas aparentemente não relacionadas revela ser a mesma queixa.

Aritmética. Os 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 tem primeiro de perceber que ['123','4'] e ['123','45'] são números cujos dígitos se alinham de uma determinada forma — e o alinhamento é diferente 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 seguinte. Alguns tokenizers mais recentes forçam os dígitos a dividir-se em grupos consistentes de três precisamente para remover este obstáculo, e os 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 carácter que vem depois. A indentação, que em Python é sintaxe, é representada de forma inconsistente — o que é uma grande parte da razão pela qual os modelos costumavam produzir Python com indentação subtilmente errada, e porque os tokenizers focados em código adicionam tokens explícitos para sequências comuns de indentação.

Ortografia e inversão. A mesma causa que contar os r: pedir a um modelo para inverter strawberry é pedir-lhe para reordenar letras dentro de três ids opacos. Os modelos fazem-no por terem memorizado grafias durante o treino, e não por olharem, razão pela qual o fazem bem para palavras comuns e mal para palavras raras.

Glitch tokens. O caso mais marcante é SolidGoldMagikarp e um conjunto de strings semelhantes que fizeram o GPT-2 e o GPT-3 comportar-se de forma bizarra — recusando repeti-las, produzindo output não relacionado, por vezes insultando o utilizador. A explicação é banal e decorre diretamente do facto de o tokenizer ser treinado separadamente do modelo: essas strings eram frequentes no corpus de treino do tokenizer (eram nomes de utilizador do Reddit), por isso ganharam o seu próprio token, mas eram raras ou inexistentes no corpus de treino 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 o seu comportamento aí é o que quer que a inicialização aleatória tenha produzido.

Um tokenizer é uma interface com perdas entre texto e números, e todos os comportamentos estranhos deste capítulo são a interface a aparecer. Vale a pena deixar claro que a troca é deliberada: BPE ao nível dos bytes significa que nenhum input é alguma vez irrepresentável, as sequências são quatro a cinco vezes mais curtas do que seriam com caracteres, e as 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ências sobre um corpus que não viu, com um custo por língua que ninguém negociou.

Agora tem uma sequência de inteiros. Esse é o formato de input para tudo no resto da Parte II.

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

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

O Capítulo 8 é o objetivo autoregressivo, embeddings, e o primeiro lugar onde um modelo aprende algo que ninguém pôs lá.

Kudo, T. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (arXiv:1804.10959) introduz o modelo Unigram; Kudo and 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 multilingues usa; Schuster and 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 antepassados diretos do código deste capítulo e vão consideravelmente mais longe, incluindo a regex do GPT-4 e o tratamento de special tokens. O Capítulo 6 do Hugging Face LLM Course cobre os três algoritmos lado a lado com exemplos trabalhados.