Por que eu fui atrás disso

Eu passo o dia usando modelos de linguagem pra escrever código. Em algum momento percebi que dependia de uma peça que nunca tinha olhado de perto: a tokenização. É a primeira coisa que acontece com qualquer texto antes do modelo “pensar”, e mesmo assim, pra maioria de nós, é só uma chamada de biblioteca.

Resolvi abrir a caixa. Implementei os quatro algoritmos clássicos de tokenização por subpalavra em Rust, do zero, e coloquei os quatro pra brigar no mesmo benchmark controlado. Não queria reinventar a tokenizers da Hugging Face. Queria entender, na unha, o que cada critério de seleção faz de diferente, qual a matemática por trás e o que isso custa em compressão e em tempo.

Tokenização em 30 segundos

Um modelo não lê texto: ele lê inteiros. Tokenização é o processo de quebrar o texto em pedaços (tokens) e mapear cada pedaço para um id.

Os dois extremos são ruins. Por caractere, o vocabulário é minúsculo mas as sequências ficam enormes (e atenção custa quadrático no comprimento). Por palavra inteira, o vocabulário explode e qualquer palavra fora dele vira <unk>. A tokenização por subpalavra fica no meio: aprende pedaços recorrentes (aprend, ##izado, ▁de) a partir de um corpus, equilibrando tamanho de vocabulário e tamanho de sequência.

A pergunta interessante, e onde os quatro algoritmos divergem, é como esses pedaços são escolhidos. É tudo uma questão de critério de seleção.

1. BPE: o guloso por frequência

BPE parte do texto quebrado em caracteres e, a cada iteração, funde o par de símbolos adjacentes mais frequente. O critério é frequência pura:

score(a,b)=C(a,b)\text{score}(a,b) = C(a,b)

onde C(a, b) é o número de vezes que os símbolos a e b aparecem lado a lado na representação atual do corpus. Funde-se (a, b)* num novo símbolo ab, recontam-se os pares, repete-se. Para após M merges (ou ao atingir o vocabulário-alvo).

A regra é simples, e é exatamente por isso que funciona: pares frequentes viram subpalavras, subpalavras frequentes viram palavras inteiras, e o vocabulário cresce na direção do que o corpus realmente usa. É a base da família GPT. (Sennrich et al., 2016)

Custo: a versão ingênua reconta todos os pares a cada merge, O(M · N) com N o tamanho do corpus. Dá pra cortar muito mantendo as contagens de forma incremental, já que só os pares na vizinhança da posição fundida mudam a cada passo.

2. WordPiece: o critério é ganho, e isso é PMI

WordPiece parece BPE, mas troca o critério. Em vez de fundir o par mais frequente, funde o par com maior ganho:

score(a,b)=C(a,b)C(a)⋅C(b)\text{score}(a,b) = \dfrac{C(a,b)}{C(a)\cdot C(b)}

A intuição: um par pode ser frequente só porque seus dois pedaços são frequentes sozinhos. O denominador corrige isso, premiando pares que aparecem mais juntos do que se esperaria se fossem independentes.

E aqui está a parte que eu achei elegante. Esse critério é, a menos de uma constante, PMI (pointwise mutual information). Com P(·) = C(·)/N:

PMI(a,b)=log⁡P(a,b)P(a)⋅P(b)=log⁡N⋅C(a,b)C(a)⋅C(b)\begin{aligned} \text{PMI}(a,b) &= \log \dfrac{P(a,b)}{P(a)\cdot P(b)} \\ &= \log \dfrac{N\cdot C(a,b)}{C(a)\cdot C(b)} \end{aligned}

Como log N é constante entre todos os pares numa dada iteração, argmax PMI(a,b) = argmax score(a,b). Ou seja: WordPiece é BPE rankeando por PMI em vez de frequência bruta. É um detalhe pequeno na fórmula com um efeito grande no vocabulário resultante.

WordPiece marca subpalavras não-iniciais com ## e é o tokenizador do BERT. (Schuster & Nakamura, 2012)

3. SentencePiece-BPE: o mesmo BPE sem a muleta do espaço

Tanto o BPE quanto o WordPiece acima assumem uma pré-tokenização: o texto já chega quebrado em palavras (geralmente no espaço). Isso embute uma suposição que nem toda língua respeita, já que japonês e chinês não separam palavras com espaço.

SentencePiece resolve tratando o input como um fluxo cru de caracteres e codificando o próprio espaço como um caractere especial, ▁ (U+2581, “lower one eighth block”). Sem fronteira de palavra privilegiada: o algoritmo aprende ▁de, ▁para e afins como qualquer outro pedaço. O critério de merge continua o do BPE:

arg⁡max⁡a,bC(a,b)\arg\max_{a,b} C(a,b)

mas o domínio agora é a frase inteira. Resultado: o mesmo algoritmo funciona idêntico em qualquer idioma, e a detokenização é trivial, bastando trocar ▁ por espaço. (Kudo & Richardson, 2018)

4. Unigram LM: começa grande e poda pelo que menos dói

Os três anteriores constroem o vocabulário de baixo pra cima. O Unigram faz o contrário: começa com um vocabulário enorme de candidatos e vai removendo os piores.

O modelo assume que cada token é gerado de forma independente (daí “unigram”). A probabilidade de uma segmentação x = (x₁, …, x_M) de uma frase é o produto:

P(x)=∏i=1Mp(xi)sujeito a∑t∈Vp(t)=1P(x) = \prod_{i=1}^{M} p(x_i) \qquad \text{sujeito a} \qquad \sum_{t \in V} p(t) = 1

Uma mesma frase tem muitas segmentações possíveis. A melhor é a de maior probabilidade, encontrada com Viterbi sobre o lattice de segmentações:

x∗=arg⁡max⁡x∈S(X)P(x)x^{*} = \arg\max_{x \in S(X)} P(x)

Concretamente, para uma string de caracteres c₁…cₙ, a DP guarda o melhor log-score de cada prefixo:

best[0]=0best[j]=max⁡i<jci+1..j∈V(best[i]+log⁡p(ci+1..j))\begin{aligned} \text{best}[0] &= 0 \\ \text{best}[j] &= \max_{\substack{i<j \\ c_{i+1..j}\in V}} \big(\text{best}[i] + \log p(c_{i+1..j})\big) \end{aligned}

Isso roda em O(n · L_max) por frase, com L_max o comprimento do maior token do vocabulário.

O treino é EM. A verossimilhança do corpus marginaliza sobre todas as segmentações:

L=∑Xlog⁡∑x∈S(X)P(x)L = \sum_{X} \log \sum_{x \in S(X)} P(x)
  • E-step: com as probabilidades atuais, estima a frequência esperada de cada token via forward-backward (não dá pra contar direto, porque a segmentação é latente).
  • M-step: reestima p(t) a partir dessas frequências esperadas.

E então vem a poda, a etapa que define o vocabulário final. Para cada token candidato, calcula-se quanto a verossimilhança total cairia se ele fosse removido, o ΔL daquele token. Remove-se de uma vez a fração de tokens com menor ΔL (os que o corpus menos sente falta) e repete-se EM + poda até chegar no vocabulário-alvo. É isso que dá ao SentencePiece-Unigram a flexibilidade de segmentação probabilística que o BPE não tem. (Kudo, 2018)

Como implementei

Tudo num workspace Cargo, uma crate por algoritmo, com o mesmo profile de release. Escolhi Rust pelo motivo de sempre: controle de memória e previsibilidade num código que vive dentro de loops apertados de contagem.

Dois detalhes pesaram mais do que eu esperava:

  • FxHashMap no lugar do hash da stdlib. O HashMap padrão usa SipHash, resistente a ataques de colisão, o que importa pra chave vinda da rede, mas irrelevante e caro aqui. O hot path desses algoritmos é contar pares de símbolos milhões de vezes, com chaves que são inteiros pequenos. Trocar pelo FxHashMap da rustc-hash tira o custo da função de hash criptográfica de cima desse loop, e isso aparece direto no tempo de treino.
  • Paralelismo com rayon. A contagem de pares (BPE/WordPiece/SP) e o E-step do Unigram são embaraçosamente paralelos: dá pra particionar o corpus, contar em paralelo com par_chunks/par_iter e reduzir os mapas parciais no fim, sem reescrever a lógica sequencial.

Como medi (e por que a metodologia importa)

Benchmark mal feito mente com confiança. Pra não me enganar:

  • hyperfine pra rodar cada algoritmo várias vezes e reportar média e desvio, em vez de um time solitário.
  • taskset -c 2 pra prender o processo num único core. Sem isso, o scheduler migra o processo entre cores e o ruído de migração come a diferença que eu quero medir.
  • Corpus fixo: /usr/share/dict/brazilian, 276 mil palavras, o mesmo input pra todos.
  • Vocabulário-alvo de 500 tokens como ponto de comparação.

Resultados

Tempo de treino (BPE com 450 merges ≈ vocab 500, corpus completo):

Algoritmo Tempo médio Relativo
BPE (merges=450) 5,78 s 1,00×
SentencePiece-BPE (vocab=500) 5,87 s 1,02×
WordPiece (vocab=500) 5,97 s 1,03×
Unigram (vocab=500, 5k linhas) 0,63 s não comparável

Qualidade, em tokens por palavra (quanto menor, melhor a compressão):

Algoritmo Tokens/palavra Leitura
BPE 4,70 melhor compressão no vocab pequeno
SentencePiece-BPE 4,90 praticamente empata e ainda marca a fronteira de palavra
Unigram 8,05 melhora bastante com corpus maior
WordPiece 10,40 sofre feio com vocab ≤ 1000; precisa de ≥ 5k tokens pra brilhar

O que esses números querem dizer

O ponto que mais me pegou: três algoritmos treinam em essencialmente o mesmo tempo (~5,8s) e entregam qualidades radicalmente diferentes. Rodar no mesmo tempo não diz nada sobre o resultado que cada um entrega.

O WordPiece é o caso didático. Ele não é ruim, está mal-ajustado pro cenário. Com vocabulário pequeno, o critério de PMI tem pouco espaço pra formar subpalavras úteis: ele evita fundir pares “frequentes por acaso”, mas com orçamento de 500 tokens isso o deixa perto do nível de caractere. Sobe o vocabulário pra ≥ 5k e ele encosta nos outros. É o tipo de problema que só aparece quando você mede de verdade, em vez de assumir.

Onde isso encosta no custo de LLM

Num projeto anterior (a Rinha de Backend) eu falei sobre cortar custo de LLM trocando de modelo conforme a fase do trabalho. Esse experimento me lembrou que parte do custo começa antes do modelo: começa em quantos tokens o seu texto vira.

Dobrar tokens/palavra é dobrar o que você paga por requisição e quanto tempo cada uma leva, sem mexer uma linha no modelo. Pior: como o custo de atenção cresce com o quadrado do comprimento da sequência, sequência mais longa não dói só linearmente. A escolha do tokenizador e do tamanho do vocabulário é uma decisão upstream que se propaga por todo o resto do sistema, fácil de ignorar no começo e cara de corrigir depois.

O que eu tiro disso

Construir na mão as ferramentas que eu uso de pacote pronto mudou como eu leio o output de um tokenizador. Não viro especialista numa semana, mas saio com intuição de engenheiro: sei onde está o loop quente, por que o critério de PMI penaliza vocabulário pequeno, por que o Unigram precisa de EM e não de uma contagem simples, e por que prender o processo num core só não é frescura.

E acho que esse é o recado maior, principalmente pra quem (como eu) constrói rápido com IA hoje: saber os fundamentos é o que me deixa usar as ferramentas modernas com critério, em vez de só confiar nelas no escuro.