💬 NLP

Constrained Adaptive Rejection Sampling

O artigo apresenta o Constrained Adaptive Rejection Sampling (CARS), um método que aumenta a eficiência de amostragem da geração de modelos de linguagem sob restrições estritas ao podar adaptativamente continuações inválidas por meio de um trie, preservando assim a distribuição original enquanto melhora as taxas de aceitação e a diversidade em comparação com abordagens gananciosas ou de rejeição padrão existentes.

Autores originais: Paweł Parys, Sairam Vaidya, Taylor Berg-Kirkpatrick, Loris D'Antoni

Publicado 2026-06-04

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Paweł Parys, Sairam Vaidya, Taylor Berg-Kirkpatrick, Loris D'Antoni

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á ensinando um chef muito talentoso, mas levemente caótico (o Modelo de Linguagem), a cozinhar um prato específico e complexo (um output válido) baseado em um livro de receitas rigoroso (as restrições). O chef é ótimo em improvisar, mas frequentemente ignora as regras, adicionando ingredientes que tornam o prato impossível de comer ou estruturalmente inviável.

O artigo apresenta um novo método chamado CARS (Amostragem de Rejeição Adaptativa Constrita) para corrigir esse problema. Para entender por que o CARS é especial, vamos olhar para as duas formas antigas de resolver isso e por que ambas falham.

As Formas Antigas: Duas Estratégias Falhas

1. O Método do "Jogar Fora" (Amostragem de Rejeição)
Imagine que o chef cozinha uma refeição completa, você verifica a receita e, se estiver errada, joga a panela inteira no lixo e pede para ele começar de novo.

O Problema: Se a receita for muito rigorosa (como uma linguagem de programação complexa), o chef pode cozinhar 999 refeições ruins antes conseguir uma certa. Você desperdiça uma quantidade massiva de tempo e energia jogando comida fora.
O Lado Bom: A única refeição que é servida é perfeita e tem exatamente o sabor que o chef pretendia.

2. O Método da "Mão Suspensa" (Decodificação Gananciosa/Greedy Decoding)
Imagine que você fica de pé sobre o ombro do chef. Toda vez que ele tenta pegar um ingrediente que quebra as regras, você dá um tapa na mão dele e o força a escolher um ingrediente diferente.

O Problema: O chef para de cozinhar naturalmente. Ele se torna robótico, escolhendo apenas ingredientes "seguros". A refeição resultante pode até ser comestível, mas não tem mais o estilo único do chef; ela foi distorcida.
O Lado Bom: Você obtém uma refeição válida muito rapidamente, com quase nenhum desperdício.

A Nova Solução: CARS (O "Anotador Inteligente")

Os autores propõem o CARS, que combina o melhor dos dois mundos: mantém o estilo natural do chef (fidelidade), mas impede o desperdício de tempo com pratos impossíveis (eficiência).

Aqui está como o CARS funciona, usando uma analogia de uma Biblioteca de Caminhos Proibidos:

Começar a Cozinhar: O chef começa a cozinhar naturalmente, assim como no método "Jogar Fora".
O Erro: Suponha que o chef tente fazer uma frase que começa com 0++ (que é matematicamente inválida). O sistema detecta isso.
A Anotação Inteligente: Em vez de apenas jogar fora essa frase específica, o sistema abre um Trie (um tipo especial de caderno em forma de árvore). Ele escreve: "Qualquer prato que comece com 0++ é impossível."
O Efeito Cascata: Crucialmente, o sistema também percebe que qualquer prato que comece com 0+ seguido de outro + também está fadado ao fracasso. Ele marca todos esses ramos da árvore como "Proibidos".
Cozinhando no Futuro: Na próxima vez que o chef começar a cozinhar, ele consulta este caderno. Se ele tentar escolher um ingrediente que leve a um ramo "Proibido", o sistema o desvia gentilmente antes que ele perca tempo cozinhando toda a refeição ruim.
O Resultado: O chef nunca mais cozinha uma refeição ruim. Ele cozinha mais rápido porque não perde tempo em becos sem saída, mas quando cozinha, ainda é 100% o seu próprio estilo natural, não uma imitação forçada.

Por que isso é importante?

O artigo testou o CARS em três cenários do mundo real onde você precisa gerar muitas coisas diferentes que sejam válidas:

Fuzzing de Programas (Encontrando Bugs): Imagine tentar quebrar um software alimentando-o com milhões de entradas diferentes. Você precisa de entradas que sejam códigos válidos, mas também estranhas o suficiente para travar o sistema. O CARS encontrou mais bugs (cobriu mais linhas de código) do que os métodos antigos porque conseguia gerar entradas válidas e diversas muito mais rápido, sem ficar preso.
Descoberta Molecular (Design de Drogas): Químicos precisam gerar estruturas químicas válidas. O CARS gerou moléculas válidas e diversas muito mais rápido do que os métodos anteriores, economizando enormes quantidades de poder computacional.
Text-to-SQL (Transformar Perguntas em Consultas de Banco de Dados): Ao fazer uma pergunta a um banco de dados, a resposta deve ser uma consulta SQL perfeita. O CARS produziu as consultas mais precisas com o menor número de tentativas.

