Trie automata: novo método acelera decodificação restrita em LLMs

O que aconteceu

O artigo "Trie Automata for Constrained Decoding over Large Finite Sets" (arXiv:2608.12574) foi submetido em 12 de agosto de 2026. Os autores propõem um mecanismo chamado trie automaton, que explora a estrutura de conjuntos finitos de strings válidas — prefixos compartilhados, profundidade limitada e cardinalidade conhecida — para pré-computar máscaras de tokens por nó, usando correspondência de múltiplos padrões Aho-Corasick.

Em comparação com o XGrammar, um dos principais backends de geração restrita em vLLM e SGLang, o trie obteve 7 vezes mais rapidez no cálculo por passo de tokens válidos (0,65 microssegundos contra 5,8) e compilação de 2 a 6,5 vezes mais rápida para conjuntos com 300 ou mais valores (K ≥ 300). No teste de atendimento em lote com batch size 256, o throughput ponta a ponta no vLLM chegou a 219 req/s, contra 7,5 req/s do XGrammar — uma diferença de 29 vezes.

Contexto

LLMs cada vez mais precisam gerar saídas estruturadas que respeitem esquemas predefinidos, como selecionar uma string de um conjunto finito de valores. Sistemas atuais de decodificação restrita dependem de compilação de gramática de propósito geral, que se torna lenta conforme o número de valores cresce para milhares — o chamado "cardinality wall". O trie automaton contorna esse problema ao pré-processar a estrutura do conjunto, eliminando o custo de navegação por gramática a cada passo de decoding.

Por que importa

Como as máscaras são pré-computadas, o caminho de inferência fica sem estado, dispensando o pipeline de guided decoding. Essa diferença arquitetural explica o ganho de 29 vezes em batch serving: o speedup algorítmico se soma à economia de integração que só é possível com máscaras prontas. Para aplicações em produção, isso significa reduzir drasticamente a latência e aumentar a vazão em sistemas que exigem saídas estritamente formatadas — como APIs de dados estruturados, geração de código e automação de fluxos empresariais.

Impacto

O método manteve compilação abaixo de 100ms para conjuntos de até 10.000 valores, com custo por passo constante independentemente do tamanho do conjunto, em sete famílias de tokenizadores com vocabulários de 32 mil a 262 mil tokens. Além disso, garantiu 100% de validade das saídas, o que elimina a necessidade de retry ou pós-processamento. Esses resultados tornam o trie automaton atraente para cargas de trabalho de alta demanda, oferecendo desempenho previsível mesmo com grandes conjuntos de valores.

O que muda

Para equipes que integram vLLM ou SGLang, a nova abordagem pode simplificar a implantação de sistemas de decodificação restrita. O trie automaton oferece uma alternativa mais rápida e escalável aos métodos baseados em gramática, reduzindo tempo de compilação e custo por token. A garantia de validade total também reduz complexidade operacional em cenários onde erros de formato eram comuns.

O que vem agora

O estudo está disponível como pré-print no arXiv, mas ainda não há informações sobre liberação de código ou integração oficial nos projetos vLLM e SGLang. É provável que as equipes dessas ferramentas avaliem o método para incorporá-lo em futuras versões. A comunidade acadêmica e a indústria devem, nos próximos meses, testar a técnica em casos reais e comparar com outras estratégias de decodificação restrita.