SELF-REDRAFT : Élicitation de l'équilibre intrinsèque exploration-exploitation dans la mise à l'échelle au moment du test pour la génération de code

Informations de base

• ID de l'article : 2511.02854
• Titre : SELF-REDRAFT: Eliciting Intrinsic Exploration-Exploitation Balance in Test-Time Scaling for Code Generation
• Auteurs : Yixiang Chen*, Tianshi Zheng*, Shijue Huang, Zhitao He, Yi R. (May) Fung (*Contribution égale)
• Institution : Département d'informatique et d'ingénierie, HKUST
• Classification : cs.SE (Génie logiciel), cs.AI (Intelligence artificielle)
• Date de soumission : 31 octobre 2025
• Lien de l'article : https://arxiv.org/abs/2511.02854v1

Résumé

Cet article étudie la capacité intrinsèque des grands modèles de langage (LLM) à équilibrer l'exploration et l'exploitation lors de la génération de code dans un scénario de mise à l'échelle au moment du test sans retours d'exécution. Les méthodes existantes dépendent soit de l'exploitation gourmande (optimisation itérative), soit de l'exploration aléatoire (vote basé sur l'échantillonnage ou réordonnancement), mais l'équilibre entre les deux n'a pas été suffisamment étudié. Les auteurs proposent le cadre SELF-REDRAFT, qui ajoute au cadre Self-Refine un mécanisme de redéfinition des solutions fondamentalement erronées. Les expériences montrent que SELF-REDRAFT surpasse constamment Self-Refine avec le même budget itératif, mais il existe encore un espace d'amélioration significatif, principalement limité par deux capacités fondamentales : l'insuffisance dans la génération de retours directifs et la fragilité de la capacité discriminante. L'étude révèle également des différences significatives dans les stratégies d'équilibre entre différents LLM, reflétant des caractéristiques comportementales spécifiques au modèle.

Contexte et motivation de la recherche

1. Problème à résoudre

Cet article se concentre sur le problème de la génération de code dans le scénario de mise à l'échelle au moment du test sans retours d'exécution (execution-free test-time scaling). En pratique, les cas de test ne sont souvent pas disponibles, ce qui nécessite que les LLM améliorent autonomement la qualité du code sans retours d'exécution du programme.

2. Importance du problème

• Besoin pratique : Les cas de test manquent souvent dans les scénarios réels, et les environnements d'exécution peuvent ne pas être disponibles
• Efficacité computationnelle : La mise à l'échelle au moment du test est un moyen efficace d'améliorer les performances des LLM, mais nécessite de maximiser les performances dans un budget de calcul limité
• Valeur théorique : L'équilibre exploration-exploitation est un problème fondamental en apprentissage par renforcement et en algorithmes de recherche, mais son application dans la génération de code n'a pas été suffisamment étudiée

3. Limitations des méthodes existantes

• Méthodes dépendantes de l'exécution : Nécessitent des cas de test et un environnement d'exécution, limitées dans les scénarios pratiques
• Méthodes purement exploitantes (comme Self-Refine) : Effectuent uniquement une optimisation itérative, risquant de rester bloquées dans des optima locaux
• Méthodes purement exploratoires (comme pass@k) : Obtiennent la diversité par plusieurs échantillonnages, mais manquent d'améliorations ciblées
• Absence d'équilibre : Les méthodes existantes sans retours d'exécution dépendent principalement de l'exploitation, la dimension d'exploration étant négligée

4. Motivation de la recherche

Les auteurs visent à étudier la capacité intrinsèque (intrinsic ability) des LLM à équilibrer exploration et exploitation sans retours d'exécution, à identifier les goulots d'étranglement des modèles actuels et à indiquer des directions pour les améliorations futures.

Contributions principales

1. Proposition du cadre SELF-REDRAFT : Introduction d'un choix d'exploration explicite basé sur Self-Refine, permettant au modèle de redéfinir les solutions fondamentalement erronées (redraft), réalisant un équilibre entre exploration et exploitation
2. Établissement d'une évaluation de référence : Évaluation systématique de 6 LLM open-source et propriétaires sur LiveCodeBench, démontrant une amélioration moyenne de 0,615% après 16 itérations avec SELF-REDRAFT
3. Identification des goulots d'étranglement fondamentaux : Révélation par analyse approfondie de deux facteurs de limitation clés :
   • Insuffisance dans la génération de retours directifs (Insufficient Model Critique)
   • Fragilité de la capacité à discriminer le code correct/incorrect (Fragile Code Discrimination)
4. Révélation des comportements spécifiques au modèle : Découverte de différences significatives dans les stratégies d'équilibre entre différents LLM, indiquant que cette capacité n'est pas universelle mais plutôt une propriété émergente spécifique au modèle
5. Quantification de l'espace d'amélioration : Quantification de l'écart entre les méthodes actuelles et le potentiel d'exploration pure par comparaison avec la limite supérieure pass@8

Explication détaillée de la méthode

Définition de la tâche

Entrée : Description de la tâche de programmation $x$
Sortie : Solution de code $\hat{y}$ satisfaisant les exigences de la tâche
Objectif : Maximiser la correction fonctionnelle du code par itérations limitées (calcul au moment du test) sans retours d'exécution de cas de test

Architecture du modèle

SELF-REDRAFT est un cadre itératif comprenant trois étapes principales :

Étape 0 : Initialisation

Étant donné la tâche $x$ et l'invite de génération $p_{gen}$, le modèle génère une solution initiale : $y_0 \sim \pi(\cdot | p_{gen}, x)$

Étape 1 : Génération de retours (Feedback)

Le modèle évalue la solution actuelle $y_i$, utilisant l'invite de retours $p_{fb}$ pour générer les retours $c_i$ : $c_i \sim \pi(\cdot | p_{fb}, x, y_i)$

Les retours comprennent deux parties :

• Critique (critique) : Analyse des problèmes du code et fourniture de recommandations spécifiques
• Suggestion d'action (suggestion) : Instructions explicites pour l'étape suivante, incluant trois choix :
  • PASS : Code correct, arrêt de l'itération
  • REFINE : Amélioration mineure, maintien de la méthode originale
  • REDRAFT : Erreur fondamentale, nécessité d'une nouvelle approche

Étape 2 : Régénération (Regeneration)

Basée sur les retours et l'historique des trajectoires, le modèle génère une nouvelle solution : $y_{i+1} \sim \pi(\cdot | p_{regen}, x, y_i, c_i, \ldots, y_0, c_0)$

Selon les recommandations de retours :

• Si REDRAFT : Génération d'une solution entièrement nouvelle (exploration)
• Si REFINE : Amélioration basée sur la solution originale (exploitation)

Itération jusqu'à satisfaction des conditions d'arrêt (atteinte du nombre maximum d'itérations $T$ ou sortie PASS du modèle).

Points d'innovation technique

1. Mécanisme d'exploration explicite

Différence fondamentale avec Self-Refine : Self-Refine ne supporte que PASS et REFINE, étant purement exploitant. SELF-REDRAFT introduit l'option REDRAFT, permettant au modèle d'identifier les erreurs fondamentales et de redéfinir les solutions.

Justification de la conception :

• Les problèmes de code se divisent en erreurs superficielles (syntaxe, conditions limites) et erreurs méthodologiques (choix d'algorithme incorrect)
• Les erreurs superficielles conviennent à l'optimisation progressive (refine), les erreurs méthodologiques nécessitent une réflexion nouvelle (redraft)
• En laissant le modèle juger autonomement le type d'erreur, on réalise un équilibre dynamique exploration-exploitation

2. Conception de retours structurés

Utilisation de balises XML pour forcer la génération de sorties structurées :

<critique>
Analyse et critique détaillées
</critique>
<suggestion>
pass/refine/redraft
</suggestion>

Cette conception facilite :

• L'extraction d'informations et la prise de décision algorithmique
• L'analyse expérimentale ultérieure
• L'assurance de l'opérabilité des retours

3. Mécanisme de mémoire de trajectoire

L'inclusion de l'historique complet des trajectoires $(y_0, c_0, \ldots, y_i, c_i)$ lors de la régénération permet au modèle de :

• Éviter les erreurs répétées
• Apprendre les modèles d'amélioration
• Conserver les informations valides lors de l'exploration

Configuration expérimentale

Ensemble de données

LiveCodeBench (Jain et al., 2024) :

• Échelle : 1 055 problèmes de programmation
• Gradation de difficulté : Trois niveaux - facile, moyen, difficile
• Caractéristiques :
  • Référence d'évaluation complète et non contaminée
  • Provenant de véritables compétitions de programmation
  • Mise à jour continue, évitant les fuites de données d'entraînement

Métriques d'évaluation

1. Pass@k : Métrique de correction fonctionnelle $\text{pass@k} = \mathbb{E}_{\text{Problème}}\left[1 - \frac{\binom{n-c}{k}}{\binom{n}{k}}\right]$ où $n$ est le nombre d'échantillons générés et $c$ le nombre d'échantillons corrects. Cet article utilise $n=16, k=8$.
2. Taux d'amélioration ($r_{imp}$) : Proportion de solutions initialement erronées corrigées
3. Taux de régression ($r_{reg}$) : Proportion de solutions initialement correctes détériorées
4. Rappel sur Redraft : Taux de rappel du correcteur auxiliaire pour identifier correctement les recommandations "redraft"

Méthodes de comparaison

• Self-Refine : Ligne de base purement exploitante, supportant uniquement l'optimisation itérative
• Pass@8 : Limite supérieure purement exploratoire, obtenue par échantillonnage indépendant

Détails d'implémentation

Configuration des modèles (6 LLM) :

• GPT-4.1 mini, GPT-4.1 nano (OpenAI)
• Kimi K2 (32B paramètres actifs, 1T paramètres totaux MoE)
• Llama 4 Maverick (17B paramètres actifs, 128 experts MoE)
• LongCat-Flash-Chat (MoE, spécialisé dans les tâches d'agent)
• Qwen3-Next-80B-A3B-Instruct

Paramètres de génération (conformes aux paramètres par défaut de LiveCodeBench) :

• Température : 0,2
• Top-p : 0,95
• Pénalité de fréquence : 0
• Pénalité de présence : 0

Configuration itérative :

• Nombre maximum d'itérations : 16
• Utilisation du même ensemble de solutions initiales pour assurer l'équité
• Arrêt anticipé autorisé (lorsque le modèle sort PASS)

Résultats expérimentaux

Résultats principaux

Performance globale (Figure 2, résultats complets du tableau en Annexe E) :

• SELF-REDRAFT améliore en moyenne Self-Refine de 0,615% après 16 itérations
• L'amélioration apparaît constamment sur les 6 modèles testés
• Les performances se stabilisent à 16 itérations

Performance par modèle (Figure 8) :

• Différences significatives de performance absolue entre modèles
• Formes de courbes itératives variées, reflétant différentes stratégies d'équilibre
• Certains modèles atteignent un pic aux premières itérations, avec fluctuations ultérieures

Potentiel d'exploration non exploité

Comparaison avec la limite supérieure pass@8 (Figure 3) :

• Pass@8 surpasse significativement SELF-REDRAFT×16 (17 solutions)
• Découverte clé : L'exploration pure (8 échantillons indépendants) est plus efficace que l'équilibre exploration-exploitation actuel
• Exemples d'écarts :
  • GPT-4.1 mini : SELF-REDRAFT 35,1% vs Pass@8 41,8%
  • Qwen3-Next : SELF-REDRAFT 48,2% vs Pass@8 55,3%

Interprétation : De nombreux problèmes peuvent être résolus simplement par échantillonnage diversifié, mais SELF-REDRAFT n'exploite pas efficacement cet avantage, indiquant une faible efficacité du mécanisme d'exploration actuel.

Analyse de la qualité des retours

Conception d'expérience en aveugle (Section 3.3) :

• Échantillonnage de triplets (solution originale, retours, nouvelle solution) à partir des trajectoires
• Le correcteur auxiliaire juge uniquement les paires de solutions pour détecter les changements méthodologiques
• Comparaison des jugements du correcteur avec les recommandations de retours originales (refine vs redraft)
• Équilibrage des échantillons : chaque groupe contient un nombre égal d'étiquettes "draft" et "refine"
• Maximum 1 000 échantillons par modèle générateur

Résultats du rappel sur Redraft (Figure 5) :

• Taux de rappel moyen : entre 30-55%
• Découverte de corrélation positive (Figure 4) : Le rappel sur Redraft est positivement corrélé à l'ampleur d'amélioration de SELF-REDRAFT (coefficient de corrélation environ 0,6-0,7)
• Cohérence entre correcteurs (Figure 7) : Le classement de différents modèles auxiliaires est hautement cohérent (Spearman ρ > 0,8)

Conclusion fondamentale : La plupart des modèles ne peuvent pas fournir de retours opérationnels pour la correction méthodologique, limitant l'exploration efficace.

Analyse de la capacité discriminante

Comparaison des taux d'amélioration et de régression (Tableau 1) :

Découvertes clés :

1. Le taux d'amélioration de SELF-REDRAFT est plus élevé (corrige plus d'erreurs)
2. Mais le taux de régression augmente également significativement (détériore plus de solutions correctes)
3. L'augmentation du taux de régression est importante sur certains modèles (par exemple Llama-4-Maverick +2,10%)

Interprétation : La redéfinition est une opération à haut risque. En raison de la capacité discriminante limitée, le modèle classe souvent incorrectement les solutions correctes comme erronées et les "améliore" en les détériorant, annulant les bénéfices de l'exploration.

Différences de comportement entre modèles

Différences de stratégie d'équilibre (Figure 6) :

• Le diagramme papillon montre le nombre de recommandations "refine" vs "redraft" de chaque modèle sur 16 itérations
• Différences énormes :
  • Certains modèles préfèrent "refine" (orientation exploitante)
  • Certains modèles préfèrent "redraft" (orientation exploratoire)
  • Aucun modèle unifié

Implications : L'équilibre exploration-exploitation n'est pas une capacité universelle, mais une propriété émergente spécifique au modèle, reflétant :

• Les différences dans les données d'entraînement préalable
• L'influence de l'architecture du modèle
• Les stratégies d'ajustement d'instructions différentes

Analyse de cas

Cas complets en Annexe F :

• Tâche : Problème d'échange de tableau de style LeetCode
• Solution originale : Logique confuse, contenant plusieurs erreurs conceptuelles
• Retours : Identification détaillée de 5 problèmes spécifiques, recommandation de "redraft"
• Nouvelle solution : Adoption d'une approche entièrement différente de programmation dynamique, résolvant correctement le problème

Observations :

• Lorsque la qualité des retours est élevée, redraft peut efficacement sortir de la méthode erronée
• La nouvelle solution démontre une compréhension renouvelée du problème
• Cependant, cette qualité de retours élevée n'est pas la norme dans les expériences

Travaux connexes

1. Méthodes de mise à l'échelle au moment du test

Dépendantes de l'exécution :

• Self-Debug (Chen et al., 2023) : Débogage itératif utilisant les retours d'exécution
• Reflexion (Shinn et al., 2023) : Agent de langage basé sur l'apprentissage par renforcement
• AIDE (Jiang et al., 2025) : Exploration dirigée par IA dans l'espace de code
• S* (Li et al., 2025) : Méthode de recherche au moment du test

Indépendantes de l'exécution :

• Self-Refine (Madaan et al., 2023) : Auto-optimisation purement exploitante
• SETS (Chen et al., 2025) : Auto-vérification et auto-correction

2. Équilibre exploration-exploitation

• Tang et al. (2024) : Modélisation de la correction de code LLM comme équilibre exploration-exploitation
• Distinction de cet article : Focus sur le scénario sans retours d'exécution, étude de la capacité d'équilibre intrinsèque

3. Capacité de retours des LLM

• Zheng et al. (2024) : Mécanismes de raisonnement dans la génération de code multi-tours
• Xie et al. (2025) : Enseignement de la critique aux LLM par apprentissage par renforcement
• Contribution de cet article : Quantification de l'impact de la qualité des retours sur l'efficacité de l'exploration

4. Évaluation de la génération de code

• LiveCodeBench (Jain et al., 2024) : Évaluation complète non contaminée
• Métrique Pass@k (Kulal et al., 2019; Chen et al., 2021)

Conclusion et discussion

Conclusions principales

1. SELF-REDRAFT est efficace mais limité : Surpasse constamment Self-Refine avec le même budget itératif, mais l'ampleur de l'amélioration est limitée (moyenne 0,615%)
2. Deux goulots d'étranglement majeurs :
   • Génération de retours insuffisante : Le modèle a du mal à identifier les erreurs méthodologiques, incapable de fournir des conseils efficaces pour la redéfinition
   • Capacité discriminante fragile : Les erreurs de classification entraînent des redéfinitions nuisibles, l'augmentation du taux de régression annulant les bénéfices
3. Spécificité du modèle : Les stratégies d'équilibre diffèrent énormément entre les LLM, ce n'est pas une capacité universelle
4. Potentiel énorme : L'écart avec la limite supérieure pass@8 indique un espace largement inexploité dans la dimension d'exploration

Limitations

Limitations explicitement indiquées par les auteurs :

1. Paradigme sans exécution :
   • La portée de la recherche est limitée au scénario sans retours d'exécution
   • Pas directement comparable aux méthodes dépendantes de l'exécution
   • Les méthodes hybrides sont une direction future
2. Généralisation du référentiel :
   • Évaluation uniquement sur LiveCodeBench
   • La généralisation à d'autres langages de programmation et domaines reste à vérifier
3. Dépendance aux capacités intrinsèques :
   • Les performances sont limitées par les capacités inhérentes du modèle pré-entraîné
   • Pas d'exploration des améliorations dirigées par l'entraînement (comme l'ajustement fin de la capacité critique)
   • Pas d'étude des stratégies d'exploration non intrinsèques

Directions futures

Directions de recherche proposées par l'article :

1. Amélioration de la génération de retours :
   • Entraînement de modèles critiques spécialisés
   • Conception d'invites de retours plus efficaces
   • Introduction de connaissances externes pour assister le diagnostic
2. Amélioration de la capacité discriminante :
   • Amélioration de la fiabilité du jugement de correction du code
   • Réduction des redéfinitions nuisibles
   • Possibilité de nécessiter des vérificateurs spécialisés
3. Stratégies adaptatives par modèle :
   • Conception de stratégies d'équilibre personnalisées pour différents modèles
   • Ajustement dynamique du ratio exploration-exploitation
   • Apprentissage du moment optimal d'arrêt
4. Méthodes hybrides :
   • Combinaison des retours d'exécution et des capacités intrinsèques
   • Stratégie optimale avec cas de test limités

Évaluation approfondie

Points forts

1. Définition claire et importante du problème

• Concentration sur des scénarios pratiques (absence de cas de test)
• L'équilibre exploration-exploitation est un problème classique, son application dans la génération de code est novatrice
• L'étude des capacités intrinsèques plutôt que des outils externes a une valeur théorique élevée

2. Conception de méthode simple et efficace

• Modifications minimales basées sur Self-Refine, comparaison claire
• La conception à trois options (pass/refine/redraft) est intuitive et opérationnelle
• Les retours structurés facilitent l'analyse

3. Conception expérimentale rigoureuse

• Comparaison équitable : Utilisation du même ensemble de solutions initiales
• Vérification multi-modèles : 6 LLM de différentes tailles et architectures
• Analyse multi-dimensionnelle : Performance, qualité des retours, capacité discriminante, différences entre modèles
• Conception en aveugle : Évite les biais, utilise des modèles auxiliaires pour vérification

4. Analyse approfondie et honnête

• Non seulement rapporte les améliorations, mais indique honnêtement les limitations
• Quantifie l'écart avec la limite supérieure, clarifie l'espace d'amélioration
• Identifie les goulots d'étranglement spécifiques (retours, discrimination) plutôt que des conclusions générales
• Révèle la spécificité du modèle, évite la sur-généralisation

5. Forte reproductibilité

• Pseudocode d'algorithme détaillé (Algorithme 1)
• Modèles d'invites complets (Annexe A.2)
• Configuration des modèles et hyperparamètres clairs (Annexe C)
• Engagement d'ouvrir le code

Insuffisances

1. Ampleur d'amélioration limitée

• L'amélioration moyenne de 0,615% est relativement faible, la signification statistique n'est pas clairement rapportée
• Certains modèles peuvent être dans la plage de bruit
• Nécessite plus d'expériences pour vérifier la stabilité

2. Portée d'évaluation limitée

• Un seul référentiel LiveCodeBench
• Pas de test sur d'autres langages de programmation (au-delà de Python)
• Pas d'évaluation d'autres dimensions de qualité du code (lisibilité, efficacité)

3. Manque d'analyse théorique

• Pourquoi 0,615% est-il une attente raisonnable ?
• Quel est le ratio optimal exploration-exploitation ?
• Absence de cadre théorique formel

4. L'impact de la conception des conditions d'arrêt n'est pas suffisamment discuté

• La décision autonome du modèle de quand PASS peut introduire des biais
• Les taux d'arrêt anticipé entre modèles ne sont pas rapportés
• Peut affecter l'équité

5. Absence d'évaluation humaine

• Toutes les évaluations dépendent de métriques automatiques et de jugements de modèles
• Perspective humaine manquante sur la qualité des retours et du code
• L'évaluation en aveugle utilise des modèles plutôt que des humains

6. Coût computationnel non discuté

• Coût réel de 16 itérations ?
• Comparaison des coûts avec pass@16 ?
• Évaluation insuffisante de l'utilité pratique

Impact

Contribution au domaine

1. Ouverture d'une nouvelle direction de recherche : Établissement d'une référence pour l'équilibre exploration-exploitation sans retours d'exécution
2. Identification des goulots d'étranglement clés : Clarification que les retours et la discrimination sont les limitations fondamentales
3. Inspiration pour les travaux futurs : Fourniture d'un chemin d'amélioration clair

Valeur pratique

• Modérée : L'amélioration actuelle est limitée, mais indique une direction
• Appropriée pour les scénarios où les cas de test ne sont pas disponibles
• Peut servir de complément aux méthodes dépendantes de l'exécution

Reproductibilité

• Élevée : Description détaillée de la méthode, modèles d'invites, configuration
• Le code sera mis en open source
• Utilisation de référentiels publics et de modèles accessibles via API

Scénarios d'application

Scénarios appropriés :

1. Génération de code sans cas de test (phase de développement précoce)
2. Environnement d'exécution indisponible ou coûteux
3. Exploration de solutions diversifiées
4. Étape préalable aux méthodes dépendantes de l'exécution

Scénarios inappropriés :

1. Lorsque des cas de test suffisants sont disponibles (les méthodes dépendantes de l'exécution sont supérieures)
2. Code critique nécessitant une précision extrême
3. Budget de calcul extrêmement limité (amélioration faible)
4. Scénarios nécessitant une amélioration monotone garantie (risque de régression)

Références (Références clés)

1. Madaan et al. (2023) - Self-Refine : Méthode de base de cet article
2. Jain et al. (2024) - LiveCodeBench : Référentiel d'évaluation
3. Tang et al. (2024) - Application de l'équilibre exploration-exploitation à la correction de code
4. Xie et al. (2025) - Amélioration de la capacité critique par RL
5. Chen et al. (2021) - Codex et métrique pass@k
6. Snell et al. (2024) - Fondements théoriques de la mise à l'échelle du calcul au moment du test

Résumé

Cet article est une recherche empirique solide, concentrée sur un problème important mais négligé dans la génération de code : l'équilibre exploration-exploitation sans retours d'exécution. La méthode SELF-REDRAFT est simple et élégante, introduisant un mécanisme d'exploration par modification minimale. Bien que l'amélioration absolue soit limitée (0,615%), la valeur de l'article réside dans :

1. Attitude scientifique honnête : Ne pas exagérer les effets, clarifier les limitations et les écarts
2. Analyse mécanique approfondie : Identification de deux goulots d'étranglement - retours et discrimination
3. Trajectoire de recherche claire : Indication de directions pour les travaux futurs

La contribution principale de l'article n'est pas de proposer une nouvelle méthode puissante, mais de révéler systématiquement les insuffisances des LLM actuels dans l'équilibre autonome exploration-exploitation, ce qui est tout aussi important pour l'avancement du domaine. Pour les chercheurs, cela fournit des objectifs d'amélioration clairs ; pour les praticiens, cela rappelle les limitations des méthodes actuelles.

Recommandations pour les travaux ultérieurs, en se concentrant sur :

1. Entraînement de capacités critiques et discriminantes plus fortes
2. Exploration de l'intégration de connaissances externes et d'outils
3. Étude de stratégies d'équilibre adaptatives par modèle
4. Vérification sur plus de référentiels et de scénarios