Resumo Técnico: RISCOSET para Quantificação de Incerteza em Geração de Código Baseada em LLM

Declaração do Problema

Modelos de Linguagem de Grande Escala (LLMs) são cada vez mais utilizados para geração de código, mas sofrem com alucinações e a geração de saídas tóxicas ou enviesadas, limitando sua implantação em aplicações de alto risco. Embora a Predição Conformal (CP) ofereça um framework para quantificação de incerteza com garantias livres de distribuição, adaptá-la a tarefas de geração estruturada, como código, é desafiador.

As abordagens existentes, como conjuntos de predição PAC (Provavelmente Corretos Aproximadamente) para código (Khakhar et al., 2023), enfrentam duas limitações críticas:

1. Restrições de Monotonicidade: Elas dependem de uma forte suposição de monotonicidade em relação ao risco e ao tamanho do conjunto de predição. Isso restringe o espaço de programas parciais admissíveis, frequentemente levando a soluções subótimas que removem muitos nós de código.
2. Suposição de Rótulo Único: Elas são projetadas para classificação de rótulo único. No entanto, a geração de código é inerentemente um problema de múltiplos rótulos, onde múltiplos programas sintaticamente diferentes podem possuir semânticas idênticas e corretas. Os métodos existentes falham em acomodar essa multiplicidade, limitando severamente o espaço de candidatos.

Metodologia: RISCOSET

Os autores propõem o RISCOSET, um método que constrói conjuntos de predição com controle de risco para geração de código baseada em LLM, reformulando o problema como uma tarefa de classificação de múltiplos rótulos e aproveitando o framework Learn Then Test (LTT) (Angelopoulos et al., 2025).

Componentes Principais

1. Reformulação de Múltiplos Rótulos e Risco Estruturado:
   Em vez de impor monotonicidade, o RISCOSET define uma função de risco estruturada baseada na correção semântica. Para uma dada entrada, o objetivo é produzir um conjunto de predição (representado como um programa parcial ou subárvore de AST) que contenha pelo menos um programa correto de um conjunto de rótulos aprimorado $\tilde{Y}$. O risco empírico é definido como a fração de instâncias de calibração onde o conjunto de predição falha em intersecionar com o conjunto de programas corretos.

2. Otimização para Programas Parciais:
   Para gerar o conjunto de predição, o método resolve um problema de otimização para podar nós da Árvore de Sintaxe Abstrata (AST) do código gerado.

   • Objetivo: Retener o máximo possível de nós, garantindo que a incerteza total (log-probabilidade negativa) do programa parcial restante não exceda um limiar $\lambda$.
   • Restrições: A solução deve satisfazer a conectividade da árvore (se um pai é removido, os filhos devem ser removidos) e um limite no número de remoções de subárvores permitidas ($t_{max}$). Crucialmente, essa otimização remove a restrição de monotonicidade estrita encontrada em métodos PAC, permitindo um espaço de rótulos viável maior.

3. Teste de Múltiplas Hipóteses (LTT):
   O RISCOSET emprega o framework LTT para selecionar o parâmetro ótimo $\hat{\lambda}$ que controla o risco.

   • Trata a seleção de $\lambda$ como um problema de teste de múltiplas hipóteses.
   • Para um conjunto de valores candidatos de $\lambda$, calcula valores-$p$ baseados no risco estruturado empírico.
   • Usando um algoritmo de controle da Taxa de Erro Familiar (FWER), identifica um conjunto válido de parâmetros $\Lambda_{valid}$ que garante que o risco permaneça abaixo de uma tolerância especificada pelo usuário $\alpha$ com alta confiança ($1-\delta$).

4. Estratégia de Execução Seletiva:
   Como a geração de código é de múltiplos rótulos, o processo de calibração requer a amostragem de múltiplos programas candidatos e sua verificação via execução de casos de teste, o que é computacionalmente caro. Para mitigar isso, o RISCOSET introduz uma estratégia de execução seletiva:

   • Utiliza pontuações de incerteza (por exemplo, perplexidade) para decidir quais programas amostrados requerem execução de teste.
   • Programas com baixa incerteza são aceitos como corretos sem execução, enquanto programas de alta incerteza são verificados.
   • Essa estratégia usa amostragem por importância e a desigualdade de Hoeffding para estimar um limite superior de erro, garantindo que a taxa de erro de rótulo permaneça dentro de um limite controlado $\epsilon$, enquanto reduz significativamente os custos computacionais.

Contribuições Principais

1. Framework RISCOSET: A primeira aplicação do framework LTT à geração de código estruturada, reformulando a construção de conjuntos de predição como um problema de múltiplos rótulos com restrições mais fracas do que as abordagens baseadas em PAC.
2. Otimização de Risco Estruturado: Uma formulação de otimização inovadora para gerar programas parciais (subárvores AST) que maximiza a informação retida enquanto satisfaz garantias de controle de risco, livre de suposições de monotonicidade restritivas.
3. Calibração Eficiente: Uma estratégia de execução seletiva que equilibra o trade-off entre controle de risco e o custo computacional da verificação de rótulos, apoiada por limites de erro não assintóticos.
4. Validação Empírica: Experimentos abrangentes demonstrando a eficácia do método em três LLMs (Deepseek-Coder, Qwen2.5-Coder, Llama3.1) e três conjuntos de dados (HumanEval, MBPP, APPS).

Resultados Experimentais

Os autores avaliaram o RISCOSET contra baselines de última geração, incluindo a abordagem de conjunto de predição PAC e uma variante gananciosa.

• Redução na Remoção de Nós: O RISCOSET reduz significativamente o número de nós AST removidos em comparação com as baselines, mantendo o mesmo nível de controle de risco. Por exemplo, no conjunto de dados MBPP com $\alpha=0.15$, o método reduziu a remoção de código em 24,5% em comparação com o melhor concorrente.
• Garantias de Cobertura: Os conjuntos de predição construídos consistentemente alcançaram taxas de cobertura superiores ao limite alvo ($1-\alpha$), validando as garantias teóricas de controle de risco.
• Escalabilidade do Modelo: O método performou bem tanto em modelos especializados em código (Qwen2.5-Coder) quanto em modelos de propósito geral (Llama3.1), mostrando que o desempenho melhora com modelos generativos mais poderosos.
• Eficiência da Execução Seletiva: A estratégia de execução seletiva reduziu com sucesso a proporção de programas que requerem execução de casos de teste (por exemplo, evitando a execução para ~30% dos programas com uma taxa de erro de rótulo de $\epsilon=0.1$), mantendo a cobertura acima do limiar alvo.

Significado e Alegações

O artigo alega ser o primeiro trabalho a introduzir o framework LTT em tarefas de geração de código estruturada. Seu significado principal reside em abordar as limitações dos métodos existentes baseados em PAC ao:

• Eliminar a necessidade de fortes suposições de monotonicidade, expandindo assim o espaço de programas candidatos e reduzindo a remoção desnecessária de código.
• Acomodar naturalmente a natureza de múltiplos rótulos da geração de código (múltiplas soluções válidas para uma única tarefa).
• Fornecer garantias estatísticas rigorosas para a correção dos conjuntos de código gerados, sem depender de suposições de independência que falham em domínios estruturados como código.

Os autores concluem que, embora seu foco seja a geração de código, o método proposto é adaptável a outros problemas de predição estruturada onde a quantificação de incerteza é crítica. Eles reconhecem a sobrecarga computacional da fase de calibração, mas enfatizam que a estratégia de execução seletiva mitiga efetivamente esse custo.