Barriers to Universal Reasoning With Transformers (And How to Overcome Them)

1. Enunciato del Problema

Sebbene il prompting Chain-of-Thought (CoT) abbia migliorato empiricamente le prestazioni dei Transformer e sia stato dimostrato teoricamente che ne aumenta l'espressività fino alla Completezza di Turing, persiste un divario critico: i Transformer possono imparare a generalizzare il ragionamento CoT a lunghezze superiori a quelle osservate durante l'addestramento?

Le evidenze empiriche esistenti suggeriscono che l'accuratezza dei Transformer degrada drasticamente all'aumentare della lunghezza della traccia CoT, anche su compiti algoritmici e logici. Il documento indaga se l'affermazione teorica della completezza di Turing regga sotto il requisito più rigoroso della apprendibilità generalizzabile per lunghezza. Nello specifico, si chiede:

• I formati CoT standard permettono ai Transformer di risolvere problemi oltre la classe di complessità $\text{TC}^0$ (circuiti a soglia a profondità costante) quando si generalizza a sequenze più lunghe?
• Quali barriere strutturali specifiche impediscono questa generalizzazione?
• È possibile superare queste barriere attraverso strategie di formattazione specifiche?

2. Metodologia

Gli autori impiegano una combinazione di formalismo teorico e validazione empirica:

Quadro Teorico

Lo studio utilizza recenti framework teorici per la generalizzazione della lunghezza nei Transformer:

• C-RASP: Un formalismo per il ragionamento sui Transformer con alfabeti finiti e codifiche posizionali. L'appartenenza implica garanzie di generalizzazione della lunghezza.
• C-RASP:* Un'estensione di C-RASP che consente un alfabeto infinito (in particolare, token segnaposto illimitati) e predicati di corrispondenza locale.
• Modello di Apprendimento: Gli autori adottano un modello di apprendimento idealizzato in cui una sequenza di Transformer addestrati su lunghezze di input crescenti converge verso un singolo algoritmo sottostante. La generalizzazione è garantita se il compito può essere espresso all'interno di questi formalismi.

Setup Empirico

• Compiti: Sono stati selezionati tre compiti di ragionamento algoritmico:
  1. Parità: Determinare se il numero di 1 in una stringa binaria è pari o dispari.
  2. Valutazione Booleana: Valutare il valore di verità di formule logiche nidificate.
  3. Permutazione S5: Tracciare lo stato di 5 oggetti dopo una serie di operazioni di scambio.
• Modelli:
  • Da zero (From-Scratch): Modelli GPT-2 (25M parametri) addestrati su tracce CoT con e senza formattazione specifica.
  • LLM Pre-addestrati: Esperimenti di prompting zero-shot e few-shot su Qwen2.5-7B, Mistral-Small-24B e Llama-3.3-70B.
• Varianti di Formattazione:
  • CoT Naive: Ragionamento sequenziale standard.
  • Token Segnaposto: Assegnazione di identificatori unici (es. <34>) a posizioni o operazioni specifiche per abilitare l'indirizzamento arbitrario.
  • Codifica delle Variazioni di Valore: Invece di registrare l'intero stato ad ogni passaggio, il modello registra solo le variazioni dei valori (es. 1 -> 0) o registra esplicitamente quando un valore rimane invariato.

3. Contributi Chiave e Risultati Teorici

Contributo 1: Il Limite degli Alfabeti Finiti (Il Risultato Negativo)

Gli autori dimostrano che, sotto codifiche posizionali standard e un alfabeto finito, i Transformer con CoT non possono generalizzare per lunghezza per risolvere problemi esterni a $\text{TC}^0$.

• Teorema 3.4: Se un linguaggio $L$ ha una traccia CoT esprimibile in C-RASP (con primitive posizionali), allora $L$ è definibile in $\text{TC}^0$.
• Implicazione: Sebbene il CoT permetta teoricamente la completezza di Turing, l'apprendibilità di tali simulazioni è limitata a $\text{TC}^0$ se il vocabolario è fisso. I benefici in termini di espressività non si traducono in apprendibilità generalizzabile per lunghezza.

Contributo 2: Superare le Barriere con Alfabeti Infiniti (Il Risultato Positivo)

Il documento identifica due barriere fondamentali alla generalizzazione della lunghezza:

1. Copia Ripetuta: La difficoltà di copiare stringhe arbitrarie in nuove posizioni.
2. Recupero dell'Ultima Occorrenza: La difficoltà di recuperare il valore più recente di una variabile quando si verificano aggiornamenti multipli (recupero non univoco).

