💬 NLP

Joint Optimization for Greedy Longest-match Tokenization

Este artigo introduz o JOLT, um framework de otimização conjunta que formula o aprendizado de vocabulário como um programa inteiro com restrições de consistência gulosa para alinhar o treinamento com a decodificação de correspondência mais longa, alcançando uma compressão quase ideal que supera significativamente o BPE padrão ao mesmo tempo em que fornece um certificado de quase-otimalidade.

Autores originais: Adhiraj Singh, Deepanshu Mody, Ghina Al Shdaifat, Hamza Alshamy, Adam Wiemerslage, Varshini Reddy, Craig W. Schmidt

Publicado 2026-07-28

📖 8 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Adhiraj Singh, Deepanshu Mody, Ghina Al Shdaifat, Hamza Alshamy, Adam Wiemerslage, Varshini Reddy, Craig W. Schmidt

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está tentando guardar uma biblioteca massiva de livros em uma única e pequena mala para uma viagem. Você quer encaixar o máximo de texto possível em um espaço limitado, mas não pode simplesmente esmagar as páginas em uma bola; você precisa organizá-las em blocos limpos e gerenciáveis. No mundo da inteligência artificial, essa "mala" é a memória do computador, e os "blocos" são chamados de tokens. Os modelos de IA leem o texto não como palavras inteiras, mas como esses pedaços menores. A maneira como cortamos as palavras importa muito: se as cortarmos mal, usamos mais espaço e o computador tem que trabalhar mais para lê-las. Durante anos, a forma padrão de cortar essas palavras tem sido um método chamado Byte Pair Encoding (BPE). Pense no BPE como um bibliotecário muito eficiente, mas ligeiramente rígido, que segue uma regra estrita: "Sempre cole as duas partes de texto mais comuns primeiro". É uma abordagem rápida e gananciosa (greedy) que funcionou bem, mas é essencialmente uma heurística — um bom palpite baseado em uma regra simples, não uma solução matemática perfeita.

Recentemente, cientistas começaram a fazer uma grande pergunta: será que o "bom palpite" deste bibliotecário é realmente o melhor que podemos fazer? Ou existe uma maneira mais inteligente de cortar as palavras que caiba ainda mais texto na mala? Este artigo mergulha nessa questão ao observar uma forma específica de a IA ler o texto chamada "Greedy Longest-Match" (Correspondência Mais Longa Gananciosa). Imagine ler uma frase e, em cada etapa, pegar a maior palavra possível que você conhece antes de passar para a próxima letra. Os autores queriam ver se poderiam projetar um vocabulário especificamente para este estilo de leitura, em vez de apenas esperar que um vocabulário de propósito geral funcionasse. Eles construíram um novo sistema chamado JOLT (Joint Optimization for Greedy Longest-match Tokenization). Em vez de apenas colar pedaços com base na frequência, o JOLT trata todo o problema como um quebra-cabeça gigante e complexo. Ele usa matemática avançada para descobrir exatamente quais pedaços de palavras manter e como cortar cada palavra nos dados de treinamento para que, quando a IA a leia usando a regra de "correspondência mais longa", ela use o número mínimo absoluto de pedaços possível.

O artigo descobre que, embora o antigo bibliotecário (BPE) seja realmente muito bom — já estando dentro de 1% a 2% do melhor empacotamento teórico possível — o novo sistema, JOLT, consegue espremer um pouco mais de espaço. Ao resolver este quebra-cabeça matemático, o JOLT consegue fechar quase todo o espaço restante entre o método antigo e o limite teórico perfeito. Em testes com diferentes tamanhos de dados de texto, o JOLT reduziu o número de tokens em até 0,78% em comparação com o método padrão. Embora esse número pareça pequeno, no mundo da IA, economizar até mesmo uma fração de um por cento significa que o modelo pode ler mais texto, pensar mais rápido e custar menos para rodar. Os autores mostram que, ao alinhar o vocabulário perfeitamente com a maneira como a IA realmente lê, podemos recuperar quase todo o "espaço de compressão" que anteriormente havia sido deixado sobre a mesa.

A História do JOLT: Resolvendo o Quebra-Cabeça das Palavras

