Sintesi Tecnica: Scoperta di LLM Sensibile al Budget tramite Utilità della Frontiera Calibrata sui Costi

Formulazione del Problema

I grandi modelli linguistici (LLM) sono sempre più impiegati per la scoperta scientifica e algoritmica attraverso la ricerca durante l'inferenza, in cui candidati soluzioni vengono generati, valutati e raffinati sequenzialmente. In domini quali l'ottimizzazione matematica, la progettazione di algoritmi e la scoperta di programmi eseguibili, i valutatori deterministici forniscono segnali di qualità ripetibili. Tuttavia, gli attuali controller di scoperta adattivi assegnano il credito alle azioni di ricerca basandosi esclusivamente sul progresso del punteggio, ignorando l'eterogeneità dei costi delle azioni.

Sotto la tassazione API basata sui token, diverse azioni di ricerca comportano costi vastamente differenti. Un breve raffinamento può costare una singola generazione di riferimento, mentre una chiamata di guida a contesto lungo o un tentativo di riprova di un codice non valido può costarne sei o più. Quando un controller accredita un'azione ad alto costo e un'azione a basso costo allo stesso modo perché producono lo stesso miglioramento del punteggio, esso non tiene conto del costo opportunità del budget rimanente. Il documento formalizza questo come un problema di allocazione a livello di popolazione su uno spazio discreto di candidati eseguibili, dove l'orizzonte di ricerca effettivo è definito da un budget di token cumulativo e realizzato, piuttosto che da un numero fisso di iterazioni.

Gli autori dimostrano (Proposizione 1) che in istanze con costi delle azioni eterogenei, un controller "cieco ai costi" — uno la cui distribuzione di azioni dipende solo dalla cronologia dei punteggi e non dai costi realizzati — può ottenere solo una frazione trascurabile dell'obiettivo ottimale del budget all'aumentare del numero di frontiere di ricerca e delle disparità di costo.

Metodologia: CostAda

Per colmare questa lacuna, gli autori introducono CostAda, un controller adattivo calibrato sui costi progettato per la scoperta tramite LLM sotto espliciti budget di token lato ricerca. CostAda sostituisce il credito basato solo sul progresso con l'utilità della frontiera calibrata sui costi, che integra il progresso locale della frontiera, il miglioramento globale rispetto al migliore attuale, il costo dell'azione realizzato e il budget rimanente.

Il meccanismo centrale opera attraverso tre controlli accoppiati:

1. Utilità della Frontiera Calibrata sui Costi:
   L'utilità $u_t^{(k)}$ per una frontiera $k$ all'iterazione $t$ è definita come:
   $$u_t^{(k)} = \frac{\lambda_t g_t + (1 - \lambda_t) \delta_t^{(k)}}{d_t}$$
   Dove:

   • $g_t$ è il guadagno globale (miglioramento rispetto al miglior valore globale attuale).
   • $\delta_t^{(k)}$ è il guadagno locale (miglioramento rispetto all'archivio locale della frontiera).
   • $\lambda_t = 1 - \rho_t$ è il peso globale, condizionato sul rapporto di budget rimanente $\rho_t$. Man mano che il budget si esaurisce, il controller sposta il focus dallo sviluppo locale al miglioramento globale.
   • $d_t = 1 + \lambda_t^c \phi_t$ è un divisore di costo basato sul costo del passo realizzato normalizzato. Ciò assicura che guadagni uguali da azioni costose ricevano meno credito rispetto a quelli da azioni economiche.

2. Decisioni di Controllo Sensibili al Budget:

   • Intensità di Esplorazione Locale: L'ampiezza di campionamento attorno a una frontiera viene regolata in base alla sua utilità smussata. Un'alta utilità porta a un raffinamento a bassa intensità; una bassa utilità innesca un'esplorazione più ampia. Fondamentalmente, il rapporto di budget rimanente $\rho_t$ sopprime l'esplorazione costosa man mano che il budget si avvicina all'esaurimento.
   • Allocazione della Frontiera: Il controller alloca il budget futuro alle frontiere in base al guadagno globale per costo realizzato ($r_t^{(k)} = g_t / d_t$). Le frontiere che migliorano solo rispetto ad archivi locali deboli non ricevono credito di allocazione. Una regola dell'upper-confidence bound bilancia lo sfruttamento di frontiere ad alte prestazioni con l'esplorazione di quelle sotto-campionate, filtrata dal budget rimanente.
   • Intervento di Tattica a Budget Gestito: La guida di livello superiore (ad esempio, chiamate "guida" o "tattica") viene acquistata solo quando sono soddisfatti specifici predicati di evidenza: (1) il budget rimanente può permettere la guida più una riserva per i test; (2) vi è un'assenza sostenuta di progresso globale (stagnazione) o un accumulo di spese a basso rendimento; e (3) nessuna finestra di consolidamento è attiva. Ciò evita interventi costosi vicino all'orizzonte a meno che non siano strettamente necessari.

Contributi Chiave

1. Formulazione del Problema e Limite Teorico: Il documento formalizza la scoperta tramite LLM sotto espliciti budget di token lato ricerca e dimostra che le strategie di credito cieche ai costi rinunciano all'obiettivo del budget in contesti di costi eterogenei.
2. Utilità della Frontiera Calibrata sui Costi: Gli autori introducono un principio di credito che condiziona il progresso al costo dell'azione realizzato e al budget rimanente, garantendo che il costo opportunità di ogni azione sia esplicito.
3. Controller CostAda: Un'istanza di questo principio che coordina l'esplorazione locale con gate sul budget, l'allocazione della frontiera consapevole dei costi e l'intervento tattico a budget gestito.
4. Validazione Empirica: Esperimenti estesi che dimostrano come CostAda raggiunga una superiore efficienza del budget e una qualità della soluzione finale rispetto ai migliori baseline.

Risultati Sperimentali

Gli autori hanno valutato CostAda contro AdaEvolve (un baseline consapevole del progresso) ed EvoX (un controller di evoluzione delle strategie) su otto benchmark (che spaziano nel packing geometrico, geometria estrema, combinatoria additiva e ottimizzazione di programmi eseguibili) utilizzando due modelli backbone: GLM-5 e GPT-5.4.

• Efficienza: CostAda raggiunge la qualità del pieno budget del miglior baseline con al massimo la metà del budget in 12 dei 16 accoppiamenti benchmark–backbone.
• Qualità Finale: In entrambi i backbone, CostAda raggiunge la migliore qualità media finale su tutti gli otto benchmark.
• Percorso del Budget: A un quarto del budget, il punteggio normalizzato medio di CostAda supera la media del pieno budget del miglior baseline. Raggiunge l'area sotto la curva (AUC) normalizzata più alta in 15 dei 16 accoppiamenti benchmark–backbone.
• Stabilità: CostAda dimostra una varianza inferiore nei risultati rispetto ai baseline, in particolare su benchmark come Circle Packing Rect sotto GLM-5.

Significato e Rivendicazioni

Il documento afferma che CostAda cambia fondamentalmente il modo in cui le risorse di ricerca vengono gestite nella scoperta guidata da LLM. Trattando il costo realizzato e il budget rimanente come input di controllo attivi piuttosto che come variabili di contabilità post-hoc o semplici regole di arresto, CostAda allinea la strategia di ricerca con la realtà economica della tassazione basata sui token.

Gli autori sostengono che il loro approccio preservi la qualità della soluzione finale migliorando significativamente l'efficienza del budget. I risultati suggeriscono che la calibrazione dei costi è essenziale per scalare la scoperta tramite LLM, poiché ignorare l'eterogeneità dei costi porta a un'allocazione delle risorse subottimale che non può essere recuperata semplicemente smussando i segnali di progresso. Il lavoro dimostra che un controller può navigare efficacemente il compromesso tra esplorazione e sfruttamento quando il "costo" di un'azione è variabile quanto il "guadagno" che produce.