Resumo Técnico: Tokenização BPE Incremental

Declaração do Problema

Os pipelines modernos de Grandes Modelos de Linguagem (LLMs) dependem fortemente da Codificação de Par de Bytes (BPE) para a tokenização. No entanto, as implementações de estado da arte atuais (por exemplo, tokenizers da Hugging Face e tiktoken da OpenAI) são predominantemente projetadas como processos offline. Elas exigem que a sequência de entrada inteira ou um fragmento pré-segmentado seja totalmente observado antes de produzir uma tokenização canônica. Essa limitação arquitetural força a tokenização e o preenchimento inicial (pre-filling) do modelo a executarem sequencialmente, em vez de concorrentemente, introduzindo latência em cenários de streaming e de inferência de contexto longo.

Além disso, as implementações existentes frequentemente dependem de filas de prioridade baseadas em heap para selecionar fusões (merges) sobre todo o input, resultando em formulações que são inerentemente globais e difíceis de adaptar para atualizações byte a byte. Embora algumas ferramentas utilizem a pré-segmentação baseada em regex para limitar os custos de fusão, essa abordagem pode ser frágil, levando à degradação de desempenho ou exaustão de pilha em entradas patológicas (por exemplo, repetições extensas de caracteres), onde algumas ferramentas exibem comportamento $O(n^2)$.

Metodologia

Os autores propõem um novo algoritmo para tokenização BPE incremental que mantém os resultados da tokenização BPE para cada prefixo da sequência de texto em tempo real. A abordagem é fundamentada nas propriedades estruturais do BPE e introduz várias inovações algorítmicas chave:

1. Fundamentos Estruturais

• Consistência de Prefixo: Aproveitando a propriedade de que uma tokenização BPE válida pode ser livremente truncada, o algoritmo modela a tokenização de uma string crescente como uma extensão da tokenização válida anterior de um prefixo mais curto, em vez de uma recomputação.
• Último Token ($\theta(s)$): O algoritmo foca em manter o "Último Token" da string atual $s$. A tokenização completa é implicitamente codificada pela sequência de últimos tokens, recuperável via retrocesso (backtracking).
• Floresta de Sucessores & Árvore de Sufixo-Sucessor: O vocabulário é normalizado para tokens canônicos, formando uma estrutura topológica chamada Floresta de Sucessores. Para qualquer input, o espaço de busca para o novo último token é confinado a uma Árvore de Sufixo-Sucessor, que organiza todos os potenciais tokens de sufixo.

2. A Propriedade do Caminho Monotônico

Uma contribuição teórica central é a Propriedade do Caminho Monotônico, que estabelece que, para qualquer string de entrada, o conjunto de tokens de sufixo capazes de servir como o último token forma um caminho único e contínuo dentro da Árvore de Sufixo-Sucessor. Este caminho está ancorado na raiz (o token atômico) e se estende até o verdadeiro último token $\theta(s)$. Esta propriedade reduz o espaço de busca de toda a árvore para um único caminho, permitindo uma verificação eficiente.

3. Implementação Algorítmica

O processo de atualização incremental envolve duas etapas principais:

1. Identificação do Espaço de Busca: Usando um autômato de Aho–Corasick aumentado com ladrilhamento de raiz quadrada persistente, o algoritmo identifica o token de sufixo mais longo $\tau(sc)$ em $O(1)$ de tempo, definindo a Árvore de Sufixo-Sucessor delimitadora.
2. Busca de Extensão de Caminho: Para encontrar o nó mais profundo válido no caminho monotônico, o algoritmo emprega Decomposição de Centróide. Ele percorre uma Árvore de Busca de Centróides (CST) pré-computada de altura $O(\log |\tau|)$. Em cada etapa, ele verifica a Condição de Último-Token de Prefixo (checando alcançabilidade e dominância de prioridade) usando intervalos de linearização DFS. Isso permite que o algoritmo determine a direção do caminho válido em $O(\log |\tau|)$ de tempo.

4. Mecanismo de Saída Ansiosa (Eager Output)

