Résumé Technique : Découverte par LLM Sensible au Budget via l'Utilité de Frontière Calibrée sur les Coûts

Formulation du Problème

Les grands modèles de langage (LLM) sont de plus en plus employés pour la découverte scientifique et algorithmique via la recherche au moment de l'inférence, où des solutions candidates sont générées, évaluées et affinées séquentiellement. Dans des domaines tels que l'optimisation mathématique, la conception d'algorithmes et la découverte de programmes exécutables, des évaluateurs déterministes fournissent des signaux de qualité reproductibles. Cependant, les contrôleurs de découverte adaptatifs existants attribuent généralement le crédit aux actions de recherche en se basant uniquement sur la progression du score, ignorant l'hétérogénéité des coûts d'action.

Sous un régime de tarification par jetons (tokens) via API, différentes actions de recherche engendrent des coûts très disparates. Un raffinement court peut coûter une seule génération de référence, tandis qu'un appel de guidage à contexte long ou une tentative de réexécution d'un code invalide peut en coûter six ou plus. Lorsqu'un contrôleur attribue de manière égale le crédit à une action coûteuse et à une action peu coûteuse parce qu'elles produisent la même amélioration de score, il ne tient pas compte du coût d'opportunité du budget restant. Le papier formalise cela comme un problème d'allocation au niveau de la population sur un espace discret de candidats exécutables, où l'horizon de recherche effectif est défini par un budget de jetons cumulé et réalisé plutôt que par un nombre fixe d'itérations.

Les auteurs prouvent (Proposition 1) que dans des cas présentant des coûts d'action hétérogènes, un contrôleur « aveugle au coût » — dont la distribution d'actions dépend uniquement de l'historique des scores et non des coûts réalisés — ne peut atteindre qu'une fraction négligeable de l'objectif budgétisé optimal à mesure que le nombre de frontières de recherche et les disparités de coûts augmentent.

Méthodologie : CostAda

Pour combler cette lacune, les auteurs introduisent CostAda, un contrôleur adaptatif calibré sur les coûts, conçu pour la découverte par LLM sous des budgets de jetons explicites côté recherche. CostAda remplace le crédit basé uniquement sur la progression par une utilité de frontière calibrée sur les coûts, qui intègre la progression locale de la frontière, l'amélioration globale par rapport au meilleur score actuel, le coût d'action réalisé et le budget restant.

Le mécanisme central opère via trois contrôles couplés :

