Résumé Technique : La Loterie Invisible : Comment des indices subtils orientent le choix d'algorithme dans la génération de code par les LLM

1. Énoncé du problème

Alors que les grands modèles de langage (LLM) sont de plus en plus utilisés pour générer du code de production, les métriques d'évaluation standard (ex. HumanEval, MBPP) se concentrent presque exclusivement sur la correctitude fonctionnelle (succès/échec par rapport aux tests unitaires). Cette approche occulte une dimension critique de la génération de code : le choix de l'algorithme.

Lorsque plusieurs algorithmes valides existent pour une même tâche (ex. récursion naïve vs exponentiation de matrice pour Fibonacci), le modèle doit en sélectionner un. Cette sélection est souvent invisible pour le développeur. Le papier postule que les indices de prompt incidents — mots contextuels, métadonnées, prompts système ou détails du projet en dehors de la spécification de la tâche centrale — orientent systématiquement le modèle vers des familles d'algorithmes spécifiques. Ces choix ont des implications profondes sur la performance (complexité temporelle/spatiale), la sécurité (ex. raccourcis dangereux comme eval) et la maintenabilité, pourtant ils restent indétectables par les benchmarks basés uniquement sur la correctitude. Les auteurs nomment ce phénomène la « loterie invisible », où la « politique » du code généré (ses caractéristiques implicites de performance et de sécurité) est déterminée par un contexte subtil et souvent involontaire plutôt que par l'intention explicite du développeur.

2. Méthodologie

L'étude utilise un cadre expérimental contrôlé pour quantifier l'orientation algorithmique.

2.1 Conception expérimentale

