🤖 AI

Accelerating Constrained Decoding with Token Space Compression

Este artigo apresenta o CFGzip, uma técnica de compressão offline do espaço de tokens que reduz significativamente a sobrecarga computacional da decodificação restrita, alcançando até 7,5 vezes de aceleração no tempo total de geração para gramáticas livres de contexto complexas.

Autores originais: Michael Sullivan, Alexander Koller

Publicado 2026-05-29

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Michael Sullivan, Alexander Koller

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ê tem um chef muito talentoso, mas um pouco caótico (o LLM) que consegue cozinhar quase qualquer coisa. No entanto, você precisa que ele prepare um prato que siga uma receita muito estrita e complexa (uma Gramática Livre de Contexto ou CFG), como uma linguagem de programação específica ou um formato de dados preciso.

Se o chef adivinhar o ingrediente errado, todo o prato é estragado. Para evitar isso, você contrata um Motor de Gramática rigoroso (como um chef de cozinha ou um inspetor de segurança alimentar) que fica ao lado do chef. Antes de o chef adicionar qualquer ingrediente, o inspetor verifica toda a despensa para ver se aquele ingrediente específico é permitido neste exato passo da receita.

O Problema: A "Despensa" é Grande Demais

O problema é que a despensa do chef (o vocabulário de tokens) é massiva, contendo centenas de milhares de ingredientes diferentes (palavras, símbolos, trechos de código).

Toda vez que o chef quer adicionar um ingrediente, o inspetor precisa percorrer toda a despensa para verificar se aquele item específico é válido. Para receitas simples (como dados JSON), isso é rápido. Mas para receitas complexas (como código C++ ou uma linguagem inventada chamada "Bython"), o inspetor fica sobrecarregado. Ele precisa verificar tantas possibilidades que o processo de cozimento fica drasticamente mais lento — às vezes levando 2 a 10 vezes mais do que o normal. O artigo chama isso de "sobrecarga intratavelmente alta".

A Solução: CFGZIP (O Truque de "Agrupamento")

Os autores apresentam uma nova ferramenta chamada CFGZIP. Em vez de fazer o inspetor verificar cada ingrediente individual na despensa, o CFGZIP reorganiza a despensa antes mesmo do cozimento começar.

Aqui está a analogia:

Agrupando Ingredientes: O CFGZIP olha para a despensa e percebe que muitos ingredientes são intercambiáveis para o propósito da receita. Por exemplo, em uma parte específica de uma receita de código, as palavras if, else e while podem todas atuar da mesma maneira gramaticalmente. Ou, em um contexto diferente, os números 1, 2 e 3 podem ser todos marcadores válidos.
Criando Baldes "Representativos": O CFGZIP agrupa esses ingredientes intercambiáveis em baldes. Ele escolhe um ingrediente "representativo" de cada balde (geralmente o mais curto) para representar todo o grupo.
O Novo Fluxo de Trabalho:
- Antes do Cozimento (Offline): O sistema faz o trabalho pesado de classificar a despensa nesses baldes. Isso é feito uma vez e salvo.
- Durante o Cozimento (Inferência): Quando o chef escolhe um ingrediente, o sistema o troca rapidamente pelo seu "representante" do balde. O inspetor só precisa verificar o representante contra a receita, não a despensa inteira.
- O Resultado: Como o inspetor agora está verificando uma lista minúscula de representantes em vez da despensa original massiva, o processo torna-se incrivelmente rápido.

Por Que Isso é Importante

O artigo afirma que usar o CFGZIP com um motor de gramática de ponta (XGrammar2) cria uma aceleração massiva:

Redução de Latência: O tempo necessário para verificar as regras cai de 10 a 100 vezes (duas ordens de grandeza).
Aceleração Total: Todo o processo de geração de texto torna-se 7,5 vezes mais rápido para tarefas complexas.
Sem Perda de Qualidade: Esta é uma compressão "sem perdas". A saída final é byte a byte idêntica ao que você obteria sem a aceleração. O chef ainda produz o prato perfeito exato; ele apenas chegou lá muito mais rápido.

Resultados do Mundo Real do Artigo

Os pesquisadores testaram isso em três modelos de IA diferentes (Llama, Qwen e GPT) e quatro tarefas diferentes:

JSON & XML: Formatos de dados padrão.
C++: Uma linguagem de programação complexa.
Bython: Uma linguagem de programação fictícia e inventada (semelhante ao Python, mas com chaves e ponto e vírgula em vez de espaços).

