Résumé technique : Prédiction des performances des programmes symboliques et des programmes par incitation avec exemples

Énoncé du problème

L'incitation (prompting) par les grands modèles de langage (LLM) est largement adoptée pour des tâches formulées naturellement, mais souffre d'un manque de fiabilité ; un prompt peut réussir quelques cas de test tout en échouant de manière imprévisible lors du déploiement. En revanche, les programmes symboliques (par exemple, Python, expressions régulières) sont souvent considérés comme fiables une fois qu'ils ont réussi quelques cas de test représentatifs. Cet article examine la question fondamentale : Pourquoi quelques tests réussis certifient-ils les programmes symboliques mais pas les programmes par incitation ?

Les auteurs formulent cela comme un problème de prédiction de performance : étant donné un programme (soit symbolique, soit un prompt exécuté par un LLM) et un petit ensemble de résultats d'exécution dans le domaine (réussite/échec), prédire sa vraie performance ($\theta$) sur des tâches non vues issues du même domaine. L'objectif est d'inférer une distribution a posteriori sur le taux de réussite du programme afin de déterminer sa déployabilité et les niveaux de confiance.

Méthodologie

1. Cadre théorique : Le modèle du lancer de pièce

Les auteurs adoptent une approche bayésienne, modélisant chaque exécution d'un programme sur un cas de test comme une variable aléatoire de Bernoulli indépendante (un « lancer de pièce »).

• Observation ($O$) : Un ensemble de $a$ réussites et $b$ échecs.
• Vraisemblance : $P(O|\theta) \propto \theta^a (1-\theta)^b$.
• Postérieur : $P(\theta|O) \propto P(\theta) \cdot \theta^a (1-\theta)^b$.

L'insight critique est que, bien que la vraisemblance soit facilement calculable, l'a priori de performance $P(\theta)$ est inconnu et dicte la distribution postérieure. L'article soutient que la différence de prévisibilité entre les programmes symboliques et les programmes par incitation découle entièrement de la forme de leurs a priori respectifs.

2. A priori de performance empiriques

Pour comprendre les a priori, les auteurs ont compilé un corpus de 700 programmes symboliques (sp) et 700 programmes par incitation (pp) couvrant divers domaines (par exemple, Regex, HumanEval, ARC, List Rules). Ils ont évalué chaque programme sur 100 instances échantillonnées pour estimer sa vraie performance.

• Programmes symboliques (sp) : Présentent un a priori « tout ou rien ». La distribution est fortement bimodale, concentrée près de $\theta=0.0$ (totalement incorrect) et $\theta=1.0$ (parfait).
• Programmes par incitation (pp) : Présentent un a priori diffus. Il existe une masse substantielle sur des valeurs de performance intermédiaires, représentant des programmes « presque corrects » qui peuvent réussir quelques tests par chance mais échouer sur d'autres.

Implication : Pour les programmes symboliques, quelques succès déplacent rapidement la masse postérieure vers 1,0, offrant une grande confiance. Pour les programmes par incitation, les mêmes succès ne déplacent que légèrement l'a priori diffus, laissant la vraie performance incertaine.

3. RAP (A priori approximatif récupéré)

Pour remédier à la difficulté de prédire la performance des programmes par incitation, les auteurs proposent RAP, une méthode basée sur la récupération pour construire un a priori spécifique à la tâche.

• Entrée : Un programme par incitation cible ($p_{target}$), un ensemble d'exemples observés dans le domaine ($D$), et un corpus de tâches et de prompts ($M$).
• Récupération :
  1. Tâches similaires : Récupérer les $n$ meilleures tâches du corpus similaires aux exemples observés en utilisant des plongements textuels.
  2. Prompts similaires : Récupérer les $K$ meilleurs programmes par incitation du corpus qui présentent un comportement similaire (accord sur la correction) à $p_{target}$ sur les tâches récupérées.
• Construction de l'a priori : La performance des prompts récupérés sur les tâches récupérées est utilisée pour construire un mélange de distributions Beta comme a priori approximatif.
• Mise à jour : Les résultats observés ($O$) mettent à jour ce mélange d'a priori par conjugaison.
• Raffinement : RAP inclut un Ajustement de la force de l'a priori par composante. Il met à l'échelle les paramètres de chaque composante Beta en fonction de la distance de transport optimal (Earth Mover's Distance, EMD) entre la composante récupérée et l'a priori dérivé uniquement des observations dans le domaine. Cela empêche les données du corpus non pertinentes de déformer le postérieur lorsque les données dans le domaine sont rares.

Contributions clés

1. Formalisation : L'article formalise la prédiction de performance comme une inférence bayésienne sous un simple modèle de lancer de pièce, séparant explicitement la vraisemblance (données observées) de l'a priori (caractéristiques du type de programme).
2. Découverte empirique : Il fournit la première preuve empirique que les programmes symboliques ont un a priori de performance « tout ou rien », tandis que les programmes par incitation ont un a priori diffus avec une masse significative sur des performances intermédiaires. Cela explique le fossé de certification entre les deux types de programmes.
3. Solution algorithmique : L'introduction de RAP, une méthode basée sur la récupération qui construit un a priori approximatif spécifique au domaine à partir d'un corpus. RAP surpasse les lignes de base qui n'utilisent aucun corpus ou qui utilisent l'ensemble du corpus de manière naïve.

Résultats

Les auteurs ont évalué RAP sur 60 programmes par incitation dans divers contextes (dans le domaine et hors du domaine) en utilisant les métriques de Densité de probabilité à la vérité terrain (SC) et Erreur absolue (AE).

• Supériorité : RAP surpasse constamment les lignes de base (sans corpus et tout le corpus) dans les contextes dans le domaine et hors du domaine.
• Avantage dans le domaine : L'utilisation d'exemples dans le domaine dans le corpus améliore considérablement la précision de la prédiction, en particulier lorsque le nombre de cas de test observés est faible.
• Convergence : À mesure que le nombre d'observations dans le domaine augmente, RAP converge gracieusement vers le postérieur empirique, garantissant que le terme de vraisemblance finit par dominer l'a priori.
• Robustesse : La méthode reste robuste face à différents choix d'hyperparamètres, tailles de corpus et architectures de LLM.

Importance et affirmations

L'article revendique d'être le premier travail à étudier la prédiction de performance pour les programmes symboliques et les programmes par incitation en utilisant un cadre bayésien unifié. Sa signification principale réside dans :

• Quantification de l'intuition : Fournir une explication mathématique de la raison pour laquelle peu de cas de test certifient le code symbolique mais pas les prompts, en l'attribuant aux différences structurelles de leurs a priori de performance.
• Déploiement pratique : Offrir une méthode (RAP) pour estimer la confiance dans le déploiement d'un programme par incitation lorsque seules des données de test limitées sont disponibles, un besoin critique pour des contextes non critiques où une performance de 80 % est précieuse mais où l'incertitude doit être gérée.
• Limites : Les auteurs notent modestement que RAP est une « première ligne d'attaque ». Ils reconnaissent que la récupération des $K$ meilleures paires pertinentes devient coûteuse en calcul à mesure que le corpus grandit, suggérant un travail futur sur les requêtes actives et les approximations de rang faible du corpus tâche-prompt.