1. Utilité de Frontière Calibrée sur les Coûts :
   L'utilité $u_t^{(k)}$ pour une frontière $k$ à l'itération $t$ est définie par :
   $$u_t^{(k)} = \frac{\lambda_t g_t + (1 - \lambda_t) \delta_t^{(k)}}{d_t}$$
   Où :

   • $g_t$ est le gain global (amélioration par rapport au meilleur score global actuel).
   • $\delta_t^{(k)}$ est le gain local (amélioration par rapport à l'archive locale de la frontière).
   • $\lambda_t = 1 - \rho_t$ est le poids global, conditionné par le ratio de budget restant $\rho_t$. À mesure que le budget s'épuise, le contrôleur déplace son attention du développement local vers l'amélioration globale.
   • $d_t = 1 + \lambda_t^c \phi_t$ est un diviseur de coût basé sur le coût de l'étape réalisée normalisé. Cela garantit que des gains égaux provenant d'actions coûteuses reçoivent moins de crédit que ceux provenant d'actions peu coûteuses.

2. Décisions de Contrôle Sensibles au Budget :

   • Intensité d'Exploration Locale : La largeur d'échantillonnage autour d'une frontière est ajustée en fonction de son utilité lissée. Une utilité élevée conduit à un raffinement de faible intensité ; une faible utilité déclenche une exploration plus large. Crucialement, le ratio de budget restant $\rho_t$ supprime l'exploration coûteuse à mesure que le budget approche de l'épuisement.
   • Allocation de Frontière : Le contrôleur alloue le budget futur aux frontières en fonction du gain global par coût réalisé ($r_t^{(k)} = g_t / d_t$). Les frontières qui n'améliorent que des archives locales faibles ne reçoivent aucun crédit d'allocation. Une règle de borne supérieure de confiance (Upper Confidence Bound) équilibre l'exploitation des frontières performantes avec l'exploration de celles sous-échantillonnées, le tout encadré par le budget restant.
   • Intervention de Tactique Budgétisée : Les guidages de haut niveau (ex: appels de type "guide" ou "tactic") ne sont achetés que lorsque des prédicats de preuve spécifiques sont remplis : (1) le budget restant peut permettre le guidage plus une réserve pour les tests ; (2) il y a une absence soutenue de progrès global (stagnation) ou une accumulation de dépenses à faible rendement ; et (3) aucune fenêtre de consolidation n'est active. Cela empêche les interventions coûteuses à l'approche de l'horizon, sauf si elles sont strictement nécessaires.

Contributions Clés

1. Formalisation du Problème et Borne Théorique : Le papier formalise la découverte par LLM sous des budgets de jetons explicites côté recherche et prouve que les stratégies de crédit aveugles au coût sacrifient l'objectif budgétisé dans des contextes de coûts hétérogènes.
2. Utilité de Frontière Calibrée sur les Coûts : Les auteurs introduisent un principe de crédit qui conditionne la progression au coût d'action réalisé et au budget restant, garantissant que le coût d'opportunité de chaque action est explicite.
3. Contrôleur CostAda : Une instanciation de ce principe qui coordonne l'exploration locale budgétisée, l'allocation de frontière sensible aux coûts et l'intervention de tactique budgétisée.
4. Validation Empirique : Des expériences approfondies démontrant que CostAda atteint une efficacité de budget et une qualité de solution finale supérieures par rapport aux autres méthodes de pointe.

Résultats Expérimentaux

Les auteurs ont évalué CostAda contre AdaEvolve (un baseline sensible à la progression) et EvoX (un contrôleur d'évolution de stratégie) sur huit benchmarks (couvrant le packing géométrique, la géométrie extrémale, la combinatoire additive et l'optimisation de programmes exécutables) en utilisant deux modèles de base : GLM-5 et GPT-5.4.

• Efficacité : CostAda atteint la qualité du meilleur baseline avec au plus la moitié du budget dans 12 des 16 paires benchmark–backbone.
• Qualité Finale : Sur les deux backbones, CostAda atteint la meilleure qualité moyenne finale sur les huit benchmarks.
• Trajectoire de Budget : À un quart du budget, le score normalisé moyen de CostAda dépasse la moyenne du plein budget du meilleur baseline. Il atteint l'aire sous la courbe (AUC) normalisée la plus élevée sur 15 des 16 paires benchmark–backbone.
• Stabilité : CostAda démontre une variance plus faible dans les résultats par rapport aux baselines, particulièrement sur des benchmarks comme Circle Packing Rect sous GLM-5.

Signification et Revendications

Le papier affirme que CostAda change fondamentalement la gestion des ressources de recherche dans la découverte pilotée par LLM. En traitant le coût réalisé et le budget restant comme des entrées de contrôle actives plutôt que comme des variables comptables post-hoc ou de simples règles d'arrêt, CostAda aligne la stratégie de recherche avec la réalité économique de la tarification par jetons.

Les auteurs soutiennent que leur approche préserve la qualité de la solution finale tout en améliorant considérablement l'efficacité du budget. Les résultats suggèrent que la calibration des coûts est essentielle pour passer à l'échelle la découverte par LLM, car ignorer l'hétérogénéité des coûts conduit à une allocation de ressources sous-optimale qui ne peut être récupérée par un simple lissage des signaux de progression. Le travail démontre qu'un contrôleur peut naviguer efficacement entre l'exploration et l'exploitation lorsque le « coût » d'une action est aussi variable que le « gain » qu'elle produit.