Para suportar streaming real, os autores introduzem um algoritmo de saída ansiosa (eager output). Ele identifica a "Fronteira Ativa" da árvore de tokenização — o intervalo de prefixos que poderiam potencialmente se tornar pais de futuros tokens. Ao manter um subgrafo dinâmico desses candidatos, o sistema pode emitir tokens assim que seus limites se tornam invariantes (ou seja, quando todos os caminhos ativos convergem para um único filho da raiz virtual), permitindo o pleno pipelining com a inferência do modelo.

Principais Contribuições

• Complexidade Algorítmica: O algoritmo proposto processa cada byte de entrada com uma complexidade de tempo de pior caso estrita de $O(\log_2 t)$, onde $t$ é o comprimento máximo do token. Isso resulta em uma complexidade total de $O(n \log_2 t)$ para um input de comprimento $n$.
• Capacidade de Streaming: O método funciona como um substituto direto (drop-in replacement) para as etapas padrão de BPE, permitindo uma tokenização parcial eficiente em cenários de streaming sem alterar a correção das etapas de pré-processamento circundantes.
• Saída Ansiosa: A introdução de um mecanismo de saída ansiosa permite o streaming real e o pipelining com a inferência do modelo, emitindo tokens imediatamente após a resolução de fronteiras.
• Robustez: Diferente de ferramentas existentes que podem degradar para $O(n^2)$ em entradas patológicas, esta abordagem mantém garantias de desempenho estáveis.
• Suporte a Prefixo Total: O algoritmo suporta naturalmente cenários que exigem acesso às tokenizações de todos os prefixos (por exemplo, tarefas de "fill-in-the-middle" ou correção de tokens) sem truncamento heurístico ou recomputação.

Resultados

Os autores implementaram o algoritmo em Rust e realizaram testes comparativos contra os tokenizers da Hugging Face e o tiktoken da OpenAI.

• Vazão (Throughput): A abordagem incremental alcança um aumento de velocidade de ponta a ponta de até $\sim 3\times$ sobre os tokenizadores da Hugging Face, particularmente em cenários que carecem de pré-tokenização baseada em regex (ex: CodeLlama).
• Latência em Entradas Patológicas: Em inputs com repetições extensas, o tiktoken exibe uma queda de vazão consistente com a complexidade $O(n^2)$. Em contraste, o método proposto mantém uma vazão estável, demonstrando reduções significativas de latência nesses casos patológicos.
• Sobrecarga de Saída Ansiosa: O mecanismo de saída ansiosa introduz uma sobrecarga de aproximadamente 10% na vazão de ponta a ponta em comparação com a versão incremental não-ansiosa, um custo que os autores observam que pode ser amortizado em sistemas onde a tokenização é colocada em pipeline com I/O ou inferência.

Significância e Alegações

O artigo demonstra que a tokenização BPE pode ser realizada incrementalmente com garantias de pior caso estritas, mantendo a compatibilidade semântica exata com o BPE padrão.

Os autores alegam que seu trabalho preenche a lacuna entre formalismos teóricos (que sugerem estabilidade de prefixo) e a engenharia prática (que tem dependido de processamento global e offline). Ao fornecer um algoritmo com complexidade $O(n \log_2 t)$, o trabalho possibilita:

1. Redução de Latência: Ao permitir que a tokenização seja totalmente integrada via pipeline com a inferência do modelo, removendo o gargalo sequencial na inferência de streaming.
2. Robustez do Sistema: Ao mitigar o risco de ataques de complexidade algorítmica (ex: Negação de Serviço via inputs criados) que exploram as vulnerabilidades $O(n^2)$ dos tokenizadores atuais.
3. Otimização de Pipeline: Ao tornar certas etapas de pré-segmentação (projetadas apenas para limitar os custos globais de BPE) algoritmicamente redundantes, permitindo designs de pipeline mais limpos e eficientes.

Os autores concluem que sua abordagem pavimenta o caminho para pipelines de LLM mais robustos, responsivos e energeticamente eficientes, ao traduzir garantias algorítmicas estritas em benefícios práticos de latência.