💻 computer science

Trie Automata for Constrained Decoding over Large Finite Sets

Este artigo introduz o autômato de trie, um mecanismo especializado que utiliza o Aho-Corasick de correspondência de múltiplos padrões para pré-computar máscaras de tokens para decodificação com restrição de conjunto finito, alcançando até 29x mais throughput e uma compilação significativamente mais rápida em comparação com sistemas existentes como o XGrammar, enquanto garante 100% de validade de saída.

Autores originais: Xingzi Xu, Karim Bouyarmane

Publicado 2026-08-14

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Xingzi Xu, Karim Bouyarmane

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 um mundo onde os computadores são como chefs incrivelmente talentosos, mas ligeiramente caóticos. Eles podem escrever histórias, resolver problemas matemáticos e até programar softwares, mas têm o mau hábito de inventar coisas. Se você pedir para eles listarem as capitais do mundo, eles podem inventar confiantemente uma cidade chamada "Nárnia" ou errar a grafia de "Paris". Para impedir isso, os cientistas usam uma técnica chamada decodificação com restrição (constrained decoding). Pense nisso como dar ao chef um livro de receitas rigoroso. Em vez de deixar o chef escolher qualquer ingrediente de todo o universo, o livro de receitas diz: "Você só pode usar farinha, açúcar ou ovos". O computador verifica cada palavra que deseja escrever contra essa lista para garantir que não invente acidentalmente um novo ingrediente.

Isso funciona muito bem quando a lista é curta, como uma receita com três ingredientes. Mas e se a lista for enorme? Imagine uma receita que diz: "Você pode usar quaisquer dos 10.000 temperos diferentes do mundo", ou "Você pode escolher quaisquer das 50.000 ferramentas em uma oficina gigante". Verificar uma lista de três itens é fácil. Verificar uma lista de 50.000 itens toda vez que o computador pensa em uma nova palavra é como tentar encontrar uma agulha específica em um palheiro que fica cada vez maior. O computador fica tão sobrecarregado verificando a lista que para de cozinhar completamente, ou demora tanto que a comida esfria. Este é o problema que os pesquisadores estão tentando resolver: como manter o computador rápido e preciso mesmo quando a "lista proibida" é massiva.

A Grande Biblioteca das Palavras Proibidas

Neste artigo, os pesquisadores apresentam uma ferramenta nova e inteligente chamada Autômato de Trie (Trie Automaton). Para entender por que isso é um divisor de águas, vamos observar como o método antigo funcionava. Imagine que o computador é um segurança na porta de uma biblioteca enorme. Toda vez que o computador quer dizer uma palavra, o segurança tem que percorrer um longo corredor, verificar um livro de registros gigante e empoeirado (a lista de 10.000 palavras válidas) e ver se a palavra é permitida. Se a lista for enorme, o segurança passa todo o tempo correndo de um lado para o outro, e a fila de pessoas esperando para entrar (os pensamentos do computador) fica travada. Isso é o que o artigo chama de "parede de cardinalidade" (cardinality wall) — um ponto onde a lista fica tão grande que o sistema simplesmente trava ou fica extremamente lento.

Os pesquisadores perceberam que o método antigo tratava cada lista como um amontoado aleatório de palavras. Mas, no mundo real, as listas não são aleatórias. Pense em uma lista de nomes de ferramentas: "aws.create_user", "aws.delete_user", "aws.list_user". Todas começam com "aws.". Depois, todas têm "create", "delete" ou "list". Elas compartilham muitas das mesmas partes iniciais, como ramos em uma árvore. O antigo segurança não percebia isso; ele verificava cada palavra do zero todas as vezes.

O novo Autômato de Trie é como um bibliotecário superinteligente que constrói um mapa especial da biblioteca. Em vez de um corredor longo, o bibliotecário constrói um caminho em forma de árvore.

