Recurrent Reasoning on Symbolic Puzzles with Sequence Models

Sintesi Tecnica: Ragionamento Ricorrente su Puzzle Simbolici con Modelli di Sequenza

Enunciato del Problema
I grandi modelli linguistici (LLM) dimostrano spesso un'apparente competenza in compiti simbolici e algoritmici, tuttavia questa prestazione maschera frequentemente un comportamento fragile quando i problemi aumentano in lunghezza, difficoltà o deviano leggermente dalla distribuzione di addestramento. I benchmark di ragionamento attuali spesso privilegiano la produzione di una risposta finale valida rispetto alla robustezza, alla minimità e alla stabilità del processo di soluzione. Questo articolo sostiene che per i problemi algoritmici, la correttezza richiede non solo un endpoint plausibile, ma la capacità di scegliere ripetutamente azioni valide, evitare transizioni illegali e mantenere la coerenza su orizzonti temporali lunghi. Gli autori postulano che il ragionamento algoritmico serva come un contesto critico per distinguere la vera robustezza dal semplice riconoscimento di pattern superficiali.

Metodologia: Il Benchmark RecurrReason
Per affrontare queste limitazioni, gli autori introducono RecurrReason, un benchmark a difficoltà controllata composto da quattro puzzle logici ricorrenti:

1. Block World: Riarrangiamento di blocchi in pile.
2. Checkers Jumping: Scambio di posizioni tra pedine rosse e blu su un tabellone lineare.
3. Torre di Hanoi: Spostamento di dischi tra pioli sotto vincoli di dimensione.
4. River Crossing: Trasporto di coppie agente-attore attraverso un fiume con vincoli di sicurezza.

Il benchmark è costruito con le seguenti caratteristiche:

• Difficoltà Scalabile: Ogni puzzle è parametrizzato da un singolo intero $N \in \{1, \dots, 10\}$.
• Traiettorie Ottimali: Tutte le istanze sono risolte utilizzando la ricerca in ampiezza (Breadth-First Search, BFS) per generare traiettorie ottimali, per un totale di 10.817 puzzle unici e 285.933 mosse.
• Formulazione del Task: Il compito è formulato come un problema di "predizione del passo successivo". I modelli ricevono lo stato corrente ($s_t$) e lo stato obiettivo ($g$) e devono predire lo stato successivo ($s_{t+1}$). La valutazione avviene tramite rollout autoregressivi senza stati intermedi di ground-truth.
• Protocollo di Valutazione: I modelli sono addestrati su istanze dove $N=1$ a $7$ e valutati su istanze fuori distribuzione (OOD) e in-distribuzione (ID) tenute in riserva ($N=1$ a $7$ per ID; $N=8$ a $10$ per OOD). Le metriche includono il tasso di successo della traiettoria, la legalità delle mosse e il gap di ottimalità.

Configurazione Sperimentale
Lo studio mette a confronto due famiglie di Transformer sotto costanti split di dati e condizioni di addestramento (da zero, zero-shot e fine-tuning):

1. Stile T5 (Encoder-Decoder): Un modello da 60 milioni di parametri (T5-small) dove l'encoder calcola l'attenzione bidirezionale sulla concatenazione dello stato e dell'obiettivo, rendendo l'obiettivo un segnale di condizionamento "di prima classe" ad ogni passo.
2. Stile GPT-2 (Decoder-Only): Un modello da 124 milioni di parametri (GPT-2) che utilizza una maschera causale, la quale impedisce ai token dello stato corrente di attendere ai token dell'obiettivo (che appaiono successivamente nella sequenza), creando un collo di bottiglia strutturale per la pianificazione orientata all'obiettivo.

Risultati Chiave
Gli esperimenti rivelano che la struttura del puzzle è un determinante della apprendibilità più forte della scala del modello o del pre-addestramento:

• Successo in Block World: Il modello T5 pre-addestrato e sottoposto a fine-tuning ha raggiunto una precisione di validazione del 97,27% e una precisione OOD dell'81,00%. Questo successo è attribuito alla funzione di transizione locale del puzzle (controllo solo della parte superiore di una pila, complessità $O(1)$), alla crescita lineare della lunghezza della soluzione ($L(N) = O(N)$) e alla densità dei segnali di addestramento.
• Fallimento sugli altri Puzzle:
  • River Crossing: Tutti i modelli hanno ottenuto uno score dello 0,00% in tutte le condizioni. Il puzzle richiede la verifica di vincoli globali ($O(N)$) ad ogni passo e possiede uno spazio di azione combinatorio, che ha sconfitto tutte le architetture.
  • Torre di Hanoi: I modelli hanno raggiunto al massimo l'11,11% di precisione di validazione (solo su casi triviali $N=1$) e lo 0,00% in OOD. La lunghezza della soluzione esponenziale ($2^N - 1$) causa errori cumulativi che impediscono la generalizzazione oltre $N=1$.
  • Checkers Jumping: I modelli hanno raggiunto al massimo l'1,11% di precisione di validazione, risolvendo solo istanze triviali dove lo stato iniziale è uguale allo stato obiettivo. La lunghezza quadratica della soluzione e la necessità di evitare vicoli ciechi si sono rivelate insormontabili.
• Architettura vs Scala: Il modello T5 più piccolo (60M) ha superato significativamente il modello GPT-2 più grande (124M). Gli autori attribuiscono ciò alla capacità dell'architettura encoder-decoder di attendere bidirezionalmente all'obiettivo, mentre la maschera causale nei modelli decoder-only crea un collo di bottiglia strutturale che impedisce una pianificazione efficace anche con un maggior numero di parametri.
• Trasferimento dal Pre-addestramento: I benefici del pre-addestramento sono stati osservati solo per i puzzle con funzioni di transizione a struttura locale (Block World). Non ha fornito alcun trasferimento per i puzzle che richiedono vincoli globali (River Crossing) o decomposizione ricorsiva (Torre di Hanoi).

Analisi delle Modalità di Fallimento
Gli autori identificano specifici modi di fallimento correlati alla struttura del puzzle:

• Mosse Invalide: Hanno dominato i fallimenti nei puzzle con vincoli globali (Torre di Hanoi, River Crossing), indicando un fallimento nella generalizzazione dei vincoli.
• Loop (Cicli): La principale modalità di fallimento per Block World nei modelli decoder-only, suggerendo un apprendimento parziale delle regole senza selezione orientata all'obiettivo.
• Arresti Prematuri: Osservati in GPT-2 su Torre di Hanoi, legati alla sovrarappresentazione statistica dei token di stop nei dati di addestramento.

Significatività e Rivendicazioni
L'articolo sostiene che gli bias induttivi dell'architettura contano più della scala per il ragionamento algoritmico sistematico. Nello specifico:

1. Determinismo Strutturale: La apprendibilità di un puzzle è determinata da tre proprietà strutturali: località della transizione, dimensione dello spazio di azione e crescita della lunghezza della soluzione. Gli autori formalizzano un modello di errore cumulativo mostrando che la probabilità di successo decade esponenzialmente con la lunghezza della soluzione ($P \approx e^{-\epsilon L(N)}$).
2. Condizionamento dell'Obiettivo: Il condizionamento bidirezionale dell'obiettivo (come in T5) è critico per la pianificazione orientata all'obiettivo, mentre l'attenzione causale (come in GPT-2) crea un collo di bottiglia strutturale che impedisce una pianificazione efficace anche con un maggior numero di parametri.
3. Limiti del Pre-addestramento: Il pre-addestramento impartisce un bias induttivo gerarchico che si trasferisce solo a compiti con strutture localmente decomponibili. Non equipaggia intrinsecamente i modelli a gestire vincoli globali o profondità ricorsiva.
4. Direzioni Future: I risultati suggeriscono che il ragionamento multi-step affidabile negli LLM richieda o la ricerca di architetture (architectural search) o il controllo esplicito dei vincoli simbolici, piuttosto che il semplice aumento delle dimensioni del modello.

Gli autori concludono che RecurrReason fornisce un banco di prova controllato per il lavoro futuro sulla generalizzazione della lunghezza, la pianificazione condizionata all'obiettivo e i requisiti architettonici per il ragionamento algoritmico sistematico.