Resumo Técnico: Tokenização com Árvores de Divisão (ToaST)

Declaração do Problema

A tokenização é uma etapa fundamental no processamento de linguagem natural, contudo, os métodos existentes frequentemente dependem de heurísticas gananciosas que podem não otimizar a compressão ou o desempenho em tarefas subsequentes. Embora a Codificação de Pares de Bytes (BPE) minimize a contagem de tokens por meio de uma estratégia de mesclagem gananciosa, ela é uma aproximação heurística. Trabalhos anteriores estabeleceram que encontrar um tokenizador que maximize a compressão é NP-completo, mesmo sobre alfabetos limitados. Além disso, a relação entre compressão e desempenho em tarefas subsequentes permanece debatida; enquanto alguns estudos sugerem uma correlação, outros argumentam que a compressão sozinha é insuficiente para explicar a qualidade da tokenização. Alternativas existentes, como UnigramLM ou PathPiece, utilizam procedimentos de inferência diferentes (por exemplo, inferência top-down ablativa ou de caminho mais curto), mas ainda enfrentam desafios na otimização global e na escalabilidade computacional.

Metodologia

Os autores introduzem a Tokenização com Árvores de Divisão (ToaST), um método de tokenização de subpalavras que desacopla a construção de tokens candidatos da seleção do vocabulário final. A abordagem consiste em três etapas principais:

1. Construção da Árvore de Divisão

Diferentemente da BPE, que constrói tokens de baixo para cima, ou do UnigramLM, que aprende probabilidades de cima para baixo, o ToaST constrói uma árvore binária completa para cada pretoken único no corpus de treinamento, independentemente de qualquer vocabulário.

