💬 NLP

Tokenisation over Bounded Alphabets is Hard

Este artigo prova que a tokenização sobre alfabetos limitados, incluindo os casos binário e unário, é fundamentalmente NP-completa e APX-difícil, estabelecendo que sua intratabilidade computacional é uma barreira inerente em vez de um artefato de grandes alfabetos de entrada e explicando a necessidade de abordagens heurísticas nos algoritmos práticos atuais.

Autores originais: Violeta Kastreva, Philip Whittington, Dennis Komm, Tiago Pimentel

Publicado 2026-08-11

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

Autores originais: Violeta Kastreva, Philip Whittington, Dennis Komm, Tiago Pimentel

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 enviar uma mensagem secreta para um amigo, mas a única maneira de enviar é quebrando suas palavras em pequenos pedaços pré-aprovados. Se você enviar "superduper", pode ter que dividir em "super" e "duper" em vez da palavra inteira, porque o dicionário do seu amigo só tem essas duas partes. Isso é o coração da tokenização, o primeiro passo para ensinar computadores a entender a linguagem humana. Antes de um computador conseguir ler uma frase, ele deve picotá-la nesses "tokens" gerenciáveis (como peças de Lego). O objetivo é picotar o texto de uma forma que utilize o menor número de peças possível, tornando a mensagem mais curta e rápida de enviar. Isso é chamado de compressão. Se você conseguir comprimir um livro em menos peças, o computador poderá lê-lo mais rápido e aprender com ele de forma mais eficiente. Durante anos, cientistas construíram algoritmos inteligentes e gananciosos — como uma criança agarrando a maior peça de Lego disponível que consegue encontrar — para fazer esse corte automaticamente. Mas uma grande questão pairou: existe uma maneira matematicamente perfeita e ótima de picotar qualquer texto, ou estamos presos com suposições "boas o suficiente"?

Este artigo, intitulado "Tokenisation Over Bounded Alphabets Is Hard", mergulha fundo nessa questão. Os autores, uma equipe de pesquisadores da ETH Zürich e da Universidade de Sófia, propuseram-se a provar se encontrar esse método de corte perfeito é, na verdade, um pesadelo para os computadores, mesmo quando as regras são simples. Eles focam em duas formas principais de picotar: Tokenização Direta, onde você escolhe o melhor conjunto de peças de Lego (um vocabulário) de uma só vez, e Tokenização Bottom-Up, onde você começa com letras individuais e continua colando pares até que a cola acabe (fusões/merges). A grande reviravolta em sua história é que eles testam esses métodos não no alfabeto infinito e caótico de todos os sons humanos, mas nos conjuntos minúsculos e fixos que realmente usamos em computadores: binário (apenas 0s e 1s, como um interruptor de luz) e unário (apenas um único símbolo, como uma corda de contas idênticas).

A principal descoberta do artigo é um "Não, você não consegue encontrar facilmente a solução perfeita" ressonante. Os autores provam que, mesmo com os alfabetos mais simples possíveis — como um mundo feito apenas de zeros e uns — encontrar a maneira ideal de comprimir um texto é NP-completo e APX-hard. Em termos simples, isso significa que, não importa quanta capacidade de computação você jogue no problema, não existe um algoritmo rápido e eficiente que possa garantir o melhor resultado possível. Não é apenas que o problema seja difícil; é que ele é fundamentalmente difícil. O artigo descarta explicitamente a ideia de que a dificuldade venha da complexidade da linguagem humana ou de alfabetos enormes. Em vez disso, eles mostam que a barreira existe mesmo nos cenários mais simples e restritos. Além disso, eles provam que você nem sequer consegue chegar "perto o suficiente" da resposta perfeita em um tempo razoável; não existe um esquema de aproximação de tempo polinomial (PTAS) que possa chegar arbitrariamente perto da melhor solução, a menos que um grande mistério matemático (P = NP) seja resolvido.

Os pesquisadores também abordam o caso unário, onde o alfabeto possui apenas um símbolo (pense em uma mensagem feita inteiramente da letra "a"). Você poderia pensar: "Se eu tenho apenas uma letra, quão difícil pode ser?". Surpreendentemente, eles provam que, mesmo aqui, encontrar a maneira ideal de picotar o texto é fortemente NP-completo. Este é um resultado matemático pesado, sugerindo que a dificuldade não é apenas uma peculiaridade de grandes conjuntos de dados; ela está gravada na própria lógica de tentar comprimir um texto de forma otimizada.

Então, o que isso significa para o futuro? O artigo não oferece um novo algoritmo mágico para resolver o problema. Em vez disso, ele explica por por que as ferramentas que usamos hoje, como BPE (Byte-Pair Encoding) e UnigramLM, são forçadas a serem heurísticas — o que significa que usam atalhos inteligentes e suposições em vez de calcular a resposta perfeita. Os autores argumentam que, como a resposta perfeita é computacionalmente impossível de encontrar rapidamente, os pesquisadores devem parar de perseguir o "santo graal" do tokenizador ideal e, em vez disso, focar na construção de métodos de aproximação melhores e comprovadamente bons. A porta para a perfeição está trancada e a chave não existe; o melhor que podemos fazer é aprender a escolher a melhor gazua que temos.

