Technische Samenvatting: Budgetbewuste LLM-ontdekking via Kosten-gekalibreerde Frontier Utility

Probleemformulering

Large Language Models (LLM's) worden steeds vaker ingezet voor wetenschappelijke en algoritmische ontdekking via inferentie-tijd zoekprocessen, waarbij kandidaat-oplossingen sequentieel worden gegenereerd, geëvalueerd en verfijnd. In domeinen zoals wiskundige optimalisatie, algoritmeontwerp en de ontdekking van uitvoerbare programma's bieden deterministische evaluatoren herhaalbare kwaliteitssignalen. Bestaande adaptieve ontdekkingscontrollers wijzen echter krediet toe aan zoekacties uitsluitend op basis van scoreprogressie, waarbij de heterogeniteit van actiekosten wordt genegeerd.

Onder token-gebaseerde API-prijzen brengen verschillende zoekacties zeer uiteenlopende kosten met zich mee. Een korte verfijning kan de kosten van één referentiegenereeractie hebben, terwijl een lang-context begeleiding of een poging tot herstel van ongeldige code zes of meer kan kosten. Wanneer een controller een dure actie en een goedkope actie gelijkwaardig krediteert omdat ze dezelfde scoreverbetering opleveren, houdt deze geen rekening met de opportuniteitskosten van het resterende budget. De paper formaliseert dit als een populatie-niveau allocatieprobleem over een discrete ruimte van uitvoerbare kandidaten, waarbij de effectieve zoekhorizon wordt gedefinieerd door een cumulatief, gerealiseerd tokenbudget in plaats van een vast aantal iteraties.

De auteurs bewijzen (Propositie 1) dat in instanties met heterogene actiekosten, een "kosten-blinde" controller — een controller wiens actieverdeling enkel afhangt van scoregeschiedenis en niet van gerealiseerde kosten — slechts een verwaarloosbaar deel van het optimale budgettaire objectief kan bereiken naarmate het aantal zoekfrontiers en de kostenverschillen toenemen.

Methodologie: CostAda

Om dit gat te dichten, introduceren de auteurs CostAda, een kosten-gekalibreerde adaptieve controller ontworpen voor LLM-ontdekking onder expliciete zoekzijde tokenbudgetten. CostAda vervangt progressie-gebaseerde kredietverlening door kosten-gekalibreerde frontier utility, die lokale frontier-progressie, globale verbetering ten opzichte van de beste tot nu toe, gerealiseerde actiekosten en het resterende budget integreert.

Het kernmechanisme werkt via drie gekoppelde controles:

1. Kosten-gekalibreerde Frontier Utility:
   De utility $u_t^{(k)}$ voor een frontier $k$ op iteratie $t$ is gedefinieerd als:
   $$u_t^{(k)} = \frac{\lambda_t g_t + (1 - \lambda_t) \delta_t^{(k)}}{d_t}$$
   Waarbij:

   • $g_t$ de globale winst (verbetering ten opzichte van de globale beste tot nu toe) is.
   • $\delta_t^{(k)}$ de lokale winst (verbetering ten opzichte van het lokale archief van de frontier) is.
   • $\lambda_t = 1 - \rho_t$ de globale weging is, geconditioneerd op de resterende budgetratio $\rho_t$. Naarmate het budget slinkt, verschuift de controller de focus van lokale ontwikkeling naar globale verbetering.
   • $d_t = 1 + \lambda_t^c \phi_t$ een kosten-divisor is gebaseerd op de genormaliseerde gerealiseerde stapkosten. Dit zorgt ervoor dat gelijke winsten uit dure acties minder krediet ontvangen dan goedkope acties.

2. Budgetbewuste Controlebeslissingen:

   • Lokale Exploratie-intensiteit: De breedte van de bemonstering rond een frontier wordt aangepast op basis van de gladgestreken utility. Hoge utility leidt tot lage-intensiteit verfijning; lage utility triggert bredere exploratie. Cruciaal is dat de resterende budgetratio $\rho_t$ dure exploratie onderdrukt naarmate het budget uitgeput raakt.
   • Frontier Allocatie: De controller wijst toekomstig budget toe aan frontiers op basis van globale winst per gerealiseerde kosten ($r_t^{(k)} = g_t / d_t$). Frontiers die enkel verbeteren ten opzichte van zwakke lokale archieven, ontvangen geen allocatiekrediet. Een upper-confidence bound regel balanceert de exploitatie van hoogpresterende frontiers met de exploratie van onder-gesamplede frontiers, afgeschermd door het resterende budget.
   • Budgettaire Tactic Interventie: Hogere-orde begeleiding (bijv. "guide" of "tactic" calls) wordt alleen aangekocht wanneer specifieke bewijspredicaten zijn vervuld: (1) het resterende budget kan de begeleiding plus een reserve voor testen bekostigen; (2) er is een aanhoudende afwezigheid van globale progressie (stagnatie) of geaccumuleerde laag-rendabele uitgaven; en (3) er is geen consolidatievenster actief. Dit voorkomt dure interventies nabij de horizon, tenzij deze strikt noodzakelijk zijn.

Belangrijkste Bijdragen

1. Probleemformulering en Theoretische Grens: De paper formaliseert LLM-ontdekking onder expliciete zoekzijde tokenbudgetten en bewijst dat kosten-blinde kredietstrategieën het budgettaire objectief opgeven in scenario's met heterogene kosten.
2. Kosten-gekalibreerde Frontier Utility: De auteurs introduceren een kredietprincipe dat progressie conditioneert op de gerealiseerde actiekosten en het resterende budget, waardoor de opportuniteitskosten van elke actie expliciet worden.
3. CostAda Controller: Een instantie van dit principe die budget-afgeschermde lokale exploratie, kosten-bewuste frontier allocatie en budgettaire tactic interventie coördineert.
4. Empirische Validatie: Uitgebreide experimenten die aantonen dat CostAda een superieure budgetefficiëntie en finale oplossingskwaliteit bereikt vergeleken met state-of-the-art baselines.

Experimentele Resultaten

De auteurs evalueerden CostAda tegenover AdaEvolve (een progressie-bewuste baseline) en EvoX (een strategie-evolutie controller) over acht benchmarks (variërend van geometrische pakking, extremale geometrie, additieve combinatoriek tot uitvoerbare programma-optimalisatie) met twee backbone modellen: GLM-5 en GPT-5.4.

• Efficiëntie: CostAda bereikt de kwaliteit van de sterkste baseline met het volledige budget met maximaal de helft van het budget in 12 van de 16 benchmark-backbone paren.
• Finale Kwaliteit: Over beide backbones heen bereikt CostAda de hoogste gemiddelde finale kwaliteit op alle acht benchmarks.
• Budgetpad: Bij een kwart van het budget overtreft de gemiddelde genormaliseerde score van CostAda de gemiddelde volledige-budget score van de sterkste baseline. Het bereikt de hoogste genormaliseerde Area Under the Curve (AUC) in 15 van de 16 benchmark-backbone paren.
• Stabiliteit: CostAda vertoont een lagere variantie in resultaten vergeleken met baselines, met name op benchmarks zoals Circle Packing Rect onder GLM-5.

Betekenis en Claims

De paper claimt dat CostAda fundamenteel verandert hoe zoekresources worden beheerd in LLM-gestuurde ontdekking. Door gerealiseerde kosten en het resterende budget te behandelen als actieve controle-inputs in plaats van post-hoc boekhoudkundige variabelen of eenvoudige stopregels, brengt CostAda de zoekstrategie in lijn met de economische realiteit van token-gebaseerde prijsstelling.

De auteurs stellen dat hun aanpak de finale oplossingskwaliteit behoudt terwijl de budgetefficiëntie aanzienlijk wordt verbeteren. De resultaten suggereren dat kosten-kalibratie essentieel is voor het schalen van LLM-ontdekking, aangezien het negeren van kosten-heterogeniteit leidt tot suboptimale resource-allocatie die niet kan worden hersteld door simpelweg de progressie-signalen te middelen. Het werk demonstreert dat een controller effectief de trade-off tussen exploratie en exploitatie kan navigeren wanneer de "kosten" van een actie even variabel zijn als de "winst" die het produceert.