Résumé technique : RISCOSET pour la quantification de l'incertitude dans la génération de code par les LLM

Énoncé du problème

Les grands modèles de langage (LLM) sont de plus en plus utilisés pour la génération de code, mais ils souffrent d'hallucinations et de la production de sorties toxiques ou biaisées, ce qui limite leur déploiement dans des applications à haut risque. Bien que la prédiction conforme (CP) offre un cadre pour la quantification de l'incertitude avec des garanties sans hypothèse de distribution, son adaptation aux tâches de génération structurée comme le code reste difficile.

Les approches existantes, telles que les ensembles de prédiction PAC (Probably Approximately Correct) pour le code (Khakhar et al., 2023), se heurtent à deux limitations critiques :

1. Contraintes de monotonie : Elles reposent sur une forte hypothèse de monotonie concernant le risque et la taille de l'ensemble de prédiction. Cela restreint l'espace des programmes partiels admissibles, conduisant souvent à des solutions sous-optimales qui éliminent trop de nœuds de code.
2. Hypothèse d'étiquette unique : Elles sont conçues pour la classification à étiquette unique. Or, la génération de code est intrinsèquement un problème multi-étiquettes, où plusieurs programmes syntaxiquement différents peuvent posséder une sémantique identique et correcte. Les méthodes existantes ne parviennent pas à accommoder cette multiplicité, limitant sévèrement l'espace des candidats.

Méthodologie : RISCOSET

Les auteurs proposent RISCOSET, une méthode qui construit des ensembles de prédiction contrôlant le risque pour la génération de code par les LLM en reformulant le problème comme une tâche de classification multi-étiquettes et en exploitant le cadre Learn Then Test (LTT) (Angelopoulos et al., 2025).

Composants principaux

1. Reformulation multi-étiquettes et risque structuré :
   Au lieu d'imposer une monotonie, RISCOSET définit une fonction de risque structurée basée sur la correction sémantique. Pour une entrée donnée, l'objectif est de produire un ensemble de prédiction (représenté comme un programme partiel ou un sous-arbre AST) contenant au moins un programme correct issu d'un ensemble d'étiquettes enrichi $\tilde{Y}$. Le risque empirique est défini comme la fraction des instances d'étalonnage où l'ensemble de prédiction échoue à intersecter l'ensemble des programmes corrects.

2. Optimisation pour les programmes partiels :
   Pour générer l'ensemble de prédiction, la méthode résout un problème d'optimisation afin d'élaguer des nœuds de l'arbre de syntaxe abstraite (AST) du code généré.

   • Objectif : Conserver un maximum de nœuds tout en s'assurant que l'incertitude totale (négatif du logarithme de la probabilité) du programme partiel restant ne dépasse pas un seuil $\lambda$.
   • Contraintes : La solution doit satisfaire la connectivité de l'arbre (si un parent est supprimé, ses enfants doivent l'être) et une limite sur le nombre de suppressions de sous-arbres autorisées ($t_{max}$). Crucialement, cette optimisation élimine la contrainte de monotonie stricte présente dans les méthodes PAC, permettant un espace d'étiquettes réalisable plus vaste.

3. Tests d'hypothèses multiples (LTT) :
   RISCOSET utilise le cadre LTT pour sélectionner le paramètre optimal $\hat{\lambda}$ qui contrôle le risque.

   • Il traite la sélection de $\lambda$ comme un problème de tests d'hypothèses multiples.
   • Pour un ensemble de valeurs candidates de $\lambda$, il calcule des valeurs $p$ basées sur le risque structuré empirique.
   • En utilisant un algorithme de contrôle du taux d'erreur familial (FWER), il identifie un ensemble valide de paramètres $\Lambda_{valid}$ garantissant que le risque reste en dessous d'une tolérance spécifiée par l'utilisateur $\alpha$ avec une haute confiance ($1-\delta$).