• Pré-processamento: Os dados de treinamento são divididos em pretokenos usando uma expressão regular.
• Lógica de Divisão: Para um dado pretoken, o algoritmo divide-o recursivamente em duas partes não vazias. O ponto de divisão é escolhido deterministicamente para maximizar a contagem mínima dos n-gramas de bytes resultantes à esquerda e à direita ($\max \min(c_p, c_{p'})$), com base em estatísticas de n-gramas pré-calculadas do corpus.
• Estrutura: Este processo continua até que as folhas sejam bytes únicos. Os nós dessas árvores formam o conjunto de todos os tokens candidatos. Esta construção é independente do vocabulário final e não requer treinamento iterativo.

2. Inferência Recursiva

Dado um vocabulário $V$, a tokenização é realizada por meio de uma descida recursiva na árvore de divisão:

• Começando na raiz (o pretoken completo), o algoritmo verifica se o nó atual está em $V$.
• Se o nó estiver em $V$, ele é emitido como um token.
• Se não estiver, o algoritmo processa recursivamente os dois filhos.
• Propriedades: Este procedimento garante que qualquer vocabulário contendo todos os bytes únicos necessários produza uma tokenização válida. Remover um token do vocabulário simplesmente força a inferência a descer mais profundamente na árvore, sem efeitos cascata sobre outros tokens, ao contrário de métodos baseados em mesclagem.

3. Seleção de Vocabulário via Programação Inteira

A inovação central é formular a seleção de vocabulário como um Programa Inteiro (PI) para minimizar a contagem total de tokens no corpus de treinamento.

• Variáveis: Variáveis binárias $x_i$ indicam se o token candidato $i$ está no vocabulário. Variáveis binárias $z_{jk}$ indicam se o nó $k$ na árvore de divisão $j$ é emitido durante a inferência.
• Objetivo: Minimizar a contagem ponderada total de tokens emitidos: $\min \sum_{j} c_j \sum_{k} z_{jk}$.
• Restrições:
  • Tamanho do Vocabulário: A soma dos tokens selecionados deve ser igual ao tamanho alvo $m$.
  • Cobertura: Para cada caminho de uma folha até a raiz, exatamente um nó deve ser selecionado (garantindo que todo o pretoken seja coberto).
  • Consistência: Um nó só pode ser emitido ($z_{jk}=1$) se estiver no vocabulário ($x_i=1$) e nenhum de seus ancestrais estiver.
• Resolução: O PI é relaxado para um Programa Linear (PL). Na prática, o relaxamento PL é "quase-integral", o que significa que a solução contém muito poucos valores fracionários. Uma heurística simples de arredondamento é aplicada para obter uma solução inteira que é provadamente quase ótima (dentro de uma fração negligenciável do ótimo global).

Contribuições Principais

1. Novo Framework de Tokenização: O ToaST introduz uma abordagem baseada em árvores de divisão que evita as aproximações gananciosas da BPE e as restrições específicas de inferência do UnigramLM.
2. Otimização Global: Ao formular a seleção de vocabulário como um PI com um relaxamento PL apertado, o ToaST encontra um vocabulário que minimiza globalmente as contagens de tokens para um conjunto dado de árvores de divisão, em vez de depender de decisões locais gananciosas.
3. Escalabilidade: O método escala quadraticamente com o número de árvores de divisão, permitindo o processamento de grandes corpora (cobrindo 99% das contagens de pretokenos) dentro de tempos de treinamento viáveis.
4. Design Desacoplado: A separação entre a construção da árvore (baseada em estatísticas do corpus) e a seleção do vocabulário (baseada em otimização) permite extensões flexíveis, como incorporar preferências morfológicas ou em nível de caractere sem retreinar o modelo de otimização.

Resultados Experimentais

Os autores avaliaram o ToaST em texto inglês usando o conjunto de dados CulturaX e compararam-no com BPE, WordPiece e UnigramLM.

• Compressão: Em tamanhos de vocabulário de 40.960 e acima, o ToaST reduz a contagem de tokens em mais de 11% em comparação com todas as linhas de base. Isso é medido em bytes por token.
• Distribuição de Tokens: O ToaST reduz significativamente a frequência de tokens "Folha" (fallbacks de byte único) em 14–19 vezes em comparação com as linhas de base em um tamanho de vocabulário de 65.536. Por outro lado, produz substancialmente mais tokens "Raiz" (pretokenos completos), indicando melhor retenção de unidades semânticas.
• Eficiência de Rényi: O ToaST alcança maior eficiência de Rényi (com $\alpha=2.5$), indicando uma distribuição de tokens mais uniforme e menos tokens de alta frequência, o que frequentemente se correlaciona com melhor desempenho em tarefas subsequentes.
• Desempenho em Tarefas Subsequentes: Em experimentos treinando modelos de linguagem de 1,5 bilhão de parâmetros (nanochat), o ToaST alcançou a maior pontuação CORE (uma média de 22 benchmarks), superando as linhas de base em 2,6% a 7,6%. Superou significativamente a BPE e o UnigramLM e foi o melhor desempenho em 13 de 22 tarefas individuais.
• Qualidade da Otimização: O relaxamento PL foi encontrado excepcionalmente apertado. Em 128 instâncias de problemas, a lacuna relativa máxima entre a solução inteira arredondada e o limite do PL foi de $5,76 \times 10^{-7}$, com muitas instâncias sendo totalmente inteiras.

Significado e Alegações

O artigo afirma que o ToaST demonstra o valor de otimizar a tokenização diretamente para compressão usando um framework de otimização global, em vez de depender de heurísticas gananciosas. Os autores argumentam que a compressão superior leva a uma janela de contexto efetiva maior e, consequentemente, a um desempenho aprimorado em tarefas subsequentes.

O significado do trabalho reside em:

• Praticidade: Apesar da NP-completude teórica da tokenização ótima, o relaxamento PL torna a abordagem computacionalmente viável e prática para treinamento em grande escala.
• Desempenho: Os resultados empíricos sugerem que a redução de 11% na contagem de tokens se traduz em ganhos mensuráveis no desempenho do modelo de linguagem (pontuação CORE), apoiando a hipótese de que melhor compressão correlaciona-se com melhor utilidade do modelo.
• Flexibilidade: A arquitetura permite futuras extensões, como o tratamento de caracteres multibyte ou divisões morfológicas, modificando a hierarquia de construção da árvore sem alterar a lógica de otimização do vocabulário.

Os autores observam limitações, especificamente que os experimentos foram conduzidos exclusivamente em texto inglês, e a eficácia do treinamento nos pretokenos agregados superiores pode variar para idiomas não delimitados por espaços. Eles também divulgam o uso de LLMs para implementação de código e geração de figuras.