As Descobertas:

Para formatos padrão (JSON), a aceleração foi boa, mas não revolucionária, porque essas regras já são simples.
Para linguagens complexas e desconhecidas (como C++ e Bython), a diferença foi enorme. Sem o CFGZIP, o motor de gramática era tão lento que tornava a IA praticamente inutilizável para essas tarefas. Com o CFGZIP, a IA podia gerar código complexo rapidamente e corretamente.
Curiosamente, para a tarefa "Bython" (que a IA nunca tinha visto antes), usar esse método restrito melhorou a capacidade da IA de escrever código funcional de 2,3% para 46,9% (para um modelo), provando que regras estritas ajudam a IA quando a tarefa é difícil.

O Problema (Limitações)

O artigo aponta uma limitação principal: Tempo de Preparação.
Classificar a despensa em baldes (o "pré-cálculo offline") leva tempo.

Se você precisar gerar um arquivo JSON para uma tarefa única e rápida, o tempo que leva para classificar a despensa pode ser maior do que apenas fazer a tarefa normalmente.
No entanto, se você estiver fazendo geração de código em larga escala ou usando as mesmas regras complexas repetidamente, o tempo inicial de configuração vale a pena porque o cozimento (geração) torna-se muito mais rápido.

Resumo

CFGZIP é como um bibliotecário inteligente que reorganiza uma biblioteca massiva em "baldes de tópicos" antes de você chegar. Em vez de você procurar em cada livro individual para encontrar o certo, o bibliotecário apenas aponta para o "representante do balde de tópicos". Isso torna a busca pela informação correta (ou, neste caso, a geração do código correto) dramaticamente mais rápida, sem nunca perder um único livro ou alterar a história.

Resumo Técnico: Aceleração de Decodificação Restrita com Compressão do Espaço de Tokens (CFGZIP)

Declaração do Problema

Modelos de Linguagem de Grande Escala (LLMs) são frequentemente exigidos a gerar texto que obedeça a estruturas específicas, como JSON, XML ou linguagens de programação específicas de domínio. Embora os LLMs se saiam bem em formatos comuns encontrados em seus dados de treinamento, eles têm dificuldade com formatos novos ou complexos. Para garantir a correção sintática, são empregados motores de Decodificação Restrita. Esses motores utilizam Gramáticas Livres de Contexto (CFGs) para mascarar tokens inválidos a cada etapa de geração.

No entanto, os motores de gramática mais avançados (SoTA) atuais (por exemplo, XGrammar2) enfrentam um gargalo de desempenho significativo. Embora otimizados, eles devem validar tokens contra todo o vocabulário de tokens a cada etapa de decodificação. Para CFGs complexas (por exemplo, C++ ou linguagens personalizadas), isso resulta em sobrecarga proibitiva, fazendo com que a latência de inferência aumente de 2x a 10x em comparação com a geração sem restrições. Essa latência torna a decodificação restrita inviável para aplicações em grande escala que envolvem gramáticas complexas.

Metodologia: CFGZIP

Os autores introduzem o CFGZIP, uma técnica offline projetada para comprimir o espaço de busca de tokens, reduzindo assim o tempo de execução por etapa do motor de gramática sem sacrificar a correção.

Conceito Central: Classes de Equivalência

A ideia fundamental do CFGZIP é que muitos tokens em um vocabulário são intercambiáveis em relação a uma CFG específica. Se dois tokens $t$ e $u$ são "sintaticamente congruentes", eles podem ser trocados em qualquer string válida da linguagem $L(G)$ sem afetar a validade. Consequentemente, o motor de gramática precisa apenas verificar a validade de um token representante por classe de equivalência, em vez de cada token individual.

O Pipeline