Per superare queste, gli autori propongono una costruzione utilizzando C-RASP*:

• Token Segnaposto: Assegnazione di un token unico e illimitato (da un alfabeto infinito) a ogni posizione del nastro o passaggio operativo. Questo risolve la barriera della copia permettendo l'indicizzazione arbitraria senza memorizzare identità assolute.
• Codifica delle Variazioni di Valore: Invece di registrare l'intero stato, la traccia CoT registra solo le transizioni (es. "il valore è cambiato da $x$ a $y$"). Lo stato corrente viene recuperato contando le variazioni nette rispetto allo stato iniziale. Questo risolve la barriera del recupero rendendo il valore corrente una funzione di conteggi piuttosto che una ricerca dell'ultima occorrenza.
• Teorema 3.8: I Transformer con CoT possono generalizzare per lunghezza per simulare qualsiasi Macchina di Turing se utilizzano un alfabeto infinito di token segnaposto e codificano i calcoli tramite variazioni di valore. La lunghezza della traccia CoT rimane lineare rispetto al tempo di esecuzione simulato.

4. Risultati Empirici

Addestramento da Zero

• Parità: Il CoT standard non è riuscito a generalizzare oltre le lunghezze di addestramento. La codifica delle variazioni di valore ha permesso una generalizzazione robusta fino a $2\times$ la lunghezza di addestramento.
• Valutazione Booleana e Permutazione S5: Questi compiti più difficili (esterni a $\text{TC}^0$) hanno fallito con il CoT naive. L'aggiunta di token segnaposto ha migliorato significativamente la generalizzazione della lunghezza, sebbene S5 sia rimasto impegnativo a causa di possibili "scorciatoie" (euristiche) che il modello poteva sfruttare.
• Permutazione Binaria: Una variante di S5 con alta ripetizione. I CoT Naive e solo Segnaposto hanno fallito a causa di errori di "recupero non univoco". La combinazione di Segnaposto + Variazioni di Valore ha prodotto i migliori risultati, confermando la necessità teorica di entrambi i meccanismi.

Prompting di LLM Pre-addestrati

• Segnaposto: L'uso di numeri naturali come suggerimenti segnaposto nei prompt few-shot ha migliorato le prestazioni sui compiti Booleani e S5 per tutti gli LLM testati (da 7B a 70B), specialmente a lunghezze di sequenza maggiori.
• Variazioni di Valore: In un compito di esecuzione di codice (tracciamento degli assegnamenti di variabili), fornire commenti inline che registravano esplicitamente le variazioni di valore (es. # nodo a: 9 -> 0) ha migliorato significativamente l'accuratezza della risposta finale rispetto alla formattazione standard del codice, anche senza passaggi di ragionamento intermedi.

5. Significato e Conclusione

• Ridefinire il Successo del CoT: Il documento sostiene che il successo del CoT non è intrinseco al processo di "pensiero" stesso, ma dipende fortemente dalla formattazione della traccia. I formati CoT standard spesso falliscono nella generalizzazione perché violano i vincoli richiesti per l'apprendibilità (località e invarianza alla traduzione).
• Confini Teorici: Chiarisce che la completezza di Turing per i Transformer è condizionata. Vale per l'espressività (codificare a mano una soluzione) ma non per l'apprendibilità (addestrare un modello a generalizzare) a meno che non vengano forniti specifici aiuti strutturali (alfabeti infiniti/segnaposto).
• Linee Guida Pratiche: I risultati offrono principi attuabili per migliorare le prestazioni degli LLM su compiti di ragionamento difficili:
  1. Usare Suggerimenti di Indice: Segnare esplicitamente posizioni o passaggi con identificatori unici per facilitare il recupero.
  2. Registrare le Variazioni, non gli Stati: Formattare le tracce di ragionamento per evidenziare le transizioni di stato piuttosto che i dump completi dello stato per evitare ambiguità nel recupero.
• Direzioni Future: Il lavoro suggerisce che i futuri dati di pre-addestramento e gli schemi CoT dovrebbero essere progettati tenendo conto di questi vincoli teorici per sbloccare il pieno potenziale computazionale dei Transformer su compiti di ragionamento a lungo termine.

In sintesi, il documento dimostra che, sebbene i Transformer siano teoricamente capaci di ragionamento universale, realizzare questa capacità in modo generalizzabile per lunghezza richiede il superamento di specifiche barriere architetturali e di formattazione attraverso l'uso di token segnaposto e codifiche delle variazioni di valore.