O Mapa: Eles desenham um caminho para "aws.". Uma vez que você está no caminho "aws.", você não precisa mais verificar "aws.". Você apenas olha para a próxima bifurcação no caminho: "create", "delete" ou "list".
A Pré-verificação: Aqui está o truque de mágica. Antes mesmo de o computador começar a falar, o bibliotecário pré-calcula exatamente quais palavras são permitidas em cada bifurcação da árvore. Eles escrevem essas respostas em pequenos post-its e os colam diretamente nos ramos da árvore.
A Velocidade: Agora, quando o computador quer falar, o bibliotecário não corre para o livro de registros. Ele apenas olha para o post-it no ramo atual. "Ah, você está no ramo 'aws'? O bilhete diz que você só pode dizer 'create', 'delete' ou 'list' em seguida". Isso leva uma fração de segundo.

Os Resultados: De um Caracol a um Foguete

Os pesquisadores testaram este novo sistema contra os melhores métodos atuais (como o XGrammar) usando listas de palavras válidas variando de 10 a 10.000 itens. Os resultados foram dramáticos.

Velocidade de Compilação: Ao construir o mapa para uma lista de 1.000 itens, o sistema antigo levava cerca de 75 milissegundos (uma pequena espera). O novo Autômato de Trie fez isso em cerca de 33 milissegundos. Mas conforme a lista crescia para 10.000 itens, o sistema antigo levava quase 240 milissegundos, enquanto o novo permanecia quase constante em 40 milissegundos. Era como se o sistema antigo estivesse correndo na lama, enquanto o novo estava correndo em uma esteira que não ficava mais difícil, não importa o quão rápido você fosse.
A "Parede de Cardinalidade": Os sistemas antigos começavam a falhar ou a desacelerar drasticamente quando a lista passava de algumas centenas de itens. O novo sistema lidou com listas de 10.000 itens sem fazer esforço, e os pesquisadores mostraram que ele poderia, teoricamente, lidar com até 100.000 itens.
Serviço em Lote (A Grande Vitória): A maior surpresa veio quando testaram o sistema com muitas solicitações simultâneas (como um restaurante movimentado com 256 pedidos). O sistema antigo conseguia processar apenas cerca de 7,5 pedidos por segundo. O novo Autômato de Trie processou 219 pedidos por segundo. Isso é uma melhoria de 29 vezes.

Por que foi tão mais rápido? Não foi apenas o mapa; foi como o mapa foi usado. Como as respostas já estavam escritas nos post-its, o computador não precisava realizar nenhum pensamento ou verificação complexa enquanto falava. Ele podia apenas pegar o bilhete e seguir em frente. Isso permitiu que o computador pulasse uma série de etapas lentas e complicadas que o sistema antigo tinha que realizar a cada vez.

O Que Isso Significa

O artigo prova que, para tipos específicos de listas — como escolher uma ferramenta de um registro, selecionar um código médico ou escolher uma categoria de produto — o antigo método de "verificar tudo" é muito lento. Ao usar a estrutura das palavras (os começos compartilhados) e pré-calcular as respostas, o novo método torna a decodificação com restrição rápida e confiável novamente.

Os pesquisadores foram muito cuidadosos ao notar que este novo método não torna o computador mais inteligente nem altera o que ele diz; ele apenas garante que ele diga apenas o que deve dizer, e o faz incrivelmente rápido. Eles mediram isso em chips de computador reais e descobriram que o novo método é 100% preciso ao seguir as regras, assim como o método antigo, mas o faz 7 vezes mais rápido para cada palavra gerada. Quando você multiplica essa velocidade por centenas de solicitações acontecendo ao mesmo tempo, a diferença é enorme.

Em resumo, o artigo encontrou uma maneira de transformar uma busca caótica e lenta através de um palheiro gigante em uma caminhada rápida e organizada por um caminho pré-iluminado. Ele resolve o problema da "parede de cardinalidade", permitendo que a IA lide com listas massivas de opções sem travar, o que é crucial para o futuro dos agentes de IA que precisam escolher entre milhares de ferramentas ou serviços instantaneamente.

Resumo Técnico: Autômatos de Trie para Decodificação com Restrições sobre Grandes Conjuntos Finitos

1. Declaração do Problema: O Muro da Cardinalidade