4. Stratégie d'exécution sélective :
   Puisque la génération de code est multi-étiquettes, le processus d'étalonnage nécessite d'échantillonner plusieurs programmes candidats et de les vérifier par exécution de cas de test, ce qui est coûteux en calcul. Pour atténuer cela, RISCOSET introduit une stratégie d'exécution sélective :

   • Elle utilise des scores d'incertitude (par exemple, la perplexité) pour décider quels programmes échantillonnés nécessitent une exécution de test.
   • Les programmes à faible incertitude sont acceptés comme corrects sans exécution, tandis que ceux à forte incertitude sont vérifiés.
   • Cette stratégie utilise l'échantillonnage par l'importance et l'inégalité de Hoeffding pour estimer une borne supérieure de l'erreur, garantissant que le taux d'erreur d'étiquette reste dans une borne contrôlée $\epsilon$ tout en réduisant considérablement les coûts de calcul.

Contributions clés

1. Cadre RISCOSET : La première application du cadre LTT à la génération de code structurée, reformulant la construction d'ensembles de prédiction comme un problème multi-étiquettes avec des contraintes plus faibles que les approches basées sur PAC.
2. Optimisation du risque structuré : Une nouvelle formulation d'optimisation pour générer des programmes partiels (sous-arbres AST) qui maximise l'information conservée tout en satisfaisant les garanties de contrôle du risque, libérée des hypothèses de monotonie restrictives.
3. Étalonnage efficace : Une stratégie d'exécution sélective qui équilibre le compromis entre le contrôle du risque et le coût computationnel de la vérification des étiquettes, soutenue par des bornes d'erreur non asymptotiques.
4. Validation empirique : Des expériences complètes démontrant l'efficacité de la méthode sur trois LLM (Deepseek-Coder, Qwen2.5-Coder, Llama3.1) et trois jeux de données (HumanEval, MBPP, APPS).

Résultats expérimentaux

Les auteurs ont évalué RISCOSET par rapport à des références de l'état de l'art, notamment l'approche d'ensemble de prédiction PAC et une variante gourmande.

• Réduction de l'élagage des nœuds : RISCOSET réduit considérablement le nombre de nœuds AST supprimés par rapport aux références tout en maintenant le même niveau de contrôle du risque. Par exemple, sur le jeu de données MBPP avec $\alpha=0.15$, la méthode a réduit la suppression de code de 24,5 % par rapport au meilleur concurrent.
• Garanties de couverture : Les ensembles de prédiction construits ont systématiquement atteint des taux de couverture dépassant la borne cible ($1-\alpha$), validant les garanties théoriques de contrôle du risque.
• Évolutivité des modèles : La méthode a bien fonctionné aussi bien sur des modèles spécialisés dans le code (Qwen2.5-Coder) que sur des modèles à usage général (Llama3.1), montrant que les performances s'améliorent avec des modèles génératifs plus puissants.
• Efficacité de l'exécution sélective : La stratégie d'exécution sélective a réussi à réduire la proportion de programmes nécessitant une exécution de cas de test (par exemple, en évitant l'exécution pour ~30 % des programmes à un taux d'erreur d'étiquette de $\epsilon=0.1$) tout en maintenant une couverture au-dessus du seuil cible.

Importance et affirmations

L'article affirme être le premier travail à introduire le cadre LTT dans les tâches de génération de code structurée. Son importance principale réside dans la résolution des limitations des méthodes PAC existantes en :

• Éliminant le besoin d'hypothèses de monotonie fortes, élargissant ainsi l'espace des programmes candidats et réduisant la suppression de code inutile.
• Accueillant naturellement la nature multi-étiquettes de la génération de code (plusieurs solutions valides pour une seule tâche).
• Fournissant des garanties statistiques rigoureuses sur la correction des ensembles de code générés sans dépendre des hypothèses d'indépendance qui échouent dans les domaines structurés comme le code.

Les auteurs concluent que, bien que leur objectif soit la génération de code, la méthode proposée est adaptable à d'autres problèmes de prédiction structurée où la quantification de l'incertitude est critique. Ils reconnaissent la surcharge computationnelle de la phase d'étalonnage mais soulignent que la stratégie d'exécution sélective atténue efficacement ce coût.