Para entender como o JOLT funciona, imagine que você é um mestre chef tentando criar o menu perfeito para um banquete massivo. Você tem uma lista enorme de ingredientes (o texto) e precisa cortá-los em tamanhos específicos (tokens) para servir aos seus convidados (a IA). O detalhe é que seus convidados têm um hábito de comer muito específico: eles sempre pegam a maior mordida que conseguem encontrar que caiba em sua boca antes de passar para a próxima mordida. Esta é a regra da "Greedy Longest-Match" (Correspondência Mais Longa Gananciosa).

Por muito tempo, os chefs (pesquisadores de IA) usaram uma receita padrão chamada BPE. Eles olhavam para os ingredientes e diziam: "Ei, 'th' e 'e' aparecem juntos muitas vezes, vamos colá-los em 'the'". Eles continuavam fazendo isso, colando os pares mais comuns, até terem um menu de um certo tamanho. Funcionava bem, mas era um pouco como construir uma casa apenas empilhando tijolos sem verificar se as paredes estavam perfeitamente retas. Era uma abordagem "gananciosa" (greedy) — fazer a coisa fácil e óbvia primeiro.

Os autores deste artigo perceberam que, se você quer que os convidados comam de forma eficiente, não deve apenas construir um menu baseado no que é comum; você deve construir um menu baseado em como eles comem. Eles criaram o JOLT, que é como um chef super inteligente que planeja todo o menu de uma só vez, considerando cada ingrediente e cada possível maneira de cortá-lo, garantindo que o resultado final seja perfeitamente otimizado para o hábito de "maior mordida" dos convidados.

O Quebra-Cabeça Matemático
O núcleo do JOLT é um problema matemático massivo. Os autores tiveram que decidir duas coisas simultaneamente:

Quais ingredientes manter: Quais pedaços de palavras devem estar no vocabulário final?
Como cortar o texto: Para cada palavra no conjunto de dados de treinamento, quais pedaços específicos devem ser usados para construí-la?

A parte difícil é que essas duas decisões estão travadas entre si. Você não pode decidir cortar uma palavra em "ta" e "ble" a menos que tenha decidido manter "ta" e "ble" em seu vocabulário. Além disso, como a IA usa a regra de "correspondência mais longa", você tem que garantir que, se você cortar uma palavra em "ta" e "ble", não exista um pedaço mais longo como "table" em seu vocabulário que roube a cena. Se "table" existir, a IA comerá "table" inteira, e seu plano de servir "ta" e "ble" falhará.

Para resolver isso, os autores usaram uma técnica chamada "Programação Inteira". Imagine uma grade gigante de interruptores. Alguns interruptores ligam uma palavra (colocam-na no vocabulário) e outros ligam uma forma específica de cortar uma palavra. O objetivo é acionar os interruptores para obter o menor número total de pedaços possível. No entanto, resolver essa grade para uma biblioteca inteira de texto é tão enorme que até os computadores mais rápidos levariam uma eternidade.

O Atalho Inteligente
Então, os autores criaram um truque inteligente. Em vez de tentar resolver todo o quebra-cabeça de uma vez, eles começaram com uma versão pequena e simples. Eles consideraram apenas cortar palavras em um ou dois pedaços. Eles resolveram o problema matemático e, se o computador dissesse: "Ei, esta palavra é muito difícil de cortar apenas com estas peças, preciso de mais opções", eles adicionavam opções de corte mais complexas apenas para aquela palavra. Eles repetiram esse processo, adicionando complexidade apenas onde era necessário, até que a solução se estabilizasse.

Essa abordagem permitiu que encontrassem uma solução que é incrivelmente próxima do limite teórico perfeito. Eles descobriram que o método BPE padrão já estava fazendo um ótimo trabalho, situando-se dentro de 1% a 2% do melhor resultado possível. Mas o JOLT conseguiu fechar de 89,6% a 99,4% desse intervalo restante.

Os Resultados
Quando testaram seu novo sistema em diferentes quantidades de dados (de 100.000 a 400.000 palavras) e diferentes tamanhos de vocabulário (32.000 e 64.000 palavras), os resultados foram claros. O JOLT consistentemente usou menos tokens do que o método padrão BPE.

Com um vocabulário de 32.000 palavras, o JOLT reduziu a contagem de tokens em até 0,78% em comparação com o método padrão.
Com um vocabulário de 64.000 palavras, a melhoria foi menor, mas ainda presente, atingindo até 0,31%.

