Résumé Technique : CodeRescue : Routage de Récupération Calibré sur Budget pour les Agents de Codage

1. Formulation du Problème

Le papier traite du défi de déploiement des agents de codage opérant dans des environnements exécutables où les tentatives échouées génèrent un retour d'information exploitable (par exemple, des erreurs de compilation, des tests échoués, des traces stderr) plutôt que de simples sorties incorrectes. Les systèmes actuels sensibles aux coûts traitent généralement l'échec du modèle comme une décision binaire : escalader immédiatement vers un modèle plus puissant et plus coûteux.

Les auteurs soutiennent que cette approche est sous-optimale pour le codage car le retour d'information d'exécution peut rendre les tentatives ultérieures d'un modèle peu coûteux pertinentes. Cela crée une question de déploiement budgétisé : lorsqu'un agent échoue, doit-il dépenser plus de calcul peu coûteux pour réparer la solution (réfléchir/reflect) ou replanifier, ou doit-il escalader vers un modèle plus fort ?

Le problème est formulé comme un routage de récupération post-échec. Étant donné un échec initial par un modèle peu coûteux, le système doit choisir parmi trois actions hétérogènes :

1. Réfléchir (Reflect) : Réviser la solution existante en utilisant le retour d'information d'exécution.
2. Replanifier (Replan) : Générer une nouvelle solution à partir d'un plan différent en utilisant le modèle peu coûteux.
3. Escalader (Escalate) : Déléguer le problème (avec le retour d'information) à un modèle plus fort et plus coûteux.

L'objectif est de maximiser le taux de résolution sous réserve d'un budget de récupération moyen ($B$) spécifié par l'utilisateur, sans réentraîner la politique pour chaque nouvelle contrainte budgétaire.

2. Méthodologie

2.1 Routeur de Récupération Supervisé

Le composant central est un routeur supervisé entraîné sur des déroulements d'exécution hors ligne.

• Entrée : Un contexte de récupération $x = (q, v_0, e_0)$, composé de l'énoncé du problème, du verdict d'exécution et de la trace stderr.
• Étiquetage : Pour chaque instance échouée, l'étiquette « oracle » est définie comme l'action réussie la plus économique ($a^\dagger$) parmi l'ensemble des actions qui résolvent l'instance ($S(x)$). Les instances où aucune action ne réussit sont exclues.
• Entraînement : Un modèle de langage (par exemple, Qwen3.5-4B) est affiné via l'entropie croisée pour prédire l'action réussie la moins coûteuse. Le routeur évalue les actions sur la base des log-probabilités et les normalise via softmax.

2.2 Politique Régularisée par le Coût

Pour permettre un déploiement sous des budgets variables sans réentraînement, les auteurs introduisent une pénalité de coût $\lambda \ge 0$. La politique $\pi_\lambda(x)$ sélectionne l'action maximisant :
$$s_\theta(a | x) - \lambda c(a, x)$$
où $s_\theta$ est le score du routeur et $c(a, x)$ est le coût de déploiement estimé.

• À mesure que $\lambda$ augmente, la politique s'oriente vers des actions moins coûteuses (réflexion/replanification).
• Cela crée un ensemble discret de points de fonctionnement (une frontière coût-qualité) dérivé d'un seul routeur entraîné.

2.3 Calibration Budgétaire Conforme (CRC)

Pour sélectionner la valeur de $\lambda$ appropriée pour un budget utilisateur spécifique $B$ avec des garanties statistiques, les auteurs appliquent le Contrôle de Risque Conforme (CRC).

• Mécanisme : En utilisant un ensemble de calibration de instances échouées, le système calcule le coût moyen empirique pour diverses valeurs de $\lambda$.
• Règle de Sélection : Il sélectionne la pénalité la moins restrictive $\hat{\lambda}$ telle que la contrainte de budget d'échantillon fini soit satisfaite :
  $$\frac{n \hat{C}_n(\lambda) + c_{\max}}{n + 1} \le B$$
  où $c_{\max}$ est un plafond de coût connu et le terme additif fournit une correction conforme de type « leave-one-out ».
• Garantie : Sous l'hypothèse d'échangeabilité, cette procédure garantit que le coût moyen attendu de récupération de la politique déployée sur les données de test futures ne dépasse pas $B$. Crucialement, cette garantie s'applique au coût, et non au taux de résolution, permettant des schémas de succès non monotones à travers les actions.

3. Contributions Clés

1. Routage de Récupération Post-Échec : Le papier formule la récupération des agents de codage comme un problème de routage sur des actions hétérogènes (réflexion, replanification, escalade) plutôt que comme une simple cascade vers un modèle plus fort.
2. Déploiement Contrôlable par le Budget : Il introduit une pénalité de coût calibrée par CRC qui permet à un seul routeur entraîné de fonctionner à plusieurs points budgétaires avec un contrôle marginal du coût attendu, éliminant ainsi le besoin de réentraîner pour différentes contraintes budgétaires.
3. Compétitivité de la Récupération Empirique : L'étude fournit des preuves empiriques que la récupération peu coûteuse et l'escalade de modèle présentent des schémas de succès complémentaires (c'est-à-dire que certains échecs ne sont solubles que par des actions peu coûteuses, d'autres uniquement par l'escalade, et certains par les deux), formant une frontière discrète coût-qualité.

4. Résultats Expérimentaux

Le système a été évalué sur cinq benchmarks de codage (APPS, TACO, BigCodeBench, LiveCodeBench, CodeContests) en utilisant GPT-5.4-NANO comme modèle peu coûteux et GPT-5.4 comme modèle fort.

• Efficacité du Routeur : Un routeur appris surpasse significativement les baselines à action fixe. Le routeur appris non contraint a atteint un taux de résolution de 81,7 % avec un coût moyen de 5,51 m$, contre 68,6 % pour l'approche « toujours escalader » à 7,22 m$.
• Complémentarité : L'analyse des actions les plus économiques de l'« oracle » a révélé que 28 % des échecs étaient solubles uniquement par des actions peu coûteuses, 45 % uniquement par l'escalade, et 27 % par les deux. Cette hétérogénéité justifie l'utilisation d'un routeur plutôt qu'une cascade fixe.
• Calibration Budgétaire : La frontière calibrée par CRC a démontré qu'avec un budget de 2,56 m$, le système a atteint un taux de résolution de 71,7 %. Cela a dépassé la baseline « toujours escalader » (68,6 %) tout en n'utilisant que 35 % du coût moyen de la stratégie « toujours escalader ».
• Baselines : Le routeur appris a surpassé les routeurs basés uniquement sur le prompt (LLM zero-shot agissant comme routeurs) et les baselines de cascade binaire, confirmant que le signal de routage nécessite un apprentissage à partir de déroulements plutôt qu'un simple ingénierie de prompt.

5. Signification et Revendications

Le papier affirme que traiter les échecs de codage comme un problème de réparation diagnostiquable plutôt que comme un simple écart de capacité permet une allocation de ressources plus efficace. En découplant l'entraînement du routeur du budget de déploiement via le CRC, le système offre un mécanisme pratique pour un inférence contrôlée par le budget.

Les auteurs soulignent que leur approche ne prétend pas contrôler le taux de résolution de manière conforme ; elle fournit une garantie de coût, tandis que les améliorations du taux de résolution sont des observations empiriques. Le travail suggère que pour les agents de codage, la « prochaine étape utile la moins chère » n'est souvent pas le modèle le plus fort, mais une action de récupération spécifique adaptée au mode d'échec, et que cette décision peut être prise dynamiquement sous des contraintes budgétaires strictes.

Limites notées par les auteurs :

• La récupération est modélisée comme une décision post-échec unique, alors que les agents réels peuvent itérer sur plusieurs cycles.
• L'étiquette « le plus économique réussi » est un proxy et non une estimation de probabilité calibrée.
• Le CRC contrôle le coût attendu, pas le taux de résolution, ce qui signifie que les améliorations de la qualité restent des observations empiriques.