🤖 AI

Exploit More, Explore Smarter for Budget-Constrained Agentic Search

Questo articolo introduce ExTS, una nuova politica di ricerca ad albero che ottimizza la ricerca agentica con budget limitato trattando l'espansione come una decisione sul valore dell'informazione attraverso la modellazione discriminativa della ricompensa, figli virtuali stocastici e ramificazione condizionata alla qualità, ottenendo miglioramenti costanti delle prestazioni in compiti diversificati rispetto ai metodi standard.

Autori originali: Haoyang Fang, Bernie Wang

Pubblicato 2026-08-26

📖 6 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Haoyang Fang, Bernie Wang

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Nel mondo in rapida evoluzione dell'intelligenza artificiale, è emersa una nuova classe di sistemi che non si limitano a rispondere alle domande, ma cercano attivamente soluzioni. Questi sistemi "agentici" agiscono come esploratori digitali, proponendo idee, testandole e perfezionando i loro tentativi migliori ancora e ancora. Che stiano scrivendo codice informatico, progettando composti chimici o risolvendo complessi enigmi logici, questi agenti si affidano a un ciclo di generazione e validazione. Creano una soluzione candidata, la sottopongono a un test per vedere quanto funzioni bene e poi usano quel feedback per creare una versione migliore. Tuttavia, questo processo è costoso. Ogni volta che il sistema genera una nuova idea o esegue un test, consuma una risorsa limitata: un budget computazionale. In molti scenari del mondo reale, questo budget è ristretto, permettendo solo poche decine o poche centinaia di tentativi prima che il sistema debba fermarsi. La sfida centrale per i ricercatori è come spendere saggiamente questo budget limitato. Se il sistema spreca i suoi tentativi su vicoli ciechi, non riesce a trovare la soluzione migliore possibile. Se è troppo cauto, potrebbe perdere una svolta che si trova solo pochi passi più avanti lungo un percorso promettente.

Per anni, il metodo standard per navigare in questi alberi di ricerca è stato una strategia mutuata dagli algoritmi di gioco, che bilancia due istinti contrastanti: esplorazione e sfruttamento. L'esplorazione significa provare nuovi percorsi non testati per vedere se promettono qualcosa, mentre lo sfruttamento significa scavare più a fondo in percorsi che hanno già mostrato buoni risultati. L'approccio tradizionale tratta ogni nuovo ramo dell'albero di ricerca con una certa dose di curiosità, spesso espandendo tutte le opzioni disponibili prima di impegnarsi in una singola decisione. Questo funziona bene quando c'è tempo e denaro abbondanti per esplorare tutto. Ma nel mondo ad alto rischio e con budget limitati degli agenti IA moderni, questo approccio "provare tutto" spesso fallisce. Distribuisce le risorse limitate troppo sottilmente su un albero ampio e poco profondo, lasciando le idee più promettenti poco sviluppate. Il sistema finisce con una mappa ampia di molte soluzioni mediocri piuttosto che una comprensione profonda di alcune eccellenti.

Per risolvere questo problema, i ricercatori di Amazon AGI hanno introdotto una nuova politica di ricerca chiamata ExTS. Invece di espandere ciecamente ogni ramo, questo nuovo metodo tratta la decisione di creare un nuovo ramo come un investimento calcolato. Pone una domanda critica prima di spendere qualsiasi budget: il valore potenziale della creazione di un nuovo percorso vale il costo? Il sistema lo fa osservando la storia dei propri successi e fallimenti. Se una particolare linea di ragionamento ha prodotto molti tentativi falliti, il sistema impara a smettere di espandere quel percorso e a concentrare invece la sua energia sull'approfondimento delle linee che stanno già funzionando. Filtra efficacementamente il rumore, ignorando i vicoli ciechi che avrebbero consumato preziose risorse nei sistemi precedenti.