A Conclusão

Pense no CARS como um filtro de aprendizado.

Métodos antigos ou desperdiçavam tempo jogando fora tentativas ruins (Amostragem de Rejeição) ou estragavam a qualidade ao forçar a IA a ser rígida demais (Decodificação Gananciosa).
CARS aprende com cada erro. Ele constrói um mapa de "becos sem saída" para que a IA nunca mais entre neles. Isso significa que você obtém resultados perfeitamente válidos que ainda mantêm a voz natural da IA, mas você os obtém muito mais rápido porque para de gastar energia em caminhos impossíveis.

O artigo afirma que este é o primeiro método que é simultaneamente exato (perfeitamente preciso) e eficiente (rápido) para esses tipos de tarefas rigorosas.

Resumo Técnico: Constrained Adaptive Rejection Sampling (CARS)

1. Definição do Problema

Modelos de Linguagem (LMs) são cada vez mais implantados em aplicações que exigem saídas que satisfaçam restrições semânticas ou sintáticas estritas, como a geração de código sintaticamente válido, a adesão a esquemas de dados ou a produção de estruturas químicas. O desafio central na geração com restrições é equilibrar dois requisitos concorrentes:

Fidelidade: As amostras devem seguir a distribuição condicional exata do LM dado a restrição ( $P_L$ ), em vez de uma aproximação.
Eficiência: O método deve minimizar o número de passagens de ida (forward passes) do LM necessárias para gerar amostras válidas.

As abordagens existentes dividem-se em três categorias, cada uma falhando em atender a ambos os critérios simultaneamente:

Exata, mas Ineficiente: O Rejection Sampling (RS) padrão produz amostras imparciais da verdadeira distribuição restrita, mas descarta a vasta maioria dos candidatos em domínios estruturados (ex: taxas de aceitação <1%), levando a custos computacionais proibitivos.
Eficiente, mas Enviesada: O Greedy Constrained Decoding (GCD) impõe a validade ao mascarar tokens inválidos durante a geração. Embora eficiente, ele distorce comprovadamente a distribuição condicional do LM, frequentemente degradando o desempenho a jusante e potencialmente falhando em terminar.
Assintoticamente Exata, mas Instável: Métodos como MCMC ou Sequential Monte Carlo (SMC) convergem para a distribuição correta no limite, mas não oferecem uma regra de parada fundamentada. As amostras iniciais podem ser arbitrariamente enviesadas, e a eficiência depende fortemente do ajuste de hiperparâmetros e do número de iterações necessárias para a estabilização.

O artigo argumenta que existe uma lacuna para um algoritmo que seja exato (preservando a distribuição verdadeira) e amortizadamente eficiente (melhorando a eficiência ao longo do tempo sem sacrificar a fidelidade), particularmente em domínios que exigem conjuntos diversos de amostras válidas, como fuzzing de programas e descoberta molecular.

2. Metodologia: Constrained Adaptive Rejection Sampling (CARS)

O CARS é um algoritmo de amostragem exata que combina a fidelidade do Rejection Sampling com a eficiência da poda adaptativa. Ele baseia-se no Adaptive Rejection Sampling (ARS), mas o estende aproveitando a estrutura das restrições para podar não apenas amostras rejeitadas, mas famílias inteiras de continuações inválidas.

Mecanismo Central

O algoritmo mantém um conjunto de prefixos inválidos ( $W$ ) descobertos durante o processo de amostragem. Ele utiliza uma estrutura de dados Trie para armazenar esses prefixos e remodelar dinamicamente a distribuição de amostragem ( $R_W$ ) para evitá-los.

Inicialização: O algoritmo começa com um conjunto de prefixos inválidos vazio ( $W = \emptyset$ ).
Amostragem: Em cada iteração, o algoritmo amostra uma sequência de uma distribuição reponderada $R_W$ $R_{W}$ . Esta distribuição é derivada da distribuição original do LM $P$ $P$ ao normalizar sobre sequências que não estendem nenhum prefixo em $W$ $W$ .
- Formalmente, para um prefixo $u$ , a probabilidade de estendê-lo para uma sequência válida é rastreada como $p_u$ . Se $u$ estende um prefixo conhecido como inválido, $p_u = 0$ .
- A probabilidade de amostragem para um token $a$ dado o prefixo $u$ é ajustada: $R_W(ua | u) = P(ua | u) \cdot \frac{p_{ua}}{p_u}$ .
Poda Adaptativa (A Inovação Principal): Quando uma amostra é gerada, o CARS não apenas registra a string rejeitada (como no ARS padrão). Em vez disso, ele identifica todos os prefixos da sequência gerada que violam a restrição e todas as suas continuações inválidas.
- Especificamente, se uma sequência $w$ é gerada, o CARS adiciona ao $W$ o prefixo mais curto $u$ de $w$ que não pertence à linguagem válida $L$ .
- Crucialmente, ele também adiciona todas as extensões $ua$ (onde $a$ é um token) tais que $ua \notin prefix(L)$ .
- Este processo efetivamente "subtrai" a massa de probabilidade de subárvores inteiras de continuações inválidas de sorteios futuros.
Atualização: A Trie é atualizada para refletir os novos prefixos inválidos, e os valores de probabilidade ( $p_u$ ) são propagados para cima. Isso garante que amostras futuras nunca revisitem esses caminhos inválidos, aumentando monotonicamente a taxa de aceitação.