O artigo também verificou o quão próximo eles estavam do limite matemático absoluto. Descobriram que sua solução final, arredondada, estava dentro de 0,008% a 0,176% do melhor teórico. Isso significa que o processo de "arredondamento" (transformar a solução matemática em um vocabulário real e utilizável) não perdeu muita eficiência. Os pequenos ganhos que o JOLT obteve sobre o BPE não foram apenas um acaso; foram melhorias estruturais reais.

Por que isso importa
Os autores também observaram outros métodos. Eles descobriram que um método popular chamado WordPiece, que é projetado para o mesmo estilo de leitura de "correspondência mais longa", na verdade teve um desempenho pior que o BPE quando testado. Isso ocorreu porque o WordPiece foi treinado para maximizar um objetivo diferente (prever a próxima palavra) em vez de minimizar o número de pedaços. Isso prova que você não pode simplesmente usar um vocabulário projetado para um propósito e esperar que ele funcione perfeitamente para outro. Você tem que treinar o vocabulário especificamente para a maneira como a IA lê.

Em resumo, este artigo mostra que, embora o antigo bibliotecário "ganancioso" (BPE) estivesse fazendo um trabalho surpreendentemente bom, ainda resta um pequeno espaço para espremer. Ao usar uma abordagem matematicamente rigorosa que alinha o vocabulário perfeitamente com o estilo de leitura da IA, o JOLT recupera quase todo esse espaço perdido. É um lembrete de que, no mundo da IA, mesmo pequenas melhorias na eficiência podem levar a modelos mais rápidos, mais baratos e mais capazes. Os autores não apenas adivinharam; eles provaram matematicamente que seu método nos aproxima mais do trabalho de empacotamento perfeito do que nunca.

Resumo Técnico: Otimização Conjunta para Tokenização de Correspondência Mais Longa Gulosa (JOLT)

Definição do Problema
A tokenização de subpalavras é uma etapa de pré-processamento crítica em PLN, onde a conversão de texto em tokens afeta a capacidade da janela de contexto e os custos de inferência. Embora o Byte Pair Encoding (BPE) seja o heurístico dominante, trabalhos recentes (ex: ToaST, ConvexTok) demonstraram que o treinamento de vocabulário pode ser formulado como um problema de otimização para minimizar diretamente a contagem de tokens para regras de inferência específicas. No entanto, as abordagens de otimização existentes visam regras de inferência de árvore de divisão (split-tree) ou de caminho mais curto (shortest-path). Há uma carência de técnicas de construção de vocabulário especificamente projetadas para a decodificação de correspondência mais longa Greedy Left-to-Right (GL2R), a regra de inferência padrão usada pelo WordPiece. O desafio reside em formular a seleção de vocabulário de tal forma que a contagem de tokens resultante corresponda exatamente ao que o algoritmo GL2R produz durante o deployment, uma restrição que acopla a seleção de vocabulário com as escolhas de segmentação de uma forma não trivial.

Metodologia
Os autores propõem o JOLT (Joint Optimization for Greedy Longest-match Tokenization), que formula o aprendizado de vocabulário como um Programa Inteiro (IP) e o resolve via relaxação de Programação Linear (LP).

Formulação: O modelo otimiza conjuntamente dois conjuntos de variáveis binárias:
1. Variáveis de seleção de vocabulário ( $x_t$ ): Determinam quais tokens candidatos entram no vocabulário.
2. Variáveis de escolha de segmentação ( $z_{p,s}$ ): Determinam qual segmentação $s$ é selecionada para cada pretoken $p$ .
Restrições de Consistência Gulosa (Greedy-Consistency): A inovação central é um conjunto de restrições que garante que uma segmentação selecionada seja exatamente o que o algoritmo GL2R produziria dado o vocabulário selecionado. Para que uma segmentação seja válida sob GL2R, nenhum token de vocabulário mais longo pode existir que se sobreponha ao início de qualquer segmento nesta segmentação. Essas restrições forçam a otimização a considerar explicitamente o comportamento de "correspondência mais longa".
Escalonamento Iterativo: Como o número de segmentações possíveis cresce exponencialmente com o comprimento do pretoken, o JOLT não instancia todos os candidatos inicialmente. Ele começa com segmentações de ordem baixa (até ordem 2) e uma opção de "fallback". Se o solver selecionar o fallback para um pretoken, o sistema escala a ordem máxima de segmentação para aquele pretoken na rodada seguinte, adicionando candidatos de ordem superior. Isso mantém o tamanho do LP tratável.
Relaxação de LP e Arredondamento: O IP é relaxado para um LP (permitindo valores fracionários para $x_t$ e $z_{p,s}$ ) e resolvido usando o Gurobi. Um esquema de arredondamento ponderado baseado em contribuição extrai um vocabulário discreto da solução fracionária. O arredondamento prioriza tokens que contribuem mais para comprimir pretokens de alta frequência.