• Échelle : 46 535 expériences contrôlées à travers 11 tâches (8 algorithmes classiques, 3 tâches de production appliquées), 19 types d'indices (18 canaux + 1 ablation sémantique-vs-surface) et 15 configurations de modèles (incluant GPT-5, Claude Sonnet 4, Gemini 3 Flash et divers modèles open-source).
• Suite de tâches : Comprend des problèmes classiques (Fibonacci, parcours d'arbre, plus courts chemins) et des tâches appliquées (cache LRU, limitation de débit, somme mobile).
• Injection d'indices : Les prompts ont été construits avec une spécification de tâche fixe et un « indice » variable injecté dans le contexte. Les indices ont été catégorisés en :
  • Canaux Sémantiques : Codent des priorités d'optimisation ou des rôles (ex. « critique pour le temps », « persona académique », « import functools »).
  • Canaux Inoffensifs : Contexte algorithmiquement non pertinent (ex. noms d'équipe, noms de code de projet, thèmes de couleurs, identifiants aléatoires).
• Décodage : Les expériences ont été menées à une température $T=0$ (et des balayages jusqu'à $T=1.0$) pour isoler les effets des indices du bruit d'échantillonnage.

2.2 Détection et métriques

• Classification basée sur l'AST : Un classificateur d'arbre de syntaxe abstraite (AST) a cartographié le code généré vers des familles d'algorithmes spécifiques (ex. distinguant les parcours d'arbres récursifs, itératifs et de Morris).
• Delta de pilotage ($\Delta$) : Défini comme le décalage de la distribution des familles d'algorithmes entre un indice spécifique et une base de référence (sans indice), mesuré en points de pourcentage (pp).
• Seuil : Un indice est considéré comme « orientant » si $|\Delta| > 15$ pp.
• Garde-fous : Des tests de stress (ex. Fibonacci $n=36$, récursion profonde) ont été ajoutés pour détecter les échements de performance que les tests unitaires manquent.

3. Contributions clés

1. Méthodologie : Développement d'un cadre de détection basé sur l'AST et d'une suite de benchmarks de 11 tâches multi-algorithmes pour mesurer les distributions de sélection d'algorithmes plutôt que les taux de réussite binaire succès/échec.
2. Identification du phénomène : Quantification de l'orientation algorithmique, démontrant que des indices incidents peuvent déplacer les distributions de familles d'algorithmes jusqu'à 100 points de pourcentage.
3. Taxonomie : Une classification de 18 canaux d'orientation, révélant que tant les indices sémantiques (rôles, contraintes) que les indices placebo « neutres » (noms d'équipe) induisent des décalages significatifs.
4. Perspectives exploitables : Identification du compromis entre sophistication de l'algorithme et fiabilité, et validation de la dénomination directe de l'algorithme comme stratégie de mitigation.

4. Résultats clés

4.1 Magnitude de l'orientation

• Décalages systématiques : À travers 930 cellules d'API qualifiées, la capacité de pilotage médiane était de 40 pp, avec une moyenne de 50,0 pp. 65 % des cellules dépassaient un décalage de 15 pp, et 56 % dépassaient 30 pp.
• Effets maximaux : Dans des paires tâche-canal spécifiques, les décalages ont atteint 100 pp.
  • Parcours d'arbre : Les indices de « lisibilité » ont conduit à 89 % de récursion, tandis que les indices d'« espace » ont conduit à 0 % de récursion (oscillation de 89 pp).
  • Analyse d'expression : Le contexte « prototype » a activé des raccourcis eval() non sécurisés dans 70 % des sorties contre 6 % sous le contexte « entretien » (oscillation de 64 pp).
  • Mémoïsation : Le persona « Junior » a produit des solutions 100 % optimisées pour l'espace, tandis que le persona « Académique » a produit 43 % d'exponentiation de matrice (ce qui a introduit des modes d'échec).

4.2 Effets Sémantiques vs de Surface

• Le sens dirige l'orientation : Les indices sémantiques (ex. « critique pour le temps ») ont eu des effets nettement plus forts que les indices inoffensifs. Cependant, même les indices placebo « neutres » (noms d'équipe, IDs aléatoires) ont produit un décalage moyen de 26 pp, suggérant que tout contexte réduit la capacité de choix algorithmique du modèle par rapport à une base sans indice.
• Forme de surface : Les études d'ablation ont montré qu'une fois le contenu sémantique constant, les variations de surface (ex. casse, ponctuation) ajoutent un effet négligeable supplémentaire.

4.3 Dépendance au Modèle et à la Température

• Divergence des modèles : Un même indice peut pousser différents modèles dans des directions opposées. Par exemple, sous un persona « académique » pour la mémoïsation :
  • Claude Sonnet 4 : A sélectionné l'exponentiation de matrice avec un taux de réussite de 100 %.
  • GPT-5 : A tenté l'exponentiation de matrice mais a échoué à tous les essais (0 % de taux de réussite).
  • Gemini 3 Flash : Est revenu par défaut à une récursion naïve avec un taux de réussite de 100 %.
• Température : Les effets d'orientation persistent à travers les températures $0, 0.3, 0.7$ et $1.0$, bien que le taux d'« inconnu » augmente légèrement à des températures plus élevées.

4.4 Compromis Sophistication–Fiabilité

• Les indices implicites qui poussent les modèles vers des algorithmes « sophistiqués » réduisent souvent la correctitude.
  • Mémoïsation : Le persona « académique » a augmenté l'utilisation de l'exponentiation de matrice mais a fait chuter le taux de réussite à 80 % (contre 100 % pour le persona « junior » utilisant une mémoïsation simple).
  • Analyse d'expression : Les indices « prototype » ont augmenté l'usage de eval, entraînant un code fragile et des taux de réussite plus faibles (71,5 % au total).

4.5 Transfert aux tâches appliquées et aux benchmarks

• Les effets d'orientation se sont transférés aux tâches appliquées (Limitation de débit, Somme mobile), où les indices ont déplacé les implémentations entre des approches par fenêtre glissante et par bacs (buckets).
• Aveuglement de HumanEval : Sur les tâches standard HumanEval, l'orientation s'est produite dans 5/12 (tâche, modèle) paires. Crucialement, ces changements étaient invisibles pour le pass@k, car tous les algorithmes générés passaient les tests unitaires malgré des complexités très différentes.

5. Mitigation et Recommandations

Le papier idente la spécification directe de l'algorithme comme la mitigation la plus fiable.

• Nomination explicite : Lorsque les prompts demandaient explicitement un algorithme nommé (ex. « utilisez l'exponentiation de matrice »), la conformité était de 98,3 % (normalisée) et les taux de réussite étaient de 100 %.
• Limites des Personas : Les personas « experts » (ex. « académique ») ne garantissent pas un meilleur code ; ils déclenchent souvent des algorithmes sophistiqués qui introduisent de nouveaux modes d'échec.
• Directives pratiques :
  1. Spécifiez les algorithmes directement lorsque la performance ou la sécurité est critique ; évitez de compter sur les indices de persona ou de contrainte comme substituts.
  2. Standardisez les prompts système, les imports et les métadonnées pour assurer la reproductibilité.
  3. Testez sur plusieurs modèles, car la direction de l'orientation est spécifique au modèle.
  4. Implémentez des tests de stress (ex. entrées volumineuses) pour faire émerger la fragilité algorithmique que les tests unitaires manquent.

6. Signification et Revendications

Le papier affirme que le choix de l'algorithme est une décision de politique actuellement pilotée par une « loterie invisible » de contexte incident.

• Écart d'évaluation : Les benchmarks actuels (pass@k) sont insuffisants car ils réduisent toutes les implémentations correctes à un seul bit, masquant les différences critiques de complexité, d'empreinte mémoire et de sécurité.
• Sécurité et Reproductibilité : Les conclusions suggèrent que sans auditer les familles d'algorithmes, les développeurs peuvent involontairement livrer du code avec une complexité $O(n^2)$, des risques de dépassement de pile (stack overflow) ou des raccourcis non sécurisés (comme eval) simplement à cause de la présence d'un nom de projet spécifique ou d'un persona dans le prompt.
• Portée modeste : Les auteurs reconnaissent les limites de la couverture des tâches (se concentrant sur 11 tâches spécifiques) et des mises à jour des modèles, mais affirment que le phénomène d'orientation induite par le contexte est une propriété fondamentale de la génération de code par les LLM actuels qui nécessite l'attention immédiate des développeurs et des évaluateurs.

Le travail conclut que pour dépasser la génération de code « boîte noire », la communauté doit évaluer les distributions de familles d'algorithmes parallèlement à la correctitude, rendant la « loterie invisible » visible et gérable.