I ricercatori hanno testato questo approccio in quattro campi molto diversi: l'ottimizzazione delle istruzioni per i modelli linguistici, la generazione di codice informatico, la deduzione della struttura delle molecole da dati spettrali e la progettazione di flussi di lavoro automatizzati. In ogni caso, hanno dato al nuovo sistema lo stesso budget ristretto con cui i metodi precedenti dovevano lavorare. I risultati sono stati coerenti. Essendo più intelligenti su dove spendere i propri soldi, il nuovo sistema ha trovato costantemente soluzioni migliori rispetto ai metodi specializzati progettati per ciascun compito specifico. Ad esempio, nel compito di ottimizzazione dei prompt per il question-answering, il nuovo metodo ha migliorato l'accuratezza di oltre il dieci percento rispetto al precedente approccio migliore. Nella generazione di codice, ha risolto problemi significativamente più difficili, trovando soluzioni che i vecchi metodi avevano mancato. Anche nel campo altamente tecnico dell'elucidazione della struttura molecolare, dove il sistema doveva determinare la forma di una molecola dalla sua firma spettrale, il nuovo metodo ha ottenuto un'accuratezza superiore con lo stesso numero di tentativi.

Un'intuizione chiave dietro questo successo è che il nuovo sistema non guarda solo al punteggio di un singolo tentativo; guarda al modello dei punteggi. In molti di questi compiti, la differenza tra una buona soluzione e una ottima è sottile, e i punteggi possono essere raggruppati molto vicini tra loro. I vecchi metodi faticavano a distinguere, trattando tutte le opzioni come circa uguali. Il nuovo sistema utilizza una tecnica per amplificare queste piccole differenze, permettendogli di distinguere tra un percorso leggermente migliore e uno veramente eccellente. Utilizza anche un concetto di "figlio virtuale" per simulare cosa potrebbe accadere se dovesse creare un nuovo ramo. Campionando dalla storia di ciò che ha funzionato in precedenza, può stimare il valore di un nuovo percorso senza dover effettivamente spendere il budget per costruirlo. Se la simulazione suggerisce che il nuovo percorso è improbabile che sia fruttuoso, il sistema lo salta completamente e va più a fondo nel percorso provato.

I ricercatori hanno anche scoperto che non tutti i problemi di ricerca sono uguali. Alcuni compiti sono soggetti a frequenti fallimenti, dove la maggior parte dei tentativi risulta in errori, mentre altri sono più stabili. Alcuni compiti hanno punteggi che cambiano drasticamente con le nuove scoperte, mentre altri rimangono costanti. Il nuovo sistema è abbastanza flessibile da adattarsi a questi diversi paesaggi. Eseguendo un piccolo test preliminare per comprendere la natura del problema, il sistema può regolare leggermente la sua strategia per adattarsi alle sfide specifiche del compito. Questa adattabilità gli permette di performare bene in una vasta gamma di domini senza la necessità di un nuovo design completo per ciascuno di essi.

Lo studio dimostra che il modo in cui un agente IA spende il suo budget computazionale è importante quanto l'intelligenza che possiede. Riprogettando il processo di ricerca per essere più selettivo e più consapevole della qualità del proprio progresso, il sistema può ottenere risultati significativamente migliori con lo stesso sforzo. Questo approccio offre una guida pratica per costruire agenti IA più efficienti che possano risolvere problemi complessi senza richiedere un'infinita potenza di calcolo. I risultati suggeriscono che, in futuro, i sistemi di IA più efficaci non saranno necessariamente quelli che provano più cose, ma quelli che sanno esattamente quali cose vale la pena provare.

Riassunto Tecnico: Esplorare di più, Esplorare meglio per la Ricerca Agente in Regimi a Budget Limitato

Definizione del Problema

Il documento affronta la ricerca agente con budget limitato (budget-constrained agentic search), un regime in cui gli agenti basati su Large Language Model (LLM) devono proporre e raffinare iterativamente dei candidati (ad esempio, prompt, codice, strutture molecolari) sotto un rigoroso budget di valutazione. In questi scenari, la validazione è costosa, la generazione richiede molteplici chiamate al modello, o entrambi i fattori. Il budget totale è spesso limitato a decine o centinaia di chiamate.

Gli autori identificano che la ricerca standard Monte Carlo Tree Search (MCTS), specificamente la politica Upper Confidence Bound applied to Trees (UCT), performa scarsamente in questo regime a causa di tre limitazioni strutturali:

Dominanza del bonus di esplorazione: Con bassi conteggi di visite, il termine di esplorazione domina, causando l'effetto per cui l'algoritmo tratta nodi non promettenti come altrettanto attraenti rispetto a quelli promettenti.
Espansione completa forzata: La MCTS standard forza l'espansione di tutti i fratelli prima di approfondire una catena promettente, sprecando budget su rami non promettenti.
Branching (ramificazione) agnostico rispetto al punteggio: Le decisioni di espansione sono indipendenti dalla qualità del nodo; l'algoritmo non limita la ramificazione in base al fatto che il punteggio di un nodo giustifichi il costo.

Le soluzioni esistenti si concentrano spesso sul "harness" (framework che avvolgono la ricerca) o mirano a tipi di task specifici con algoritmi personalizzati (ad esempio, Thompson sampling per il codice, selezione della frontiera di Pareto per i prompt), mancando di una politica unificata capace di adattarsi a diversi problemi agentici.

Metodologia: ExTS

Gli autori introducono ExTS (Exploit More, Explore Smarter), una politica di ricerca ad albero che riprogetta congiuntamente le decisioni di selezione e di espansione dei nodi. ExTS tratta l'espansione stessa come una decisione di Valore dell'Informazione (VOI). Opera attraverso tre meccanismi principali:

1. Modellazione Discriminativa del Premio (Discriminative Reward Shaping)

Per affrontare il problema dei punteggi di validazione grezzi che si raggruppano in intervalli stretti (facendo apparire i nodi ugualmente attraenti), ExTS applica una funzione di modellazione non lineare $\phi$ ai premi.

Meccanismo: Utilizza una funzione convessa controllata dalla temperatura $\phi(r) = \frac{e^{\hat{r}/T} - 1}{e^{1/T} - 1}$ (dove $T < 1$ ) per comprimere i punteggi bassi e amplificare quelli alti.
Pesatura del tasso di successo: Incorpora un peso del tasso di successo $(n^+_v / n_v)^\alpha$ per scontare i nodi i cui sottotitoli producono principalmente output non validi (fallimenti).
Risultato: Questo crea segnali di selezione efficaci anche quando i punteggi grezzi sono strettamente raggruppati, permettendo all'algoritmo di distinguere tra i candidati.

2. Stima del VOI tramite il Figlio Virtuale

ExTS riformula l'espansione come una decisione tra l'approfondimento di una catena esistente o la creazione di un nuovo ramo.

Meccanismo: In ogni nodo interno, ExTS calcola un punteggio di un figlio virtuale. Questo figlio virtuale rappresenta il valore atteso della creazione di un nuovo ramo.
Campionamento: Il punteggio del figlio virtuale è stimato campionando $k$ punteggi dalla cronologia dei premi del genitore (inclusi il punteggio del genitore stesso) e applicando la funzione di modellazione. Il numero di campioni $k$ è proporzionale al conteggio delle visite "quota equa" (fair-share), catturando l'incertezza del campione finito.
Decisione: L'algoritmo confronta il punteggio del miglior figlio reale contro quello del figlio virtuale. Se il punteggio del figlio virtuale è superiore, l'algoritmo seleziona il nodo corrente per l'espansione (creando un nuovo ramo); altrimenti, ricorsivamente entra nel miglior figlio reale. Ciò consente alla ricerca di approfondire le catene promettenti senza espandere completamente i fratelli non promettenti.

3. Branching Condizionato alla Qualità

ExTS limita l'espansione in base alla qualità del nodo per evitare lo spreco di budget.

Gate di Espansione: I nodi che non sono radici sono autorizzati ad espandersi solo se il loro punteggio di validazione supera un $\tau$ -quantile dei punteggi della popolazione. I nodi sotto la soglia possono ancora essere visitati e aggiornati, ma non possono generare nuovi figli.
Progressive Widening condizionata alla qualità: Il fattore di ramificazione massimo cresce con il conteggio delle visite (allargamento progressivo) solo per i nodi la cui qualità giustifica il costo (ovvero quelli sopra un quantile più alto $\gamma$ ). I nodi a basso punteggio rimangono limitati a un piccolo fattore di ramificazione iniziale $M_0$ .

Contributi Chiave

