Analysis of Optimality of Large Language Models on Planning Problems

1. Il Problema e il Contesto

Il lavoro esamina la capacità dei moderni Modelli Linguistici di Grande Dimensione (LLM) di eseguire pianificazione autonoma, un campo storicamente dominato da algoritmi di ricerca classici (come A* o LAMA).
Mentre le valutazioni precedenti si concentravano sul tasso di successo binario (successo/fallimento), questo studio indaga la qualità della pianificazione (ottimalità) e i limiti strutturali della capacità di ragionamento degli LLM.

Il dominio di test scelto è il Blocksworld, un problema classico di IA in cui un agente deve spostare blocchi etichettati da una configurazione iniziale a una configurazione obiettivo tramite azioni primitive (prendere, mettere giù, impilare, sfilare).

• Ipotesi di partenza: Gli LLM potrebbero fallire generalizzando o affidarsi a euristiche semplici invece di un ragionamento sistematico.
• Approccio topologico: Gli autori mappano il problema del Blocksworld su una struttura grafica isomorfa chiamata $P^*$ (Path-Star). In questa rappresentazione, il "tavolo" è il nodo radice e ogni torre di blocchi è un ramo disgiunto. Risolvere il problema equivale a eseguire una serie di traversate dinamiche su questo grafo, identificando i rami corretti e tracciando le catene di dipendenza.

2. Metodologia

Gli autori hanno creato un dataset sintetico sistematico per stressare le capacità di pianificazione lungo tre assi di complessità:

1. Profondità (Depth): Altezza delle torri (fino a 1000 blocchi).
2. Larghezza (Width): Numero di torri (fino a 100).
3. Composizionalità (Compositionality): Numero di blocchi obiettivo (fino a 220).

Curricula di valutazione:

• Harvest: Scalare il numero di blocchi obiettivo (uno per torre).
• High Towers: Scalare l'altezza delle torri con un solo obiettivo.
• Grand Challenge: Scalare simultaneamente profondità, larghezza e numero di obiettivi.
• Interleaved Harvest: Una variante più complessa con due obiettivi per torre che richiedono dipendenze incrociate.

Strategia di Prompting:
Per isolare le capacità di ragionamento intrinseche, è stata utilizzata una strategia di In-Context Learning (ICL) minimale:

• Specifica del dominio PDDL.
• Un singolo esempio risolto (demonstration).
• Il problema target.
  Non sono state usate strategie di prompting complesse per "guidare" il modello, forzandolo a fare affidamento sull'inferenza pura.

Verifica dell'Ottimalità:
È stato calcolato analiticamente il costo ottimo ($C_{opt}$) della pianificazione. Gli LLM (in particolare Gemini 3.0 Pro con modalità di ragionamento attivo) sono stati confrontati con:

• LAMA-2011: Un pianificatore "satisficing" (scambia l'ottimalità per la velocità).
• A/LM-Cut:* Un pianificatore ottimo classico (garantisce la soluzione più breve ma soffre dell'esplosione combinatoria).

3. Risultati Chiave

A. Inversione dell'Ottimalità (Optimality Inversion)

Il risultato più sorprendente è l'inversione delle prestazioni rispetto alla complessità:

• Pianificatori Classici: Subiscono un "muro computazionale" (hard wall) precoce. LAMA fallisce o produce piani subottimali non appena il numero di obiettivi supera ~25. A* fallisce su quasi tutti gli istanze complesse a causa dell'esplosione dello spazio di ricerca.
• LLM (Gemini 3.0 Pro): Non solo risolvono problemi molto più complessi (fino a 100+ obiettivi o torri di 1000 blocchi), ma mantengono l'ottimalità teorica quasi perfettamente. Quando l'LLM ha successo, il costo del piano generato coincide esattamente con il limite ottimo teorico, senza degradazione graduale.

B. Zone di Instabilità vs. Muri Computazionali

Mentre i pianificatori classici falliscono in modo binario a causa della memoria o del tempo, gli LLM mostrano una "zona di instabilità". In questa regione, il modello continua a generare piani ottimali fino a un certo punto, per poi passare a un fallimento completo (piani non validi o truncati) senza degradare la qualità dei piani parziali. Questo suggerisce un limite fisso nella memoria di lavoro o nella capacità di simulazione.

C. Ragionamento Topologico Puro

Per verificare che gli LLM non stiano semplicemente memorizzando euristiche semantiche (es. "smontare i blocchi sopra l'obiettivo"), gli autori hanno riformulato il problema come un problema di riscrittura di grafi astratti, rimuovendo ogni riferimento fisico (gravità, blocchi, tavolo).

• Risultato: Gli LLM hanno mantenuto alte prestazioni anche su questa formulazione astratta, dimostrando un vero ragionamento topologico e non solo un richiamo di pattern semantici.

D. Analisi del Compute di Inferenza

Analizzando i "token di pensiero" (reasoning tokens) di Gemini 3.0 Pro, è emersa una relazione lineare stretta: circa 47 token di ragionamento per ogni passo del piano ottimo.

• Questo supporta l'ipotesi che il modello esegua una Simulazione Algoritmica Attiva (Serial Algorithmic Simulation), tracciando sistematicamente le dipendenze passo dopo passo, piuttosto che fare un lookup geometrico parallelo o un guess probabilistico.

4. Contributi Principali

1. Spazio dei Problemi Multi-Scenario: Introduzione di una tassonomia basata sulla struttura $P^*$ per isolare assi di complessità specifici (altezza, larghezza, densità degli obiettivi).
2. Analisi Strutturale: Dimostrazione che il ragionamento nel Blocksworld è isomorfo alla traversata di un grafo $P^*$, permettendo di studiare come gli LLM gestiscono il recupero e l'ordinamento delle dipendenze.
3. Inversione dell'Ottimalità: Evidenza empirica che, in regimi di alta complessità strutturale, gli LLM avanzati superano i pianificatori classici sia in termini di capacità di risolvere il problema che di mantenere l'ottimalità.
4. Caratterizzazione dei Fallimenti: Distinzione tra i fallimenti dei pianificatori classici (esplosione dello spazio di ricerca) e quelli degli LLM (instabilità binaria dovuta a limiti di memoria di lavoro/simulazione).

5. Significato e Implicazioni

Questo studio sfida la visione tradizionale secondo cui gli LLM sono inadatti alla pianificazione logica complessa.

• Superamento dei limiti classici: Gli LLM, sfruttando il ragionamento attivo (chain-of-thought), riescono a decomporre spazi di ricerca esponenziali in sequenze lineari gestibili, bypassando i colli di bottiglia computazionali che bloccano gli algoritmi di ricerca simbolica.
• Meccanismo di Ragionamento: Le evidenze suggeriscono che gli LLM non stanno solo "indovinando" la prossima azione, ma stanno eseguendo una simulazione algoritmica interna, utilizzando i token di pensiero come una memoria di lavoro dinamica per tracciare lo stato del mondo e le dipendenze.
• Futuro della Ricerca: Il lavoro apre la strada a una comprensione più profonda di come i modelli di linguaggio rappresentino la topologia e la struttura dei problemi, suggerendo che per certi tipi di strutture (come $P^*$), gli LLM possono agire come pianificatori ottimali superiori agli approcci classici, purché il problema sia decomponibile in sotto-problemi indipendenti.

In sintesi, il paper dimostra che i modelli di frontiera (come Gemini 3.0) non solo "possono pianificare", ma in contesti strutturati specifici, lo fanno con un'efficienza e un'ottimalità che i sistemi simbolici tradizionali non riescono più a garantire su larga scala.