Enunciado do Problema
Trabalhos teóricos recentes estabeleceram que encontrar um tokenizador ideal para um conjunto de dados é NP-completo. No entanto, esses resultados anteriores baseiam-se na premissa de que a tokenização opera sobre alfabetos ilimitadamente grandes. Na prática do processamento de linguagem natural, os tokenizadores operam sobre alfabetos de tamanho fixo e limitado (por exemplo, bytes com tamanho 256, caracteres Unicode com tamanho ~170.000, ou cadeias binárias/de bits com tamanho 2). Permanece uma questão em aberto se a intratabilidade computacional da tokenização persiste quando o tamanho do alfabeto é limitado por uma constante. Este artigo aborda essa lacuna analisando a complexidade da tokenização sobre alfabetos limitados, investigando especificamente se tokenizadores ideais podem ser encontrados eficientemente para alfabetos binários (tamanho 2) e unários (tamanho 1).

Metodologia
Os autores definem o problema de tokenização $n$ -ária, onde o alfabeto de entrada $\Sigma$ tem tamanho $n$ . Eles analisam duas variantes naturais de tokenização:

Tokenização Direta: Encontrar um vocabulário $S$ de tamanho $K$ que, quando aplicado de forma ótima a um conjunto de dados, minimiza o comprimento total da compressão.
Tokenização Bottom-up: Encontrar uma sequência de $K$ operações de fusão (merge) que, quando aplicadas sequencialmente a um conjunto de dados, minimiza o comprimento total da compressão.

A função objetivo utilizada é o comprimento comprimido (o número total de tokens após a codificação), que se correlaciona com os custos de treinamento e inferência do modelo. Os autores empregam técnicas padrão de teoria da complexidade para estabelecer a dureza:

NP-Dureza (NP-Hardness): Provada via reduções de tempo polinomial de problemas conhecidos como NP-difíceis (especificamente 3-OCC-MAX2SAT e Vertex Cover) para os problemas de decisão de tokenização.
APX-Dureza (APX-Hardness): Provada via reduções preservadoras de aproximação (L-reductions) de problemas APX-completos. Isso demonstra que os problemas não pertencem à classe PTAS (Esquema de Aproximação de Tempo Polinomial), o que significa que eles não podem ser aproximados arbitrariamente bem em tempo polinomial, a menos que P = NP.
Problemas de Gap: Os autores definem versões de gap dos problemas para derivar constantes explícitas de dureza de aproximação.

Principais Contribuições e Resultados

Tokenização Binária é APX-Hard:
O artigo prova que tanto a tokenização direta binária quanto a tokenização bottom-up binária são APX-hard.
- Caso Direto: Demonstra-se que a tokenização direta binária não pode ser aproximada em tempo polinomial com uma razão de aproximação $\rho < 1,000002$ (a menos que P = NP).
- Caso Bottom-up: Da mesma forma, a tokenização bottom-up binária é APX-hard com uma constante de dureza de $\rho < 1,0000001$ .
- Estes resultados implicam que, mesmo para o alfabeto mais simples não trivial (binário), encontrar um tokenizador ideal é computacionalmente intratável, e nenhum algoritmo de tempo polinomial pode garantir uma aproximação arbitrariamente próxima do ótimo.
Tokenização Unária é Fortemente NP-Completa:
Os autores investigam o caso unário (tamanho de alfabeto 1), que é teoricamente a variante "mais fácil".
- Eles provam que a tokenização direta unária é fortemente NP-completa. Isso é alcançado via uma redução do problema Vertex Cover. A prova estabelece que a dureza é intrínseca à estrutura do problema e não um artefato da representação da entrada (string vs. comprimento da string).
- Para a tokenização bottom-up unária, o artigo estabelece que uma variante conhecida como tokenização de Codificação de Par Ótimo (OPE) é (pelo menos) fracamente NP-completa, via uma redução do problema de Cadeia de Adição (Addition Chain). A complexidade da tokenização bottom-up unária padrão permanece uma questão em aberto neste trabalho.
Hierarquia de Dureza:
O artigo estabelece uma hierarquia clara: se a tokenização $n$ -ária é difícil, então a tokenização $n'$ -ária para todo $n' > n$ também é difícil. Consequentemente, os resultados de dureza para os casos binário e unário estendem-se trivialmente a todos os alfabetos limitados maiores (incluindo alfabetos de bytes e Unicode).

Significância e Alegações
O artigo alega que estes resultados alteram fundamentalmente a compreensão da complexidade da tokenização. Ao provar que a tokenização permanece difícil mesmo sobre alfabetos unários e binários, os autores demonstram que a intratabilidade computacional não é um artefato de alfabetos grandes ou operações de fusão complexas. Em vez disso, é uma barreira fundamental inerente ao problema de comprimir dados de forma ótima via tokenização.

Estas descobertas fornecem uma justificativa teórica para o motivo pelo qual os algoritmos práticos atuais, como Byte-Pair Encoding (BPE) e UnigramLM, dependem de heurísticas e estratégias gulosas (greedy) em vez de otimização exata. O artigo conclui que pesquisas futuras devem focar no desenvolvimento de algoritmos de aproximação comprovadamente bons ou no relaxamento das restrições do problema, uma vez que encontrar tokenizadores ideais exatos é provavelmente impossível para qualquer tamanho de conjunto de dados não trivial.

Mais como este