Modelos de linguagem de grande escala (LLMs) exigem cada vez mais saídas estruturadas que conformem a esquemas predefinidos, particularmente a seleção de uma string de um conjunto finito conhecido (ex: nomes de ferramentas, códigos médicos, taxonomias de produtos). Sistemas atuais de decodificação com restrições, como o XGrammar e o Outlines, lidam com essas restrições compilando esquemas em autômatos de propósito geral (Máquinas de Estados Finitos, Autômatos de Pilha ou parsers de Earley).

Embora eficaz para gramáticas complexas, essa abordagem de propósito geral cria um "muro da cardinalidade" para restrições de conjuntos finitos simples. À medida que o número de strings válidas ( $K$ ) cresce para milhares, o tempo de compilação e a latência de decodificação por passo tornam-se proibitivamente lentos. Provedores existentes impõem limites estritos (ex: OpenAI em 1.000 enums, Google Gemini em ~120) porque o pipeline de compilação padrão escala mal com $K$ . O problema central é um descompasso fundamental: motores de propósito geral complexos são aplicados a restrições simples (uniões finitas de strings) que possuem estrutura explorável (prefixos compartilhados, profundidade limitada, cardinalidade conhecida).

2. Metodologia: O Autômato de Trie

Os autores introduzem o autômato de trie, um backend especializado para restrições de conjuntos finitos que substitui a camada de FSM de propósito geral. O método aproveita a estrutura do conjunto de restrições para alcançar uma compilação sublinear e uma máscara por passo de tempo constante.

Mecanismos Principais

Construção de Trie ao Nível de Caractere: Em vez de tries ao nível de token (que falham em compartilhar prefixos entre fronteiras de tokens) ou DFAs gerais, o sistema constrói uma trie ao nível de caractere diretamente a partir do conjunto de strings válidas. Isso funde prefixos compartilhados, reduzindo o número de nós de $O(K \cdot L_{max})$ para $O(N_{chars})$ , onde $N_{chars}$ é a contagem total de caracteres.
Alinhamento BPE-Trie via Aho-Corasick: Um desafio central é alinhar a trie de nível de caractere com o vocabulário de Byte-Pair Encoding (BPE) do modelo. Um único token BPE pode abranger múltiplas arestas da trie. Os autores resolvem isso reduzindo o problema à correspondência de strings de múltiplos padrões. Eles constroem um autômmo de Aho-Corasick (AC) a partir dos tokens do vocabulário e percorrem a trie, pré-computando o conjunto de tokens BPE válidos (valid[n]) para cada nó $n$ da trie.
Máscaras Pré-computadas: Durante a compilação, o sistema computa valid[n] para todos os nós. No momento da decodificação, a máscara reduz-se a uma busca direta de $O(1)$ : $A(s_t) = valid[s_t]$ . Isso evita a necessidade de escanear todo o vocabulário ou simular transições para cada token em cada passo.

Vantagens de Complexidade

Compilação: O custo é dominado pela construção do autômato AC sobre o vocabulário, que é $O((N_{chars} + V) \cdot \ell)$ , onde $V$ é o tamanho do vocabulário e $\ell$ é o comprimento máximo do token. Crucialmente, isso é amplamente independente de $K$ uma vez que o autômato AC é construído, levando a tempos de compilação quase constantes (30–67ms) mesmo para $K=10.000$ .
Latência de Decodificação por Passo: O custo cai de $O(V \cdot \ell)$ (escanear todos os tokens) para $O(|valid[s_t]|)$ . Como o conjunto válido diminui exponencialmente com a profundidade da trie (tipicamente 10–100 tokens após 3–4 caracteres), o custo efetivo é constante e extremamente baixo (0,65µs).
Serviço Sem Estado (Stateless): Como as máscaras são pré-computadas, a trie pode operar como um LogitsProcessor sem estado, contornando o gerenciamento de estado do pipeline de decodificação guiada e o overhead de escalonamento exigido por abordagens baseadas em FSM.

3. Principais Contribuições