Propriedades Teóricas

Exatidão: O CARS produz amostras exatamente da distribuição restrita alvo $P_L$ . O reponderamento garante que a massa de probabilidade seja redistribuída corretamente entre as sequências válidas.
Monotonicidade: A taxa de aceitação melhora monotonicamente conforme o conjunto $W$ cresce.
Retornos Decrescentes: A massa de probabilidade esperada removida por amostra é não-crescente. Isso sugere uma heurística prática: uma vez que a trie para de remover massa de probabilidade significativa, a distribuição pode ser "congelada" para amostragem subsequente sem perda significativa de eficiência.

3. Principais Contribuições

Design de Algoritmo: Introdução do CARS, um novo algoritmo para geração de LM com restrições que alcança exatidão com eficiência prática ao aproveitar a estrutura de restrições para podar continuações de prefixos inválidos.
Garantias Teóricas: Prova de que o CARS amostra da verdadeira distribuição restrita e que suas atualizações adaptativas aumentam monotonicamente a probabilidade de obter amostras válidas.
Validação Empírica: Demonstração de que o CARS supera os métodos existentes em termos de eficiência de amostragem (menos passagens de ida do LM por amostra válida) e diversidade de amostras em múltiplos domínios.

4. Resultados Experimentais

Os autores avaliaram o CARS em quatro modelos (Llama-3.1-8B/70B, Qwen2.5-7B/14B) em três domínios distintos:

A. Fuzzing Baseado em Gramática

Tarefa: Gerar sementes de programas diversas e válidas (JSON, SQL, XML) para maximizar a cobertura de código em fuzzers.
Resultados: O CARS atingiu a meta de 100 amostras válidas com significativamente menos gerações do que o RS, ARS e RSFT. Por exemplo, na geração de XML sem prompts de gramática, o CARS exigiu ~440 gerações comparado a >2.000 para RS/ARS (que falharam em atingir a meta).
Impacto: As sementes geradas pelo CARS levaram a uma maior cobertura de linhas (~~7.985 linhas) comparado ao GCD (~~7.115) e MCMC (~7.965), demonstrando que a fidelidade da distribuição se traduz em melhor desempenho a jusante.

B. Síntese Molecular

Tarefa: Gerar strings SMILES válidas para classes químicas específicas (Acrilatos, Extensores de Cadeia, Isocianatos).
Resultados: O CARS exigiu 4,3× menos amostras que o RS e 1,3× menos que o ARS para gerar 100 moléculas válidas. Alcançou a maior validade e pontuação de diversidade entre os métodos exatos.
Fidelidade: A divergência KL do CARS foi 1,5× menor que a do MCMC e 1,8× menor que a do AWRS, indicando uma adesão superior à distribuição real.

C. Geração de Text-to-SQL

Tarefa: Gerar consultas SQL a partir de perguntas em linguagem natural (dataset Spider).
Resultados: O CARS alcançou a maior precisão de execução (0,578) entre todos os métodos. Exigiu 1,85× menos amostras que o RS e 1,28× menos que o ARS.
Comparação: Enquanto métodos aproximados como o GCD foram mais rápidos (1,00 amostras/consulta), eles sofreram com menor precisão (0,525). O CARS ofereceu o melhor equilíbrio, superando o GCD em precisão, exigindo apenas 1,1× o número de amostras.

5. Significância e Alegações

O artigo afirma que o CARS estabelece um novo estado da arte para a amostragem da distribuição exata de um LM. Sua significância reside em resolver o conflito fundamental entre exatidão e eficiência:

Ao contrário do RS, o CARS é amortizadamente eficiente na prática, tornando-o viável para tarefas que exigem muitas amostras diversas.
Ao contrário do GCD e outros métodos aproximados, o CARS preserva a verdadeira distribuição do LM, garantindo que o desempenho a jusante (ex: cobertura de fuzzing, diversidade química, precisão de execução SQL) não seja comprometido pela distorção de distribuição.

Os autores observam que o CARS é mais eficaz quando as restrições são verificáveis por prefixo e altamente informativas para a poda (ex: gramáticas livres de contexto). Em cenários onde o espaço de entradas inválidas consiste em muitos subespaços de baixa probabilidade independentes sem prefixos compartilhados, os ganhos sobre o ARS podem ser mais modestos, e métodos aproximados podem permanecer uma alternativa prática. No entanto, para a maioria das tarefas de geração estruturada, o CARS fornece uma solução principiada, exata e eficiente.