Politica Unificata: ExTS fornisce una singola configurazione fissa che è competitiva o migliora le baseline specifiche per task in quattro domini diversi: ottimizzazione dei prompt, generazione di codice, eluzione di strutture molecolari e ottimizzazione di workflow agentici.
Riprogettazione Strutturale: A differenza del lavoro precedente che si limita a regolare le costanti di esplorazione, ExTS introduce meccanismi strutturali (figli virtuali, gating della qualità) per decidere dove e quando espandere, piuttosto che solo quanto esplorare.
Diagnostica di Pilotaggio (Pilot-Run Diagnostics): Gli autori introducono quattro diagnostiche ( $\hat{\sigma}_A$ , $\hat{\sigma}_f$ , $\kappa$ , $\rho$ ) per caratterizzare il panorama di ricerca di un task. Questi parametri spiegano perché diversi task rispondono a diverse configurazioni e offrono una guida pratica per adattare gli iperparametri (ad esempio, regolando la temperatura $T$ per task a basso drift o l'esponente di successo $\alpha$ per task ad alto tasso di fallimento).

Risultati

ExTS è stato valutato in quattro domini con una singola configurazione fissa e una versione adattata ( $ExTS^*$ ) che regola 1-2 iperparametri basandosi sulle diagnostiche pilota.

Ottimizzazione dei Prompt (HotpotQA, HoVeR): ExTS ha migliorato la baseline GEPA Pareto di +10.8% su HotpotQA (con una varianza 6.4 $\times$ inferiore) e ha eguagliato le prestazioni su HoVeR. La versione adattata $ExTS^*$ ha ulteriormente migliorato HotpotQA portandolo al 66.00%.
Generazione di Codice (LiveCodeBench): Sul split "hard", ExTS ha raggiunto il 19.1% di pass@1, superando AB-MCTS-A (17.1%) e lo Standard MCTS (18.1%). La configurazione fissa ha ottenuto il 46.2% complessivo di pass@1, mentre la versione adattata ( $ExTS^*$ ) ha raggiunto il 47.4%.
Eluzione di Strutture Molecolari (K-MSE): ExTS ha migliorato l'accuratezza dell'esatta corrispondenza di +1.3% rispetto alla baseline K-MSE (91.0% vs 89.8%).
Ottimizzazione di Workflow Agentici (DROP): ExTS ha ottenuto la dominanza di Pareto con un'accuratezza media del 90.96% (varianza e costo minimi) rispetto alle baseline CoT e AFlow. La versione adattata ( $ExTS^*$ ) ha ulteriormente migliorato l'accuratezza media al 91.54%.
Scalabilità del Budget: ExTS dimostra una conversione più efficiente da budget a performance, particolarmente sugli istanze difficili dove il raffinamento iterativo è critico. Supera la MCTS standard a bassi budget (es. $B \approx 8$ ) e mantiene un divario crescente all'aumentare del budget.

Significato e Rivendicazioni

Il documento sostiene che ExTS rappresenti un passaggio dalla regolazione delle costanti di esplorazione alla riprogettazione strutturale della politica di ricerca. Gli autori sostengono che, nei regimi a budget limitato, la decisione di se espandere è tanto consequenziale quanto la decisione di quale figlio visitare.

Generalizzabilità: Una singola configurazione fissa funziona attraverso domini strutturalmente distinti, suggerendo che i meccanismi di modellazione del premio, stima del figlio virtuale e gating della qualità affrontino i limiti fondamentali della MCTS nella ricerca ad alta intensità di validazione.
Adattabilità: Le diagnostiche di pilotaggio forniscono un quadro pratico per comprendere la "forma" dei problemi di ricerca agentica, spiegando perché nessuna singola configurazione domini universalmente e offrendo una via per l'adattamento leggero.
Efficienza: Bloccando l'espansione sulla qualità e inquadrandola come una decisione VOI, ExTS reindirizza il budget dall'esplorazione breadth-first verso un raffinamento selettivo, ottenendo prestazioni superiori con lo stesso o un costo computazionale inferiore.

Gli autori segnalano alcune limitazioni, tra cui la dipendenza da un singolo modello per dominio a causa dei costi delle API e il fatto che le diagnostiche pilota descrivono il panorama così come visto da una specifica configurazione piuttosto che le proprietà intrinseche del dominio. Tuttavia, dimostrano che anche senza l'adattamento del pilotaggio, ExTS supera o eguaglia le baseline specializzate.