Principais Contribuições

Otimização Específica para GL2R: O JOLT é o primeiro método a formular o aprendizado de vocabulário especificamente para a inferência GL2R, garantindo que a contagem de tokens otimizada seja igual à contagem realizada no deployment.
Restrições de Consistência Gulosa: O artigo introduz um conjunto de restrições inovador que impõe matematicamente a propriedade de correspondência mais longa do GL2R dentro da estrutura de otimização, acoplando a seleção de vocabulário e a segmentação.
Estratégia de Resolução Escalável: Os autores desenvolvem um mecanismo de escalonamento baseado em fallback que evita a explosão exponencial de variáveis ao instanciar apenas segmentações de ordem superior quando necessário.
Limites Próximos do Ótimo: A relaxação de LP fornece um limite inferior válido para a contagem de tokens alcançável. Os autores mostram que as soluções arredondadas estão dentro de 0,008–0,176% deste limite inferior de LP, certificando uma compressão próxima do ótimo.

Resultados
Experimentos foram conduzidos no dataset MiniPile com escopos de treinamento ( $N$ ) de 100k, 200k, 300k e 400k pretokens, e tamanhos de vocabulário ( $|V|$ ) de 32k e 64k.

Ganhos de Compressão: Em dados de validação não vistos, o JOLT reduz a contagem de tokens em comparação com a decodificação nativa de BPE em até 0,78% (em $N=400k, |V|=32k$ ). Os ganhos geralmente aumentam com o escopo de treinamento.
Fechamento de Gap: O limite inferior de LP revela que as heurísticas padrão de BPE já estão próximas do ótimo para GL2R, situando-se dentro de 1–2% do limite teórico. O JOLT fecha 89,6–99,4% do gap restante entre o BPE e o limite de LP.
Eficiência de Arredondamento: O gap entre a relaxação de LP e o vocabulário arredondado final é negligenciável (0,008–0,176%), indicando que o processo de arredondamento quase não perde potencial de compressão.
Comparação com Baselines:
- BPE-greedy: Aplicar a decodificação GL2R a um vocabulário treinado por BPE produz apenas uma melhoria marginal (0,08%) sobre o nativo de BPE, confirmando que a heurística de merge do BPE está estruturalmente alinhada com o GL2R.
- UnigramLM-greedy: Apesar de usar inferência GL2R, o UnigramLM performa significativamente pior (28–30% mais tokens) porque seu objetivo de treinamento (maximizar a verossimilhança) diverge do objetivo de minimizar a contagem de tokens.

Significância e Alegações
O artigo alega que a principal fonte de ineficiência de compressão nos tokenizadores atuais não é o próprio processo de inferência, mas o desalinhamento entre a heurística de construção do vocabulário e a regra de inferência específica. Embora o BPE já seja próximo do ótimo para GL2R, o JOLT demonstra que o "espaço de manobra" (gap entre o BPE e o ótimo teórico) pode ser amplamente recuperado através da otimização de vocabulário alinhada à inferência. Os resultados sugerem que a maior parte da compressão alcançável para a inferência GL2R é recuperável, com o JOLT recuperando 89,6–99,4% do ganho teórico. O artigo não afirma que o JOLT supera drasticamente o BPE em termos absolutos (os ganhos são <1%), mas sim que ele fornece uma abordagem baseada em otimização e principiológica que certifica a proximidade do ótimo e recupera o potencial de compressão limitado das heurísticas padrão.

A História do JOLT: Resolvendo o Quebra-Cabeça das Palavras

Mais como este