O Autômato de Trie: Um backend de decodificação com restrições especializado que combina tries de nível de caractere, correspondência de múltiplos padrões Aho-Corasick e máscaras de tokens pré-computadas. Ele alcança uma máscara de $O(|valid[s_t]|)$ por passo, resultando em um custo efetivamente constante versus o custo de $O(V \cdot \ell)$ de abordagens FSM genéricas.
Resolução do Problema de Alinhamento BPE-Trie: O artigo aborda o desafio anteriormente não tratado de alinhar caminhos de trie de nível de caractere com tokens BPE. Ao reduzir isso à correspondência de múltiplos padrões, eles permitem uma compilação sub-100ms até $K=10.000$ através de diversas famílias de tokenizadores.
Caracterização Empírica do Muro da Cardinalidade: Os autores demonstram que o ajuste dos mecanismos de aplicação de regras à estrutura da restrição supera gargalos de escala. Eles mostram que máscaras pré-computadas permitem um caminho de serviço sem estado que abordagens FSM não podem utilizar, multiplicando ganhos algorítmicos em ganhos massivos de throughput.

4. Resultados Experimentais

Experimentos foram conduzidos em GPUs NVIDIA A100 usando sete famílias de tokenizadores (vocabulários de 32K–262K) e modelos incluindo Qwen3-8B, Mistral e Gemma3.

Velocidade de Compilação: O autômato de trie alcança uma compilação 2–6,5× mais rápida que o XGrammar para $K \ge 300$ . Enquanto a compilação do XGrammar escala linearmente com $K$ (atingindo 2,7s para $K=100.000$ ), a trie permanece plana em ~30–67ms.
Latência por Passo: A trie computa máscaras de tokens válidos em 0,65µs, comparado a 5,8µs para o XGrammar (um ganho de 7×) e 73–141µs para o LLGuidance (110–215× mais lento).
Throughput de Ponta a Ponta: No serviço em lote (vLLM), a vantagem se acumula. Com um tamanho de lote de 256, a trie alcança 219 req/s contra os 7,5 req/s do XGrammar (melhoria de 29×). Este ganho provém do ganho algorítmico de 7× somado à eliminação do overhead do pipeline de decodificação guiada.
Validade e Precisão: A trie garante 100% de validade de saída. Em benchmarks de classificação (TREC, MASSIVE, Banking77, CLINC150), a decodificação com restrições usando a trie iguala ou supera a precisão sem restrições enquanto elimina alucinações. Para modelos mais fracos, a trie atua como um habilitador crítico, melhorando a precisão de 4,8% para 24,8% no Banking77 ao garantir saídas válidas.
Escalabilidade: O método mantém a compilação abaixo de 100ms e custos por passo planos até $K=10.000$ e além, expandindo efetivamente o limite prático de enums de ~1.000 para ~100.000.

5. Significância e Alegações

O artigo afirma que o autômato de trie resolve uma ineficiência fundamental na decodificação com restrições: a aplicação de autômatos de propósito geral a restrições simples e estruturadas. Ao explorar a estrutura específica de conjuntos finitos (prefixos compartilhados), os autores demonstram que:

Eficiência Algorítmica: A trie é o algoritmo eficiente para pré-computar máscaras por estado sobre conjuntos finitos, superando a pré-computação equivalente de FSM por 196× em tempo de compilação.
Impacto Sistêmico: A capacidade de pré-computar máscaras permite um caminho de serviço sem estado que contorna o pipeline de decodificação guiada, um benefício que apenas máscaras pré-computadas tornam possível. Isso transforma a decodificação com restrições de um gargalo em um overhead negligenciável em serviço em lote.
Generalização: O princípio de ajustar os mecanismos de aplicação às estruturas de restrição (ex: usar máscaras de posição de caractere para formatos fixos) gera grandes ganhos de velocidade para qualquer restrição com regularidade explorável, não apenas para conjuntos finitos.

Os autores posicionam o autômato de trie não como uma aproximação, mas como uma alternativa exata e isomórfica para a decodificação baseada em FSM para conjuntos finitos, oferecendo 100% de validade com melhorias de desempenho de ordens de magnitude em cenários de alta cardinalidade.