Pré-computação Offline:
- Aproximação: Como a congruência sintática exata é indecidível para CFGs arbitrárias, o CFGZIP computa uma aproximação tratável chamada Equivalência de Deslocamento ( $\sim_{L(G)}$ ).
- Mecanismo: A CFG é convertida para a Forma Normal de Greibach (GNF) para utilizar um Autômato com Pilha (PDA). Para cada token, o sistema computa seu "deslocamento" $\Delta_G(t)$ , definido como o conjunto de transições de pilha de entrada/saída que o token induz no PDA. Tokens com conjuntos de deslocamento idênticos são agrupados na mesma classe de equivalência.
- Otimização: Para tornar isso computacionalmente viável, os autores restringem a operação de retrocesso da pilha usando uma relação de adjacência de pilha pré-computada, prevenindo o estouro de memória em gramáticas grandes.
- Cache: O sistema mapeia IDs de tokens para IDs de classe e seleciona um token de byte mais curto como o "representante" para cada classe. Esses mapeamentos são armazenados em cache no disco.
Operação em Tempo de Inferência:
- Redução de Vocabulário: O motor de gramática é inicializado com o vocabulário de representantes de classe de equivalência em vez do vocabulário completo de tokens.
- Mapeamento de Tokens: Quando o LLM amostra um token, o CFGZIP mapeia-o para seu representante de classe e passa esse representante ao motor de gramática para atualizar o estado do analisador.
- Mascaramento: O motor de gramática produz uma máscara de validade sobre o conjunto menor de representantes. Essa máscara é então "coletada" e aplicada aos logits originais do LLM. Esta operação é paralelizável em GPUs e incorre em sobrecarga mínima.

Propriedades Principais

Sem Perdas: A compressão é comprovadamente sem perdas; as saídas de um motor equipado com CFGZIP são idênticas em bytes às do motor original.
Independente do Motor: Teoricamente compatível com qualquer motor de gramática, embora o artigo se concentre no XGrammar2.
Offline: O processamento pesado ocorre uma vez por par tokenizador/CFG, incorrendo em sobrecarga virtualmente nula durante a inferência.

Resultados Experimentais

Os autores avaliaram o CFGZIP acoplado ao XGrammar2 em Llama-3.2-3B, Qwen3-4B e gpt-oss-20B em quatro tarefas: Esquema JSON, XML, C++ e Bython (uma variante personalizada de Python baseada em chaves).

Redução de Latência: O CFGZIP reduziu a sobrecarga do motor de gramática em uma a duas ordens de magnitude.
- Para C++, o tempo total de inferência foi quase reduzido à metade.
- Para Bython (uma linguagem complexa e de baixo recurso), o tempo total de geração restrita foi reduzido por um fator de ~7,5x.
Correção: O CFGZIP manteve 100% de correção sintática (idêntico em bytes ao motor de base).
- Correção Funcional: A decodificação restrita melhorou significativamente a correção funcional, particularmente para a tarefa Bython, onde modelos sem restrições lutaram (por exemplo, o GPT-20B melhorou de 10,8% para 46,9% de correção funcional).
Razões de Compressão: A técnica alcançou razões de compressão variando de 40:1 (Llama-3B/C++) a 800:1 (GPT-20B/JSON), reduzindo drasticamente o tamanho do vocabulário que o motor deve processar.

Significado e Alegações

O artigo afirma que o CFGZIP torna a decodificação restrita viável em escala para CFGs complexas.

Preenchendo a Lacuna: Enquanto motores SoTA são eficientes para gramáticas simples (como JSON), eles introduzem latência intratável para gramáticas complexas (como C++). O CFGZIP reduz essa sobrecarga para níveis quase negligenciáveis, desbloqueando os benefícios de desempenho da decodificação restrita para esses casos difíceis.
Custo-Efetividade: Os resultados sugerem que, para modelos menores e mais baratos, a decodificação restrita pode ser uma alternativa viável ao uso de modelos maiores para alcançar alta correção funcional.
Praticidade: Ao desacoplar o trabalho pesado para uma fase de pré-computação offline, o CFGZIP habilita aplicações em tempo real que exigem adesão estrita a linguagens específicas de domínio complexas sem sacrificar a velocidade.

Limitações

Os autores observam que o CFGZIP não é uma solução universal para todos os cenários:

Contextos Dinâmicos: O tempo de pré-computação offline (variando de segundos a minutos) torna-o menos adequado para CFGs dinâmicas de uso único (por exemplo, esquemas JSON ad hoc ou chamadas de função) onde motores como o llguidance já são altamente otimizados.
Compatibilidade com Motores: Embora teoricamente independente do motor, a implementação atual é baseada em Python e integrada ao XGrammar2. Não é compatível com motores exclusivos de C++ como llama.cpp (devido à falta de bindings Python) ou motores que não suportam as CFGs específicas usadas (por exemplo, gramáticas recursivas à esquerda em transformers-cfg).
Escopo: O método é mais adequado para CFGs estáticas, grandes e complexas, como as usadas na geração de código.